File : asgc-graph-links.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 contains the links (or edges, or arcs) between nodes in a
-- graph. It implements it using two generic parameters:
-- Link_Type - the way to reference another node in a graph.
-- Link_Contained_Type - A user data value that is stored and return
-- but not operated on.
--
-- This package instantiates Graph_Link and Graph_Link iterators as
-- abstract types.
-- Note that the "Value" operated on in all these functions is a node
-- pointer or index (depending on Link_Type).
--
-- Users can create their own link types. If they have lots of links on a
-- node, a hash table of links might be nice, for instance. If they do
-- this they must instantiate this generic with the proper types and then
-- subclass Graph_Link and Graph_Link_It. In addition, three different
-- type of link are already defined in subpackages:
--
-- Dynamic - keeps a linked list of graph links, each allocated
-- with new.
--
-- Fixed - keeps a fixed-sized array of graph links. Since the
-- size (number of array elements) can't be specified here, this type
-- itself is in its own generic that takes a size parameter.
--
-- Expandable - are like fixed links, but its array is
-- dynamically allocated and will grow as necessary (by reallocation).
-- Like fixed links, it is declared in its own generic but it takes two
-- parmeters: an initial size and an amount it increase the array on every
-- reallocation.
--
generic
type Link_Type is private;
type Link_Contained_Type is private;
package Asgc.Graph.Links is
-- A node in a graph, which holds links. Note that a node can hold more
-- than one distinct link to the same other node. Graph nodes have to
-- have the property that if we add the same value to the same node more
-- than one time, A(1), A(2), and A(3), and we add another value to
-- another node the same number of times, B(1), B(2), B(3), the A and B
-- values will occur in the same order (If A(3) is first in one node,
-- then B(3) is first in the second node) through other deletions and
-- additions. Since we support multiple links between two nodes, we
-- must be able to find the right link back for deletion, this property
-- says that if we are the Nth instance in our node, then the link back
-- to us will be the Nth instance of the link back in the remote node.
-- The graph data structures will never copy a link, so there is never a
-- call to Adjust or the likes.
type Graph_Link is abstract tagged private;
type Graph_Link_Class is access all Graph_Link'Class;
-- Called when the user is done with the graph link and is about to
-- destroy it. This can be used to free data and clean up.
procedure Free_Graph_Link (Node : in out Graph_Link)
is abstract;
-- Called when a link is copied. This is so the graph links can track
-- their data properly and generate new copies if necessary.
procedure Copied_Graph_Link (Node : in out Graph_Link)
is abstract;
type Graph_Link_It is abstract tagged private;
-- Set the node that the iterator references.
procedure Set_Node (Iter : in out Graph_Link_It;
Node : in Graph_Link_Class)
is abstract;
-- Add a link to a node. The Contents is associated data that can be
-- held in the link.
procedure Add (Node : in out Graph_Link;
Val : in Link_Type;
Contents : in Link_Contained_Type)
is abstract;
-- Delete the first link from the node.
procedure Delete_First (Node : in out Graph_Link)
is abstract;
-- Find the first link holding "Val" and delete it.
procedure Delete_Val (Node : in out Graph_Link;
Val : in Link_Type;
Instance : in Positive := 1)
is abstract;
-- Return the value at the given numeric position.
function Get_Pos (Node : in Graph_Link;
Pos : in Positive)
return Link_Type
is abstract;
-- Return True if the value is in one of the links in the node and False
-- if it does not exist.
function Val_Exists (Node : in Graph_Link;
Val : in Link_Type;
Instance : in Positive := 1)
return Boolean
is abstract;
-- Delete the link the iterator currently references.
procedure Delete (Iter : in out Graph_Link_It;
Is_End : out End_Marker)
is abstract;
-- Move the iterator to the first link in the node.
procedure First (Iter : in out Graph_Link_It;
Is_End : out End_Marker)
is abstract;
-- Move the iterator to the Next link in the node.
procedure Next (Iter : in out Graph_Link_It;
Is_End : out End_Marker)
is abstract;
-- Find "Val" in the current node and move the iterator to if. If Val
-- is not a link in the current node, Found will be False and the
-- iterator will not be modified.
procedure Find (Iter : in out Graph_Link_It;
Val : in Link_Type;
Found : out Boolean;
Instance : in Positive := 1)
is abstract;
-- Search forward in the iterator for the same value the iterator
-- currently references.
procedure Find_Again (Iter : in out Graph_Link_It;
Found : out Boolean)
is abstract;
-- Return the instance number of the value the iterator currently
-- references. A value may occur more than once in the node and they
-- will have a specific order. The first will return 1, the second 2,
-- and so on.
function Get_Instance_Number (Iter : in Graph_Link_It)
return Positive
is abstract;
-- Same as above, but works on absolute position.
function Get_Instance_Number (Node : in Graph_Link;
Pos : in Positive)
return Positive
is abstract;
-- Get the value of the link the iterator references.
function Get (Iter : in Graph_Link_It) return Link_Type
is abstract;
-- Get the contents of the link the iterator references.
function Get_Contents (Iter : in Graph_Link_It)
return Link_Contained_Type
is abstract;
-- Get the contents of the first link holding that specified value.
function Get_Contents (Node : in Graph_Link;
Val : in Link_Type;
Instance : in Positive := 1)
return Link_Contained_Type
is abstract;
-- Get the contents of the value at the beginning of the list of
-- links.
function Get_First_Contents (Node : in Graph_Link)
return Link_Contained_Type
is abstract;
-- Set the contents of the link the iterator references.
procedure Set_Contents (Iter : in out Graph_Link_It;
Contents : in Link_Contained_Type)
is abstract;
-- Return the number of links in the current node.
function Link_Count (Node : in Graph_Link) return Natural
is abstract;
private
type Update_Count is mod 2 ** 32;
Invalid_Update : constant Update_Count := 0 - 1;
type Graph_Link is abstract tagged record
Update : Update_Count := 0;
end record;
type Graph_Link_It is abstract tagged record
Update : Update_Count := Invalid_Update;
end record;
end Asgc.Graph.Links;