# Simple way to store an `HashMap[K, Array[V]]`
#
# Unlike standard HashMap, MultiHashMap provides a new
# empty array on the first access on a unknown key.
#
#     var m = new MultiHashMap[String, Char]
#     assert not m.has_key("four")
#     m["four"].add('i')
#     m["four"].add('i')
#     m["four"].add('i')
#     m["four"].add('i')
#     assert m.has_key("four")
#     assert m["four"] == ['i', 'i', 'i', 'i']
#     assert m["zzz"] == new Array[Char]
class MultiHashMap[K, V]
	super HashMap[K, Array[V]]

	# Add `v` to the array associated with `k`.
	#
	# If there is no array associated, then create it.
	#
	# For the inverse operation, see `remove_one`.
	#
	# ```
	# var m = new MultiHashMap[String, Char]
	# m.add_one("four", 'i')
	# m.add_one("four", 'i')
	# m.add_one("four", 'i')
	# m.add_one("four", 'i')
	# assert m.has_key("four")
	# assert m["four"] == ['i', 'i', 'i', 'i']
	# ```
	fun add_one(k: K, v: V)
	do
		var x = self.get_or_null(k)
		if x != null then
			x.add(v)
		else
			self[k] = [v]
		end
	end

	redef fun provide_default_value(key) do
		var res = new Array[V]
		self[key] = res
		return res
	end

	# Remove an occurrence of `v` from the array associated with `k`.
	#
	# If the associated array does not contain `v`, do nothing. If the
	# associated array only contain one element and this element is `v`, remove
	# the key `k`.
	#
	# In a nutshell, does the inverse operation of `add_one`.
	#
	# ```
	# var m = new MultiHashMap[String, Char]
	# m["four"]        =  ['4', 'i', 'i', 'i', 'i']
	# m.remove_one("four", 'i')
	# assert m["four"] == ['4', 'i', 'i', 'i']
	#
	# m = new MultiHashMap[String, Char]
	# m.add_one("one", '1')
	# m.remove_one("one", '?')
	# assert m["one"] == ['1']
	# m.remove_one("one", '1')
	# assert not m.has_key("one")
	# assert m["one"] == new Array[Char]
	#
	# m = new MultiHashMap[String, Char]
	# m.add_one("one", '1')
	# m.remove_one("two", '2')
	# assert not m.has_key("two")
	# assert m["one"] == ['1']
	# assert m["two"] == new Array[Char]
	# ```
	fun remove_one(k: K, v: V)
	do
		var x = get_or_null(k)
		if x != null then
			x.remove(v)
			if x.is_empty then keys.remove(k)
		end
	end

	# Search the values in `pe.greaters` from the most smaller elements that have a value.
	#
	# Elements without values are ignored.
	#
	# Basically, values defined in nearest greater elements of `pe` are inherited.
	#
	# ~~~
	# var pos = new POSet[String]
	# pos.add_chain(["E", "D", "C", "B", "A"])
	# pos.add_chain(["D", "X", "B"])
	#
	# var map = new MultiHashMap[String, String]
	# map["A"].append(["a", "1"])
	# map["C"].append(["c", "2"])
	# map["X"].append(["x", "2"])
	# map["E"].add "e"
	#
	# assert map.lookup_joined_values(pos["B"]).has_exactly(["a", "1"])
	# assert map.lookup_joined_values(pos["C"]).has_exactly(["c", "2"])
	# assert map.lookup_joined_values(pos["D"]).has_exactly(["c", "x", "2"])
	# ~~~
	fun lookup_joined_values(pe: POSetElement[K]): Set[V]
	do
		var res = new Set[V]
		for k in pe.poset.select_smallest(filter_keys(pe.greaters)) do res.add_all self[k]
		return res

	end
end