import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
+import java.util.Map;
import java.util.Set;
public class Lattice<T> {
this.bottom = bottom;
table.put(top, new HashSet<T>());
+ table.put(bottom, new HashSet<T>());
}
return table.keySet();
}
+ public Map<T, Set<T>> getTable() {
+ return table;
+ }
+
+ public void setTable(Map<T, Set<T>> in) {
+ Set<T> keySet = in.keySet();
+ for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+ T key = (T) iterator.next();
+ Set<T> setIn = in.get(key);
+ Set<T> newSet = new HashSet<T>();
+ newSet.addAll(setIn);
+ table.put(key, newSet);
+ }
+ }
+
public boolean put(T key) {
if (table.containsKey(key)) {
return false;
}
public boolean put(T key, T value) {
+
+ if (isComparable(key, value) && isGreaterThan(key, value)) {
+ // this relation already exists
+ return false;
+ }
+
Set<T> s;
Set<T> topNeighbor = table.get(top);
-
if (table.containsKey(key)) {
s = table.get(key);
} else {
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);
}
// if value is already connected with top, it is no longer to be
- topNeighbor.remove(value);
+ if (!key.equals(top)) {
+ 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
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;
boolean reachable = false;
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;
}
while (!needtovisit.isEmpty()) {
T key = needtovisit.iterator().next();
Set<T> lowerSet = table.get(key);
- if(lowerSet!=null){
+ if (lowerSet != null) {
for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
T lowerItem = (T) iterator.next();
set.add(new Pair(key, lowerItem));