# 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]

	redef type N: HashMapNode[K, V] is fixed

	redef fun [](key)
	do
		var c = node_at(key)
		if c == null then
			return provide_default_value(key)
		else
			return c._value
		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 do return new HashMapIterator[K,V](self)

	redef fun length do return _the_length

	redef fun is_empty do return _the_length == 0

	redef fun []=(key, v)
	do
		if _capacity == 0 then enlarge(17) # 17 because magic in `store`
		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 clear do raz

	init
	do
		_capacity = 0
		_the_length = 0
	end

	# Build a list filled with the items of `coll`.
	init from(coll: Map[K, V]) do
		init
		add_all(coll)
	end

	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