bundles/org.simantics.db.layer0/src/org/simantics/db/layer0/util/HierarchyMultiMap.java

   1 package org.simantics.db.layer0.util;\r
   2 \r
   3 import gnu.trove.map.hash.THashMap;\r
   4 import gnu.trove.set.hash.THashSet;\r
   5 \r
   6 import java.util.ArrayList;\r
   7 import java.util.Collection;\r
   8 import java.util.Collections;\r
   9 import java.util.List;\r
  10 \r
  11 import org.simantics.db.ReadGraph;\r
  12 import org.simantics.db.exception.DatabaseException;\r
  13 \r
  14 /**\r
  15  * <p>HierarchyMultiMap is a multi map whose keys are \r
  16  * partially ordered. When values are asked for a key \r
  17  * all values associated with that key and all its\r
  18  * superkeys are returned. The order of the returned values\r
  19  * is such that values associated with subelements are \r
  20  * in the list before their superelements.</p>\r
  21  *\r
  22  * @author Hannu Niemist&ouml;\r
  23  */\r
  24 public abstract class HierarchyMultiMap<A,B> {\r
  25     THashMap<A, List<B>> map = new THashMap<A, List<B>>();\r
  26     THashMap<A, List<B>> cache;\r
  27 \r
  28     /**\r
  29      * Associates the value {@code b} with the key {@code a}.\r
  30      */\r
  31     public synchronized void put(A a, B b) {\r
  32         List<B> bs = map.get(a);\r
  33         if(bs == null) {\r
  34             bs = new ArrayList<B>(2);\r
  35             map.put(a, bs);\r
  36         }\r
  37         bs.add(b);\r
  38         cache = null;\r
  39     }\r
  40     \r
  41     /**\r
  42      * Gets the values stored into the map for the key {@code a} or\r
  43      * its superelements.\r
  44      */\r
  45     public synchronized List<B> get(ReadGraph g, A a) throws DatabaseException {\r
  46         if(cache == null)\r
  47             cache = new THashMap<A, List<B>>();\r
  48             \r
  49         List<B> bs = cache.get(a);\r
  50         if(bs == null) {\r
  51             List<B> base = map.get(a);\r
  52             Collection<A> supers = getImmediateSuperelements(g, a);\r
  53             \r
  54             if(base == null) {\r
  55                 if(supers.isEmpty())\r
  56                     bs = Collections.emptyList();\r
  57                 else if(supers.size() == 1)\r
  58                     bs = get(g, supers.iterator().next());\r
  59                 else {\r
  60                     THashSet<B> temp = new THashSet<B>();\r
  61                     for(A s : supers)\r
  62                         temp.addAll(get(g, s));\r
  63                     bs = new ArrayList<B>(temp);\r
  64                     sort(bs);\r
  65                 }\r
  66             }\r
  67             else {\r
  68                 if(supers.isEmpty()) {\r
  69                     bs = base;\r
  70                     sort(bs);\r
  71                 }\r
  72                 else {\r
  73                     bs = new ArrayList<B>(base);\r
  74                     // Filter is used to remove duplicates from the result\r
  75                     THashSet<B> filter = new THashSet<B>(base);\r
  76                     for(A s : supers) \r
  77                         for(B b : get(g, s))\r
  78                             if(filter.add(b))\r
  79                                 bs.add(b);                    \r
  80                     \r
  81                     // Do not store duplicate of the base unnecessarily\r
  82                     if(bs.size() == base.size())\r
  83                         bs = base;\r
  84                     sort(bs);\r
  85                 }\r
  86             }\r
  87             cache.put(a, bs);\r
  88         }\r
  89         return bs;\r
  90     }\r
  91     \r
  92     /**\r
  93      * Returns the immediate superelements of {@code a}.\r
  94      * @throws DatabaseException \r
  95      */\r
  96     protected abstract Collection<A> getImmediateSuperelements(ReadGraph g, A a) throws DatabaseException;\r
  97     \r
  98     protected void sort(List<B> values) {\r
  99     }\r
 100 }\r