# This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2004-2008 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.

# 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

redef class Object
	# The hash code of the object.
	# Assuming that a = b -> a.hash = b.hash
	##
	# Without redefinition, it is the `id' of the instance.
	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

redef class Char
	redef fun hash do return ascii
end

redef class Bool
	redef fun hash
	do
		if self then
			return 1
		else
			return 0
		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