Generic Map Package in Ada 95

Developed By: George Chastain

Download Source

Some time ago, I developed a generic package that implemented a mapped ordered list.   This generic package allows the client to instantiate an ordered list of any type of data and map each element in the list to a key.  The key may also be any type of data, including a record type.  The package, GENERIC_MAP has been used often.

This class may be used in declaring and manipulating objects containing a list of data ordered by a specific, primary key. The list may contain multiple entries with the same primary key. They are not required to be unique.  All memory-management for objects of the class is automatically handled by the class.

This kinda-sorta-somewhat implements the basic functionality of the multimap container class template in the C++ Standard Template Library for those of you familiar with C++.

The real power comes from the generics that the instantiation of this generic package provides.

IMPORTANT: INSTANTIATING THIS GENERIC PACKAGE DOES NOT CREATE ANY Ordered Map. IT SIMPLY PROVIDES THE TYPES AND FUNCTIONALITY FOR MANIPULATING ORDERED Ordered Map OF A SPECIFIED TYPE.

GENERIC FORMAL PARAMETERS

This section describes the Generic Formal Parameters that MUST be supplied for an instantiation of this package.

ELEMENT_TYPE

The Generic Actual Paramter specified for this Generic Formal Parameter should be the type to be used for each entry in the Ordered Map.

 

KEYTYPE

The Generic Actual Parameter specified for this Generic Formal Parameter should be the type to be used for the primary key contained within each entry of the Ordered Map. The Ordered Map is always ordered according to the primary key. ELEMENT_TYPE should contain the KEYTYPE key or it should be the same type.

 

function OrderCompare(Key1 : in KEYTYPE; Key2 : in KEYTYPE) return Boolean is <>;

The Generic Actual Parameter specified for this Generic Formal Subprogram is used to control the order of the list. This function is used when an item is inserted into the list to control the ordering of the entries in the list. The client-specified function should compare Key1 to Key2 and return TRUE if Key1 is logically less than Key2.

 

function keyequal(Key1 : in KEYTYPE; Key2 : in KEYTYPE) return Boolean;

The Generic Actual Parameter specified for this Generic Formal Subprogram is used to check to see if two keys are equal.

PUBLIC DATA TYPES

This section describes the data types available to the client by an instantiation of this generic package.

type ORDERED_MAP_TYPE is private;

Used in declaring objects containing an Ordered Map.

 

type OCCURRENCE_TYPE is (FIRST, LAST, EVERY, NOT_DEFINED);

Used in by the search and delete subprograms to specify which occurrence(s) of item(s) to return or delete.

PUBLIC INTERFACES

This section describes the public interfaces for the Generic Ordered Map.  The Ordered_Map type maintains a Location Pointer within the Ordered Map.  Search functions, as well as the Next(), Prev, GetData() and UpdateData() all utilize and/or update the Location Pointer. Details will be noted below in the discussions of the individual public interfaces.

procedure Insert(Ordered_Map : in out ORDERED_MAP_TYPE;  
                 Key : in KEYTYPE;  
                 Item : in ELEMENT_TYPE);

Used to add an element to the Ordered Map, "Ordered_Map".  The new element is inserted into the list based on the criteria defined by the OrderCompare() function supplied by the client when this generic is instantiated. The Location Pointer within the Ordered_Map will be updated to point to the location of the newly inserted item.

 

function Size(Ordered_Map : in ORDERED_MAP_TYPE) return integer;

Returns the number of entries in "Ordered_Map".

procedure Delete(Ordered_Map : in out ORDERED_MAP_TYPE; 
                 Key         : in KEYTYPE; 
                 Occurrence  : in OCCURRENCE_TYPE);

Used to delete the data from the Ordered Map, "Ordered_Map" containing the specified primary key, "Key", according to the setting of "Occurrence". The caller may specify Occurrence as follows:

FIRST -- Deletes the first occurrence of an item containing primary key "Key".

LAST -- Deletes the last occurrence of an item containing primary key "Key".

EVERY -- Deletes all occurrences of items containing primary key "Key".

If the Location Pointer was positioned at the item that is being deleted, the Location Pointer will be updated to "point" to the item AFTER the one that is being deleted unless it was positioned at the end of the list. In that case, the Location Pointer will be positioned at the new end of the list.

function Search(Ordered_Map : in ORDERED_MAP_TYPE; 
                Key         : in KEYTYPE; 
                Occurrence  : in OCCURRENCE_TYPE := EVERY; 
                DeleteFlag  : in Boolean := FALSE ) return ORDERED_MAP_TYPE;

Returns the data stored in the Ordered Map, "Ordered_Map" containing the specified primary key, "Key".  The function returns a list of type ORDERED_MAP_TYPE. The returned list may contain more than one item if there were multiple entries in the list containing the same key.  NOTE: The Ordered Map is always ordered by KEYTYPE. The caller may specify Occurrence as follows:

FIRST -- Searches the first occurrence of an item containing primary key "Key".

LAST -- Searches the last occurrence of an item containing primary key "Key".

EVERY -- Searches all occurrences of items containing primary key "Key".

If the client sets the "DeleteFlag" parameter to TRUE on the call, then any and all items found and returned will ALSO be deleted from the Ordered Map, "Ordered_Map".  If the Location Pointer was positioned at an item that was deleted, the Location Pointer will be repositioned according to the rules set forth in the description for the Delete() interface above.  If the Search() was performed for the FIRST occurrence of a Key, and that item is found, the Location Pointer will be repositioned to that entry. If the Search() was performed for EVERY occurrence of a Key or for the LAST occurence of the Key, the Location Pointer will be repositioned at the LAST entry for the Key in the  Ordered_Map.

function DoesThisKeyExist(Ordered_Map : in out ORDERED_MAP_TYPE; 
                          Key         : in KEYTYPE) return Boolean;

Returns TRUE if the specified Key is present in the Ordered Map. That is, it returns TRUE if there is AT LEAST ONE entry in the Ordered Map for that key.  This allows the client to make a "quick" check of the Ordered Map for the presence of an key without the added overhead of returning data for one or more entries associated with the specified key.

procedure GetFirst(Ordered_Map : in out ORDERED_MAP_TYPE; 
                   Key         : in KEYTYPE; 
                   Result      : out ELEMENT_TYPE; 
                   DeleteFlag  : in Boolean := FALSE);

Returns the first occurrence of an entry with the specified Key. The entry is returned in "Result".  The same rules apply to the handling of the Location Pointer by an instantiation of the Generic_Search() procedure as are discussed in the description of Search() above.

procedure Clear(Ordered_Map : in out ORDERED_MAP_TYPE);

Frees up all memory allocated to the Ordered Map. Note that the allocated memory is also automatically freed when an object of type ORDERED_MAP_TYPE is destroyed.

procedure GetBegin(Ordered_Map : in ORDERED_MAP_TYPE; 
                   Key         : out KEYTYPE; 
                   Item        : out ELEMENT_TYPE);

Returns the item in the Ordered Map "Ordered_Map" that is at the beginning of the list. Depending on how the OrderCompare function behaves, this could be either the logically smallest or the logically largest item in the list.  The Location Pointer is positioned at the beginning of the Ordered_Map.

procedure GetEnd(Ordered_Map : in ORDERED_MAP_TYPE; 
                 Key         : out KEYTYPE; 
                 Item        : out ELEMENT_TYPE);

Returns the item in the Ordered Map "Ordered_Map" that is at the end of the list. Depending on how the OrderCompare function behaves, this could be either the logically smallest or the logically largest item in the list.  The Location Pointer is positioned at the end of the Ordered_Map.

procedure PopBegin(Ordered_Map : in out ORDERED_MAP_TYPE; 
                   Key         : out KEYTYPE; 
                   Item        : out ELEMENT_TYPE);

Returns the item in the Ordered Map "Ordered_Map" that is at the beginning of the list. Depending on how the OrderCompare function behaves, this could be either the logically smallest or the logically largest item in the list. It also removes that item from the list.  The Location Pointer is unchanged if it was not positioned at the beginning of the Ordered_Map. If it was positioned at the beginning of the Ordered_Map, it will be repositioned to the new starting entry of the list. If there was only one entry in the list when PopBegin() is called, the Location Pointer will be 0.

procedure PopEnd(Ordered_Map : in out ORDERED_MAP_TYPE; 
                 Key         : out KEYTYPE; 
                 Item        : out ELEMENT_TYPE);

Returns the item in the Ordered Map "Ordered_Map" that is at the end of the list. Depending on how the OrderCompare function behaves, this could be either the logically smallest or the logically largest item in the list.   It also removes that item from the list.  The Location Pointer is unchanged if it was not positioned at the end of the Ordered_Map. If it was positioned at the end of the Ordered_Map, it will be repositioned to the new end entry of the list. If there was only one entry in the list when PopEnd() is called, the Location Pointer will be 0.

procedure Next(Ordered_Map : in out ORDERED_MAP_TYPE);

Moves the Location Poniter to the next item in the Ordered_Map. If the Location Pointer was at the end of the list when the client calls Next(), CONSTRAINT_ERROR is raised.

procedure Prev(Ordered_Map : in out ORDERED_MAP_TYPE);

Moves the Location Poniter to the previous item in the Ordered_Map. If the Location Pointer was at the beginning of the list when the client calls Prev(), CONSTRAINT_ERROR is raised.

procedure GetData(Ordered_Map : in ORDERED_MAP_TYPE; 
                  Key         : out KEYTYPE; 
                  Item        : out ELEMENT_TYPE);

The GetData() procedure allows the client to obtain the key and the associated data from the position of the Location Pointer.

procedure UpdateData(Ordered_Map : in ORDERED_MAP_TYPE; 
                     Item        : in ELEMENT_TYPE);

The UpdateData() procedure allows the client to update the data stored at the position of the Location Pointer.  CONSTRAINT_ERROR is raised if the list is empty.

GENERIC SUBPROGRAMS PROVIDED BY AN INSTANTIATION OF THIS CONTAINER CLASS

This section describes the Generic Subprograms provided by an instantiation of this generic container class. These subprograms are optional in that the client is free to instantiate any or none of these subprograms. In order to instantiate any of these custom Generic Subprograms, the client must first create an instantiation of this generic Ordered Map container class. Then the client may instantiate versions of these Generic Subprograms from that instantiation of this generic container class.

GENERIC

procedure Generic_Traverse(Ordered_Map : in out ORDERED_MAP_TYPE);

Allows the client to instantiate a procedure to traverse the entire list, typically to modify its contents. The client must provide the Generic Actual Parameter for the following Generic Formal Parameter:

procedure Visit(Key  : in KEYTYPE; 
                Item : in ELEMENT_TYPE);

This client-supplied procedure accepts a parameter of the type specified for the Generic Formal Parameter ELEMENT_TYPE when this container class was instantiated. This would also be a convenient way to print the contents of the list. The client would provide a print procedure for the Visit() Generic Subprogram that would print the contents of any given entry. The position of the Location Pointer is set to the end of the Ordered Map.

GENERIC

procedure Generic_Traverse2(Ordered_Map : in out ORDERED_MAP_TYPE; 
                            DATA        : in out RETURN_TYPE);

Used to traverse the Ordered Map and return any kind of the client wishes.  The client must provide a Generic Actual Parameter data type for the Generic Formal Parameter RETURN_TYPE when instantiating the generic Generic_Traverse2 procedure. Further, the client must specify a Generic Actual Parameter procedure for the following Generic Formal Parameter:

procedure Visit2(Key  : in KEYTYPE; 
                 Item : in ELEMENT_TYPE; 
                 DATA : in out RETURN_TYPE);

This client-supplied procedure accepts a parameter of the type specified for the Generic Formal Parameter ELEMENT_TYPE when this container class was instantiated. Further, the client-supplied procedure accepts a parameter of the type specified for RETURN_TYPE when instantiating this generic procedure, Generic_Traverse2().  This gives the client the capability to return special information as a result of the traversal.  For example, the client could obtain a linked list of data, possibly a subset of the Ordered Map based on criteria defined by the client-supplied Visit2() procedure.  The position of the Location Pointer is set to the end of the Ordered Map.

GENERIC

function Generic_Search(Ordered_Map : in ORDERED_MAP_TYPE; 
                        Criteria    : in GENERIC_SEARCH_CRITERIA_TYPE; 
                        Occurrence  : in OCCURRENCE_TYPE := EVERY; 
                        DeleteFlag  : in Boolean := FALSE )  return ORDERED_MAP_TYPE;

Used to search for any item in the list based on a client-specified set of criteria.  The client must provide a Generic Actual Parameter for the Generic Formal Parameter GENERIC_SEARCH_CRITERIA_TYPE when the client instantiates Generic_Search().  This is the data type containing the information to be used in the search.  The instantiation of Generic_Search() will use the information contained by the parameter "Criteria" when searching for items in the Orderd List.  The client must also provide a Generic Actual Parameter for the following Generic Formal Parameter:

function Generic_Search_Compare(Item     : in ELEMENT_TYPE; 
                                Criteria : in GENERIC_SEARCH_CRITERIA_TYPE) return BOOLEAN;

This client-supplied procedure will compare information contained within the "Criteria" passed into Generic_Search() against the data within any given entry of the Ordered Map. This client-supplied Generic Actual Parameter must return TRUE if the criteria results in a positive match for the data in any given entry of the Ordered Map. When the client calls the instantiation of Generic_Search(), the client may specify Occurrence as follows:

FIRST -- Searches the first occurrence of an item matching the specified criteria.

LAST -- Searches the last occurrence of an item matching the specified criteria.

EVERY -- Searches all occurrences of items matching the specified criteria.

The same rules apply to the handling of the Location Pointer by an instantiation of the Generic_Search() procedure as are discussed in the description of Search() above.

GENERIC

function Generic_Delete(Ordered_Map : in ORDERED_MAP_TYPE; 
                        Criteria    : in GENERIC_DELETE_CRITERIA_TYPE) return BOOLEAN;

Used to delete entries from the list based on a client-specified set of criteria.  The client must provide a Generic Actual Parameter for the Generic Formal Parameter GENERIC_DELINSERT_CRITERIA_TYPE when the client instantiates Generic_Delete().  Further, the client must provide a Generic Actual Parameter for the following  Generic Formal Parameter:

function Generic_Delete_Compare(Item     : in ELEMENT_TYPE; 
                                Criteria : in GENERIC_DELINSERT_CRITERIA_TYPE) return BOOLEAN;

This client-supplied procedure will compare information contained within the "Criteria" passed into Generic_Delete() against the data in each entry of the Ordered Map. This client-supplied Generic Actual Parameter must return TRUE if the criteria results in a positive match for the data in any given- entry of the Ordered Map.  For every entry for which the Generic_Delete_Compare() function returns TRUE, the item will be deleted from the Ordered Map.  The same rules apply regarding the position of the Location Pointer as described for the Delete() procedure above.

GENERIC

procedure GenericDeletionInsert(Ordered_Map : in ORDERED_MAP_TYPE; 
                                Item        : in ELEMENT_TYPE; 
                                Criteria    : in GENERIC_INSERT_CRITERIA_TYPE);

A more specialized insert. This procedure allows the client to insert an item into the Ordered Map WHILE DELETING ENTRIES LOWER/HIGHER IN LOGICAL ORDER THAT MATCH A CLIENT-SPECIFIED SET OF CRITERIA. That is, the client is able to delete any entries from the Ordered Map that come before the item being inserted according to criteria supplied by the client. When instantiating the generic subprogram Generic_Insert(), the client must provide a Generic Actual Parameter data type for the Generic Formal Parameter GENERIC_INSERT_CRITERIA_TYPE. This will contain data used as the deletion criteria. Further, the client must supply a function for the following Generic Formal Parameter:

function Generic_Deletion_Compare(Item     : in ELEMENT_TYPE; 
                                  Criteria : in GENERIC_INSERT_CRITERIA_TYPE) return BOOLEAN;

This function will compare the contents of the criteria passed into the instantiation of the Generic_Insert() subprogram with each element in the list UP TO THE POINT OF INSERTION. Any comparison that returns TRUE will cause the instantiation of Generic_Insert() to delete that item from the list, "Ordered_Map". This is a more efficient way of inserting items if you need to delete some, or all, items logically before the item being inserted. This prevents having to instantiate Generic_Delete() and deleting some items then calling Insert() to insert the new item.  The instantiation of Generic_Insert() returns immediately after the insertion of the new item. The same rules apply to the handling of the Location Pointer by an instantiation of the GenericDeletionInsert() procedure as are discussed in the description of Insert() above.

Top

EXCEPTIONS DEFINED

This section describes the exceptions that may be raised by subprograms provided by this container class.

INVALID_INPUT_DATA : Raised if an invalid Ordered Map is passed into a procedure or function.

ITEM_NOT_FOUND : Raised if an item being searched for in a search or delete call is not found.

NULL_LIST : Raised if a search or delete operation is attempted on an empty list.

ADDITIONAL NOTES

Assignment is defined for the data type ORDERED_MAP_TYPE. When assigning an Ordered Map to another Ordered Map of the same type, a duplicate of the original list is made and assigned to the target list of the assignment. The target list does NOT represent the same list as the original list. It is a copy. Therefor, modifying one list will not make changes to the copy.

No guarantees are provided with this code either expressed or implied.  I accept no liability for any damages or losses incurred through the use of this code.  I would advise you to thoroughly test this code for yourself before committing to use it on an important project.

Enjoy.  
George.

Download Source Ada Package (Self-extracting Exe) 

Top