X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2Futil%2FTopologicalBag.java;h=259560260e602efd057bfc41fb16f59c57ffaec6;hb=74e53cbf7227f5958ff7495abe31cb0462d62c4e;hp=38e3925a9e6af487db128cba2d639046394d151b;hpb=014de68a21aa2d17fdfd0bac7e404a725997a246;p=sbp.git

diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java
index 38e3925..2595602 100644
--- a/src/edu/berkeley/sbp/util/TopologicalBag.java
+++ b/src/edu/berkeley/sbp/util/TopologicalBag.java
@@ -12,7 +12,7 @@ import java.lang.ref.*;
 //
 
 /** a mapping from topologies over <tt>K</tt> to <i>sets of</i> values of type <tt>V</tt> */
-public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
+public class TopologicalBag<K,V> implements MapBag<Topology<K>,V>, VisitableMap<K,V> {
 
     // CRUCIAL INVARIANT: keys in this hashmap MUST be disjoint or the universe will implode
     private final HashMap<Topology<K>,HashSet<V>> h = new HashMap<Topology<K>,HashSet<V>>();
@@ -134,5 +134,47 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
             return ret;
         }
     }
+
+    public VisitableMap<K,V> optimize(final Functor<K,Integer> f) {
+        ArrayList<Long> min_ = new ArrayList<Long>();
+        ArrayList<Long> max_ = new ArrayList<Long>();
+        ArrayList<Object[]> v_ = new ArrayList<Object[]>();
+        for(Topology<K> t : h.keySet()) {
+            ArrayList<V> al = new ArrayList<V>();
+            for(V vv : h.get(t)) al.add(vv);
+            Object[] vs = new Object[al.size()];
+            al.toArray(vs);
+            IntegerTopology it = (IntegerTopology)t;
+            for(Range r : it.getRanges()) {
+                min_.add(r.isMinNegInf() ? Long.MIN_VALUE : r.getMin());
+                max_.add(r.isMaxPosInf() ? Long.MAX_VALUE : r.getMax());
+                v_.add(vs);
+            }
+        }
+        final int size = v_.size();
+        final long[]     min = new long[size];     for(int i=0; i<min.length; i++) min[i]=min_.get(i);
+        final long[]     max = new long[size];     for(int i=0; i<max.length; i++) max[i]=max_.get(i);
+        final Object[][]   v = new Object[size][]; v_.toArray(v);
+        return new VisitableMap<K,V>() {
+            public boolean contains(K k) {
+                int asint = f.invoke(k);
+                for(int i=0; i<size; i++)
+                    if (min[i] <= asint && max[i] >= asint && v[i].length > 0)
+                        return true;
+                return false;
+            }
+            public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
+                int asint = f.invoke(k);
+                for(int i=0; i<size; i++) {
+                    if (min[i] <= asint && max[i] >= asint) {
+                        Object[] arr = v[i];
+                        for(int j=0; j<arr.length; j++)
+                            ivbc.invoke((V)arr[j], b, c);
+                    }
+                }
+            }
+        };
+    }
+
     private final Iterable<V> emptyIterator = new EmptyIterator<V>();
 }