View Javadoc

1   // OrderIterator.java, created Oct 24, 2004 12:20:11 AM 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.Iterator;
8   import java.util.LinkedList;
9   import java.util.List;
10  import java.util.NoSuchElementException;
11  import jwutil.math.CombinationGenerator;
12  import jwutil.util.Assert;
13  
14  /***
15   * Iterate through all possible orders of a given list.
16   * 
17   * @author jwhaley
18   * @version $Id: OrderIterator.java 435 2005-02-13 03:24:59Z cs343 $
19   */
20  public class OrderIterator implements Iterator {
21      
22      List orig;
23      List/*<CombinationGenerator>*/ combos;
24      int comboCounter;
25      
26      public OrderIterator(List a) {
27          orig = new ArrayList(a);
28          combos = new ArrayList(a.size());
29          comboCounter = 0;
30          gotoNextCombo();
31      }
32      
33      void gotoNextCombo() {
34          combos.clear();
35          int remaining = orig.size();
36          int size = 1;
37          int bits = comboCounter++;
38          while (remaining > 0) {
39              CombinationGenerator g;
40              if (remaining == size) {
41                  g = new CombinationGenerator(remaining, size);
42                  if (!combos.isEmpty()) g.getNext();
43                  combos.add(g);
44                  break;
45              }
46              if ((bits&1)==0) {
47                  g = new CombinationGenerator(remaining, size);
48                  if (!combos.isEmpty()) g.getNext();
49                  combos.add(g);
50                  remaining -= size;
51                  size = 0;
52              }
53              size++;
54              bits >>= 1;
55          }
56      }
57      
58      boolean hasNextCombo() {
59          int elements = orig.size();
60          return (comboCounter < (1 << (elements-1)));
61      }
62      
63      boolean hasMore() {
64          for (Iterator i = combos.iterator(); i.hasNext(); ) {
65              CombinationGenerator g = (CombinationGenerator) i.next();
66              if (g.hasMore()) return true;
67          }
68          return false;
69      }
70      
71      public boolean hasNext() {
72          return hasMore() || hasNextCombo();
73      }
74      
75      public Object next() {
76          return nextOrder();
77      }
78      
79      public Order nextOrder() {
80          if (!hasMore()) {
81              if (!hasNextCombo()) {
82                  throw new NoSuchElementException();
83              }
84              gotoNextCombo();
85          }
86          List result = new LinkedList();
87          List used = new ArrayList(orig);
88          boolean carry = true;
89          for (Iterator i = combos.iterator(); i.hasNext(); ) {
90              CombinationGenerator g = (CombinationGenerator) i.next();
91              int[] p;
92              if (carry) {
93                  if (!g.hasMore()) g.reset();
94                  else carry = false;
95                  p = g.getNext();
96              } else {
97                  p = g.getCurrent();
98              }
99              if (p.length == 1) {
100                 result.add(used.remove(p[0]));
101             } else {
102                 LinkedList c = new LinkedList();
103                 for (int k = p.length-1; k >= 0; --k) {
104                     c.addFirst(used.remove(p[k]));
105                 }
106                 result.add(c);
107             }
108         }
109         Assert._assert(!carry);
110         return new Order(result);
111     }
112     
113     public void remove() {
114         throw new UnsupportedOperationException();
115     }
116 }