------------------------------------------------------------------------------
--                                                                          --
--                         GNAT RUN-TIME COMPONENTS                         --
--                                                                          --
--                           G N A T . G R A P H S                          --
--                                                                          --
--                                 S p e c                                  --
--                                                                          --
--             Copyright (C) 2018-2019, Free Software Foundation, Inc.      --
--                                                                          --
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
--                                                                          --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception,   --
-- version 3.1, as published by the Free Software Foundation.               --
--                                                                          --
-- You should have received a copy of the GNU General Public License and    --
-- a copy of the GCC Runtime Library Exception along with this program;     --
-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
-- <http://www.gnu.org/licenses/>.                                          --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

pragma Compiler_Unit_Warning;

with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables;
with GNAT.Lists;           use GNAT.Lists;
with GNAT.Sets;            use GNAT.Sets;

package GNAT.Graphs is

   ---------------
   -- Component --
   ---------------

   --  The following type denotes a strongly connected component handle
   --  (referred to as simply "component") in a graph.

   type Component_Id is new Natural;
   No_Component : constant Component_Id := Component_Id'First;

   function Hash_Component (Comp : Component_Id) return Bucket_Range_Type;
   --  Map component Comp into the range of buckets

   function Present (Comp : Component_Id) return Boolean;
   --  Determine whether component Comp exists

   ---------------------
   -- Directed_Graphs --
   ---------------------

   --  The following package offers a directed graph abstraction with the
   --  following characteristics:
   --
   --    * Dynamic resizing based on number of vertices and edges
   --    * Creation of multiple instances, of different sizes
   --    * Discovery of strongly connected components
   --    * Iterable attributes
   --
   --  The following use pattern must be employed when operating this graph:
   --
   --    Graph : Directed_Graph := Create (<some size>, <some size>);
   --
   --    <various operations>
   --
   --    Destroy (Graph);
   --
   --  The destruction of the graph reclaims all storage occupied by it.

   generic

      --------------
      -- Vertices --
      --------------

      type Vertex_Id is private;
      --  The handle of a vertex

      No_Vertex : Vertex_Id;
      --  An indicator for a nonexistent vertex

      with function Hash_Vertex (V : Vertex_Id) return Bucket_Range_Type;
      --  Map vertex V into the range of buckets

      with function Same_Vertex
             (Left  : Vertex_Id;
              Right : Vertex_Id) return Boolean;
      --  Compare vertex Left to vertex Right for identity

      -----------
      -- Edges --
      -----------

      type Edge_Id is private;
      --  The handle of an edge

      No_Edge : Edge_Id;
      --  An indicator for a nonexistent edge

      with function Hash_Edge (E : Edge_Id) return Bucket_Range_Type;
      --  Map edge E into the range of buckets

      with function Same_Edge
             (Left  : Edge_Id;
              Right : Edge_Id) return Boolean;
      --  Compare edge Left to edge Right for identity

   package Directed_Graphs is

      --  The following exceptions are raised when an attempt is made to add
      --  the same edge or vertex in a graph.

      Duplicate_Edge   : exception;
      Duplicate_Vertex : exception;

      --  The following exceptions are raised when an attempt is made to delete
      --  or reference a nonexistent component, edge, or vertex in a graph.

      Missing_Component : exception;
      Missing_Edge      : exception;
      Missing_Vertex    : exception;

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

      --  The following type denotes a graph handle. Each instance must be
      --  created using routine Create.

      type Directed_Graph is private;
      Nil : constant Directed_Graph;

      procedure Add_Edge
        (G           : Directed_Graph;
         E           : Edge_Id;
         Source      : Vertex_Id;
         Destination : Vertex_Id);
      --  Add edge E to graph G which links vertex source Source and desination
      --  vertex Destination. The edge is "owned" by vertex Source. This action
      --  raises the following exceptions:
      --
      --    * Duplicate_Edge, when the edge is already present in the graph
      --
      --    * Iterated, when the graph has an outstanding edge iterator
      --
      --    * Missing_Vertex, when either the source or desination are not
      --      present in the graph.

      procedure Add_Vertex
        (G : Directed_Graph;
         V : Vertex_Id);
      --  Add vertex V to graph G. This action raises the following exceptions:
      --
      --    * Duplicate_Vertex, when the vertex is already present in the graph
      --
      --    * Iterated, when the graph has an outstanding vertex iterator

      function Component
        (G : Directed_Graph;
         V : Vertex_Id) return Component_Id;
      --  Obtain the component where vertex V of graph G resides. This action
      --  raises the following exceptions:
      --
      --    * Missing_Vertex, when the vertex is not present in the graph

      function Contains_Component
        (G    : Directed_Graph;
         Comp : Component_Id) return Boolean;
      --  Determine whether graph G contains component Comp

      function Contains_Edge
        (G : Directed_Graph;
         E : Edge_Id) return Boolean;
      --  Determine whether graph G contains edge E

      function Contains_Vertex
        (G : Directed_Graph;
         V : Vertex_Id) return Boolean;
      --  Determine whether graph G contains vertex V

      function Create
        (Initial_Vertices : Positive;
         Initial_Edges    : Positive) return Directed_Graph;
      --  Create a new graph with vertex capacity Initial_Vertices and edge
      --  capacity Initial_Edges. This routine must be called at the start of
      --  a graph's lifetime.

      procedure Delete_Edge
        (G : Directed_Graph;
         E : Edge_Id);
      --  Delete edge E from graph G. This action raises these exceptions:
      --
      --    * Iterated, when the graph has an outstanding edge iterator
      --
      --    * Missing_Edge, when the edge is not present in the graph
      --
      --    * Missing_Vertex, when the source vertex that "owns" the edge is
      --      not present in the graph.

      function Destination_Vertex
        (G : Directed_Graph;
         E : Edge_Id) return Vertex_Id;
      --  Obtain the destination vertex of edge E of graph G. This action
      --  raises the following exceptions:
      --
      --    * Missing_Edge, when the edge is not present in the graph

      procedure Destroy (G : in out Directed_Graph);
      --  Destroy the contents of graph G, rendering it unusable. This routine
      --  must be called at the end of a graph's lifetime. This action raises
      --  the following exceptions:
      --
      --    * Iterated, if the graph has any outstanding iterator

      procedure Find_Components (G : Directed_Graph);
      --  Find all components of graph G. This action raises the following
      --  exceptions:
      --
      --    * Iterated, when the components or vertices of the graph have an
      --      outstanding iterator.

      function Is_Empty (G : Directed_Graph) return Boolean;
      --  Determine whether graph G is empty

      function Number_Of_Component_Vertices
        (G    : Directed_Graph;
         Comp : Component_Id) return Natural;
      --  Obtain the total number of vertices of component Comp of graph G

      function Number_Of_Components (G : Directed_Graph) return Natural;
      --  Obtain the total number of components of graph G

      function Number_Of_Edges (G : Directed_Graph) return Natural;
      --  Obtain the total number of edges of graph G

      function Number_Of_Outgoing_Edges
        (G : Directed_Graph;
         V : Vertex_Id) return Natural;
      --  Obtain the total number of outgoing edges of vertex V of graph G

      function Number_Of_Vertices (G : Directed_Graph) return Natural;
      --  Obtain the total number of vertices of graph G

      function Present (G : Directed_Graph) return Boolean;
      --  Determine whether graph G exists

      function Source_Vertex
        (G : Directed_Graph;
         E : Edge_Id) return Vertex_Id;
      --  Obtain the source vertex that "owns" edge E of graph G. This action
      --  raises the following exceptions:
      --
      --    * Missing_Edge, when the edge is not present in the graph

      -------------------------
      -- Iterator operations --
      -------------------------

      --  The following types represent iterators over various attributes of a
      --  graph. Each iterator locks all mutation operations of its associated
      --  attribute, and unlocks them once it is exhausted. The iterators must
      --  be used with the following pattern:
      --
      --    Iter : Iterate_XXX (Graph);
      --    while Has_Next (Iter) loop
      --       Next (Iter, Element);
      --    end loop;
      --
      --  It is possible to advance the iterators by using Next only, however
      --  this risks raising Iterator_Exhausted.

      --  The following type represents an iterator over all edges of a graph

      type All_Edge_Iterator is private;

      function Has_Next (Iter : All_Edge_Iterator) return Boolean;
      --  Determine whether iterator Iter has more edges to examine

      function Iterate_All_Edges (G : Directed_Graph) return All_Edge_Iterator;
      --  Obtain an iterator over all edges of graph G

      procedure Next
        (Iter : in out All_Edge_Iterator;
         E    : out Edge_Id);
      --  Return the current edge referenced by iterator Iter and advance to
      --  the next available edge. This action raises the following exceptions:
      --
      --    * Iterator_Exhausted, when the iterator has been exhausted and
      --      further attempts are made to advance it.

      --  The following type represents an iterator over all vertices of a
      --  graph.

      type All_Vertex_Iterator is private;

      function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
      --  Determine whether iterator Iter has more vertices to examine

      function Iterate_All_Vertices
        (G : Directed_Graph) return All_Vertex_Iterator;
      --  Obtain an iterator over all vertices of graph G

      procedure Next
        (Iter : in out All_Vertex_Iterator;
         V    : out Vertex_Id);
      --  Return the current vertex referenced by iterator Iter and advance
      --  to the next available vertex. This action raises the following
      --  exceptions:
      --
      --    * Iterator_Exhausted, when the iterator has been exhausted and
      --      further attempts are made to advance it.

      --  The following type represents an iterator over all components of a
      --  graph.

      type Component_Iterator is private;

      function Has_Next (Iter : Component_Iterator) return Boolean;
      --  Determine whether iterator Iter has more components to examine

      function Iterate_Components
        (G : Directed_Graph) return Component_Iterator;
      --  Obtain an iterator over all components of graph G

      procedure Next
        (Iter : in out Component_Iterator;
         Comp : out Component_Id);
      --  Return the current component referenced by iterator Iter and advance
      --  to the next component. This action raises the following exceptions:
      --
      --    * Iterator_Exhausted, when the iterator has been exhausted and
      --      further attempts are made to advance it.

      --  The following type prepresents an iterator over all vertices of a
      --  component.

      type Component_Vertex_Iterator is private;

      function Has_Next (Iter : Component_Vertex_Iterator) return Boolean;
      --  Determine whether iterator Iter has more vertices to examine

      function Iterate_Component_Vertices
        (G    : Directed_Graph;
         Comp : Component_Id) return Component_Vertex_Iterator;
      --  Obtain an iterator over all vertices that comprise component Comp of
      --  graph G.

      procedure Next
        (Iter : in out Component_Vertex_Iterator;
         V    : out Vertex_Id);
      --  Return the current vertex referenced by iterator Iter and advance to
      --  the next vertex. This action raises the following exceptions:
      --
      --    * Iterator_Exhausted, when the iterator has been exhausted and
      --      further attempts are made to advance it.

      --  The following type represents an iterator over all outgoing edges of
      --  a vertex.

      type Outgoing_Edge_Iterator is private;

      function Has_Next (Iter : Outgoing_Edge_Iterator) return Boolean;
      --  Determine whether iterator Iter has more outgoing edges to examine

      function Iterate_Outgoing_Edges
        (G : Directed_Graph;
         V : Vertex_Id) return Outgoing_Edge_Iterator;
      --  Obtain an iterator over all the outgoing edges "owned" by vertex V of
      --  graph G.

      procedure Next
        (Iter : in out Outgoing_Edge_Iterator;
         E    : out Edge_Id);
      --  Return the current outgoing edge referenced by iterator Iter and
      --  advance to the next available outgoing edge. This action raises the
      --  following exceptions:
      --
      --    * Iterator_Exhausted, when the iterator has been exhausted and
      --      further attempts are made to advance it.

   private
      pragma Unreferenced (No_Edge);

      --------------
      -- Edge_Map --
      --------------

      type Edge_Attributes is record
         Destination : Vertex_Id := No_Vertex;
         --  The target of a directed edge

         Source : Vertex_Id := No_Vertex;
         --  The origin of a directed edge. The source vertex "owns" the edge.
      end record;

      No_Edge_Attributes : constant Edge_Attributes :=
        (Destination => No_Vertex,
         Source      => No_Vertex);

      procedure Destroy_Edge_Attributes (Attrs : in out Edge_Attributes);
      --  Destroy the contents of attributes Attrs

      package Edge_Map is new Dynamic_Hash_Tables
        (Key_Type              => Edge_Id,
         Value_Type            => Edge_Attributes,
         No_Value              => No_Edge_Attributes,
         Expansion_Threshold   => 1.5,
         Expansion_Factor      => 2,
         Compression_Threshold => 0.3,
         Compression_Factor    => 2,
         "="                   => Same_Edge,
         Destroy_Value         => Destroy_Edge_Attributes,
         Hash                  => Hash_Edge);

      --------------
      -- Edge_Set --
      --------------

      package Edge_Set is new Membership_Sets
        (Element_Type => Edge_Id,
         "="          => "=",
         Hash         => Hash_Edge);

      -----------------
      -- Vertex_List --
      -----------------

      procedure Destroy_Vertex (V : in out Vertex_Id);
      --  Destroy the contents of a vertex

      package Vertex_List is new Doubly_Linked_Lists
        (Element_Type    => Vertex_Id,
         "="             => Same_Vertex,
         Destroy_Element => Destroy_Vertex);

      ----------------
      -- Vertex_Map --
      ----------------

      type Vertex_Attributes is record
         Component : Component_Id := No_Component;
         --  The component where a vertex lives

         Outgoing_Edges : Edge_Set.Membership_Set := Edge_Set.Nil;
         --  The set of edges that extend out from a vertex
      end record;

      No_Vertex_Attributes : constant Vertex_Attributes :=
        (Component      => No_Component,
         Outgoing_Edges => Edge_Set.Nil);

      procedure Destroy_Vertex_Attributes (Attrs : in out Vertex_Attributes);
      --  Destroy the contents of attributes Attrs

      package Vertex_Map is new Dynamic_Hash_Tables
        (Key_Type              => Vertex_Id,
         Value_Type            => Vertex_Attributes,
         No_Value              => No_Vertex_Attributes,
         Expansion_Threshold   => 1.5,
         Expansion_Factor      => 2,
         Compression_Threshold => 0.3,
         Compression_Factor    => 2,
         "="                   => Same_Vertex,
         Destroy_Value         => Destroy_Vertex_Attributes,
         Hash                  => Hash_Vertex);

      -------------------
      -- Component_Map --
      -------------------

      type Component_Attributes is record
         Vertices : Vertex_List.Doubly_Linked_List := Vertex_List.Nil;
      end record;

      No_Component_Attributes : constant Component_Attributes :=
        (Vertices => Vertex_List.Nil);

      procedure Destroy_Component_Attributes
        (Attrs : in out Component_Attributes);
      --  Destroy the contents of attributes Attrs

      package Component_Map is new Dynamic_Hash_Tables
        (Key_Type              => Component_Id,
         Value_Type            => Component_Attributes,
         No_Value              => No_Component_Attributes,
         Expansion_Threshold   => 1.5,
         Expansion_Factor      => 2,
         Compression_Threshold => 0.3,
         Compression_Factor    => 2,
         "="                   => "=",
         Destroy_Value         => Destroy_Component_Attributes,
         Hash                  => Hash_Component);

      -----------
      -- Graph --
      -----------

      type Directed_Graph_Attributes is record
         All_Edges : Edge_Map.Dynamic_Hash_Table := Edge_Map.Nil;
         --  The map of edge -> edge attributes for all edges in the graph

         All_Vertices : Vertex_Map.Dynamic_Hash_Table := Vertex_Map.Nil;
         --  The map of vertex -> vertex attributes for all vertices in the
         --  graph.

         Components : Component_Map.Dynamic_Hash_Table := Component_Map.Nil;
         --  The map of component -> component attributes for all components
         --  in the graph.
      end record;

      type Directed_Graph is access Directed_Graph_Attributes;
      Nil : constant Directed_Graph := null;

      ---------------
      -- Iterators --
      ---------------

      type All_Edge_Iterator         is new Edge_Map.Iterator;
      type All_Vertex_Iterator       is new Vertex_Map.Iterator;
      type Component_Iterator        is new Component_Map.Iterator;
      type Component_Vertex_Iterator is new Vertex_List.Iterator;
      type Outgoing_Edge_Iterator    is new Edge_Set.Iterator;
   end Directed_Graphs;

private
   First_Component : constant Component_Id := No_Component + 1;

end GNAT.Graphs;