with

    Ada.Iterator_Interfaces;


generic
    type Label_Enum is (<>);
    type Element is private;
    type Element_Array is array (Positive range <>) of Element;
    with package My_Interfaces is new Interfaces (Label_Enum, Element, Element_Array);
package Packrat.Graphs is


    type Node is new My_Interfaces.Node with private;

    type Node_Reference (Data : not null access Node'Class) is limited null record
        with Implicit_Dereference => Data;


    type Cursor is new My_Interfaces.Cursor with private;

    type Iter_Cursor (Data : not null access Cursor) is private
        with Implicit_Dereference => Data;


    type Parse_Graph is new My_Interfaces.Graph with private
        with Default_Iterator  => Iterate,
             Iterator_Element  => Node_Reference,
             Variable_Indexing => Node_At;




    No_Position : constant Cursor;

    Empty_Graph : constant Parse_Graph;




    function Leaf
           (New_Item : in Element_Array;
            Start    : in Positive;
            Finish   : in Natural)
        return Node;

    function Branch
           (Label  : in Label_Enum;
            Start  : in Positive;
            Finish : in Natural)
        return Node;


    function Is_Leaf
           (This : in Node)
        return Boolean;

    function Is_Branch
           (This : in Node)
        return Boolean;


    function Label
           (This : in Node)
        return Label_Enum;

    function Elements
           (This : in Node)
        return Element_Array;

    function Start
           (This : in Node)
        return Positive;

    function Finish
           (This : in Node)
        return Natural;




    function Is_Nothing
           (Position : in Cursor)
        return Boolean;




    function Depth
           (Position : in Cursor)
        return Natural;

    function Is_Node
           (Position : in Cursor)
        return Boolean;

    function Is_Root
           (Position : in Cursor)
        return Boolean;

    function Is_Branch
           (Position : in Cursor)
        return Boolean;

    function Is_Leaf
           (Position : in Cursor)
        return Boolean;




    function Label
           (Position : in Cursor)
        return Label_Enum;

    function Elements
           (Position : in Cursor)
        return Element_Array;

    function Start
           (Position : in Cursor)
        return Positive;

    function Finish
           (Position : in Cursor)
        return Natural;

    function Choices
           (Position : in Cursor)
        return Natural;




    function Parent
           (Position : in Cursor)
        return Cursor;

    function Child_Count
           (Position : in Cursor;
            Choice   : in Positive)
        return Natural;

    function Child_Count
           (Position : in Cursor)
        return Natural;

    function All_Child_Count
           (Position : in Cursor)
        return Natural;

    function First_Child
           (Position : in Cursor;
            Choice   : in Positive)
        return Cursor;

    function Last_Child
           (Position : in Cursor;
            Choice   : in Positive)
        return Cursor;

    function First_Child
           (Position : in Cursor)
        return Cursor;

    function Last_Child
           (Position : in Cursor)
        return Cursor;

    function Next_Sibling
           (Position : in Cursor)
        return Cursor;

    function Prev_Sibling
           (Position : in Cursor)
        return Cursor;

    procedure Delete_Children
           (Position : in out Cursor;
            Choice   : in     Positive);

    procedure Delete_Children
           (Position : in out Cursor);

    procedure Delete_All_Children
           (Position : in out Cursor);




    function Equal_Subgraph
           (Left, Right : in Cursor)
        return Boolean;

    function Subgraph_Node_Count
           (Position : in Cursor)
        return Natural;

    function Find_In_Subgraph
           (Position : in Cursor;
            Item     : in Element_Array)
        return Cursor;




    function Contains
           (Container : in Parse_Graph;
            Position  : in My_Interfaces.Cursor'Class)
        return Boolean;




    function Singleton
           (Input : in My_Interfaces.Node'Class)
        return Parse_Graph;

    function Node_At
           (Container : in Parse_Graph;
            Position  : in My_Interfaces.Cursor'Class)
        return Node_Reference
    with Pre =>
            Position.Is_Node;




    function Is_Empty
           (Container : in Parse_Graph)
        return Boolean;

    function Is_Ambiguous
           (Container : in Parse_Graph)
        return Boolean;

    function Node_Count
           (Container : in Parse_Graph)
        return Natural;




    function Root_Count
           (Container : in Parse_Graph)
        return Natural;

    function Root
           (Container : in Parse_Graph;
            Index     : in Positive)
        return My_Interfaces.Cursor'Class;




    procedure Append
           (Container : in out Parse_Graph;
            Addition  : in     Parse_Graph);

    procedure Prepend
           (Container : in out Parse_Graph;
            Addition  : in     Parse_Graph);

    procedure Attach_Choice
           (Container : in out Parse_Graph;
            Position  : in     My_Interfaces.Cursor'Class;
            Addition  : in     Parse_Graph);




    procedure Clear
           (Container : in out Parse_Graph);

    procedure Delete_Position
           (Container : in out Parse_Graph;
            Position  : in out My_Interfaces.Cursor'Class);




    function Find
           (Container : in Parse_Graph;
            Item      : in Element_Array)
        return My_Interfaces.Cursor'Class;




    function Is_Valid_Node
           (Position : in Iter_Cursor)
        return Boolean;




    package Graph_Iterators is
        new Ada.Iterator_Interfaces (Iter_Cursor, Is_Valid_Node);

    type Choosing_Function is access function
           (Position : in Cursor)
        return Natural;




    function Iterate
           (This : in Parse_Graph)
        return Graph_Iterators.Reversible_Iterator'Class;

    function Iterate_Subtree
           (This     : in Parse_Graph;
            Position : in My_Interfaces.Cursor'Class)
        return Graph_Iterators.Reversible_Iterator'Class;

    function Iterate_Choice
           (This : in Parse_Graph;
            Func : in Choosing_Function)
        return Graph_Iterators.Forward_Iterator'Class;




private


    type Node is new My_Interfaces.Node with null record;

    type Cursor is new My_Interfaces.Cursor with null record;

    type Iter_Cursor (Data : not null access Cursor) is null record;

    type Parse_Graph is new My_Interfaces.Graph with null record;




    No_Node : constant Node := (My_Interfaces.Node with null record);

    No_Position : constant Cursor := (My_Interfaces.Cursor with null record);

    Empty_Graph : constant Parse_Graph := (My_Interfaces.Graph with null record);




    type Forward_Iterator is new Graph_Iterators.Forward_Iterator with record
        My_Container : access Parse_Graph;
        My_Position  : Cursor;
    end record;

    overriding function First
           (Object : in Forward_Iterator)
        return Iter_Cursor;

    overriding function Next
           (Object : in Forward_Iterator;
            Place  : in Iter_Cursor)
        return Iter_Cursor;

    type Reversible_Iterator is new Graph_Iterators.Reversible_Iterator with record
        My_Container : access Parse_Graph;
        My_Position  : Cursor;
    end record;

    overriding function First
           (Object : in Reversible_Iterator)
        return Iter_Cursor;

    overriding function Next
           (Object : in Reversible_Iterator;
            Place  : in Iter_Cursor)
        return Iter_Cursor;

    overriding function Last
           (Object : in Reversible_Iterator)
        return Iter_Cursor;

    overriding function Previous
           (Object : in Reversible_Iterator;
            Place  : in Iter_Cursor)
        return Iter_Cursor;


end Packrat.Graphs;