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