cae46fd0fb834737b72ff553682237ca24ef1daf
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
]
22 var array
: nullable NativeArray[nullable N
] = null # Used to store items
23 var capacity
: Int = 0 # Size of _array
24 var the_length
: Int = 0 # Number of items in the map
26 var first_item
: nullable N
= null # First added item (used to visit items in nice order)
27 var last_item
: nullable N
= null # Last added item (same)
29 # The last key accessed (used for cache)
30 var last_accessed_key
: nullable K
= null
32 # The last node accessed (used for cache)
33 var last_accessed_node
: nullable N
= null
35 # Return the index of the key k
36 fun index_at
(k
: K
): Int
38 if k
== null then return 0
40 var i
= k
.hash
% _capacity
45 # Return the node associated with the key
46 fun node_at
(k
: K
): nullable N
48 # cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
49 if k
.is_same_instance
(_last_accessed_key
) then return _last_accessed_node
51 var res
= node_at_idx
(index_at
(k
), k
)
52 _last_accessed_key
= k
53 _last_accessed_node
= res
57 # Return the node associated with the key (but with the index already known)
58 fun node_at_idx
(i
: Int, k
: K
): nullable N
63 if ck
.is_same_instance
(k
) or ck
== k
then # FIXME prefilter because the compiler is not smart enought yet
66 c
= c
._next_in_bucklet
71 # Add a new node at a given index
72 fun store
(index
: Int, node
: N
)
74 # Store the item in the list
75 if _first_item
== null then
78 _last_item
._next_item
= node
80 node
._prev_item
= _last_item
81 node
._next_item
= null
84 # Then store it in the array
85 var next
= _array
[index
]
87 node
._next_in_bucklet
= next
88 if next
!= null then next
._prev_in_bucklet
= node
90 _last_accessed_key
= node
._key
91 _last_accessed_node
= node
97 # Magic values determined empirically
98 # We do not want to enlarge too much
99 # We also want a odd capacity so that the modulo is more distributive
101 if l
>= _capacity
then
102 enlarge
(l
* 3 / 2 + 1)
106 # Remove the node assosiated with the key
107 fun remove_node
(k
: K
)
110 var node
= node_at_idx
(i
, k
)
111 if node
== null then return
113 # Remove the item in the list
114 var prev
= node
._prev_item
115 var next
= node
._next_item
117 prev
._next_item
= next
122 next
._prev_item
= prev
127 # Remove the item in the array
129 prev
= node
._prev_in_bucklet
130 next
= node
._next_in_bucklet
132 prev
._next_in_bucklet
= next
137 next
._prev_in_bucklet
= prev
140 _last_accessed_key
= null
143 # Clear the whole structure
146 var i
= _capacity
- 1
154 _last_accessed_key
= null
158 fun enlarge
(cap
: Int)
160 var old_cap
= _capacity
162 if cap
< _the_length
+ 1 then cap
= _the_length
+ 1
163 if cap
<= _capacity
then return
165 _last_accessed_key
= null
168 var new_array
= new NativeArray[nullable N
](cap
)
171 # clean the new array
178 if _capacity
<= old_cap
then return
180 # Reput items in the array
181 var node
= _first_item
182 while node
!= null do
183 var index
= index_at
(node
._key
)
184 # Then store it in the array
185 var next
= new_array
[index
]
186 new_array
[index
] = node
187 node
._prev_in_bucklet
= null
188 node
._next_in_bucklet
= next
189 if next
!= null then next
._prev_in_bucklet
= node
190 node
= node
._next_item
195 private abstract class HashNode[K
]
198 var next_item
: nullable N
= null
199 var prev_item
: nullable N
= null
200 var prev_in_bucklet
: nullable N
= null
201 var next_in_bucklet
: nullable N
= null
204 # A `Map` implemented with a hash table.
207 # var map = new HashMap[nullable String, Int]
212 # assert map[null] == 0
213 # assert map["one"] == 1
214 # assert map.keys.has("two")
215 # assert map.values.length == 3
219 super HashCollection[K
]
221 redef type N
: HashMapNode[K
, V
] is fixed
227 return provide_default_value
(key
)
233 redef fun iterator
: HashMapIterator[K
, V
] do return new HashMapIterator[K
,V
](self)
235 redef fun length
do return _the_length
237 redef fun is_empty
do return _the_length
== 0
239 redef fun []=(key
, v
)
241 var i
= index_at
(key
)
242 var c
= node_at_idx
(i
, key
)
247 store
(i
, new HashMapNode[K
, V
](key
, v
))
251 redef fun clear
do raz
260 redef var keys
: RemovableCollection[K
] = new HashMapKeys[K
, V
](self)
261 redef var values
: RemovableCollection[V
] = new HashMapValues[K
, V
](self)
264 # View of the keys of a HashMap
265 private class HashMapKeys[K
, V
]
266 super RemovableCollection[K
]
268 var map
: HashMap[K
, V
]
270 redef fun count
(k
) do if self.has
(k
) then return 1 else return 0
271 redef fun first
do return self.map
._first_item
._key
272 redef fun has
(k
) do return self.map
.node_at
(k
) != null
273 redef fun has_only
(k
) do return (self.has
(k
) and self.length
== 1) or self.is_empty
274 redef fun is_empty
do return self.map
.is_empty
275 redef fun length
do return self.map
.length
277 redef fun iterator
do return new MapKeysIterator[K
, V
](self.map
.iterator
)
279 redef fun clear
do self.map
.clear
281 redef fun remove
(key
) do self.map
.remove_node
(key
)
282 redef fun remove_all
(key
) do self.map
.remove_node
(key
)
285 # View of the values of a Map
286 private class HashMapValues[K
, V
]
287 super RemovableCollection[V
]
289 var map
: HashMap[K
, V
]
291 redef fun count
(item
)
294 var c
= self.map
._first_item
296 if c
._value
== item
then nb
+= 1
301 redef fun first
do return self.map
._first_item
._value
305 var c
= self.map
._first_item
307 if c
._value
== item
then return true
313 redef fun has_only
(item
)
315 var c
= self.map
._first_item
317 if c
._value
!= item
then return false
323 redef fun is_empty
do return self.map
.is_empty
324 redef fun length
do return self.map
.length
326 redef fun iterator
do return new MapValuesIterator[K
, V
](self.map
.iterator
)
328 redef fun clear
do self.map
.clear
330 redef fun remove
(item
)
333 var c
= map
._first_item
335 if c
._value
== item
then
336 map
.remove_node
(c
._key
)
343 redef fun remove_all
(item
)
346 var c
= map
._first_item
348 if c
._value
== item
then
349 map
.remove_node
(c
._key
)
356 private class HashMapNode[K
, V
]
358 redef type N
: HashMapNode[K
, V
]
362 # A `MapIterator` over a `HashMap`.
363 class HashMapIterator[K
, V
]
364 super MapIterator[K
, V
]
365 redef fun is_ok
do return _node
!= null
373 #redef fun item=(value)
376 # _node.second = value
388 _node
= _node
._next_item
391 # The map to iterate on
392 private var map
: HashMap[K
, V
]
395 private var node
: nullable HashMapNode[K
, V
] = null
400 _node
= _map
._first_item
404 # A `Set` implemented with a hash table.
405 # Keys of such a map cannot be null and require a working `hash` method
406 class HashSet[E
: Object]
408 super HashCollection[E
]
410 redef type N
: HashSetNode[E
] is fixed
412 redef fun length
do return _the_length
414 redef fun is_empty
do return _the_length
== 0
418 assert _the_length
> 0
419 return _first_item
._key
424 return node_at
(item
) != null
429 var i
= index_at
(item
)
430 var c
= node_at_idx
(i
, item
)
434 store
(i
,new HashSetNode[E
](item
))
438 redef fun remove
(item
) do remove_node
(item
)
440 redef fun clear
do raz
442 redef fun iterator
do return new HashSetIterator[E
](self)
451 # Build a list filled with the items of `coll`.
452 init from
(coll
: Collection[E
]) do
457 redef fun new_set
do return new HashSet[E
]
460 private class HashSetNode[E
: Object]
462 redef type N
: HashSetNode[E
]
465 private class HashSetIterator[E
: Object]
467 redef fun is_ok
do return _node
!= null
478 _node
= _node
._next_item
481 # The set to iterate on
484 # The position in the internal map storage
485 var node
: nullable HashSetNode[E
] = null
489 _node
= _set
._first_item