src/edu/berkeley/sbp/util/TopologicalBag.java

   1 package edu.berkeley.sbp.util;
   2 import edu.berkeley.sbp.util.*;
   3 import edu.berkeley.sbp.*;
   4 import java.io.*;
   5 import java.util.*;
   6 import java.lang.reflect.*;
   7 import java.lang.ref.*;
   8
   9 //
  10 // This is a fairly crude implementation; if things need to be fast,
  11 // you should implement a special-purpose class
  12 //
  13
  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>, VisitableMap<K,V> {
  16
  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>>();
  19
  20     public Iterator<Topology<K>> iterator() { return h.keySet().iterator(); }
  21
  22     public void addAll(TopologicalBag<K,V> tb) {
  23         for(Topology<K> k : tb)
  24             addAll(k, tb.getAll(k));
  25     }
  26
  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); }
  29
  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)) {
  35                 h.get(ht).add(v);
  36                 return;
  37             }
  38             if (ht.containsAll(t)) {
  39                 HashSet<V> v0 = h.get(ht);
  40                 HashSet<V> v1 = new HashSet<V>();
  41                 v1.addAll(v0);
  42                 h.remove(ht);
  43                 v1.add(v);
  44                 h.put(ht.intersect(t), v1);
  45                 h.put(ht.minus(t), v0);
  46                 return;
  47             }
  48             put(t.intersect(ht), v);
  49             put(t.minus(ht), v);
  50             return;
  51         }
  52         HashSet<V> v1 = new HashSet<V>();
  53         v1.add(v);
  54         h.put(t, v1);
  55     }
  56
  57
  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);
  64             ret.putAll(tk, it);
  65         }
  66         return ret;
  67     }
  68
  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));
  74         }
  75         return ret;
  76     }
  77
  78     public boolean empty(K k) {
  79         for(Topology<K> t : h.keySet())
  80             if (t.contains(k) && h.get(t).size() > 0)
  81                 return false;
  82         return true;
  83     }
  84
  85     public boolean contains(K k) { return has(k); }
  86
  87     public boolean contains(K k, V v) {
  88         for(Topology<K> t : h.keySet())
  89             if (t.contains(k))
  90                 return h.get(t).contains(v);
  91         return false;
  92     }
  93
  94     public boolean has(K k) {
  95         for(Topology<K> t : h.keySet())
  96             if (t.contains(k) && !h.get(t).isEmpty())
  97                 return true;
  98         return false;
  99     }
 100
 101     private HashMap<K,Iterable<V>> cache = new HashMap<K,Iterable<V>>();
 102     public Iterable<V> getAll(Topology<K> k) { return h.get(k); }
 103
 104     public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
 105         for(Topology<K> t : h.keySet())
 106             if (t.contains(k))
 107                 for(V v : h.get(t))
 108                     ivbc.invoke(v, b, c);
 109     }
 110
 111     public Iterable<V> get(K k) {
 112         Iterable<V> c = cache.get(k);
 113         if (c != null) return c;
 114         HashSet<V> ret = null;
 115         HashSet<V> ret0 = null;
 116         for(Topology<K> t : h.keySet())
 117             if (t.contains(k)) {
 118                 if (ret==null) {
 119                     ret0 = ret = h.get(t);
 120                 } else {
 121                     if (ret0 != null) {
 122                         ret = new HashSet<V>();
 123                         ret.addAll(ret0);
 124                         ret0 = null;
 125                     }
 126                     ret.addAll(h.get(t));
 127                 }
 128             }
 129         if (ret==null) {
 130             cache.put(k, emptyIterator);
 131             return emptyIterator;
 132         } else {
 133             cache.put(k, new FastSet<V>(ret));
 134             return ret;
 135         }
 136     }
 137
 138     public VisitableMap<K,V> optimize(final Functor<K,Integer> f) {
 139         ArrayList<Long> min_ = new ArrayList<Long>();
 140         ArrayList<Long> max_ = new ArrayList<Long>();
 141         ArrayList<Object[]> v_ = new ArrayList<Object[]>();
 142         for(Topology<K> t : h.keySet()) {
 143             ArrayList<V> al = new ArrayList<V>();
 144             for(V vv : h.get(t)) al.add(vv);
 145             Object[] vs = new Object[al.size()];
 146             al.toArray(vs);
 147             IntegerTopology it = (IntegerTopology)t;
 148             for(Range r : it.getRanges()) {
 149                 min_.add(r.isMinNegInf() ? Long.MIN_VALUE : r.getMin());
 150                 max_.add(r.isMaxPosInf() ? Long.MAX_VALUE : r.getMax());
 151                 v_.add(vs);
 152             }
 153         }
 154         final int size = v_.size();
 155         final long[]     min = new long[size];     for(int i=0; i<min.length; i++) min[i]=min_.get(i);
 156         final long[]     max = new long[size];     for(int i=0; i<max.length; i++) max[i]=max_.get(i);
 157         final Object[][]   v = new Object[size][]; v_.toArray(v);
 158         return new VisitableMap<K,V>() {
 159             public boolean contains(K k) {
 160                 int asint = f.invoke(k);
 161                 for(int i=0; i<size; i++)
 162                     if (min[i] <= asint && max[i] >= asint && v[i].length > 0)
 163                         return true;
 164                 return false;
 165             }
 166             public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
 167                 int asint = f.invoke(k);
 168                 for(int i=0; i<size; i++) {
 169                     if (min[i] <= asint && max[i] >= asint) {
 170                         Object[] arr = v[i];
 171                         for(int j=0; j<arr.length; j++)
 172                             ivbc.invoke((V)arr[j], b, c);
 173                     }
 174                 }
 175             }
 176         };
 177     }
 178
 179     private final Iterable<V> emptyIterator = new EmptyIterator<V>();
 180 }