gcc/ada/a-crbtgo.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT LIBRARY COMPONENTS                          --
   4 --                                                                          --
   5 --             ADA.CONTAINERS.RED_BLACK_TREES.GENERIC_OPERATIONS            --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 2004-2009, Free Software Foundation, Inc.         --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
  17 --                                                                          --
  18 -- As a special exception under Section 7 of GPL version 3, you are granted --
  19 -- additional permissions described in the GCC Runtime Library Exception,   --
  20 -- version 3.1, as published by the Free Software Foundation.               --
  21 --                                                                          --
  22 -- You should have received a copy of the GNU General Public License and    --
  23 -- a copy of the GCC Runtime Library Exception along with this program;     --
  24 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  25 -- <http://www.gnu.org/licenses/>.                                          --
  26 --                                                                          --
  27 -- This unit was originally developed by Matthew J Heaney.                  --
  28 ------------------------------------------------------------------------------
  29
  30 --  Tree_Type is used to implement the ordered containers. This package
  31 --  declares the tree operations that do not depend on keys.
  32
  33 with Ada.Streams; use Ada.Streams;
  34
  35 generic
  36    with package Tree_Types is new Generic_Tree_Types (<>);
  37    use Tree_Types;
  38
  39    with function  Parent (Node : Node_Access) return Node_Access is <>;
  40    with procedure Set_Parent (Node : Node_Access; Parent : Node_Access) is <>;
  41    with function  Left (Node : Node_Access) return Node_Access is <>;
  42    with procedure Set_Left (Node : Node_Access; Left : Node_Access) is <>;
  43    with function  Right (Node : Node_Access) return Node_Access is <>;
  44    with procedure Set_Right (Node : Node_Access; Right : Node_Access) is <>;
  45    with function  Color (Node : Node_Access) return Color_Type is <>;
  46    with procedure Set_Color (Node : Node_Access; Color : Color_Type) is <>;
  47
  48 package Ada.Containers.Red_Black_Trees.Generic_Operations is
  49    pragma Pure;
  50
  51    function Min (Node : Node_Access) return Node_Access;
  52    --  Returns the smallest-valued node of the subtree rooted at Node
  53
  54    function Max (Node : Node_Access) return Node_Access;
  55    --  Returns the largest-valued node of the subtree rooted at Node
  56
  57    --  NOTE: The Check_Invariant operation was used during early
  58    --  development of the red-black tree. Now that the tree type
  59    --  implementation has matured, we don't really need Check_Invariant
  60    --  anymore.
  61
  62    --  procedure Check_Invariant (Tree : Tree_Type);
  63
  64    function Vet (Tree : Tree_Type; Node : Node_Access) return Boolean;
  65    --  Inspects Node to determine (to the extent possible) whether
  66    --  the node is valid; used to detect if the node is dangling.
  67
  68    function Next (Node : Node_Access) return Node_Access;
  69    --  Returns the smallest node greater than Node
  70
  71    function Previous (Node : Node_Access) return Node_Access;
  72    --  Returns the largest node less than Node
  73
  74    generic
  75       with function Is_Equal (L, R : Node_Access) return Boolean;
  76    function Generic_Equal (Left, Right : Tree_Type) return Boolean;
  77    --  Uses Is_Equal to perform a node-by-node comparison of the
  78    --  Left and Right trees; processing stops as soon as the first
  79    --  non-equal node is found.
  80
  81    procedure Delete_Node_Sans_Free
  82      (Tree : in out Tree_Type;
  83       Node : Node_Access);
  84    --  Removes Node from Tree without deallocating the node. If Tree
  85    --  is busy then Program_Error is raised.
  86
  87    generic
  88       with procedure Free (X : in out Node_Access);
  89    procedure Generic_Delete_Tree (X : in out Node_Access);
  90    --  Deallocates the tree rooted at X, calling Free on each node
  91
  92    generic
  93       with function Copy_Node (Source : Node_Access) return Node_Access;
  94       with procedure Delete_Tree (X : in out Node_Access);
  95    function Generic_Copy_Tree (Source_Root : Node_Access) return Node_Access;
  96    --  Copies the tree rooted at Source_Root, using Copy_Node to copy each
  97    --  node of the source tree. If Copy_Node propagates an exception
  98    --  (e.g. Storage_Error), then Delete_Tree is first used to deallocate
  99    --  the target tree, and then the exception is propagated.
 100
 101    generic
 102       with function Copy_Tree (Root : Node_Access) return Node_Access;
 103    procedure Generic_Adjust (Tree : in out Tree_Type);
 104    --  Used to implement controlled Adjust. On input to Generic_Adjust, Tree
 105    --  holds a bitwise (shallow) copy of the source tree (as would be the case
 106    --  when controlled Adjust is called). On output, Tree holds its own (deep)
 107    --  copy of the source tree, which is constructed by calling Copy_Tree.
 108
 109    generic
 110       with procedure Delete_Tree (X : in out Node_Access);
 111    procedure Generic_Clear (Tree : in out Tree_Type);
 112    --  Clears Tree by deallocating all of its nodes. If Tree is busy then
 113    --  Program_Error is raised.
 114
 115    generic
 116       with procedure Clear (Tree : in out Tree_Type);
 117    procedure Generic_Move (Target, Source : in out Tree_Type);
 118    --  Moves the tree belonging to Source onto Target. If Source is busy then
 119    --  Program_Error is raised. Otherwise Target is first cleared (by calling
 120    --  Clear, to deallocate its existing tree), then given the Source tree, and
 121    --  then finally Source is cleared (by setting its pointers to null).
 122
 123    generic
 124       with procedure Process (Node : Node_Access) is <>;
 125    procedure Generic_Iteration (Tree : Tree_Type);
 126    --  Calls Process for each node in Tree, in order from smallest-valued
 127    --  node to largest-valued node.
 128
 129    generic
 130       with procedure Process (Node : Node_Access) is <>;
 131    procedure Generic_Reverse_Iteration (Tree : Tree_Type);
 132    --  Calls Process for each node in Tree, in order from largest-valued
 133    --  node to smallest-valued node.
 134
 135    generic
 136       with procedure Write_Node
 137         (Stream : not null access Root_Stream_Type'Class;
 138          Node   : Node_Access);
 139    procedure Generic_Write
 140      (Stream : not null access Root_Stream_Type'Class;
 141       Tree   : Tree_Type);
 142    --  Used to implement stream attribute T'Write. Generic_Write
 143    --  first writes the number of nodes into Stream, then calls
 144    --  Write_Node for each node in Tree.
 145
 146    generic
 147       with procedure Clear (Tree : in out Tree_Type);
 148       with function Read_Node
 149         (Stream : not null access Root_Stream_Type'Class) return Node_Access;
 150    procedure Generic_Read
 151      (Stream : not null access Root_Stream_Type'Class;
 152       Tree   : in out Tree_Type);
 153    --  Used to implement stream attribute T'Read. Generic_Read
 154    --  first clears Tree. It then reads the number of nodes out of
 155    --  Stream, and calls Read_Node for each node in Stream.
 156
 157    procedure Rebalance_For_Insert
 158      (Tree : in out Tree_Type;
 159       Node : Node_Access);
 160    --  This rebalances Tree to complete the insertion of Node (which
 161    --  must already be linked in at its proper insertion position).
 162
 163 end Ada.Containers.Red_Black_Trees.Generic_Operations;