1 package org.simantics.db.layer0.util;
\r
3 import gnu.trove.map.hash.THashMap;
\r
4 import gnu.trove.set.hash.THashSet;
\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
11 import org.simantics.db.ReadGraph;
\r
12 import org.simantics.db.exception.DatabaseException;
\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
22 * @author Hannu Niemistö
\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
29 * Associates the value {@code b} with the key {@code a}.
\r
31 public synchronized void put(A a, B b) {
\r
32 List<B> bs = map.get(a);
\r
34 bs = new ArrayList<B>(2);
\r
42 * Gets the values stored into the map for the key {@code a} or
\r
43 * its superelements.
\r
45 public synchronized List<B> get(ReadGraph g, A a) throws DatabaseException {
\r
47 cache = new THashMap<A, List<B>>();
\r
49 List<B> bs = cache.get(a);
\r
51 List<B> base = map.get(a);
\r
52 Collection<A> supers = getImmediateSuperelements(g, a);
\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
60 THashSet<B> temp = new THashSet<B>();
\r
62 temp.addAll(get(g, s));
\r
63 bs = new ArrayList<B>(temp);
\r
68 if(supers.isEmpty()) {
\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
77 for(B b : get(g, s))
\r
81 // Do not store duplicate of the base unnecessarily
\r
82 if(bs.size() == base.size())
\r
93 * Returns the immediate superelements of {@code a}.
\r
94 * @throws DatabaseException
\r
96 protected abstract Collection<A> getImmediateSuperelements(ReadGraph g, A a) throws DatabaseException;
\r
98 protected void sort(List<B> values) {
\r