Add MergeableMap (an implementation of the union-find algorithm)

[julianhyde]

Add interface MergeableMap, an implementation of the union-find algorithm using the disjoint set data structure.

A MergeableMap<K, V> is a Map<K, V> with an additional operation:

• V merge(K k1, K k2) that declares that two keys are in the same equivalence class

We provide an implementation, class MergeableHashMap<K, V>, based on a hash map.

If you just want to build equivalence classes, you can create a MergeableMap with a Void value.

[julianhyde]

Similar to JGraphT's UnionFind.

[julianhyde]

Dev branch: https://github.com/julianhyde/morel/tree/236-disjoint-set

[julianhyde]

As of julianhyde@fd1527d the put(K key, V value) method (inherited from Map<K, V>) is a bit awkward. If key is new, or is a singleton equivalence class, it works as you would expect. But if key is part of a larger equivalence class, value will replace the value for the whole equivalence class. That doesn't seem right if value has been carefully constructed by aggregating the values of all keys in the equivalence class. It's not even possible to re-compute the value, because the per-key values have been lost.

For similar reasons, we don't allow remove(key). We would have to re-compute the sum for the whole equivalence class.

Maybe the solution is for MergeableMap<K, V> to become MergeableMap<K, V, S> where S is the summed value for an equivalence set. We remember the values of each individual key, and V get(K) and put(K, V)work on these values.Map.Entry<K, S> find(K)` returns the representative key and summed value for an equivalence set.

put(K, V) and remove(K) would be expensive because we have to scan the whole map, to find all the members of the equivalence class, to compute its sum from scratch. We could make them cheaper by adding a Function<S, V, S> subtractor as inverse for Function<S, V, S> combiner.

Of course if you don't have values, you can use MergeableMap<K, Dummy, Dummy> where

enum Dummy {
  INSTANCE;

  Dummy add(Dummy d) { return this; )
  Dummy subtract(Dummy d) { return this; }
}

is a singleton.