# another product.
# Introduce Hashmap and Hashset.
-package hash_collection
+module hash_collection
import array
-import hash
# A HashCollection is an array of HashNode[K] indexed by the K hash value
-private class HashCollection[K: Object, N: HashNode[K]]
+private abstract class HashCollection[K: Object, N: HashNode[Object]]
super ArrayCapable[nullable N]
+
var _array: nullable NativeArray[nullable N] = null # Used to store items
var _capacity: Int = 0 # Size of _array
var _length: Int = 0 # Number of items in the map
- readable var _first_item: nullable N = null # First added item (used to visit items in nice order)
+ var _first_item: nullable N = null # First added item (used to visit items in nice order)
var _last_item: nullable N = null # Last added item (same)
# The last key accessed (used for cache)
# Return the node assosiated with the key
fun node_at(k: K): nullable N
do
- # cache: `is' is used instead of `==' because it is a faster filter (even if not exact)
- if k is _last_accessed_key then return _last_accessed_node
+ # cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
+ if k.is_same_instance(_last_accessed_key) then return _last_accessed_node
var res = node_at_idx(index_at(k), k)
_last_accessed_key = k
var c = _array[i]
while c != null do
var ck = c._key
- if ck is k or ck == k then # prefilter with `is' because the compiler is not smart enought yet
+ if ck.is_same_instance(k) or ck == k then # FIXME prefilter because the compiler is not smart enought yet
break
end
c = c._next_in_bucklet
_last_accessed_key = null
end
+ # Clear the whole structure
fun raz
do
var i = _capacity - 1
_last_accessed_key = null
end
+ # Force a capacity
fun enlarge(cap: Int)
do
var old_cap = _capacity
# Then store it in the array
var next = new_array[index]
new_array[index] = node
+ node._prev_in_bucklet = null
node._next_in_bucklet = next
if next != null then next._prev_in_bucklet = node
node = node._next_item
end
end
-private class HashNode[K: Object]
+private abstract class HashNode[K: Object]
var _key: K
type N: HashNode[K]
- readable writable var _next_item: nullable N = null
- readable writable var _prev_item: nullable N = null
+ var _next_item: nullable N = null
+ var _prev_item: nullable N = null
var _prev_in_bucklet: nullable N = null
var _next_in_bucklet: nullable N = null
init(k: K)
end
end
+# A map implemented with a hash table.
+# Keys of such a map cannot be null and require a working `hash` method
class HashMap[K: Object, V]
super Map[K, V]
super HashCollection[K, HashMapNode[K, V]]
do
var c = node_at(key)
if c == null then
- abort
+ return provide_default_value(key)
else
return c._value
end
redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
- redef fun iterate
- !each(k: K, v: V)
- do
- var c = _first_item
- while c != null do
- each(c._key, c._value)
- c = c._next_item
- end
- end
-
redef fun length do return _length
redef fun is_empty do return _length == 0
enlarge(0)
end
- redef var keys: HashMapKeys[K, V] = new HashMapKeys[K, V](self)
- redef var values: HashMapValues[K, V] = new HashMapValues[K, V](self)
+ redef var keys: RemovableCollection[K] = new HashMapKeys[K, V](self)
+ redef var values: RemovableCollection[V] = new HashMapValues[K, V](self)
end
-class HashMapKeys[K: Object, V]
+# View of the keys of a HashMap
+private class HashMapKeys[K: Object, V]
super RemovableCollection[K]
# The original map
var map: HashMap[K, V]
redef fun remove_all(key) do self.map.remove_node(key)
end
-class HashMapValues[K: Object, V]
+# View of the values of a Map
+private class HashMapValues[K: Object, V]
super RemovableCollection[V]
# The original map
var map: HashMap[K, V]
end
end
-class HashMapNode[K: Object, V]
+private class HashMapNode[K: Object, V]
super HashNode[K]
redef type N: HashMapNode[K, V]
var _value: V
init(map: HashMap[K, V])
do
_map = map
- _node = map.first_item
+ _node = map._first_item
end
end
+# A `Set` implemented with a hash table.
+# Keys of such a map cannot be null and require a working `hash` method
class HashSet[E: Object]
super Set[E]
super HashCollection[E, HashSetNode[E]]
_length = 0
enlarge(0)
end
+
+ # Build a list filled with the items of `coll`.
+ init from(coll: Collection[E]) do
+ init
+ add_all(coll)
+ end
+
+ redef fun new_set do return new HashSet[E]
end
-class HashSetNode[E: Object]
+private class HashSetNode[E: Object]
super HashNode[E]
redef type N: HashSetNode[E]
end
end
-class HashSetIterator[E: Object]
+private class HashSetIterator[E: Object]
super Iterator[E]
redef fun is_ok do return _node != null
nitlanguage / nit.git / blobdiff