|
111
|
1 ------------------------------------------------------------------------------
|
|
|
2 -- --
|
|
|
3 -- GNAT LIBRARY COMPONENTS --
|
|
|
4 -- --
|
|
|
5 -- ADA.CONTAINERS.RED_BLACK_TREES.GENERIC_BOUNDED_KEYS --
|
|
|
6 -- --
|
|
|
7 -- S p e c --
|
|
|
8 -- --
|
|
145
|
9 -- Copyright (C) 2004-2019, Free Software Foundation, Inc. --
|
|
111
|
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
|
|
|
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;
|
