Re: Pascal Calling Convention

[stefan-lucks@see-the.signature]

On Tue, 29 Mar 2011, Georg Bauhaus wrote:

> A transliteration attempt follows, with these additions in mind.

Very nice, indeed. Here is a bare minimum version, which is closer to the 
original proposal. Note that in Ada we don't need to perform the explicit 
check for K < N, unlike C++.

pragma Profile(Ravenscar);
pragma Restrictions (No_Allocators);

generic
    type Elements is mod <>;
package USets is

    type Set is tagged private;

    function Has(This  : Set; K : Elements) return Boolean;
    -- K has been stored in This

    procedure Add(This : in out Set; K: Elements);
      -- Insert K into This. Don't do anything if K is already there.

    procedure Del(This : in out Set; K: Elements);
      -- Remove K from This. Don't do anything if K isn't there.

    procedure clr(This : in out Set);
      -- Set This to the empty set.

private
   type A_Type is array (Elements) of Elements;
   subtype Counter_Type is Integer range 0 .. Integer(Elements'Last)+1;
    type Set is tagged record
        N    : Counter_Type := 0;
        S, D : A_Type; -- if I is in Set then D(S(I))=I
    end record;
end USets;

---------

package body USets is

   function Has(This : Set; K: Elements) return Boolean is
      N: Counter_Type renames This.N;
      S: A_Type renames This.S;
      D: A_Type renames This.D;
   begin
      return Integer(S(K)) < N and then D(S(K))=K;
   end Has;

   procedure Add(This : in out Set; K: Elements) is
      N: Counter_Type renames This.N;
      S: A_Type renames This.S;
      D: A_Type renames This.D;
   begin
      if not This.Has(K) then
         D(Elements(N)) := K; S(K) := Elements(N); -- now D(S(K))=K;
         N := N + 1;
      end if;
   end Add;

   procedure Del(This : in out Set; K: Elements) is
      N: Counter_Type renames This.N;
      S: A_Type renames This.S;
      D: A_Type renames This.D;
   begin
      if This.Has(K) then
         declare
            I: Elements := S(K);
         begin
            N := N - 1;
            D(I) := D(Elements(N)); S(D(I)) := I;
         end;
      end if;
   end Del;

   procedure Clr(This : in out Set) is
      N : Counter_Type renames This.N;
   begin
      N := 0;
   end Clr;
end USets;

---------

The original C++ from Hyman Rosen was

template <unsigned N>
class set
{
    unsigned n;    // number of members in set
    unsigned d[N]; // members are in d[0..n-1]
    unsigned s[N]; // d[s[k]] == k if k is a member
    // unspecified elements of d and s are arbitrary

public:
    set() : n(0) { }
    bool has(unsigned k)
        { return k < N && s[k] < n && d[s[k]] == k; }
    void add(unsigned k)
        { if (k < N && !has(k)) { d[n] = k; s[k] = n++; }
    void del(unsigned k)
        { if (has(k)) { unsigned i = s[k]; d[i] = d[--n]; s[d[i]] = i; }
    void clr() { n = 0; }
};



-- 
------ Stefan Lucks   --  Bauhaus-University Weimar  --   Germany  ------
               Stefan dot Lucks at uni minus weimar dot de
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------