]>
Commit | Line | Data |
---|---|---|
4c2d6a70 AC |
1 | ------------------------------------------------------------------------------ |
2 | -- -- | |
3 | -- GNAT LIBRARY COMPONENTS -- | |
4 | -- -- | |
2a6b365a | 5 | -- ADA.CONTAINERS.INDEFINITE_HASHED_SETS -- |
4c2d6a70 AC |
6 | -- -- |
7 | -- S p e c -- | |
8 | -- -- | |
4b490c1e | 9 | -- Copyright (C) 2004-2020, 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 | ||
ffb35bbf | 34 | with Ada.Iterator_Interfaces; |
3c24c853 | 35 | |
2a6b365a | 36 | private with Ada.Containers.Hash_Tables; |
1f8f3e6e | 37 | with Ada.Containers.Helpers; |
2a6b365a MH |
38 | private with Ada.Streams; |
39 | private with Ada.Finalization; | |
4c2d6a70 AC |
40 | |
41 | generic | |
42 | type Element_Type (<>) is private; | |
43 | ||
44 | with function Hash (Element : Element_Type) return Hash_Type; | |
45 | ||
8d3ed5b8 AC |
46 | with function Equivalent_Elements (Left, Right : Element_Type) |
47 | return Boolean; | |
4c2d6a70 AC |
48 | |
49 | with function "=" (Left, Right : Element_Type) return Boolean is <>; | |
50 | ||
51 | package Ada.Containers.Indefinite_Hashed_Sets is | |
6031f544 | 52 | pragma Annotate (CodePeer, Skip_Analysis); |
ba355842 | 53 | pragma Preelaborate; |
f97ccb3a | 54 | pragma Remote_Types; |
4c2d6a70 | 55 | |
ffb35bbf ES |
56 | type Set is tagged private |
57 | with Constant_Indexing => Constant_Reference, | |
58 | Default_Iterator => Iterate, | |
59 | Iterator_Element => Element_Type; | |
60 | ||
9b832db5 | 61 | pragma Preelaborable_Initialization (Set); |
4c2d6a70 AC |
62 | |
63 | type Cursor is private; | |
9b832db5 | 64 | pragma Preelaborable_Initialization (Cursor); |
4c2d6a70 AC |
65 | |
66 | Empty_Set : constant Set; | |
8236f027 MH |
67 | -- Set objects declared without an initialization expression are |
68 | -- initialized to the value Empty_Set. | |
4c2d6a70 AC |
69 | |
70 | No_Element : constant Cursor; | |
8236f027 MH |
71 | -- Cursor objects declared without an initialization expression are |
72 | -- initialized to the value No_Element. | |
4c2d6a70 | 73 | |
ffb35bbf ES |
74 | function Has_Element (Position : Cursor) return Boolean; |
75 | -- Equivalent to Position /= No_Element | |
76 | ||
77 | package Set_Iterator_Interfaces is new | |
78 | Ada.Iterator_Interfaces (Cursor, Has_Element); | |
79 | ||
4c2d6a70 | 80 | function "=" (Left, Right : Set) return Boolean; |
8236f027 MH |
81 | -- For each element in Left, set equality attempts to find the equal |
82 | -- element in Right; if a search fails, then set equality immediately | |
83 | -- returns False. The search works by calling Hash to find the bucket in | |
84 | -- the Right set that corresponds to the Left element. If the bucket is | |
85 | -- non-empty, the search calls the generic formal element equality operator | |
86 | -- to compare the element (in Left) to the element of each node in the | |
87 | -- bucket (in Right); the search terminates when a matching node in the | |
88 | -- bucket is found, or the nodes in the bucket are exhausted. (Note that | |
89 | -- element equality is called here, not Equivalent_Elements. Set equality | |
90 | -- is the only operation in which element equality is used. Compare set | |
91 | -- equality to Equivalent_Sets, which does call Equivalent_Elements.) | |
4c2d6a70 | 92 | |
8d3ed5b8 | 93 | function Equivalent_Sets (Left, Right : Set) return Boolean; |
8236f027 MH |
94 | -- Similar to set equality, with the difference that the element in Left is |
95 | -- compared to the elements in Right using the generic formal | |
96 | -- Equivalent_Elements operation instead of element equality. | |
8d3ed5b8 | 97 | |
2368f04e | 98 | function To_Set (New_Item : Element_Type) return Set; |
8236f027 MH |
99 | -- Constructs a singleton set comprising New_Element. To_Set calls Hash to |
100 | -- determine the bucket for New_Item. | |
2368f04e | 101 | |
ba355842 | 102 | function Capacity (Container : Set) return Count_Type; |
8236f027 MH |
103 | -- Returns the current capacity of the set. Capacity is the maximum length |
104 | -- before which rehashing in guaranteed not to occur. | |
105 | ||
106 | procedure Reserve_Capacity (Container : in out Set; Capacity : Count_Type); | |
107 | -- Adjusts the current capacity, by allocating a new buckets array. If the | |
108 | -- requested capacity is less than the current capacity, then the capacity | |
109 | -- is contracted (to a value not less than the current length). If the | |
110 | -- requested capacity is greater than the current capacity, then the | |
111 | -- capacity is expanded (to a value not less than what is requested). In | |
112 | -- either case, the nodes are rehashed from the old buckets array onto the | |
113 | -- new buckets array (Hash is called once for each existing element in | |
114 | -- order to compute the new index), and then the old buckets array is | |
115 | -- deallocated. | |
ba355842 | 116 | |
4c2d6a70 | 117 | function Length (Container : Set) return Count_Type; |
8236f027 | 118 | -- Returns the number of items in the set |
4c2d6a70 AC |
119 | |
120 | function Is_Empty (Container : Set) return Boolean; | |
8236f027 | 121 | -- Equivalent to Length (Container) = 0 |
4c2d6a70 AC |
122 | |
123 | procedure Clear (Container : in out Set); | |
8236f027 | 124 | -- Removes all of the items from the set |
4c2d6a70 AC |
125 | |
126 | function Element (Position : Cursor) return Element_Type; | |
8236f027 | 127 | -- Returns the element of the node designated by the cursor |
4c2d6a70 | 128 | |
ba355842 MH |
129 | procedure Replace_Element |
130 | (Container : in out Set; | |
131 | Position : Cursor; | |
132 | New_Item : Element_Type); | |
8236f027 MH |
133 | -- If New_Item is equivalent (as determined by calling Equivalent_Elements) |
134 | -- to the element of the node designated by Position, then New_Element is | |
135 | -- assigned to that element. Otherwise, it calls Hash to determine the | |
136 | -- bucket for New_Item. If the bucket is not empty, then it calls | |
137 | -- Equivalent_Elements for each node in that bucket to determine whether | |
138 | -- New_Item is equivalent to an element in that bucket. If | |
139 | -- Equivalent_Elements returns True then Program_Error is raised (because | |
140 | -- an element may appear only once in the set); otherwise, New_Item is | |
141 | -- assigned to the node designated by Position, and the node is moved to | |
142 | -- its new bucket. | |
ba355842 | 143 | |
4c2d6a70 AC |
144 | procedure Query_Element |
145 | (Position : Cursor; | |
146 | Process : not null access procedure (Element : Element_Type)); | |
8236f027 | 147 | -- Calls Process with the element (having only a constant view) of the node |
ffb35bbf ES |
148 | -- designated by the cursor. |
149 | ||
150 | type Constant_Reference_Type | |
151 | (Element : not null access constant Element_Type) is private | |
152 | with Implicit_Dereference => Element; | |
153 | ||
154 | function Constant_Reference | |
155 | (Container : aliased Set; | |
c9423ca3 | 156 | Position : Cursor) return Constant_Reference_Type; |
794b9b72 | 157 | pragma Inline (Constant_Reference); |
4c2d6a70 | 158 | |
a31945d7 AC |
159 | procedure Assign (Target : in out Set; Source : Set); |
160 | ||
161 | function Copy (Source : Set; Capacity : Count_Type := 0) return Set; | |
162 | ||
8236f027 MH |
163 | procedure Move (Target : in out Set; Source : in out Set); |
164 | -- Clears Target (if it's not empty), and then moves (not copies) the | |
165 | -- buckets array and nodes from Source to Target. | |
4c2d6a70 AC |
166 | |
167 | procedure Insert | |
168 | (Container : in out Set; | |
169 | New_Item : Element_Type; | |
170 | Position : out Cursor; | |
171 | Inserted : out Boolean); | |
8236f027 MH |
172 | -- Conditionally inserts New_Item into the set. If New_Item is already in |
173 | -- the set, then Inserted returns False and Position designates the node | |
174 | -- containing the existing element (which is not modified). If New_Item is | |
175 | -- not already in the set, then Inserted returns True and Position | |
176 | -- designates the newly-inserted node containing New_Item. The search for | |
177 | -- an existing element works as follows. Hash is called to determine | |
178 | -- New_Item's bucket; if the bucket is non-empty, then Equivalent_Elements | |
179 | -- is called to compare New_Item to the element of each node in that | |
180 | -- bucket. If the bucket is empty, or there were no equivalent elements in | |
181 | -- the bucket, the search "fails" and the New_Item is inserted in the set | |
182 | -- (and Inserted returns True); otherwise, the search "succeeds" (and | |
183 | -- Inserted returns False). | |
4c2d6a70 AC |
184 | |
185 | procedure Insert (Container : in out Set; New_Item : Element_Type); | |
8236f027 MH |
186 | -- Attempts to insert New_Item into the set, performing the usual insertion |
187 | -- search (which involves calling both Hash and Equivalent_Elements); if | |
188 | -- the search succeeds (New_Item is equivalent to an element already in the | |
189 | -- set, and so was not inserted), then this operation raises | |
190 | -- Constraint_Error. (This version of Insert is similar to Replace, but | |
191 | -- having the opposite exception behavior. It is intended for use when you | |
192 | -- want to assert that the item is not already in the set.) | |
4c2d6a70 AC |
193 | |
194 | procedure Include (Container : in out Set; New_Item : Element_Type); | |
8236f027 MH |
195 | -- Attempts to insert New_Item into the set. If an element equivalent to |
196 | -- New_Item is already in the set (the insertion search succeeded, and | |
197 | -- hence New_Item was not inserted), then the value of New_Item is assigned | |
198 | -- to the existing element. (This insertion operation only raises an | |
199 | -- exception if cursor tampering occurs. It is intended for use when you | |
200 | -- want to insert the item in the set, and you don't care whether an | |
201 | -- equivalent element is already present.) | |
4c2d6a70 AC |
202 | |
203 | procedure Replace (Container : in out Set; New_Item : Element_Type); | |
8236f027 MH |
204 | -- Searches for New_Item in the set; if the search fails (because an |
205 | -- equivalent element was not in the set), then it raises | |
206 | -- Constraint_Error. Otherwise, the existing element is assigned the value | |
207 | -- New_Item. (This is similar to Insert, but with the opposite exception | |
208 | -- behavior. It is intended for use when you want to assert that the item | |
209 | -- is already in the set.) | |
4c2d6a70 | 210 | |
4c2d6a70 | 211 | procedure Exclude (Container : in out Set; Item : Element_Type); |
8236f027 MH |
212 | -- Searches for Item in the set, and if found, removes its node from the |
213 | -- set and then deallocates it. The search works as follows. The operation | |
214 | -- calls Hash to determine the item's bucket; if the bucket is not empty, | |
215 | -- it calls Equivalent_Elements to compare Item to the element of each node | |
216 | -- in the bucket. (This is the deletion analog of Include. It is intended | |
217 | -- for use when you want to remove the item from the set, but don't care | |
218 | -- whether the item is already in the set.) | |
4c2d6a70 | 219 | |
ba355842 | 220 | procedure Delete (Container : in out Set; Item : Element_Type); |
8236f027 MH |
221 | -- Searches for Item in the set (which involves calling both Hash and |
222 | -- Equivalent_Elements). If the search fails, then the operation raises | |
223 | -- Constraint_Error. Otherwise it removes the node from the set and then | |
224 | -- deallocates it. (This is the deletion analog of non-conditional | |
225 | -- Insert. It is intended for use when you want to assert that the item is | |
226 | -- already in the set.) | |
8d3ed5b8 | 227 | |
ba355842 | 228 | procedure Delete (Container : in out Set; Position : in out Cursor); |
8236f027 MH |
229 | -- Removes the node designated by Position from the set, and then |
230 | -- deallocates the node. The operation calls Hash to determine the bucket, | |
231 | -- and then compares Position to each node in the bucket until there's a | |
232 | -- match (it does not call Equivalent_Elements). | |
4c2d6a70 AC |
233 | |
234 | procedure Union (Target : in out Set; Source : Set); | |
8236f027 MH |
235 | -- The operation first calls Reserve_Capacity if the current capacity is |
236 | -- less than the sum of the lengths of Source and Target. It then iterates | |
237 | -- over the Source set, and conditionally inserts each element into Target. | |
4c2d6a70 AC |
238 | |
239 | function Union (Left, Right : Set) return Set; | |
8236f027 MH |
240 | -- The operation first copies the Left set to the result, and then iterates |
241 | -- over the Right set to conditionally insert each element into the result. | |
4c2d6a70 AC |
242 | |
243 | function "or" (Left, Right : Set) return Set renames Union; | |
244 | ||
245 | procedure Intersection (Target : in out Set; Source : Set); | |
8236f027 MH |
246 | -- Iterates over the Target set (calling First and Next), calling Find to |
247 | -- determine whether the element is in Source. If an equivalent element is | |
248 | -- not found in Source, the element is deleted from Target. | |
4c2d6a70 AC |
249 | |
250 | function Intersection (Left, Right : Set) return Set; | |
8236f027 MH |
251 | -- Iterates over the Left set, calling Find to determine whether the |
252 | -- element is in Right. If an equivalent element is found, it is inserted | |
253 | -- into the result set. | |
4c2d6a70 AC |
254 | |
255 | function "and" (Left, Right : Set) return Set renames Intersection; | |
256 | ||
257 | procedure Difference (Target : in out Set; Source : Set); | |
8236f027 MH |
258 | -- Iterates over the Source (calling First and Next), calling Find to |
259 | -- determine whether the element is in Target. If an equivalent element is | |
260 | -- found, it is deleted from Target. | |
4c2d6a70 AC |
261 | |
262 | function Difference (Left, Right : Set) return Set; | |
8236f027 MH |
263 | -- Iterates over the Left set, calling Find to determine whether the |
264 | -- element is in the Right set. If an equivalent element is not found, the | |
265 | -- element is inserted into the result set. | |
4c2d6a70 AC |
266 | |
267 | function "-" (Left, Right : Set) return Set renames Difference; | |
268 | ||
269 | procedure Symmetric_Difference (Target : in out Set; Source : Set); | |
8236f027 MH |
270 | -- The operation first calls Reserve_Capacity if the current capacity is |
271 | -- less than the sum of the lengths of Source and Target. It then iterates | |
272 | -- over the Source set, searching for the element in Target (calling Hash | |
273 | -- and Equivalent_Elements). If an equivalent element is found, it is | |
274 | -- removed from Target; otherwise it is inserted into Target. | |
4c2d6a70 AC |
275 | |
276 | function Symmetric_Difference (Left, Right : Set) return Set; | |
8236f027 MH |
277 | -- The operation first iterates over the Left set. It calls Find to |
278 | -- determine whether the element is in the Right set. If no equivalent | |
279 | -- element is found, the element from Left is inserted into the result. The | |
280 | -- operation then iterates over the Right set, to determine whether the | |
281 | -- element is in the Left set. If no equivalent element is found, the Right | |
282 | -- element is inserted into the result. | |
4c2d6a70 AC |
283 | |
284 | function "xor" (Left, Right : Set) return Set | |
285 | renames Symmetric_Difference; | |
286 | ||
4c2d6a70 | 287 | function Overlap (Left, Right : Set) return Boolean; |
8236f027 MH |
288 | -- Iterates over the Left set (calling First and Next), calling Find to |
289 | -- determine whether the element is in the Right set. If an equivalent | |
290 | -- element is found, the operation immediately returns True. The operation | |
291 | -- returns False if the iteration over Left terminates without finding any | |
292 | -- equivalent element in Right. | |
4c2d6a70 | 293 | |
8d3ed5b8 | 294 | function Is_Subset (Subset : Set; Of_Set : Set) return Boolean; |
8236f027 MH |
295 | -- Iterates over Subset (calling First and Next), calling Find to determine |
296 | -- whether the element is in Of_Set. If no equivalent element is found in | |
297 | -- Of_Set, the operation immediately returns False. The operation returns | |
298 | -- True if the iteration over Subset terminates without finding an element | |
299 | -- not in Of_Set (that is, every element in Subset is equivalent to an | |
300 | -- element in Of_Set). | |
4c2d6a70 | 301 | |
ba355842 | 302 | function First (Container : Set) return Cursor; |
8236f027 MH |
303 | -- Returns a cursor that designates the first non-empty bucket, by |
304 | -- searching from the beginning of the buckets array. | |
4c2d6a70 | 305 | |
ba355842 | 306 | function Next (Position : Cursor) return Cursor; |
8236f027 MH |
307 | -- Returns a cursor that designates the node that follows the current one |
308 | -- designated by Position. If Position designates the last node in its | |
309 | -- bucket, the operation calls Hash to compute the index of this bucket, | |
310 | -- and searches the buckets array for the first non-empty bucket, starting | |
311 | -- from that index; otherwise, it simply follows the link to the next node | |
312 | -- in the same bucket. | |
ba355842 MH |
313 | |
314 | procedure Next (Position : in out Cursor); | |
8236f027 | 315 | -- Equivalent to Position := Next (Position) |
ba355842 MH |
316 | |
317 | function Find (Container : Set; Item : Element_Type) return Cursor; | |
8236f027 MH |
318 | -- Searches for Item in the set. Find calls Hash to determine the item's |
319 | -- bucket; if the bucket is not empty, it calls Equivalent_Elements to | |
320 | -- compare Item to each element in the bucket. If the search succeeds, Find | |
321 | -- returns a cursor designating the node containing the equivalent element; | |
322 | -- otherwise, it returns No_Element. | |
ba355842 MH |
323 | |
324 | function Contains (Container : Set; Item : Element_Type) return Boolean; | |
8236f027 | 325 | -- Equivalent to Find (Container, Item) /= No_Element |
ba355842 | 326 | |
ba355842 | 327 | function Equivalent_Elements (Left, Right : Cursor) return Boolean; |
8236f027 MH |
328 | -- Returns the result of calling Equivalent_Elements with the elements of |
329 | -- the nodes designated by cursors Left and Right. | |
ba355842 MH |
330 | |
331 | function Equivalent_Elements | |
332 | (Left : Cursor; | |
333 | Right : Element_Type) return Boolean; | |
8236f027 MH |
334 | -- Returns the result of calling Equivalent_Elements with element of the |
335 | -- node designated by Left and element Right. | |
ba355842 MH |
336 | |
337 | function Equivalent_Elements | |
338 | (Left : Element_Type; | |
339 | Right : Cursor) return Boolean; | |
8236f027 MH |
340 | -- Returns the result of calling Equivalent_Elements with element Left and |
341 | -- the element of the node designated by Right. | |
ba355842 MH |
342 | |
343 | procedure Iterate | |
344 | (Container : Set; | |
345 | Process : not null access procedure (Position : Cursor)); | |
8236f027 | 346 | -- Calls Process for each node in the set |
4c2d6a70 | 347 | |
ffb35bbf ES |
348 | function Iterate (Container : Set) |
349 | return Set_Iterator_Interfaces.Forward_Iterator'Class; | |
350 | ||
4c2d6a70 | 351 | generic |
ba355842 | 352 | type Key_Type (<>) is private; |
4c2d6a70 AC |
353 | |
354 | with function Key (Element : Element_Type) return Key_Type; | |
355 | ||
356 | with function Hash (Key : Key_Type) return Hash_Type; | |
357 | ||
ba355842 | 358 | with function Equivalent_Keys (Left, Right : Key_Type) return Boolean; |
4c2d6a70 AC |
359 | |
360 | package Generic_Keys is | |
361 | ||
4c2d6a70 | 362 | function Key (Position : Cursor) return Key_Type; |
8236f027 MH |
363 | -- Applies generic formal operation Key to the element of the node |
364 | -- designated by Position. | |
4c2d6a70 AC |
365 | |
366 | function Element (Container : Set; Key : Key_Type) return Element_Type; | |
8236f027 MH |
367 | -- Searches (as per the key-based Find) for the node containing Key, and |
368 | -- returns the associated element. | |
4c2d6a70 | 369 | |
ffabcde5 | 370 | procedure Replace |
8d3ed5b8 AC |
371 | (Container : in out Set; |
372 | Key : Key_Type; | |
373 | New_Item : Element_Type); | |
8236f027 MH |
374 | -- Searches (as per the key-based Find) for the node containing Key, and |
375 | -- then replaces the element of that node (as per the element-based | |
376 | -- Replace_Element). | |
4c2d6a70 | 377 | |
ba355842 | 378 | procedure Exclude (Container : in out Set; Key : Key_Type); |
8236f027 MH |
379 | -- Searches for Key in the set, and if found, removes its node from the |
380 | -- set and then deallocates it. The search works by first calling Hash | |
381 | -- (on Key) to determine the bucket; if the bucket is not empty, it | |
382 | -- calls Equivalent_Keys to compare parameter Key to the value of | |
383 | -- generic formal operation Key applied to element of each node in the | |
384 | -- bucket. | |
ba355842 | 385 | |
4c2d6a70 | 386 | procedure Delete (Container : in out Set; Key : Key_Type); |
8236f027 MH |
387 | -- Deletes the node containing Key as per Exclude, with the difference |
388 | -- that Constraint_Error is raised if Key is not found. | |
4c2d6a70 | 389 | |
ba355842 | 390 | function Find (Container : Set; Key : Key_Type) return Cursor; |
8236f027 MH |
391 | -- Searches for the node containing Key, and returns a cursor |
392 | -- designating the node. The search works by first calling Hash (on Key) | |
393 | -- to determine the bucket. If the bucket is not empty, the search | |
394 | -- compares Key to the element of each node in the bucket, and returns | |
395 | -- the matching node. The comparison itself works by applying the | |
396 | -- generic formal Key operation to the element of the node, and then | |
397 | -- calling generic formal operation Equivalent_Keys. | |
ba355842 MH |
398 | |
399 | function Contains (Container : Set; Key : Key_Type) return Boolean; | |
8236f027 | 400 | -- Equivalent to Find (Container, Key) /= No_Element |
4c2d6a70 | 401 | |
8d3ed5b8 | 402 | procedure Update_Element_Preserving_Key |
4c2d6a70 AC |
403 | (Container : in out Set; |
404 | Position : Cursor; | |
405 | Process : not null access | |
406 | procedure (Element : in out Element_Type)); | |
8236f027 MH |
407 | -- Calls Process with the element of the node designated by Position, |
408 | -- but with the restriction that the key-value of the element is not | |
409 | -- modified. The operation first makes a copy of the value returned by | |
410 | -- applying generic formal operation Key on the element of the node, and | |
411 | -- then calls Process with the element. The operation verifies that the | |
412 | -- key-part has not been modified by calling generic formal operation | |
413 | -- Equivalent_Keys to compare the saved key-value to the value returned | |
414 | -- by applying generic formal operation Key to the post-Process value of | |
415 | -- element. If the key values compare equal then the operation | |
416 | -- completes. Otherwise, the node is removed from the map and | |
417 | -- Program_Error is raised. | |
4c2d6a70 | 418 | |
ffb35bbf ES |
419 | type Reference_Type (Element : not null access Element_Type) is private |
420 | with Implicit_Dereference => Element; | |
421 | ||
422 | function Reference_Preserving_Key | |
423 | (Container : aliased in out Set; | |
ce72a9a3 | 424 | Position : Cursor) return Reference_Type; |
ffb35bbf | 425 | |
c9423ca3 AC |
426 | function Constant_Reference |
427 | (Container : aliased Set; | |
428 | Key : Key_Type) return Constant_Reference_Type; | |
429 | ||
ffb35bbf ES |
430 | function Reference_Preserving_Key |
431 | (Container : aliased in out Set; | |
ce72a9a3 | 432 | Key : Key_Type) return Reference_Type; |
ffb35bbf ES |
433 | |
434 | private | |
6b6bce61 AC |
435 | type Set_Access is access all Set; |
436 | for Set_Access'Storage_Size use 0; | |
437 | ||
14f73211 BD |
438 | package Impl is new Helpers.Generic_Implementation; |
439 | ||
6b6bce61 | 440 | type Reference_Control_Type is |
14f73211 | 441 | new Impl.Reference_Control_Type with |
6b6bce61 AC |
442 | record |
443 | Container : Set_Access; | |
444 | Index : Hash_Type; | |
445 | Old_Pos : Cursor; | |
446 | Old_Hash : Hash_Type; | |
447 | end record; | |
448 | ||
d6e8719d | 449 | overriding procedure Finalize (Control : in out Reference_Control_Type); |
6b6bce61 AC |
450 | pragma Inline (Finalize); |
451 | ||
452 | type Reference_Type (Element : not null access Element_Type) is record | |
db222ead AC |
453 | Control : Reference_Control_Type := |
454 | raise Program_Error with "uninitialized reference"; | |
455 | -- The RM says, "The default initialization of an object of | |
456 | -- type Constant_Reference_Type or Reference_Type propagates | |
457 | -- Program_Error." | |
6b6bce61 | 458 | end record; |
c9423ca3 AC |
459 | |
460 | use Ada.Streams; | |
461 | ||
462 | procedure Read | |
463 | (Stream : not null access Root_Stream_Type'Class; | |
464 | Item : out Reference_Type); | |
465 | ||
466 | for Reference_Type'Read use Read; | |
467 | ||
468 | procedure Write | |
469 | (Stream : not null access Root_Stream_Type'Class; | |
470 | Item : Reference_Type); | |
471 | ||
472 | for Reference_Type'Write use Write; | |
4c2d6a70 AC |
473 | end Generic_Keys; |
474 | ||
475 | private | |
f97ccb3a BD |
476 | pragma Inline (Next); |
477 | ||
4c2d6a70 AC |
478 | type Node_Type; |
479 | type Node_Access is access Node_Type; | |
480 | ||
14f73211 | 481 | type Element_Access is access all Element_Type; |
4c2d6a70 | 482 | |
3c25856a AC |
483 | type Node_Type is limited record |
484 | Element : Element_Access; | |
485 | Next : Node_Access; | |
486 | end record; | |
8d3ed5b8 | 487 | |
3c25856a AC |
488 | package HT_Types is |
489 | new Hash_Tables.Generic_Hash_Table_Types (Node_Type, Node_Access); | |
4c2d6a70 | 490 | |
8d3ed5b8 AC |
491 | type Set is new Ada.Finalization.Controlled with record |
492 | HT : HT_Types.Hash_Table_Type; | |
493 | end record; | |
4c2d6a70 | 494 | |
607d0635 | 495 | overriding procedure Adjust (Container : in out Set); |
4c2d6a70 | 496 | |
607d0635 | 497 | overriding procedure Finalize (Container : in out Set); |
4c2d6a70 | 498 | |
14f73211 | 499 | use HT_Types, HT_Types.Implementation; |
8d3ed5b8 | 500 | use Ada.Finalization; |
2368f04e | 501 | use Ada.Streams; |
8d3ed5b8 | 502 | |
3c24c853 MH |
503 | procedure Write |
504 | (Stream : not null access Root_Stream_Type'Class; | |
505 | Container : Set); | |
506 | ||
507 | for Set'Write use Write; | |
508 | ||
509 | procedure Read | |
510 | (Stream : not null access Root_Stream_Type'Class; | |
511 | Container : out Set); | |
512 | ||
513 | for Set'Read use Read; | |
514 | ||
8d3ed5b8 | 515 | type Set_Access is access all Set; |
4c2d6a70 AC |
516 | for Set_Access'Storage_Size use 0; |
517 | ||
3c25856a AC |
518 | type Cursor is record |
519 | Container : Set_Access; | |
520 | Node : Node_Access; | |
521 | end record; | |
4c2d6a70 | 522 | |
2368f04e | 523 | procedure Write |
d90e94c7 | 524 | (Stream : not null access Root_Stream_Type'Class; |
2368f04e MH |
525 | Item : Cursor); |
526 | ||
527 | for Cursor'Write use Write; | |
528 | ||
529 | procedure Read | |
d90e94c7 | 530 | (Stream : not null access Root_Stream_Type'Class; |
2368f04e MH |
531 | Item : out Cursor); |
532 | ||
533 | for Cursor'Read use Read; | |
534 | ||
14f73211 BD |
535 | subtype Reference_Control_Type is Implementation.Reference_Control_Type; |
536 | -- It is necessary to rename this here, so that the compiler can find it | |
794b9b72 | 537 | |
ffb35bbf | 538 | type Constant_Reference_Type |
794b9b72 AC |
539 | (Element : not null access constant Element_Type) is |
540 | record | |
db222ead AC |
541 | Control : Reference_Control_Type := |
542 | raise Program_Error with "uninitialized reference"; | |
543 | -- The RM says, "The default initialization of an object of | |
544 | -- type Constant_Reference_Type or Reference_Type propagates | |
545 | -- Program_Error." | |
794b9b72 | 546 | end record; |
ffb35bbf ES |
547 | |
548 | procedure Read | |
549 | (Stream : not null access Root_Stream_Type'Class; | |
550 | Item : out Constant_Reference_Type); | |
551 | ||
552 | for Constant_Reference_Type'Read use Read; | |
553 | ||
554 | procedure Write | |
555 | (Stream : not null access Root_Stream_Type'Class; | |
556 | Item : Constant_Reference_Type); | |
557 | ||
558 | for Constant_Reference_Type'Write use Write; | |
559 | ||
14f73211 BD |
560 | -- Three operations are used to optimize in the expansion of "for ... of" |
561 | -- loops: the Next(Cursor) procedure in the visible part, and the following | |
562 | -- Pseudo_Reference and Get_Element_Access functions. See Sem_Ch5 for | |
563 | -- details. | |
564 | ||
565 | function Pseudo_Reference | |
566 | (Container : aliased Set'Class) return Reference_Control_Type; | |
567 | pragma Inline (Pseudo_Reference); | |
568 | -- Creates an object of type Reference_Control_Type pointing to the | |
569 | -- container, and increments the Lock. Finalization of this object will | |
570 | -- decrement the Lock. | |
571 | ||
572 | function Get_Element_Access | |
573 | (Position : Cursor) return not null Element_Access; | |
574 | -- Returns a pointer to the element designated by Position. | |
575 | ||
576 | Empty_Set : constant Set := (Controlled with others => <>); | |
4c2d6a70 | 577 | |
3c24c853 MH |
578 | No_Element : constant Cursor := (Container => null, Node => null); |
579 | ||
e2441021 AC |
580 | type Iterator is new Limited_Controlled and |
581 | Set_Iterator_Interfaces.Forward_Iterator with | |
582 | record | |
583 | Container : Set_Access; | |
14f73211 BD |
584 | end record |
585 | with Disable_Controlled => not T_Check; | |
e2441021 AC |
586 | |
587 | overriding procedure Finalize (Object : in out Iterator); | |
588 | ||
589 | overriding function First (Object : Iterator) return Cursor; | |
590 | ||
591 | overriding function Next | |
592 | (Object : Iterator; | |
593 | Position : Cursor) return Cursor; | |
594 | ||
4c2d6a70 | 595 | end Ada.Containers.Indefinite_Hashed_Sets; |