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