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   private Hashtable<T, Set<T>> table;
  10   int size;
  11
  12   public Lattice() {
  13     table = new Hashtable<T, Set<T>>();
  14   }
  15
  16   public boolean put(T key, T value) {
  17     Set<T> s;
  18     if (table.containsKey(key)) {
  19       s = table.get(key);
  20     } else {
  21       s = new HashSet<T>();
  22       table.put(key, s);
  23     }
  24     if (value!=null && !s.contains(value)) {
  25       size++;
  26       s.add(value);
  27       return true;
  28     } else
  29       return false;
  30   }
  31
  32   public boolean isIntroducingCycle(T key) {
  33
  34     Set<T> reachableSet = new HashSet<T>();
  35     Set<T> neighborSet = get(key);
  36
  37     if (neighborSet == null) {
  38       return false;
  39     } else {
  40       reachableSet.addAll(neighborSet);
  41     }
  42
  43     int oldReachableSize;
  44     do {
  45       oldReachableSize = reachableSet.size();
  46       Set<T> nextLevelNeighbors = new HashSet<T>();
  47       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
  48         T element = iterator.next();
  49         Set<T> neighbors = get(element);
  50         if (neighbors != null) {
  51           nextLevelNeighbors.addAll(neighbors);
  52           reachableSet.addAll(neighbors);
  53         }
  54
  55         if (reachableSet.contains(key)) {
  56           // found cycle
  57           return true;
  58         }
  59       }
  60       neighborSet = nextLevelNeighbors;
  61     } while (oldReachableSize != reachableSet.size());
  62
  63     return false;
  64   }
  65
  66   public Set<T> get(T key) {
  67     return table.get(key);
  68   }
  69
  70   public boolean containsKey(T o) {
  71     return table.containsKey(o);
  72   }
  73
  74   public boolean isGreaterThan(T a, T b) {
  75
  76     Set<T> neighborSet = get(a);
  77
  78     if (neighborSet == null) {
  79       return false;
  80     } else if (neighborSet.contains(b)) {
  81       return true;
  82     } else {
  83       boolean reachable = false;
  84       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
  85         T neighbor = iterator.next();
  86         reachable = reachable || isGreaterThan(neighbor, b);
  87       }
  88       return reachable;
  89     }
  90   }
  91
  92   public T getGLB(Set<T> inputSet) {
  93
  94     Set<T> lowerSet = new HashSet<T>();
  95
  96     // get lower set of input locations
  97     for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
  98       T element = iterator.next();
  99       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
 100     }
 101
 102     // calculate the greatest element of lower set
 103     // find an element A, where every lower bound B of lowerSet, B<A
 104     for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
 105       T lowerElement = iterator.next();
 106       boolean isGreaterThanAll = true;
 107       for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 108         T e = iterator2.next();
 109         if (!lowerElement.equals(e)) {
 110           if (!isGreaterThan(lowerElement, e)) {
 111             isGreaterThanAll = false;
 112             break;
 113           }
 114         }
 115       }
 116       if (isGreaterThanAll) {
 117         return lowerElement;
 118       }
 119     }
 120     return null;
 121   }
 122
 123   public Set<T> getLowerSet(T element, Set<T> lowerSet) {
 124
 125     Set<T> neighborSet = get(element);
 126     if (neighborSet != null) {
 127       lowerSet.addAll(neighborSet);
 128       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
 129         T neighbor = iterator.next();
 130         lowerSet = getLowerSet(neighbor, lowerSet);
 131       }
 132     }
 133     return lowerSet;
 134   }
 135
 136 }