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.Map;
   7 import java.util.Set;
   8
   9 public class Lattice<T> {
  10
  11   private Hashtable<T, Set<T>> table;
  12   int size;
  13
  14   private T top;
  15   private T bottom;
  16
  17   public Lattice(T top, T bottom) {
  18     table = new Hashtable<T, Set<T>>();
  19     this.top = top;
  20     this.bottom = bottom;
  21
  22     table.put(top, new HashSet<T>());
  23
  24   }
  25
  26   public T getTopItem() {
  27     return top;
  28   }
  29
  30   public T getBottomItem() {
  31     return bottom;
  32   }
  33
  34   public Set<T> getKeySet() {
  35     return table.keySet();
  36   }
  37
  38   public Map<T, Set<T>> getTable() {
  39     return table;
  40   }
  41
  42   public boolean put(T key) {
  43     if (table.containsKey(key)) {
  44       return false;
  45     } else {
  46       // new key, need to be connected with top/bottom
  47       size++;
  48       table.get(top).add(key);
  49       Set<T> neightborSet = new HashSet<T>();
  50       neightborSet.add(bottom);
  51       table.put(key, neightborSet);
  52       return true;
  53     }
  54   }
  55
  56   public boolean put(T key, T value) {
  57     Set<T> s;
  58
  59     Set<T> topNeighbor = table.get(top);
  60
  61     if (table.containsKey(key)) {
  62       s = table.get(key);
  63     } else {
  64       // new key, need to be connected with top
  65       topNeighbor.add(key);
  66
  67       s = new HashSet<T>();
  68       table.put(key, s);
  69     }
  70     if (value != null && !s.contains(value)) {
  71       size++;
  72       s.add(value);
  73
  74       if ((!table.containsKey(value)) && (!value.equals(bottom))) {
  75         Set<T> lowerNeighbor = new HashSet<T>();
  76         lowerNeighbor.add(bottom);
  77         table.put(value, lowerNeighbor);
  78       }
  79
  80       // if value is already connected with top, it is no longer to be
  81       topNeighbor.remove(value);
  82
  83       // if key is already connected with bottom,, it is no longer to be
  84       if (!value.equals(getBottomItem())) {
  85         table.get(key).remove(getBottomItem());
  86       }
  87
  88       return true;
  89     } else
  90       return false;
  91   }
  92
  93   public boolean isIntroducingCycle(T key) {
  94
  95     Set<T> reachableSet = new HashSet<T>();
  96     Set<T> neighborSet = get(key);
  97
  98     if (neighborSet == null) {
  99       return false;
 100     } else {
 101       reachableSet.addAll(neighborSet);
 102     }
 103
 104     int oldReachableSize;
 105     do {
 106       oldReachableSize = reachableSet.size();
 107       Set<T> nextLevelNeighbors = new HashSet<T>();
 108       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 109         T element = iterator.next();
 110         Set<T> neighbors = get(element);
 111         if (neighbors != null) {
 112           nextLevelNeighbors.addAll(neighbors);
 113           reachableSet.addAll(neighbors);
 114         }
 115
 116         if (reachableSet.contains(key)) {
 117           // found cycle
 118           return true;
 119         }
 120       }
 121       neighborSet = nextLevelNeighbors;
 122     } while (oldReachableSize != reachableSet.size());
 123
 124     return false;
 125   }
 126
 127   public Set<T> get(T key) {
 128     return table.get(key);
 129   }
 130
 131   public boolean containsKey(T o) {
 132     return table.containsKey(o);
 133   }
 134
 135   public boolean isComparable(T a, T b) {
 136
 137     Set<T> neighborSet = get(a);
 138
 139     if (a.equals(b)) {
 140       return true;
 141     } else if (neighborSet == null) {
 142       return false;
 143     } else if (neighborSet.contains(b)) {
 144       return true;
 145     } else {
 146       boolean reachable = false;
 147       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 148         T neighbor = iterator.next();
 149         reachable = reachable || isComparable(neighbor, b);
 150       }
 151       return reachable;
 152     }
 153
 154   }
 155
 156   public boolean isGreaterThan(T a, T b) {
 157
 158     Set<T> visited = new HashSet<T>();
 159     return isGreaterThan(a, b, visited);
 160
 161   }
 162
 163   public boolean isGreaterThan(T a, T b, Set<T> visited) {
 164
 165     if (a.equals(b)) {
 166       return false;
 167     }
 168
 169     if (a.equals(top)) {
 170       if (b.equals(top)) {
 171         return false;
 172       }
 173       return true;
 174     }
 175     if (b.equals(top)) {
 176       return false;
 177     }
 178     if (a.equals(bottom)) {
 179       return false;
 180     }
 181     if (b.equals(bottom)) {
 182       return true;
 183     }
 184
 185     Set<T> neighborSet = get(a);
 186
 187     if (neighborSet == null) {
 188       return false;
 189     } else if (neighborSet.contains(b)) {
 190       return true;
 191     } else {
 192       boolean reachable = false;
 193       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 194         T neighbor = iterator.next();
 195         if (!visited.contains(neighbor)) {
 196           visited.add(neighbor);
 197           reachable = reachable || isGreaterThan(neighbor, b, visited);
 198         }
 199       }
 200       return reachable;
 201     }
 202   }
 203
 204   public T getGLB(Set<T> inputSet) {
 205
 206     Set<T> lowerSet = new HashSet<T>();
 207
 208     // get lower set of input locations
 209     for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
 210       T element = iterator.next();
 211       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
 212       lowerSet.add(element);
 213     }
 214
 215     // an element of lower bound should be lower than every input set
 216     Set<T> toberemoved = new HashSet<T>();
 217     for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
 218       T inputElement = inputIterator.next();
 219
 220       for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
 221         T lowerElement = (T) iterator.next();
 222         if (!inputElement.equals(lowerElement)) {
 223           if (!isGreaterThan(inputElement, lowerElement)) {
 224             toberemoved.add(lowerElement);
 225           }
 226         }
 227       }
 228     }
 229     lowerSet.removeAll(toberemoved);
 230
 231     // calculate the greatest element of lower set
 232     // find an element A, where every lower bound B of lowerSet, B<A
 233     for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
 234       T lowerElement = iterator.next();
 235       boolean isGreaterThanAll = true;
 236       for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 237         T e = iterator2.next();
 238         if (!lowerElement.equals(e)) {
 239           if (!isGreaterThan(lowerElement, e)) {
 240             isGreaterThanAll = false;
 241             break;
 242           }
 243         }
 244       }
 245       if (isGreaterThanAll) {
 246         return lowerElement;
 247       }
 248     }
 249     return null;
 250   }
 251
 252   public Set<T> getLowerSet(T element, Set<T> lowerSet) {
 253
 254     Set<T> neighborSet = get(element);
 255     if (neighborSet != null) {
 256       lowerSet.addAll(neighborSet);
 257       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 258         T neighbor = iterator.next();
 259         lowerSet = getLowerSet(neighbor, lowerSet);
 260       }
 261     }
 262     return lowerSet;
 263   }
 264
 265   public Set<Pair<T, T>> getOrderingPairSet() {
 266     // return the set of pairs in the lattice
 267
 268     Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
 269
 270     Set<T> visited = new HashSet<T>();
 271     Set<T> needtovisit = new HashSet<T>();
 272     needtovisit.add(top);
 273
 274     while (!needtovisit.isEmpty()) {
 275       T key = needtovisit.iterator().next();
 276       Set<T> lowerSet = table.get(key);
 277       if (lowerSet != null) {
 278         for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
 279           T lowerItem = (T) iterator.next();
 280           set.add(new Pair(key, lowerItem));
 281           if (!visited.contains(key)) {
 282             needtovisit.add(lowerItem);
 283           }
 284         }
 285       }
 286       visited.add(key);
 287       needtovisit.remove(key);
 288     }
 289     return set;
 290   }
 291
 292 }