X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2Futil%2FTopologicalBag.java;h=28166fb561fd66d4a01db4506b8e2e95ddaf1d84;hp=7812a516d27a20a8803968b5211d0c94251a0f7b;hb=f069d11a0bc59d63b078df8a4aa488498c4e9cc2;hpb=0a0227b9180534d2a431f3d6e08a398bde2244c4

diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java
index 7812a51..28166fb 100644
--- a/src/edu/berkeley/sbp/util/TopologicalBag.java
+++ b/src/edu/berkeley/sbp/util/TopologicalBag.java
@@ -1,3 +1,5 @@
+// Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
+
 package edu.berkeley.sbp.util;
 import edu.berkeley.sbp.util.*;
 import edu.berkeley.sbp.*;
@@ -12,7 +14,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>, Serializable {
 
     // 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>>();
@@ -27,11 +29,11 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
     public void add(Topology<K> t, V v) { put(t, v); }
     public void addAll(Topology<K> k, Iterable<V> vi) { putAll(k, vi); }
 
-    public void putAll(Topology<K> k, Iterable<V> vi) { for(V v : vi) put(k, v); }
+    public void putAll(Topology<K> k, Iterable<V> vi) { if (vi!=null) for(V v : vi) put(k, v); }
     public void put(Topology<K> t, V v) {
         for(Topology<K> ht : h.keySet()) {
             if (t.disjoint(ht)) continue;
-            if (t.equals(ht)) {
+            if (t.containsAll(ht) && ht.containsAll(t)) {
                 h.get(ht).add(v);
                 return;
             }
@@ -59,7 +61,9 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
         TopologicalBag<K,V> ret = new TopologicalBag<K,V>();
         for(Topology<K> ht : h.keySet()) {
             if (ht.disjoint(t)) continue;
-            ret.putAll(ht.intersect(t), h.get(ht));
+            Iterable<V> it = h.get(ht);
+            Topology<K> tk = ht.intersect(t);
+            ret.putAll(tk, it);
         }
         return ret;
     }
@@ -80,7 +84,7 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
         return true;
     }
 
-    public boolean contains(K k) { return get(k).iterator().hasNext(); }
+    public boolean contains(K k) { return has(k); }
 
     public boolean contains(K k, V v) {
         for(Topology<K> t : h.keySet())
@@ -89,8 +93,23 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
         return false;
     }
 
+    public boolean has(K k) {
+        for(Topology<K> t : h.keySet())
+            if (t.contains(k) && !h.get(t).isEmpty())
+                return true;
+        return false;
+    }
+
     private HashMap<K,Iterable<V>> cache = new HashMap<K,Iterable<V>>();
     public Iterable<V> getAll(Topology<K> k) { return h.get(k); }
+
+    public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
+        for(Topology<K> t : h.keySet())
+            if (t.contains(k))
+                for(V v : h.get(t))
+                    ivbc.invoke(v, b, c);
+    }
+
     public Iterable<V> get(K k) {
         Iterable<V> c = cache.get(k);
         if (c != null) return c;
@@ -117,5 +136,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>();
 }