--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2004-2009 Jean Privat <jean@pryen.org>
+#
+# This file is free software, which comes along with NIT. This software is
+# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# PARTICULAR PURPOSE. You can modify it is you want, provided this header
+# is kept unaltered, and a notification of the changes is added.
+# You are allowed to redistribute it and sell it, alone or is a part of
+# another product.
+
+# Introduce Hashmap and Hashset.
+package 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]
+ 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
+
+ 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)
+
+ # The last index accessed
+ var _last_accessed_index: Int = -1
+
+ # The last key accessed
+ var _last_accessed_key: nullable K = null
+
+ # Return the index of the k element
+ fun index_at(k: K): Int
+ do
+ var arr = _array
+
+ # Fisrt step: look in the last indexed elt
+ if k == _last_accessed_key then return _last_accessed_index
+
+ # Compute the base position of the key
+ var base = k.hash % _capacity
+ if base < 0 then base = - base
+
+ # Look for the key in the array
+ var cur = base
+ while true do
+ var c = arr[cur]
+ if c == null or c.key == k then # REAL equals
+ _last_accessed_index = cur
+ _last_accessed_key = k
+ return cur
+ end
+ cur -= 1
+ if cur < 0 then cur = _capacity - 1
+ assert no_loop: cur != base
+ end
+ abort
+ end
+
+ # Add a new node (should be free)
+ fun store(index: Int, node: N)
+ do
+ # Store the item in the list
+ if _first_item == null then
+ _first_item = node
+ else
+ _last_item.next_item = node
+ end
+ node.prev_item = _last_item
+ node.next_item = null
+ _last_item = node
+ # Then store it in the array
+ assert _array[index] == null
+ _array[index] = node
+ var l = _length
+ _length = l + 1
+ l = (l + 5) * 150 / 100
+ if l >= _capacity then
+ enlarge(l * 2)
+ end
+ end
+
+ fun remove_index(i: Int)
+ do
+ assert correct_index: i >= 0 and i < _capacity
+ var node = _array[i]
+ assert has_couple: node != null
+ # Remove the item in the list
+ var prev = node.prev_item
+ var next = node.next_item
+ if prev != null then
+ prev.next_item = next
+ else
+ _first_item = next
+ end
+ if next != null then
+ next.prev_item = prev
+ else
+ _last_item = prev
+ end
+ # Remove the item in the array
+ _array[i] = null
+ _length -= 1
+ # Now replaces things before if needed
+ while true do
+ i -= 1
+ if i < 0 then
+ i = _capacity - 1
+ end
+ var n = _array[i]
+ if n == null then
+ return
+ end
+ var i2 = index_at(n.key)
+ if i != i2 then
+ _array[i] = null
+ assert _array[i2] == null
+ _array[i2] = n
+ end
+ end
+ end
+
+ fun raz
+ do
+ var i = _capacity - 1
+ while i >= 0 do
+ _array[i] = null
+ i -= 1
+ end
+ _length = 0
+ _first_item = null
+ _last_item = null
+ _last_accessed_key = null
+ end
+
+ fun enlarge(cap: Int)
+ do
+ var old_cap = _capacity
+ # get a new capacity
+ # cap = cap * 130 / 100 + 5 + 1000 # /
+ if cap < _length + 1 then cap = _length + 1
+ if cap <= _capacity then return
+ _capacity = cap
+ _last_accessed_key = null
+
+ # get a new array
+ var new_array = calloc_array(cap)
+ _array = new_array
+
+ # clean the new array
+ var i = cap - 1
+ while i >=0 do
+ new_array[i] = null
+ i -= 1
+ end
+
+ if _capacity <= old_cap then return
+
+ var new_array = _array
+ # Reput items in the array
+ var node = _first_item
+ while node != null do
+ var ind = index_at(node.key)
+ assert new_array[ind] == null
+ new_array[ind] = node
+ node = node.next_item
+ end
+ _last_accessed_key = null
+ end
+end
+
+private class HashNode[K]
+ fun key: K is abstract
+ type N: HashNode[K]
+ readable writable var _next_item: nullable N = null
+ readable writable var _prev_item: nullable N = null
+end
+
+class HashMap[K, V]
+special CoupleMap[K, V]
+special HashCollection[K, HashMapNode[K, V], V]
+
+ redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
+
+ redef fun first
+ do
+ assert _length > 0
+ return _first_item.second
+ end
+
+ redef fun is_empty do return _length == 0
+
+ redef fun count(item)
+ do
+ var nb = 0
+ var i = 0
+ while i < _capacity do
+ var c = _array[i]
+ if c != null and c.second == item then nb += 1
+ i += 1
+ end
+ return nb
+ end
+
+ redef fun has(item)
+ do
+ var i = 0
+ while i < _capacity do
+ var c = _array[i]
+ if c != null and c.second == item then return true
+ i += 1
+ end
+ return false
+ end
+
+ redef fun has_only(item)
+ do
+ var i = 0
+ while i < _capacity do
+ var c = _array[i]
+ if c != null and c.second != item then return false
+ i += 1
+ end
+ return true
+ end
+
+ redef fun []=(key, v)
+ do
+ assert key != null
+ var i = index_at(key)
+ var c = _array[i]
+ if c != null then
+ c.first = key
+ c.second = v
+ else
+ store(i, new HashMapNode[K, V](key, v))
+ end
+ end
+
+ redef fun remove(item)
+ do
+ var i = 0
+ while i < _capacity do
+ var c = _array[i]
+ if c != null and c.second == item then
+ remove_index(i)
+ return
+ end
+ i += 1
+ end
+ end
+
+ redef fun remove_at(key) do remove_index(index_at(key))
+
+ redef fun clear do raz
+
+ redef fun couple_at(key) do return _array[index_at(key)]
+
+ init
+ do
+ _capacity = 0
+ _length = 0
+ enlarge(0)
+ end
+end
+
+class HashMapNode[K, V]
+special Couple[K, V]
+special HashNode[K]
+ redef fun key do return first
+ redef type N: HashMapNode[K, V]
+
+ init(k: K, v: V)
+ do
+ first = k
+ second = v
+ end
+end
+
+class HashMapIterator[K, V]
+special MapIterator[K, V]
+ redef fun is_ok do return _node != null
+
+ redef fun item
+ do
+ assert is_ok
+ return _node.second
+ end
+
+ #redef fun item=(value)
+ #do
+ # assert is_ok
+ # _node.second = value
+ #end
+
+ redef fun key
+ do
+ assert is_ok
+ return _node.first
+ end
+
+ redef fun next
+ do
+ assert is_ok
+ _node = _node.next_item
+ end
+
+ # The map to iterate on
+ var _map: HashMap[K, V]
+
+ # The current node
+ var _node: nullable HashMapNode[K, V]
+
+ init(map: HashMap[K, V])
+ do
+ _map = map
+ _node = map.first_item
+ end
+end
+
+class HashSet[E]
+special Set[E]
+special HashCollection[E, HashSetNode[E], E]
+
+ redef fun is_empty do return _length == 0
+
+ redef fun first
+ do
+ assert _length > 0
+ return _first_item.key
+ end
+
+ redef fun has(item)
+ do
+ return _array[index_at(item)] != null
+ end
+
+ redef fun add(item)
+ do
+ var i = index_at(item)
+ var c = _array[i]
+ if c != null then
+ c.key = item
+ else
+ store(i,new HashSetNode[E](item))
+ end
+ end
+
+ redef fun remove(item) do remove_index(index_at(item))
+
+ redef fun clear do raz
+
+ redef fun iterator do return new HashSetIterator[E](self)
+
+ init
+ do
+ _capacity = 0
+ _length = 0
+ enlarge(0)
+ end
+end
+
+class HashSetNode[E]
+special HashNode[E]
+ redef type N: HashSetNode[E]
+
+ redef readable writable var _key: E
+
+ init(e: E)
+ do
+ _key = e
+ end
+end
+
+class HashSetIterator[E]
+special Iterator[E]
+ redef fun is_ok do return _node != null
+
+ redef fun item
+ do
+ assert is_ok
+ return _node.key
+ end
+
+ redef fun next
+ do
+ assert is_ok
+ _node = _node.next_item
+ end
+
+ # The set to iterate on
+ var _set: HashSet[E]
+
+ # The position in the internal map storage
+ var _node: nullable HashSetNode[E]
+
+ init(set: HashSet[E])
+ do
+ _set = set
+ _node = set.first_item
+ end
+end
+
# This module is about hashable things.
# It introduces an hash funtion in objects.
-# It also introduces two classes, an Hashmap and an Hashset.
package hash
-intrude import string
+import kernel
redef class Object
# The hash code of the object.
fun hash: Int do return object_id / 8
end
-redef class String
- redef fun hash
- do
- # djb2 hash algorythm
- var h = 5381
- var i = _length - 1
- var it = _items
- while i >= 0 do
- h = (h * 32) + h + it[i].ascii
- i -= 1
- end
- return h
-
- end
-end
-
redef class Int
redef fun hash do return self
end
end
end
-# 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]
- 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
-
- 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)
-
- # The last index accessed
- var _last_accessed_index: Int = -1
-
- # The last key accessed
- var _last_accessed_key: nullable K = null
-
- # Return the index of the k element
- fun index_at(k: K): Int
- do
- var arr = _array
-
- # Fisrt step: look in the last indexed elt
- if k == _last_accessed_key then return _last_accessed_index
-
- # Compute the base position of the key
- var base = k.hash % _capacity
- if base < 0 then base = - base
-
- # Look for the key in the array
- var cur = base
- while true do
- var c = arr[cur]
- if c == null or c.key == k then # REAL equals
- _last_accessed_index = cur
- _last_accessed_key = k
- return cur
- end
- cur -= 1
- if cur < 0 then cur = _capacity - 1
- assert no_loop: cur != base
- end
- abort
- end
-
- # Add a new node (should be free)
- fun store(index: Int, node: N)
- do
- # Store the item in the list
- if _first_item == null then
- _first_item = node
- else
- _last_item.next_item = node
- end
- node.prev_item = _last_item
- node.next_item = null
- _last_item = node
- # Then store it in the array
- assert _array[index] == null
- _array[index] = node
- var l = _length
- _length = l + 1
- l = (l + 5) * 150 / 100
- if l >= _capacity then
- enlarge(l * 2)
- end
- end
-
- fun remove_index(i: Int)
- do
- assert correct_index: i >= 0 and i < _capacity
- var node = _array[i]
- assert has_couple: node != null
- # Remove the item in the list
- var prev = node.prev_item
- var next = node.next_item
- if prev != null then
- prev.next_item = next
- else
- _first_item = next
- end
- if next != null then
- next.prev_item = prev
- else
- _last_item = prev
- end
- # Remove the item in the array
- _array[i] = null
- _length -= 1
- # Now replaces things before if needed
- while true do
- i -= 1
- if i < 0 then
- i = _capacity - 1
- end
- var n = _array[i]
- if n == null then
- return
- end
- var i2 = index_at(n.key)
- if i != i2 then
- _array[i] = null
- assert _array[i2] == null
- _array[i2] = n
- end
- end
- end
-
- fun raz
- do
- var i = _capacity - 1
- while i >= 0 do
- _array[i] = null
- i -= 1
- end
- _length = 0
- _first_item = null
- _last_item = null
- _last_accessed_key = null
- end
-
- fun enlarge(cap: Int)
- do
- var old_cap = _capacity
- # get a new capacity
- # cap = cap * 130 / 100 + 5 + 1000 # /
- if cap < _length + 1 then cap = _length + 1
- if cap <= _capacity then return
- _capacity = cap
- _last_accessed_key = null
-
- # get a new array
- var new_array = calloc_array(cap)
- _array = new_array
-
- # clean the new array
- var i = cap - 1
- while i >=0 do
- new_array[i] = null
- i -= 1
- end
-
- if _capacity <= old_cap then return
-
- var new_array = _array
- # Reput items in the array
- var node = _first_item
- while node != null do
- var ind = index_at(node.key)
- assert new_array[ind] == null
- new_array[ind] = node
- node = node.next_item
- end
- _last_accessed_key = null
- end
-end
-
-private class HashNode[K]
- fun key: K is abstract
- type N: HashNode[K]
- readable writable var _next_item: nullable N = null
- readable writable var _prev_item: nullable N = null
-end
-
-class HashMap[K, V]
-special CoupleMap[K, V]
-special HashCollection[K, HashMapNode[K, V], V]
-
- redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
-
- redef fun first
- do
- assert _length > 0
- return _first_item.second
- end
-
- redef fun is_empty do return _length == 0
-
- redef fun count(item)
- do
- var nb = 0
- var i = 0
- while i < _capacity do
- var c = _array[i]
- if c != null and c.second == item then nb += 1
- i += 1
- end
- return nb
- end
-
- redef fun has(item)
- do
- var i = 0
- while i < _capacity do
- var c = _array[i]
- if c != null and c.second == item then return true
- i += 1
- end
- return false
- end
-
- redef fun has_only(item)
- do
- var i = 0
- while i < _capacity do
- var c = _array[i]
- if c != null and c.second != item then return false
- i += 1
- end
- return true
- end
-
- redef fun []=(key, v)
- do
- assert key != null
- var i = index_at(key)
- var c = _array[i]
- if c != null then
- c.first = key
- c.second = v
- else
- store(i, new HashMapNode[K, V](key, v))
- end
- end
-
- redef fun remove(item)
- do
- var i = 0
- while i < _capacity do
- var c = _array[i]
- if c != null and c.second == item then
- remove_index(i)
- return
- end
- i += 1
- end
- end
-
- redef fun remove_at(key) do remove_index(index_at(key))
-
- redef fun clear do raz
-
- redef fun couple_at(key) do return _array[index_at(key)]
-
- init
- do
- _capacity = 0
- _length = 0
- enlarge(0)
- end
-end
-
-class HashMapNode[K, V]
-special Couple[K, V]
-special HashNode[K]
- redef fun key do return first
- redef type N: HashMapNode[K, V]
-
- init(k: K, v: V)
- do
- first = k
- second = v
- end
-end
-
-class HashMapIterator[K, V]
-special MapIterator[K, V]
- redef fun is_ok do return _node != null
-
- redef fun item
- do
- assert is_ok
- return _node.second
- end
-
- #redef fun item=(value)
- #do
- # assert is_ok
- # _node.second = value
- #end
-
- redef fun key
- do
- assert is_ok
- return _node.first
- end
-
- redef fun next
- do
- assert is_ok
- _node = _node.next_item
- end
-
- # The map to iterate on
- var _map: HashMap[K, V]
-
- # The current node
- var _node: nullable HashMapNode[K, V]
-
- init(map: HashMap[K, V])
- do
- _map = map
- _node = map.first_item
- end
-end
-
-class HashSet[E]
-special Set[E]
-special HashCollection[E, HashSetNode[E], E]
-
- redef fun is_empty do return _length == 0
-
- redef fun first
- do
- assert _length > 0
- return _first_item.key
- end
-
- redef fun has(item)
- do
- return _array[index_at(item)] != null
- end
-
- redef fun add(item)
- do
- var i = index_at(item)
- var c = _array[i]
- if c != null then
- c.key = item
- else
- store(i,new HashSetNode[E](item))
- end
- end
-
- redef fun remove(item) do remove_index(index_at(item))
-
- redef fun clear do raz
-
- redef fun iterator do return new HashSetIterator[E](self)
-
- init
- do
- _capacity = 0
- _length = 0
- enlarge(0)
- end
-end
-
-class HashSetNode[E]
-special HashNode[E]
- redef type N: HashSetNode[E]
-
- redef readable writable var _key: E
-
- init(e: E)
- do
- _key = e
- end
-end
-
-class HashSetIterator[E]
-special Iterator[E]
- redef fun is_ok do return _node != null
-
- redef fun item
- do
- assert is_ok
- return _node.key
- end
-
- redef fun next
- do
- assert is_ok
- _node = _node.next_item
- end
-
- # The set to iterate on
- var _set: HashSet[E]
-
- # The position in the internal map storage
- var _node: nullable HashSetNode[E]
-
- init(set: HashSet[E])
- do
- _set = set
- _node = set.first_item
- end
-end
-
nitlanguage / nit.git / commitdiff