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 (K : Key) return Natural is <>;
27   Buckets : Positive;
28   Maximum_Size : Positive;
29package BC.Containers.Maps.Bounded 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;
50      Maximum_Size : Positive) is new Abstract_Map with private;
51
52   subtype Map is Unconstrained_Map (Number_Of_Buckets => Buckets,
53                                     Maximum_Size => Maximum_Size);
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 Available (M : Unconstrained_Map) return Natural;
80   --  Return the number of unused slots in the map.
81
82   function Extent (M : Unconstrained_Map) return Natural;
83   --  Return the number of key/item bindings in the map.
84
85   function Is_Empty (M : Unconstrained_Map) return Boolean;
86   --  Return True if and only if there are no key/item bindings in
87   --  the map; otherwise, return False.
88
89   function Is_Bound (M : Unconstrained_Map; K : Key) return Boolean;
90   --  Return True if and only if there is a binding for the given key
91   --  in the map; otherwise, return False.
92
93   function Item_Of (M : Unconstrained_Map; K : Key) return Item;
94   --  If the key does not exist in the map, raises
95   --  BC.Not_Found. Otherwise, return a copy of the item bound to the
96   --  given key.
97
98   function New_Iterator
99     (For_The_Map : Unconstrained_Map) return Iterator'Class;
100   --  Return a reset Iterator bound to the specific Map.
101
102private
103
104   package Keys is new BC.Support.Bounded_Hash_Tables.Item_Signature
105     (Item => Key,
106      Item_Ptr => Key_Ptr,
107      Eq => Maps."=",
108      Hash => Hash);
109
110   package Items is new BC.Support.Bounded_Hash_Tables.Value_Signature
111     (Value => Item,
112      Value_Ptr => Item_Ptr,
113      Eq => Containers."=");
114
115   package Tables is new BC.Support.Bounded_Hash_Tables.Tables
116     (Items => Keys,
117      Values => Items);
118
119   type Unconstrained_Map
120     (Number_Of_Buckets : Positive;
121      Maximum_Size : Positive)
122   is new Abstract_Map with record
123      Rep : Tables.Table (Number_Of_Buckets => Number_Of_Buckets,
124                          Maximum_Size => Maximum_Size);
125   end record;
126
127   type Bounded_Map_Iterator is new Map_Iterator with null record;
128
129   procedure Reset (It : in out Bounded_Map_Iterator);
130
131   procedure Next (It : in out Bounded_Map_Iterator);
132
133   function Is_Done (It : Bounded_Map_Iterator) return Boolean;
134
135   function Current_Key (It : Bounded_Map_Iterator) return Key;
136
137   function Current_Item (It : Bounded_Map_Iterator) return Item;
138
139   function Current_Item_Ptr (It : Bounded_Map_Iterator) return Item_Ptr;
140
141   procedure Delete_Item_At (It : in out Bounded_Map_Iterator);
142
143end BC.Containers.Maps.Bounded;
144