# You are allowed to redistribute it and sell it, alone or is a part of
# another product.
-# Introduce Hashmap and Hashset.
+# Introduce `HashMap` and `HashSet`.
module hash_collection
import array
+redef class Map[K, V]
+ # Get a `HashMap[K, V]` as default implementation
+ new do return new HashMap[K, V]
+end
+
# A HashCollection is an array of HashNode[K] indexed by the K hash value
-private abstract class HashCollection[K: Object, N: HashNode[Object]]
- super ArrayCapable[nullable N]
+private abstract class HashCollection[K]
+ type N: HashNode[K]
var array: nullable NativeArray[nullable N] = null # Used to store items
var capacity: Int = 0 # Size of _array
var last_item: nullable N = null # Last added item (same)
# The last key accessed (used for cache)
- var last_accessed_key: nullable K = null
+ var last_accessed_key: nullable Object = null
# The last node accessed (used for cache)
var last_accessed_node: nullable N = null
# Return the index of the key k
- fun index_at(k: K): Int
+ fun index_at(k: nullable Object): Int
do
+ if k == null then return 0
+
var i = k.hash % _capacity
if i < 0 then i = - i
return i
end
- # Return the node assosiated with the key
- fun node_at(k: K): nullable N
+ # Return the node associated with the key
+ fun node_at(k: nullable Object): nullable N
do
# 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
return res
end
- # Return the node assosiated with the key (but with the index already known)
- fun node_at_idx(i: Int, k: K): nullable N
+ # Return the node associated with the key (but with the index already known)
+ fun node_at_idx(i: Int, k: nullable Object): nullable N
do
var c = _array[i]
while c != null do
end
# Remove the node assosiated with the key
- fun remove_node(k: K)
+ fun remove_node(k: nullable Object)
do
var i = index_at(k)
var node = node_at_idx(i, k)
_last_accessed_key = null
# get a new array
- var new_array = calloc_array(cap)
+ var new_array = new NativeArray[nullable N](cap)
_array = new_array
# clean the new array
end
end
-private abstract class HashNode[K: Object]
+private abstract class HashNode[K]
var key: K
type N: HashNode[K]
var next_item: nullable N = null
var next_in_bucklet: nullable N = null
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]
+# A `Map` implemented with a hash table.
+#
+# ~~~
+# var map = new HashMap[nullable String, Int]
+# map[null] = 0
+# map["one"] = 1
+# map["two"] = 2
+#
+# assert map[null] == 0
+# assert map["one"] == 1
+# assert map.keys.has("two")
+# assert map.values.length == 3
+# ~~~
+class HashMap[K, V]
super Map[K, V]
- super HashCollection[K, HashMapNode[K, V]]
+ super HashCollection[K]
+
+ redef type N: HashMapNode[K, V] is fixed
redef fun [](key)
do
end
end
+ redef fun get_or_null(key)
+ do
+ var c = node_at(key)
+ if c == null then
+ return null
+ else
+ return c._value
+ end
+ end
+
redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
redef fun length do return _the_length
enlarge(0)
end
- redef var keys: RemovableCollection[K] = new HashMapKeys[K, V](self)
- redef var values: RemovableCollection[V] = new HashMapValues[K, V](self)
+ redef var keys: RemovableCollection[K] = new HashMapKeys[K, V](self) is lazy
+ redef var values: RemovableCollection[V] = new HashMapValues[K, V](self) is lazy
+ redef fun has_key(k) do return node_at(k) != null
end
# View of the keys of a HashMap
-private class HashMapKeys[K: Object, V]
+private class HashMapKeys[K, V]
super RemovableCollection[K]
# The original map
var map: HashMap[K, V]
end
# View of the values of a Map
-private class HashMapValues[K: Object, V]
+private class HashMapValues[K, V]
super RemovableCollection[V]
# The original map
var map: HashMap[K, V]
end
end
-private class HashMapNode[K: Object, V]
+private class HashMapNode[K, V]
super HashNode[K]
redef type N: HashMapNode[K, V]
var value: V
end
# A `MapIterator` over a `HashMap`.
-class HashMapIterator[K: Object, V]
+class HashMapIterator[K, V]
super MapIterator[K, V]
redef fun is_ok do return _node != null
# 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]
+class HashSet[E]
super Set[E]
- super HashCollection[E, HashSetNode[E]]
+ super HashCollection[E]
+
+ redef type N: HashSetNode[E] is fixed
redef fun length do return _the_length
redef fun new_set do return new HashSet[E]
end
-private class HashSetNode[E: Object]
+private class HashSetNode[E]
super HashNode[E]
redef type N: HashSetNode[E]
end
-private class HashSetIterator[E: Object]
+private class HashSetIterator[E]
super Iterator[E]
redef fun is_ok do return _node != null
nitlanguage / nit.git / blobdiff