File : bc-graphs.ads


-- Copyright (C) 1994-1999 Grady Booch and Simon Wright.
-- All Rights Reserved.
--
--      This program is free software; you can redistribute it
--      and/or modify it under the terms of the Ada Community
--      License which comes with this Library.
--
--      This program is distributed in the hope that it will be
--      useful, but WITHOUT ANY WARRANTY; without even the implied
--      warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
--      PURPOSE. See the Ada Community License for more details.
--      You should have received a copy of the Ada Community
--      License with this library, in the file named "Ada Community
--      License" or "ACL". If not, contact the author of this library
--      for a copy.
--

-- $Id: bc-graphs.ads,v 1.9.2.1 1999/12/31 15:17:02 simon Exp $

with Ada.Finalization;
with BC.Smart;
with System.Storage_Pools;

generic
  type Vertex_Item is private;
  with function "=" (L, R : Vertex_Item) return Boolean is <>;
  type Arc_Item is private;
  with function "=" (L, R : Arc_Item) return Boolean is <>;
  type Storage_Manager (<>)
  is new System.Storage_Pools.Root_Storage_Pool with private;
  Storage : in out Storage_Manager;
package BC.Graphs is

  pragma Elaborate_Body;

  -- A directed graph is an unrooted collection of vertices and directed
  -- arcs where cycles and cross-references are not permitted. An
  -- undirected graph is an unrooted collection of vertices and undirected
  -- arcs where cycles and cross-references are permitted. Three types
  -- collaborate to form the abstraction of a directed and undirected
  -- graph: a graph type, a vertex type, and an arc type.

  -- Directed and undirected graphs are monolithic structures although
  -- copying, assignment, and equality are prohibited. Their vertices and
  -- arcs are polylithic structures, and hence the semantics of copying,
  -- assignment, and equality involve structural sharing. Care must be
  -- taken in manipulating the same vertex or arc named by more than one
  -- alias.

  -- These classes are not intended to be subclassed.

  -- These abstractions have been carefully constructed to eliminate all
  -- storage leaks, except in the case of intentional abuses. When a graph
  -- is manipulated, all items that become unreachable are automatically
  -- reclaimed. Furthermore, this design protects against dangling
  -- references: an item is never reclaimed if there exists a reference to
  -- it.

  -- Each vertex and arc is a member of exactly one graph; furthermore, the
  -- vertices at both ends of an arc are guaranteed to be members of the
  -- same graph as the arc. This guarantee is provided by an implementation
  -- strategy whereby every graph is given a unique identity, and each
  -- vertex and arc is created only in the context of a particular graph.

  -- Note that objects of type Vertex, Arc are handles or references to the
  -- actual Graph components.

  -- Note that Containers contain just one sort of Item; Graphs aren't
  -- therefore Containers.

  type Graph is abstract new Ada.Finalization.Limited_Controlled with private;
  type Graph_Ptr is access all Graph'Class;

  type Vertex is abstract new Ada.Finalization.Controlled with private;

  type Arc is abstract new Ada.Finalization.Controlled with private;

  ----------------------
  -- Graph operations --
  ----------------------

  procedure Clear (G : in out Graph);
  -- Destroy all the vertices in the graph, and by implication, all the
  -- arcs in the graph. The semantics of destroy are such that any aliased
  -- vertices and arcs are not eliminated from the graph, because to do so
  -- would introduce dangling references.

  procedure Create_Vertex (G : in out Graph;
                           V : in out Vertex'Class;
                           I : Vertex_Item);
  -- Create a new vertex and add it to the graph, setting the second
  -- argument of this function as an alias to this new vertex.

  -- Arc creation is provided in concrete derivations.

  procedure Destroy_Vertex (G : in out Graph;
                            V : in out Vertex'Class);
  -- Destroy the given vertex and any associated arcs. If the vertex has no
  -- other aliases, eliminate it from the graph.

  procedure Destroy_Arc (G : in out Graph;
                         A : in out Arc'Class);
  -- Destroy the given arc and any associated vertices. If the arc has no
  -- other aliases, eliminate it from the graph.

  function Number_Of_Vertices (G : Graph) return Natural;
  -- Return the number of vertices in the graph.

  function Is_Empty (G : Graph) return Boolean;
  -- Return True if and only if the graph does not contain any vertices or
  -- arcs.

  function Is_Member (G : Graph; V : Vertex'Class) return Boolean;
  -- Return True if and only if the given vertex is not null and denotes a
  -- vertex in the graph.

  function Is_Member (G : Graph; A : Arc'Class) return Boolean;
  -- Return True if and only if the given arc is not null and denotes an
  -- arc in the graph.

  -----------------------
  -- Vertex operations --
  -----------------------

  function "=" (L, R : Vertex) return Boolean;
  -- Return True if and only if both vertices are null or are an alias to
  -- the same vertex.

  procedure Clear (V : in out Vertex);
  -- If the vertex is not null, remove this alias.

  procedure Set_Item (V : in out Vertex; I : Vertex_Item);
  -- Set the item of the given vertex.

  function Is_Null (V : Vertex) return Boolean;
  -- Return True if and only if the vertex is null.

  function Is_Shared (V : Vertex) return Boolean;
  -- Return True if and only if the vertex has other aliases.

  function Item (V : Vertex) return Vertex_Item;
  -- Return the item associated with the vertex.

  generic
    with procedure Process (I : in out Vertex_Item);
  procedure Access_Vertex_Item (V : Vertex'Class);
  -- Process has read-write access to the item associated with the vertex.

  function Enclosing_Graph (V : Vertex) return Graph_Ptr;
  -- Return the graph enclosing the vertex.

  --------------------
  -- Arc operations --
  --------------------

  function "=" (L, R : Arc) return Boolean;
  -- Return True if and only if both arcs are null or are an alias to the
  -- same arc.

  procedure Clear (A : in out Arc);
  -- If the arc is not null, remove this alias.

  procedure Set_Item (A : in out Arc; I : Arc_Item);
  -- Set the item of the given arc.

  function Is_Null (A : Arc) return Boolean;
  -- Return 1 if and only if the arc is null.

  function Is_Shared (A : Arc) return Boolean;
  -- Return True if and only if the arc has other aliases.

  function Item (A : Arc) return Arc_Item;
  -- Return the item associated with the arc.

  generic
    with procedure Process (I : in out Arc_Item);
  procedure Access_Arc_Item (A : Arc'Class);
  -- Process has read-write access to the item associated with the arc.

  function Enclosing_Graph (A : Arc) return Graph_Ptr;
  -- Return the graph enclosing the arc.

  --------------------------------------------
  -- Iteration over the Vertices in a Graph --
  --------------------------------------------

  -- Active iteration

  type Graph_Iterator (<>) is private;

  function New_Graph_Iterator (For_The_Graph : Graph) return Graph_Iterator
    is abstract;
  -- Return a reset Graph_Iterator bound to the specific Graph.

  procedure Reset (Obj : in out Graph_Iterator);
  -- Reset the Graph_Iterator to the beginning.

  procedure Next (Obj : in out Graph_Iterator);
  -- Advance the Graph_Iterator to the next Vertex in the Graph.

  function Is_Done (Obj : Graph_Iterator) return Boolean;
  -- Return True if there are no more Vertices in the Graph.

  function Current_Vertex (Obj : Graph_Iterator) return Vertex'Class;
  -- Return a handle on the current Vertex.

  -- Passive iteration

  generic
    with procedure Apply (Elem : in Vertex'Class; OK : out Boolean);
  procedure Visit_Vertices (Using : in out Graph_Iterator);
  -- Call Apply with a handle on each Vertex in the Graph to which the
  -- iterator Using is bound. The iteration will terminate early if Apply
  -- sets OK to False.

  ---------------------------------------------------
  -- Iteration over the Arcs connected to a Vertex --
  ---------------------------------------------------

  -- Note, in the case of a Directed Graph, these iterators only cover the
  -- outgoing arcs. See BC.Graphs.Directed_Graphs for iteration over
  -- incoming arcs.

  -- Active iteration

  type Vertex_Iterator (<>) is private;

  function New_Vertex_Iterator (For_The_Vertex : Vertex) return Vertex_Iterator
    is abstract;
  -- Return a reset Vertex_Iterator bound to the specific Vertex.

  procedure Reset (Obj : in out Vertex_Iterator);
  -- Reset the Vertex_Iterator to the beginning.

  procedure Next (Obj : in out Vertex_Iterator);
  -- Advance the Vertex_Iterator to the next Arc in the Vertex.

  function Is_Done (Obj : Vertex_Iterator) return Boolean;
  -- Return True if there are no more Arcs in the Vertex.

  function Current_Arc (Obj : Vertex_Iterator) return Arc'Class;
  -- Return a handle on the current Arc.

  -- Passive iteration

  generic
    with procedure Apply (Elem : in Arc'Class; OK : out Boolean);
  procedure Visit_Arcs (Using : in out Vertex_Iterator);
  -- Call Apply with a handle on each Arc in the Vertex to which the
  -- iterator Using is bound. The iteration will terminate early if Apply
  -- sets OK to False.

private

  type Vertex_Node;
  type Vertex_Node_Ptr is access Vertex_Node;
  for Vertex_Node_Ptr'Storage_Pool use Storage;
  type Arc_Node;
  type Arc_Node_Ptr is access Arc_Node;
  for Arc_Node_Ptr'Storage_Pool use Storage;

  -- A Vertex Node is a simple node consisting of an item, a pointer to the
  -- enclosing graph, a pointer to the next vertex, pointers to the
  -- outgoing and incoming arcs, and a reference count
  -- XXX controlled only for check at finalization
  type Vertex_Node is new Ada.Finalization.Controlled with record
    Item : Vertex_Item;
    Enclosing : Graph_Ptr;
    Incoming : Arc_Node_Ptr;
    Outgoing : Arc_Node_Ptr;
    Next : Vertex_Node_Ptr;
    Count : Natural;
  end record;
  procedure Clear_Vertex_Node (G : in out Graph'Class;
                               N : in out Vertex_Node_Ptr);
  procedure Finalize (V : in out Vertex_Node);

  -- An Arc Node is a simple node consisting of an item, a pointer to the
  -- enclosing graph, a pointer to the next arc, pointers to the vertices
  -- to and from the arc, and a reference count
  -- XXX controlled only for check at finalization
  type Arc_Node is new Ada.Finalization.Controlled with record
    Item : Arc_Item;
    Enclosing : Graph_Ptr;
    From : Vertex_Node_Ptr;
    To : Vertex_Node_Ptr;
    Next_Incoming : Arc_Node_Ptr;
    Next_Outgoing : Arc_Node_Ptr;
    Count : Natural;
  end record;
  procedure Finalize (A : in out Arc_Node);

  type Graph is abstract new Ada.Finalization.Limited_Controlled with record
    Rep : Vertex_Node_Ptr;
  end record;
  procedure Finalize (G : in out Graph);

  type Vertex is abstract new Ada.Finalization.Controlled with record
    Rep : Vertex_Node_Ptr;
  end record;
  procedure Adjust (V : in out Vertex);
  procedure Finalize (V : in out Vertex);

  type Arc is abstract new Ada.Finalization.Controlled with record
    Rep : Arc_Node_Ptr;
  end record;
  procedure Adjust (A : in out Arc);
  procedure Finalize (A : in out Arc);

  -- Actual_Graph_Iterators are strongly dependent on the concrete Graph
  -- implementation. The externally-visible Graph_Iterator is implemented as
  -- a (smart) pointer to the specific Graph's Actual_Graph_Iterator.
  --
  -- All the primitive subprograms of Graph_Iterator are implemented in terms
  -- of matching subprograms of Actual_Graph_Iterator.

  type Actual_Graph_Iterator (For_The_Graph : access Graph'Class)
  is abstract new Ada.Finalization.Limited_Controlled with null record;

  type Graph_Iterator_P is access Actual_Graph_Iterator'Class;

  type Vertex_Ptr is access Vertex'Class;

  procedure Reset (Obj : in out Actual_Graph_Iterator) is abstract;

  procedure Next (Obj : in out Actual_Graph_Iterator) is abstract;

  function Is_Done (Obj : Actual_Graph_Iterator) return Boolean is abstract;

  function Current_Vertex (Obj : Actual_Graph_Iterator) return Vertex'Class
    is abstract;

  package GSP is new BC.Smart (T => Actual_Graph_Iterator'Class,
                               P => Graph_Iterator_P);

  type Graph_Iterator is new GSP.Pointer;

  -- Actual_Vertex_Iterators are strongly dependent on the concrete Vertex
  -- implementation. The externally-visible Vertex_Iterator is implemented as
  -- a (smart) pointer to the specific Vertex's Actual_Vertex_Iterator.
  --
  -- All the primitive subprograms of Vertex_Iterator are implemented in terms
  -- of matching subprograms of Actual_Vertex_Iterator.

  type Actual_Vertex_Iterator (For_The_Vertex : access Vertex'Class)
  is abstract new Ada.Finalization.Limited_Controlled with null record;

  type Vertex_Iterator_P is access Actual_Vertex_Iterator'Class;

  type Arc_Ptr is access Arc'Class;

  procedure Reset (Obj : in out Actual_Vertex_Iterator) is abstract;

  procedure Next (Obj : in out Actual_Vertex_Iterator) is abstract;

  function Is_Done (Obj : Actual_Vertex_Iterator) return Boolean is abstract;

  function Current_Arc (Obj : Actual_Vertex_Iterator) return Arc'Class
    is abstract;

  package VSP is new BC.Smart (T => Actual_Vertex_Iterator'Class,
                               P => Vertex_Iterator_P);

  type Vertex_Iterator is new VSP.Pointer;


end BC.Graphs;