3 import java.util.HashSet;
4 import java.util.Hashtable;
5 import java.util.Iterator;
8 public class Lattice<T> {
10 private Hashtable<T, Set<T>> table;
16 public Lattice(T top, T bottom) {
17 table = new Hashtable<T, Set<T>>();
21 table.put(top, new HashSet<T>());
25 public T getTopItem() {
29 public T getBottomItem() {
33 public boolean put(T key, T value) {
36 Set<T> topNeighbor = table.get(top);
38 if (table.containsKey(key)) {
41 // new key, need to be connected with top
47 if (value != null && !s.contains(value)) {
51 if (!table.containsKey(value)) {
52 Set<T> lowerNeighbor = new HashSet<T>();
53 lowerNeighbor.add(bottom);
54 table.put(value, lowerNeighbor);
57 // if value is already connected with top, it is no longer to be
58 topNeighbor.remove(value);
60 // if key is already connected with bottom,, it is no longer to be
61 table.get(key).remove(getBottomItem());
68 public boolean isIntroducingCycle(T key) {
70 Set<T> reachableSet = new HashSet<T>();
71 Set<T> neighborSet = get(key);
73 if (neighborSet == null) {
76 reachableSet.addAll(neighborSet);
81 oldReachableSize = reachableSet.size();
82 Set<T> nextLevelNeighbors = new HashSet<T>();
83 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
84 T element = iterator.next();
85 Set<T> neighbors = get(element);
86 if (neighbors != null) {
87 nextLevelNeighbors.addAll(neighbors);
88 reachableSet.addAll(neighbors);
91 if (reachableSet.contains(key)) {
96 neighborSet = nextLevelNeighbors;
97 } while (oldReachableSize != reachableSet.size());
102 public Set<T> get(T key) {
103 return table.get(key);
106 public boolean containsKey(T o) {
107 return table.containsKey(o);
110 public boolean isGreaterThan(T a, T b) {
112 Set<T> neighborSet = get(a);
114 if (neighborSet == null) {
116 } else if (neighborSet.contains(b)) {
119 boolean reachable = false;
120 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
121 T neighbor = iterator.next();
122 reachable = reachable || isGreaterThan(neighbor, b);
128 public T getGLB(Set<T> inputSet) {
130 Set<T> lowerSet = new HashSet<T>();
132 // get lower set of input locations
133 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
134 T element = iterator.next();
135 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
138 // calculate the greatest element of lower set
139 // find an element A, where every lower bound B of lowerSet, B<A
140 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
141 T lowerElement = iterator.next();
142 boolean isGreaterThanAll = true;
143 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
144 T e = iterator2.next();
145 if (!lowerElement.equals(e)) {
146 if (!isGreaterThan(lowerElement, e)) {
147 isGreaterThanAll = false;
152 if (isGreaterThanAll) {
159 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
161 Set<T> neighborSet = get(element);
162 if (neighborSet != null) {
163 lowerSet.addAll(neighborSet);
164 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
165 T neighbor = iterator.next();
166 lowerSet = getLowerSet(neighbor, lowerSet);