-- ============================================================================
-- >>>>>>>>>>>>>>>>>>>>>>>>>> ADA COMPILATION UNIT <<<<<<<<<<<<<<<<<<<<<<<<<<<<
-- ============================================================================
--
-- NAME:        Graph_Directed_Unbounded_Managed
--
--              SPECIFICATION
-- 
-- AUTHOR:      Chuck Hobin
--
-- DATE:        9 November 1993
--
--                               CHANGE HISTORY
--
-- MM-DD-YY | Initials | Description
-- ----------------------------------------------------------------------------
-- <include SPR#, if applicable>
-- ============================================================================

with Set_Simple_Sequential_Unbounded_Managed_Iterator;
with Structure_Exceptions;

generic

    type Item is private;
    type Attribute is private;

package Graph_Directed_Unbounded_Managed is

-- Based on the graph structure presented in Booch, "Software Components
-- with Ada", Benjamin-Cummings, 1987, Chapter 12.

    type Graph is limited private;
    type Vertex is private;
    type Arc is private;

    Null_Vertex : constant Vertex;
    Null_Arc : constant Arc;


    procedure Copy (From_The_Graph : in Graph; To_The_Graph : in out Graph);

    -- Copy the vertices and arcs from one graph to another graph.
    --
    -- Raises : Overflow, if the size of the destination graph cannot
    --          grow large enough to hold the source state.

    procedure Clear (The_Graph : in out Graph);

    -- Remove all vertices and arcs (if any) from the graph and make
    -- the graph empty.

    procedure Add (The_Vertex : in out Vertex; 
		   With_The_Item : in Item; 
		   To_The_Graph : in out Graph);

    -- Create a vertex with a given value in the graph.
    --
    -- Raises : Overflow, if the graph cannot grow large enough to 
    --          hold the vertex.

    procedure Remove (The_Vertex : in out Vertex; 
		      From_The_Graph : in out Graph);

    -- Destroy the designated vertex in the graph.
    --
    -- Raises : Vertex_Is_Not_In_Graph, if the vertex is not a member
    --          of the graph.
    --
    -- Raises : Vertex_Is_Null, if the vertex is null.
    --
    -- Raises : Vertex_Has_References, if the vertex is the destination
    --          of at least one arc.

    procedure Set_Item (Of_The_Vertex : in out Vertex; To_The_Item : in Item);

    -- Set the value of the designated vertex to the given item.
    --
    -- Raises : Vertex_Is_Null, if the vertex is null.

    procedure Create (The_Arc : in out Arc; 
		      With_The_Attribute : in Attribute; 
		      From_The_Vertex : in out Vertex; 
		      To_The_Vertex : in Vertex; 
		      In_The_Graph : in out Graph);

    -- Generate an arc with the given attribute; the origin and destination
    -- vertices of this arc must be designated, as well as the graph
    -- enclosing these vertices.
    --
    -- Raises : Overflow, if the graph cannot grow large enough to 
    --          hold the arc.
    --
    -- Raises : Vertex_Is_Not_In_Graph, if either vertex is not a member
    --          of the graph.
    --
    -- Raises : Vertex_Is_Null, if either vertex is null.

    procedure Destroy (The_Arc : in out Arc; In_The_Graph : in out Graph);

    -- Remove the given arc in the graph.
    --
    -- Raises : Arc_Is_Null, if the arc is null.
    -- 
    -- Raises : Arc_Is_Not_In_Graph, if the arc is not a member
    --          of the graph.

    procedure Set_Attribute (Of_The_Arc : in out Arc; 
			     To_The_Attribute : in Attribute);

    -- Set the value of the designated arc to the given attribute.
    --
    -- Raises : Arc_Is_Null, if the arc is null.

    function Is_Empty (The_Graph : in Graph) return Boolean;

    -- Return true if the graph contains no vertices.

    function Is_Null (The_Vertex : in Vertex) return Boolean;

    -- Return True if the object does not denote any vertex.

    function Is_Null (The_Arc : in Arc) return Boolean;

    -- Return True if the object does not denote any arc.

    function Number_Of_Vertices_In (The_Graph : in Graph) return Natural;

    -- Return the number of vertices in the given graph.

    function Number_Of_Arcs_In (The_Graph : in Graph) return Natural;

    -- Return the number of arcs in the given graph.

    function Number_Of_Arcs_From (The_Vertex : in Vertex) return Natural;

    -- Return the number of arcs originating from the given vertex.
    -- 
    -- Raises : Vertex_is_Null, if the vertex is null.

    function Item_Of (The_Vertex : in Vertex) return Item;

    -- Return the item from the designated vertex.
    -- 
    -- Raises : Vertex_is_Null, if the vertex is null.

    function Attribute_Of (The_Arc : in Arc) return Attribute;

    -- Return the attribute from the designated arc.
    -- 
    -- Raises : Arc_is_Null, if the arc is null.

    function Source_Of (The_Arc : in Arc) return Vertex;

    -- Return the vertex that is the source of the given arc.
    -- 
    -- Raises : Arc_is_Null, if the arc is null.

    function Destination_Of (The_Arc : in Arc) return Vertex;

    -- Return the vertex that is the destination of the given arc.
    -- 
    -- Raises : Arc_is_Null, if the arc is null.

    function Is_A_Member (The_Vertex : in Vertex; Of_The_Graph : in Graph) 
			 return Boolean;

    -- Return True if the designated vertex is contained in the given graph.
    -- 
    -- Raises : Vertex_is_Null, if the vertex is null.

    function Is_A_Member 
		(The_Arc : in Arc; Of_The_Graph : in Graph) return Boolean;

    -- Return True if the designated arc is contained in the given graph.
    -- 
    -- Raises : Arc_is_Null, if the arc is null.

    generic
	with procedure Process (The_Vertex : in Vertex; Continue : out Boolean);
    procedure Iterate_Vertices (Over_The_Graph : in Graph);

    -- Visit every vertex in the given graph.

    generic
	with procedure Process (The_Arc : in Arc; Continue : out Boolean);
    procedure Iterate_Arcs (Over_The_Graph : in Graph);

    -- Visit every arc in the given graph.

    generic
	with procedure Process (The_Arc : in Arc; Continue : out Boolean);
    procedure Reiterate (Over_The_Vertex : in Vertex);

    -- Visit every arc that originates from the given vertex.
    -- 
    -- Raises : Vertex_is_Null, if the vertex is null.

    Overflow : exception renames Structure_Exceptions.Overflow;
    Vertex_Is_Null : exception;
    Vertex_Is_Not_In_Graph : exception;
    Vertex_Has_References : exception;
    Arc_Is_Null : exception;
    Arc_Is_Not_In_Graph : exception;

private

    type Vertex_Node;
    type Vertex is access Vertex_Node;

    package Vertex_Set is 
       new Set_Simple_Sequential_Unbounded_Managed_Iterator (Item => Vertex);

    type Arc_Node;
    type Arc is access Arc_Node;

    package Arc_Set is 
       new Set_Simple_Sequential_Unbounded_Managed_Iterator (Item => Arc);

    type Graph is
	record
	    The_Vertices : Vertex_Set.Set;
	    The_Arcs : Arc_Set.Set;
	end record;

    Null_Vertex : constant Vertex := null;
    Null_Arc : constant Arc := null;

end Graph_Directed_Unbounded_Managed;