3 import java.util.HashSet;
4 import java.util.Hashtable;
5 import java.util.Iterator;
9 public class Lattice<T> {
11 private Hashtable<T, Set<T>> table;
17 public Lattice(T top, T bottom) {
18 table = new Hashtable<T, Set<T>>();
22 table.put(top, new HashSet<T>());
23 table.put(bottom, new HashSet<T>());
27 public T getTopItem() {
31 public T getBottomItem() {
35 public Set<T> getKeySet() {
36 return table.keySet();
39 public Map<T, Set<T>> getTable() {
43 public boolean put(T key) {
44 if (table.containsKey(key)) {
47 // new key, need to be connected with top/bottom
49 table.get(top).add(key);
50 Set<T> neightborSet = new HashSet<T>();
51 neightborSet.add(bottom);
52 table.put(key, neightborSet);
57 public boolean put(T key, T value) {
60 Set<T> topNeighbor = table.get(top);
62 if (table.containsKey(key)) {
65 // new key, need to be connected with top
71 if (value != null && !s.contains(value)) {
75 if ((!table.containsKey(value)) && (!value.equals(bottom))) {
76 Set<T> lowerNeighbor = new HashSet<T>();
77 lowerNeighbor.add(bottom);
78 table.put(value, lowerNeighbor);
81 // if value is already connected with top, it is no longer to be
82 topNeighbor.remove(value);
84 // if key is already connected with bottom,, it is no longer to be
85 if (!value.equals(getBottomItem())) {
86 table.get(key).remove(getBottomItem());
94 public boolean isIntroducingCycle(T key) {
96 Set<T> reachableSet = new HashSet<T>();
97 Set<T> neighborSet = get(key);
99 if (neighborSet == null) {
102 reachableSet.addAll(neighborSet);
105 int oldReachableSize;
107 oldReachableSize = reachableSet.size();
108 Set<T> nextLevelNeighbors = new HashSet<T>();
109 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
110 T element = iterator.next();
111 Set<T> neighbors = get(element);
112 if (neighbors != null) {
113 nextLevelNeighbors.addAll(neighbors);
114 reachableSet.addAll(neighbors);
117 if (reachableSet.contains(key)) {
122 neighborSet = nextLevelNeighbors;
123 } while (oldReachableSize != reachableSet.size());
128 public Set<T> get(T key) {
129 return table.get(key);
132 public boolean containsKey(T o) {
133 return table.containsKey(o);
136 public boolean isComparable(T a, T b) {
138 Set<T> neighborSet = get(a);
142 } else if (neighborSet == null) {
144 } else if (neighborSet.contains(b)) {
147 boolean reachable = false;
148 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
149 T neighbor = iterator.next();
150 reachable = reachable || isComparable(neighbor, b);
157 public boolean isGreaterThan(T a, T b) {
159 Set<T> visited = new HashSet<T>();
160 return isGreaterThan(a, b, visited);
164 public boolean isGreaterThan(T a, T b, Set<T> visited) {
179 if (a.equals(bottom)) {
182 if (b.equals(bottom)) {
186 Set<T> neighborSet = get(a);
188 if (neighborSet == null) {
190 } else if (neighborSet.contains(b)) {
193 boolean reachable = false;
194 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
195 T neighbor = iterator.next();
196 if (!visited.contains(neighbor)) {
197 visited.add(neighbor);
198 reachable = reachable || isGreaterThan(neighbor, b, visited);
205 public T getGLB(Set<T> inputSet) {
207 Set<T> lowerSet = new HashSet<T>();
209 // get lower set of input locations
210 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
211 T element = iterator.next();
212 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
213 lowerSet.add(element);
216 // an element of lower bound should be lower than every input set
217 Set<T> toberemoved = new HashSet<T>();
218 for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
219 T inputElement = inputIterator.next();
221 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
222 T lowerElement = (T) iterator.next();
223 if (!inputElement.equals(lowerElement)) {
224 if (!isGreaterThan(inputElement, lowerElement)) {
225 toberemoved.add(lowerElement);
230 lowerSet.removeAll(toberemoved);
232 // calculate the greatest element of lower set
233 // find an element A, where every lower bound B of lowerSet, B<A
234 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
235 T lowerElement = iterator.next();
236 boolean isGreaterThanAll = true;
237 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
238 T e = iterator2.next();
239 if (!lowerElement.equals(e)) {
240 if (!isGreaterThan(lowerElement, e)) {
241 isGreaterThanAll = false;
246 if (isGreaterThanAll) {
253 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
255 Set<T> neighborSet = get(element);
256 if (neighborSet != null) {
257 lowerSet.addAll(neighborSet);
258 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
259 T neighbor = iterator.next();
260 lowerSet = getLowerSet(neighbor, lowerSet);
266 public Set<Pair<T, T>> getOrderingPairSet() {
267 // return the set of pairs in the lattice
269 Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
271 Set<T> visited = new HashSet<T>();
272 Set<T> needtovisit = new HashSet<T>();
273 needtovisit.add(top);
275 while (!needtovisit.isEmpty()) {
276 T key = needtovisit.iterator().next();
277 Set<T> lowerSet = table.get(key);
278 if (lowerSet != null) {
279 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
280 T lowerItem = (T) iterator.next();
281 set.add(new Pair(key, lowerItem));
282 if (!visited.contains(key)) {
283 needtovisit.add(lowerItem);
288 needtovisit.remove(key);