0c772b8745c0eaaf65db98dcfe2884718eb94ce9
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 package hash_collection
19 # A HashCollection is an array of HashNode[K] indexed by the K hash value
20 private abstract class HashCollection[K
: Object, N
: HashNode[Object]]
21 super ArrayCapable[nullable N
]
23 var _array
: nullable NativeArray[nullable N
] = null # Used to store items
24 var _capacity
: Int = 0 # Size of _array
25 var _length
: Int = 0 # Number of items in the map
27 readable var _first_item
: nullable N
= null # First added item (used to visit items in nice order)
28 var _last_item
: nullable N
= null # Last added item (same)
30 # The last key accessed (used for cache)
31 var _last_accessed_key
: nullable K
= null
33 # The last node accessed (used for cache)
34 var _last_accessed_node
: nullable N
= null
36 # Return the index of the key k
37 fun index_at
(k
: K
): Int
39 var i
= k
.hash
% _capacity
44 # Return the node assosiated with the key
45 fun node_at
(k
: K
): nullable N
47 # cache: `is' is used instead of `==' because it is a faster filter (even if not exact)
48 if k
is _last_accessed_key
then return _last_accessed_node
50 var res
= node_at_idx
(index_at
(k
), k
)
51 _last_accessed_key
= k
52 _last_accessed_node
= res
56 # Return the node assosiated with the key (but with the index already known)
57 fun node_at_idx
(i
: Int, k
: K
): nullable N
62 if ck
is k
or ck
== k
then # prefilter with `is' because the compiler is not smart enought yet
65 c
= c
._next_in_bucklet
70 # Add a new node at a given index
71 fun store
(index
: Int, node
: N
)
73 # Store the item in the list
74 if _first_item
== null then
77 _last_item
._next_item
= node
79 node
._prev_item
= _last_item
80 node
._next_item
= null
83 # Then store it in the array
84 var next
= _array
[index
]
86 node
._next_in_bucklet
= next
87 if next
!= null then next
._prev_in_bucklet
= node
89 _last_accessed_key
= node
._key
90 _last_accessed_node
= node
96 if l
>= _capacity
then
101 # Remove the node assosiated with the key
102 fun remove_node
(k
: K
)
105 var node
= node_at_idx
(i
, k
)
106 if node
== null then return
108 # Remove the item in the list
109 var prev
= node
._prev_item
110 var next
= node
._next_item
112 prev
._next_item
= next
117 next
._prev_item
= prev
122 # Remove the item in the array
124 prev
= node
._prev_in_bucklet
125 next
= node
._next_in_bucklet
127 prev
._next_in_bucklet
= next
132 next
._prev_in_bucklet
= prev
135 _last_accessed_key
= null
138 # Clear the whole structure
141 var i
= _capacity
- 1
149 _last_accessed_key
= null
153 fun enlarge
(cap
: Int)
155 var old_cap
= _capacity
157 if cap
< _length
+ 1 then cap
= _length
+ 1
158 if cap
<= _capacity
then return
160 _last_accessed_key
= null
163 var new_array
= calloc_array
(cap
)
166 # clean the new array
173 if _capacity
<= old_cap
then return
175 # Reput items in the array
176 var node
= _first_item
177 while node
!= null do
178 var index
= index_at
(node
._key
)
179 # Then store it in the array
180 var next
= new_array
[index
]
181 new_array
[index
] = node
182 node
._next_in_bucklet
= next
183 if next
!= null then next
._prev_in_bucklet
= node
184 node
= node
._next_item
189 private abstract class HashNode[K
: Object]
192 readable writable var _next_item
: nullable N
= null
193 readable writable var _prev_item
: nullable N
= null
194 var _prev_in_bucklet
: nullable N
= null
195 var _next_in_bucklet
: nullable N
= null
202 # A map implemented with a hash table.
203 # Keys of such a map cannot be null and require a working `hash' method
204 class HashMap[K
: Object, V
]
206 super HashCollection[K
, HashMapNode[K
, V
]]
218 redef fun iterator
: HashMapIterator[K
, V
] do return new HashMapIterator[K
,V
](self)
225 each
(c
._key
, c
._value
)
230 redef fun length
do return _length
232 redef fun is_empty
do return _length
== 0
234 redef fun []=(key
, v
)
236 var i
= index_at
(key
)
237 var c
= node_at_idx
(i
, key
)
242 store
(i
, new HashMapNode[K
, V
](key
, v
))
246 redef fun clear
do raz
255 redef var keys
: HashMapKeys[K
, V
] = new HashMapKeys[K
, V
](self)
256 redef var values
: HashMapValues[K
, V
] = new HashMapValues[K
, V
](self)
259 # View of the keys of a HashMap
260 class HashMapKeys[K
: Object, V
]
261 super RemovableCollection[K
]
263 var map
: HashMap[K
, V
]
265 redef fun count
(k
) do if self.has
(k
) then return 1 else return 0
266 redef fun first
do return self.map
._first_item
._key
267 redef fun has
(k
) do return self.map
.node_at
(k
) != null
268 redef fun has_only
(k
) do return (self.has
(k
) and self.length
== 1) or self.is_empty
269 redef fun is_empty
do return self.map
.is_empty
270 redef fun length
do return self.map
.length
272 redef fun iterator
do return new MapKeysIterator[K
, V
](self.map
.iterator
)
274 redef fun clear
do self.map
.clear
276 redef fun remove
(key
) do self.map
.remove_node
(key
)
277 redef fun remove_all
(key
) do self.map
.remove_node
(key
)
280 # View of the values of a Map
281 class HashMapValues[K
: Object, V
]
282 super RemovableCollection[V
]
284 var map
: HashMap[K
, V
]
286 redef fun count
(item
)
289 var c
= self.map
._first_item
291 if c
._value
== item
then nb
+= 1
296 redef fun first
do return self.map
._first_item
._value
300 var c
= self.map
._first_item
302 if c
._value
== item
then return true
308 redef fun has_only
(item
)
310 var c
= self.map
._first_item
312 if c
._value
!= item
then return false
318 redef fun is_empty
do return self.map
.is_empty
319 redef fun length
do return self.map
.length
321 redef fun iterator
do return new MapValuesIterator[K
, V
](self.map
.iterator
)
323 redef fun clear
do self.map
.clear
325 redef fun remove
(item
)
328 var c
= map
._first_item
330 if c
._value
== item
then
331 map
.remove_node
(c
._key
)
338 redef fun remove_all
(item
)
341 var c
= map
._first_item
343 if c
._value
== item
then
344 map
.remove_node
(c
._key
)
351 private class HashMapNode[K
: Object, V
]
353 redef type N
: HashMapNode[K
, V
]
363 class HashMapIterator[K
: Object, 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 var _map
: HashMap[K
, V
]
395 var _node
: nullable HashMapNode[K
, V
]
397 init(map
: HashMap[K
, V
])
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
, HashSetNode[E
]]
410 redef fun length
do return _length
412 redef fun is_empty
do return _length
== 0
417 return _first_item
._key
422 return node_at
(item
) != null
427 var i
= index_at
(item
)
428 var c
= node_at_idx
(i
, item
)
432 store
(i
,new HashSetNode[E
](item
))
436 redef fun remove
(item
) do remove_node
(item
)
438 redef fun clear
do raz
440 redef fun iterator
do return new HashSetIterator[E
](self)
450 private class HashSetNode[E
: Object]
452 redef type N
: HashSetNode[E
]
460 class HashSetIterator[E
: Object]
462 redef fun is_ok
do return _node
!= null
473 _node
= _node
._next_item
476 # The set to iterate on
479 # The position in the internal map storage
480 var _node
: nullable HashSetNode[E
]
482 init(set
: HashSet[E
])
485 _node
= set
._first_item