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.HashSet;
10 import java.util.Iterator;
11 import java.util.LinkedHashSet;
12 import java.util.LinkedList;
13 import java.util.List;
14 import java.util.ListIterator;
15 import java.util.Map;
16 import java.util.Random;
17 import java.util.Set;
18 import java.util.StringTokenizer;
19 import java.io.BufferedReader;
20 import java.io.IOException;
21 import java.io.InputStreamReader;
22 import java.math.BigInteger;
23 import jwutil.collections.GenericMultiMap;
24 import jwutil.collections.MultiMap;
25 import jwutil.math.CombinationGenerator;
26 import jwutil.math.Distributions;
27 import jwutil.util.Assert;
28 import net.sf.bddbddb.order.OrderConstraint.AfterConstraint;
29 import net.sf.bddbddb.order.OrderConstraint.BeforeConstraint;
30 import net.sf.bddbddb.order.OrderConstraint.InterleaveConstraint;
31
32 /***
33 * OrderConstraintSet
34 *
35 * @author jwhaley
36 * @version $Id: OrderConstraintSet.java 502 2005-04-13 00:26:23Z joewhaley $
37 */
38 public class OrderConstraintSet {
39
40 LinkedHashSet set;
41 MultiMap objToConstraints;
42
43 /***
44 *
45 */
46 public OrderConstraintSet() {
47 set = new LinkedHashSet();
48 objToConstraints = new GenericMultiMap();
49 }
50
51 public OrderConstraintSet copy() {
52 return new OrderConstraintSet(this);
53 }
54
55 private OrderConstraintSet(LinkedHashSet set, MultiMap objToConstraints){
56 this.set = set;
57 this.objToConstraints = objToConstraints;
58 }
59
60 public OrderConstraintSet(OrderConstraintSet that) {
61 set = new LinkedHashSet(that.set);
62 objToConstraints = new GenericMultiMap();
63 for (Iterator i = set.iterator(); i.hasNext(); ) {
64 OrderConstraint c = (OrderConstraint) i.next();
65 objToConstraints.add(c.a, c);
66 objToConstraints.add(c.b, c);
67 }
68 }
69 public OrderConstraintSet translate(Map translationMap){
70 OrderConstraintSet newOcs = new OrderConstraintSet();
71 for(Iterator it = set.iterator(); it.hasNext(); ){
72 OrderConstraint oc = (OrderConstraint) it.next();
73 Object newA = translationMap.get(oc.a);
74 Object newB = translationMap.get(oc.b);
75 if(newA == null || newB == null) continue;
76 OrderConstraint newOc = OrderConstraint.makeConstraint(oc.getType(), newA, newB);
77 newOcs.constrain(newOc);
78 }
79 return newOcs;
80 }
81
82 public int size(){ return set.size(); }
83 public boolean constrain(OrderConstraintSet ocs, Collection invalidConstraints){
84 return constrain(ocs.set, invalidConstraints);
85
86 }
87 public boolean constrain(Order c, Collection
88 return constrain(c.getConstraints(), invalidConstraints);
89 }
90
91 public boolean constrain(Collection c, Collection
92 boolean worked = true;
93 for (Iterator i = c.iterator(); i.hasNext(); ) {
94 OrderConstraint oc = (OrderConstraint) i.next();
95 if(!constrain(oc)){
96 worked = false;
97 if(invalidConstraints != null) invalidConstraints.add(oc);
98 }
99 }
100 return worked;
101 }
102
103 public boolean constrain(OrderConstraint c) {
104 if (set.contains(c)) return true;
105 if (set.contains(c.getOpposite1())) return false;
106 if (set.contains(c.getOpposite2())) return false;
107 if (c instanceof InterleaveConstraint){
108
109
110
111 addInterleaveConstraint((InterleaveConstraint) c);
112 }else {
113 if (c.a.equals(c.b)) return false;
114 addPrecedenceConstraint(c);
115 }
116 return true;
117 }
118
119 void checkTransitivePrecedence(Object a, Object b, Object c, Object d) {
120 if (b.equals(c)) {
121 addPrecedenceConstraint(a, d);
122 } else if (a.equals(d)) {
123 addPrecedenceConstraint(c, b);
124 }
125 }
126
127 void addInterleaveConstraint(Object a, Object b) {
128 if (a.equals(b)) return;
129 InterleaveConstraint o = (InterleaveConstraint) OrderConstraint.makeInterleaveConstraint(a, b);
130 addInterleaveConstraint(o);
131 }
132 void addInterleaveConstraint(InterleaveConstraint c) {
133 if (set.contains(c)) return;
134 set.add(c);
135 Collection c1 = objToConstraints.getValues(c.a);
136 Collection c2 = objToConstraints.getValues(c.b);
137 objToConstraints.add(c.a, c);
138 objToConstraints.add(c.b, c);
139 addInterleaveConstraints(c.a, c.b, c1);
140 addInterleaveConstraints(c.a, c.b, c2);
141 }
142 void addInterleaveConstraints(Object a, Object b, Collection ocs) {
143
144 ocs = new ArrayList(ocs);
145 for (Iterator i = ocs.iterator(); i.hasNext(); ) {
146 OrderConstraint oc = (OrderConstraint) i.next();
147 if (oc instanceof InterleaveConstraint) {
148 addInterleaveConstraint(a, oc.a);
149 addInterleaveConstraint(a, oc.b);
150 addInterleaveConstraint(b, oc.a);
151 addInterleaveConstraint(b, oc.b);
152 } else {
153 Object c, d;
154 if (oc instanceof BeforeConstraint) {
155 c = oc.a; d = oc.b;
156 } else {
157 c = oc.b; d = oc.a;
158 }
159 checkTransitivePrecedence(a, b, c, d);
160 checkTransitivePrecedence(b, a, c, d);
161 }
162 }
163 }
164
165 void addPrecedenceConstraint(Object a, Object b) {
166 Assert._assert(!a.equals(b));
167 OrderConstraint o = OrderConstraint.makePrecedenceConstraint(a, b);
168 addPrecedenceConstraint(o);
169 }
170 void addPrecedenceConstraint(OrderConstraint c) {
171 Assert._assert(c instanceof BeforeConstraint || c instanceof AfterConstraint);
172 Assert._assert(!c.a.equals(c.b));
173 if (set.contains(c)) return;
174 set.add(c);
175 Collection c1 = objToConstraints.getValues(c.a);
176 Collection c2 = objToConstraints.getValues(c.b);
177 objToConstraints.add(c.a, c);
178 objToConstraints.add(c.b, c);
179 if (c instanceof BeforeConstraint) {
180 addPrecedenceConstraints(c.a, c.b, c1);
181 addPrecedenceConstraints(c.a, c.b, c2);
182 } else {
183 addPrecedenceConstraints(c.b, c.a, c1);
184 addPrecedenceConstraints(c.b, c.a, c2);
185 }
186 }
187 void addPrecedenceConstraints(Object a, Object b, Collection ocs) {
188 Assert._assert(!a.equals(b));
189
190 ocs = new ArrayList(ocs);
191 for (Iterator i = ocs.iterator(); i.hasNext(); ) {
192 OrderConstraint oc = (OrderConstraint) i.next();
193 Object c, d;
194 if (oc instanceof AfterConstraint) {
195 c = oc.b; d = oc.a;
196 } else {
197 c = oc.a; d = oc.b;
198 if (oc instanceof InterleaveConstraint)
199 checkTransitivePrecedence(a, b, d, c);
200 }
201 checkTransitivePrecedence(a, b, c, d);
202 }
203 }
204
205 /***
206 * Find the earliest element in the order.
207 */
208 public Object findEarliest(Object o) {
209 return findEarliest(o, null);
210 }
211 /***
212 * Find the earliest element in the order, other than the orders in the skip set.
213 */
214 public Object findEarliest(Object o, Set skip) {
215 Collection c = objToConstraints.getValues(o);
216 if (c != null) {
217 for (Iterator i = c.iterator(); i.hasNext(); ) {
218 OrderConstraint oc = (OrderConstraint) i.next();
219 if (oc instanceof BeforeConstraint) {
220 if (o.equals(oc.b) &&
221 (skip == null || !skip.contains(oc.a))) {
222 return findEarliest(oc.a, skip);
223 }
224 } else if (oc instanceof AfterConstraint) {
225 if (o.equals(oc.a) &&
226 (skip == null || !skip.contains(oc.b))) {
227 return findEarliest(oc.b, skip);
228 }
229 }
230 }
231 }
232 return o;
233 }
234
235 /***
236 * Get the elements that must be interleaved with this element.
237 *
238 * @param o element
239 * @return collection of interleaved elements, including o
240 */
241 Collection getInterleaved(Object o) {
242 Collection result = new LinkedList();
243 Set visited = new HashSet();
244 result.add(o);
245 visited.add(o);
246 Collection c = objToConstraints.getValues(o);
247 if (c != null) {
248 for (Iterator i = c.iterator(); i.hasNext(); ) {
249 OrderConstraint oc = (OrderConstraint) i.next();
250 if (oc instanceof InterleaveConstraint) {
251 if (o.equals(oc.a)) {
252 if (visited.add(oc.b))
253 result.add(oc.b);
254 } else {
255 if (visited.add(oc.a))
256 result.add(oc.a);
257 }
258 }
259 }
260 }
261 return result;
262 }
263
264 public boolean hasPredecessor(Object o, Collection skip) {
265 Collection cons = objToConstraints.getValues(o);
266 for (Iterator i = cons.iterator(); i.hasNext(); ) {
267 OrderConstraint oc = (OrderConstraint) i.next();
268 if (oc instanceof BeforeConstraint) {
269 if (o.equals(oc.b) &&
270 (skip == null || !skip.contains(oc.a))) {
271 return true;
272 }
273 } else if (oc instanceof AfterConstraint) {
274 if (o.equals(oc.a) &&
275 (skip == null || !skip.contains(oc.b))) {
276 return true;
277 }
278 }
279 }
280 return false;
281 }
282
283 BigInteger countAllWays(Collection vars, List earliest, Set skip) {
284 BigInteger result = BigInteger.ZERO;
285 if (earliest.size() == 0) {
286 return BigInteger.ONE;
287 }
288 Iterator i = earliest.iterator();
289 while (i.hasNext()) {
290
291 Collection c = (Collection) i.next();
292
293 skip.addAll(c);
294 List newEarliest = findAllEarliest(vars, skip);
295 BigInteger r = countAllWays(vars, newEarliest, skip);
296 skip.removeAll(c);
297 result = result.add(r);
298 }
299 int num = earliest.size();
300 for (int k = 2; k <= num; ++k) {
301
302 CombinationGenerator cg = new CombinationGenerator(num, k);
303 while (cg.hasMore()) {
304 int[] p = cg.getNext();
305 Collection combo = new LinkedList();
306 for (int x = 0; x < p.length; ++x) {
307 Collection c = (Collection) earliest.get(p[x]);
308 combo.addAll(c);
309 }
310
311 skip.addAll(combo);
312 List newEarliest = findAllEarliest(vars, skip);
313 BigInteger r = countAllWays(vars, newEarliest, skip);
314 skip.removeAll(combo);
315 result = result.add(r);
316 }
317 }
318 return result;
319 }
320
321 List combineAllWays(Collection vars, List earliest, Set skip) {
322 List result = new LinkedList();
323 if (earliest.size() == 0) {
324 result.add(Collections.EMPTY_LIST);
325 return result;
326 }
327 Iterator i = earliest.iterator();
328 while (i.hasNext()) {
329
330 Collection c = (Collection) i.next();
331
332 skip.addAll(c);
333 List newEarliest = findAllEarliest(vars, skip);
334
335 List r = combineAllWays(vars, newEarliest, skip);
336
337 skip.removeAll(c);
338 for (Iterator j = r.iterator(); j.hasNext(); ) {
339 List list = (List) j.next();
340 List list2 = new ArrayList(list);
341 list2.add(0, c);
342
343 result.add(list2);
344 }
345 }
346 int num = earliest.size();
347 for (int k = 2; k <= num; ++k) {
348
349 CombinationGenerator cg = new CombinationGenerator(num, k);
350 while (cg.hasMore()) {
351 Collection combo = new LinkedList();
352 int[] p = cg.getNext();
353 for (int x = 0; x < p.length; ++x) {
354 Collection c = (Collection) earliest.get(p[x]);
355 combo.addAll(c);
356 }
357
358 skip.addAll(combo);
359 List newEarliest = findAllEarliest(vars, skip);
360
361 List r = combineAllWays(vars, newEarliest, skip);
362
363 skip.removeAll(combo);
364 for (Iterator j = r.iterator(); j.hasNext(); ) {
365 List list = (List) j.next();
366 List list2 = new ArrayList(list);
367 list2.add(0, combo);
368
369 result.add(list2);
370 }
371 }
372 }
373 return result;
374 }
375
376 List findAllEarliest(Collection vars, Collection skip) {
377 List earliest = new LinkedList();
378 Set mySkip = new HashSet();
379 if (skip != null) mySkip.addAll(skip);
380 for (Iterator i = vars.iterator(); i.hasNext(); ) {
381 Object o = i.next();
382 if (mySkip != null && mySkip.contains(o)) continue;
383 if (hasPredecessor(o, skip)) continue;
384 Collection c = getInterleaved(o);
385 mySkip.addAll(c);
386 earliest.add(c);
387 }
388 return earliest;
389 }
390
391 public boolean onlyOneOrder(int n) {
392 if (n == 0 || n == 1) return true;
393 int maxc = n * (n-1) / 2;
394 return set.size() == maxc;
395 }
396
397 static final double LOG2 = Math.log(2);
398
399 public int approxNumOrders(int n) {
400 if (n == 0) return 0;
401 if (n == 1) return 1;
402 double result = Distributions.recurrenceA000670(n).doubleValue();
403 double nc = Math.log(set.size()) / LOG2;
404 if (nc < 0) nc = 0;
405 double maxc = Math.log(n * (n-1) / 2) / LOG2;
406 if (maxc < 1) maxc = 1;
407 double result2 = result - ((result - 1) * nc / maxc);
408 double max = (double) Integer.MAX_VALUE;
409 if (result2 > max) return Integer.MAX_VALUE;
410 else return (int) result2;
411 }
412
413 public BigInteger countAllOrders(Collection vars) {
414 return countAllOrders(vars, null);
415 }
416
417 public BigInteger countAllOrders(Collection vars, Set skip) {
418 List earliest = findAllEarliest(vars, skip);
419 if (skip == null) skip = new HashSet();
420 BigInteger result = countAllWays(vars, earliest, skip);
421 return result;
422 }
423
424 public List generateAllOrders(Collection vars) {
425 return generateAllOrders(vars, null);
426 }
427
428 public List generateAllOrders(Collection vars, Set skip) {
429
430
431
432
433 List earliest = findAllEarliest(vars, skip);
434
435
436 if (skip == null) skip = new HashSet();
437
438
439 List result = combineAllWays(vars, earliest, skip);
440
441
442 for (ListIterator i = result.listIterator(); i.hasNext(); ) {
443 List a = (List) i.next();
444 for (ListIterator j = a.listIterator(); j.hasNext(); ) {
445 Collection c = (Collection) j.next();
446 if (c.size() == 1)
447 j.set(c.iterator().next());
448 }
449 Order o = new Order(a);
450 i.set(o);
451 }
452
453 return result;
454 }
455
456 static Random random = new Random(System.currentTimeMillis());
457 public Order generateRandomOrder(Collection vars) {
458 Set done = new HashSet(vars.size());
459 ArrayList input = new ArrayList(vars);
460 List result = new ArrayList(vars.size());
461 while (!input.isEmpty()) {
462 int r = random.nextInt(input.size());
463 Object o = input.get(r);
464 o = findEarliest(o, done);
465 Collection c = getInterleaved(o);
466 boolean interleave = false;
467 if (!result.isEmpty()) {
468 Object prev = result.get(result.size()-1);
469 if (prev instanceof Collection) prev = ((Collection) prev).iterator().next();
470 if (!set.contains(OrderConstraint.makePrecedenceConstraint(prev, o))) {
471
472 interleave = random.nextBoolean();
473 }
474 }
475 if (interleave) {
476 Object prev = result.get(result.size()-1);
477 if (prev instanceof Collection) ((Collection) prev).addAll(c);
478 else {
479 c.add(prev);
480 result.set(result.size()-1, c);
481 }
482 } else {
483 if (c.size() == 1) result.add(c.iterator().next());
484 else result.add(c);
485 }
486 done.addAll(c);
487 input.removeAll(c);
488 }
489 Order o = new Order(result);
490 return o;
491 }
492
493 public String toString() {
494 return set.toString();
495 }
496
497 public static void main(String[] args) {
498 OrderConstraintSet dis = new OrderConstraintSet();
499 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
500 Set allStrings = new HashSet();
501 try {
502 for (;;) {
503 System.out.print("Enter constraint: ");
504 String s = in.readLine();
505 if (s == null) break;
506 if (s.equals("done")) break;
507 if (s.length() == 0) continue;
508 StringTokenizer st = new StringTokenizer(s, "<>~", true);
509 String a = st.nextToken();
510 if (!st.hasMoreTokens()) {
511 allStrings.add(a);
512 continue;
513 }
514 String op = st.nextToken();
515 String b = st.nextToken();
516 OrderConstraint c;
517 if (op.equals("<")) c = OrderConstraint.makePrecedenceConstraint(a, b);
518 else if (op.equals(">")) c = OrderConstraint.makePrecedenceConstraint(b, a);
519 else if (op.equals("~")) c = OrderConstraint.makeInterleaveConstraint(a, b);
520 else {
521 continue;
522 }
523 if (dis.constrain(c)) {
524 System.out.println("Constraints now: "+dis);
525 } else {
526 System.out.println("Cannot add constraint!");
527 }
528 allStrings.add(a);
529 allStrings.add(b);
530 }
531 } catch (IOException e) {
532
533 e.printStackTrace();
534 }
535 for (int i = 0; i < 10; ++i) {
536 Order o = dis.generateRandomOrder(allStrings);
537 System.out.println("One random order is: "+o);
538 }
539 BigInteger c = dis.countAllOrders(allStrings);
540 System.out.println("Total number of orders: "+c);
541 List allOrders = dis.generateAllOrders(allStrings);
542 System.out.println("All orders ("+allOrders.size()+"): "+allOrders);
543 }
544 }