]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.db.layer0/src/org/simantics/db/layer0/util/HierarchyMultiMap.java
Initial support for concurrency in databoard, bindings and serializers
[simantics/platform.git] / 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 }