with

    Ada.Iterator_Interfaces;

private with

    Ada.Containers.Helpers,
    Ada.Finalization,
    Ada.Streams;
    --  maps? sets?


generic

    type Node_Type is (<>);
    type Node_Array is array (Positive) of Node_Type;

    type Node_Label_Type is private;
    type Edge_Label_Type is private;

package Ada.Containers.Directed_Graphs is


    subtype Path is Node_Array;

    subtype Extended_Node_Type is Node_Type'Base
        range Node_Type'First - 1 ..
              Node_Type'Min (Node_Type'Base'Last - 1, Node_Type'Last) + 1;

    No_Node : constant Extended_Node_Type := Extended_Node_Type'First;




    type Edge_Type is record
        From : Node_Type;
        To   : Node_Type;
    end record;

    type Edge_Array is array (Positive) of Edge_Type;




    type Graph is tagged private;

    type Cursor is private;

    No_Element : constant Cursor;

    function Has_Element
           (Position : in Cursor)
        return Boolean;

    package Graph_Iterator_Interfaces is new
        Ada.Iterator_Interfaces (Cursor, Has_Element);

    Empty_Graph : constant Graph;

    overriding function "="
           (Left, Right : in Graph)
        return Boolean;

    function To_Graph
           (Nodes : in Node_Array;
            Edges : in Edge_Array)
        return Graph;

    function To_Cursor
           (Container : in Graph;
            Node      : in Node_Type)
        return Cursor;




    procedure Assign
           (Target : in out Graph;
            Source : in     Graph);

    function Copy
           (Source : in Graph)
        return Graph;

    procedure Move
           (Target, Source : in out Graph);




    function Is_Empty
           (Container : in Graph)
        return Boolean;

    procedure Clear
           (Container : in out Graph);

    procedure Clear_Labels
           (Container : in out Graph);




    function Node_Count
           (Container : in Graph)
        return Count_Type;

    function Edge_Count
           (Container : in Graph)
        return Count_Type;

    function Nodes
           (Container : in Graph)
        return Node_Array;

    function Edges
           (Container : in Graph)
        return Edge_Array;

    procedure Node_Range
           (Container : in     Graph;
            Minimum   :    out Node;
            Maximum   :    out Node);

    function Unused_Nodes
           (Container : in Graph;
            Count     : in Positive := 1)
        return Node_Array;




    procedure Insert
           (Container : in out Graph;
            Node      : in     Node_Type);

    procedure Insert
           (Container : in out Graph;
            Node      : in     Node_Type;
            Label     : in     Node_Label_Type);

    procedure Insert
           (Container : in out Graph;
            Nodes     : in     Node_Array);

    procedure Insert
           (Container : in out Graph;
            Edge      : in     Edge_Type);

    procedure Insert
           (Container : in out Graph;
            Edge      : in     Edge_Type;
            Label     : in     Edge_Label_Type);

    procedure Insert
           (Container : in out Graph;
            Edges     : in     Edge_Array);

    procedure Append
           (Container : in out Graph;
            Position  :    out Cursor);

    procedure Append
           (Container : in out Graph;
            Label     : in     Node_Label_Type;
            Position  :    out Cursor);

    procedure Delete
           (Container : in out Graph;
            Node      : in     Node_Type);

    procedure Delete
           (Position : in out Cursor);

    procedure Delete
           (Container : in out Graph;
            Nodes     : in     Node_Array);

    procedure Delete
           (Container : in out Graph;
            Edge      : in     Edge_Type);

    procedure Delete
           (Container : in out Graph;
            Edges     : in     Edge_Array);

    procedure Append_Label
           (Container : in out Graph;
            Node      : in     Node_Type;
            Label     : in     Node_Label_Type);

    procedure Append_Label
           (Position : in out Cursor;
            Label    : in     Node_Label_Type);

    procedure Append_Label
           (Container : in out Graph;
            Edge      : in     Edge_Type;
            Label     : in     Edge_Label_Type);

    procedure Replace_Label
           (Container : in out Graph;
            Node      : in     Node_Type;
            Label     : in     Node_Label_Type);

    procedure Replace_Label
           (Position : in out Cursor;
            Label    : in     Node_Label_Type);

    procedure Replace_Label
           (Container : in out Graph;
            Edge      : in     Edge_Type;
            Label     : in     Edge_Label_Type);

    procedure Delete_Label
           (Container : in out Graph;
            Node      : in     Node_Type);

    procedure Delete_Label
           (Position : in out Cursor);

    procedure Delete_Label
           (Container : in out Graph;
            Edge      : in     Edge_Type);

    procedure Delete_Subgraph
           (Position : in out Cursor);

    procedure Swap
           (Container   : in out Graph;
            Left, Right : in     Node_Type);

    procedure Swap
           (Left, Right : in out Cursor);




    procedure Context
           (Container : in     Graph;
            Node      : in     Node_Type;
            Parents   :    out Node_Array;
            Children  :    out Node_Array);

    procedure Context
           (Position : in     Cursor;
            Parents  :    out Node_Array;
            Children :    out Node_Array);

    procedure Labeled_Context
           (Container : in     Graph;
            Node      : in     Node_Type;
            Parents   :    out Node_Array;
            Children  :    out Node_Array;
            Label     :    out Node_Label_Type);

    procedure Labeled_Context
           (Position : in     Cursor;
            Parents  :    out Node_Array;
            Children :    out Node_Array;
            Label    :    out Node_Label_Type);

    function Has_Label
           (Container : in Graph;
            Node      : in Node_Type)
        return Boolean;

    function Has_Label
           (Position : in Cursor)
        return Boolean;

    function Has_Label
           (Container : in Graph;
            Edge      : in Edge_Type)
        return Boolean;

    function Label
           (Container : in Graph;
            Node      : in Node_Type)
        return Node_Label_Type;

    function Label
           (Position : in Cursor)
        return Node_Label_Type;

    function Label
           (Container : in Graph;
            Edge      : in Edge_Type)
        return Edge_Label_Type;

    type Node_Label_Constant_Reference
        (Element : not null access constant Node_Label_Type) is private
    with Implicit_Dereference => Element;

    function Constant_Label_Reference
           (Container : in Graph;
            Node      : in Node_Type)
        return Node_Label_Constant_Reference;

    function Constant_Label_Reference
           (Position : in Cursor)
        return Node_Label_Constant_Reference;

    type Node_Label_Reference
        (Element : not null access Node_Label_Type) is private
    with Implicit_Dereference => Element;

    function Label_Reference
           (Container : in Graph;
            Node      : in Node_Type)
        return Node_Label_Reference;

    function Label_Reference
           (Position : in Cursor)
        return Node_Label_Reference;

    type Edge_Label_Constant_Reference
        (Element : not null access constant Edge_Label_Type) is private
    with Implicit_Dereference => Element;

    function Constant_Label_Reference
           (Container : in Graph;
            Edge      : in Edge_Type)
        return Edge_Label_Constant_Reference;

    type Edge_Label_Reference
        (Element : not null access Edge_Label_Type) is private
    with Implicit_Dereference => Element;

    function Label_Reference
           (Container : in Graph;
            Edge      : in Edge_Type)
        return Edge_Label_Reference;

    function Neighbors
           (Container : in Graph;
            Node      : in Node_Type)
        return Node_Array;

    function Neighbors
           (Position : in Cursor)
        return Node_Array;

    function Parents
           (Container : in Graph;
            Node      : in Node_Type)
        return Node_Array;

    function Parents
           (Position : in Cursor)
        return Node_Array;

    function Children
           (Container : in Graph;
            Node      : in Node_Type)
        return Node_Array;

    function Children
           (Position : in Cursor)
        return Node_Array;

    function Outbound
           (Container : in Graph;
            Node      : in Node_Type)
        return Edge_Array;

    function Outbound
           (Position : in Cursor)
        return Edge_Array;

    function Inbound
           (Container : in Graph;
            Node      : in Node_Type)
        return Edge_Array;

    function Inbound
           (Position : in Cursor)
        return Edge_Array;

    function Outdegree
           (Container : in Graph;
            Node      : in Node_Type)
        return Count_Type;

    function Outdegree
           (Position : in Cursor)
        return Count_Type;

    function Indegree
           (Container : in Graph;
            Node      : in Node_Type)
        return Count_Type;

    function Indegree
           (Position : in Cursor)
        return Count_Type;

    function Degree
           (Container : in Graph;
            Node      : in Node_Type)
        return Count_Type;

    function Degree
           (Position : in Cursor)
        return Count_Type;

    function Has_Edge
           (Container     : in Graph;
            Parent, Child : in Node_Type)
        return Boolean;

    function Has_Edge
           (Parent, Child : in Cursor)
        return Boolean;

    function Has_Labeled_Edge
           (Container     : in Graph;
            Parent, Child : Node_Type)
        return Boolean;

    function Has_Labeled_Edge
           (Parent, Child : in Cursor)
        return Boolean;

    function Has_Neighbor
           (Container   : in Graph;
            Left, Right : in Node_Type)
        return Boolean;

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




    function Find
           (Container : in Graph;
            Label     : in Node_Label_Type)
        return Node_Array;

    function Find
           (Container : in Graph;
            Label     : in Edge_Label_Type)
        return Edge_Array;

    function Find_In_Subgraph
           (Position : in Cursor;
            Label    : in Node_Label_Type)
        return Node_Array;

    function Find_In_Subgraph
           (Position : in Cursor;
            Label    : in Edge_Label_Type)
        return Edge_Array;

    function Contains
           (Container : in Graph;
            Node      : in Node_Type)
        return Boolean;

    function Contains
           (Container : in Graph;
            Node      : in Node_Type;
            Label     : in Node_Label_Type)
        return Boolean;

    function Contains
           (Container : in Graph;
            Edge      : in Edge_Type)
        return Boolean;

    function Contains
           (Container : in Graph;
            Edge      : in Edge_Type;
            Label     : in Edge_Label_Type)
        return Boolean;

    function Contains_Label
           (Container : in Graph;
            Label     : in Node_Label_Type)
        return Boolean;

    function Contains_Label
           (Container : in Graph;
            Label     : in Edge_Label_Type)
        return Boolean;

    function Contains_In_Subgraph
           (Position : in Cursor;
            Node     : in Node_Type)
        return Boolean;

    function Contains_In_Subgraph
           (Position : in Cursor;
            Node     : in Node_Type;
            Label    : in Node_Label_Type)
        return Boolean;

    function Contains_In_Subgraph
           (Position : in Cursor;
            Edge     : in Edge_Type)
        return Boolean;

    function Contains_In_Subgraph
           (Position : in Cursor;
            Edge     : in Edge_Type;
            Label    : in Edge_Label_Type)
        return Boolean;

    function Contains_Label_In_Subgraph
           (Position : in Cursor;
            Label    : in Node_Label_Type)
        return Boolean;

    function Contains_Label_In_Subgraph
           (Position : in Cursor;
            Label    : in Edge_Label_Type)
        return Boolean;




    function Iterate
           (Container : in Graph)
        return Graph_Iterator_Interfaces.Reversible_Iterator'Class;

    function Iterate_Subgraph
           (Container : in Graph;
            Position  : in Cursor)
        return Graph_Iterator_Interfaces.Forward_Iterator'Class;


private


end Ada.Containers.Directed_Graphs;