with Unchecked_Deallocation;
package body Singly_Linked_List is
    --------------------------------------------------------------------------
    -- Abstract   : This package provides an abstraction for a singly linked
    --              list.
    --------------------------------------------------------------------------
    -- Assumptions:
    --      The lists being manipulated must be in one of the following states
    --      both before and after execution of any subprogram in the package:
    --              (1) empty-list          -- Head = null, Tail = null,
    --                                         Previous = null, Current = null
    --              (2) beginning-of-list   -- Head /= null, Tail /= null
    --                                         Previous = null, Current = Head
    --              (3) inside-of-list      -- Head /= null, Tail /= null
    --                                         Previous.Next = Current
    --              (4) outside-of-list     -- Head /= null, Tail /= null
    --                                         Previous = null, Current = null
    ----------------------------------------------------------------------
    function Empty (List : List_Type) return Boolean is
        --------------------------------------------------------------------------
        -- Abstract   : Indicates whether the list contains any elements.
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be queried.
        --------------------------------------------------------------------------
    begin
        return (List.Head = null);
    end Empty;
    function Null_Node (List : List_Type) return Boolean is
        --------------------------------------------------------------------------
        -- Abstract   : Indicates whether the "current pointer" references an
        --              element in the list.
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be queried.
        --------------------------------------------------------------------------
    begin
        return (List.Current = null);
    end Null_Node;
    function Head_Node (List : List_Type) return Boolean is
        --------------------------------------------------------------------------
        -- Abstract   : Indicates whether the "current pointer" references the
        --              head of the list.
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be queried.
        --------------------------------------------------------------------------
    begin
        return (List.Current = List.Head);
    end Head_Node;
    function Tail_Node (List : List_Type) return Boolean is
        --------------------------------------------------------------------------
        -- Abstract   : Indicates whether the "current pointer" references the
        --              tail of the list.
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be queried.
        --------------------------------------------------------------------------
    begin
        return (List.Current = List.Tail);
    end Tail_Node;
    function Current_Element (List : List_Type) return List_Element is
        --------------------------------------------------------------------------
        -- Abstract   : Returns the value of the element referenced by the
        --              "current pointer".
        --              Raises END_ERROR if NULL_NODE(LIST) = TRUE.
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be queried.
        --------------------------------------------------------------------------
    begin
        if List.Current = null then
            raise End_Error;
        else
            return List.Current.Element;
        end if;
    end Current_Element;
    procedure First (List : in out List_Type) is
        --------------------------------------------------------------------------
        -- Abstract   : Positions the "current pointer" at the head of the list
        --              (even if the list is empty).
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be modified.
        --------------------------------------------------------------------------
    begin
        List.Previous := null;
        List.Current := List.Head;
    end First;
    procedure Next (List : in out List_Type) is
        --------------------------------------------------------------------------
        -- Abstract   : Positions the "current pointer" at the next element in the
        --              list.  After the last element in the list NULL_NODE(LIST)
        --              becomes true.
        --              Raises END_ERROR if NULL_NODE(LIST) = TRUE.
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be modified.
        --------------------------------------------------------------------------
    begin
        if List.Current = null then
            raise End_Error;
        else
            if List.Current = List.Tail then
                List.Previous := null;
            else
                List.Previous := List.Current;
            end if;
            List.Current := List.Current.Next;
        end if;
    end Next;
    procedure Insert_After (List : in out List_Type; Element : List_Element) is
        --------------------------------------------------------------------------
        -- Abstract   : Inserts an element after the "current pointer".
        --              If NULL_NODE(LIST) = TRUE the element is appended after
        --              the tail element of the list.
        --------------------------------------------------------------------------
        -- Parameters : LIST    - is the list to be modified.
        --              ELEMENT - is the element to be inserted.
        --------------------------------------------------------------------------
    begin
        if List.Current = null then
            List.Current := List.Tail;
        end if;
        if Empty (List) then
            List.Head := new Node'(Element, null);
            List.Tail := List.Head;
            List.Previous := null;
            List.Current := List.Head;
        else
            declare
                New_Node : Node_Access := new Node'(Element, List.Current.Next);
            begin
                if List.Current = List.Tail then
                    List.Tail := New_Node;
                end if;
                List.Previous := List.Current;
                List.Previous.Next := New_Node;
                List.Current := New_Node;
            end;
        end if;
    end Insert_After;
    procedure Insert_Before (List : in out List_Type; Element : List_Element) is
        -------------------------------------------------------------------------
        -- Abstract   : Inserts an element before the "current pointer".
        --              If NULL_NODE(LIST) = TRUE the element is prepended before
        --              the head element of the list.
        --------------------------------------------------------------------------
        -- Parameters : LIST    - is the list to be modified.
        --              ELEMENT - is the element to be inserted.
        --------------------------------------------------------------------------
    begin
        if List.Current = null then
            List.Current := List.Head;
        end if;
        if Empty (List) then
            List.Head := new Node'(Element, null);
            List.Tail := List.Head;
            List.Previous := null;
            List.Current := List.Head;
        elsif List.Current = List.Head then
            List.Head := new Node'(Element, List.Head);
            List.Previous := null;
            List.Current := List.Head;
        else
            List.Previous.Next := new Node'(Element, List.Current);
            List.Current := List.Previous.Next;
        end if;
    end Insert_Before;
    procedure Delete_Element (List : in out List_Type) is
        --------------------------------------------------------------------------
        -- Abstract   : Deletes the element referenced by the "current pointer"
        --              from the list.  Upon deletion the "current pointer"
        --              references the element after the deleted element.
        --              Raises END_ERROR if NULL_NODE(LIST) = TRUE.
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be modified.
        --------------------------------------------------------------------------
        procedure Free is new Unchecked_Deallocation (Node, Node_Access);
    begin
        if List.Current = null then
            raise End_Error;
        elsif List.Current = List.Head then
            declare
                Next_Node : Node_Access := List.Head.Next;
            begin
                Free (List.Head);  -- List.Head:=null; --
                List.Head := Next_Node;
                if List.Head = null then
                    List.Tail := null;
                end if;
                List.Current := List.Head;
            end;
        else
            if List.Current = List.Tail then
                List.Tail := List.Previous;
            end if;
            List.Previous.Next := List.Current.Next;
            Free (List.Current);  --  List.Current:=null; --
            List.Current := List.Previous.Next;
            if List.Current = null then
                List.Previous := null;
            end if;
        end if;
    end Delete_Element;
    procedure Modify (List : List_Type) is
        --------------------------------------------------------------------------
        -- Abstract   : Permits modification of the element referenced by the
        --              "current pointer" where the modification doesn't require
        --              external values (e.g. incrementing a field of the element).
        --              Raises END_ERROR if NULL_NODE(LIST) = TRUE.
        --------------------------------------------------------------------------
        -- Parameters : LIST - is the list to be modified.
        --------------------------------------------------------------------------
    begin
        if List.Current = null then
            raise End_Error;
        else
            Transformation (List.Current.Element);
        end if;
    end Modify;
    procedure Update (List : List_Type; Information : Update_Information) is
        --------------------------------------------------------------------------
        -- Abstract   : Permits modification of the element referenced by the
        --              "current pointer" where the modification requires
        --              external values (e.g. assigning a value to a field of
        --              the element).
        --              Raises END_ERROR if NULL_NODE(LIST) = TRUE.
        --------------------------------------------------------------------------
        -- Parameters : LIST        - is the list to be modified.
        --              INFORMATION - is the data necessary for the modification.
        --------------------------------------------------------------------------
    begin
        if List.Current = null then
            raise End_Error;
        else

            Transformation (List.Current.Element, Information);
        end if;
    end Update;
end Singly_Linked_List;