131
|
1 ------------------------------------------------------------------------------
|
|
2 -- --
|
|
3 -- GNAT RUN-TIME COMPONENTS --
|
|
4 -- --
|
|
5 -- G N A T . S E T S --
|
|
6 -- --
|
|
7 -- S p e c --
|
|
8 -- --
|
|
9 -- Copyright (C) 2018, AdaCore --
|
|
10 -- --
|
|
11 -- GNAT is free software; you can redistribute it and/or modify it under --
|
|
12 -- terms of the GNU General Public License as published by the Free Soft- --
|
|
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
|
|
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
|
|
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
|
|
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
|
|
17 -- --
|
|
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
|
|
19 -- additional permissions described in the GCC Runtime Library Exception, --
|
|
20 -- version 3.1, as published by the Free Software Foundation. --
|
|
21 -- --
|
|
22 -- You should have received a copy of the GNU General Public License and --
|
|
23 -- a copy of the GCC Runtime Library Exception along with this program; --
|
|
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
|
|
25 -- <http://www.gnu.org/licenses/>. --
|
|
26 -- --
|
|
27 -- GNAT was originally developed by the GNAT team at New York University. --
|
|
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
|
|
29 -- --
|
|
30 ------------------------------------------------------------------------------
|
|
31
|
|
32 pragma Compiler_Unit_Warning;
|
|
33
|
|
34 with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables;
|
|
35
|
|
36 package GNAT.Sets is
|
|
37
|
|
38 --------------------
|
|
39 -- Membership_Set --
|
|
40 --------------------
|
|
41
|
|
42 -- The following package offers a membership set abstraction with the
|
|
43 -- following characteristics:
|
|
44 --
|
|
45 -- * Creation of multiple instances, of different sizes.
|
|
46 -- * Iterable elements.
|
|
47 --
|
|
48 -- The following use pattern must be employed with this set:
|
|
49 --
|
|
50 -- Set : Instance := Create (<some size>);
|
|
51 --
|
|
52 -- <various operations>
|
|
53 --
|
|
54 -- Destroy (Set);
|
|
55 --
|
|
56 -- The destruction of the set reclaims all storage occupied by it.
|
|
57
|
|
58 generic
|
|
59 type Element_Type is private;
|
|
60
|
|
61 with function "="
|
|
62 (Left : Element_Type;
|
|
63 Right : Element_Type) return Boolean;
|
|
64
|
|
65 with function Hash (Key : Element_Type) return Bucket_Range_Type;
|
|
66 -- Map an arbitrary key into the range of buckets
|
|
67
|
|
68 package Membership_Set is
|
|
69
|
|
70 --------------------
|
|
71 -- Set operations --
|
|
72 --------------------
|
|
73
|
|
74 -- The following type denotes a membership set handle. Each instance
|
|
75 -- must be created using routine Create.
|
|
76
|
|
77 type Instance is private;
|
|
78 Nil : constant Instance;
|
|
79
|
|
80 function Contains (S : Instance; Elem : Element_Type) return Boolean;
|
|
81 -- Determine whether membership set S contains element Elem
|
|
82
|
|
83 function Create (Initial_Size : Positive) return Instance;
|
|
84 -- Create a new membership set with bucket capacity Initial_Size. This
|
|
85 -- routine must be called at the start of the membership set's lifetime.
|
|
86
|
|
87 procedure Delete (S : Instance; Elem : Element_Type);
|
|
88 -- Delete element Elem from membership set S. The routine has no effect
|
|
89 -- if the element is not present in the membership set. This action will
|
|
90 -- raise Iterated if the membership set has outstanding iterators.
|
|
91
|
|
92 procedure Destroy (S : in out Instance);
|
|
93 -- Destroy the contents of membership set S, rendering it unusable. This
|
|
94 -- routine must be called at the end of the membership set's lifetime.
|
|
95 -- This action will raise Iterated if the hash table has outstanding
|
|
96 -- iterators.
|
|
97
|
|
98 procedure Insert (S : Instance; Elem : Element_Type);
|
|
99 -- Insert element Elem in membership set S. The routine has no effect
|
|
100 -- if the element is already present in the membership set. This action
|
|
101 -- will raise Iterated if the membership set has outstanding iterators.
|
|
102
|
|
103 function Is_Empty (S : Instance) return Boolean;
|
|
104 -- Determine whether set S is empty
|
|
105
|
|
106 function Size (S : Instance) return Natural;
|
|
107 -- Obtain the number of elements in membership set S
|
|
108
|
|
109 -------------------------
|
|
110 -- Iterator operations --
|
|
111 -------------------------
|
|
112
|
|
113 -- The following type represents an element iterator. An iterator locks
|
|
114 -- all mutation operations, and unlocks them once it is exhausted. The
|
|
115 -- iterator must be used with the following pattern:
|
|
116 --
|
|
117 -- Iter := Iterate (My_Set);
|
|
118 -- while Has_Next (Iter) loop
|
|
119 -- Next (Iter, Element);
|
|
120 -- end loop;
|
|
121 --
|
|
122 -- It is possible to advance the iterator by using Next only, however
|
|
123 -- this risks raising Iterator_Exhausted.
|
|
124
|
|
125 type Iterator is private;
|
|
126
|
|
127 function Iterate (S : Instance) return Iterator;
|
|
128 -- Obtain an iterator over the elements of membership set S. This action
|
|
129 -- locks all mutation functionality of the associated membership set.
|
|
130
|
|
131 function Has_Next (Iter : Iterator) return Boolean;
|
|
132 -- Determine whether iterator Iter has more keys to examine. If the
|
|
133 -- iterator has been exhausted, restore all mutation functionality of
|
|
134 -- the associated membership set.
|
|
135
|
|
136 procedure Next (Iter : in out Iterator; Elem : out Element_Type);
|
|
137 -- Return the current element referenced by iterator Iter and advance
|
|
138 -- to the next available element. If the iterator has been exhausted
|
|
139 -- and further attempts are made to advance it, this routine restores
|
|
140 -- mutation functionality of the associated membership set, and then
|
|
141 -- raises Iterator_Exhausted.
|
|
142
|
|
143 private
|
|
144 package Hashed_Set is new Dynamic_HTable
|
|
145 (Key_Type => Element_Type,
|
|
146 Value_Type => Boolean,
|
|
147 No_Value => False,
|
|
148 Expansion_Threshold => 1.5,
|
|
149 Expansion_Factor => 2,
|
|
150 Compression_Threshold => 0.3,
|
|
151 Compression_Factor => 2,
|
|
152 "=" => "=",
|
|
153 Hash => Hash);
|
|
154
|
|
155 type Instance is new Hashed_Set.Instance;
|
|
156 Nil : constant Instance := Instance (Hashed_Set.Nil);
|
|
157
|
|
158 type Iterator is new Hashed_Set.Iterator;
|
|
159 end Membership_Set;
|
|
160
|
|
161 end GNAT.Sets;
|