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