// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
package edu.berkeley.sbp;
-import edu.berkeley.sbp.*;
-import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.Parser.Table.*;
import edu.berkeley.sbp.Sequence.Position;
-import java.io.*;
-import java.util.*;
-import java.lang.reflect.*;
final class Reduction implements Comparable<Reduction> {
- public Position position;
- public GSS.Phase phase;
- public Forest result;
- public Node node;
- boolean done = false;
+ private Position reduction;
+ private GSS.Phase phase;
+ private Forest forest;
+ private Node parent;
- public Reduction(Node node, Position position, Forest result, GSS.Phase target) {
- this.position = position;
- this.result = result;
+ public Reduction(Node parent, Position reduction, Forest forest, GSS.Phase target) {
+ this.reduction = reduction;
+ this.forest = forest;
this.phase = target;
- this.node = node;
- target.reductionQueue.add(this);
- }
-
- public void perform() {
- if (done) return;
- done = true;
- node.finish(position, result, phase);
+ this.parent = parent;
+ target.addReduction(this);
}
public int compareTo(Reduction r) {
- int ret = compareTo0(r);
- if (ret != 0) return -1 * ret;
- return (position.ord - r.position.ord);
- }
-
- private static boolean isRightNullable(Walk.Cache c, Position p) {
- if (p.isLast()) return true;
- if (!c.possiblyEpsilon(p.element())) return false;
- return isRightNullable(c, p.next());
- }
-
- public static boolean canKill(Walk.Cache cache, Position mep, Position himp) {
- if (!isRightNullable(cache, mep)) return false;
- if (!isRightNullable(cache, himp)) return false;
- Sequence me = mep.owner();
- Sequence him = himp.owner();
- Boolean b = me.canKill.get(him);
- if (b!=null) return b;
- for(Sequence killer : him.hates()) {
- HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
- if (eq2.contains(me)) { me.canKill.put(him, true); return true; }
+ if (parent.phase()!=null || r.parent.phase()!=null) {
+ if (parent.phase()==null) return 1;
+ if (r.parent.phase()==null) return -1;
+ if (parent.phase().pos < r.parent.phase().pos) return 1;
+ if (parent.phase().pos > r.parent.phase().pos) return -1;
}
- me.canKill.put(him, false);
- return false;
+ /*
+ int master = Parser.mastercache.comparePositions(reduction(), r.reduction());
+ if (master != 0 && master != signum(reduction.ord - r.reduction.ord))
+ throw new Error("master="+master+" and a="+reduction.ord+" and b="+r.reduction.ord+"\n"+reduction+"\n"+r.reduction);
+ */
+ return reduction.ord - r.reduction.ord;
}
- public static final int LESS_THAN = -1;
- public static final int EQUAL_TO = 0;
- public static final int GREATER_THAN = 1;
-
- public int compareTo0(Reduction n) {
- if (targetPhase()==null && n.targetPhase()==null) return EQUAL_TO;
- if (targetPhase()==null) return LESS_THAN;
- if (n.targetPhase()==null) return GREATER_THAN;
- if (targetPhase().pos < n.targetPhase().pos) return LESS_THAN;
- if (targetPhase().pos > n.targetPhase().pos) return GREATER_THAN;
- return 0;
+ private int signum(int x) {
+ if (x==0) return 0;
+ if (x<0) return -1;
+ return 1;
}
- public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; }
- public GSS.Phase targetPhase() { return node.phase(); }
- public static boolean canNeed(Walk.Cache cache, Position mep, Position himp) {
- if (!isRightNullable(cache, mep)) return false;
- if (!isRightNullable(cache, himp)) return false;
- Sequence me = mep.owner();
- Sequence him = himp.owner();
- Boolean b = me.canNeed.get(him);
- if (b!=null) return b;
- for(Sequence needer : him.needs()) {
- HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
- if (eq2.contains(me)) { me.canNeed.put(him, true); return true; }
- }
- me.canNeed.put(him, false);
- return false;
- }
+ public void perform() { new Result(forest, parent, reduction, phase); }
+ public GSS.Phase parentPhase() { return parent.phase(); }
+ public Position reduction() { return reduction; }
+ public GSS.Phase targetPhase() { return phase; }
+ public String toString() { return (parent.phase()==null ? 0 : parent.phase().pos) + ":"+reduction.ord+":"+ reduction+" "+reduction.owner(); }
}