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)) {
  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     if (a.equals(b)) {
 159       return false;
 160     }
 161
 162     if (a.equals(top)) {
 163       if (b.equals(top)) {
 164         return false;
 165       }
 166       return true;
 167     }
 168     if (b.equals(top)) {
 169       return false;
 170     }
 171     if (a.equals(bottom)) {
 172       return false;
 173     }
 174     if (b.equals(bottom)) {
 175       return true;
 176     }
 177
 178     Set<T> neighborSet = get(a);
 179
 180     if (neighborSet == null) {
 181       return false;
 182     } else if (neighborSet.contains(b)) {
 183       return true;
 184     } else {
 185       boolean reachable = false;
 186       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 187         T neighbor = iterator.next();
 188         reachable = reachable || isGreaterThan(neighbor, b);
 189       }
 190       return reachable;
 191     }
 192   }
 193
 194   public T getGLB(Set<T> inputSet) {
 195
 196     Set<T> lowerSet = new HashSet<T>();
 197
 198     // get lower set of input locations
 199     for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
 200       T element = iterator.next();
 201       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
 202       lowerSet.add(element);
 203     }
 204
 205     // an element of lower bound should be lower than every input set
 206     Set<T> toberemoved = new HashSet<T>();
 207     for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
 208       T inputElement = inputIterator.next();
 209
 210       for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
 211         T lowerElement = (T) iterator.next();
 212         if (!inputElement.equals(lowerElement)) {
 213           if (!isGreaterThan(inputElement, lowerElement)) {
 214             toberemoved.add(lowerElement);
 215           }
 216         }
 217       }
 218     }
 219     lowerSet.removeAll(toberemoved);
 220
 221     // calculate the greatest element of lower set
 222     // find an element A, where every lower bound B of lowerSet, B<A
 223     for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
 224       T lowerElement = iterator.next();
 225       boolean isGreaterThanAll = true;
 226       for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 227         T e = iterator2.next();
 228         if (!lowerElement.equals(e)) {
 229           if (!isGreaterThan(lowerElement, e)) {
 230             isGreaterThanAll = false;
 231             break;
 232           }
 233         }
 234       }
 235       if (isGreaterThanAll) {
 236         return lowerElement;
 237       }
 238     }
 239     return null;
 240   }
 241
 242   public Set<T> getLowerSet(T element, Set<T> lowerSet) {
 243
 244     Set<T> neighborSet = get(element);
 245     if (neighborSet != null) {
 246       lowerSet.addAll(neighborSet);
 247       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 248         T neighbor = iterator.next();
 249         lowerSet = getLowerSet(neighbor, lowerSet);
 250       }
 251     }
 252     return lowerSet;
 253   }
 254
 255   public Set<Pair<T, T>> getOrderingPairSet() {
 256     // return the set of pairs in the lattice
 257
 258     Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
 259
 260     Set<T> visited = new HashSet<T>();
 261     Set<T> needtovisit = new HashSet<T>();
 262     needtovisit.add(top);
 263
 264     while (!needtovisit.isEmpty()) {
 265       T key = needtovisit.iterator().next();
 266       Set<T> lowerSet = table.get(key);
 267       if (lowerSet != null) {
 268         for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
 269           T lowerItem = (T) iterator.next();
 270           set.add(new Pair(key, lowerItem));
 271           if (!visited.contains(key)) {
 272             needtovisit.add(lowerItem);
 273           }
 274         }
 275       }
 276       visited.add(key);
 277       needtovisit.remove(key);
 278     }
 279     return set;
 280   }
 281
 282 }