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

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