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.Dynamic;
24with BC.Support.Hash_Tables;
25with System.Storage_Pools;
26
27generic
28   with function Hash (V : Item) return Natural is <>;
29   Buckets : Positive;
30   Storage : in out System.Storage_Pools.Root_Storage_Pool'Class;
31   Initial_Size : Positive := 10;
32package BC.Containers.Sets.Dynamic is
33
34   pragma Preelaborate;
35
36   --  A set denotes a collection of items, drawn from some
37   --  well-defined universe. A set may not contain duplicate items.
38
39   --  The hash function (the generic parameter Hash) determines the
40   --  allocation of items to hash buckets. The value returned must
41   --  not change during the lifetime of a given Item. The range of
42   --  hash values need not be constrained to the number of buckets in
43   --  the set.
44
45   --  The hash function must satisfy the condition that, for objects
46   --  A and B, if A = B, then Hash (A) must equal Hash (B). The hash
47   --  function should attempt to spread the set of possible items
48   --  uniformly across the number of buckets. The quality of the hash
49   --  function has a significant impact upon performance.
50
51   type Set is new Abstract_Set with private;
52
53   function Null_Container return Set;
54
55   function Create (Size : Positive) return Set;
56   --  Creates a new Dynamic Set each of whose buckets is preallocated
57   --  for 'Size' elements
58
59   procedure Clear (S : in out Set);
60   --  Empty the set of all items.
61
62   procedure Add (S : in out 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 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 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 Extent (S : Set) return Natural;
77   --  Return the number of items in the set.
78
79   function Is_Empty (S : Set) return Boolean;
80   --  Return True if and only if there are no items in the set.
81
82   function Is_Member (S : Set; I : Item) return Boolean;
83   --  Return True if and only if the item exists in the set.
84
85   procedure Preallocate (S : in out Set; Size : Positive);
86   --  Allocates 'Size' additional storage elements for each bucket of
87   --  the Set.
88
89   procedure Set_Chunk_Size (S : in out Set; Size : Positive);
90   --  Establishes the Size each bucket of the Set will grow if the
91   --  Set exhausts its current size.
92
93   function Chunk_Size (S : Set) return Positive;
94   --  Returns the Chunk_Size.
95
96   function New_Iterator (For_The_Set : Set) return Iterator'Class;
97   --  Return a reset Iterator bound to the specific Set.
98
99private
100
101   package IC is new BC.Support.Dynamic (Item => Item,
102                                         Item_Ptr => Item_Ptr,
103                                         Storage => Storage,
104                                         Initial_Size => Initial_Size);
105   package Items is new BC.Support.Hash_Tables.Item_Signature
106     (Item => Item,
107      Item_Ptr => Item_Ptr,
108      Eq => Containers."=",
109      Hash => Hash,
110      Item_Container => IC.Dyn_Node,
111      Clear => IC.Clear,
112      Insert => IC.Insert,
113      Append => IC.Append,
114      Remove => IC.Remove,
115      Replace => IC.Replace,
116      Length => IC.Length,
117      Item_At => IC.Item_At,
118      Access_Item_At => IC.Item_At,
119      Location => IC.Location);
120
121   --  We need a dummy type for the Value component of the hash table.
122   type Dummy is null record;
123   type Dummy_Ptr is access all Dummy;
124   package VC is new BC.Support.Dynamic (Item => Dummy,
125                                         Item_Ptr => Dummy_Ptr,
126                                         Storage => Storage,
127                                         Initial_Size => Initial_Size);
128   package Values is new BC.Support.Hash_Tables.Value_Signature
129     (Value => Dummy,
130      Value_Ptr => Dummy_Ptr,
131      Eq => "=",
132      Value_Container => VC.Dyn_Node,
133      Clear => VC.Clear,
134      Insert => VC.Insert,
135      Append => VC.Append,
136      Remove => VC.Remove,
137      Replace => VC.Replace,
138      Length => VC.Length,
139      Item_At => VC.Item_At,
140      Access_Item_At => VC.Item_At,
141      Location => VC.Location);
142
143   package Tables is new BC.Support.Hash_Tables.Tables
144     (Items => Items,
145      Values => Values);
146
147   type Set is new Abstract_Set with record
148      Rep : Tables.Table (Number_Of_Buckets => Buckets);
149   end record;
150
151   --  Iterators
152
153   type Dynamic_Set_Iterator is new Set_Iterator with null record;
154
155   procedure Reset (It : in out Dynamic_Set_Iterator);
156
157   procedure Next (It : in out Dynamic_Set_Iterator);
158
159   function Is_Done (It : Dynamic_Set_Iterator) return Boolean;
160
161   function Current_Item (It : Dynamic_Set_Iterator) return Item;
162
163   function Current_Item_Ptr (It : Dynamic_Set_Iterator) return Item_Ptr;
164
165   procedure Delete_Item_At (It : in out Dynamic_Set_Iterator);
166
167end BC.Containers.Sets.Dynamic;
168