-- 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;