File : a-rbtgbk.ads
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-2015, 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 -- --
19 -- --
20 -- --
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
33 with Ada.Containers.Red_Black_Trees.Generic_Bounded_Operations;
34
35 generic
36 with package Tree_Operations is new Generic_Bounded_Operations (<>);
37
38 use Tree_Operations.Tree_Types, Tree_Operations.Tree_Types.Implementation;
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
50 package 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
193 end Ada.Containers.Red_Black_Trees.Generic_Bounded_Keys;