import array
# 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 _length: Int = 0 # Number of items in the map
+ var array: nullable NativeArray[nullable N] = null # Used to store items
+ var capacity: Int = 0 # Size of _array
+ var the_length: Int = 0 # Number of items in the map
- 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)
+ 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)
- var _last_accessed_key: nullable K = null
+ var last_accessed_key: nullable K = null
# The last node accessed (used for cache)
- var _last_accessed_node: nullable N = null
+ var last_accessed_node: nullable N = null
# Return the index of the key k
fun index_at(k: K): 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
+ # Return the node associated 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)
return res
end
- # Return the node assosiated with the key (but with the index already known)
+ # Return the node associated with the key (but with the index already known)
fun node_at_idx(i: Int, k: K): nullable N
do
var c = _array[i]
_last_accessed_node = node
# Enlarge if needed
- var l = _length
- _length = l + 1
- l = (l + 5) * 3 / 2
+ var l = _the_length
+ _the_length = l + 1
+
+ # Magic values determined empirically
+ # We do not want to enlarge too much
+ # We also want a odd capacity so that the modulo is more distributive
+ l = (l + 5) * 2 + 1
if l >= _capacity then
- enlarge(l * 2)
+ enlarge(l * 3 / 2 + 1)
end
end
end
# Remove the item in the array
- _length -= 1
+ _the_length -= 1
prev = node._prev_in_bucklet
next = node._next_in_bucklet
if prev != null then
_array[i] = null
i -= 1
end
- _length = 0
+ _the_length = 0
_first_item = null
_last_item = null
_last_accessed_key = null
do
var old_cap = _capacity
# get a new capacity
- if cap < _length + 1 then cap = _length + 1
+ if cap < _the_length + 1 then cap = _the_length + 1
if cap <= _capacity then return
_capacity = cap
_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]
- var _key: K
+private abstract class HashNode[K]
+ var key: K
type N: HashNode[K]
- 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)
- do
- _key = k
- end
+ 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
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
redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
- redef fun length do return _length
+ redef fun length do return _the_length
- redef fun is_empty do return _length == 0
+ redef fun is_empty do return _the_length == 0
redef fun []=(key, v)
do
init
do
_capacity = 0
- _length = 0
+ _the_length = 0
enlarge(0)
end
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
-
- init(k: K, v: V)
- do
- super(k)
- _value = v
- end
+ var value: V
end
-class HashMapIterator[K: Object, V]
+# A `MapIterator` over a `HashMap`.
+class HashMapIterator[K, V]
super MapIterator[K, V]
redef fun is_ok do return _node != null
end
# The map to iterate on
- var _map: HashMap[K, V]
+ private var map: HashMap[K, V]
# The current node
- var _node: nullable HashMapNode[K, V]
+ private var node: nullable HashMapNode[K, V] = null
- init(map: HashMap[K, V])
+ init
do
_map = map
- _node = map._first_item
+ _node = _map._first_item
end
end
# 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]]
+ super HashCollection[E]
+
+ redef type N: HashSetNode[E] is fixed
- redef fun length do return _length
+ redef fun length do return _the_length
- redef fun is_empty do return _length == 0
+ redef fun is_empty do return _the_length == 0
redef fun first
do
- assert _length > 0
+ assert _the_length > 0
return _first_item._key
end
init
do
_capacity = 0
- _length = 0
+ _the_length = 0
enlarge(0)
end
private class HashSetNode[E: Object]
super HashNode[E]
redef type N: HashSetNode[E]
-
- init(e: E)
- do
- _key = e
- end
end
private class HashSetIterator[E: Object]
end
# The set to iterate on
- var _set: HashSet[E]
+ var set: HashSet[E]
# The position in the internal map storage
- var _node: nullable HashSetNode[E]
+ var node: nullable HashSetNode[E] = null
- init(set: HashSet[E])
+ init
do
- _set = set
- _node = set._first_item
+ _node = _set._first_item
end
end
nitlanguage / nit.git / blobdiff