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