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     Set<T> neighborSet = get(a);
 117
 118     if (neighborSet == null) {
 119       return false;
 120     } else if (neighborSet.contains(b)) {
 121       return true;
 122     } else {
 123       boolean reachable = false;
 124       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 125         T neighbor = iterator.next();
 126         reachable = reachable || isGreaterThan(neighbor, b);
 127       }
 128       return reachable;
 129     }
 130   }
 131
 132   public T getGLB(Set<T> inputSet) {
 133
 134     Set<T> lowerSet = new HashSet<T>();
 135
 136     // get lower set of input locations
 137     for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
 138       T element = iterator.next();
 139       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
 140     }
 141
 142     // calculate the greatest element of lower set
 143     // find an element A, where every lower bound B of lowerSet, B<A
 144     for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
 145       T lowerElement = iterator.next();
 146       boolean isGreaterThanAll = true;
 147       for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 148         T e = iterator2.next();
 149         if (!lowerElement.equals(e)) {
 150           if (!isGreaterThan(lowerElement, e)) {
 151             isGreaterThanAll = false;
 152             break;
 153           }
 154         }
 155       }
 156       if (isGreaterThanAll) {
 157         return lowerElement;
 158       }
 159     }
 160     return null;
 161   }
 162
 163   public Set<T> getLowerSet(T element, Set<T> lowerSet) {
 164
 165     Set<T> neighborSet = get(element);
 166     if (neighborSet != null) {
 167       lowerSet.addAll(neighborSet);
 168       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 169         T neighbor = iterator.next();
 170         lowerSet = getLowerSet(neighbor, lowerSet);
 171       }
 172     }
 173     return lowerSet;
 174   }
 175
 176 }