File : asgc-graph.ads


-- The Ada Structured Library - A set of container classes and general
--   tools for use with Ada95.
-- Copyright (C) 1998-1999  Corey Minyard (minyard@acm.org)
--
-- This library is free software; you can redistribute it and/or modify it
-- under the terms of the GNU General Public License as published by the
-- Free Software Foundation; either version 2 of the License, or (at your
-- option) any later version.
--
-- This library 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 GNU
-- General Public License for more details.
--
-- You should have received a copy of the GNU General Public License along
-- with this library; if not, write to the Free Software Foundation, Inc.,
-- 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
--
-- As a special exception, if other files instantiate generics from this
-- unit, or you link this unit with other files to produce an executable,
-- this unit does not by itself cause the resulting executable to be
-- covered by the GNU General Public License.  This exception does not
-- however invalidate any other reasons why the executable file might be
-- covered by the GNU Public License.
--

-- This package implements a graph container.  A graph is a set of nodes
-- that are connected with links.  The nodes contain a user value and the
-- links may also contain a (different) user value.  The value for a graph
-- node is the base value for the container classes (defined in the Asgc
-- package), the value for a graph link is specified in Link_Contained_Type
-- below.  Note that internally, a graph uses a hash table to keep track of
-- values.  Unfortunately, this must be exposed because a hash function is
-- needed to keep track of the values and a hash table size must also be
-- specified.
--

generic
   type Link_Contained_Type is private;
   with function Do_Hash (Val : in Contained_Type) return Natural;
package Asgc.Graph is

   ------------------------------------------------------------------------
   -- This is the graph container.
   type Object is abstract new Asgc.Object with private;
   type Object_Class is access all Object'Class;

   function "=" (O1, O2 : in Object) return Boolean is abstract;

   -- Add a link between the given values.
   procedure Add_Link (O          : in out Object;
                       From       : in Contained_Type;
                       To         : in Contained_Type;
                       Contents   : in Link_Contained_Type;
                       Ignore_Dup : in Boolean      := True)
      is abstract;

   function Link_Exists (O     : in Object;
                         From  : in Contained_Type;
                         To    : in Contained_Type)
                         return Boolean
      is abstract;

   -- Callbacks for adding and removing links.  If Set_Link_Callbacks is
   -- called with a non-null value, the callbacks for that object will be
   -- called accordingly.
   -- IMPORTANT - With regular graphs, these functions will be called
   --             TWICE for every link added, deleted, or copied, since
   --             the link goes both directions.  The methods must account
   --             for this properly, especially if they generate a new
   --             copy, since each link direction will have a different
   --             copy in that case.  The methods should not assume any
   --             calling order, so doing something like "Odd adds are
   --             real and even one just use the last value" is dangerous.
   --             This does NOT apply to directed graphs.
   type Link_Callbacks is abstract new Baseclass.Object with private;
   type Link_Callbacks_Class is access all Link_Callbacks'Class;

   -- A link was added to the container.
   procedure Added (Cb  : access Link_Callbacks;
                    O   : in Object'Class;
                    Val : in out Link_Contained_Type)
      is abstract;

   -- A link was copied to a new container.
   procedure Copied (Cb  : access Link_Callbacks;
                     O   : in Object'Class;
                     Val : in out Link_Contained_Type)
      is abstract;

   -- A link was deleted from a container.
   procedure Deleted (Cb  : access Link_Callbacks;
                      O   : in Object'Class;
                      Val : in out Link_Contained_Type)
      is abstract;


   -- Set the link callbacks for an object.  Setting it to null will turn
   -- the callbacks off.
   procedure Set_Link_Callbacks (O  : in out Object;
                                 Cb : in Link_Callbacks_Class);


   ------------------------------------------------------------------------
   -- An iterator for a graph container.
   type Iterator is abstract new Asgc.Iterator with private;
   type Iterator_Class is access all Iterator'Class;

   function "=" (Iter1, Iter2 : in Iterator) return Boolean is abstract;

   ------------------------------------------------------------------------
   -- A single element in a graph has "links" to other graph nodes, thus it
   -- needs a way to move through these.  Each element in a graph contains
   -- a set of links to other elements in the graph.  The iterator, in
   -- addition to being positioned on a graph element, has a subposition
   -- that iterates through the links for a graph element.

   -- Add a link from the "From" iterator's element to the "To" iterators
   -- element.  If Ignore_Dup is True, the call will not perform an action
   -- if the link already exists.  If Ignore_Dup is False, the call will
   -- raise Link_Already_Exists if the link already exists.
   procedure Add_Link (From       : in out Iterator;
                       To         : in out Iterator;
                       Contents   : in Link_Contained_Type;
                       Ignore_Dup : in Boolean      := True)
      is abstract;

   -- Two more add_link routines that reference a contained type and one
   -- iterator.
   procedure Add_Link (From       : in out Iterator;
                       To         : in Contained_Type;
                       Contents   : in Link_Contained_Type;
                       Ignore_Dup : in Boolean      := True)
      is abstract;

   procedure Add_Link (From       : in Contained_Type;
                       To         : in out Iterator;
                       Contents   : in Link_Contained_Type;
                       Ignore_Dup : in Boolean      := True)
      is abstract;

   -- Delete the link the the current iterator references.  Raises
   -- Invalid_Link if the iterator has no link position.
   procedure Delete_Link (Iter : in out Iterator; Is_End : out End_Marker)
      is abstract;

   -- Find a link from the "From" iterator's current position to the "To"
   -- iterator.  Raises Item_Not_Found if the link does not exist.
   function Find_Link (From : in Iterator;
                       To   : in Iterator)
                       return Iterator
      is abstract;

   function Find_Link (From : in Iterator;
                       To   : in Contained_Type)
                       return Iterator
      is abstract;

   function Find_Link (From : in Contained_Type;
                       To   : in Iterator)
                       return Iterator
      is abstract;

   -- Search the "From" iterator's current position for a link to the "To"
   -- iterator.  If Found returns True, the link was found and "From" will
   -- be positioned on that link.  If Found returns False, the link was not
   -- found and the "From" iterator is not modified.
   procedure Find_Link (From  : in out Iterator;
                        To    : in Iterator;
                        Found : out Boolean)
      is abstract;

   procedure Find_Link (From  : in out Iterator;
                        To    : in Contained_Type;
                        Found : out Boolean)
      is abstract;


   -- Search from the "From" iterator's next position for another link with
   -- the same value as the current value of "From".  If Found returns
   -- True, the link was found and "From" will be positioned on that link.
   -- If Found returns False, the link was not found and the "From"
   -- iterator is not modified.
   procedure Find_Link_Again (From  : in out Iterator;
                              Found : out Boolean)
      is abstract;

   -- Returns True if there is a link from From to To, False if not.
   function Link_Exists (From  : in Iterator;
                         To    : in Iterator)
                         return Boolean
      is abstract;

   function Link_Exists (From  : in Iterator;
                         To    : in Contained_Type)
                         return Boolean
      is abstract;

   function Link_Exists (From  : in Contained_Type;
                         To    : in Iterator)
                         return Boolean
      is abstract;


   -- Move the iterator to the first link in the iterator's current
   -- location.  Is_End will be set to Past_End if the member has no links.
   procedure First_Link (Iter : in out Iterator; Is_End : out End_Marker)
      is abstract;

   -- Move the iterator to the next link in the iterator's current
   -- location.  Raises Invalid_Iterator if the iterator has no link
   -- position.  Is_End will be set to Past_End and the iterator will not
   -- be modified if the iterator is at the last link in the member.
   procedure Next_Link (Iter : in out Iterator; Is_End : out End_Marker)
      is abstract;

   -- Follow the current link in the iterators current location, returning
   -- an iterator that is positioned on the element the current link
   -- references.  Raises Invalid_Iterator if the iterator has no link
   -- position.
   function Follow_Link (Iter : in Iterator) return Iterator
      is abstract;

   -- Follow a link, but move the iterator itself to the position where it
   -- points.  Raises Invalid_Iterator if the iterator has no link
   -- position.
   procedure Follow_Link (Iter : in out Iterator)
      is abstract;

   -- Return the number of links in the current element of the iterator.
   function Link_Count (Iter : in Iterator) return Natural
      is abstract;

   -- Return the user value contained in the link
   function Get_Link (Iter : in Iterator) return Link_Contained_Type
      is abstract;

   -- Set the user value contained in the link.
   procedure Set_Link (Iter : in out Iterator;
                       Val  : in Link_Contained_Type)
      is abstract;


   ------------------------------------------------------------------------
   -- Nodes in the graph will descend from this type.  Nodes must be based
   -- upon a tagged type for polymorphism with links, but don't use
   -- Baseclass.Object because of the overhead of it being controlled.  The
   -- graph container handles calling the proper routines for adjusting and
   -- finalizing graph links.
   type Node_Base is abstract tagged private;
   type Node_Base_Class is access all Node_Base'Class;

   ------------------------------------------------------------------------
   -- Graphs can be dynamic, fixed, or expandable.  As well, the individual
   -- elements may also be in those categories, and it is independent of
   -- the graph type.  A dynamic element uses dynamic allocation for each
   -- link.  A fixed element has a fixed maximum number of links in an
   -- array.  An expandable uses an array like a fixed element, but the
   -- array will resize to grow as it fills up.  These work much like
   -- iterators.


   Internal_Graph_Error : exception;

private

   type Object is abstract new Asgc.Object with record
      Link_Cb : Link_Callbacks_Class := null;
   end record;

   type Link_Callbacks is abstract new Baseclass.Object with null record;

   type Iterator is abstract new Asgc.Iterator with null record;

   type Node_Base is abstract tagged null record;

end Asgc.Graph;