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 isGreaterThan(T a, T b) {
139 if (a.equals(bottom)) {
142 if (b.equals(bottom)) {
146 Set<T> neighborSet = get(a);
148 if (neighborSet == null) {
150 } else if (neighborSet.contains(b)) {
153 boolean reachable = false;
154 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
155 T neighbor = iterator.next();
156 reachable = reachable || isGreaterThan(neighbor, b);
162 public T getGLB(Set<T> inputSet) {
164 Set<T> lowerSet = new HashSet<T>();
166 // get lower set of input locations
167 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
168 T element = iterator.next();
169 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
170 lowerSet.add(element);
173 // an element of lower bound should be lower than every input set
174 Set<T> toberemoved = new HashSet<T>();
175 for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
176 T inputElement = inputIterator.next();
178 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
179 T lowerElement = (T) iterator.next();
180 if (!inputElement.equals(lowerElement)) {
181 if (!isGreaterThan(inputElement, lowerElement)) {
182 toberemoved.add(lowerElement);
187 lowerSet.removeAll(toberemoved);
189 // calculate the greatest element of lower set
190 // find an element A, where every lower bound B of lowerSet, B<A
191 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
192 T lowerElement = iterator.next();
193 boolean isGreaterThanAll = true;
194 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
195 T e = iterator2.next();
196 if (!lowerElement.equals(e)) {
197 if (!isGreaterThan(lowerElement, e)) {
198 isGreaterThanAll = false;
203 if (isGreaterThanAll) {
210 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
212 Set<T> neighborSet = get(element);
213 if (neighborSet != null) {
214 lowerSet.addAll(neighborSet);
215 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
216 T neighbor = iterator.next();
217 lowerSet = getLowerSet(neighbor, lowerSet);
223 public Set<Pair<T, T>> getOrderingPairSet() {
224 // return the set of pairs in the lattice
226 Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
228 Set<T> visited = new HashSet<T>();
229 Set<T> needtovisit = new HashSet<T>();
230 needtovisit.add(top);
232 while (!needtovisit.isEmpty()) {
233 T key = needtovisit.iterator().next();
234 Set<T> lowerSet = table.get(key);
236 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
237 T lowerItem = (T) iterator.next();
238 set.add(new Pair(key, lowerItem));
239 if (!visited.contains(key)) {
240 needtovisit.add(lowerItem);
245 needtovisit.remove(key);