Robust/src/Util/Lattice.java

   1 package Util;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.Set;
   7
   8 public class Lattice<T> {
   9
  10   private Hashtable<T, Set<T>> table;
  11   int size;
  12
  13   private T top;
  14   private T bottom;
  15
  16   public Lattice(T top, T bottom) {
  17     table = new Hashtable<T, Set<T>>();
  18     this.top = top;
  19     this.bottom = bottom;
  20
  21     table.put(top, new HashSet<T>());
  22
  23   }
  24
  25   public T getTopItem() {
  26     return top;
  27   }
  28
  29   public T getBottomItem() {
  30     return bottom;
  31   }
  32
  33   public Set<T> getKeySet() {
  34     return table.keySet();
  35   }
  36
  37   public boolean put(T key, T value) {
  38     Set<T> s;
  39
  40     Set<T> topNeighbor = table.get(top);
  41
  42     if (table.containsKey(key)) {
  43       s = table.get(key);
  44     } else {
  45       // new key, need to be connected with top
  46       topNeighbor.add(key);
  47
  48       s = new HashSet<T>();
  49       table.put(key, s);
  50     }
  51     if (value != null && !s.contains(value)) {
  52       size++;
  53       s.add(value);
  54
  55       if (!table.containsKey(value)) {
  56         Set<T> lowerNeighbor = new HashSet<T>();
  57         lowerNeighbor.add(bottom);
  58         table.put(value, lowerNeighbor);
  59       }
  60
  61       // if value is already connected with top, it is no longer to be
  62       topNeighbor.remove(value);
  63
  64       // if key is already connected with bottom,, it is no longer to be
  65       table.get(key).remove(getBottomItem());
  66
  67       return true;
  68     } else
  69       return false;
  70   }
  71
  72   public boolean isIntroducingCycle(T key) {
  73
  74     Set<T> reachableSet = new HashSet<T>();
  75     Set<T> neighborSet = get(key);
  76
  77     if (neighborSet == null) {
  78       return false;
  79     } else {
  80       reachableSet.addAll(neighborSet);
  81     }
  82
  83     int oldReachableSize;
  84     do {
  85       oldReachableSize = reachableSet.size();
  86       Set<T> nextLevelNeighbors = new HashSet<T>();
  87       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
  88         T element = iterator.next();
  89         Set<T> neighbors = get(element);
  90         if (neighbors != null) {
  91           nextLevelNeighbors.addAll(neighbors);
  92           reachableSet.addAll(neighbors);
  93         }
  94
  95         if (reachableSet.contains(key)) {
  96           // found cycle
  97           return true;
  98         }
  99       }
 100       neighborSet = nextLevelNeighbors;
 101     } while (oldReachableSize != reachableSet.size());
 102
 103     return false;
 104   }
 105
 106   public Set<T> get(T key) {
 107     return table.get(key);
 108   }
 109
 110   public boolean containsKey(T o) {
 111     return table.containsKey(o);
 112   }
 113
 114   public boolean isGreaterThan(T a, T b) {
 115
 116     if (a.equals(top)) {
 117       if (b.equals(top)) {
 118         return false;
 119       }
 120       return true;
 121     }
 122     if (b.equals(top)) {
 123       return false;
 124     }
 125     if (a.equals(bottom)) {
 126       return false;
 127     }
 128     if (b.equals(bottom)) {
 129       return true;
 130     }
 131
 132     Set<T> neighborSet = get(a);
 133
 134     if (neighborSet == null) {
 135       return false;
 136     } else if (neighborSet.contains(b)) {
 137       return true;
 138     } else {
 139       boolean reachable = false;
 140       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 141         T neighbor = iterator.next();
 142         reachable = reachable || isGreaterThan(neighbor, b);
 143       }
 144       return reachable;
 145     }
 146   }
 147
 148   public T getGLB(Set<T> inputSet) {
 149
 150     Set<T> lowerSet = new HashSet<T>();
 151
 152     // get lower set of input locations
 153     for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
 154       T element = iterator.next();
 155       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
 156     }
 157
 158     // calculate the greatest element of lower set
 159     // find an element A, where every lower bound B of lowerSet, B<A
 160     for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
 161       T lowerElement = iterator.next();
 162       boolean isGreaterThanAll = true;
 163       for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 164         T e = iterator2.next();
 165         if (!lowerElement.equals(e)) {
 166           if (!isGreaterThan(lowerElement, e)) {
 167             isGreaterThanAll = false;
 168             break;
 169           }
 170         }
 171       }
 172       if (isGreaterThanAll) {
 173         return lowerElement;
 174       }
 175     }
 176     return null;
 177   }
 178
 179   public Set<T> getLowerSet(T element, Set<T> lowerSet) {
 180
 181     Set<T> neighborSet = get(element);
 182     if (neighborSet != null) {
 183       lowerSet.addAll(neighborSet);
 184       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 185         T neighbor = iterator.next();
 186         lowerSet = getLowerSet(neighbor, lowerSet);
 187       }
 188     }
 189     return lowerSet;
 190   }
 191
 192 }