--------------------------------- COPYRIGHT ------------------------------------
-- (C) 1987 Swiss Federal Institute of Technology (EPFL).                     --
--     Represented by A. Strohmeier DMA-EPFL 1015 Lausanne Switzerland.       --
--     All Rights Reserved.                                                   --
--------------------------------------------------------------------------------

--+ TITLE: GENERIC PACKAGE FOR TABLES OF STRINGS ASSOCIATED WITH VALUES.
--+ SUPPORT: S.R.Y. Louboutin, CGL-DMA-EPFL 1015 Lausanne.
--+ APPROVAL: 03-DEC-1987 C. Genillard.
--+ CREATION: 13-AUG-1987 A. Strohmeier.

with Table_Of_Dynamic_Keys_And_Dynamic_Values_G;
generic
    with function Less (Left, Right : String) return Boolean;
    -- Defines ordering of strings.
    with function Equals (Left, Right : String) return Boolean;
    -- Defines equality between strings.

    type Value_Type is limited private;
    with procedure Assign (Destination : in out Value_Type;
                           Source : in Value_Type);
    -- Assigns SOURCE to DESTINATION. If needed, DESTINATION has to be destroyed
    -- before assignement, since ASSIGN is called without a previous call to
    -- DESTROY in the implementation of the package.
    with procedure Destroy (Value : in out Value_Type);
package Table_Of_Strings_And_Dynamic_Values_G is

--+ OVERVIEW:
--+   This package provides associative tables of unlimited dynamic size with
--+ entries of type (STRING, VALUE_TYPE), where VALUE_TYPE is specified by a
--+ generic parameter. Such a couple will also be called an item. The string
--+ component acts as a key. Its length is varying.
--+   The type TABLE_TYPE is implemented in such a way that every object
--+ has the implied initial value of an empty table.
--+   Two items (s1, v1) and (s2, v2) have same key if and only if
--+ EQUALS (s1, s2).
--+    A table may not contain duplicate items, that is items with same key.
--+   The following consistency condition must be fullfilled by the relational
--+ operation LESS and EQUALS:
--+   (i)  EQUALS (s1, s2) implies not LESS (s1, s2) and not LESS (s2, s1)
--+   (ii) not LESS (s1, s2) and not EQUALS (s1, s2) implies LESS (s2, s1)
--+   In our terminology, a static type is a type which is neither a limited
--+ type nor an access type. When an actual generic access type is associated
--+ with a generic static type, objects would be shared, i.e. only the access
--+ value would be stored, without copying the accessed object.
--+   On the opposite, a dynamic type may be limited or an access type.
--+ However a dynamic type must have the feature that every object has an
--+ implied initial value.
--+   Depending on the very nature of the type VALUE_TYPE, one of the provided
--+ packages has to be used:
--+ TABLE_OF_STRINGS_AND_DYNAMIC_VALUES_G
--+ TABLE_OF_STRINGS_AND_STATIC_VALUES_G
--+
--+ CAUTION:
--+   Functions which return the value of an item (or part of it) of the
--+ structure share the item with the structure and do not return a copy of it.
--+ This may have consequences if the type of the item, (or some component of
--+ it) is an access type. For instance, when accessing an item by a function
--+ call, this item must not be destroyed or modified during the query.
--+
--+ PRIMITIVES:
--+   CONSTRUCTORS:
--+     ASSIGN
--+     INSERT (2)
--+     INSERT_OR_REPLACE_VALUE
--+     REPLACE_VALUE (2)
--+     REMOVE (3)
--+     REMOVE_MIN (3)
--+     REMOVE_MAX (3)
--+     UPDATE_VALUE_OR_EXCEPTION_G
--+     UPDATE_VALUE_OR_STATUS_G
--+   QUERIES:
--+     SIZE
--+     IS_EMPTY
--+     IS_PRESENT
--+     VALUE
--+     GET_VALUE
--+     GET_MIN_ITEM
--+     GET_MAX_ITEM
--+     MIN_KEY
--+     GET_MIN_KEY
--+     MAX_KEY
--+     GET_MAX_KEY
--+     GET_LESS_ITEM
--+     GET_LESS_OR_EQUAL_ITEM
--+     GET_GREATER_ITEM
--+     GET_GREATER_OR_EQUAL_ITEM
--+     LESS_KEY
--+     GET_LESS_KEY
--+     LESS_OR_EQUAL_KEY
--+     GET_LESS_OR_EQUAL_KEY
--+     GREATER_KEY
--+     GET_GREATER_KEY
--+     GREATER_OR_EQUAL_KEY
--+     GET_GREATER_OR_EQUAL_KEY
--+   SET_OPERATIONS:
--+     SET_OPERATIONS_G
--+       UNION
--+       INTERSECTION
--+       DIFFERENCE
--+       SYMMETRIC_DIFFERENCE
--+       "=" (set equality)
--+       "<" (strict set inclusion)
--+       "<=" (set inclusion)
--+       ">" (strict set inclusion)
--+       ">=" (set inclusion)
--+   ITERATORS:
--+     TRAVERSE_ASC_G
--+     TRAVERSE_DESC_G
--+     TRAVERSE_ASC_AND_UPDATE_VALUE_G
--+     TRAVERSE_DESC_AND_UPDATE_VALUE_G
--+     DISORDER_TRAVERSE_G
--+     DISORDER_TRAVERSE_AND_UPDATE_VALUE_G
--+   HEAP MANAGEMENT:
--+     DESTROY
--+     RELEASE_FREE_LIST
--+     SET_MAX_FREE_LIST_SIZE
--+     FREE_LIST_SIZE
--+
--+ ALGORITHM:
--+    A table is implemented as a balanced search binary tree (AVL-tree)
--+ using pointers. The items are sorted in the tree by increasing keys in
--+ conformance to inorder.
--+    An internal free list is used to avoid returning each free item (i.e.
--+ coming from REMOVE) to the system, so long as the length of this list does
--+ not exceed MAX_FREE_LIST_SIZE, in which case the free item is immediately
--+ returned to the system. When a new item has to be inserted (i.e. by a call
--+ to INSERT), an element is recovered from the free list if it is not empty.
--+ Otherwise, new space is taken from the system.


    type Table_Type is limited private;

    Duplicate_Item_Error, Missing_Item_Error, Empty_Structure_Error : exception;
    String_Constraint_Error : exception;

--/ CONSTRUCTORS:

    procedure Assign (Destination : in out Table_Type; Source : in Table_Type);
    --+ OVERVIEW:
    --+   Begins by a call to DESTROY (DESTINATION) and then copies SOURCE into
    --+ DESTINATION. Note the "in out" mode of the formal parameter DESTINATION.

    procedure Insert (Table : in out Table_Type;
                      Key : in String;
                      Value : in Value_Type);
    --+ OVERVIEW:
    --+   Inserts the couple (KEY, VALUE) into TABLE.
    --+ ERROR:
    --+   If an entry with the given key is already in the table, then exception
    --+ DUPLICATE_ITEM_ERROR is raised.

    procedure Insert (Table : in out Table_Type;
                      Key : in String;
                      Value : in Value_Type;
                      Duplicate_Item : out Boolean);
    --+ OVERVIEW:
    --+   Inserts the couple (KEY, VALUE) into TABLE. No action is taken and no
    --+ error occurs if an entry with the given key is already in the table
    --+ except that DUPLICATE_ITEM is set to true.

    procedure Insert_Or_Replace_Value (Table : in out Table_Type;
                                       Key : in String;
                                       Value : in Value_Type);
    --+ OVERVIEW:
    --+   Inserts the couple (KEY, VALUE) into TABLE if there is no entry with
    --+ this key. Otherwise the given VALUE replaces the previous one.

    procedure Replace_Value (Table : in out Table_Type;
                             Key : in String;
                             Value : in Value_Type);
    --+ OVERVIEW:
    --+   An entry having key KEY is searched for in TABLE. The given VALUE then
    --+ replaces the previous one.
    --+ ERROR:
    --+   If there is no entry with the given key, the exception
    --+ MISSING_ITEM_ERROR is raised.

    procedure Replace_Value (Table : in out Table_Type;
                             Key : in String;
                             Value : in Value_Type;
                             Found : out Boolean);
    --+ OVERVIEW:
    --+   An entry having key KEY is searched for in TABLE. The given VALUE then
    --+ replaces the previous one. No action is taken and no error occurs if
    --+ there is no entry with the given key, except that FOUND is set to false.

    procedure Remove (Table : in out Table_Type; Key : in String);
    procedure Remove (Table : in out Table_Type;
                      Key : in String;
                      Value : in out Value_Type);
    --+ OVERVIEW:
    --+   Removes the entry with key KEY from TABLE and returns in parameter
    --+ VALUE, if present, the associated VALUE.
    --+ ERROR:
    --+   If there is no entry with the given key, the exception
    --+ MISSING_ITEM_ERROR is raised.


    procedure Remove (Table : in out Table_Type;
                      Key : in String;
                      Found : out Boolean);
    --+ OVERVIEW:
    --+   Removes the entry with key KEY from TABLE. No action is taken and no
    --+ error occurs if there is no entry with the given key value, except that
    --+ FOUND is set to false.

    procedure Remove_Min (Table : in out Table_Type);
    --+ OVERVIEW:
    --+   Removes the entry with the smallest key from TABLE.
    --+ ERROR:
    --+   Raises EMPTY_STRUCTURE_ERROR if TABLE is empty.

    procedure Remove_Max (Table : in out Table_Type);
    --+ OVERVIEW:
    --+   Removes the entry with the greatest key from TABLE.
    --+ ERROR:
    --+   Raises EMPTY_STRUCTURE_ERROR if TABLE is empty.

    generic
        with procedure Modify (Key : in String;
                               Value : in out Value_Type) is <>;
    procedure Update_Value_Or_Exception_G
                 (Table : in out Table_Type; Key : in String);
    --+ OVERVIEW:
    --+   An entry with key KEY is searched for in TABLE. The associated item is
    --+ then passed to procedure MODIFY for modification of its value part.
    --+ ERROR:
    --+   Raises MISSING_ITEM_ERROR if KEY is not in TABLE.

    generic
        with procedure Modify (Key : in String;
                               Value : in out Value_Type) is <>;
    procedure Update_Value_Or_Status_G (Table : in out Table_Type;
                                        Key : in String;
                                        Found : out Boolean);
    --+ OVERVIEW:
    --+   An entry with key KEY is searched for in TABLE. The associated item is
    --+ then passed to procedure MODIFY for modification of its value part. No
    --+ action is taken and no error occurs if there is no entry with the given
    --+ key, except that FOUND is set to false.

--/ QUERIES:


    function Size (Table : Table_Type) return Natural;
    --+ OVERVIEW:
    --+   Returns the number of entries currently in TABLE.

    function Is_Empty (Table : Table_Type) return Boolean;
    --+ OVERVIEW:
    --+   Returns TRUE if and only if the TABLE is empty.

    function Is_Present (Table : Table_Type; Key : String) return Boolean;
    --+ OVERVIEW:
    --+   Returns TRUE if and only if an ITEM with key KEY is in TABLE.

    function Value (Table : Table_Type; Key : String) return Value_Type;

    procedure Get_Value (Table : in Table_Type;
                         Key : in String;
                         Value : in out Value_Type);
    --+ OVERVIEW:
    --+   Gives the VALUE associated with KEY in TABLE.
    --+ ERROR:
    --+   Raises MISSING_ITEM_ERROR if KEY is not found in TABLE.

    procedure Get_Min_Item (Table : in Table_Type;
                            Key : out String;
                            Last : out Natural;
                            Value : in out Value_Type);
    --+ OVERVIEW:
    --+   Gives the smallest KEY and the VALUE associated with it in TABLE;
    --+ returns in LAST the index value such that KEY(LAST) is the last character
    --+ replaced.
    --+ ERROR:
    --+   Raises EMPTY_STRUCTURE_ERROR if TABLE is empty.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY is too short.

    procedure Get_Max_Item (Table : in Table_Type;
                            Key : out String;
                            Last : out Natural;
                            Value : in out Value_Type);
    --+ OVERVIEW:
    --+   Gives the biggest KEY and the VALUE associated with it in TABLE;
    --+ returns in LAST the index value such that KEY(LAST) is the last character
    --+ replaced.
    --+ ERROR:
    --+   Raises EMPTY_STRUCTURE_ERROR if TABLE is empty.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY is too short.

    function Min_Key (Table : Table_Type) return String;
    --+ OVERVIEW:
    --+   Gives the smallest KEY of TABLE.
    --+ ERROR:
    --+   Raises EMPTY_STRUCTURE_ERROR if TABLE is empty.

    procedure Get_Min_Key
                 (Table : in Table_Type; Key : out String; Last : out Natural);
    --+ OVERVIEW:
    --+   Gives the smallest KEY of TABLE; returns in LAST the index value such
    --+ that KEY(LAST) is the last character replaced.
    --+ ERROR:
    --+   Raises EMPTY_STRUCTURE_ERROR if TABLE is empty.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY is too short.

    function Max_Key (Table : Table_Type) return String;
    --+ OVERVIEW:
    --+   Gives the biggest KEY of TABLE.
    --+ ERROR:
    --+   Raises EMPTY_STRUCTURE_ERROR if TABLE is empty.

    procedure Get_Max_Key
                 (Table : in Table_Type; Key : out String; Last : out Natural);
    --+ OVERVIEW:
    --+   Gives the biggest KEY of TABLE; returns in LAST the index value such
    --+ that KEY(LAST) is the last character replaced.
    --+ ERROR:
    --+   Raises EMPTY_STRUCTURE_ERROR if TABLE is empty.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY is too short.

    procedure Get_Less_Item (Table : in Table_Type;
                             Key_In : in String;
                             Key_Out : out String;
                             Last : out Natural;
                             Value : in out Value_Type);
    --+ OVERVIEW:
    --+   Gives the entry (KEY_OUT, VALUE) having the greatest key value less
    --+ than the value of the parameter KEY_IN; returns in LAST the index value
    --+ such that KEY_OUT(LAST) is the last character replaced.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such
    --+ an entry in the table.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY_OUT is too short.

    procedure Get_Less_Or_Equal_Item (Table : in Table_Type;
                                      Key_In : in String;
                                      Key_Out : out String;
                                      Last : out Natural;
                                      Value : in out Value_Type);
    --+ OVERVIEW:
    --+   Gives the entry (KEY_OUT, VALUE) having the greatest key value less
    --+ than or equal to the value of the parameter KEY_IN; returns in LAST the
    --+ index value such that KEY_OUT(LAST) is the last character replaced.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY_OUT is too short.

    procedure Get_Greater_Item (Table : in Table_Type;
                                Key_In : in String;
                                Key_Out : out String;
                                Last : out Natural;
                                Value : in out Value_Type);
    --+ OVERVIEW:
    --+   Gives the entry (KEY_OUT, VALUE) having the smallest key value greater
    --+ than the value of the parameter KEY_IN; returns in LAST the index value
    --+ such that KEY_OUT(LAST) is the last character replaced.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY_OUT is too short.

    procedure Get_Greater_Or_Equal_Item (Table : in Table_Type;
                                         Key_In : in String;
                                         Key_Out : out String;
                                         Last : out Natural;
                                         Value : in out Value_Type);
    --+ OVERVIEW:
    --+   Gives the entry (KEY_OUT, VALUE) having the smallest key value greater
    --+ than or equal to the value of the parameter KEY_IN; returns in LAST the
    --+ index value such that KEY_OUT(LAST) is the last character replaced.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY_OUT is too short.

    function Less_Key (Table : Table_Type; Key : String) return String;
    --+ OVERVIEW:
    --+   Gives the greatest key value less than the value of the parameter KEY.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.

    procedure Get_Less_Key (Table : in Table_Type;
                            Key_In : in String;
                            Key_Out : out String;
                            Last : out Natural);
    --+ OVERVIEW:
    --+   Gives in KEY_OUT the greatest key value less than the value of the
    --+ parameter KEY_IN; returns in LAST the index value such that KEY_OUT(LAST)
    --+ is the last character replaced.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY_OUT is too short.

    function Less_Or_Equal_Key (Table : Table_Type; Key : String) return String;
    --+ OVERVIEW:
    --+   Gives the greatest key value less than or equal to the value of the
    --+ parameter KEY.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.

    procedure Get_Less_Or_Equal_Key (Table : in Table_Type;
                                     Key_In : in String;
                                     Key_Out : out String;
                                     Last : out Natural);
    --+ OVERVIEW:
    --+   Gives in KEY_OUT the greatest key value less than or equal to the value
    --+ of the parameter KEY_IN; returns in LAST the index value such that
    --+ KEY_OUT(LAST) is the last character replaced.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY_OUT is too short.

    function Greater_Key (Table : Table_Type; Key : String) return String;
    --+ OVERVIEW:
    --+   Gives the smallest key value greater than the value of the parameter
    --+ KEY.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.

    procedure Get_Greater_Key (Table : in Table_Type;
                               Key_In : in String;
                               Key_Out : out String;
                               Last : out Natural);
    --+ OVERVIEW:
    --+   Gives in KEY_OUT the smallest key value greater than the value of the
    --+ parameter KEY_IN; returns in LAST the index value such that KEY_OUT(LAST)
    --+ is the last character replaced.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY_OUT is too short.

    function Greater_Or_Equal_Key
                (Table : Table_Type; Key : String) return String;
    --+ OVERVIEW:
    --+   Gives the smallest key value greater than or equal to the
    --+ value of the parameter KEY.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such an
    --+ entry in the table.

    procedure Get_Greater_Or_Equal_Key (Table : in Table_Type;
                                        Key_In : in String;
                                        Key_Out : out String;
                                        Last : out Natural);
    --+ OVERVIEW:
    --+   Gives in KEY_OUT the smallest key value greater than or equal to the
    --+ value of the parameter KEY_IN; returns in LAST the index value such that
    --+ KEY_OUT(LAST) is the last character replaced.
    --+ ERROR:
    --+   The exception MISSING_ITEM_ERROR is raised if there is not such
    --+ an entry in the table.
    --+   Raises STRING_CONSTRAINT_ERROR if KEY_OUT is too short.

    --/ SET_OPERATIONS:

    generic
    package Set_Operations_G is

        procedure Union (Destination : in out Table_Type;
                         Left, Right : in Table_Type);
        --+ OVERVIEW:
        --+   Union of LEFT and RIGHT. If a key is both in LEFT and RIGHT, the
        --+ value is taken from LEFT.

        procedure Intersection (Destination : in out Table_Type;
                                Left, Right : in Table_Type);
        --+ OVERVIEW:
        --+   Intersection of LEFT and RIGHT. The entries are taken from LEFT.

        procedure Difference (Destination : in out Table_Type;
                              Left, Right : in Table_Type);
        --+ OVERVIEW:
        --+   Set difference of LEFT and RIGHT. An entry is in the resulting table
        --+ if it is in LEFT and if there is no entry with same key in RIGHT.

        procedure Symmetric_Difference (Destination : in out Table_Type;
                                        Left, Right : in Table_Type);
        --+ OVERVIEW:
        --+   Symmetric set difference of LEFT and RIGHT. An entry is in the
        --+ resulting table if it is in LEFT but there is no entry with same key
        --+ in RIGHT or if it is in RIGHT but there is no entry with same key in
        --+ LEFT.

        function "=" (Left, Right : Table_Type) return Boolean;
        --+ OVERVIEW:
        --+   Set equality; the LEFT and RIGHT tables contain entries with same
        --+ keys.

        function "<" (Left, Right : Table_Type) return Boolean;
        --+ OVERVIEW:
        --+   Strict set inclusion; to each entry in the LEFT table an entry with
        --+ same key is associated in the RIGHT table, but the two sets are not
        --+ identical.

        function "<=" (Left, Right : Table_Type) return Boolean;
        --+ OVERVIEW:
        --+   Set inclusion; to each entry in the LEFT table an entry with same
        --+ key is associated in the RIGHT table.

        function ">" (Left, Right : Table_Type) return Boolean;
        --+ OVERVIEW:
        --+   Strict set inclusion; to each entry in the RIGHT table an entry with
        --+ same key is associated in the LEFT table, but the two sets are not
        --+ identical.

        function ">=" (Left, Right : Table_Type) return Boolean;
        --+ OVERVIEW:
        --+   Set inclusion; to each entry in the RIGHT table an entry with same
        --+ key is associated in the LEFT table.

    end Set_Operations_G;

--/ ITERATORS:

    generic
        with procedure Action (Key : in String;
                               Value : in Value_Type;
                               Order_Number : in Positive;
                               Continue : in out Boolean) is <>;
    procedure Traverse_Asc_G (Table : in Table_Type);
    --+ OVERVIEW:
    --+   The entries in TABLE are visited in ascending order of their key
    --+ values. Procedure ACTION is applied on each entry within TABLE.
    --+   ORDER_NUMBER gives the position of the visited entry in order of
    --+ traversal. The boolean CONTINUE specifies if you want to proceed to the
    --+ next entry or if you want to stop traversing. As long as you do not
    --+ modify its value within ACTION, its value remains TRUE.
    --+ REQUIREMENT:
    --+   For your actual procedure  ACTION, you must not use a procedure
    --+ which modifies the traversed table.


    generic
        with procedure Action (Key : in String;
                               Value : in Value_Type;
                               Order_Number : in Positive;
                               Continue : in out Boolean) is <>;
    procedure Traverse_Desc_G (Table : in Table_Type);
    --+ OVERVIEW:
    --+   The entries in TABLE are visited in descending order of their key
    --+ values. Procedure ACTION is applied on each entry within TABLE.
    --+   ORDER_NUMBER gives the position of the visited entry in order of
    --+ traversal. The boolean CONTINUE specifies if you want to proceed to the
    --+ next entry or if you want to stop traversing. As long as you do not
    --+ modify its value within ACTION, its value remains TRUE.
    --+ REQUIREMENT:
    --+   For your actual procedure  ACTION, you must not use a procedure
    --+ which modifies the traversed table.

    generic
        with procedure Modify (Key : in String;
                               Value : in out Value_Type;
                               Order_Number : in Positive;
                               Continue : in out Boolean) is <>;
    procedure Traverse_Asc_And_Update_Value_G (Table : in out Table_Type);
    --+ OVERVIEW:
    --+   The entries in TABLE are visited in ascending order of their key
    --+ values. For each visited entry, procedure MODIFY is called. The value of
    --+ the current entry is then replaced by the new value.
    --+   ORDER_NUMBER gives the position of the visited entry in order of
    --+ traversal. The boolean CONTINUE specifies if you want to proceed to the
    --+ next entry or if you want to stop traversing. As long as you do not
    --+ modify its value within MODIFY, its value remains TRUE.
    --+ REQUIREMENT:
    --+   For your actual procedure MODIFY, you must not use a procedure which
    --+ modifies the traversed table.

    generic
        with procedure Modify (Key : in String;
                               Value : in out Value_Type;
                               Order_Number : in Positive;
                               Continue : in out Boolean) is <>;
    procedure Traverse_Desc_And_Update_Value_G (Table : in out Table_Type);
    --+ OVERVIEW:
    --+   The entries in TABLE are visited in descending order of their key
    --+ values. For each visited entry, procedure MODIFY is called. The item
    --+ value of the current entry is then replaced by the new value.
    --+   ORDER_NUMBER gives the position of the visited entry in order of
    --+ traversal. The boolean CONTINUE specifies if you want to proceed to the
    --+ next entry or if you want to stop traversing. As long as you do not
    --+ modify its value within MODIFY, its value remains TRUE.
    --+ REQUIREMENT:
    --+   For your actual procedure MODIFY, you must not use a procedure which
    --+ modifies the traversed table.

    generic
        with procedure Action (Key : in String;
                               Value : in Value_Type;
                               Order_Number : in Positive;
                               Continue : in out Boolean) is <>;
    procedure Disorder_Traverse_G (Table : in Table_Type);
    --+ OVERVIEW:
    --+   The entries in TABLE are visited in disorder of their key values.
    --+ procedure ACTION is applied on each entry within TABLE.
    --+   ORDER_NUMBER gives the position of the visited entry in order of
    --+ traversal. The boolean CONTINUE specifies if you want to proceed to the
    --+ next entry or if you want to stop traversing. As long as you do not
    --+ modify its value within ACTION, its value remains TRUE.
    --+   Traversal by DISORDER_TRAVERSE_G is faster than by TRAVERSE_ASC_G or
    --+ TRAVERSE_DESC_G. Moreover, use of the generic procedure
    --+ DISORDER_TRAVERSE_G is recommended for saving a table in a backstore
    --+ (file or linear list) because recovery will be efficient.
    --+ REQUIREMENT:
    --+   For your actual procedure  ACTION, you must not use a procedure
    --+ which modifies the traversed table.

    generic
        with procedure Modify (Key : in String;
                               Value : in out Value_Type;
                               Order_Number : in Positive;
                               Continue : in out Boolean) is <>;
    procedure Disorder_Traverse_And_Update_Value_G (Table : in out Table_Type);
    --+ OVERVIEW:
    --+   The entries in TABLE are visited in disorder of their key values.
    --+ procedure MODIFY is applied on each entry within TABLE. The item
    --+ value of the current entry is then replaced by the new value.
    --+   ORDER_NUMBER gives the position of the visited entry in order of
    --+ traversal. The boolean CONTINUE specifies if you want to proceed to the
    --+ next entry or if you want to stop traversing. As long as you do not
    --+ modify its value within MODIFY, its value remains TRUE.
    --+   Traversal by DISORDER_TRAVERSE_G is faster than by TRAVERSE_ASC_G or
    --+ TRAVERSE_DESC_G.
    --+ REQUIREMENT:
    --+   For your actual procedure  MODIFY, you must not use a procedure
    --+ which modifies the traversed table.

--/ HEAP MANAGEMENT:

    procedure Destroy (Table : in out Table_Type);
    --+ OVERVIEW:
    --+   Empties the TABLE and returns space to the free list.

    procedure Release_Free_List;
    --+ OVERVIEW:
    --+   Releases all items from the free list giving their space back to the
    --+ system.


    procedure Set_Max_Free_List_Size (Max_Free_List_Size : in Natural);
    --+ OVERVIEW:
    --+   Sets the maximum length of the internal free list which is 0 by default.
    --+ If parameter MAX_FREE_LIST_SIZE is smaller than the current size
    --+ of the list, the items in excess are returned to the system.


    function Free_List_Size return Natural;
    --+ OVERVIEW:
    --+   Returns the actual length of the internal free list.

private
    type Access_String_Type is access String;
    function Less (Left, Right : Access_String_Type) return Boolean;
    function Equals (Left, Right : Access_String_Type) return Boolean;
    procedure Assign (Destination : in out Access_String_Type;
                      Source : in Access_String_Type);
    procedure Destroy (Access_String : in out Access_String_Type);

    package Local_Package is new Table_Of_Dynamic_Keys_And_Dynamic_Values_G
                                    (Access_String_Type, Less, Equals, Assign,
                                     Destroy, Value_Type, Assign, Destroy);
    type Table_Type is new Local_Package.Table_Type;
end Table_Of_Strings_And_Dynamic_Values_G;