changes.

[IRC.git] / Robust / src / Util / Lattice.java

diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java
index de9c98b31fdb26e43b7ed15693da7152ea76bcfd..16c8936940414b957c8a51d44ccd690e5e5f6e1a 100644 (file)
--- a/Robust/src/Util/Lattice.java
+++ b/Robust/src/Util/Lattice.java
@@ -3,6 +3,7 @@ package Util;
 import java.util.HashSet;
 import java.util.Hashtable;
 import java.util.Iterator;
+import java.util.Map;
 import java.util.Set;
 
 public class Lattice<T> {
@@ -19,6 +20,7 @@ public class Lattice<T> {
     this.bottom = bottom;
 
     table.put(top, new HashSet<T>());
+    table.put(bottom, new HashSet<T>());
 
   }
 
@@ -34,6 +36,24 @@ public class Lattice<T> {
     return table.keySet();
   }
 
+  public Map<T, Set<T>> getTable() {
+    return table;
+  }
+
+  public boolean put(T key) {
+    if (table.containsKey(key)) {
+      return false;
+    } else {
+      // new key, need to be connected with top/bottom
+      size++;
+      table.get(top).add(key);
+      Set<T> neightborSet = new HashSet<T>();
+      neightborSet.add(bottom);
+      table.put(key, neightborSet);
+      return true;
+    }
+  }
+
   public boolean put(T key, T value) {
     Set<T> s;
 
@@ -52,7 +72,7 @@ public class Lattice<T> {
       size++;
       s.add(value);
 
-      if (!table.containsKey(value)) {
+      if ((!table.containsKey(value)) && (!value.equals(bottom))) {
         Set<T> lowerNeighbor = new HashSet<T>();
         lowerNeighbor.add(bottom);
         table.put(value, lowerNeighbor);
@@ -62,7 +82,9 @@ public class Lattice<T> {
       topNeighbor.remove(value);
 
       // if key is already connected with bottom,, it is no longer to be
-      table.get(key).remove(getBottomItem());
+      if (!value.equals(getBottomItem())) {
+        table.get(key).remove(getBottomItem());
+      }
 
       return true;
     } else
@@ -84,7 +106,7 @@ public class Lattice<T> {
     do {
       oldReachableSize = reachableSet.size();
       Set<T> nextLevelNeighbors = new HashSet<T>();
-      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext(); ) {
+      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
         T element = iterator.next();
         Set<T> neighbors = get(element);
         if (neighbors != null) {
@@ -111,8 +133,40 @@ public class Lattice<T> {
     return table.containsKey(o);
   }
 
+  public boolean isComparable(T a, T b) {
+
+    Set<T> neighborSet = get(a);
+
+    if (a.equals(b)) {
+      return true;
+    } else if (neighborSet == null) {
+      return false;
+    } else if (neighborSet.contains(b)) {
+      return true;
+    } else {
+      boolean reachable = false;
+      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
+        T neighbor = iterator.next();
+        reachable = reachable || isComparable(neighbor, b);
+      }
+      return reachable;
+    }
+
+  }
+
   public boolean isGreaterThan(T a, T b) {
 
+    Set<T> visited = new HashSet<T>();
+    return isGreaterThan(a, b, visited);
+
+  }
+
+  public boolean isGreaterThan(T a, T b, Set<T> visited) {
+
+    if (a.equals(b)) {
+      return false;
+    }
+
     if (a.equals(top)) {
       if (b.equals(top)) {
         return false;
@@ -137,9 +191,12 @@ public class Lattice<T> {
       return true;
     } else {
       boolean reachable = false;
-      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext(); ) {
+      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
         T neighbor = iterator.next();
-        reachable = reachable || isGreaterThan(neighbor, b);
+        if (!visited.contains(neighbor)) {
+          visited.add(neighbor);
+          reachable = reachable || isGreaterThan(neighbor, b, visited);
+        }
       }
       return reachable;
     }
@@ -150,7 +207,7 @@ public class Lattice<T> {
     Set<T> lowerSet = new HashSet<T>();
 
     // get lower set of input locations
-    for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext(); ) {
+    for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
       T element = iterator.next();
       lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
       lowerSet.add(element);
@@ -158,10 +215,10 @@ public class Lattice<T> {
 
     // an element of lower bound should be lower than every input set
     Set<T> toberemoved = new HashSet<T>();
-    for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext(); ) {
+    for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
       T inputElement = inputIterator.next();
 
-      for (Iterator iterator = lowerSet.iterator(); iterator.hasNext(); ) {
+      for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
         T lowerElement = (T) iterator.next();
         if (!inputElement.equals(lowerElement)) {
           if (!isGreaterThan(inputElement, lowerElement)) {
@@ -174,10 +231,10 @@ public class Lattice<T> {
 
     // calculate the greatest element of lower set
     // find an element A, where every lower bound B of lowerSet, B<A
-    for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext(); ) {
+    for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
       T lowerElement = iterator.next();
       boolean isGreaterThanAll = true;
-      for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext(); ) {
+      for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
         T e = iterator2.next();
         if (!lowerElement.equals(e)) {
           if (!isGreaterThan(lowerElement, e)) {
@@ -198,7 +255,7 @@ public class Lattice<T> {
     Set<T> neighborSet = get(element);
     if (neighborSet != null) {
       lowerSet.addAll(neighborSet);
-      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext(); ) {
+      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
         T neighbor = iterator.next();
         lowerSet = getLowerSet(neighbor, lowerSet);
       }
@@ -206,4 +263,31 @@ public class Lattice<T> {
     return lowerSet;
   }
 
+  public Set<Pair<T, T>> getOrderingPairSet() {
+    // return the set of pairs in the lattice
+
+    Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
+
+    Set<T> visited = new HashSet<T>();
+    Set<T> needtovisit = new HashSet<T>();
+    needtovisit.add(top);
+
+    while (!needtovisit.isEmpty()) {
+      T key = needtovisit.iterator().next();
+      Set<T> lowerSet = table.get(key);
+      if (lowerSet != null) {
+        for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
+          T lowerItem = (T) iterator.next();
+          set.add(new Pair(key, lowerItem));
+          if (!visited.contains(key)) {
+            needtovisit.add(lowerItem);
+          }
+        }
+      }
+      visited.add(key);
+      needtovisit.remove(key);
+    }
+    return set;
+  }
+
 }