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 void setTable(Map<T, Set<T>> in) {
44 Set<T> keySet = in.keySet();
45 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
46 T key = (T) iterator.next();
47 Set<T> setIn = in.get(key);
48 Set<T> newSet = new HashSet<T>();
50 table.put(key, newSet);
54 public boolean put(T key) {
55 if (table.containsKey(key)) {
58 // new key, need to be connected with top/bottom
60 table.get(top).add(key);
61 Set<T> neightborSet = new HashSet<T>();
62 neightborSet.add(bottom);
63 table.put(key, neightborSet);
68 public boolean put(T key, T value) {
70 if (isComparable(key, value) && isGreaterThan(key, value)) {
71 // this relation already exists
77 Set<T> topNeighbor = table.get(top);
78 if (table.containsKey(key)) {
81 // new key, need to be connected with top
87 if (value != null && !s.contains(value)) {
91 if ((!table.containsKey(value)) && (!value.equals(bottom))) {
92 Set<T> lowerNeighbor = new HashSet<T>();
93 lowerNeighbor.add(bottom);
94 table.put(value, lowerNeighbor);
97 // if value is already connected with top, it is no longer to be
98 if (!key.equals(top)) {
99 topNeighbor.remove(value);
102 // if key is already connected with bottom,, it is no longer to be
103 if (!value.equals(getBottomItem())) {
104 table.get(key).remove(getBottomItem());
112 public boolean isIntroducingCycle(T key) {
114 Set<T> reachableSet = new HashSet<T>();
115 Set<T> neighborSet = get(key);
117 if (neighborSet == null) {
120 reachableSet.addAll(neighborSet);
123 int oldReachableSize;
125 oldReachableSize = reachableSet.size();
126 Set<T> nextLevelNeighbors = new HashSet<T>();
127 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
128 T element = iterator.next();
129 Set<T> neighbors = get(element);
130 if (neighbors != null) {
131 nextLevelNeighbors.addAll(neighbors);
132 reachableSet.addAll(neighbors);
135 if (reachableSet.contains(key)) {
140 neighborSet = nextLevelNeighbors;
141 } while (oldReachableSize != reachableSet.size());
146 public Set<T> get(T key) {
147 return table.get(key);
150 public boolean containsKey(T o) {
151 return table.containsKey(o);
154 public boolean isComparable(T a, T b) {
156 Set<T> neighborSet = get(a);
160 } else if (neighborSet == null) {
162 } else if (neighborSet.contains(b)) {
165 boolean reachable = false;
166 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
167 T neighbor = iterator.next();
168 reachable = reachable || isComparable(neighbor, b);
175 public boolean isGreaterThan(T a, T b) {
177 Set<T> visited = new HashSet<T>();
178 return isGreaterThan(a, b, visited);
182 public boolean isGreaterThan(T a, T b, Set<T> visited) {
197 if (a.equals(bottom)) {
200 if (b.equals(bottom)) {
204 Set<T> neighborSet = get(a);
206 if (neighborSet == null) {
208 } else if (neighborSet.contains(b)) {
211 boolean reachable = false;
212 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
213 T neighbor = iterator.next();
214 if (!visited.contains(neighbor)) {
215 visited.add(neighbor);
216 reachable = reachable || isGreaterThan(neighbor, b, visited);
223 public T getGLB(Set<T> inputSet) {
225 Set<T> lowerSet = new HashSet<T>();
227 // get lower set of input locations
228 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
229 T element = iterator.next();
230 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
231 lowerSet.add(element);
234 // an element of lower bound should be lower than every input set
235 Set<T> toberemoved = new HashSet<T>();
236 for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
237 T inputElement = inputIterator.next();
239 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
240 T lowerElement = (T) iterator.next();
241 if (!inputElement.equals(lowerElement)) {
242 if (!isGreaterThan(inputElement, lowerElement)) {
243 toberemoved.add(lowerElement);
248 lowerSet.removeAll(toberemoved);
250 // calculate the greatest element of lower set
251 // find an element A, where every lower bound B of lowerSet, B<A
252 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
253 T lowerElement = iterator.next();
254 boolean isGreaterThanAll = true;
255 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
256 T e = iterator2.next();
257 if (!lowerElement.equals(e)) {
258 if (!isGreaterThan(lowerElement, e)) {
259 isGreaterThanAll = false;
264 if (isGreaterThanAll) {
271 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
273 Set<T> neighborSet = get(element);
274 if (neighborSet != null) {
275 lowerSet.addAll(neighborSet);
276 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
277 T neighbor = iterator.next();
278 lowerSet = getLowerSet(neighbor, lowerSet);
284 public Set<Pair<T, T>> getOrderingPairSet() {
285 // return the set of pairs in the lattice
287 Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
289 Set<T> visited = new HashSet<T>();
290 Set<T> needtovisit = new HashSet<T>();
291 needtovisit.add(top);
293 while (!needtovisit.isEmpty()) {
294 T key = needtovisit.iterator().next();
295 Set<T> lowerSet = table.get(key);
296 if (lowerSet != null) {
297 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
298 T lowerItem = (T) iterator.next();
299 set.add(new Pair(key, lowerItem));
300 if (!visited.contains(key)) {
301 needtovisit.add(lowerItem);
306 needtovisit.remove(key);