optimizations to IntPairMap.java

[sbp.git] / src / edu / berkeley / sbp / util / TopologicalBag.java

diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java
index 8862be6..28166fb 100644 (file)
--- 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>>();
@@ -82,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())
@@ -91,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;
@@ -119,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>();
 }