⟦35df1b2f2⟧

E3 Source Code



--| @SUMMARY Implements a pure-Ada, sorted, doubly-linked list abstraction.
--|
--| @DESCRIPTION This package implements a sorted, doubly-linked list
--| abstraction. Iteration as well as addition and deletion are provided,
--| in a mixed-mode (so that addition/deletion can be performed while
--| iterating). Elements in the list are kept sorted at all times.
--|
--| @RAISES No_Current_Element, No_Previous_Element, No_Next_Element.
--| Also, all "Add" operations propagate Storage_Error if it occurs.
--|
--| @INDICES (List_Processing, Data_Structure)
--|
--| @SPECIAL_NOTES This package maintains an internal free-list of reclaimed
--| nodes. Access to the free-list is serialized, so this component is safe
--| in multi-tasking applications.
--|
generic

    type Element is private;

    with function "<" (Smaller_Element : in Element;  
                       Larger_Element  : in Element) return Boolean;
    --
    -- The Add operation will sort the elements using this client-specified
    -- function "<".

package Sorted_List_Generic is

    type List is private;

    --| @SUMMARY Returns an empty list.
    --|
    function Create return List;

    --| @SUMMARY Returns True if the specified list contains no elements.
    --|
    function Is_Empty (This_List : in List) return Boolean;

    --| @SUMMARY Returns the number of elements in the specified list.
    --|
    function Elements_In (This_List : in List) return Natural;

    --| @SUMMARY Returns a copy of the specified list.
    --|
    --| @DESCRIPTION Creates and returns a copy of the specified list,
    --| using the supplied copy function to copy the individual elements
    --| in the list.
    --|
    --| @SPECIAL_NOTES If the supplied copy function provides a true
    --| (non-aliased) copy of the elements, then the resulting copied
    --| list will be a true copy of the original list. Very different
    --| from ":=".
    --|
    generic

        with function Copy (Of_Element : in Element) return Element;

    function Copy (Of_List : in List) return List;

    --| @SUMMARY Resets the current element in the list to be the
    --| first element.
    --|
    --| @SPECIAL_NOTES If the list is empty, has no effect (the list
    --| is already "Done").
    --|
    procedure Reset_To_First (This_List : in out List);

    --| @SUMMARY Resets the current element in the list to be the last
    --| element.
    --|
    --| @SPECIAL_NOTES If the list is empty, has no effect (the list
    --| is already "Done").
    --|
    procedure Reset_To_Last (This_List : in out List);

    --| @SUMMARY Returns True iff the list is "Done".
    --|
    --| @DESCRIPTION The list is considered "Done" if the list has been
    --| advanced past the last element, has been backed-up past the first
    --| element, or is empty.
    --|
    --| @SPECIAL_NOTES Note that empty lists are always "Done", but "Done"
    --| lists are not necessarily empty.
    --|
    function Done (This_List : in List) return Boolean;

    --| @SUMMARY Returns True if the current position is the first element
    --| in the list.
    --|
    --| @SPECIAL_NOTES Will be True at the same time as "At_Last" if the
    --| list contains only one element. Returns False if the list is empty.
    --|
    function At_First (This_List : in List) return Boolean;

    --| @SUMMARY Returns True if the current position is the last element
    --| in the list.
    --|
    --| @SPECIAL_NOTES Will be True at the same time as "At_First" if the
    --| list contains only one element. Returns False if the list is empty.
    --|
    function At_Last (This_List : in List) return Boolean;

    --| @SUMMARY Backs up the current element in the list to the previous
    --| element.
    --|
    --| @RAISES No_Previous_Element (if "Done")
    --|
    procedure Previous (This_List : in out List);

    --| @SUMMARY Advances the current element in the list to the next element.
    --|
    --| @RAISES No_Next_Element (if "Done")
    --|
    procedure Next (This_List : in out List);

    --| @SUMMARY Returns the current element in the list.
    --|
    --| @RAISES No_Current_Element (if "Done")
    --|
    function Current (This_List : in List) return Element;

    --| @SPECIAL_NOTES Elements are numbered 1..N
    --|
    type Positions is new Positive; -- Elements are numbered 1..N

    --| @SUMMARY Returns the position of the current element in the list.
    --|
    --| @RAISES No_Current_Element (if "Done")
    --|
    function Position (In_List : in List) return Positions;

    --| @SUMMARY Sets the current element in the list to the specified
    --| position.
    --|
    --| @RAISES Out_Of_Range (if the specified position is off either
    --| end of the list)
    --|
    procedure Set (This_List : in out List; To_Position : in Positions);

    --| @SUMMARY Returns the element at the current position in the list.
    --|
    --| @RAISES Out_Of_Range (if the specified position is off either
    --| end of the list)
    --|
    function Element_At (This_Position : in Positions; In_List : in List)
                        return Element;

    --| @SPECIAL_NOTES Control the reaction to attempts to add duplicate
    --| elements to the list.
    --|
    type Duplicate_Reactions is (Disallow, Overwrite, Insert);

    --| @SUMMARY Adds the specified element to the appropriate place
    --| in the list, as determined by the client-supplied "<" function.
    --|
    --| @RAISES Reaction in the case of duplicate elements depends
    --| on the "Duplicate_Reaction":
    --|
    --| If "Disallow", raises "Duplicate_Element" when a duplicate element
    --| is encountered.
    --|
    --| If "Overwrite", replaces the old duplicate element with the new
    --| duplicate element.
    --|
    --| If "Insert", inserts the current duplicate element after all other
    --| duplicates of the current duplicate element.
    --|
    --| @SPECIAL_NOTES Does not alter iterator state. The iterator is still
    --| pointing to the same element as it was before the operation (the only
    --| exception to this is if the element just added is the only element in
    --| the list, in which case it becomes the first element, the last element,
    --| the current position, and the current element simultaneously).
    --|
    procedure Add (To_List            : in out List;  
                   This_Element       : in     Element;
                   Duplicate_Reaction : in     Duplicate_Reactions);

    --| @SUMMARY Deletes the current element from the list.
    --|
    --| @RAISES No_Current_Element (if the list is "Done" before the delete
    --| is attempted)
    --|
    --| @SPECIAL_NOTES Deletes the current element from the list. The new
    --| current element is set to the element immediately following the
    --| deleted element. If the deleted element was the last element in the
    --| list, the list becomes "Done".
    --|
    procedure Delete (From_List : in out List);

    --| @SUMMARY Deletes the element at the specified position from the list.
    --|
    --| @RAISES Out_Of_Range (if the specified position is off either end
    --| of the list)
    --|
    --| @SPECIAL_NOTES If the element at the specified position is not the
    --| current element, the state of the iterator is unchanged (note, however,
    --| that deletions which decrease the number of elements preceeding the
    --| original position will decrement the current position by 1).
    --|
    --| If the element at the specified position is the current element,
    --| the new current element is set to the element immediately following
    --| the deleted element (note that the position remains unchanged). If
    --| the deleted element was the last element in the list, the list becomes
    --| "Done".
    --|
    procedure Delete (From_List : in out List; At_Position : in Positions);

    --| @SUMMARY Reclaims storage.
    --|
    --| @SPECIAL_NOTES Puts the nodes of the list back on the internal
    --| free-list. Is an unchecked operation: aliased lists will be
    --| disposed of without mercy.
    --|
    procedure Dispose (Of_This_List : in out List);

    No_Current_Element  : exception;
    No_Previous_Element : exception;
    No_Next_Element     : exception;

    Out_Of_Range : exception;

    Duplicate_Element : exception;

    -- Note: the "Add" operation propagates Storage_Error if it occurs.

private

    type Node;

    type Pointer is access Node;

    type Node is  
        record
            Contents : Element;  
            Next     : Pointer := null;
            Previous : Pointer := null;
        end record;

    type List is  
        record
            First    : Pointer := null;
            Last     : Pointer := null;
            Current  : Pointer := null;
            Position : Natural := 0;
            Count    : Natural := 0;  
        end record;

end Sorted_List_Generic;
DataMuseum.dk

Rational R1000/400

⟦35df1b2f2⟧ Ada Source

Derivation

E3 Source Code

E3 Meta Data
