8e27c806f4fcc5568c17d67c8f1d592be6b38b9f
1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2004-2009 Jean Privat <jean@pryen.org>
5 # This file is free software, which comes along with NIT. This software is
6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
7 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
8 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
9 # is kept unaltered, and a notification of the changes is added.
10 # You are allowed to redistribute it and sell it, alone or is a part of
13 # Introduce Hashmap and Hashset.
14 module hash_collection
18 # A HashCollection is an array of HashNode[K] indexed by the K hash value
19 private abstract class HashCollection[K
: Object, N
: HashNode[Object]]
21 private var array
: nullable NativeArray[nullable N
] = null # Used to store items
22 private var capacity
: Int = 0 # Size of _array
23 private var the_length
: Int = 0 # Number of items in the map
25 private var first_item
: nullable N
= null # First added item (used to visit items in nice order)
26 private var last_item
: nullable N
= null # Last added item (same)
28 # The last key accessed (used for cache)
29 private var last_accessed_key
: nullable K
= null
31 # The last node accessed (used for cache)
32 private var last_accessed_node
: nullable N
= null
34 # Return the index of the key k
35 fun index_at
(k
: K
): Int
37 var i
= k
.hash
% _capacity
42 # Return the node assosiated with the key
43 fun node_at
(k
: K
): nullable N
45 # cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
46 if k
.is_same_instance
(_last_accessed_key
) then return _last_accessed_node
48 var res
= node_at_idx
(index_at
(k
), k
)
49 _last_accessed_key
= k
50 _last_accessed_node
= res
54 # Return the node assosiated with the key (but with the index already known)
55 fun node_at_idx
(i
: Int, k
: K
): nullable N
60 if ck
.is_same_instance
(k
) or ck
== k
then # FIXME prefilter because the compiler is not smart enought yet
63 c
= c
._next_in_bucklet
68 # Add a new node at a given index
69 fun store
(index
: Int, node
: N
)
71 # Store the item in the list
72 if _first_item
== null then
75 _last_item
._next_item
= node
77 node
._prev_item
= _last_item
78 node
._next_item
= null
81 # Then store it in the array
82 var next
= _array
[index
]
84 node
._next_in_bucklet
= next
85 if next
!= null then next
._prev_in_bucklet
= node
87 _last_accessed_key
= node
._key
88 _last_accessed_node
= node
94 # Magic values determined empirically
95 # We do not want to enlarge too much
96 # We also want a odd capacity so that the modulo is more distributive
98 if l
>= _capacity
then
99 enlarge
(l
* 3 / 2 + 1)
103 # Remove the node assosiated with the key
104 fun remove_node
(k
: K
)
107 var node
= node_at_idx
(i
, k
)
108 if node
== null then return
110 # Remove the item in the list
111 var prev
= node
._prev_item
112 var next
= node
._next_item
114 prev
._next_item
= next
119 next
._prev_item
= prev
124 # Remove the item in the array
126 prev
= node
._prev_in_bucklet
127 next
= node
._next_in_bucklet
129 prev
._next_in_bucklet
= next
134 next
._prev_in_bucklet
= prev
137 _last_accessed_key
= null
140 # Clear the whole structure
143 var i
= _capacity
- 1
151 _last_accessed_key
= null
155 fun enlarge
(cap
: Int)
157 var old_cap
= _capacity
159 if cap
< _the_length
+ 1 then cap
= _the_length
+ 1
160 if cap
<= _capacity
then return
162 _last_accessed_key
= null
165 var new_array
= new NativeArray[nullable N
](cap
)
168 # clean the new array
175 if _capacity
<= old_cap
then return
177 # Reput items in the array
178 var node
= _first_item
179 while node
!= null do
180 var index
= index_at
(node
._key
)
181 # Then store it in the array
182 var next
= new_array
[index
]
183 new_array
[index
] = node
184 node
._prev_in_bucklet
= null
185 node
._next_in_bucklet
= next
186 if next
!= null then next
._prev_in_bucklet
= node
187 node
= node
._next_item
192 private abstract class HashNode[K
: Object]
195 private var next_item
: nullable N
= null
196 private var prev_item
: nullable N
= null
197 private var prev_in_bucklet
: nullable N
= null
198 private var next_in_bucklet
: nullable N
= null
201 # A map implemented with a hash table.
202 # Keys of such a map cannot be null and require a working `hash` method
203 class HashMap[K
: Object, V
]
205 super HashCollection[K
, HashMapNode[K
, V
]]
211 return provide_default_value
(key
)
217 redef fun iterator
: HashMapIterator[K
, V
] do return new HashMapIterator[K
,V
](self)
219 redef fun length
do return _the_length
221 redef fun is_empty
do return _the_length
== 0
223 redef fun []=(key
, v
)
225 var i
= index_at
(key
)
226 var c
= node_at_idx
(i
, key
)
231 store
(i
, new HashMapNode[K
, V
](key
, v
))
235 redef fun clear
do raz
244 redef var keys
: RemovableCollection[K
] = new HashMapKeys[K
, V
](self)
245 redef var values
: RemovableCollection[V
] = new HashMapValues[K
, V
](self)
248 # View of the keys of a HashMap
249 private class HashMapKeys[K
: Object, V
]
250 super RemovableCollection[K
]
252 var map
: HashMap[K
, V
]
254 redef fun count
(k
) do if self.has
(k
) then return 1 else return 0
255 redef fun first
do return self.map
._first_item
._key
256 redef fun has
(k
) do return self.map
.node_at
(k
) != null
257 redef fun has_only
(k
) do return (self.has
(k
) and self.length
== 1) or self.is_empty
258 redef fun is_empty
do return self.map
.is_empty
259 redef fun length
do return self.map
.length
261 redef fun iterator
do return new MapKeysIterator[K
, V
](self.map
.iterator
)
263 redef fun clear
do self.map
.clear
265 redef fun remove
(key
) do self.map
.remove_node
(key
)
266 redef fun remove_all
(key
) do self.map
.remove_node
(key
)
269 # View of the values of a Map
270 private class HashMapValues[K
: Object, V
]
271 super RemovableCollection[V
]
273 var map
: HashMap[K
, V
]
275 redef fun count
(item
)
278 var c
= self.map
._first_item
280 if c
._value
== item
then nb
+= 1
285 redef fun first
do return self.map
._first_item
._value
289 var c
= self.map
._first_item
291 if c
._value
== item
then return true
297 redef fun has_only
(item
)
299 var c
= self.map
._first_item
301 if c
._value
!= item
then return false
307 redef fun is_empty
do return self.map
.is_empty
308 redef fun length
do return self.map
.length
310 redef fun iterator
do return new MapValuesIterator[K
, V
](self.map
.iterator
)
312 redef fun clear
do self.map
.clear
314 redef fun remove
(item
)
317 var c
= map
._first_item
319 if c
._value
== item
then
320 map
.remove_node
(c
._key
)
327 redef fun remove_all
(item
)
330 var c
= map
._first_item
332 if c
._value
== item
then
333 map
.remove_node
(c
._key
)
340 private class HashMapNode[K
: Object, V
]
342 redef type N
: HashMapNode[K
, V
]
346 class HashMapIterator[K
: Object, V
]
347 super MapIterator[K
, V
]
348 redef fun is_ok
do return _node
!= null
356 #redef fun item=(value)
359 # _node.second = value
371 _node
= _node
._next_item
374 # The map to iterate on
375 private var map
: HashMap[K
, V
]
378 private var node
: nullable HashMapNode[K
, V
] = null
383 _node
= _map
._first_item
387 # A `Set` implemented with a hash table.
388 # Keys of such a map cannot be null and require a working `hash` method
389 class HashSet[E
: Object]
391 super HashCollection[E
, HashSetNode[E
]]
393 redef fun length
do return _the_length
395 redef fun is_empty
do return _the_length
== 0
399 assert _the_length
> 0
400 return _first_item
._key
405 return node_at
(item
) != null
410 var i
= index_at
(item
)
411 var c
= node_at_idx
(i
, item
)
415 store
(i
,new HashSetNode[E
](item
))
419 redef fun remove
(item
) do remove_node
(item
)
421 redef fun clear
do raz
423 redef fun iterator
do return new HashSetIterator[E
](self)
432 # Build a list filled with the items of `coll`.
433 init from
(coll
: Collection[E
]) do
438 redef fun new_set
do return new HashSet[E
]
441 private class HashSetNode[E
: Object]
443 redef type N
: HashSetNode[E
]
446 private class HashSetIterator[E
: Object]
448 redef fun is_ok
do return _node
!= null
459 _node
= _node
._next_item
462 # The set to iterate on
463 private var set
: HashSet[E
]
465 # The position in the internal map storage
466 private var node
: nullable HashSetNode[E
] = null
470 _node
= _set
._first_item