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