1 package edu.berkeley.sbp.util;
2 import edu.berkeley.sbp.util.*;
3 import edu.berkeley.sbp.*;
6 import java.lang.reflect.*;
7 import java.lang.ref.*;
10 // This is a fairly crude implementation; if things need to be fast,
11 // you should implement a special-purpose class
14 /** a mapping from topologies over <tt>K</tt> to <i>sets of</i> values of type <tt>V</tt> */
15 public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
17 // CRUCIAL INVARIANT: keys in this hashmap MUST be disjoint or the universe will implode
18 private final HashMap<Topology<K>,HashSet<V>> h = new HashMap<Topology<K>,HashSet<V>>();
20 public Iterator<Topology<K>> iterator() { return h.keySet().iterator(); }
22 public void addAll(TopologicalBag<K,V> tb) {
23 for(Topology<K> k : tb)
24 addAll(k, tb.getAll(k));
27 public void add(Topology<K> t, V v) { put(t, v); }
28 public void addAll(Topology<K> k, Iterable<V> vi) { putAll(k, vi); }
30 public void putAll(Topology<K> k, Iterable<V> vi) { if (vi!=null) for(V v : vi) put(k, v); }
31 public void put(Topology<K> t, V v) {
32 for(Topology<K> ht : h.keySet()) {
33 if (t.disjoint(ht)) continue;
34 if (t.containsAll(ht) && ht.containsAll(t)) {
38 if (ht.containsAll(t)) {
39 HashSet<V> v0 = h.get(ht);
40 HashSet<V> v1 = new HashSet<V>();
44 h.put(ht.intersect(t), v1);
45 h.put(ht.minus(t), v0);
48 put(t.intersect(ht), v);
52 HashSet<V> v1 = new HashSet<V>();
58 public TopologicalBag<K,V> subset(Topology<K> t) {
59 TopologicalBag<K,V> ret = new TopologicalBag<K,V>();
60 for(Topology<K> ht : h.keySet()) {
61 if (ht.disjoint(t)) continue;
62 Iterable<V> it = h.get(ht);
63 Topology<K> tk = ht.intersect(t);
69 public Map<Topology<K>,HashSet<V>> gett(Topology<K> t) {
70 HashMap<Topology<K>,HashSet<V>> ret = new HashMap<Topology<K>,HashSet<V>>();
71 for(Topology<K> ht : h.keySet()) {
72 if (ht.disjoint(t)) continue;
73 ret.put(ht.intersect(t), h.get(ht));
78 public boolean empty(K k) {
79 for(Topology<K> t : h.keySet())
80 if (t.contains(k) && h.get(t).size() > 0)
85 public boolean contains(K k) { return get(k).iterator().hasNext(); }
87 public boolean contains(K k, V v) {
88 for(Topology<K> t : h.keySet())
90 return h.get(t).contains(v);
94 private HashMap<K,Iterable<V>> cache = new HashMap<K,Iterable<V>>();
95 public Iterable<V> getAll(Topology<K> k) { return h.get(k); }
96 public Iterable<V> get(K k) {
97 Iterable<V> c = cache.get(k);
98 if (c != null) return c;
99 HashSet<V> ret = null;
100 HashSet<V> ret0 = null;
101 for(Topology<K> t : h.keySet())
104 ret0 = ret = h.get(t);
107 ret = new HashSet<V>();
111 ret.addAll(h.get(t));
115 cache.put(k, emptyIterator);
116 return emptyIterator;
118 cache.put(k, new FastSet<V>(ret));
122 private final Iterable<V> emptyIterator = new EmptyIterator<V>();