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 (!s.contains(value)) {
  25       size++;
  26       s.add(value);
  27       return true;
  28     } else
  29       return false;
  30   }
  31
  32   public Set<T> get(T key) {
  33     return table.get(key);
  34   }
  35
  36   public boolean containsKey(T o) {
  37     return table.containsKey(o);
  38   }
  39
  40   public boolean isGreaterThan(T a, T b) {
  41
  42     Set<T> neighborSet = get(a);
  43     System.out.println("neightborSet of " + a + "=" + neighborSet);
  44
  45     if (neighborSet == null) {
  46       return false;
  47     } else if (neighborSet.contains(b)) {
  48       return true;
  49     } else {
  50       boolean reachable = false;
  51       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
  52         T neighbor = iterator.next();
  53         reachable = reachable || isGreaterThan(neighbor, b);
  54       }
  55       return reachable;
  56     }
  57   }
  58
  59   public T getGLB(Set<T> inputSet) {
  60
  61     Set<T> lowerSet = new HashSet<T>();
  62
  63     // get lower set of input locations
  64     for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
  65       T element = iterator.next();
  66       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
  67     }
  68
  69     // calculate the greatest element of lower set
  70     // find an element A, where every lower bound B of lowerSet, B<A
  71     for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
  72       T lowerElement = iterator.next();
  73       boolean isGreaterThanAll = true;
  74       for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
  75         T e = iterator2.next();
  76         if (!lowerElement.equals(e)) {
  77           if (!isGreaterThan(lowerElement, e)) {
  78             isGreaterThanAll = false;
  79             break;
  80           }
  81         }
  82       }
  83       if (isGreaterThanAll) {
  84         return lowerElement;
  85       }
  86     }
  87     return null;
  88   }
  89
  90   public Set<T> getLowerSet(T element, Set<T> lowerSet) {
  91
  92     Set<T> neighborSet = get(element);
  93     if (neighborSet != null) {
  94       lowerSet.addAll(neighborSet);
  95       for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
  96         T neighbor = iterator.next();
  97         lowerSet = getLowerSet(neighbor, lowerSet);
  98       }
  99     }
 100     return lowerSet;
 101   }
 102
 103 }