X-Git-Url: http://nitlanguage.org

diff --git a/lib/more_collections.nit b/lib/more_collections.nit
index 019dc67..dd68f12 100644
--- a/lib/more_collections.nit
+++ b/lib/more_collections.nit
@@ -16,6 +16,7 @@
 module more_collections is serialize
 
 import serialization
+import poset
 
 # Simple way to store an `HashMap[K, Array[V]]`
 #
@@ -35,7 +36,20 @@ 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)
@@ -51,6 +65,73 @@ class MultiHashMap[K, 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
 
 # Simple way to store an `HashMap[K1, HashMap[K2, V]]`
@@ -97,6 +178,13 @@ class HashMap2[K1, K2, V]
 		level2.keys.remove(k2)
 	end
 
+	# Is there a value at `k1, k2`?
+	fun has(k1: K1, k2: K2): Bool
+	do
+		if not level1.keys.has(k1) then return false
+		return level1[k1].keys.has(k2)
+	end
+
 	# Remove all items
 	fun clear do level1.clear
 end
@@ -145,6 +233,68 @@ class HashMap3[K1, K2, K3, V]
 		level2.remove_at(k2, k3)
 	end
 
+	# Is there a value at `k1, k2, k3`?
+	fun has(k1: K1, k2: K2, k3: K3): Bool
+	do
+		if not level1.keys.has(k1) then return false
+		return level1[k1].has(k2, k3)
+	end
+
+	# Remove all items
+	fun clear do level1.clear
+end
+
+# Simple way to store an `HashMap[K1, HashMap[K2, HashMap[K3, HashMap[K4, V]]]]`
+#
+# ~~~~
+# var hm4 = new HashMap4[Int, String, Int, String, Float]
+# hm4[1, "one", 11, "un"] = 1.0
+# hm4[2, "two", 22, "deux"] = 2.0
+# assert hm4[1, "one", 11, "un"] == 1.0
+# assert hm4[2, "not-two", 22, "deux"] == null
+# ~~~~
+class HashMap4[K1, K2, K3, K4, V]
+
+	private var level1 = new HashMap[K1, HashMap3[K2, K3, K4, V]]
+
+	# Return the value associated to the keys `k1`, `k2`, `k3` and `k4`.
+	# Return `null` if no such a value.
+	fun [](k1: K1, k2: K2, k3: K3, k4: K4): nullable V
+	do
+		var level1 = self.level1
+		var level2 = level1.get_or_null(k1)
+		if level2 == null then return null
+		return level2[k2, k3, k4]
+	end
+
+	# Set `v` the value associated to the keys `k1`, `k2`, `k3` and `k4`.
+	fun []=(k1: K1, k2: K2, k3: K3, k4: K4, v: V)
+	do
+		var level1 = self.level1
+		var level2 = level1.get_or_null(k1)
+		if level2 == null then
+			level2 = new HashMap3[K2, K3, K4, V]
+			level1[k1] = level2
+		end
+		level2[k2, k3, k4] = v
+	end
+
+	# Remove the item at `k1`, `k2`, `k3` and `k4`
+	fun remove_at(k1: K1, k2: K2, k3: K3, k4: K4)
+	do
+		var level1 = self.level1
+		var level2 = level1.get_or_null(k1)
+		if level2 == null then return
+		level2.remove_at(k2, k3, k4)
+	end
+
+	# Is there a value at `k1, k2, k3, k4`?
+	fun has(k1: K1, k2: K2, k3: K3, k4: K4): Bool
+	do
+		if not level1.keys.has(k1) then return false
+		return level1[k1].has(k2, k3, k4)
+	end
+
 	# Remove all items
 	fun clear do level1.clear
 end
@@ -526,3 +676,44 @@ private class UnrolledIterator[E]
 		end
 	end
 end
+
+# Keep track of the best elements according to a distance value.
+#
+# ~~~
+# var bests = new BestDistance[String](5)
+# bests.update(10, "Too big")
+# assert bests.best_items.is_empty
+# bests.update(5, "Just fine")
+# bests.update(5, "Another one")
+# assert bests.best_items.has_exactly(["Just fine", "Another one"])
+# bests.update(2, "A better one")
+# bests.update(4, "Not good enough")
+# assert bests.best_distance == 2
+# assert bests.best_items.has_exactly(["A better one"])
+# ~~~
+class BestDistance[E]
+	# Current smallest distance
+	var best_distance: Int is writable
+
+	# Known elements with the smallest distance
+	var best_items = new Set[E] is writable
+
+	# Register a `candidate` with a `distance`
+	#
+	# * To high, it is ignored.
+	# * Equal to the current best, it is added
+	# * Better that them, is is the new best element
+	#
+	# Return `true` if the candidate is kept (alone or with other)
+	# returns `false` if the candidate is ignored.
+	fun update(distance: Int, candidate: E): Bool
+	do
+		if distance > best_distance then return false
+		if distance < best_distance then
+			best_distance = distance
+			best_items.clear
+		end
+		best_items.add candidate
+		return true
+	end
+end