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 { 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()); table.put(bottom, new HashSet()); } public T getTopItem() { return top; } public T getBottomItem() { return bottom; } public Set getKeySet() { return table.keySet(); } public Map> getTable() { return table; } public void setTable(Map> in) { Set keySet = in.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { T key = (T) iterator.next(); Set setIn = in.get(key); Set newSet = new HashSet(); newSet.addAll(setIn); table.put(key, newSet); } } 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 neightborSet = new HashSet(); neightborSet.add(bottom); table.put(key, neightborSet); return true; } } 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)) && (!value.equals(bottom))) { 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 if (!value.equals(getBottomItem())) { 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 isComparable(T a, T b) { Set 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 iterator = neighborSet.iterator(); iterator.hasNext();) { T neighbor = iterator.next(); reachable = reachable || isComparable(neighbor, b); } return reachable; } } public boolean isGreaterThan(T a, T b) { Set visited = new HashSet(); return isGreaterThan(a, b, visited); } public boolean isGreaterThan(T a, T b, Set visited) { if (a.equals(b)) { return false; } 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(); if (!visited.contains(neighbor)) { visited.add(neighbor); reachable = reachable || isGreaterThan(neighbor, b, visited); } } 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())); lowerSet.add(element); } // an element of lower bound should be lower than every input set Set toberemoved = new HashSet(); for (Iterator inputIterator = inputSet.iterator(); inputIterator.hasNext();) { T inputElement = inputIterator.next(); for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) { T lowerElement = (T) iterator.next(); if (!inputElement.equals(lowerElement)) { if (!isGreaterThan(inputElement, lowerElement)) { toberemoved.add(lowerElement); } } } } lowerSet.removeAll(toberemoved); // 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; } public Set> getOrderingPairSet() { // return the set of pairs in the lattice Set> set = new HashSet>(); Set visited = new HashSet(); Set needtovisit = new HashSet(); needtovisit.add(top); while (!needtovisit.isEmpty()) { T key = needtovisit.iterator().next(); Set 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; } }