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      * Gets the values stored into the map for the key {@code a} or
  43      * its superelements.
  44      */
  45     public synchronized List<B> get(ReadGraph g, A a) throws DatabaseException {
  46         if(cache == null)
  47             cache = new THashMap<A, List<B>>();
  48
  49         List<B> bs = cache.get(a);
  50         if(bs == null) {
  51             List<B> base = map.get(a);
  52             Collection<A> supers = getImmediateSuperelements(g, a);
  53
  54             if(base == null) {
  55                 if(supers.isEmpty())
  56                     bs = Collections.emptyList();
  57                 else if(supers.size() == 1)
  58                     bs = get(g, supers.iterator().next());
  59                 else {
  60                     THashSet<B> temp = new THashSet<B>();
  61                     for(A s : supers)
  62                         temp.addAll(get(g, s));
  63                     bs = new ArrayList<B>(temp);
  64                     sort(bs);
  65                 }
  66             }
  67             else {
  68                 if(supers.isEmpty()) {
  69                     bs = base;
  70                     sort(bs);
  71                 }
  72                 else {
  73                     bs = new ArrayList<B>(base);
  74                     // Filter is used to remove duplicates from the result
  75                     THashSet<B> filter = new THashSet<B>(base);
  76                     for(A s : supers)
  77                         for(B b : get(g, s))
  78                             if(filter.add(b))
  79                                 bs.add(b);
  80
  81                     // Do not store duplicate of the base unnecessarily
  82                     if(bs.size() == base.size())
  83                         bs = base;
  84                     sort(bs);
  85                 }
  86             }
  87             cache.put(a, bs);
  88         }
  89         return bs;
  90     }
  91
  92     /**
  93      * Returns the immediate superelements of {@code a}.
  94      * @throws DatabaseException
  95      */
  96     protected abstract Collection<A> getImmediateSuperelements(ReadGraph g, A a) throws DatabaseException;
  97
  98     protected void sort(List<B> values) {
  99     }
 100 }