# 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], E]
-special Collection[E]
-special ArrayCapable[nullable N]
+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
- redef readable var _length: Int = 0 # Number of items in the map
+ 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 _last_item: nullable N = null # Last added item (same)
# 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)
+ # 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
var res = node_at_idx(index_at(k), 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 k or ck == k then # prefilter with `is` 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
end
end
-private class HashNode[K]
+private abstract class HashNode[K: Object]
var _key: K
type N: HashNode[K]
readable writable var _next_item: nullable N = null
end
end
-class HashMap[K, V]
-special Map[K, V]
-special HashCollection[K, HashMapNode[K, V], V]
+# 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]]
redef fun [](key)
do
end
end
- redef fun has_key(key) do return node_at(key) != null
-
redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
- redef fun iterate
- !each(e: V)
+ redef fun length do return _length
+
+ redef fun is_empty do return _length == 0
+
+ redef fun []=(key, v)
do
- var c = _first_item
- while c != null do
- each(c._value)
- c = c._next_item
+ var i = index_at(key)
+ var c = node_at_idx(i, key)
+ if c != null then
+ c._key = key
+ c._value = v
+ else
+ store(i, new HashMapNode[K, V](key, v))
end
end
- redef fun first
+ redef fun clear do raz
+
+ init
do
- assert _length > 0
- return _first_item._value
+ _capacity = 0
+ _length = 0
+ enlarge(0)
end
- redef fun is_empty do return _length == 0
+ redef var keys: HashMapKeys[K, V] = new HashMapKeys[K, V](self)
+ redef var values: HashMapValues[K, V] = new HashMapValues[K, V](self)
+end
+
+# View of the keys of a HashMap
+class HashMapKeys[K: Object, V]
+ super RemovableCollection[K]
+ # The original map
+ var map: HashMap[K, V]
+
+ redef fun count(k) do if self.has(k) then return 1 else return 0
+ redef fun first do return self.map._first_item._key
+ redef fun has(k) do return self.map.node_at(k) != null
+ redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
+ redef fun is_empty do return self.map.is_empty
+ redef fun length do return self.map.length
+
+ redef fun iterator do return new MapKeysIterator[K, V](self.map.iterator)
+
+ redef fun clear do self.map.clear
+
+ redef fun remove(key) do self.map.remove_node(key)
+ redef fun remove_all(key) do self.map.remove_node(key)
+end
+
+# View of the values of a Map
+class HashMapValues[K: Object, V]
+ super RemovableCollection[V]
+ # The original map
+ var map: HashMap[K, V]
redef fun count(item)
do
var nb = 0
- var c = _first_item
+ var c = self.map._first_item
while c != null do
if c._value == item then nb += 1
c = c._next_item
end
return nb
end
+ redef fun first do return self.map._first_item._value
redef fun has(item)
do
- var c = _first_item
+ var c = self.map._first_item
while c != null do
if c._value == item then return true
c = c._next_item
redef fun has_only(item)
do
- var c = _first_item
+ var c = self.map._first_item
while c != null do
if c._value != item then return false
c = c._next_item
return true
end
- redef fun []=(key, v)
- do
- assert key != null
- var i = index_at(key)
- var c = node_at_idx(i, key)
- if c != null then
- c._key = key
- c._value = v
- else
- store(i, new HashMapNode[K, V](key, v))
- end
- end
+ redef fun is_empty do return self.map.is_empty
+ redef fun length do return self.map.length
+
+ redef fun iterator do return new MapValuesIterator[K, V](self.map.iterator)
+
+ redef fun clear do self.map.clear
redef fun remove(item)
do
- var c = _first_item
+ var map = self.map
+ var c = map._first_item
while c != null do
if c._value == item then
- remove_node(c._key)
+ map.remove_node(c._key)
return
end
c = c._next_item
end
end
- redef fun remove_at(key) do remove_node(key)
-
- redef fun clear do raz
-
- init
+ redef fun remove_all(item)
do
- _capacity = 0
- _length = 0
- enlarge(0)
+ var map = self.map
+ var c = map._first_item
+ while c != null do
+ if c._value == item then
+ map.remove_node(c._key)
+ end
+ c = c._next_item
+ end
end
end
-class HashMapNode[K, V]
-special HashNode[K]
+private class HashMapNode[K: Object, V]
+ super HashNode[K]
redef type N: HashMapNode[K, V]
var _value: V
end
end
-class HashMapIterator[K, V]
-special MapIterator[K, V]
+class HashMapIterator[K: Object, V]
+ super MapIterator[K, V]
redef fun is_ok do return _node != null
redef fun item
end
end
-class HashSet[E]
-special Set[E]
-special HashCollection[E, HashSetNode[E], E]
+# 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]]
+
+ redef fun length do return _length
redef fun is_empty do return _length == 0
_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
end
-class HashSetNode[E]
-special HashNode[E]
+private class HashSetNode[E: Object]
+ super HashNode[E]
redef type N: HashSetNode[E]
init(e: E)
end
end
-class HashSetIterator[E]
-special Iterator[E]
+class HashSetIterator[E: Object]
+ super Iterator[E]
redef fun is_ok do return _node != null
redef fun item
nitlanguage / nit.git / blobdiff