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