]>
Commit | Line | Data |
---|---|---|
f2acf80c AC |
1 | ------------------------------------------------------------------------------ |
2 | -- -- | |
3 | -- GNAT LIBRARY COMPONENTS -- | |
4 | -- -- | |
5 | -- A D A . C O N T A I N E R S . B O U N D E D _ H A S H E D _ S E T S -- | |
6 | -- -- | |
7 | -- S p e c -- | |
8 | -- -- | |
c54796e0 | 9 | -- Copyright (C) 2004-2011, Free Software Foundation, Inc. -- |
f2acf80c 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- -- | |
17 | -- ware Foundation; either version 3, or (at your option) any later ver- -- | |
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 -- | |
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/>. -- | |
30 | -- -- | |
31 | -- This unit was originally developed by Matthew J Heaney. -- | |
32 | ------------------------------------------------------------------------------ | |
33 | ||
34 | private with Ada.Containers.Hash_Tables; | |
35 | private with Ada.Streams; | |
36 | ||
37 | generic | |
38 | type Element_Type is private; | |
39 | ||
40 | with function Hash (Element : Element_Type) return Hash_Type; | |
41 | ||
42 | with function Equivalent_Elements | |
43 | (Left, Right : Element_Type) return Boolean; | |
44 | ||
45 | with function "=" (Left, Right : Element_Type) return Boolean is <>; | |
46 | ||
47 | package Ada.Containers.Bounded_Hashed_Sets is | |
48 | pragma Pure; | |
49 | pragma Remote_Types; | |
50 | ||
51 | type Set (Capacity : Count_Type; Modulus : Hash_Type) is tagged private; | |
52 | pragma Preelaborable_Initialization (Set); | |
53 | ||
54 | type Cursor is private; | |
55 | pragma Preelaborable_Initialization (Cursor); | |
56 | ||
57 | Empty_Set : constant Set; | |
58 | -- Set objects declared without an initialization expression are | |
59 | -- initialized to the value Empty_Set. | |
60 | ||
61 | No_Element : constant Cursor; | |
62 | -- Cursor objects declared without an initialization expression are | |
63 | -- initialized to the value No_Element. | |
64 | ||
65 | function "=" (Left, Right : Set) return Boolean; | |
66 | -- For each element in Left, set equality attempts to find the equal | |
67 | -- element in Right; if a search fails, then set equality immediately | |
68 | -- returns False. The search works by calling Hash to find the bucket in | |
69 | -- the Right set that corresponds to the Left element. If the bucket is | |
70 | -- non-empty, the search calls the generic formal element equality operator | |
71 | -- to compare the element (in Left) to the element of each node in the | |
72 | -- bucket (in Right); the search terminates when a matching node in the | |
73 | -- bucket is found, or the nodes in the bucket are exhausted. (Note that | |
74 | -- element equality is called here, not Equivalent_Elements. Set equality | |
75 | -- is the only operation in which element equality is used. Compare set | |
76 | -- equality to Equivalent_Sets, which does call Equivalent_Elements.) | |
77 | ||
78 | function Equivalent_Sets (Left, Right : Set) return Boolean; | |
79 | -- Similar to set equality, with the difference that the element in Left is | |
80 | -- compared to the elements in Right using the generic formal | |
81 | -- Equivalent_Elements operation instead of element equality. | |
82 | ||
83 | function To_Set (New_Item : Element_Type) return Set; | |
84 | -- Constructs a singleton set comprising New_Element. To_Set calls Hash to | |
85 | -- determine the bucket for New_Item. | |
86 | ||
87 | function Capacity (Container : Set) return Count_Type; | |
88 | -- Returns the current capacity of the set. Capacity is the maximum length | |
89 | -- before which rehashing in guaranteed not to occur. | |
90 | ||
91 | procedure Reserve_Capacity (Container : in out Set; Capacity : Count_Type); | |
92 | -- If the value of the Capacity actual parameter is less or equal to | |
93 | -- Container.Capacity, then the operation has no effect. Otherwise it | |
94 | -- raises Capacity_Error (as no expansion of capacity is possible for a | |
95 | -- bounded form). | |
96 | ||
97 | function Default_Modulus (Capacity : Count_Type) return Hash_Type; | |
98 | -- Returns a modulus value (hash table size) which is optimal for the | |
99 | -- specified capacity (which corresponds to the maximum number of items). | |
100 | ||
101 | function Length (Container : Set) return Count_Type; | |
102 | -- Returns the number of items in the set | |
103 | ||
104 | function Is_Empty (Container : Set) return Boolean; | |
105 | -- Equivalent to Length (Container) = 0 | |
106 | ||
107 | procedure Clear (Container : in out Set); | |
108 | -- Removes all of the items from the set | |
109 | ||
110 | function Element (Position : Cursor) return Element_Type; | |
111 | -- Returns the element of the node designated by the cursor | |
112 | ||
113 | procedure Replace_Element | |
114 | (Container : in out Set; | |
115 | Position : Cursor; | |
116 | New_Item : Element_Type); | |
117 | -- If New_Item is equivalent (as determined by calling Equivalent_Elements) | |
118 | -- to the element of the node designated by Position, then New_Element is | |
119 | -- assigned to that element. Otherwise, it calls Hash to determine the | |
120 | -- bucket for New_Item. If the bucket is not empty, then it calls | |
121 | -- Equivalent_Elements for each node in that bucket to determine whether | |
122 | -- New_Item is equivalent to an element in that bucket. If | |
123 | -- Equivalent_Elements returns True then Program_Error is raised (because | |
124 | -- an element may appear only once in the set); otherwise, New_Item is | |
125 | -- assigned to the node designated by Position, and the node is moved to | |
126 | -- its new bucket. | |
127 | ||
128 | procedure Query_Element | |
129 | (Position : Cursor; | |
130 | Process : not null access procedure (Element : Element_Type)); | |
131 | -- Calls Process with the element (having only a constant view) of the node | |
132 | -- designed by the cursor. | |
133 | ||
134 | procedure Assign (Target : in out Set; Source : Set); | |
135 | -- If Target denotes the same object as Source, then the operation has no | |
136 | -- effect. If the Target capacity is less then the Source length, then | |
137 | -- Assign raises Capacity_Error. Otherwise, Assign clears Target and then | |
138 | -- copies the (active) elements from Source to Target. | |
139 | ||
140 | function Copy | |
141 | (Source : Set; | |
142 | Capacity : Count_Type := 0; | |
143 | Modulus : Hash_Type := 0) return Set; | |
144 | -- Constructs a new set object whose elements correspond to Source. If the | |
145 | -- Capacity parameter is 0, then the capacity of the result is the same as | |
146 | -- the length of Source. If the Capacity parameter is equal or greater than | |
147 | -- the length of Source, then the capacity of the result is the specified | |
148 | -- value. Otherwise, Copy raises Capacity_Error. If the Modulus parameter | |
149 | -- is 0, then the modulus of the result is the value returned by a call to | |
150 | -- Default_Modulus with the capacity parameter determined as above; | |
151 | -- otherwise the modulus of the result is the specified value. | |
152 | ||
153 | procedure Move (Target : in out Set; Source : in out Set); | |
154 | -- Clears Target (if it's not empty), and then moves (not copies) the | |
155 | -- buckets array and nodes from Source to Target. | |
156 | ||
157 | procedure Insert | |
158 | (Container : in out Set; | |
159 | New_Item : Element_Type; | |
160 | Position : out Cursor; | |
161 | Inserted : out Boolean); | |
162 | -- Conditionally inserts New_Item into the set. If New_Item is already in | |
163 | -- the set, then Inserted returns False and Position designates the node | |
164 | -- containing the existing element (which is not modified). If New_Item is | |
165 | -- not already in the set, then Inserted returns True and Position | |
166 | -- designates the newly-inserted node containing New_Item. The search for | |
167 | -- an existing element works as follows. Hash is called to determine | |
168 | -- New_Item's bucket; if the bucket is non-empty, then Equivalent_Elements | |
169 | -- is called to compare New_Item to the element of each node in that | |
170 | -- bucket. If the bucket is empty, or there were no equivalent elements in | |
171 | -- the bucket, the search "fails" and the New_Item is inserted in the set | |
172 | -- (and Inserted returns True); otherwise, the search "succeeds" (and | |
173 | -- Inserted returns False). | |
174 | ||
175 | procedure Insert (Container : in out Set; New_Item : Element_Type); | |
176 | -- Attempts to insert New_Item into the set, performing the usual insertion | |
177 | -- search (which involves calling both Hash and Equivalent_Elements); if | |
178 | -- the search succeeds (New_Item is equivalent to an element already in the | |
179 | -- set, and so was not inserted), then this operation raises | |
180 | -- Constraint_Error. (This version of Insert is similar to Replace, but | |
181 | -- having the opposite exception behavior. It is intended for use when you | |
182 | -- want to assert that the item is not already in the set.) | |
183 | ||
184 | procedure Include (Container : in out Set; New_Item : Element_Type); | |
185 | -- Attempts to insert New_Item into the set. If an element equivalent to | |
186 | -- New_Item is already in the set (the insertion search succeeded, and | |
187 | -- hence New_Item was not inserted), then the value of New_Item is assigned | |
188 | -- to the existing element. (This insertion operation only raises an | |
189 | -- exception if cursor tampering occurs. It is intended for use when you | |
190 | -- want to insert the item in the set, and you don't care whether an | |
191 | -- equivalent element is already present.) | |
192 | ||
193 | procedure Replace (Container : in out Set; New_Item : Element_Type); | |
194 | -- Searches for New_Item in the set; if the search fails (because an | |
195 | -- equivalent element was not in the set), then it raises | |
196 | -- Constraint_Error. Otherwise, the existing element is assigned the value | |
197 | -- New_Item. (This is similar to Insert, but with the opposite exception | |
198 | -- behavior. It is intended for use when you want to assert that the item | |
199 | -- is already in the set.) | |
200 | ||
201 | procedure Exclude (Container : in out Set; Item : Element_Type); | |
202 | -- Searches for Item in the set, and if found, removes its node from the | |
203 | -- set and then deallocates it. The search works as follows. The operation | |
204 | -- calls Hash to determine the item's bucket; if the bucket is not empty, | |
205 | -- it calls Equivalent_Elements to compare Item to the element of each node | |
206 | -- in the bucket. (This is the deletion analog of Include. It is intended | |
207 | -- for use when you want to remove the item from the set, but don't care | |
208 | -- whether the item is already in the set.) | |
209 | ||
210 | procedure Delete (Container : in out Set; Item : Element_Type); | |
211 | -- Searches for Item in the set (which involves calling both Hash and | |
212 | -- Equivalent_Elements). If the search fails, then the operation raises | |
213 | -- Constraint_Error. Otherwise it removes the node from the set and then | |
214 | -- deallocates it. (This is the deletion analog of non-conditional | |
215 | -- Insert. It is intended for use when you want to assert that the item is | |
216 | -- already in the set.) | |
217 | ||
218 | procedure Delete (Container : in out Set; Position : in out Cursor); | |
219 | -- Removes the node designated by Position from the set, and then | |
220 | -- deallocates the node. The operation calls Hash to determine the bucket, | |
221 | -- and then compares Position to each node in the bucket until there's a | |
222 | -- match (it does not call Equivalent_Elements). | |
223 | ||
224 | procedure Union (Target : in out Set; Source : Set); | |
225 | -- Iterates over the Source set, and conditionally inserts each element | |
226 | -- into Target. | |
227 | ||
228 | function Union (Left, Right : Set) return Set; | |
229 | -- The operation first copies the Left set to the result, and then iterates | |
230 | -- over the Right set to conditionally insert each element into the result. | |
231 | ||
232 | function "or" (Left, Right : Set) return Set renames Union; | |
233 | ||
234 | procedure Intersection (Target : in out Set; Source : Set); | |
235 | -- Iterates over the Target set (calling First and Next), calling Find to | |
236 | -- determine whether the element is in Source. If an equivalent element is | |
237 | -- not found in Source, the element is deleted from Target. | |
238 | ||
239 | function Intersection (Left, Right : Set) return Set; | |
240 | -- Iterates over the Left set, calling Find to determine whether the | |
241 | -- element is in Right. If an equivalent element is found, it is inserted | |
242 | -- into the result set. | |
243 | ||
244 | function "and" (Left, Right : Set) return Set renames Intersection; | |
245 | ||
246 | procedure Difference (Target : in out Set; Source : Set); | |
247 | -- Iterates over the Source (calling First and Next), calling Find to | |
248 | -- determine whether the element is in Target. If an equivalent element is | |
249 | -- found, it is deleted from Target. | |
250 | ||
251 | function Difference (Left, Right : Set) return Set; | |
252 | -- Iterates over the Left set, calling Find to determine whether the | |
253 | -- element is in the Right set. If an equivalent element is not found, the | |
254 | -- element is inserted into the result set. | |
255 | ||
256 | function "-" (Left, Right : Set) return Set renames Difference; | |
257 | ||
258 | procedure Symmetric_Difference (Target : in out Set; Source : Set); | |
259 | -- The operation iterates over the Source set, searching for the element | |
260 | -- in Target (calling Hash and Equivalent_Elements). If an equivalent | |
308e6f3a | 261 | -- element is found, it is removed from Target; otherwise it is inserted |
f2acf80c AC |
262 | -- into Target. |
263 | ||
264 | function Symmetric_Difference (Left, Right : Set) return Set; | |
265 | -- The operation first iterates over the Left set. It calls Find to | |
266 | -- determine whether the element is in the Right set. If no equivalent | |
267 | -- element is found, the element from Left is inserted into the result. The | |
268 | -- operation then iterates over the Right set, to determine whether the | |
269 | -- element is in the Left set. If no equivalent element is found, the Right | |
270 | -- element is inserted into the result. | |
271 | ||
272 | function "xor" (Left, Right : Set) return Set | |
273 | renames Symmetric_Difference; | |
274 | ||
275 | function Overlap (Left, Right : Set) return Boolean; | |
276 | -- Iterates over the Left set (calling First and Next), calling Find to | |
277 | -- determine whether the element is in the Right set. If an equivalent | |
278 | -- element is found, the operation immediately returns True. The operation | |
279 | -- returns False if the iteration over Left terminates without finding any | |
280 | -- equivalent element in Right. | |
281 | ||
282 | function Is_Subset (Subset : Set; Of_Set : Set) return Boolean; | |
283 | -- Iterates over Subset (calling First and Next), calling Find to determine | |
284 | -- whether the element is in Of_Set. If no equivalent element is found in | |
285 | -- Of_Set, the operation immediately returns False. The operation returns | |
286 | -- True if the iteration over Subset terminates without finding an element | |
287 | -- not in Of_Set (that is, every element in Subset is equivalent to an | |
288 | -- element in Of_Set). | |
289 | ||
290 | function First (Container : Set) return Cursor; | |
291 | -- Returns a cursor that designates the first non-empty bucket, by | |
292 | -- searching from the beginning of the buckets array. | |
293 | ||
294 | function Next (Position : Cursor) return Cursor; | |
295 | -- Returns a cursor that designates the node that follows the current one | |
296 | -- designated by Position. If Position designates the last node in its | |
297 | -- bucket, the operation calls Hash to compute the index of this bucket, | |
298 | -- and searches the buckets array for the first non-empty bucket, starting | |
299 | -- from that index; otherwise, it simply follows the link to the next node | |
300 | -- in the same bucket. | |
301 | ||
302 | procedure Next (Position : in out Cursor); | |
303 | -- Equivalent to Position := Next (Position) | |
304 | ||
305 | function Find | |
306 | (Container : Set; | |
307 | Item : Element_Type) return Cursor; | |
308 | -- Searches for Item in the set. Find calls Hash to determine the item's | |
309 | -- bucket; if the bucket is not empty, it calls Equivalent_Elements to | |
310 | -- compare Item to each element in the bucket. If the search succeeds, Find | |
311 | -- returns a cursor designating the node containing the equivalent element; | |
312 | -- otherwise, it returns No_Element. | |
313 | ||
314 | function Contains (Container : Set; Item : Element_Type) return Boolean; | |
315 | -- Equivalent to Find (Container, Item) /= No_Element | |
316 | ||
317 | function Has_Element (Position : Cursor) return Boolean; | |
318 | -- Equivalent to Position /= No_Element | |
319 | ||
320 | function Equivalent_Elements (Left, Right : Cursor) return Boolean; | |
321 | -- Returns the result of calling Equivalent_Elements with the elements of | |
322 | -- the nodes designated by cursors Left and Right. | |
323 | ||
324 | function Equivalent_Elements | |
325 | (Left : Cursor; | |
326 | Right : Element_Type) return Boolean; | |
327 | -- Returns the result of calling Equivalent_Elements with element of the | |
328 | -- node designated by Left and element Right. | |
329 | ||
330 | function Equivalent_Elements | |
331 | (Left : Element_Type; | |
332 | Right : Cursor) return Boolean; | |
333 | -- Returns the result of calling Equivalent_Elements with element Left and | |
334 | -- the element of the node designated by Right. | |
335 | ||
336 | procedure Iterate | |
337 | (Container : Set; | |
338 | Process : not null access procedure (Position : Cursor)); | |
339 | -- Calls Process for each node in the set | |
340 | ||
341 | generic | |
342 | type Key_Type (<>) is private; | |
343 | ||
344 | with function Key (Element : Element_Type) return Key_Type; | |
345 | ||
346 | with function Hash (Key : Key_Type) return Hash_Type; | |
347 | ||
348 | with function Equivalent_Keys (Left, Right : Key_Type) return Boolean; | |
349 | ||
350 | package Generic_Keys is | |
351 | ||
352 | function Key (Position : Cursor) return Key_Type; | |
353 | -- Applies generic formal operation Key to the element of the node | |
354 | -- designated by Position. | |
355 | ||
356 | function Element (Container : Set; Key : Key_Type) return Element_Type; | |
357 | -- Searches (as per the key-based Find) for the node containing Key, and | |
358 | -- returns the associated element. | |
359 | ||
360 | procedure Replace | |
361 | (Container : in out Set; | |
362 | Key : Key_Type; | |
363 | New_Item : Element_Type); | |
364 | -- Searches (as per the key-based Find) for the node containing Key, and | |
365 | -- then replaces the element of that node (as per the element-based | |
366 | -- Replace_Element). | |
367 | ||
368 | procedure Exclude (Container : in out Set; Key : Key_Type); | |
369 | -- Searches for Key in the set, and if found, removes its node from the | |
370 | -- set and then deallocates it. The search works by first calling Hash | |
371 | -- (on Key) to determine the bucket; if the bucket is not empty, it | |
372 | -- calls Equivalent_Keys to compare parameter Key to the value of | |
373 | -- generic formal operation Key applied to element of each node in the | |
374 | -- bucket. | |
375 | ||
376 | procedure Delete (Container : in out Set; Key : Key_Type); | |
377 | -- Deletes the node containing Key as per Exclude, with the difference | |
378 | -- that Constraint_Error is raised if Key is not found. | |
379 | ||
380 | function Find (Container : Set; Key : Key_Type) return Cursor; | |
381 | -- Searches for the node containing Key, and returns a cursor | |
382 | -- designating the node. The search works by first calling Hash (on Key) | |
383 | -- to determine the bucket. If the bucket is not empty, the search | |
384 | -- compares Key to the element of each node in the bucket, and returns | |
385 | -- the matching node. The comparison itself works by applying the | |
386 | -- generic formal Key operation to the element of the node, and then | |
387 | -- calling generic formal operation Equivalent_Keys. | |
388 | ||
389 | function Contains (Container : Set; Key : Key_Type) return Boolean; | |
390 | -- Equivalent to Find (Container, Key) /= No_Element | |
391 | ||
392 | procedure Update_Element_Preserving_Key | |
393 | (Container : in out Set; | |
394 | Position : Cursor; | |
395 | Process : not null access | |
396 | procedure (Element : in out Element_Type)); | |
397 | -- Calls Process with the element of the node designated by Position, | |
398 | -- but with the restriction that the key-value of the element is not | |
399 | -- modified. The operation first makes a copy of the value returned by | |
400 | -- applying generic formal operation Key on the element of the node, and | |
401 | -- then calls Process with the element. The operation verifies that the | |
402 | -- key-part has not been modified by calling generic formal operation | |
403 | -- Equivalent_Keys to compare the saved key-value to the value returned | |
404 | -- by applying generic formal operation Key to the post-Process value of | |
405 | -- element. If the key values compare equal then the operation | |
406 | -- completes. Otherwise, the node is removed from the map and | |
407 | -- Program_Error is raised. | |
408 | ||
409 | end Generic_Keys; | |
410 | ||
411 | private | |
412 | ||
413 | pragma Inline (Next); | |
414 | ||
415 | type Node_Type is record | |
416 | Element : Element_Type; | |
417 | Next : Count_Type; | |
418 | end record; | |
419 | ||
420 | package HT_Types is | |
421 | new Hash_Tables.Generic_Bounded_Hash_Table_Types (Node_Type); | |
422 | ||
423 | type Set (Capacity : Count_Type; Modulus : Hash_Type) is | |
424 | new HT_Types.Hash_Table_Type (Capacity, Modulus) with null record; | |
425 | ||
426 | use HT_Types; | |
427 | use Ada.Streams; | |
428 | ||
429 | type Set_Access is access all Set; | |
430 | for Set_Access'Storage_Size use 0; | |
431 | ||
d85fd922 AC |
432 | -- Note: If a Cursor object has no explicit initialization expression, |
433 | -- it must default initialize to the same value as constant No_Element. | |
434 | -- The Node component of type Cursor has scalar type Count_Type, so it | |
435 | -- requires an explicit initialization expression of its own declaration, | |
436 | -- in order for objects of record type Cursor to properly initialize. | |
437 | ||
f2acf80c AC |
438 | type Cursor is record |
439 | Container : Set_Access; | |
c54796e0 | 440 | Node : Count_Type := 0; |
f2acf80c AC |
441 | end record; |
442 | ||
443 | procedure Write | |
444 | (Stream : not null access Root_Stream_Type'Class; | |
445 | Item : Cursor); | |
446 | ||
447 | for Cursor'Write use Write; | |
448 | ||
449 | procedure Read | |
450 | (Stream : not null access Root_Stream_Type'Class; | |
451 | Item : out Cursor); | |
452 | ||
453 | for Cursor'Read use Read; | |
454 | ||
455 | No_Element : constant Cursor := (Container => null, Node => 0); | |
456 | ||
457 | procedure Write | |
458 | (Stream : not null access Root_Stream_Type'Class; | |
459 | Container : Set); | |
460 | ||
461 | for Set'Write use Write; | |
462 | ||
463 | procedure Read | |
464 | (Stream : not null access Root_Stream_Type'Class; | |
465 | Container : out Set); | |
466 | ||
467 | for Set'Read use Read; | |
468 | ||
469 | Empty_Set : constant Set := | |
470 | (Hash_Table_Type with Capacity => 0, Modulus => 0); | |
471 | ||
472 | end Ada.Containers.Bounded_Hashed_Sets; |