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>());
26 public T getTopItem() {
30 public T getBottomItem() {
34 public Set<T> getKeySet() {
35 return table.keySet();
38 public Map<T, Set<T>> getTable() {
42 public boolean put(T key) {
43 if (table.containsKey(key)) {
46 // new key, need to be connected with top/bottom
48 table.get(top).add(key);
49 Set<T> neightborSet = new HashSet<T>();
50 neightborSet.add(bottom);
51 table.put(key, neightborSet);
56 public boolean put(T key, T value) {
59 Set<T> topNeighbor = table.get(top);
61 if (table.containsKey(key)) {
64 // new key, need to be connected with top
70 if (value != null && !s.contains(value)) {
74 if ((!table.containsKey(value)) && (!value.equals(bottom))) {
75 Set<T> lowerNeighbor = new HashSet<T>();
76 lowerNeighbor.add(bottom);
77 table.put(value, lowerNeighbor);
80 // if value is already connected with top, it is no longer to be
81 topNeighbor.remove(value);
83 // if key is already connected with bottom,, it is no longer to be
84 if (!value.equals(getBottomItem())) {
85 table.get(key).remove(getBottomItem());
93 public boolean isIntroducingCycle(T key) {
95 Set<T> reachableSet = new HashSet<T>();
96 Set<T> neighborSet = get(key);
98 if (neighborSet == null) {
101 reachableSet.addAll(neighborSet);
104 int oldReachableSize;
106 oldReachableSize = reachableSet.size();
107 Set<T> nextLevelNeighbors = new HashSet<T>();
108 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
109 T element = iterator.next();
110 Set<T> neighbors = get(element);
111 if (neighbors != null) {
112 nextLevelNeighbors.addAll(neighbors);
113 reachableSet.addAll(neighbors);
116 if (reachableSet.contains(key)) {
121 neighborSet = nextLevelNeighbors;
122 } while (oldReachableSize != reachableSet.size());
127 public Set<T> get(T key) {
128 return table.get(key);
131 public boolean containsKey(T o) {
132 return table.containsKey(o);
135 public boolean isComparable(T a, T b) {
137 Set<T> neighborSet = get(a);
141 } else if (neighborSet == null) {
143 } else if (neighborSet.contains(b)) {
146 boolean reachable = false;
147 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
148 T neighbor = iterator.next();
149 reachable = reachable || isComparable(neighbor, b);
156 public boolean isGreaterThan(T a, T b) {
158 Set<T> visited = new HashSet<T>();
159 return isGreaterThan(a, b, visited);
163 public boolean isGreaterThan(T a, T b, Set<T> visited) {
178 if (a.equals(bottom)) {
181 if (b.equals(bottom)) {
185 Set<T> neighborSet = get(a);
187 if (neighborSet == null) {
189 } else if (neighborSet.contains(b)) {
192 boolean reachable = false;
193 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
194 T neighbor = iterator.next();
195 if (!visited.contains(neighbor)) {
196 visited.add(neighbor);
197 reachable = reachable || isGreaterThan(neighbor, b, visited);
204 public T getGLB(Set<T> inputSet) {
206 Set<T> lowerSet = new HashSet<T>();
208 // get lower set of input locations
209 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
210 T element = iterator.next();
211 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
212 lowerSet.add(element);
215 // an element of lower bound should be lower than every input set
216 Set<T> toberemoved = new HashSet<T>();
217 for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
218 T inputElement = inputIterator.next();
220 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
221 T lowerElement = (T) iterator.next();
222 if (!inputElement.equals(lowerElement)) {
223 if (!isGreaterThan(inputElement, lowerElement)) {
224 toberemoved.add(lowerElement);
229 lowerSet.removeAll(toberemoved);
231 // calculate the greatest element of lower set
232 // find an element A, where every lower bound B of lowerSet, B<A
233 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
234 T lowerElement = iterator.next();
235 boolean isGreaterThanAll = true;
236 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
237 T e = iterator2.next();
238 if (!lowerElement.equals(e)) {
239 if (!isGreaterThan(lowerElement, e)) {
240 isGreaterThanAll = false;
245 if (isGreaterThanAll) {
252 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
254 Set<T> neighborSet = get(element);
255 if (neighborSet != null) {
256 lowerSet.addAll(neighborSet);
257 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
258 T neighbor = iterator.next();
259 lowerSet = getLowerSet(neighbor, lowerSet);
265 public Set<Pair<T, T>> getOrderingPairSet() {
266 // return the set of pairs in the lattice
268 Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
270 Set<T> visited = new HashSet<T>();
271 Set<T> needtovisit = new HashSet<T>();
272 needtovisit.add(top);
274 while (!needtovisit.isEmpty()) {
275 T key = needtovisit.iterator().next();
276 Set<T> lowerSet = table.get(key);
277 if (lowerSet != null) {
278 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
279 T lowerItem = (T) iterator.next();
280 set.add(new Pair(key, lowerItem));
281 if (!visited.contains(key)) {
282 needtovisit.add(lowerItem);
287 needtovisit.remove(key);