# A HashCollection is an array of HashNode[K] indexed by the K hash value
private abstract class HashCollection[K]
	type N: HashNode[K]

	var array: NativeArray[nullable N] is noautoinit # 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)

	# The last key accessed (used for cache)
	var last_accessed_key: nullable Object = null

	# The last node accessed (used for cache)
	var last_accessed_node: nullable N = null

	# Return the index of the key k
	fun index_at(k: nullable Object): 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 associated with the key
	fun node_at(k: nullable Object): nullable N
	do
		if _the_length == 0 then return null
		# cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
		if k.is_same_instance(_last_accessed_key) then return _last_accessed_node

		var res = node_at_idx(index_at(k), k)
		_last_accessed_key = k
		_last_accessed_node = res
		return res
	end

	# Return the node associated with the key (but with the index already known)
	fun node_at_idx(i: Int, k: nullable Object): nullable N
	do
		if _the_length == 0 then return null
		var c = _array[i]
		while c != null do
			var ck = c._key
			if ck.is_same_instance(k) or ck == k then # FIXME prefilter because the compiler is not smart enought yet
				break
			end
			c = c._next_in_bucklet
		end
		return c
	end

	# Add a new node at a given index
	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
		var next = _array[index]
		_array[index] = node
		node._next_in_bucklet = next
		if next != null then next._prev_in_bucklet = node

		_last_accessed_key = node._key
		_last_accessed_node = node

		# Enlarge if needed
		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 * 3 / 2 + 1)
		end
	end

	# Remove the node assosiated with the key
	fun remove_node(k: nullable Object)
	do
		if _the_length == 0 then return
		var i = index_at(k)
		var node = node_at_idx(i, k)
		if node == null then return

		# 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
		_the_length -= 1
		prev = node._prev_in_bucklet
		next = node._next_in_bucklet
		if prev != null then
			prev._next_in_bucklet = next
		else
			_array[i] = next
		end
		if next != null then
			next._prev_in_bucklet = prev
		end

		_last_accessed_key = null
	end

	# Clear the whole structure
	fun raz
	do
		var i = _capacity - 1
		while i >= 0 do
			_array[i] = null
			i -= 1
		end
		_the_length = 0
		_first_item = null
		_last_item = null
		_last_accessed_key = null
	end

	# Force a capacity
	fun enlarge(cap: Int)
	do
		# get a new capacity
		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 = new NativeArray[nullable N](cap)
		_array = new_array

		# Reput items in the array
		var node = _first_item
		while node != null do
			var index = index_at(node._key)
			# Then store it in the array
			var next = new_array[index]
			new_array[index] = node
			node._prev_in_bucklet = null
			node._next_in_bucklet = next
			if next != null then next._prev_in_bucklet = node
			node = node._next_item
		end
	end
end