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) {
71 Set<T> topNeighbor = table.get(top);
73 if (table.containsKey(key)) {
76 // new key, need to be connected with top
82 if (value != null && !s.contains(value)) {
86 if ((!table.containsKey(value)) && (!value.equals(bottom))) {
87 Set<T> lowerNeighbor = new HashSet<T>();
88 lowerNeighbor.add(bottom);
89 table.put(value, lowerNeighbor);
92 // if value is already connected with top, it is no longer to be
93 topNeighbor.remove(value);
95 // if key is already connected with bottom,, it is no longer to be
96 if (!value.equals(getBottomItem())) {
97 table.get(key).remove(getBottomItem());
105 public boolean isIntroducingCycle(T key) {
107 Set<T> reachableSet = new HashSet<T>();
108 Set<T> neighborSet = get(key);
110 if (neighborSet == null) {
113 reachableSet.addAll(neighborSet);
116 int oldReachableSize;
118 oldReachableSize = reachableSet.size();
119 Set<T> nextLevelNeighbors = new HashSet<T>();
120 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
121 T element = iterator.next();
122 Set<T> neighbors = get(element);
123 if (neighbors != null) {
124 nextLevelNeighbors.addAll(neighbors);
125 reachableSet.addAll(neighbors);
128 if (reachableSet.contains(key)) {
133 neighborSet = nextLevelNeighbors;
134 } while (oldReachableSize != reachableSet.size());
139 public Set<T> get(T key) {
140 return table.get(key);
143 public boolean containsKey(T o) {
144 return table.containsKey(o);
147 public boolean isComparable(T a, T b) {
149 Set<T> neighborSet = get(a);
153 } else if (neighborSet == null) {
155 } else if (neighborSet.contains(b)) {
158 boolean reachable = false;
159 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
160 T neighbor = iterator.next();
161 reachable = reachable || isComparable(neighbor, b);
168 public boolean isGreaterThan(T a, T b) {
170 Set<T> visited = new HashSet<T>();
171 return isGreaterThan(a, b, visited);
175 public boolean isGreaterThan(T a, T b, Set<T> visited) {
190 if (a.equals(bottom)) {
193 if (b.equals(bottom)) {
197 Set<T> neighborSet = get(a);
199 if (neighborSet == null) {
201 } else if (neighborSet.contains(b)) {
204 boolean reachable = false;
205 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
206 T neighbor = iterator.next();
207 if (!visited.contains(neighbor)) {
208 visited.add(neighbor);
209 reachable = reachable || isGreaterThan(neighbor, b, visited);
216 public T getGLB(Set<T> inputSet) {
218 Set<T> lowerSet = new HashSet<T>();
220 // get lower set of input locations
221 for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
222 T element = iterator.next();
223 lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
224 lowerSet.add(element);
227 // an element of lower bound should be lower than every input set
228 Set<T> toberemoved = new HashSet<T>();
229 for (Iterator<T> inputIterator = inputSet.iterator(); inputIterator.hasNext();) {
230 T inputElement = inputIterator.next();
232 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
233 T lowerElement = (T) iterator.next();
234 if (!inputElement.equals(lowerElement)) {
235 if (!isGreaterThan(inputElement, lowerElement)) {
236 toberemoved.add(lowerElement);
241 lowerSet.removeAll(toberemoved);
243 // calculate the greatest element of lower set
244 // find an element A, where every lower bound B of lowerSet, B<A
245 for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
246 T lowerElement = iterator.next();
247 boolean isGreaterThanAll = true;
248 for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
249 T e = iterator2.next();
250 if (!lowerElement.equals(e)) {
251 if (!isGreaterThan(lowerElement, e)) {
252 isGreaterThanAll = false;
257 if (isGreaterThanAll) {
264 public Set<T> getLowerSet(T element, Set<T> lowerSet) {
266 Set<T> neighborSet = get(element);
267 if (neighborSet != null) {
268 lowerSet.addAll(neighborSet);
269 for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
270 T neighbor = iterator.next();
271 lowerSet = getLowerSet(neighbor, lowerSet);
277 public Set<Pair<T, T>> getOrderingPairSet() {
278 // return the set of pairs in the lattice
280 Set<Pair<T, T>> set = new HashSet<Pair<T, T>>();
282 Set<T> visited = new HashSet<T>();
283 Set<T> needtovisit = new HashSet<T>();
284 needtovisit.add(top);
286 while (!needtovisit.isEmpty()) {
287 T key = needtovisit.iterator().next();
288 Set<T> lowerSet = table.get(key);
289 if (lowerSet != null) {
290 for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
291 T lowerItem = (T) iterator.next();
292 set.add(new Pair(key, lowerItem));
293 if (!visited.contains(key)) {
294 needtovisit.add(lowerItem);
299 needtovisit.remove(key);