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