From fe637b465179cf2a217bbfc76d12bc41551b4ac4 Mon Sep 17 00:00:00 2001
From: adam <adam@megacz.com>
Date: Sun, 25 Feb 2007 20:34:37 -0500
Subject: [PATCH] add killing of doomed nodes via Node.check()/Result.check()
 methods

darcs-hash:20070226013437-5007d-8b3860db0ef782cfcbc57d9b33d4fedca6db2075.gz
---
 src/edu/berkeley/sbp/GSS.java    |    1 +
 src/edu/berkeley/sbp/Node.java   |   37 +++++++++++++++++++++++++++++++++++++
 src/edu/berkeley/sbp/Result.java |   35 +++++++++++++++++++++++++++++++++++
 3 files changed, 73 insertions(+)

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index f222fe5..91ef765 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -89,6 +89,7 @@ class GSS {
                 if (token == null) continue;
                 n.state().invokeShifts(token, this, new Result(result, n, null), null);
             }
+            for(Node n : hash.values()) n.check();
             if (!good && token!=null) ParseFailed.error("unexpected character", this);
             if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
         }
diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java
index b360071..1d5e05a 100644
--- a/src/edu/berkeley/sbp/Node.java
+++ b/src/edu/berkeley/sbp/Node.java
@@ -26,11 +26,43 @@ final class Node
     public boolean merge(Result r) {
         if (results.contains(r)) return true;
         results.add(r);
+        r.addChild(this);
         if (fromEmptyReduction) return false;
         state.invokeReductions(phase().getToken(), this, false, r);
         return false;
     }
 
+    private boolean destroyed = false;
+    public boolean check() {
+        boolean dead = true;
+        // - all nodes must have a parent
+        // - non-doomed nodes must either:
+        //      - be on the frontier or
+        //      - have a non-doomed node closer to the frontier than themself
+
+        if (phase.isFrontier()) dead = false;
+        for(Result r : children)
+            if (state.doomed) { if (r.usedByAnyNode()) dead = false; }
+            else              { if (r.usedByNonDoomedNode()) dead = false; }
+        dead |= results.size()==0;
+        if (!dead || destroyed) return dead;
+        destroyed = true;
+        while(children.size()>0)
+            for(Result r : children) {
+                children.remove(r);
+                r.destroy();
+                break;
+            }
+        while(results.size()>0)
+            for(Result r : results) {
+                results.remove(r);
+                r.removeChild(this);
+                r.check();
+                break;
+            }
+        return dead;
+    }
+
     //////////////////////////////////////////////////////////////////////
 
     private static int node_idx = 0;
@@ -41,6 +73,10 @@ final class Node
     private final boolean fromEmptyReduction;
     //private       FastSet<Result> results = new FastSet<Result>();
     private       HashSet<Result> results = new HashSet<Result>();
+    private       HashSet<Result> children = new HashSet<Result>();
+    public void removeChild(Result child) { children.remove(child); }
+    public void removeResult(Result result) { results.remove(result); }
+    public void addChild(Result child) { children.add(child); }
 
     public final void invoke(Position r, Boolean emptyProductions, Result only) {
         if (emptyProductions != (r.pos==0)) return;
@@ -72,6 +108,7 @@ final class Node
         this.state = state;
         this.fromEmptyReduction = fromEmptyReduction;
         results.add(result);
+        result.addChild(this);
         if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
         phase.hash.put(state, result.phase(), this);
 
diff --git a/src/edu/berkeley/sbp/Result.java b/src/edu/berkeley/sbp/Result.java
index cb351eb..7888625 100644
--- a/src/edu/berkeley/sbp/Result.java
+++ b/src/edu/berkeley/sbp/Result.java
@@ -15,16 +15,51 @@ class Result implements GraphViz.ToGraphViz {
     private Node parent;
     private GSS.Phase phase;
     private Position reduction;
+    private HashSet<Node> children = new HashSet<Node>();
+    private boolean destroyed = false;
 
     public Position reduction() { return reduction; }
     public GSS.Phase phase() { return phase; }
     public Forest getForest() { return f; }
     public Node parent() { return parent; }
+    public void addChild(Node child) { children.add(child); }
+    public void removeChild(Node child) { children.remove(child); }
+
+    public boolean usedByAnyNode() { return children.size() > 0; }
+    public boolean usedByNonDoomedNode() {
+        for(Node n : children)
+            if (!n.state().doomed)
+                return true;
+        return false;
+    }
+
+    public String toString() { return super.toString()+"->"+parent(); }
+
+    public void check() { if (children.size()==0) destroy(); }
+    public void destroy() {
+        if (destroyed) return;
+        if (parent==null) return;  // never destroy the "primordeal" result
+        destroyed = true;
+        if (parent() != null) {
+            parent().removeChild(this);
+            parent().check();
+        }
+        OUTER: while(true) {
+            for(Node n : children) {
+                children.remove(n);
+                n.removeResult(this);
+                n.check();
+                continue OUTER;
+            }
+            break;
+        }
+    }
 
     public Result(Forest f, Node parent, Position reduction) {
         this.f = f;
         this.reduction = reduction;
         this.parent = parent;
+        if (parent != null) parent.addChild(this);
         if (parent != null) phase = parent.phase();
     }
 
-- 
1.7.10.4