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.Unbounded;
24with BC.Support.Hash_Tables;
25with System.Storage_Pools;
26
27generic
28   with function Hash (K : Key) return Natural is <>;
29   Buckets : Positive;
30   Storage : in out System.Storage_Pools.Root_Storage_Pool'Class;
31package BC.Containers.Maps.Unbounded is
32
33   pragma Preelaborate;
34
35   --  A map denotes a collection forming a dictionary of domain/range
36   --  pairs.
37
38   --  The hash function (the generic parameter Hash) determines the
39   --  allocation of pairs to hash buckets. The value returned must
40   --  not change during the lifetime of a given Item. The range of
41   --  hash values need not be constrained to the number of buckets in
42   --  the map.
43
44   --  The hash function must satisfy the condition that, for objects
45   --  A and B, if A = B, then Hash (A) must equal Hash (B). The hash
46   --  function should attempt to spread the set of possible items
47   --  uniformly across the number of buckets. The quality of the hash
48   --  function has a significant impact upon performance.
49
50   type Unconstrained_Map
51     (Number_Of_Buckets : Positive) is new Abstract_Map with private;
52
53   subtype Map is Unconstrained_Map (Number_Of_Buckets => Buckets);
54
55   function Null_Container return Unconstrained_Map;
56   --  Note, this function has to be provided but the object returned
57   --  is in fact a Map (ie, it is constrained).
58
59   function "=" (L, R : Unconstrained_Map) return Boolean;
60   --  Return True if the two Maps contain the same items bound to the
61   --  same values.
62
63   procedure Clear (M : in out Unconstrained_Map);
64   --  Empty the map of all key/item pairs.
65
66   procedure Bind (M : in out Unconstrained_Map; K : Key; I : Item);
67   --  If the key already exists in the map, raise
68   --  BC.Duplicate. Otherwise, add the key/item pair to the map.
69
70   procedure Rebind (M : in out Unconstrained_Map; K : Key; I : Item);
71   --  If the key does not exist in the map, raise
72   --  BC.Not_Found. Otherwise, change the key's binding to the given
73   --  value.
74
75   procedure Unbind (M : in out Unconstrained_Map; K : Key);
76   --  If the key does not exist in the map, raise
77   --  BC.Not_Found. Otherwise, remove the key/item binding.
78
79   function Extent (M : Unconstrained_Map) return Natural;
80   --  Return the number of key/item bindings in the map.
81
82   function Is_Empty (M : Unconstrained_Map) return Boolean;
83   --  Return True if and only if there are no key/item bindings in
84   --  the map; otherwise, return False.
85
86   function Is_Bound (M : Unconstrained_Map; K : Key) return Boolean;
87   --  Return True if and only if there is a binding for the given key
88   --  in the map; otherwise, return False.
89
90   function Item_Of (M : Unconstrained_Map; K : Key) return Item;
91   --  If the key does not exist in the map, raises
92   --  BC.Not_Found. Otherwise, return a copy of the item bound to the
93   --  given key.
94
95   function New_Iterator
96     (For_The_Map : Unconstrained_Map) return Iterator'Class;
97   --  Return a reset Iterator bound to the specific Map.
98
99private
100
101   package KC is new BC.Support.Unbounded (Item => Key,
102                                           "=" => Maps."=",
103                                           Item_Ptr => Key_Ptr,
104                                           Storage => Storage);
105   package Keys is new BC.Support.Hash_Tables.Item_Signature
106     (Item => Key,
107      Item_Ptr => Key_Ptr,
108      Eq => Maps."=",
109      Hash => Hash,
110      Item_Container => KC.Unb_Node,
111      Clear => KC.Clear,
112      Insert => KC.Insert,
113      Append => KC.Append,
114      Remove => KC.Remove,
115      Replace => KC.Replace,
116      Length => KC.Length,
117      Item_At => KC.Item_At,
118      Access_Item_At => KC.Item_At,
119      Location => KC.Location);
120
121   package IC is new BC.Support.Unbounded (Item => Item,
122                                           "=" => Containers."=",
123                                           Item_Ptr => Item_Ptr,
124                                           Storage => Storage);
125   package Items is new BC.Support.Hash_Tables.Value_Signature
126     (Value => Item,
127      Value_Ptr => Item_Ptr,
128      Eq => Containers."=",
129      Value_Container => IC.Unb_Node,
130      Clear => IC.Clear,
131      Insert => IC.Insert,
132      Append => IC.Append,
133      Remove => IC.Remove,
134      Replace => IC.Replace,
135      Length => IC.Length,
136      Item_At => IC.Item_At,
137      Access_Item_At => IC.Item_At,
138      Location => IC.Location);
139
140   package Tables is new BC.Support.Hash_Tables.Tables
141     (Items => Keys,
142      Values => Items);
143
144   type Unconstrained_Map
145     (Number_Of_Buckets : Positive)
146   is new Abstract_Map with record
147      Rep : Tables.Table (Number_Of_Buckets => Number_Of_Buckets);
148   end record;
149
150   --  Iterators
151
152   type Unbounded_Map_Iterator is new Map_Iterator with null record;
153
154   procedure Reset (It : in out Unbounded_Map_Iterator);
155
156   procedure Next (It : in out Unbounded_Map_Iterator);
157
158   function Is_Done (It : Unbounded_Map_Iterator) return Boolean;
159
160   function Current_Key (It : Unbounded_Map_Iterator) return Key;
161
162   function Current_Item (It : Unbounded_Map_Iterator) return Item;
163
164   function Current_Item_Ptr (It : Unbounded_Map_Iterator) return Item_Ptr;
165
166   procedure Delete_Item_At (It : in out Unbounded_Map_Iterator);
167
168end BC.Containers.Maps.Unbounded;
169