1
2
3
4 package net.sf.bddbddb.dataflow;
5
6 import java.util.Arrays;
7 import java.util.Collection;
8 import java.util.HashSet;
9 import java.util.Iterator;
10 import java.util.LinkedHashSet;
11 import java.util.LinkedList;
12 import java.util.List;
13 import java.util.ListIterator;
14 import java.util.Map;
15 import java.util.Set;
16 import java.util.SortedSet;
17 import java.util.TreeSet;
18
19 import jwutil.collections.GenericMultiMap;
20 import jwutil.collections.HashWorklist;
21 import jwutil.collections.MultiMap;
22 import jwutil.collections.Pair;
23 import jwutil.collections.UnionFind;
24 import jwutil.graphs.Navigator;
25 import jwutil.util.Assert;
26 import net.sf.bddbddb.Attribute;
27 import net.sf.bddbddb.BDDRelation;
28 import net.sf.bddbddb.IterationList;
29 import net.sf.bddbddb.Relation;
30 import net.sf.bddbddb.dataflow.PartialOrder.ConstraintGraph.ConstraintNavigator;
31 import net.sf.bddbddb.ir.IR;
32 import net.sf.bddbddb.ir.Operation;
33 import net.sf.bddbddb.ir.OperationVisitor;
34 import net.sf.bddbddb.ir.dynamic.If;
35 import net.sf.bddbddb.ir.dynamic.Nop;
36 import net.sf.bddbddb.ir.highlevel.Copy;
37 import net.sf.bddbddb.ir.highlevel.Difference;
38 import net.sf.bddbddb.ir.highlevel.Free;
39 import net.sf.bddbddb.ir.highlevel.GenConstant;
40 import net.sf.bddbddb.ir.highlevel.Invert;
41 import net.sf.bddbddb.ir.highlevel.Join;
42 import net.sf.bddbddb.ir.highlevel.JoinConstant;
43 import net.sf.bddbddb.ir.highlevel.Load;
44 import net.sf.bddbddb.ir.highlevel.Project;
45 import net.sf.bddbddb.ir.highlevel.Rename;
46 import net.sf.bddbddb.ir.highlevel.Save;
47 import net.sf.bddbddb.ir.highlevel.Union;
48 import net.sf.bddbddb.ir.highlevel.Universe;
49 import net.sf.bddbddb.ir.highlevel.Zero;
50 import net.sf.bddbddb.ir.lowlevel.ApplyEx;
51 import net.sf.bddbddb.ir.lowlevel.BDDProject;
52 import net.sf.bddbddb.ir.lowlevel.Replace;
53
54 /***
55 * Partial order.
56 *
57 * @author Michael Carbin
58 * @version $Id: PartialOrder.java 531 2005-04-29 06:39:10Z joewhaley $
59 */
60 public class PartialOrder extends OperationProblem {
61 IR ir;
62 boolean TRACE = false;
63 public PartialOrderFact currFact;
64
65 public PartialOrder(IR ir) {
66 this.ir = ir;
67 }
68
69
70
71
72 public boolean direction() {
73 return true;
74 }
75
76
77
78
79 public TransferFunction getTransferFunction(Operation o) {
80 return new PartialOrderTF(o);
81 }
82
83 public String toString() {
84 StringBuffer sb = new StringBuffer();
85 for (Iterator it = operationFacts.entrySet().iterator(); it.hasNext();) {
86 Map.Entry e = (Map.Entry) it.next();
87 sb.append(e.getKey() + ": " + e.getValue() + "\n");
88 }
89 return sb.toString();
90 }
91
92 public Constraints getConstraints(Relation r) {
93 return currFact.getConstraints(r);
94 }
95 public class PartialOrderFact implements OperationFact {
96 Constraints[] constraintsMap;
97 Operation op;
98 IterationList loc;
99
100 public PartialOrderFact() {
101 constraintsMap = new Constraints[ir.solver.getNumberOfRelations()];
102 }
103
104 public Constraints getConstraints(Relation r) {
105 return constraintsMap[r.id];
106 }
107
108 public Constraints[] getConstraintsMap() {
109 return constraintsMap;
110 }
111
112 public void setConstraints(Relation r, Constraints constraints) {
113 constraintsMap[r.id] = constraints;
114 }
115
116
117
118
119 public Operation getOperation() {
120 return op;
121 }
122
123
124
125
126 public Fact join(Fact that) {
127 PartialOrderFact result = (PartialOrderFact) copy(getLocation());
128 PartialOrderFact thatFact = (PartialOrderFact) that;
129 for (int i = 0; i < constraintsMap.length; i++) {
130 result.constraintsMap[i].join(thatFact.constraintsMap[i]);
131 }
132 return result;
133 }
134
135
136
137
138 public boolean equals(Object o) {
139 if (o instanceof PartialOrderFact) {
140 PartialOrderFact that = (PartialOrderFact) o;
141 return Arrays.equals(this.constraintsMap, that.constraintsMap);
142 }
143 return false;
144 }
145
146
147
148
149 public int hashCode() {
150 return this.constraintsMap.hashCode();
151 }
152
153
154
155
156 public Fact copy(IterationList loc) {
157 PartialOrderFact result = new PartialOrderFact();
158 System.arraycopy(constraintsMap, 0, result.constraintsMap, 0, constraintsMap.length);
159 result.loc = loc;
160 return result;
161 }
162
163
164
165
166 public void setLocation(IterationList loc) {
167 this.loc = loc;
168 }
169
170
171
172
173 public IterationList getLocation() {
174 return loc;
175 }
176
177 public String toString() {
178 StringBuffer sb = new StringBuffer();
179 sb.append("[ ");
180 for (int i = 0; i < constraintsMap.length; i++) {
181 Constraints c = constraintsMap[i];
182 if (!c.isEmpty()) {
183 sb.append(ir.getRelation(i).toString() + ": ");
184 sb.append(c + " ");
185 }
186 }
187 sb.append("]");
188 return sb.toString();
189 }
190 }
191 public class PartialOrderTF extends TransferFunction implements OperationVisitor {
192 Operation op;
193
194 public PartialOrderTF(Operation op) {
195 this.op = op;
196 }
197
198
199
200
201 public Fact apply(Fact f) {
202 PartialOrderFact lastFact = (PartialOrderFact) f;
203 currFact = (PartialOrderFact) lastFact.copy(lastFact.loc);
204 op.visit(this);
205 currFact.op = op;
206 setFact(op, currFact);
207 return currFact;
208 }
209
210
211
212
213 public Object visit(Join op) {
214 if (TRACE) System.out.println(op);
215 Relation src1 = op.getSrc1();
216 Relation src2 = op.getSrc2();
217 Relation dest = op.getRelationDest();
218 Constraints union = visitUnionBinary(src1, src2);
219 if (TRACE) System.out.println("union of src constraints: " + union);
220 Constraints newCons = union.join(dest.getConstraints());
221 if (TRACE) System.out.println("final constraints: " + newCons);
222 currFact.setConstraints(op.getRelationDest(), newCons);
223 return currFact;
224 }
225
226
227
228
229 public Object visit(Project op) {
230 if (TRACE) System.out.println(op);
231 Constraints c = currFact.getConstraints(op.getSrc());
232 Constraints newCons = c.copy();
233 if (TRACE) System.out.println("source constraints:" + c);
234 List attrs = op.getAttributes();
235 project(newCons, attrs);
236 currFact.setConstraints(op.getRelationDest(), newCons);
237 return currFact;
238 }
239
240 public Object visit(BDDProject op){
241 Assert.UNREACHABLE();
242 return null;
243 }
244
245
246
247
248 public Object visit(ApplyEx op) {
249
250 if (TRACE) System.out.println(op);
251 Constraints newCons = visitUnionBinary(op.getSrc1(), op.getSrc2());
252 if (TRACE) System.out.println("union of source constraints: " + newCons);
253 List attrs = op.getAttributes();
254 project(newCons, attrs);
255 Relation dest = op.getRelationDest();
256 newCons.join(dest.getConstraints());
257 if (TRACE) System.out.println("new constraints: " + newCons);
258 currFact.setConstraints(dest, newCons);
259 return currFact;
260 }
261
262 public Set project(Constraints cons, List attributes) {
263 SortedSet relCons = cons.getRelevantConstraints(attributes);
264 Constraints relCs = new Constraints(relCons);
265 if (TRACE) System.out.println("relevant constraints: " + relCs);
266 relCs.doTransitiveClosure();
267 if (TRACE) System.out.println("transitive relevant constraints: " + relCs);
268 cons.getBeforeConstraints().addAll(relCs.getBeforeConstraints());
269 cons.getInterleavedConstraints().addAll(relCs.getInterleavedConstraints());
270 Set removed = new HashSet();
271 for (Iterator it = attributes.iterator(); it.hasNext();) {
272 removed.addAll(cons.removeInvolving((Attribute) it.next()));
273 }
274 if (TRACE) System.out.println("removing: " + removed);
275 return removed;
276 }
277
278
279
280
281 public Object visit(Rename op) {
282 if (TRACE) System.out.println(op);
283 Constraints c = currFact.getConstraints(op.getSrc());
284 BDDRelation dest = (BDDRelation) op.getRelationDest();
285 Map renames = op.getRenameMap();
286 List srcAttrs = op.getSrc().getAttributes();
287 if (TRACE) System.out.println("src constraints: " + c);
288
289
290
291
292
293
294 Constraints newCons = new Constraints();
295 for (Iterator it = c.getBeforeConstraints().iterator(); it.hasNext();) {
296 Constraint oldC = (Constraint) it.next();
297 Attribute a1 = (Attribute) renames.get(oldC.getLeftAttribute());
298
299 Attribute a2 = (Attribute) renames.get(oldC.getRightAttribute());
300
301 Constraint newC = a1 != null && a2 != null ? new BeforeConstraint(dest, a1, dest, a2, oldC.confidence) : oldC;
302
303 }
304 for (Iterator it = c.getInterleavedConstraints().iterator(); it.hasNext();) {
305 Constraint oldC = (Constraint) it.next();
306 Attribute a1 = (Attribute) renames.get(oldC.getLeftAttribute());
307
308 Attribute a2 = (Attribute) renames.get(oldC.getRightAttribute());
309
310 Constraint newC = a1 != null && a2 != null ? new InterleavedConstraint(dest, a1, dest, a2, oldC.confidence) : oldC;
311
312 newCons.addInterleavedConstraint(newC);
313
314
315 }
316 newCons.join(dest.getConstraints());
317 if (TRACE) System.out.println("new constraints: " + newCons);
318 currFact.setConstraints(dest, newCons);
319 return currFact;
320 }
321
322 public Constraints visitUnionBinary(Relation src1, Relation src2) {
323 Constraints c1 = currFact.getConstraints(src1);
324 Constraints c2 = currFact.getConstraints(src2);
325 return c1.join(c2);
326 }
327
328
329
330
331 public Object visit(Union op) {
332 if (TRACE) System.out.println(op);
333 Relation src1 = op.getSrc1();
334 Relation src2 = op.getSrc2();
335 Relation dest = op.getRelationDest();
336 Constraints newCons = visitUnionBinary(src1, src2);
337 if (TRACE) System.out.println("union of source constraints: " + newCons);
338 newCons.join(dest.getConstraints());
339 if (TRACE) System.out.println("new constraints: " + newCons);
340 currFact.setConstraints(dest, newCons);
341 return currFact;
342 }
343
344
345
346
347 public Object visit(Difference op) {
348 if (TRACE) System.out.println(op);
349 Relation src1 = op.getSrc1();
350 Relation src2 = op.getSrc2();
351 Relation dest = op.getRelationDest();
352 Constraints newCons = visitUnionBinary(src1, src2);
353 if (TRACE) System.out.println("union of source constraints: " + newCons);
354 newCons.join(dest.getConstraints());
355 if (TRACE) System.out.println("new constraints: " + newCons);
356 currFact.setConstraints(dest, newCons);
357 return currFact;
358 }
359
360
361
362
363 public Object visit(Load op) {
364 if (TRACE) System.out.println(op);
365 Relation dest = op.getRelationDest();
366 if (TRACE) System.out.println("relation constraints: " + dest.getConstraints());
367 currFact.setConstraints(dest, dest.getConstraints());
368 return null;
369 }
370
371
372
373
374 public Object visit(JoinConstant op) {
375 return null;
376 }
377
378
379
380
381 public Object visit(GenConstant op) {
382 return null;
383 }
384
385
386
387
388 public Object visit(Free op) {
389 return null;
390 }
391
392
393
394
395 public Object visit(Universe op) {
396 return null;
397 }
398
399
400
401
402 public Object visit(Zero op) {
403 return null;
404 }
405
406
407
408
409 public Object visit(Invert op) {
410 return null;
411 }
412
413
414
415
416 public Object visit(Copy op) {
417 currFact.setConstraints(op.getRelationDest(), currFact.getConstraints(op.getSrc()));
418 return null;
419 }
420
421
422
423
424 public Object visit(Save op) {
425 return null;
426 }
427
428
429
430
431 public Object visit(Replace op) {
432 return null;
433 }
434
435
436
437
438 public Object visit(If op) {
439 return null;
440 }
441
442
443
444
445 public Object visit(Nop op) {
446 return null;
447 }
448 }
449
450
451
452
453 public Fact getBoundary() {
454 PartialOrderFact fact = new PartialOrderFact();
455 for (int i = 0; i < fact.constraintsMap.length; i++)
456 fact.constraintsMap[i] = new Constraints();
457 return fact;
458 }
459 public abstract static class Constraint extends Pair implements Comparable{
460 public static final int BEFORE = 0;
461 public static final int INTERLEAVED = 1;
462 double confidence;
463 public Constraint(Relation leftRel, Attribute leftAttr,
464 Relation rightRel, Attribute rightAttr, double confidence) {
465 super(new Pair(leftRel,leftAttr), new Pair(rightRel,rightAttr));
466 Assert._assert(leftRel.getAttributes().contains(leftAttr), "Left Attribute: " + leftAttr + " not part of Left Relation: " +leftRel);
467 Assert._assert(rightRel.getAttributes().contains(rightAttr), "Right attribute: " + rightAttr + " not part of Right Relation: " + rightRel);
468 this.confidence = confidence;
469 }
470
471 public Pair getLeftRelationAttrPair(){ return (Pair) left; }
472 public Pair getRightRelationAttrPair(){ return (Pair) right; }
473 public Relation getLeftRelation(){ return (Relation) ((Pair) left).left; }
474 public Attribute getLeftAttribute(){ return (Attribute) ((Pair)left).right; }
475 public Relation getRightRelation(){ return (Relation) ((Pair) right).left; }
476 public Attribute getRightAttribute(){ return (Attribute) ((Pair)right).right; }
477
478 public Constraint(Relation leftRel, Attribute leftAttr,
479 Relation rightRel, Attribute rightAttr) {
480 this(leftRel, leftAttr,rightRel, rightAttr, 0);
481 }
482
483 public String toString(){
484 return "(" + left + (getType() == BEFORE ? " before " : " interleaved with ") + right + " conf: " + confidence + ")";
485 }
486
487 public abstract int getType();
488
489 public boolean isBeforeConstraint(){ return getType() == BEFORE; }
490 public boolean isInterleavedConstraint(){ return getType() == INTERLEAVED; }
491
492 public int compareTo(Object o){
493 Constraint that = (Constraint) o;
494 return Double.compare(that.confidence,this.confidence);
495 }
496 }
497
498 public static class InterleavedConstraint extends Constraint{
499
500 /***
501 * Version ID for serialization.
502 */
503 private static final long serialVersionUID = 3257003254876616756L;
504
505 /***
506 * @param leftRel
507 * @param leftAttr
508 * @param rightRel
509 * @param rightAttr
510 */
511 public InterleavedConstraint(Relation leftRel, Attribute leftAttr, Relation rightRel, Attribute rightAttr) {
512 super(leftRel, leftAttr, rightRel, rightAttr);
513
514 }
515 /***
516 * @param leftRel
517 * @param leftAttr
518 * @param rightRel
519 * @param rightAttr
520 * @param confidence
521 */
522 public InterleavedConstraint(Relation leftRel, Attribute leftAttr, Relation rightRel, Attribute rightAttr, double confidence) {
523 super(leftRel, leftAttr, rightRel, rightAttr, confidence);
524
525 }
526 public int getType(){ return INTERLEAVED; }
527
528
529
530 }
531
532 public static class BeforeConstraint extends Constraint{
533
534 /***
535 * Version ID for serialization.
536 */
537 private static final long serialVersionUID = 3835158341730514996L;
538
539 /***
540 * @param leftRel
541 * @param leftAttr
542 * @param rightRel
543 * @param rightAttr
544 */
545 public BeforeConstraint(Relation leftRel, Attribute leftAttr, Relation rightRel, Attribute rightAttr) {
546 super(leftRel, leftAttr, rightRel, rightAttr);
547
548 }
549 /***
550 * @param leftRel
551 * @param leftAttr
552 * @param rightRel
553 * @param rightAttr
554 * @param confidence
555 */
556 public BeforeConstraint(Relation leftRel, Attribute leftAttr, Relation rightRel, Attribute rightAttr, double confidence) {
557 super(leftRel, leftAttr, rightRel, rightAttr, confidence);
558
559 }
560 public int getType(){ return BEFORE; }
561 }
562 public static class Constraints {
563 static boolean TRACE = true;
564 MultiMap graph;
565 UnionFind uf;
566
567
568
569 SortedSet constraints;
570
571 public Constraints() {
572 constraints = new TreeSet();
573
574
575
576 }
577
578
579
580
581
582
583 public Constraints(SortedSet constraints){
584 this.constraints = constraints;
585 }
586 public SortedSet getRelevantConstraints(Collection attributes) {
587 SortedSet cons = new TreeSet();
588 cons.addAll(relevantBeforeConstraints(attributes));
589 cons.addAll(relevantInterConstraints(attributes));
590 return cons;
591 }
592
593 public Collection getBeforeConstraints() {
594 SortedSet cons = new TreeSet();
595 for(Iterator it = constraints.iterator(); it.hasNext(); ){
596 Constraint con = (Constraint) it.next();
597 if(con.isBeforeConstraint())
598 cons.add(con);
599 }
600
601 return cons;
602 }
603
604 public SortedSet getInterleavedConstraints() {
605 SortedSet cons = new TreeSet();
606 for(Iterator it = constraints.iterator(); it.hasNext(); ){
607 Constraint con = (Constraint) it.next();
608 if(con.isInterleavedConstraint())
609 cons.add(con);
610 }
611
612 return cons;
613 }
614
615 public SortedSet getAllConstraints(){ return constraints; }
616
617 private List relevantConstraints(Collection attributes, Collection srcCons) {
618 List relevantConstraints = new LinkedList();
619 for (Iterator it = srcCons.iterator(); it.hasNext();) {
620 Constraint c = (Constraint) it.next();
621 if (attributes.contains(c.left) || attributes.contains(c.right)) relevantConstraints.add(c);
622 }
623 return relevantConstraints;
624 }
625
626 public List relevantBeforeConstraints(Collection attributes) {
627 return relevantConstraints(attributes, getBeforeConstraints());
628 }
629
630 public List relevantInterConstraints(Collection attributes) {
631 return relevantConstraints(attributes, getInterleavedConstraints());
632 }
633
634 public void addBeforeConstraint(Constraint c) {
635 constraints.add(c);
636 }
637
638 public void addInterleavedConstraint(Constraint c) {
639 constraints.add(c);
640 }
641
642 public Constraints copy() {
643 Constraints c = new Constraints();
644 c.constraints = new TreeSet(this.constraints);
645 return c;
646 }
647
648 public List removeInvolving(Attribute a) {
649 List removed = new LinkedList();
650 removed.addAll(removeInvolving(a, constraints));
651
652 return removed;
653 }
654
655 private List removeInvolving(Attribute a, Collection cons) {
656 List removed = new LinkedList();
657 for (Iterator it = cons.iterator(); it.hasNext();) {
658 Constraint c = (Constraint) it.next();
659 if (c.contains(a)) {
660 removed.add(c);
661 it.remove();
662 }
663 }
664 return removed;
665 }
666
667 public List buildGraphAndReps(){
668 ConstraintGraph graph = new ConstraintGraph();
669 MultiMap repToAttributes = new GenericMultiMap();
670 uf = new UnionFind(4096);
671 Set seen = new HashSet();
672 for (Iterator it = getInterleavedConstraints().iterator(); it.hasNext();) {
673 Pair p = (Pair) it.next();
674 seen.add(p.left);
675 seen.add(p.right);
676 Object repl = uf.find(p.left);
677 Object repr = uf.find(p.right);
678 if (repl == null && repr == null) {
679 uf.union(p.left, p.right);
680 } else if (repl != null && repr == null) {
681 uf.union(repl, p.right);
682 } else if (repl == null && repr != null) {
683 uf.union(p.left, repr);
684 } else {
685 uf.union(repl, repr);
686 }
687 }
688 Set nodes = new HashSet();
689
690 for (Iterator it = getBeforeConstraints().iterator(); it.hasNext();) {
691 Pair p = (Pair) it.next();
692 Object repl = uf.find(p.left);
693 Object repr = uf.find(p.right);
694 seen.add(repl);
695 seen.add(repr);
696 if (repl == null && repr == null) {
697 graph.addEdge(p.left, p.right);
698 } else if (repl != null && repr == null) {
699 graph.addEdge(repl, p.right);
700 } else if (repl == null && repr != null) {
701 graph.addEdge(p.left, repr);
702 } else {
703 graph.addEdge(repl, repr);
704 }
705 }
706
707 for (Iterator it = seen.iterator(); it.hasNext();) {
708 Object o = it.next();
709 Object rep = uf.find(o);
710 graph.addNode(rep);
711 repToAttributes.add(rep, o);
712 }
713
714 List result = new LinkedList();
715 result.add(graph);
716 result.add(uf);
717 result.add(repToAttributes);
718 return result;
719 }
720
721
722 List findCycles(Object start, Set visited, List trace, ConstraintNavigator nav) {
723 List cycles = new LinkedList();
724 trace.add(start);
725 visited.add(start);
726 Collection nexts = nav.next(start);
727 for (Iterator it = nexts.iterator(); it.hasNext();) {
728 Object next = it.next();
729 if (visited.contains(next)) {
730 if (trace.contains(next)) {
731 int index = trace.indexOf(next);
732 List cycle = new LinkedList(trace.subList(index, trace.size()));
733 cycles.add(cycle);
734 }
735 } else {
736 cycles.addAll(findCycles(next, visited, trace, nav));
737 }
738 }
739 trace.remove(trace.size() - 1);
740 return cycles;
741 }
742
743 List cycleToConstraints(List cycle, MultiMap repToAttributes) {
744
745 List constraints = new LinkedList();
746 for (ListIterator it = cycle.listIterator(); it.hasNext();) {
747 Object o1 = it.next();
748 if (it.hasNext()) {
749 constraints.addAll(constraints(o1, it.next(), repToAttributes));
750 it.previous();
751 }
752 }
753 constraints.addAll(constraints(cycle.get(cycle.size() - 1), cycle.get(0),repToAttributes));
754 return constraints;
755 }
756
757 List constraints(Object o1, Object o2, MultiMap repToActual) {
758 List constraints = new LinkedList();
759 Collection o1jects = repToActual.getValues(o1);
760 Collection o2jects = repToActual.getValues(o2);
761 Collection beforeConstraints = getBeforeConstraints();
762 for (Iterator it = o1jects.iterator(); it.hasNext();) {
763 Pair left = (Pair) it.next();
764 for (Iterator jt = o2jects.iterator(); jt.hasNext();) {
765 Pair right = (Pair) jt.next();
766 Constraint p = new BeforeConstraint((Relation) left.left, (Attribute) left.right,
767 (Relation) right.left, (Attribute) right.right);
768 if (beforeConstraints.contains(p)) {
769 constraints.add(p);
770 }
771 }
772 }
773 return constraints;
774 }
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816 public void satisfy() {
817 System.out.println("satisfying constraints" + hashCode());
818 List cycle = new LinkedList();
819 List info = buildGraphAndReps();
820 ConstraintGraph graph = (ConstraintGraph) info.get(0);
821 UnionFind uf = (UnionFind) info.get(1);
822 MultiMap repToAttributes = (MultiMap) info.get(2);
823 while(true){
824 cycle.clear();
825 if(graph.isCycle(cycle)){
826 System.out.println("cycle: " + cycle);
827 List constraints = cycleToConstraints(cycle,repToAttributes);
828 System.out.println("possibilities: " + constraints);
829 Iterator jt = constraints.iterator();
830 Constraint lowest = (Constraint) jt.next();
831 for (; jt.hasNext(); ) {
832 Constraint next = (Constraint) jt.next();
833 if (next.confidence < lowest.confidence) lowest = next;
834 }
835 System.out.println("removing: " + lowest);
836 if(constraints.remove(lowest))
837 System.out.println("removed");
838 info = buildGraphAndReps();
839 graph = (ConstraintGraph) info.get(0);
840 uf = (UnionFind) info.get(1);
841 repToAttributes = (MultiMap) info.get(2);
842 }else
843 break;
844 }
845 }
846
847 public Constraints join(Constraints that) {
848
849 Constraints result = new Constraints();
850
851
852
853
854
855
856 result.constraints = new TreeSet(this.constraints);
857 result.satisfy();
858 return result;
859 }
860
861 public boolean isEmpty() {
862 return constraints.isEmpty();
863 }
864
865
866
867
868 public boolean equals(Object o) {
869 if (o instanceof Constraints) {
870 Constraints that = (Constraints) o;
871 return this.constraints.equals(that.constraints);
872 }
873 return false;
874 }
875
876
877
878
879 public int hashCode() {
880 return constraints.hashCode();
881 }
882
883 public String toString() {
884 return "[before constraints: " + getBeforeConstraints() + " interleaved constraints: " + getInterleavedConstraints() + "]";
885 }
886
887 public void doTransitiveClosure() {
888 SortedSet newConstraints = new TreeSet();
889 newConstraints.addAll(doTransitiveClosure(getBeforeConstraints()));
890 newConstraints.addAll(doTransitiveClosure(getInterleavedConstraints()));
891 }
892
893 public Collection doTransitiveClosure(Collection
894 ConstraintGraph graph = new ConstraintGraph(constraints);
895 Collection newConstraints = new LinkedHashSet(constraints);
896 ConstraintGraph.ConstraintNavigator nav = graph.getNavigator();
897 HashWorklist w = new HashWorklist(true);
898 w.addAll(constraints);
899
900 while (!w.isEmpty()) {
901 Constraint con = (Constraint) w.pull();
902 Pair left = con.getLeftRelationAttrPair();
903 Pair right = con.getRightRelationAttrPair();
904 Collection nexts = nav.next(right);
905 for (Iterator it = nexts.iterator(); it.hasNext();) {
906 Pair trans = (Pair) it.next();
907 if(con.getType() == Constraint.BEFORE)
908 newConstraints.add(new BeforeConstraint((Relation) left.left, (Attribute) left.right, (Relation) trans.left, (Attribute)trans.right));
909 else
910 newConstraints.add(new InterleavedConstraint((Relation) left.left, (Attribute) left.right, (Relation) trans.left, (Attribute)trans.right));
911
912 w.add(new Pair(left, trans));
913 }
914 }
915 return newConstraints;
916 }
917 }
918 public static class ConstraintGraph {
919 MultiMap graph;
920 Collection nodes;
921 ConstraintNavigator nav;
922
923 public ConstraintGraph() {
924 nav = new ConstraintNavigator();
925 graph = new GenericMultiMap();
926 nodes = new HashSet();
927 }
928 public ConstraintGraph(ConstraintGraph that){
929 this.graph = ((GenericMultiMap)that.graph).copy();
930 this.nodes = new HashSet(that.nodes);
931 nav = new ConstraintNavigator();
932 }
933
934 public void update(UnionFind uf){
935 MultiMap newGraph = new GenericMultiMap();
936 Set newNodes = new HashSet();
937 for(Iterator it = nodes.iterator(); it.hasNext(); ){
938 Object node = it.next();
939 System.out.println("node: " + node + " rep: " + uf.find(node));
940 newNodes.add(uf.find(node));
941 }
942 for(Iterator it = graph.entrySet().iterator(); it.hasNext(); ){
943 Map.Entry entry = (Map.Entry) it.next();
944 Object key = entry.getKey();
945 Object value = entry.getValue();
946 Object keyRep = uf.find(key);
947 Object valueRep = uf.find(value);
948 newGraph.add(keyRep, valueRep);
949 }
950 graph = newGraph;
951 nodes = newNodes;
952 }
953
954 public ConstraintGraph(Collection constraints) {
955 this();
956 for (Iterator it = constraints.iterator(); it.hasNext();) {
957 Pair p = (Pair) it.next();
958 Object o1 = p.left;
959 Object o2 = p.right;
960 graph.add(o1, o2);
961 nodes.add(o1);
962 nodes.add(o2);
963 }
964 }
965
966 public ConstraintGraph(Collection nodes, Collection constraints) {
967 this();
968 this.nodes.addAll(nodes);
969 for (Iterator it = constraints.iterator(); it.hasNext();) {
970 Pair p = (Pair) it.next();
971 Object o1 = p.left;
972 Object o2 = p.right;
973 graph.add(o1, o2);
974 }
975 }
976
977 public void addEdge(Object o1, Object o2) {
978 graph.add(o1, o2);
979 }
980
981 public void removeEdge(Object o1, Object o2){
982 graph.remove(o1, o2);
983 }
984
985 public void removeEdgesFrom(Object o) {
986 graph.remove(o);
987 }
988
989 public void addNode(Object o) {
990 nodes.add(o);
991 }
992 public void addNodes(Collection nodes){
993 this.nodes.addAll(nodes);
994 }
995 public void removeNode(Object o) {
996 nodes.remove(o);
997 }
998
999 /***
1000 * @return collection of nodes
1001 */
1002 public Collection getNodes() {
1003 return nodes;
1004 }
1005
1006 public boolean isCycle(List cycle) {
1007 for (Iterator it = nodes.iterator(); it.hasNext();) {
1008 Object obj = it.next();
1009 if (isPath(obj, obj,cycle)) return true;
1010 }
1011 return false;
1012 }
1013
1014 public boolean isPath(Object start, Object end, List path) {
1015 return isPath(start, end, new HashSet(), path);
1016 }
1017
1018 private boolean isPath(Object start, Object target, Set visited, List path) {
1019 path.add(start);
1020 visited.add(start);
1021
1022 Collection nexts = graph.getValues(start);
1023
1024 for (Iterator it = nexts.iterator(); it.hasNext();) {
1025 Object next = it.next();
1026
1027 if (next == target) {
1028 return true;
1029 }
1030 if (!visited.contains(next))
1031 if (isPath(next, target, visited, path))
1032 return true;
1033 }
1034 path.remove(start);
1035 return false;
1036 }
1037
1038 public Collection getRoots() {
1039 Set roots = new HashSet(nodes);
1040 roots.removeAll(graph.values());
1041 return roots;
1042 }
1043
1044 public String toString() {
1045 return graph.toString();
1046 }
1047
1048 public ConstraintNavigator getNavigator() {
1049 return nav;
1050 }
1051 public class ConstraintNavigator implements Navigator {
1052
1053
1054
1055 public Collection next(Object node) {
1056 return graph.getValues(node);
1057 }
1058
1059
1060
1061
1062 public Collection prev(Object node) {
1063 throw new UnsupportedOperationException();
1064 }
1065 }
1066
1067 }
1068 }