1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
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 --
10 -- Copyright (C) 2004-2006, Free Software Foundation, Inc. --
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. --
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. --
30 -- This unit was originally developed by Matthew J Heaney. --
31 ------------------------------------------------------------------------------
33 -- Tree_Type is used to implement ordered containers. This package declares
34 -- the tree operations that depend on keys.
36 with Ada
.Containers
.Red_Black_Trees
.Generic_Operations
;
39 with package Tree_Operations
is new Generic_Operations
(<>);
41 use Tree_Operations
.Tree_Types
;
43 type Key_Type
(<>) is limited private;
45 with function Is_Less_Key_Node
47 R
: Node_Access
) return Boolean;
49 with function Is_Greater_Key_Node
51 R
: Node_Access
) return Boolean;
53 package Ada
.Containers
.Red_Black_Trees
.Generic_Keys
is
57 with function New_Node
return Node_Access
;
58 procedure Generic_Insert_Post
59 (Tree
: in out Tree_Type
;
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.
71 with procedure Insert_Post
72 (T
: in out Tree_Type
;
77 procedure Generic_Conditional_Insert
78 (Tree
: in out Tree_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
91 with procedure Insert_Post
92 (T
: in out Tree_Type
;
97 procedure Generic_Unconditional_Insert
98 (Tree
: in out Tree_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.
106 with procedure Insert_Post
107 (T
: in out Tree_Type
;
110 Z
: out Node_Access
);
112 with procedure Unconditional_Insert_Sans_Hint
113 (Tree
: in out Tree_Type
;
115 Node
: out Node_Access
);
117 procedure Generic_Unconditional_Insert_With_Hint
118 (Tree
: in out Tree_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
136 with procedure Insert_Post
137 (T
: in out Tree_Type
;
140 Z
: out Node_Access
);
142 with procedure Conditional_Insert_Sans_Hint
143 (Tree
: in out Tree_Type
;
145 Node
: out Node_Access
;
146 Inserted
: out Boolean);
148 procedure Generic_Conditional_Insert_With_Hint
149 (Tree
: in out Tree_Type
;
150 Position
: Node_Access
; -- the hint
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
161 Key
: Key_Type
) return Node_Access
;
162 -- Searches Tree for the smallest node equivalent to Key
166 Key
: Key_Type
) return Node_Access
;
167 -- Searches Tree for the smallest node equal to or greater than Key
171 Key
: Key_Type
) return Node_Access
;
172 -- Searches Tree for the largest node less than or equal to Key
176 Key
: Key_Type
) return Node_Access
;
177 -- Searches Tree for the smallest node greater than Key
180 with procedure Process
(Node
: Node_Access
);
181 procedure Generic_Iteration
184 -- Calls Process for each node in Tree equivalent to Key, in order
185 -- from earliest in range to latest.
188 with procedure Process
(Node
: Node_Access
);
189 procedure Generic_Reverse_Iteration
192 -- Calls Process for each node in Tree equivalent to Key, but in
193 -- order from largest in range to earliest.
195 end Ada
.Containers
.Red_Black_Trees
.Generic_Keys
;