1 package org.simantics.db.layer0.util;
3 import gnu.trove.map.hash.THashMap;
4 import gnu.trove.set.hash.THashSet;
6 import java.util.ArrayList;
7 import java.util.Collection;
8 import java.util.Collections;
11 import org.simantics.db.ReadGraph;
12 import org.simantics.db.exception.DatabaseException;
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>
22 * @author Hannu Niemistö
24 public abstract class HierarchyMultiMap<A,B> {
25 THashMap<A, List<B>> map = new THashMap<A, List<B>>();
26 THashMap<A, List<B>> cache;
29 * Associates the value {@code b} with the key {@code a}.
31 public synchronized void put(A a, B b) {
32 List<B> bs = map.get(a);
34 bs = new ArrayList<B>(2);
42 * Appends the contents of the specified map to this map.
44 * @param from the map to append contents from
46 public void append(HierarchyMultiMap<A,B> from) {
51 * Appends the contents of this map to the specified map.
53 * @param to the map to append to
55 public void appendTo(HierarchyMultiMap<A,B> to) {
56 map.forEachEntry((a, bl) -> {
57 bl.forEach(b -> to.put(a, b));
63 * Gets the values stored into the map for the key {@code a} or
66 public synchronized List<B> get(ReadGraph g, A a) throws DatabaseException {
68 cache = new THashMap<A, List<B>>();
70 List<B> bs = cache.get(a);
72 List<B> base = map.get(a);
73 Collection<A> supers = getImmediateSuperelements(g, a);
77 bs = Collections.emptyList();
78 else if(supers.size() == 1)
79 bs = get(g, supers.iterator().next());
81 THashSet<B> temp = new THashSet<B>();
83 temp.addAll(get(g, s));
84 bs = new ArrayList<B>(temp);
89 if(supers.isEmpty()) {
94 bs = new ArrayList<B>(base);
95 // Filter is used to remove duplicates from the result
96 THashSet<B> filter = new THashSet<B>(base);
102 // Do not store duplicate of the base unnecessarily
103 if(bs.size() == base.size())
114 * Returns the immediate superelements of {@code a}.
115 * @throws DatabaseException
117 protected abstract Collection<A> getImmediateSuperelements(ReadGraph g, A a) throws DatabaseException;
119 protected void sort(List<B> values) {