getImmediateSuperelements(ReadGraph g, A a) throws DatabaseException;
-
- protected void sort(List values) {
- }
-}
+package org.simantics.db.layer0.util;
+
+import gnu.trove.map.hash.THashMap;
+import gnu.trove.set.hash.THashSet;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+import org.simantics.db.ReadGraph;
+import org.simantics.db.exception.DatabaseException;
+
+/**
+ * HierarchyMultiMap is a multi map whose keys are
+ * partially ordered. When values are asked for a key
+ * all values associated with that key and all its
+ * superkeys are returned. The order of the returned values
+ * is such that values associated with subelements are
+ * in the list before their superelements.
+ *
+ * @author Hannu Niemistö
+ */
+public abstract class HierarchyMultiMap {
+ THashMap> map = new THashMap>();
+ THashMap> cache;
+
+ /**
+ * Associates the value {@code b} with the key {@code a}.
+ */
+ public synchronized void put(A a, B b) {
+ List bs = map.get(a);
+ if(bs == null) {
+ bs = new ArrayList(2);
+ map.put(a, bs);
+ }
+ bs.add(b);
+ cache = null;
+ }
+
+ /**
+ * Gets the values stored into the map for the key {@code a} or
+ * its superelements.
+ */
+ public synchronized List get(ReadGraph g, A a) throws DatabaseException {
+ if(cache == null)
+ cache = new THashMap>();
+
+ List bs = cache.get(a);
+ if(bs == null) {
+ List base = map.get(a);
+ Collection supers = getImmediateSuperelements(g, a);
+
+ if(base == null) {
+ if(supers.isEmpty())
+ bs = Collections.emptyList();
+ else if(supers.size() == 1)
+ bs = get(g, supers.iterator().next());
+ else {
+ THashSet temp = new THashSet();
+ for(A s : supers)
+ temp.addAll(get(g, s));
+ bs = new ArrayList(temp);
+ sort(bs);
+ }
+ }
+ else {
+ if(supers.isEmpty()) {
+ bs = base;
+ sort(bs);
+ }
+ else {
+ bs = new ArrayList(base);
+ // Filter is used to remove duplicates from the result
+ THashSet filter = new THashSet(base);
+ for(A s : supers)
+ for(B b : get(g, s))
+ if(filter.add(b))
+ bs.add(b);
+
+ // Do not store duplicate of the base unnecessarily
+ if(bs.size() == base.size())
+ bs = base;
+ sort(bs);
+ }
+ }
+ cache.put(a, bs);
+ }
+ return bs;
+ }
+
+ /**
+ * Returns the immediate superelements of {@code a}.
+ * @throws DatabaseException
+ */
+ protected abstract Collection getImmediateSuperelements(ReadGraph g, A a) throws DatabaseException;
+
+ protected void sort(List values) {
+ }
+}