DataMuseum.dk

top - download

    Length: 3743 (0xe9f)
    Types: TextFile
    Names: »V«

└─⟦afbc8121e⟧ Bits:30000532 8mm tape, Rational 1000, MC68020_OS2000 7_2_2
    └─ ⟦77aa8350c⟧ »DATA« 
        └─⟦f794ecd1d⟧ 
            └─⟦4c85d69e2⟧ 
                └─⟦this⟧ 

TextFile

generic
    Size : Integer;
    -- number of buckets

    type Domain_Type is private;
    type Range_Type  is private;
    -- both types are pure values
    -- no initialization or finalization of values of either
    --     domain_type or range_type is necessary
    -- = and := can be used for equality and copy

    with function Hash (Key : Domain_Type) return Integer is <>;
    -- efficiency => spread hash over an interval at least as great as size

    pragma Must_Be_Constrained (Yes => Domain_Type, Range_Type);

package Map_Generic is

    type Map is private;

    type Pair is
        record
            D : Domain_Type;
            R : Range_Type;
        end record;

    function  Eval (The_Map : Map; D : Domain_Type) return Range_Type;
    procedure Find (The_Map :        Map;
                    D       :        Domain_Type;
                    R       : in out Range_Type;
                    Success : out    Boolean);
    procedure Find (The_Map :        Map;
                    D       :        Domain_Type;
                    P       : in out Pair;
                    Success : out    Boolean);

    procedure Define   (The_Map        : in out Map;
                        D              :        Domain_Type;
                        R              :        Range_Type;
                        Trap_Multiples :        Boolean := False);
    procedure Undefine (The_Map : in out Map; D : Domain_Type);

    procedure Initialize (The_Map : out Map);
    function  Is_Empty   (The_Map : Map) return Boolean;
    procedure Make_Empty (The_Map : in out Map);

    procedure Copy (Target : in out Map; Source : Map);

    type Iterator is private;

    procedure Init  (Iter : out Iterator; The_Map : Map);
    procedure Next  (Iter : in out Iterator);
    function  Value (Iter : Iterator) return Domain_Type;
    function  Done  (Iter : Iterator) return Boolean;

    Undefined : exception;
    -- raised by eval if the domain value in not in the map

    Multiply_Defined : exception;
    -- raised by define if the domain value is already defined and
    -- the trap_multiples flag has been specified (ie. is true)

    function Cardinality (The_Map : Map) return Natural;
    function Nil                         return Map;
    function Is_Nil      (The_Map : Map) return Boolean;

    ------------------------------------------------------
    -- Implementation Notes and Non-Standard Operations --
    ------------------------------------------------------

    -- := and = operate on references
    --        := implies sharing (introduces an alias)
    --        = means is the same set, not the same value of type set
    -- Initializing a map also makes it empty
    -- Accessing an uninitialized map will raise CONSTRAINT_ERROR.

    -- garbage may be generated

    -- Concurrent Properties
    --    any number of find/eval/is_empty may be safely done while one
    --        define/undefine is taking place.  If the define is redefining
    -- an
    --        existing element in the domain of the map, concurrrent
    -- reading is
    --        safe if and only if := on range_type is atomic.

private
    type Node;
    type Set is access Node;

    type Node is
        record
            Value : Pair;
            Link  : Set;
        end record;

    subtype Index is Integer range 0 .. Size - 1;

    type Table is array (Index) of Set;

    type Map_Data is
        record
            Bucket : Table;
            Size   : Integer := 0;
        end record;

    type Map is access Map_Data;

    type Iterator is
        record
            The_Map     : Map;
            Index_Value : Index;
            Set_Iter    : Set;
            Done        : Boolean;
        end record;

end Map_Generic;