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

   1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
   2
   3 package edu.berkeley.sbp.util;
   4 import edu.berkeley.sbp.util.*;
   5 import edu.berkeley.sbp.*;
   6 import java.io.*;
   7 import java.util.*;
   8 import java.lang.reflect.*;
   9 import java.lang.ref.*;
  10
  11 //
  12 // This is a fairly crude implementation; if things need to be fast,
  13 // you should implement a special-purpose class
  14 //
  15
  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> {
  18
  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>>();
  21
  22     public Iterator<Topology<K>> iterator() { return h.keySet().iterator(); }
  23
  24     public void addAll(TopologicalBag<K,V> tb) {
  25         for(Topology<K> k : tb)
  26             addAll(k, tb.getAll(k));
  27     }
  28
  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); }
  31
  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)) {
  37                 h.get(ht).add(v);
  38                 return;
  39             }
  40             if (ht.containsAll(t)) {
  41                 HashSet<V> v0 = h.get(ht);
  42                 HashSet<V> v1 = new HashSet<V>();
  43                 v1.addAll(v0);
  44                 h.remove(ht);
  45                 v1.add(v);
  46                 h.put(ht.intersect(t), v1);
  47                 h.put(ht.minus(t), v0);
  48                 return;
  49             }
  50             put(t.intersect(ht), v);
  51             put(t.minus(ht), v);
  52             return;
  53         }
  54         HashSet<V> v1 = new HashSet<V>();
  55         v1.add(v);
  56         h.put(t, v1);
  57     }
  58
  59
  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);
  66             ret.putAll(tk, it);
  67         }
  68         return ret;
  69     }
  70
  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));
  76         }
  77         return ret;
  78     }
  79
  80     public boolean empty(K k) {
  81         for(Topology<K> t : h.keySet())
  82             if (t.contains(k) && h.get(t).size() > 0)
  83                 return false;
  84         return true;
  85     }
  86
  87     public boolean contains(K k) { return has(k); }
  88
  89     public boolean contains(K k, V v) {
  90         for(Topology<K> t : h.keySet())
  91             if (t.contains(k))
  92                 return h.get(t).contains(v);
  93         return false;
  94     }
  95
  96     public boolean has(K k) {
  97         for(Topology<K> t : h.keySet())
  98             if (t.contains(k) && !h.get(t).isEmpty())
  99                 return true;
 100         return false;
 101     }
 102
 103     private HashMap<K,Iterable<V>> cache = new HashMap<K,Iterable<V>>();
 104     public Iterable<V> getAll(Topology<K> k) { return h.get(k); }
 105
 106     public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
 107         for(Topology<K> t : h.keySet())
 108             if (t.contains(k))
 109                 for(V v : h.get(t))
 110                     ivbc.invoke(v, b, c);
 111     }
 112
 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())
 119             if (t.contains(k)) {
 120                 if (ret==null) {
 121                     ret0 = ret = h.get(t);
 122                 } else {
 123                     if (ret0 != null) {
 124                         ret = new HashSet<V>();
 125                         ret.addAll(ret0);
 126                         ret0 = null;
 127                     }
 128                     ret.addAll(h.get(t));
 129                 }
 130             }
 131         if (ret==null) {
 132             cache.put(k, emptyIterator);
 133             return emptyIterator;
 134         } else {
 135             cache.put(k, new FastSet<V>(ret));
 136             return ret;
 137         }
 138     }
 139
 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()];
 148             al.toArray(vs);
 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());
 153                 v_.add(vs);
 154             }
 155         }
 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)
 165                         return true;
 166                 return false;
 167             }
 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) {
 172                         Object[] arr = v[i];
 173                         for(int j=0; j<arr.length; j++)
 174                             ivbc.invoke((V)arr[j], b, c);
 175                     }
 176                 }
 177             }
 178         };
 179     }
 180
 181     private final Iterable<V> emptyIterator = new EmptyIterator<V>();
 182 }