gcc/ada/a-crbtgk.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT LIBRARY COMPONENTS                          --
   4 --                                                                          --
   5 --                ADA.CONTAINERS.RED_BLACK_TREES.GENERIC_KEYS               --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 2004-2007, 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 2,  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.  See the GNU General Public License --
  17 -- for  more details.  You should have  received  a copy of the GNU General --
  18 -- Public License  distributed with GNAT;  see file COPYING.  If not, write --
  19 -- to  the  Free Software Foundation,  51  Franklin  Street,  Fifth  Floor, --
  20 -- Boston, MA 02110-1301, USA.                                              --
  21 --                                                                          --
  22 -- As a special exception,  if other files  instantiate  generics from this --
  23 -- unit, or you link  this unit with other files  to produce an executable, --
  24 -- this  unit  does not  by itself cause  the resulting  executable  to  be --
  25 -- covered  by the  GNU  General  Public  License.  This exception does not --
  26 -- however invalidate  any other reasons why  the executable file  might be --
  27 -- covered by the  GNU Public License.                                      --
  28 --                                                                          --
  29 -- This unit was originally developed by Matthew J Heaney.                  --
  30 ------------------------------------------------------------------------------
  31
  32 --  Tree_Type is used to implement ordered containers. This package declares
  33 --  the tree operations that depend on keys.
  34
  35 with Ada.Containers.Red_Black_Trees.Generic_Operations;
  36
  37 generic
  38    with package Tree_Operations is new Generic_Operations (<>);
  39
  40    use Tree_Operations.Tree_Types;
  41
  42    type Key_Type (<>) is limited private;
  43
  44    with function Is_Less_Key_Node
  45      (L : Key_Type;
  46       R : Node_Access) return Boolean;
  47
  48    with function Is_Greater_Key_Node
  49      (L : Key_Type;
  50       R : Node_Access) return Boolean;
  51
  52 package Ada.Containers.Red_Black_Trees.Generic_Keys is
  53    pragma Pure;
  54
  55    generic
  56       with function New_Node return Node_Access;
  57    procedure Generic_Insert_Post
  58      (Tree   : in out Tree_Type;
  59       Y      : Node_Access;
  60       Before : Boolean;
  61       Z      : out Node_Access);
  62    --  Completes an insertion after the insertion position has been
  63    --  determined. On output Z contains a pointer to the newly inserted
  64    --  node, allocated using New_Node. If Tree is busy then
  65    --  Program_Error is raised. If Y is null, then Tree must be empty.
  66    --  Otherwise Y denotes the insertion position, and Before specifies
  67    --  whether the new node is Y's left (True) or right (False) child.
  68
  69    generic
  70       with procedure Insert_Post
  71         (T : in out Tree_Type;
  72          Y : Node_Access;
  73          B : Boolean;
  74          Z : out Node_Access);
  75
  76    procedure Generic_Conditional_Insert
  77      (Tree     : in out Tree_Type;
  78       Key      : Key_Type;
  79       Node     : out Node_Access;
  80       Inserted : out Boolean);
  81    --  Inserts a new node in Tree, but only if the tree does not already
  82    --  contain Key. Generic_Conditional_Insert first searches for a key
  83    --  equivalent to Key in Tree. If an equivalent key is found, then on
  84    --  output Node designates the node with that key and Inserted is
  85    --  False; there is no allocation and Tree is not modified. Otherwise
  86    --  Node designates a new node allocated using Insert_Post, and
  87    --  Inserted is True.
  88
  89    generic
  90       with procedure Insert_Post
  91         (T : in out Tree_Type;
  92          Y : Node_Access;
  93          B : Boolean;
  94          Z : out Node_Access);
  95
  96    procedure Generic_Unconditional_Insert
  97      (Tree : in out Tree_Type;
  98       Key  : Key_Type;
  99       Node : out Node_Access);
 100    --  Inserts a new node in Tree. On output Node designates the new
 101    --  node, which is allocated using Insert_Post. The node is inserted
 102    --  immediately after already-existing equivalent keys.
 103
 104    generic
 105       with procedure Insert_Post
 106         (T : in out Tree_Type;
 107          Y : Node_Access;
 108          B : Boolean;
 109          Z : out Node_Access);
 110
 111       with procedure Unconditional_Insert_Sans_Hint
 112         (Tree    : in out Tree_Type;
 113          Key     : Key_Type;
 114          Node    : out Node_Access);
 115
 116    procedure Generic_Unconditional_Insert_With_Hint
 117      (Tree : in out Tree_Type;
 118       Hint : Node_Access;
 119       Key  : Key_Type;
 120       Node : out Node_Access);
 121    --  Inserts a new node in Tree near position Hint, to avoid having to
 122    --  search from the root for the insertion position. If Hint is null
 123    --  then Generic_Unconditional_Insert_With_Hint attempts to insert
 124    --  the new node after Tree.Last. If Hint is non-null then if Key is
 125    --  less than Hint, it attempts to insert the new node immediately
 126    --  prior to Hint. Otherwise it attempts to insert the node
 127    --  immediately following Hint. We say "attempts" above to emphasize
 128    --  that insertions always preserve invariants with respect to key
 129    --  order, even when there's a hint. So if Key can't be inserted
 130    --  immediately near Hint, then the new node is inserted in the
 131    --  normal way, by searching for the correct position starting from
 132    --  the root.
 133
 134    generic
 135       with procedure Insert_Post
 136         (T : in out Tree_Type;
 137          Y : Node_Access;
 138          B : Boolean;
 139          Z : out Node_Access);
 140
 141       with procedure Conditional_Insert_Sans_Hint
 142         (Tree     : in out Tree_Type;
 143          Key      : Key_Type;
 144          Node     : out Node_Access;
 145          Inserted : out Boolean);
 146
 147    procedure Generic_Conditional_Insert_With_Hint
 148      (Tree     : in out Tree_Type;
 149       Position : Node_Access;       -- the hint
 150       Key      : Key_Type;
 151       Node     : out Node_Access;
 152       Inserted : out Boolean);
 153    --  Inserts a new node in Tree if the tree does not already contain
 154    --  Key, using Position as a hint about where to insert the new node.
 155    --  See Generic_Unconditional_Insert_With_Hint for more details about
 156    --  hint semantics.
 157
 158    function Find
 159      (Tree : Tree_Type;
 160       Key  : Key_Type) return Node_Access;
 161    --  Searches Tree for the smallest node equivalent to Key
 162
 163    function Ceiling
 164      (Tree : Tree_Type;
 165       Key  : Key_Type) return Node_Access;
 166    --  Searches Tree for the smallest node equal to or greater than Key
 167
 168    function Floor
 169      (Tree : Tree_Type;
 170       Key  : Key_Type) return Node_Access;
 171    --  Searches Tree for the largest node less than or equal to Key
 172
 173    function Upper_Bound
 174      (Tree : Tree_Type;
 175       Key  : Key_Type) return Node_Access;
 176    --  Searches Tree for the smallest node greater than Key
 177
 178    generic
 179       with procedure Process (Node : Node_Access);
 180    procedure Generic_Iteration
 181      (Tree : Tree_Type;
 182       Key  : Key_Type);
 183    --  Calls Process for each node in Tree equivalent to Key, in order
 184    --  from earliest in range to latest.
 185
 186    generic
 187       with procedure Process (Node : Node_Access);
 188    procedure Generic_Reverse_Iteration
 189      (Tree : Tree_Type;
 190       Key  : Key_Type);
 191    --  Calls Process for each node in Tree equivalent to Key, but in
 192    --  order from largest in range to earliest.
 193
 194 end Ada.Containers.Red_Black_Trees.Generic_Keys;