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, T value) {
  38     Set<T> s;
  39
  40     Set<T> topNeighbor = table.get(top);
  41
  42     if (table.containsKey(key)) {
  43       s = table.get(key);
  44     } else {
  45       // new key, need to be connected with top
  46       topNeighbor.add(key);
  47
  48       s = new HashSet<T>();
  49       table.put(key, s);
  50     }
  51     if (value != null && !s.contains(value)) {
  52       size++;
  53       s.add(value);
  54
  55       if (!table.containsKey(value)) {
  56         Set<T> lowerNeighbor = new HashSet<T>();
  57         lowerNeighbor.add(bottom);
  58         table.put(value, lowerNeighbor);
  59       }
  60
  61       // if value is already connected with top, it is no longer to be
  62       topNeighbor.remove(value);
  63
  64       // if key is already connected with bottom,, it is no longer to be
  65       table.get(key).remove(getBottomItem());
  66
  67       return true;
  68     } else
  69       return false;
  70   }
  71
  72   public boolean isIntroducingCycle(T key) {
  73
  74     Set<T> reachableSet = new HashSet<T>();
  75     Set<T> neighborSet = get(key);
  76
  77     if (neighborSet == null) {
  78       return false;
  79     } else {
  80       reachableSet.addAll(neighborSet);
  81     }
  82
  83     int oldReachableSize;
  84     do {
  85       oldReachableSize = reachableSet.size();
  86       Set<T> nextLevelNeighbors = new HashSet<T>();
  87       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext(); ) {
  88         T element = iterator.next();
  89         Set<T> neighbors = get(element);
  90         if (neighbors != null) {
  91           nextLevelNeighbors.addAll(neighbors);
  92           reachableSet.addAll(neighbors);
  93         }
  94
  95         if (reachableSet.contains(key)) {
  96           // found cycle
  97           return true;
  98         }
  99       }
 100       neighborSet = nextLevelNeighbors;
 101     } while (oldReachableSize != reachableSet.size());
 102
 103     return false;
 104   }
 105
 106   public Set<T> get(T key) {
 107     return table.get(key);
 108   }
 109
 110   public boolean containsKey(T o) {
 111     return table.containsKey(o);
 112   }
 113
 114   public boolean isGreaterThan(T a, T b) {
 115
 116     if (a.equals(top)) {
 117       if (b.equals(top)) {
 118         return false;
 119       }
 120       return true;
 121     }
 122     if (b.equals(top)) {
 123       return false;
 124     }
 125     if (a.equals(bottom)) {
 126       return false;
 127     }
 128     if (b.equals(bottom)) {
 129       return true;
 130     }
 131
 132     Set<T> neighborSet = get(a);
 133
 134     if (neighborSet == null) {
 135       return false;
 136     } else if (neighborSet.contains(b)) {
 137       return true;
 138     } else {
 139       boolean reachable = false;
 140       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext(); ) {
 141         T neighbor = iterator.next();
 142         reachable = reachable || isGreaterThan(neighbor, b);
 143       }
 144       return reachable;
 145     }
 146   }
 147
 148   public T getGLB(Set<T> inputSet) {
 149
 150     Set<T> lowerSet = new HashSet<T>();
 151
 152     // get lower set of input locations
 153     for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext(); ) {
 154       T element = iterator.next();
 155       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
 156       lowerSet.add(element);
 157     }
 158
 159     // an element of lower bound should be lower than every input set
 160     Set<T> toberemoved = new HashSet<T>();
 161     for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext(); ) {
 162       T inputElement = inputIterator.next();
 163
 164       for (Iterator iterator = lowerSet.iterator(); iterator.hasNext(); ) {
 165         T lowerElement = (T) iterator.next();
 166         if (!inputElement.equals(lowerElement)) {
 167           if (!isGreaterThan(inputElement, lowerElement)) {
 168             toberemoved.add(lowerElement);
 169           }
 170         }
 171       }
 172     }
 173     lowerSet.removeAll(toberemoved);
 174
 175     // calculate the greatest element of lower set
 176     // find an element A, where every lower bound B of lowerSet, B<A
 177     for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext(); ) {
 178       T lowerElement = iterator.next();
 179       boolean isGreaterThanAll = true;
 180       for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext(); ) {
 181         T e = iterator2.next();
 182         if (!lowerElement.equals(e)) {
 183           if (!isGreaterThan(lowerElement, e)) {
 184             isGreaterThanAll = false;
 185             break;
 186           }
 187         }
 188       }
 189       if (isGreaterThanAll) {
 190         return lowerElement;
 191       }
 192     }
 193     return null;
 194   }
 195
 196   public Set<T> getLowerSet(T element, Set<T> lowerSet) {
 197
 198     Set<T> neighborSet = get(element);
 199     if (neighborSet != null) {
 200       lowerSet.addAll(neighborSet);
 201       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext(); ) {
 202         T neighbor = iterator.next();
 203         lowerSet = getLowerSet(neighbor, lowerSet);
 204       }
 205     }
 206     return lowerSet;
 207   }
 208
 209 }