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(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
99 topNeighbor.remove(value);
103 // if key is already connected with bottom,, it is no longer to be
104 if (!value.equals(getBottomItem())) {
105 table.get(key).remove(getBottomItem());
113 public boolean isIntroducingCycle(T key) {
115 Set<T> reachableSet = new HashSet<T>();
116 Set<T> neighborSet = get(key);
118 if (neighborSet == null) {
121 reachableSet.addAll(neighborSet);
124 int oldReachableSize;
126 oldReachableSize = reachableSet.size();
127 Set<T> nextLevelNeighbors = new HashSet<T>();
128 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
129 T element = iterator.next();
130 Set<T> neighbors = get(element);
131 if (neighbors != null) {
132 nextLevelNeighbors.addAll(neighbors);
133 reachableSet.addAll(neighbors);
136 if (reachableSet.contains(key)) {
141 neighborSet = nextLevelNeighbors;
142 } while (oldReachableSize != reachableSet.size());
147 public Set<T> get(T key) {
148 return table.get(key);
151 public boolean containsKey(T o) {
152 return table.containsKey(o);
155 public boolean isComparable(T a, T b) {
157 Set<T> neighborSet = get(a);
161 } else if (neighborSet == null) {
163 } else if (neighborSet.contains(b)) {
166 boolean reachable = false;
167 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
168 T neighbor = iterator.next();
169 reachable = reachable || isComparable(neighbor, b);
176 public boolean isGreaterThan(T a, T b) {
178 Set<T> visited = new HashSet<T>();
179 return isGreaterThan(a, b, visited);
183 public boolean isGreaterThan(T a, T b, Set<T> visited) {
198 if (a.equals(bottom)) {
201 if (b.equals(bottom)) {
205 Set<T> neighborSet = get(a);
207 if (neighborSet == null) {
209 } else if (neighborSet.contains(b)) {
212 boolean reachable = false;
213 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
214 T neighbor = iterator.next();
215 if (!visited.contains(neighbor)) {
216 visited.add(neighbor);
217 reachable = reachable || isGreaterThan(neighbor, b, visited);
224 public T getGLB(Set<T> inputSet) {
226 Set<T> lowerSet = new HashSet<T>();
228 // get lower set of input locations
229 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
230 T element = iterator.next();
231 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
232 lowerSet.add(element);
235 // an element of lower bound should be lower than every input set
236 Set<T> toberemoved = new HashSet<T>();
237 for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
238 T inputElement = inputIterator.next();
240 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
241 T lowerElement = (T) iterator.next();
242 if (!inputElement.equals(lowerElement)) {
243 if (!isGreaterThan(inputElement, lowerElement)) {
244 toberemoved.add(lowerElement);
249 lowerSet.removeAll(toberemoved);
251 // calculate the greatest element of lower set
252 // find an element A, where every lower bound B of lowerSet, B<A
253 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
254 T lowerElement = iterator.next();
255 boolean isGreaterThanAll = true;
256 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
257 T e = iterator2.next();
258 if (!lowerElement.equals(e)) {
259 if (!isGreaterThan(lowerElement, e)) {
260 isGreaterThanAll = false;
265 if (isGreaterThanAll) {
272 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
274 Set<T> neighborSet = get(element);
275 if (neighborSet != null) {
276 lowerSet.addAll(neighborSet);
277 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
278 T neighbor = iterator.next();
279 lowerSet = getLowerSet(neighbor, lowerSet);
285 public Set<Pair<T, T>> getOrderingPairSet() {
286 // return the set of pairs in the lattice
288 Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
290 Set<T> visited = new HashSet<T>();
291 Set<T> needtovisit = new HashSet<T>();
292 needtovisit.add(top);
294 while (!needtovisit.isEmpty()) {
295 T key = needtovisit.iterator().next();
296 Set<T> lowerSet = table.get(key);
297 if (lowerSet != null) {
298 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
299 T lowerItem = (T) iterator.next();
300 set.add(new Pair(key, lowerItem));
301 if (!visited.contains(key)) {
302 needtovisit.add(lowerItem);
307 needtovisit.remove(key);