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