gcc/ada/a-crbtgk.ads

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