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 isComparable(T a, T b) {
 129
 130     Set<T> neighborSet = get(a);
 131
 132     if (neighborSet == null) {
 133       return false;
 134     } else if (neighborSet.contains(b)) {
 135       return true;
 136     } else {
 137       boolean reachable = false;
 138       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 139         T neighbor = iterator.next();
 140         reachable = reachable || isComparable(neighbor, b);
 141       }
 142       return reachable;
 143     }
 144
 145   }
 146
 147   public boolean isGreaterThan(T a, T b) {
 148
 149     if (a.equals(top)) {
 150       if (b.equals(top)) {
 151         return false;
 152       }
 153       return true;
 154     }
 155     if (b.equals(top)) {
 156       return false;
 157     }
 158     if (a.equals(bottom)) {
 159       return false;
 160     }
 161     if (b.equals(bottom)) {
 162       return true;
 163     }
 164
 165     Set<T> neighborSet = get(a);
 166
 167     if (neighborSet == null) {
 168       return false;
 169     } else if (neighborSet.contains(b)) {
 170       return true;
 171     } else {
 172       boolean reachable = false;
 173       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 174         T neighbor = iterator.next();
 175         reachable = reachable || isGreaterThan(neighbor, b);
 176       }
 177       return reachable;
 178     }
 179   }
 180
 181   public T getGLB(Set<T> inputSet) {
 182
 183     Set<T> lowerSet = new HashSet<T>();
 184
 185     // get lower set of input locations
 186     for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
 187       T element = iterator.next();
 188       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
 189       lowerSet.add(element);
 190     }
 191
 192     // an element of lower bound should be lower than every input set
 193     Set<T> toberemoved = new HashSet<T>();
 194     for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
 195       T inputElement = inputIterator.next();
 196
 197       for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
 198         T lowerElement = (T) iterator.next();
 199         if (!inputElement.equals(lowerElement)) {
 200           if (!isGreaterThan(inputElement, lowerElement)) {
 201             toberemoved.add(lowerElement);
 202           }
 203         }
 204       }
 205     }
 206     lowerSet.removeAll(toberemoved);
 207
 208     // calculate the greatest element of lower set
 209     // find an element A, where every lower bound B of lowerSet, B<A
 210     for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
 211       T lowerElement = iterator.next();
 212       boolean isGreaterThanAll = true;
 213       for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 214         T e = iterator2.next();
 215         if (!lowerElement.equals(e)) {
 216           if (!isGreaterThan(lowerElement, e)) {
 217             isGreaterThanAll = false;
 218             break;
 219           }
 220         }
 221       }
 222       if (isGreaterThanAll) {
 223         return lowerElement;
 224       }
 225     }
 226     return null;
 227   }
 228
 229   public Set<T> getLowerSet(T element, Set<T> lowerSet) {
 230
 231     Set<T> neighborSet = get(element);
 232     if (neighborSet != null) {
 233       lowerSet.addAll(neighborSet);
 234       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 235         T neighbor = iterator.next();
 236         lowerSet = getLowerSet(neighbor, lowerSet);
 237       }
 238     }
 239     return lowerSet;
 240   }
 241
 242   public Set<Pair<T, T>> getOrderingPairSet() {
 243     // return the set of pairs in the lattice
 244
 245     Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
 246
 247     Set<T> visited = new HashSet<T>();
 248     Set<T> needtovisit = new HashSet<T>();
 249     needtovisit.add(top);
 250
 251     while (!needtovisit.isEmpty()) {
 252       T key = needtovisit.iterator().next();
 253       Set<T> lowerSet = table.get(key);
 254       if (lowerSet != null) {
 255         for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
 256           T lowerItem = (T) iterator.next();
 257           set.add(new Pair(key, lowerItem));
 258           if (!visited.contains(key)) {
 259             needtovisit.add(lowerItem);
 260           }
 261         }
 262       }
 263       visited.add(key);
 264       needtovisit.remove(key);
 265     }
 266     return set;
 267   }
 268
 269 }