View Javadoc

1   // Order.java, created Oct 22, 2004 5:24:41 PM by jwhaley
2   // Copyright (C) 2004 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
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/*<OrderConstraint>*/ getConstraints() {
77          if (constraints == null) {
78              constraints = new LinkedList();
79              
80              // Precedence constraints.
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                             //if (!x1.equals(y1))
103                             constraints.add(OrderConstraint.makePrecedenceConstraint(x1, y1));
104                         }
105                     }
106                 }
107             }
108             
109             // Interleave constraints.
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/*<InterleaveConstraint>*/ getAllInterleaveConstraints() {
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/*<OrderConstraint>*/ getAllPrecedenceConstraints() {
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         // Calculate the maximum number of similarities.
269         int nPred = dis_preds.size();
270         int nInter = dis_inters.size();
271         
272         // Find all similarities between the orders.
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     /* (non-Javadoc)
310      * @see java.lang.Comparable#compareTo(java.lang.Object)
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     /* (non-Javadoc)
349      * @see java.lang.Object#equals(java.lang.Object)
350      */
351     public boolean equals(Object obj) {
352         if (!(obj instanceof Order)) return false;
353         return equals((Order) obj);
354     }
355     
356     /* (non-Javadoc)
357      * @see java.util.Collection#add(java.lang.Object)
358      */
359     public boolean add(Object o) {
360         return list.add(o);
361     }
362     /* (non-Javadoc)
363      * @see java.util.List#add(int, java.lang.Object)
364      */
365     public void add(int index, Object element) {
366         list.add(index, element);
367     }
368     /* (non-Javadoc)
369      * @see java.util.List#addAll(int, java.util.Collection)
370      */
371     public boolean addAll(int index, Collection c) {
372         return list.addAll(index,c);
373     }
374     /* (non-Javadoc)
375      * @see java.util.Collection#addAll(java.util.Collection)
376      */
377     public boolean addAll(Collection c) {
378         return list.addAll(c);
379     }
380     /* (non-Javadoc)
381      * @see java.util.Collection#clear()
382      */
383     public void clear() {
384         list.clear();
385     }
386     /* (non-Javadoc)
387      * @see java.util.Collection#contains(java.lang.Object)
388      */
389     public boolean contains(Object o) {
390         return list.contains(o);
391     }
392     /* (non-Javadoc)
393      * @see java.util.Collection#containsAll(java.util.Collection)
394      */
395     public boolean containsAll(Collection c) {
396         return list.containsAll(c);
397     }
398     /* (non-Javadoc)
399      * @see java.util.List#get(int)
400      */
401     public Object get(int index) {
402         return list.get(index);
403     }
404     /* (non-Javadoc)
405      * @see java.lang.Object#hashCode()
406      */
407     public int hashCode() {
408         return list.hashCode();
409     }
410     /* (non-Javadoc)
411      * @see java.util.List#indexOf(java.lang.Object)
412      */
413     public int indexOf(Object o) {
414         return list.indexOf(o);
415     }
416     /* (non-Javadoc)
417      * @see java.util.Collection#isEmpty()
418      */
419     public boolean isEmpty() {
420         return list.isEmpty();
421     }
422     /* (non-Javadoc)
423      * @see java.lang.Iterable#iterator()
424      */
425     public Iterator iterator() {
426         return list.iterator();
427     }
428     /* (non-Javadoc)
429      * @see java.util.List#lastIndexOf(java.lang.Object)
430      */
431     public int lastIndexOf(Object o) {
432         return list.lastIndexOf(o);
433     }
434     /* (non-Javadoc)
435      * @see java.util.List#listIterator()
436      */
437     public ListIterator listIterator() {
438         return list.listIterator();
439     }
440     /* (non-Javadoc)
441      * @see java.util.List#listIterator(int)
442      */
443     public ListIterator listIterator(int index) {
444         return list.listIterator(index);
445     }
446     /* (non-Javadoc)
447      * @see java.util.List#remove(int)
448      */
449     public Object remove(int index) {
450         return list.remove(index);
451     }
452     /* (non-Javadoc)
453      * @see java.util.Collection#remove(java.lang.Object)
454      */
455     public boolean remove(Object o) {
456         return list.remove(o);
457     }
458     /* (non-Javadoc)
459      * @see java.util.Collection#removeAll(java.util.Collection)
460      */
461     public boolean removeAll(Collection c) {
462         return list.removeAll(c);
463     }
464     /* (non-Javadoc)
465      * @see java.util.Collection#retainAll(java.util.Collection)
466      */
467     public boolean retainAll(Collection c) {
468         return list.retainAll(c);
469     }
470     /* (non-Javadoc)
471      * @see java.util.List#set(int, java.lang.Object)
472      */
473     public Object set(int index, Object element) {
474         return list.set(index, element);
475     }
476     /* (non-Javadoc)
477      * @see java.util.Collection#size()
478      */
479     public int size() {
480         return list.size();
481     }
482     /* (non-Javadoc)
483      * @see java.util.List#subList(int, int)
484      */
485     public List subList(int fromIndex, int toIndex) {
486         return list.subList(fromIndex,toIndex);
487     }
488     /* (non-Javadoc)
489      * @see java.util.Collection#toArray()
490      */
491     public Object[] toArray() {
492         return list.toArray();
493     }
494     /* (non-Javadoc)
495      * @see java.util.Collection#toArray(java.lang.Object[])
496      */
497     public Object[] toArray(Object[] a) {
498         return list.toArray(a);
499     }
500     /* (non-Javadoc)
501      * @see java.lang.Object#toString()
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/*<Variable,BDDDomain>*/ variableToBDDDomain) {
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     //////////////////// OLD CODE BELOW
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/*<Order,Integer>*/ calcLongSimilarities(Collection c) {
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/*<Order>*/ sim = a.findLongSimilarities(b);
615                 // todo: expand sim to also include implied suborders.
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     // TODO: this should use a dynamic programming implementation instead
678     // of recursive, because it is solving many repeated subproblems.
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/*<Order>*/ findLongSimilarities(Order that) {
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 }