1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp.util;
4 import edu.berkeley.sbp.util.*;
5 import edu.berkeley.sbp.*;
8 import java.lang.reflect.*;
9 import java.lang.ref.*;
12 // This is a fairly crude implementation; if things need to be fast,
13 // you should implement a special-purpose class
16 /** a mapping from topologies over <tt>K</tt> to <i>sets of</i> values of type <tt>V</tt> */
17 public class TopologicalBag<K,V> implements MapBag<Topology<K>,V>, VisitableMap<K,V> {
19 // CRUCIAL INVARIANT: keys in this hashmap MUST be disjoint or the universe will implode
20 private final HashMap<Topology<K>,HashSet<V>> h = new HashMap<Topology<K>,HashSet<V>>();
22 public Iterator<Topology<K>> iterator() { return h.keySet().iterator(); }
24 public void addAll(TopologicalBag<K,V> tb) {
25 for(Topology<K> k : tb)
26 addAll(k, tb.getAll(k));
29 public void add(Topology<K> t, V v) { put(t, v); }
30 public void addAll(Topology<K> k, Iterable<V> vi) { putAll(k, vi); }
32 public void putAll(Topology<K> k, Iterable<V> vi) { if (vi!=null) for(V v : vi) put(k, v); }
33 public void put(Topology<K> t, V v) {
34 for(Topology<K> ht : h.keySet()) {
35 if (t.disjoint(ht)) continue;
36 if (t.containsAll(ht) && ht.containsAll(t)) {
40 if (ht.containsAll(t)) {
41 HashSet<V> v0 = h.get(ht);
42 HashSet<V> v1 = new HashSet<V>();
46 h.put(ht.intersect(t), v1);
47 h.put(ht.minus(t), v0);
50 put(t.intersect(ht), v);
54 HashSet<V> v1 = new HashSet<V>();
60 public TopologicalBag<K,V> subset(Topology<K> t) {
61 TopologicalBag<K,V> ret = new TopologicalBag<K,V>();
62 for(Topology<K> ht : h.keySet()) {
63 if (ht.disjoint(t)) continue;
64 Iterable<V> it = h.get(ht);
65 Topology<K> tk = ht.intersect(t);
71 public Map<Topology<K>,HashSet<V>> gett(Topology<K> t) {
72 HashMap<Topology<K>,HashSet<V>> ret = new HashMap<Topology<K>,HashSet<V>>();
73 for(Topology<K> ht : h.keySet()) {
74 if (ht.disjoint(t)) continue;
75 ret.put(ht.intersect(t), h.get(ht));
80 public boolean empty(K k) {
81 for(Topology<K> t : h.keySet())
82 if (t.contains(k) && h.get(t).size() > 0)
87 public boolean contains(K k) { return has(k); }
89 public boolean contains(K k, V v) {
90 for(Topology<K> t : h.keySet())
92 return h.get(t).contains(v);
96 public boolean has(K k) {
97 for(Topology<K> t : h.keySet())
98 if (t.contains(k) && !h.get(t).isEmpty())
103 private HashMap<K,Iterable<V>> cache = new HashMap<K,Iterable<V>>();
104 public Iterable<V> getAll(Topology<K> k) { return h.get(k); }
106 public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
107 for(Topology<K> t : h.keySet())
110 ivbc.invoke(v, b, c);
113 public Iterable<V> get(K k) {
114 Iterable<V> c = cache.get(k);
115 if (c != null) return c;
116 HashSet<V> ret = null;
117 HashSet<V> ret0 = null;
118 for(Topology<K> t : h.keySet())
121 ret0 = ret = h.get(t);
124 ret = new HashSet<V>();
128 ret.addAll(h.get(t));
132 cache.put(k, emptyIterator);
133 return emptyIterator;
135 cache.put(k, new FastSet<V>(ret));
140 public VisitableMap<K,V> optimize(final Functor<K,Integer> f) {
141 ArrayList<Long> min_ = new ArrayList<Long>();
142 ArrayList<Long> max_ = new ArrayList<Long>();
143 ArrayList<Object[]> v_ = new ArrayList<Object[]>();
144 for(Topology<K> t : h.keySet()) {
145 ArrayList<V> al = new ArrayList<V>();
146 for(V vv : h.get(t)) al.add(vv);
147 Object[] vs = new Object[al.size()];
149 IntegerTopology it = (IntegerTopology)t;
150 for(Range r : it.getRanges()) {
151 min_.add(r.isMinNegInf() ? Long.MIN_VALUE : r.getMin());
152 max_.add(r.isMaxPosInf() ? Long.MAX_VALUE : r.getMax());
156 final int size = v_.size();
157 final long[] min = new long[size]; for(int i=0; i<min.length; i++) min[i]=min_.get(i);
158 final long[] max = new long[size]; for(int i=0; i<max.length; i++) max[i]=max_.get(i);
159 final Object[][] v = new Object[size][]; v_.toArray(v);
160 return new VisitableMap<K,V>() {
161 public boolean contains(K k) {
162 int asint = f.invoke(k);
163 for(int i=0; i<size; i++)
164 if (min[i] <= asint && max[i] >= asint && v[i].length > 0)
168 public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
169 int asint = f.invoke(k);
170 for(int i=0; i<size; i++) {
171 if (min[i] <= asint && max[i] >= asint) {
173 for(int j=0; j<arr.length; j++)
174 ivbc.invoke((V)arr[j], b, c);
181 private final Iterable<V> emptyIterator = new EmptyIterator<V>();