Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.db.layer0 / src / org / simantics / db / layer0 / util / HierarchyMultiMap.java

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