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