bench/engines: add a sanitary check to just run the various benched programs
[nit.git] / lib / more_collections.nit
index 019dc67..81688d9 100644 (file)
@@ -35,7 +35,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 +64,44 @@ 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
 end
 
 # Simple way to store an `HashMap[K1, HashMap[K2, V]]`
@@ -97,6 +148,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 +203,13 @@ 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
@@ -526,3 +591,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