generic

    type Item is private;

package List_Double_Iterator_Managed_Unbounded is
    --===============================================================
    -- This package provides operations needed to manipulate a     ==
    -- doubly-linked list structure. The classification of this    ==
    -- particular package is derived from Booch's notes            ==
    -- OBJECT-ORIENTED DESIGN WITH Ada. Double means doubly-linked ==
    -- list. Iterator means that this package provides an          ==
    -- operation which lets a user to be able to iterate through   ==
    -- a list (visiting every item in the list) without changing   ==
    -- the state of the list. Managed means that a garbage         ==
    -- collection mechanism is provided. Unbounded means that the  ==
    -- length of the list is virtually unlimited.                  ==
    --===============================================================

    type List is private;

    Null_List : constant List;

    procedure Clear (The_List : in out List);
    -- Clear returns The_List into the available list
    -- if it is not empty. Value of The_List is set
    -- to NULL_LIST upon return.

    procedure Share (The_List : in List; With_The_List : out List);
    -- Share assigns With_The_List to the same location
    -- The_List is currently pointing.

    function Seek (Origin : in List; Offset : in Integer) return List;
    -- Seek returns the position of nth item to the left/right of
    -- the current position (depending on Offset); if the nth item
    -- does not exist, OVERFLOW will be raised.

    procedure Construct (New_Item : in Item; And_The_List : out List);
    -- Construct creates a list with one item (New_Item) in it.

    procedure Append (This_List : in out List; And_This_List : in out List);
    -- Append will concatenate This_List with And_This_List.
    -- If either This_List or And_This_List is a NULL_LIST,
    -- exception LIST_IS_EMPTY will be raised.

    procedure Store (This_Item : in Item; In_This_Location : in out List);
    -- Store will put This_Item In_This_Location (destroying
    -- the previous content). If In_This_Location is Null_List,
    -- exception LIST_IS_EMPTY will be raised.

    function Content_Of (This_List : in List) return Item;
    -- Content_Of returns the current item pointed by This_List.
    -- Exception LIST_IS_EMPTY will be raised if This_List
    -- is a NULL_LIST.

    function Location_Of (This_Item : in Item; In_This : in List) return List;
    -- Location_Of returns the location of a given item in a
    -- given list. If the item is not found, Null_List will
    -- be returned.

    function Tail_Of (This_List : in List) return List;
    -- Tail_Of returns the position of the LAST item in the list.
    -- NULL_LIST is returned if The_List is a NULL_LIST.

    function Is_Equal (Left : in List; Right : in List) return Boolean;
    -- Is_Equal returns TRUE if Left and Right both point
    -- to the same location in the list; otherwise FALSE is
    -- returned.

    generic

        with procedure Process (This_Position : in List; Is_Done : out Boolean);

    procedure Iterate (Across_The_List : in List);
    -- Iterate will visit every item in a given list
    -- (Across_The_List) and invoke Process. If Is_Done
    -- flag is TRUE upon return, iteration process will
    -- stop; otherwise iteration will continue until all
    -- items have been visited once.

    Overflow : exception;
    -- raised when trying to search beyond either end of a given list
    -- (by Forward and Backward operations).

    List_Is_Empty : exception;
    -- raised when trying to (1) Append one or two empty lists
    --                       (2) Store an item to an empty list
    --                       (3) find the Content_Of an empty list

private

    type Node;
    type List is access Node;
    Null_List : constant List := null;

end List_Double_Iterator_Managed_Unbounded;