1a27991d11691021e97a11f047f8dcc0f25c1221
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
19 # Get a `HashMap[K, V]` as default implementation
20 new do return new HashMap[K
, V
]
23 # A HashCollection is an array of HashNode[K] indexed by the K hash value
24 private abstract class HashCollection[K
]
27 var array
: nullable NativeArray[nullable N
] = null # Used to store items
28 var capacity
: Int = 0 # Size of _array
29 var the_length
: Int = 0 # Number of items in the map
31 var first_item
: nullable N
= null # First added item (used to visit items in nice order)
32 var last_item
: nullable N
= null # Last added item (same)
34 # The last key accessed (used for cache)
35 var last_accessed_key
: nullable Object = null
37 # The last node accessed (used for cache)
38 var last_accessed_node
: nullable N
= null
40 # Return the index of the key k
41 fun index_at
(k
: nullable Object): Int
43 if k
== null then return 0
45 var i
= k
.hash
% _capacity
50 # Return the node associated with the key
51 fun node_at
(k
: nullable Object): nullable N
53 if _the_length
== 0 then return null
54 # cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
55 if k
.is_same_instance
(_last_accessed_key
) then return _last_accessed_node
57 var res
= node_at_idx
(index_at
(k
), k
)
58 _last_accessed_key
= k
59 _last_accessed_node
= res
63 # Return the node associated with the key (but with the index already known)
64 fun node_at_idx
(i
: Int, k
: nullable Object): nullable N
66 if _the_length
== 0 then return null
70 if ck
.is_same_instance
(k
) or ck
== k
then # FIXME prefilter because the compiler is not smart enought yet
73 c
= c
._next_in_bucklet
78 # Add a new node at a given index
79 fun store
(index
: Int, node
: N
)
81 # Store the item in the list
82 if _first_item
== null then
85 _last_item
._next_item
= node
87 node
._prev_item
= _last_item
88 node
._next_item
= null
91 # Then store it in the array
92 var next
= _array
[index
]
94 node
._next_in_bucklet
= next
95 if next
!= null then next
._prev_in_bucklet
= node
97 _last_accessed_key
= node
._key
98 _last_accessed_node
= node
104 # Magic values determined empirically
105 # We do not want to enlarge too much
106 # We also want a odd capacity so that the modulo is more distributive
108 if l
>= _capacity
then
109 enlarge
(l
* 3 / 2 + 1)
113 # Remove the node assosiated with the key
114 fun remove_node
(k
: nullable Object)
116 if _the_length
== 0 then return
118 var node
= node_at_idx
(i
, k
)
119 if node
== null then return
121 # Remove the item in the list
122 var prev
= node
._prev_item
123 var next
= node
._next_item
125 prev
._next_item
= next
130 next
._prev_item
= prev
135 # Remove the item in the array
137 prev
= node
._prev_in_bucklet
138 next
= node
._next_in_bucklet
140 prev
._next_in_bucklet
= next
145 next
._prev_in_bucklet
= prev
148 _last_accessed_key
= null
151 # Clear the whole structure
154 var i
= _capacity
- 1
162 _last_accessed_key
= null
166 fun enlarge
(cap
: Int)
168 var old_cap
= _capacity
170 if cap
< _the_length
+ 1 then cap
= _the_length
+ 1
171 if cap
<= _capacity
then return
173 _last_accessed_key
= null
176 var new_array
= new NativeArray[nullable N
](cap
)
179 # clean the new array
186 if _the_length
== 0 then return
187 if _capacity
<= old_cap
then return
189 # Reput items in the array
190 var node
= _first_item
191 while node
!= null do
192 var index
= index_at
(node
._key
)
193 # Then store it in the array
194 var next
= new_array
[index
]
195 new_array
[index
] = node
196 node
._prev_in_bucklet
= null
197 node
._next_in_bucklet
= next
198 if next
!= null then next
._prev_in_bucklet
= node
199 node
= node
._next_item
204 private abstract class HashNode[K
]
207 var next_item
: nullable N
= null
208 var prev_item
: nullable N
= null
209 var prev_in_bucklet
: nullable N
= null
210 var next_in_bucklet
: nullable N
= null
213 # A `Map` implemented with a hash table.
216 # var map = new HashMap[nullable String, Int]
221 # assert map[null] == 0
222 # assert map["one"] == 1
223 # assert map.keys.has("two")
224 # assert map.values.length == 3
228 super HashCollection[K
]
230 redef type N
: HashMapNode[K
, V
] is fixed
236 return provide_default_value
(key
)
242 redef fun get_or_null
(key
)
252 redef fun iterator
: HashMapIterator[K
, V
] do return new HashMapIterator[K
,V
](self)
254 redef fun length
do return _the_length
256 redef fun is_empty
do return _the_length
== 0
258 redef fun []=(key
, v
)
260 if _capacity
== 0 then enlarge
(17) # 17 because magic in `store`
261 var i
= index_at
(key
)
262 var c
= node_at_idx
(i
, key
)
267 store
(i
, new HashMapNode[K
, V
](key
, v
))
271 redef fun clear
do raz
279 redef var keys
: RemovableCollection[K
] = new HashMapKeys[K
, V
](self) is lazy
280 redef var values
: RemovableCollection[V
] = new HashMapValues[K
, V
](self) is lazy
281 redef fun has_key
(k
) do return node_at
(k
) != null
284 # View of the keys of a HashMap
285 private class HashMapKeys[K
, V
]
286 super RemovableCollection[K
]
288 var map
: HashMap[K
, V
]
290 redef fun count
(k
) do if self.has
(k
) then return 1 else return 0
291 redef fun first
do return self.map
._first_item
._key
292 redef fun has
(k
) do return self.map
.node_at
(k
) != null
293 redef fun has_only
(k
) do return (self.has
(k
) and self.length
== 1) or self.is_empty
294 redef fun is_empty
do return self.map
.is_empty
295 redef fun length
do return self.map
.length
297 redef fun iterator
do return new MapKeysIterator[K
, V
](self.map
.iterator
)
299 redef fun clear
do self.map
.clear
301 redef fun remove
(key
) do self.map
.remove_node
(key
)
302 redef fun remove_all
(key
) do self.map
.remove_node
(key
)
305 # View of the values of a Map
306 private class HashMapValues[K
, V
]
307 super RemovableCollection[V
]
309 var map
: HashMap[K
, V
]
311 redef fun count
(item
)
314 var c
= self.map
._first_item
316 if c
._value
== item
then nb
+= 1
321 redef fun first
do return self.map
._first_item
._value
325 var c
= self.map
._first_item
327 if c
._value
== item
then return true
333 redef fun has_only
(item
)
335 var c
= self.map
._first_item
337 if c
._value
!= item
then return false
343 redef fun is_empty
do return self.map
.is_empty
344 redef fun length
do return self.map
.length
346 redef fun iterator
do return new MapValuesIterator[K
, V
](self.map
.iterator
)
348 redef fun clear
do self.map
.clear
350 redef fun remove
(item
)
353 var c
= map
._first_item
355 if c
._value
== item
then
356 map
.remove_node
(c
._key
)
363 redef fun remove_all
(item
)
366 var c
= map
._first_item
368 if c
._value
== item
then
369 map
.remove_node
(c
._key
)
376 private class HashMapNode[K
, V
]
378 redef type N
: HashMapNode[K
, V
]
382 # A `MapIterator` over a `HashMap`.
383 private class HashMapIterator[K
, V
]
384 super MapIterator[K
, V
]
385 redef fun is_ok
do return _node
!= null
393 #redef fun item=(value)
396 # _node.second = value
408 _node
= _node
._next_item
411 # The map to iterate on
412 var map
: HashMap[K
, V
]
415 var node
: nullable HashMapNode[K
, V
] = null
420 _node
= _map
._first_item
424 # A `Set` implemented with a hash table.
425 # Keys of such a map cannot be null and require a working `hash` method
428 super HashCollection[E
]
430 redef type N
: HashSetNode[E
] is fixed
432 redef fun length
do return _the_length
434 redef fun is_empty
do return _the_length
== 0
438 assert _the_length
> 0
439 return _first_item
._key
444 return node_at
(item
) != null
449 if _capacity
== 0 then enlarge
(17) # 17 because magic in `store`
450 var i
= index_at
(item
)
451 var c
= node_at_idx
(i
, item
)
455 store
(i
,new HashSetNode[E
](item
))
459 redef fun remove
(item
) do remove_node
(item
)
461 redef fun clear
do raz
463 redef fun iterator
do return new HashSetIterator[E
](self)
471 # Build a list filled with the items of `coll`.
472 init from
(coll
: Collection[E
]) do
477 redef fun new_set
do return new HashSet[E
]
480 private class HashSetNode[E
]
482 redef type N
: HashSetNode[E
]
485 private class HashSetIterator[E
]
487 redef fun is_ok
do return _node
!= null
498 _node
= _node
._next_item
501 # The set to iterate on
504 # The position in the internal map storage
505 var node
: nullable HashSetNode[E
] = null
509 _node
= _set
._first_item