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 Set<T> getKeySet() {
34 return table.keySet();
37 public boolean put(T key, T value) {
40 Set<T> topNeighbor = table.get(top);
42 if (table.containsKey(key)) {
45 // new key, need to be connected with top
51 if (value != null && !s.contains(value)) {
55 if (!table.containsKey(value)) {
56 Set<T> lowerNeighbor = new HashSet<T>();
57 lowerNeighbor.add(bottom);
58 table.put(value, lowerNeighbor);
61 // if value is already connected with top, it is no longer to be
62 topNeighbor.remove(value);
64 // if key is already connected with bottom,, it is no longer to be
65 table.get(key).remove(getBottomItem());
72 public boolean isIntroducingCycle(T key) {
74 Set<T> reachableSet = new HashSet<T>();
75 Set<T> neighborSet = get(key);
77 if (neighborSet == null) {
80 reachableSet.addAll(neighborSet);
85 oldReachableSize = reachableSet.size();
86 Set<T> nextLevelNeighbors = new HashSet<T>();
87 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
88 T element = iterator.next();
89 Set<T> neighbors = get(element);
90 if (neighbors != null) {
91 nextLevelNeighbors.addAll(neighbors);
92 reachableSet.addAll(neighbors);
95 if (reachableSet.contains(key)) {
100 neighborSet = nextLevelNeighbors;
101 } while (oldReachableSize != reachableSet.size());
106 public Set<T> get(T key) {
107 return table.get(key);
110 public boolean containsKey(T o) {
111 return table.containsKey(o);
114 public boolean isGreaterThan(T a, T b) {
125 if (a.equals(bottom)) {
128 if (b.equals(bottom)) {
132 Set<T> neighborSet = get(a);
134 if (neighborSet == null) {
136 } else if (neighborSet.contains(b)) {
139 boolean reachable = false;
140 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
141 T neighbor = iterator.next();
142 reachable = reachable || isGreaterThan(neighbor, b);
148 public T getGLB(Set<T> inputSet) {
150 Set<T> lowerSet = new HashSet<T>();
152 // get lower set of input locations
153 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
154 T element = iterator.next();
155 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
156 lowerSet.add(element);
159 // an element of lower bound should be lower than every input set
160 Set<T> toberemoved = new HashSet<T>();
161 for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
162 T inputElement = inputIterator.next();
164 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
165 T lowerElement = (T) iterator.next();
166 if (!inputElement.equals(lowerElement)) {
167 if (!isGreaterThan(inputElement, lowerElement)) {
168 toberemoved.add(lowerElement);
173 lowerSet.removeAll(toberemoved);
175 // calculate the greatest element of lower set
176 // find an element A, where every lower bound B of lowerSet, B<A
177 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
178 T lowerElement = iterator.next();
179 boolean isGreaterThanAll = true;
180 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
181 T e = iterator2.next();
182 if (!lowerElement.equals(e)) {
183 if (!isGreaterThan(lowerElement, e)) {
184 isGreaterThanAll = false;
189 if (isGreaterThanAll) {
196 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
198 Set<T> neighborSet = get(element);
199 if (neighborSet != null) {
200 lowerSet.addAll(neighborSet);
201 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
202 T neighbor = iterator.next();
203 lowerSet = getLowerSet(neighbor, lowerSet);