⟦00bdb10a9⟧

E3 Source Code



--| @SUMMARY Implements a pure-Ada singly-linked list abstraction.
--|
--| @DESCRIPTION This package implements a singly-linked list abstraction.
--| Iteration as well as addition and modification are provided, in a mixed-
--| mode (so that addition/modification can be performed while iterating).
--|
--| @RAISES No_Current_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;

package Singly_Linked_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 (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, 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 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;

    --| @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;

    --| @SUMMARY Adds the specified element to the end of the list.
    --|
    --| @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);

    --| @SUMMARY Replaces the current element in the list with the
    --| new element.
    --|
    --| @RAISES No_Current_Element (if "Done")
    --|
    --| @SPECIAL_NOTES Can be called during iteration without altering
    --| iterator's position.
    --|
    procedure Modify (This_List : in out List; New_Element : in Element);

    --| @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_Next_Element    : exception;

    Out_Of_Range : exception;

private

    type Node;

    type Pointer is access Node;

    type Node is  
        record
            Contents : Element;  
            Next     : 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 Singly_Linked_List_Generic;
DataMuseum.dk

Rational R1000/400

⟦00bdb10a9⟧ Ada Source

Derivation

E3 Source Code

E3 Meta Data
