]>
Commit | Line | Data |
---|---|---|
4c2d6a70 AC |
1 | ------------------------------------------------------------------------------ |
2 | -- -- | |
3 | -- GNAT LIBRARY COMPONENTS -- | |
4 | -- -- | |
8704d4b3 | 5 | -- A D A . C O N T A I N E R S . O R D E R E D _ S E T S -- |
4c2d6a70 AC |
6 | -- -- |
7 | -- S p e c -- | |
8 | -- -- | |
748086b7 | 9 | -- Copyright (C) 2004-2009, Free Software Foundation, Inc. -- |
4c2d6a70 AC |
10 | -- -- |
11 | -- This specification is derived from the Ada Reference Manual for use with -- | |
12 | -- GNAT. The copyright notice above, and the license provisions that follow -- | |
13 | -- apply solely to the contents of the part following the private keyword. -- | |
14 | -- -- | |
15 | -- GNAT is free software; you can redistribute it and/or modify it under -- | |
16 | -- terms of the GNU General Public License as published by the Free Soft- -- | |
748086b7 | 17 | -- ware Foundation; either version 3, or (at your option) any later ver- -- |
4c2d6a70 AC |
18 | -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- |
19 | -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- | |
748086b7 JJ |
20 | -- or FITNESS FOR A PARTICULAR PURPOSE. -- |
21 | -- -- | |
22 | -- As a special exception under Section 7 of GPL version 3, you are granted -- | |
23 | -- additional permissions described in the GCC Runtime Library Exception, -- | |
24 | -- version 3.1, as published by the Free Software Foundation. -- | |
25 | -- -- | |
26 | -- You should have received a copy of the GNU General Public License and -- | |
27 | -- a copy of the GCC Runtime Library Exception along with this program; -- | |
28 | -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- | |
29 | -- <http://www.gnu.org/licenses/>. -- | |
4c2d6a70 AC |
30 | -- -- |
31 | -- This unit was originally developed by Matthew J Heaney. -- | |
32 | ------------------------------------------------------------------------------ | |
33 | ||
2a6b365a MH |
34 | private with Ada.Containers.Red_Black_Trees; |
35 | private with Ada.Finalization; | |
36 | private with Ada.Streams; | |
4c2d6a70 AC |
37 | |
38 | generic | |
4c2d6a70 AC |
39 | type Element_Type is private; |
40 | ||
41 | with function "<" (Left, Right : Element_Type) return Boolean is <>; | |
42 | with function "=" (Left, Right : Element_Type) return Boolean is <>; | |
43 | ||
44 | package Ada.Containers.Ordered_Sets is | |
ba355842 | 45 | pragma Preelaborate; |
f97ccb3a | 46 | pragma Remote_Types; |
ba355842 MH |
47 | |
48 | function Equivalent_Elements (Left, Right : Element_Type) return Boolean; | |
4c2d6a70 AC |
49 | |
50 | type Set is tagged private; | |
9b832db5 | 51 | pragma Preelaborable_Initialization (Set); |
4c2d6a70 AC |
52 | |
53 | type Cursor is private; | |
9b832db5 | 54 | pragma Preelaborable_Initialization (Cursor); |
4c2d6a70 AC |
55 | |
56 | Empty_Set : constant Set; | |
57 | ||
58 | No_Element : constant Cursor; | |
59 | ||
60 | function "=" (Left, Right : Set) return Boolean; | |
61 | ||
8704d4b3 MH |
62 | function Equivalent_Sets (Left, Right : Set) return Boolean; |
63 | ||
2368f04e MH |
64 | function To_Set (New_Item : Element_Type) return Set; |
65 | ||
4c2d6a70 AC |
66 | function Length (Container : Set) return Count_Type; |
67 | ||
68 | function Is_Empty (Container : Set) return Boolean; | |
69 | ||
70 | procedure Clear (Container : in out Set); | |
71 | ||
72 | function Element (Position : Cursor) return Element_Type; | |
73 | ||
ba355842 MH |
74 | procedure Replace_Element |
75 | (Container : in out Set; | |
76 | Position : Cursor; | |
77 | New_Item : Element_Type); | |
78 | ||
4c2d6a70 AC |
79 | procedure Query_Element |
80 | (Position : Cursor; | |
81 | Process : not null access procedure (Element : Element_Type)); | |
82 | ||
ba355842 | 83 | procedure Move (Target : in out Set; Source : in out Set); |
4c2d6a70 AC |
84 | |
85 | procedure Insert | |
86 | (Container : in out Set; | |
87 | New_Item : Element_Type; | |
88 | Position : out Cursor; | |
89 | Inserted : out Boolean); | |
90 | ||
91 | procedure Insert | |
92 | (Container : in out Set; | |
93 | New_Item : Element_Type); | |
94 | ||
95 | procedure Include | |
96 | (Container : in out Set; | |
97 | New_Item : Element_Type); | |
98 | ||
99 | procedure Replace | |
ba355842 | 100 | (Container : in out Set; |
4c2d6a70 AC |
101 | New_Item : Element_Type); |
102 | ||
ba355842 MH |
103 | procedure Exclude |
104 | (Container : in out Set; | |
105 | Item : Element_Type); | |
106 | ||
4c2d6a70 AC |
107 | procedure Delete |
108 | (Container : in out Set; | |
109 | Item : Element_Type); | |
110 | ||
4c2d6a70 AC |
111 | procedure Delete |
112 | (Container : in out Set; | |
113 | Position : in out Cursor); | |
114 | ||
115 | procedure Delete_First (Container : in out Set); | |
116 | ||
117 | procedure Delete_Last (Container : in out Set); | |
118 | ||
119 | procedure Union (Target : in out Set; Source : Set); | |
120 | ||
121 | function Union (Left, Right : Set) return Set; | |
122 | ||
123 | function "or" (Left, Right : Set) return Set renames Union; | |
124 | ||
125 | procedure Intersection (Target : in out Set; Source : Set); | |
126 | ||
127 | function Intersection (Left, Right : Set) return Set; | |
128 | ||
129 | function "and" (Left, Right : Set) return Set renames Intersection; | |
130 | ||
ba355842 | 131 | procedure Difference (Target : in out Set; Source : Set); |
4c2d6a70 AC |
132 | |
133 | function Difference (Left, Right : Set) return Set; | |
134 | ||
135 | function "-" (Left, Right : Set) return Set renames Difference; | |
136 | ||
137 | procedure Symmetric_Difference (Target : in out Set; Source : Set); | |
138 | ||
139 | function Symmetric_Difference (Left, Right : Set) return Set; | |
140 | ||
141 | function "xor" (Left, Right : Set) return Set renames Symmetric_Difference; | |
142 | ||
143 | function Overlap (Left, Right : Set) return Boolean; | |
144 | ||
145 | function Is_Subset (Subset : Set; Of_Set : Set) return Boolean; | |
146 | ||
4c2d6a70 AC |
147 | function First (Container : Set) return Cursor; |
148 | ||
149 | function First_Element (Container : Set) return Element_Type; | |
150 | ||
151 | function Last (Container : Set) return Cursor; | |
152 | ||
153 | function Last_Element (Container : Set) return Element_Type; | |
154 | ||
155 | function Next (Position : Cursor) return Cursor; | |
156 | ||
4c2d6a70 AC |
157 | procedure Next (Position : in out Cursor); |
158 | ||
8704d4b3 MH |
159 | function Previous (Position : Cursor) return Cursor; |
160 | ||
4c2d6a70 AC |
161 | procedure Previous (Position : in out Cursor); |
162 | ||
ba355842 MH |
163 | function Find (Container : Set; Item : Element_Type) return Cursor; |
164 | ||
165 | function Floor (Container : Set; Item : Element_Type) return Cursor; | |
166 | ||
167 | function Ceiling (Container : Set; Item : Element_Type) return Cursor; | |
168 | ||
169 | function Contains (Container : Set; Item : Element_Type) return Boolean; | |
170 | ||
4c2d6a70 AC |
171 | function Has_Element (Position : Cursor) return Boolean; |
172 | ||
173 | function "<" (Left, Right : Cursor) return Boolean; | |
174 | ||
175 | function ">" (Left, Right : Cursor) return Boolean; | |
176 | ||
177 | function "<" (Left : Cursor; Right : Element_Type) return Boolean; | |
178 | ||
179 | function ">" (Left : Cursor; Right : Element_Type) return Boolean; | |
180 | ||
181 | function "<" (Left : Element_Type; Right : Cursor) return Boolean; | |
182 | ||
183 | function ">" (Left : Element_Type; Right : Cursor) return Boolean; | |
184 | ||
185 | procedure Iterate | |
186 | (Container : Set; | |
187 | Process : not null access procedure (Position : Cursor)); | |
188 | ||
189 | procedure Reverse_Iterate | |
190 | (Container : Set; | |
191 | Process : not null access procedure (Position : Cursor)); | |
192 | ||
193 | generic | |
ba355842 | 194 | type Key_Type (<>) is private; |
4c2d6a70 AC |
195 | |
196 | with function Key (Element : Element_Type) return Key_Type; | |
197 | ||
ba355842 | 198 | with function "<" (Left, Right : Key_Type) return Boolean is <>; |
4c2d6a70 AC |
199 | |
200 | package Generic_Keys is | |
201 | ||
ba355842 | 202 | function Equivalent_Keys (Left, Right : Key_Type) return Boolean; |
4c2d6a70 AC |
203 | |
204 | function Key (Position : Cursor) return Key_Type; | |
205 | ||
206 | function Element (Container : Set; Key : Key_Type) return Element_Type; | |
207 | ||
8704d4b3 | 208 | procedure Replace |
ba355842 | 209 | (Container : in out Set; |
8704d4b3 MH |
210 | Key : Key_Type; |
211 | New_Item : Element_Type); | |
4c2d6a70 | 212 | |
4c2d6a70 AC |
213 | procedure Exclude (Container : in out Set; Key : Key_Type); |
214 | ||
ba355842 MH |
215 | procedure Delete (Container : in out Set; Key : Key_Type); |
216 | ||
217 | function Find (Container : Set; Key : Key_Type) return Cursor; | |
4c2d6a70 | 218 | |
ba355842 | 219 | function Floor (Container : Set; Key : Key_Type) return Cursor; |
4c2d6a70 | 220 | |
ba355842 | 221 | function Ceiling (Container : Set; Key : Key_Type) return Cursor; |
4c2d6a70 | 222 | |
ba355842 | 223 | function Contains (Container : Set; Key : Key_Type) return Boolean; |
4c2d6a70 | 224 | |
8704d4b3 | 225 | procedure Update_Element_Preserving_Key |
4c2d6a70 AC |
226 | (Container : in out Set; |
227 | Position : Cursor; | |
228 | Process : not null access | |
229 | procedure (Element : in out Element_Type)); | |
230 | ||
231 | end Generic_Keys; | |
232 | ||
233 | private | |
234 | ||
f97ccb3a BD |
235 | pragma Inline (Next); |
236 | pragma Inline (Previous); | |
237 | ||
4c2d6a70 AC |
238 | type Node_Type; |
239 | type Node_Access is access Node_Type; | |
240 | ||
8704d4b3 MH |
241 | type Node_Type is limited record |
242 | Parent : Node_Access; | |
243 | Left : Node_Access; | |
244 | Right : Node_Access; | |
245 | Color : Red_Black_Trees.Color_Type := Red_Black_Trees.Red; | |
246 | Element : Element_Type; | |
247 | end record; | |
4c2d6a70 | 248 | |
3c25856a AC |
249 | package Tree_Types is |
250 | new Red_Black_Trees.Generic_Tree_Types (Node_Type, Node_Access); | |
4c2d6a70 | 251 | |
8704d4b3 MH |
252 | type Set is new Ada.Finalization.Controlled with record |
253 | Tree : Tree_Types.Tree_Type; | |
4c2d6a70 AC |
254 | end record; |
255 | ||
2a6b365a | 256 | overriding |
4c2d6a70 AC |
257 | procedure Adjust (Container : in out Set); |
258 | ||
2a6b365a | 259 | overriding |
4c2d6a70 AC |
260 | procedure Finalize (Container : in out Set) renames Clear; |
261 | ||
8704d4b3 MH |
262 | use Red_Black_Trees; |
263 | use Tree_Types; | |
264 | use Ada.Finalization; | |
2368f04e | 265 | use Ada.Streams; |
8704d4b3 MH |
266 | |
267 | type Set_Access is access all Set; | |
268 | for Set_Access'Storage_Size use 0; | |
4c2d6a70 AC |
269 | |
270 | type Cursor is record | |
271 | Container : Set_Access; | |
272 | Node : Node_Access; | |
273 | end record; | |
274 | ||
2368f04e | 275 | procedure Write |
d90e94c7 | 276 | (Stream : not null access Root_Stream_Type'Class; |
2368f04e | 277 | Item : Cursor); |
4c2d6a70 | 278 | |
2368f04e MH |
279 | for Cursor'Write use Write; |
280 | ||
281 | procedure Read | |
d90e94c7 | 282 | (Stream : not null access Root_Stream_Type'Class; |
2368f04e MH |
283 | Item : out Cursor); |
284 | ||
285 | for Cursor'Read use Read; | |
286 | ||
287 | No_Element : constant Cursor := Cursor'(null, null); | |
4c2d6a70 AC |
288 | |
289 | procedure Write | |
d90e94c7 | 290 | (Stream : not null access Root_Stream_Type'Class; |
4c2d6a70 AC |
291 | Container : Set); |
292 | ||
293 | for Set'Write use Write; | |
294 | ||
295 | procedure Read | |
d90e94c7 | 296 | (Stream : not null access Root_Stream_Type'Class; |
4c2d6a70 AC |
297 | Container : out Set); |
298 | ||
299 | for Set'Read use Read; | |
300 | ||
301 | Empty_Set : constant Set := | |
8704d4b3 MH |
302 | (Controlled with Tree => (First => null, |
303 | Last => null, | |
304 | Root => null, | |
305 | Length => 0, | |
306 | Busy => 0, | |
307 | Lock => 0)); | |
4c2d6a70 AC |
308 | |
309 | end Ada.Containers.Ordered_Sets; |