1
2
3
4 package net.sf.bddbddb.order;
5
6 import java.util.ArrayList;
7 import java.util.Collection;
8 import java.util.Collections;
9 import java.util.HashMap;
10 import java.util.Iterator;
11 import java.util.LinkedList;
12 import java.util.List;
13 import java.util.ListIterator;
14 import java.util.Map;
15 import java.util.StringTokenizer;
16
17 import jwutil.util.Assert;
18 import net.sf.bddbddb.FindBestDomainOrder;
19 import net.sf.bddbddb.order.OrderConstraint.InterleaveConstraint;
20
21 /***
22 * Represents an order. This is just a List with a few extra utility functions.
23 *
24 * @author jwhaley
25 * @version $Id: Order.java 435 2005-02-13 03:24:59Z cs343 $
26 */
27 public class Order implements List, Comparable {
28
29 /*** Underlying list. */
30 List list;
31
32 /*** Constraints of this order. */
33 transient Collection constraints;
34
35 /***
36 * Construct a new Order that is a copy of the given Order.
37 *
38 * @param o order to copy
39 */
40 public Order(Order o) {
41 this.list = new ArrayList(o.list);
42 this.constraints = null;
43 }
44
45 /***
46 * Construct a new Order from the given list.
47 *
48 * @param l list
49 */
50 public Order(List l) {
51 for (Iterator i = l.iterator(); i.hasNext(); ) {
52 Object o = i.next();
53 if (o instanceof List) {
54 Collections.sort((List) o, OrderConstraint.elementComparator);
55 }
56 }
57 this.list = l;
58 this.constraints = null;
59 }
60
61 /***
62 * Returns true if this order obeys the given constraint.
63 *
64 * @param c constraint
65 * @return true if this order obeys the constraint, false otherwise
66 */
67 public boolean obeysConstraint(OrderConstraint c) {
68 return c.obeyedBy(this);
69 }
70
71 /***
72 * Return the collection of constraints in this order.
73 *
74 * @return collection of constraints
75 */
76 public Collection
77 if (constraints == null) {
78 constraints = new LinkedList();
79
80
81 for (Iterator i = list.iterator(); i.hasNext(); ) {
82 Object o1 = i.next();
83 Iterator j = list.iterator();
84 while (j.hasNext() && j.next() != o1) ;
85 while (j.hasNext()) {
86 Object o2 = j.next();
87 Iterator x, y;
88 if (o1 instanceof Collection) {
89 x = ((Collection) o1).iterator();
90 } else {
91 x = Collections.singleton(o1).iterator();
92 }
93 while (x.hasNext()) {
94 Object x1 = x.next();
95 if (o2 instanceof Collection) {
96 y = ((Collection) o2).iterator();
97 } else {
98 y = Collections.singleton(o2).iterator();
99 }
100 while (y.hasNext()) {
101 Object y1 = y.next();
102
103 constraints.add(OrderConstraint.makePrecedenceConstraint(x1, y1));
104 }
105 }
106 }
107 }
108
109
110 for (Iterator i = list.iterator(); i.hasNext(); ) {
111 Object o1 = i.next();
112 if (o1 instanceof Collection) {
113 Collection c = (Collection) o1;
114 for (Iterator x = c.iterator(); x.hasNext(); ) {
115 Object a = x.next();
116 Iterator y = c.iterator();
117 while (y.hasNext() && y.next() != a) ;
118 while (y.hasNext()) {
119 Object b = y.next();
120 constraints.add(OrderConstraint.makeInterleaveConstraint(a, b));
121 }
122 }
123 }
124 }
125 }
126 return constraints;
127 }
128
129 /***
130 * Returns the number of elements in this order. This includes elements
131 * within interleaves.
132 *
133 * @return number of elements in this order
134 */
135 public int numberOfElements() {
136 int total = 0;
137 for (Iterator i = list.iterator(); i.hasNext(); ) {
138 Object o = i.next();
139 if (o instanceof Collection) {
140 total += ((Collection) o).size();
141 } else {
142 ++total;
143 }
144 }
145 return total;
146 }
147
148 /***
149 * Return the flattened version of this list.
150 *
151 * @return flattened version of this list
152 */
153 public List getFlattened() {
154 List result = new LinkedList();
155 for (Iterator i = list.iterator(); i.hasNext(); ) {
156 Object o = i.next();
157 if (o instanceof Collection) {
158 result.addAll((Collection) o);
159 } else {
160 result.add(o);
161 }
162 }
163 return result;
164 }
165
166 /***
167 * Get all interleave constraints of this order.
168 *
169 * @return collection of interleave constraints
170 */
171 public Collection
172 getConstraints();
173 Collection s = new LinkedList();
174 for (Iterator i = constraints.iterator(); i.hasNext(); ) {
175 Object o = i.next();
176 if (o instanceof InterleaveConstraint)
177 s.add(o);
178 }
179 return s;
180 }
181
182 /***
183 * Get the number of interleave constraints in this order.
184 *
185 * @return number of interleave constraints
186 */
187 public int numInterleaveConstraints() {
188 int n = 0;
189 for (Iterator i = list.iterator(); i.hasNext(); ) {
190 Object o = i.next();
191 if (o instanceof Collection) {
192 int k = ((Collection) o).size();
193 n += k * (k-1) / 2;
194 }
195 }
196 return n;
197 }
198
199 /***
200 * Get all precedence constraints of this order.
201 *
202 * @return collection of precedence constraints
203 */
204 public Collection
205 getConstraints();
206 Collection s = new LinkedList();
207 for (Iterator i = constraints.iterator(); i.hasNext(); ) {
208 Object o = i.next();
209 if (!(o instanceof InterleaveConstraint))
210 s.add(o);
211 }
212 return s;
213 }
214
215 /***
216 * Get the number of precedence constraints in this order.
217 *
218 * @return number of precedence constraints
219 */
220 public int numPrecedenceConstraints() {
221 int n = 0;
222 int result = 0;
223 for (Iterator i = list.iterator(); i.hasNext(); ) {
224 Object o = i.next();
225 int k;
226 if (o instanceof Collection) {
227 k = ((Collection) o).size();
228 } else {
229 k = 1;
230 }
231 result += n*k;
232 n += k;
233 }
234 return result;
235 }
236
237 /***
238 * Returns the similarity between two orders as a number between 0.0 and 1.0.
239 * 1.0 means that the orders are exactly the same, and 0.0 means they have no
240 * similarities.
241 *
242 * Precedence constraints are weighted by the factor "PRECEDENCE_WEIGHT", and
243 * interleave constraints are weighted by the factor "INTERLEAVE_WEIGHT".
244 *
245 * @param that
246 * @return similarity measure between 0.0 and 1.0
247 */
248 public double similarity(Order that) {
249 if (this.isEmpty() || that.isEmpty()) return 1.;
250 if (this.numberOfElements() < that.numberOfElements())
251 return this.similarity0(that);
252 else
253 return that.similarity0(this);
254 }
255
256 public static double PRECEDENCE_WEIGHT = 1.;
257 public static double INTERLEAVE_WEIGHT = 3.;
258
259 private double similarity0(Order that) {
260 this.getConstraints();
261 that.getConstraints();
262
263 Collection dis_preds = this.getAllPrecedenceConstraints();
264 Collection dis_inters = this.getAllInterleaveConstraints();
265 Collection dat_preds = that.getAllPrecedenceConstraints();
266 Collection dat_inters = that.getAllInterleaveConstraints();
267
268
269 int nPred = dis_preds.size();
270 int nInter = dis_inters.size();
271
272
273 dis_preds.removeAll(dat_preds);
274 dis_inters.removeAll(dat_inters);
275 int nPred2 = dis_preds.size();
276 int nInter2 = dis_inters.size();
277
278 double total = nPred * PRECEDENCE_WEIGHT + nInter * INTERLEAVE_WEIGHT;
279 double unsimilar = nPred2 * PRECEDENCE_WEIGHT + nInter2 * INTERLEAVE_WEIGHT;
280 double sim = (total - unsimilar) / total;
281 if (FindBestDomainOrder.TRACE > 4) FindBestDomainOrder.out.println("Similarity ("+this+" and "+that+") = "+FindBestDomainOrder.format(sim));
282 return sim;
283 }
284
285 public static double[] COMPLEXITY_SINGLE =
286 { 0., 1., 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13., 14., 15. } ;
287 public static double[] COMPLEXITY_MULTI =
288 { 0., 2., 4., 8., 16., 32., 64., 128., 256., 512., 1024., 2048., 4096., 8192., 16384., 32768. } ;
289
290 /***
291 * Returns a measure of the complexity of this order. Higher numbers are
292 * more complex (i.e. have more constraints)
293 *
294 * @return a measure of the complexity of this order
295 */
296 public double complexity() {
297 int n = Math.min(list.size(), COMPLEXITY_SINGLE.length-1);
298 double total = COMPLEXITY_SINGLE[n];
299 for (Iterator i = list.iterator(); i.hasNext(); ) {
300 Object o = i.next();
301 if (o instanceof Collection) {
302 n = Math.min(((Collection) o).size(), COMPLEXITY_MULTI.length-1);
303 total += COMPLEXITY_MULTI[n];
304 }
305 }
306 return total;
307 }
308
309
310
311
312 public int compareTo(Object arg0) {
313 return compareTo((Order) arg0);
314 }
315 /***
316 * Compares orders lexigraphically.
317 *
318 * @param that order to compare to
319 * @return -1, 0, or 1 if this order is less than, equal to, or greater than
320 */
321 public int compareTo(Order that) {
322 if (this == that) return 0;
323 return this.toString().compareTo(that.toString());
324 }
325
326 public boolean equals(Order that) {
327 if (true) {
328 return list.equals(that.list);
329 } else {
330 if (this.list.size() != that.list.size()) return false;
331 Iterator i = this.list.iterator();
332 Iterator j = that.list.iterator();
333 while (i.hasNext()) {
334 Object a = i.next();
335 Object b = j.next();
336 if (a instanceof Collection) {
337 if (b instanceof Collection) {
338 Collection ac = (Collection) a;
339 Collection bc = (Collection) b;
340 if (!ac.containsAll(bc)) return false;
341 if (!bc.containsAll(ac)) return false;
342 } else return false;
343 } else if (!a.equals(b)) return false;
344 }
345 return true;
346 }
347 }
348
349
350
351 public boolean equals(Object obj) {
352 if (!(obj instanceof Order)) return false;
353 return equals((Order) obj);
354 }
355
356
357
358
359 public boolean add(Object o) {
360 return list.add(o);
361 }
362
363
364
365 public void add(int index, Object element) {
366 list.add(index, element);
367 }
368
369
370
371 public boolean addAll(int index, Collection c) {
372 return list.addAll(index,c);
373 }
374
375
376
377 public boolean addAll(Collection c) {
378 return list.addAll(c);
379 }
380
381
382
383 public void clear() {
384 list.clear();
385 }
386
387
388
389 public boolean contains(Object o) {
390 return list.contains(o);
391 }
392
393
394
395 public boolean containsAll(Collection c) {
396 return list.containsAll(c);
397 }
398
399
400
401 public Object get(int index) {
402 return list.get(index);
403 }
404
405
406
407 public int hashCode() {
408 return list.hashCode();
409 }
410
411
412
413 public int indexOf(Object o) {
414 return list.indexOf(o);
415 }
416
417
418
419 public boolean isEmpty() {
420 return list.isEmpty();
421 }
422
423
424
425 public Iterator iterator() {
426 return list.iterator();
427 }
428
429
430
431 public int lastIndexOf(Object o) {
432 return list.lastIndexOf(o);
433 }
434
435
436
437 public ListIterator listIterator() {
438 return list.listIterator();
439 }
440
441
442
443 public ListIterator listIterator(int index) {
444 return list.listIterator(index);
445 }
446
447
448
449 public Object remove(int index) {
450 return list.remove(index);
451 }
452
453
454
455 public boolean remove(Object o) {
456 return list.remove(o);
457 }
458
459
460
461 public boolean removeAll(Collection c) {
462 return list.removeAll(c);
463 }
464
465
466
467 public boolean retainAll(Collection c) {
468 return list.retainAll(c);
469 }
470
471
472
473 public Object set(int index, Object element) {
474 return list.set(index, element);
475 }
476
477
478
479 public int size() {
480 return list.size();
481 }
482
483
484
485 public List subList(int fromIndex, int toIndex) {
486 return list.subList(fromIndex,toIndex);
487 }
488
489
490
491 public Object[] toArray() {
492 return list.toArray();
493 }
494
495
496
497 public Object[] toArray(Object[] a) {
498 return list.toArray(a);
499 }
500
501
502
503 public String toString() {
504 return list.toString();
505 }
506
507 /***
508 * Generate a BDD order string from this variable order.
509 *
510 * @param variableToBDDDomain map from variable to BDD
511 * @return BDD order string
512 */
513 public String toVarOrderString(Map
514 StringBuffer varOrder = new StringBuffer();
515 for (Iterator i = iterator(); i.hasNext(); ) {
516 Object p = i.next();
517 if (p instanceof Collection) {
518 Collection c = (Collection) p;
519 int num = 0;
520 for (Iterator j = c.iterator(); j.hasNext(); ) {
521 Object v = j.next();
522 Object d;
523 if (variableToBDDDomain != null) d = variableToBDDDomain.get(v);
524 else d = v;
525 if (d != null) {
526 if (varOrder.length() > 0) {
527 if (num == 0) {
528 varOrder.append('_');
529 } else {
530 varOrder.append('x');
531 }
532 }
533 varOrder.append(d);
534 ++num;
535 }
536 }
537 } else {
538 Object d;
539 if (variableToBDDDomain != null) d = variableToBDDDomain.get(p);
540 else d = p;
541 if (d != null) {
542 if (varOrder.length() > 0) varOrder.append('_');
543 varOrder.append(d);
544 }
545 }
546 }
547 String vOrder = varOrder.toString();
548 return vOrder;
549 }
550
551 /***
552 * Parse an order from a string.
553 *
554 * @param s string to parse
555 * @param nameToObj map from name to object (variable, etc.)
556 * @return order
557 */
558 public static Order parse(String s, Map nameToObj) {
559 StringTokenizer st = new StringTokenizer(s, "[], ", true);
560 String tok = st.nextToken();
561 if (!tok.equals("[")) {
562 throw new IllegalArgumentException("Unknown \""+tok+"\" in order \""+s+"\"");
563 }
564 List o = new LinkedList();
565 List inner = null;
566 while (st.hasMoreTokens()) {
567 tok = st.nextToken();
568 if (tok.equals(" ") || tok.equals(",")) continue;
569 if (tok.equals("[")) {
570 if (inner != null)
571 throw new IllegalArgumentException("Nested \""+tok+"\" in order \""+s+"\"");
572 inner = new LinkedList();
573 continue;
574 }
575 if (tok.equals("]")) {
576 if (!st.hasMoreTokens()) break;
577 if (inner == null)
578 throw new IllegalArgumentException("Unmatched \""+tok+"\" in order \""+s+"\"");
579 o.add(inner);
580 inner = null;
581 continue;
582 }
583 Object obj = nameToObj.get(tok);
584 if (obj == null) {
585 throw new IllegalArgumentException("Unknown \""+tok+"\" in order \""+s+"\"");
586 }
587 if (inner != null) {
588 if (!inner.contains(obj)) inner.add(obj);
589 }
590 else o.add(obj);
591 }
592 return new Order(o);
593 }
594
595
596
597
598 /***
599 * Given a collection of orders, find its similarities and the
600 * number of occurrences of each similarity.
601 *
602 * @param c collection of orders
603 * @return map from order similarities to frequencies
604 */
605 public static Map
606 Map m = new HashMap();
607 if (FindBestDomainOrder.TRACE > 1) FindBestDomainOrder.out.println("Calculating similarities in the collection: "+c);
608 for (Iterator i = c.iterator(); i.hasNext(); ) {
609 Order a = (Order) i.next();
610 Iterator j = c.iterator();
611 while (j.hasNext() && j.next() != a) ;
612 while (j.hasNext()) {
613 Order b = (Order) j.next();
614 Collection
615
616 for (Iterator k = sim.iterator(); k.hasNext(); ) {
617 Order s = (Order) k.next();
618 Integer count = (Integer) m.get(s);
619 int newCount = (count==null) ? 1 : count.intValue()+1;
620 m.put(s, new Integer(newCount));
621 }
622 }
623 }
624 if (FindBestDomainOrder.TRACE > 1) FindBestDomainOrder.out.println("Similarities: "+m);
625 return m;
626 }
627
628 /***
629 * Utility function for intersecting elements and collections.
630 *
631 * @param a element or collection
632 * @param b element or collection
633 * @return element or collection which is the intersection
634 */
635 static Object intersect(Object a, Object b) {
636 if (a instanceof Collection) {
637 Collection ca = (Collection) a;
638 if (b instanceof Collection) {
639 Collection result = new LinkedList();
640 result.addAll(ca);
641 result.retainAll((Collection) b);
642 if (result.isEmpty()) return null;
643 else if (result.size() == 1) return result.iterator().next();
644 else return result;
645 }
646 if (ca.contains(b)) return b;
647 } else if (b instanceof Collection) {
648 if (((Collection) b).contains(a)) return a;
649 } else {
650 if (a.equals(b)) return a;
651 }
652 return null;
653 }
654
655 /***
656 * Utility function for adding new elements from one collection to another.
657 *
658 * @param c collection to add to
659 * @param c2 collection to add from
660 */
661 static void addAllNew(Collection c, Collection c2) {
662 outer:
663 for (ListIterator c2i = ((List)c2).listIterator(); c2i.hasNext(); ) {
664 List l2 = (List) c2i.next();
665 for (ListIterator c1i = ((List)c).listIterator(); c1i.hasNext(); ) {
666 List l1 = (List) c1i.next();
667 if (l1.containsAll(l2)) continue outer;
668 else if (l2.containsAll(l1)) {
669 c1i.set(l2);
670 continue outer;
671 }
672 }
673 c.add(l2);
674 }
675 }
676
677
678
679 static Collection findLongSimilarities(List o1, List o2) {
680 if (o1.size() == 0 || o2.size() == 0) {
681 return null;
682 }
683 Object x1 = o1.get(0);
684 List r1 = o1.subList(1, o1.size());
685 Object x2 = o2.get(0);
686 List r2 = o2.subList(1, o2.size());
687 Object x = intersect(x1, x2);
688 Collection c = null;
689 if (x != null) {
690 c = findLongSimilarities(r1, r2);
691 if (c == null) {
692 c = new LinkedList();
693 Collection c2 = new LinkedList();
694 c2.add(x);
695 c.add(c2);
696 } else {
697 for (Iterator i = c.iterator(); i.hasNext(); ) {
698 List l = (List) i.next();
699 l.add(0, x);
700 }
701 }
702 }
703 if (x == null || !x1.equals(x2)) {
704 Collection c2 = findLongSimilarities(o1, r2);
705 if (c == null) c = c2;
706 else if (c2 != null) addAllNew(c, c2);
707 Collection c3 = findLongSimilarities(r1, o2);
708 if (c == null) c = c3;
709 else if (c3 != null) addAllNew(c, c3);
710 }
711 return c;
712 }
713
714 /***
715 * Return the collection of suborders that are similar between this order
716 * and the given order. Duplicates are eliminated.
717 *
718 * @param that other order
719 * @return collection of suborders that are similar
720 */
721 public Collection
722 if (false)
723 {
724 Collection f1 = this.getFlattened();
725 Collection f2 = that.getFlattened();
726 Assert._assert(f1.containsAll(f2));
727 Assert._assert(f2.containsAll(f1));
728 }
729
730 Collection result = new LinkedList();
731 Collection c = findLongSimilarities(this.list, that.list);
732 for (Iterator i = c.iterator(); i.hasNext(); ) {
733 List l = (List) i.next();
734 if (false && l.size() == 1) {
735 Object elem = l.get(0);
736 if (!(elem instanceof List)) continue;
737 List l2 = (List) elem;
738 if (l2.size() == 1) continue;
739 }
740 result.add(new Order(l));
741 }
742 return result;
743 }
744
745 }