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