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