-- This package implements a singly-linked list abstraction.
--
generic

    type Element is private;

package Singly_Linked_List_Generic is

    type List is private; -- Is ordered.

    function Create return List;
    --
    -- Returns an empty list.

    generic

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

    function Copy (Of_List : in List) return List;
    --
    -- Returns a copy of the specified list using the supplied copy
    -- function to copy the individual elements. 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 ":=".

    procedure Add (To_List : in out List;  
                   This_Element : in Element);
    --
    -- Adds the specified element to the end of the list.
    -- Alters iterator state, so is not safe to call while iterating.

    function Done (This_List : in List) return Boolean;

    procedure Reset (This_List : in out List);
    --
    -- Resets the current element in the list to be the first element.

    function Current (This_List : in List) return Element;
    --
    -- Returns the current element in the list.
    --
    -- Raises "No_Current_Element" if already "Done".

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

    procedure Next (This_List : in out List);
    --
    -- Advances the current element in the list to the next element.
    --
    -- Raises "No_Next_Element" if already "Done".

    subtype Element_Number is Positive; -- Elements are numbered 1..N

    function Position (In_List : in List) return Element_Number;
    --
    -- Returns the element number corresponding to the current element in
    -- the list.
    --
    -- Raises "No_Current_Element" if already "Done".

    procedure Set (This_List : in out List; To_Element : in Element_Number);
    --
    -- Sets the current element in the list to the specified element number.
    --
    -- Raises "Out_Of_Range" if the specified element number is out of range.

    function Element_At (This_Position : in Element_Number; In_List : in List)
                        return Element;
    --
    -- Returns the element corresponding to the specified element number.
    -- Can be called during iteration without altering iterator's position.
    --
    -- Raises "Out_Of_Range" if the specified element number is out of range.

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

    function Elements_In (This_List : in List) return Natural;
    --
    -- Returns the number of elements in the specified 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;