package Util; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; import java.util.Set; public class Lattice { private Hashtable> table; int size; private T top; private T bottom; public Lattice(T top, T bottom) { table = new Hashtable>(); this.top = top; this.bottom = bottom; table.put(top, new HashSet()); } public T getTopItem() { return top; } public T getBottomItem() { return bottom; } public Set getKeySet() { return table.keySet(); } public boolean put(T key, T value) { Set s; Set topNeighbor = table.get(top); if (table.containsKey(key)) { s = table.get(key); } else { // new key, need to be connected with top topNeighbor.add(key); s = new HashSet(); table.put(key, s); } if (value != null && !s.contains(value)) { size++; s.add(value); if (!table.containsKey(value)) { Set lowerNeighbor = new HashSet(); 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 is already connected with bottom,, it is no longer to be table.get(key).remove(getBottomItem()); return true; } else return false; } public boolean isIntroducingCycle(T key) { Set reachableSet = new HashSet(); Set neighborSet = get(key); if (neighborSet == null) { return false; } else { reachableSet.addAll(neighborSet); } int oldReachableSize; do { oldReachableSize = reachableSet.size(); Set nextLevelNeighbors = new HashSet(); for (Iterator iterator = neighborSet.iterator(); iterator.hasNext();) { T element = iterator.next(); Set neighbors = get(element); if (neighbors != null) { nextLevelNeighbors.addAll(neighbors); reachableSet.addAll(neighbors); } if (reachableSet.contains(key)) { // found cycle return true; } } neighborSet = nextLevelNeighbors; } while (oldReachableSize != reachableSet.size()); return false; } public Set get(T key) { return table.get(key); } public boolean containsKey(T o) { return table.containsKey(o); } public boolean isGreaterThan(T a, T b) { if (a.equals(top)) { if (b.equals(top)) { return false; } return true; } if (b.equals(top)) { return false; } if (a.equals(bottom)) { return false; } if (b.equals(bottom)) { return true; } Set neighborSet = get(a); if (neighborSet == null) { return false; } else if (neighborSet.contains(b)) { return true; } else { boolean reachable = false; for (Iterator iterator = neighborSet.iterator(); iterator.hasNext();) { T neighbor = iterator.next(); reachable = reachable || isGreaterThan(neighbor, b); } return reachable; } } public T getGLB(Set inputSet) { Set lowerSet = new HashSet(); // get lower set of input locations for (Iterator iterator = inputSet.iterator(); iterator.hasNext();) { T element = iterator.next(); lowerSet.addAll(getLowerSet(element, new HashSet())); } // calculate the greatest element of lower set // find an element A, where every lower bound B of lowerSet, B iterator = lowerSet.iterator(); iterator.hasNext();) { T lowerElement = iterator.next(); boolean isGreaterThanAll = true; for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) { T e = iterator2.next(); if (!lowerElement.equals(e)) { if (!isGreaterThan(lowerElement, e)) { isGreaterThanAll = false; break; } } } if (isGreaterThanAll) { return lowerElement; } } return null; } public Set getLowerSet(T element, Set lowerSet) { Set neighborSet = get(element); if (neighborSet != null) { lowerSet.addAll(neighborSet); for (Iterator iterator = neighborSet.iterator(); iterator.hasNext();) { T neighbor = iterator.next(); lowerSet = getLowerSet(neighbor, lowerSet); } } return lowerSet; } }