1--  Copyright 1994 Grady Booch
2--  Copyright 1998-2014 Simon Wright <simon@pushface.org>
3
4--  This package is free software; you can redistribute it and/or
5--  modify it under terms of the GNU General Public License as
6--  published by the Free Software Foundation; either version 2, or
7--  (at your option) any later version. This package is distributed in
8--  the hope that it will be useful, but WITHOUT ANY WARRANTY; without
9--  even the implied warranty of MERCHANTABILITY or FITNESS FOR A
10--  PARTICULAR PURPOSE. See the GNU General Public License for more
11--  details. You should have received a copy of the GNU General Public
12--  License distributed with this package; see file COPYING.  If not,
13--  write to the Free Software Foundation, 59 Temple Place - Suite
14--  330, Boston, MA 02111-1307, USA.
15
16--  As a special exception, if other files instantiate generics from
17--  this unit, or you link this unit with other files to produce an
18--  executable, this unit does not by itself cause the resulting
19--  executable to be covered by the GNU General Public License.  This
20--  exception does not however invalidate any other reasons why the
21--  executable file might be covered by the GNU Public License.
22
23with BC.Support.Bounded_Hash_Tables;
24
25generic
26   with function Hash (V : Item) return Natural is <>;
27   Buckets : Positive;
28   Maximum_Size : Positive;
29package BC.Containers.Sets.Bounded is
30
31   pragma Preelaborate;
32
33   --  A set denotes a collection of items, drawn from some
34   --  well-defined universe. A set may not contain duplicate items.
35
36   --  The hash function (the generic parameter Hash) determines the
37   --  allocation of items to hash buckets. The value returned must
38   --  not change during the lifetime of a given Item. The range of
39   --  hash values need not be constrained to the number of buckets in
40   --  the set.
41
42   --  The hash function must satisfy the condition that, for objects
43   --  A and B, if A = B, then Hash (A) must equal Hash (B). The hash
44   --  function should attempt to spread the set of possible items
45   --  uniformly across the number of buckets. The quality of the hash
46   --  function has a significant impact upon performance.
47
48   type Unconstrained_Set
49     (Number_Of_Buckets : Positive;
50      Maximum_Size : Positive) is new Abstract_Set with private;
51
52   subtype Set is Unconstrained_Set (Number_Of_Buckets => Buckets,
53                                     Maximum_Size => Maximum_Size);
54
55   function Null_Container return Unconstrained_Set;
56   --  Note, this function has to be provided but the object returned
57   --  is in fact a Set (ie, it is constrained).
58
59   procedure Clear (S : in out Unconstrained_Set);
60   --  Empty the set of all items.
61
62   procedure Add (S : in out Unconstrained_Set; I : Item; Added : out Boolean);
63   --  Add the item to the set. If the item is not already a distinct
64   --  member of the set, copy the item and add it to the set and set
65   --  Added to True. If the item already exists, then set Added to
66   --  False.
67
68   procedure Add (S : in out Unconstrained_Set; I : Item);
69   --  Add the item to the set. If the item is not already a distinct
70   --  member of the set, copy the item and add it to the set.
71
72   procedure Remove (S : in out Unconstrained_Set; I : Item);
73   --  If the item is not a member of the set, raise
74   --  BC.Not_Found. Otherwise, remove the item from the set.
75
76   function Available (S : Unconstrained_Set) return Natural;
77   --  Return the number of unused slots in the set.
78
79   function Extent (S : Unconstrained_Set) return Natural;
80   --  Return the number of distinct items in the set.
81
82   function Is_Empty (S : Unconstrained_Set) return Boolean;
83   --  Return True if and only if there are no items in the set.
84
85   function Is_Member (S : Unconstrained_Set; I : Item) return Boolean;
86   --  Return True if and only if the item exists in the set.
87
88   function New_Iterator
89     (For_The_Set : Unconstrained_Set) return Iterator'Class;
90   --  Return a reset Iterator bound to the specific Set.
91
92private
93
94   package Items is new BC.Support.Bounded_Hash_Tables.Item_Signature
95     (Item => Item,
96      Item_Ptr => Item_Ptr,
97      Eq => Containers."=",
98      Hash => Hash);
99
100   --  We need a dummy type for the Value component of the hash table.
101   type Dummy is null record;
102   type Dummy_Ptr is access all Dummy;
103   package Values is new BC.Support.Bounded_Hash_Tables.Value_Signature
104     (Value => Dummy,
105      Value_Ptr => Dummy_Ptr,
106      Eq => "=");
107
108   package Tables is new BC.Support.Bounded_Hash_Tables.Tables
109     (Items => Items,
110      Values => Values);
111
112   type Unconstrained_Set
113     (Number_Of_Buckets : Positive;
114      Maximum_Size : Positive)
115   is new Abstract_Set with record
116      Rep : Tables.Table (Number_Of_Buckets => Buckets,
117                          Maximum_Size => Maximum_Size);
118   end record;
119
120   type Bounded_Set_Iterator is new Set_Iterator with null record;
121
122   procedure Reset (It : in out Bounded_Set_Iterator);
123
124   procedure Next (It : in out Bounded_Set_Iterator);
125
126   function Is_Done (It : Bounded_Set_Iterator) return Boolean;
127
128   function Current_Item (It : Bounded_Set_Iterator) return Item;
129
130   function Current_Item_Ptr (It : Bounded_Set_Iterator) return Item_Ptr;
131
132   procedure Delete_Item_At (It : in out Bounded_Set_Iterator);
133
134end BC.Containers.Sets.Bounded;
135