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) {
38 if (table.containsKey(key)) {
41 // new key, need to be connected with top/bottom
43 table.get(top).add(key);
44 Set<T> neightborSet = new HashSet<T>();
45 neightborSet.add(bottom);
46 table.put(key, neightborSet);
51 public boolean put(T key, T value) {
54 Set<T> topNeighbor = table.get(top);
56 if (table.containsKey(key)) {
59 // new key, need to be connected with top
65 if (value != null && !s.contains(value)) {
69 if (!table.containsKey(value)) {
70 Set<T> lowerNeighbor = new HashSet<T>();
71 lowerNeighbor.add(bottom);
72 table.put(value, lowerNeighbor);
75 // if value is already connected with top, it is no longer to be
76 topNeighbor.remove(value);
78 // if key is already connected with bottom,, it is no longer to be
79 table.get(key).remove(getBottomItem());
86 public boolean isIntroducingCycle(T key) {
88 Set<T> reachableSet = new HashSet<T>();
89 Set<T> neighborSet = get(key);
91 if (neighborSet == null) {
94 reachableSet.addAll(neighborSet);
99 oldReachableSize = reachableSet.size();
100 Set<T> nextLevelNeighbors = new HashSet<T>();
101 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
102 T element = iterator.next();
103 Set<T> neighbors = get(element);
104 if (neighbors != null) {
105 nextLevelNeighbors.addAll(neighbors);
106 reachableSet.addAll(neighbors);
109 if (reachableSet.contains(key)) {
114 neighborSet = nextLevelNeighbors;
115 } while (oldReachableSize != reachableSet.size());
120 public Set<T> get(T key) {
121 return table.get(key);
124 public boolean containsKey(T o) {
125 return table.containsKey(o);
128 public boolean isComparable(T a, T b) {
130 Set<T> neighborSet = get(a);
132 if (neighborSet == null) {
134 } else if (neighborSet.contains(b)) {
137 boolean reachable = false;
138 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
139 T neighbor = iterator.next();
140 reachable = reachable || isComparable(neighbor, b);
147 public boolean isGreaterThan(T a, T b) {
158 if (a.equals(bottom)) {
161 if (b.equals(bottom)) {
165 Set<T> neighborSet = get(a);
167 if (neighborSet == null) {
169 } else if (neighborSet.contains(b)) {
172 boolean reachable = false;
173 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
174 T neighbor = iterator.next();
175 reachable = reachable || isGreaterThan(neighbor, b);
181 public T getGLB(Set<T> inputSet) {
183 Set<T> lowerSet = new HashSet<T>();
185 // get lower set of input locations
186 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
187 T element = iterator.next();
188 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
189 lowerSet.add(element);
192 // an element of lower bound should be lower than every input set
193 Set<T> toberemoved = new HashSet<T>();
194 for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
195 T inputElement = inputIterator.next();
197 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
198 T lowerElement = (T) iterator.next();
199 if (!inputElement.equals(lowerElement)) {
200 if (!isGreaterThan(inputElement, lowerElement)) {
201 toberemoved.add(lowerElement);
206 lowerSet.removeAll(toberemoved);
208 // calculate the greatest element of lower set
209 // find an element A, where every lower bound B of lowerSet, B<A
210 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
211 T lowerElement = iterator.next();
212 boolean isGreaterThanAll = true;
213 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
214 T e = iterator2.next();
215 if (!lowerElement.equals(e)) {
216 if (!isGreaterThan(lowerElement, e)) {
217 isGreaterThanAll = false;
222 if (isGreaterThanAll) {
229 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
231 Set<T> neighborSet = get(element);
232 if (neighborSet != null) {
233 lowerSet.addAll(neighborSet);
234 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
235 T neighbor = iterator.next();
236 lowerSet = getLowerSet(neighbor, lowerSet);
242 public Set<Pair<T, T>> getOrderingPairSet() {
243 // return the set of pairs in the lattice
245 Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
247 Set<T> visited = new HashSet<T>();
248 Set<T> needtovisit = new HashSet<T>();
249 needtovisit.add(top);
251 while (!needtovisit.isEmpty()) {
252 T key = needtovisit.iterator().next();
253 Set<T> lowerSet = table.get(key);
254 if (lowerSet != null) {
255 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
256 T lowerItem = (T) iterator.next();
257 set.add(new Pair(key, lowerItem));
258 if (!visited.contains(key)) {
259 needtovisit.add(lowerItem);
264 needtovisit.remove(key);