001: package org.mandarax.reference;
002:
003: /*
004: * Copyright (C) 1999-2004 <A href="http://www-ist.massey.ac.nz/JBDietrich" target="_top">Jens Dietrich</a>
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation; either
009: * version 2 of the License, or (at your option) any later version.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: *
016: * You should have received a copy of the GNU Lesser General Public
017: * License along with this library; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019: */
020: import java.util.Iterator;
021: import java.util.Stack;
022: import java.util.Vector;
023:
024: import org.mandarax.kernel.Clause;
025:
026: /**
027: * Builder for a derivation tree. Takes the root node of a linear
028: * derivation as input and outputs the root node of the derivation
029: * tree.
030: * @author <A href="http://www-ist.massey.ac.nz/JBDietrich" target="_top">Jens Dietrich</A>
031: * @version 3.4 <7 March 05>
032: * @since 1.0
033: */
034: final class DerivationTreeBuilder {
035:
036: private class XDerivationNode extends
037: org.mandarax.reference.DerivationNodeImpl {
038:
039: public int expectedSubnodes = 0;
040: public boolean isFailedLeave = false;
041:
042: public boolean expectsMoreSubnodes() {
043: return expectedSubnodes < getSubNodes().size();
044: }
045: }
046:
047: /**
048: * Constructor.
049: */
050: public DerivationTreeBuilder() {
051: super ();
052: }
053:
054: /**
055: * Build a derivation tree.
056: * @return the root of the derivation tree
057: * @param oldRoot the first node of a (linear) chain of nodes
058: */
059: public DerivationNodeImpl buildTree(DerivationNodeImpl oldRoot) {
060: java.util.Vector linearNodes = linearize(oldRoot);
061:
062: linkNodes(linearNodes, new java.util.Stack(), 0);
063:
064: return (DerivationNodeImpl) linearNodes.elementAt(0);
065: }
066:
067: /**
068: * Linearize the derivation nodes.
069: * @return a collection
070: * @param oldRoot a derivation node
071: */
072: private java.util.Vector linearize(DerivationNodeImpl oldRoot) {
073: Vector coll = new Vector();
074:
075: linearize(oldRoot, coll);
076:
077: return coll;
078: }
079:
080: /**
081: * Linearize the derivation nodes.
082: * @param aNode a derivation node
083: * @param aCollection a collection
084: */
085: private void linearize(DerivationNodeImpl aNode,
086: java.util.Vector aCollection) {
087:
088: // first build a new XNode for aNode and add it to the collection
089: XDerivationNode aNewNode = new XDerivationNode();
090:
091: aNewNode.setFailed(aNode.isFailed());
092: aNewNode.setUnification(aNode.getUnification());
093:
094: Clause applied = aNode.getAppliedClause();
095:
096: aNewNode.setAppliedClause(applied);
097: aNewNode.setQuery(aNode.getQuery());
098:
099: aNewNode.expectedSubnodes = (applied == null) ? 1 : applied
100: .getNegativeLiterals().size();
101: aNewNode.isFailedLeave = aNode.isFailed()
102: && aNode.getSubNodes().isEmpty();
103:
104: aCollection.addElement(aNewNode);
105:
106: // then add all subnodes
107: for (Iterator it = aNode.getSubNodes().iterator(); it.hasNext();) {
108: linearize((DerivationNodeImpl) it.next(), aCollection);
109: }
110: }
111:
112: /**
113: * Link the nodes in the structure.
114: * @param nodes a collection of nodes
115: * @param stack stack of nodes
116: * @param index the position
117: */
118: private void linkNodes(Vector nodes, Stack stack, int index) {
119:
120: // handling if stack is empty
121: if ((nodes.size() == index) || (stack.isEmpty() && (index > 0))) {
122: return;
123: }
124:
125: // handling if index is 0 (root node)
126: if (index == 0) {
127: XDerivationNode rootNode = (XDerivationNode) nodes
128: .elementAt(0);
129:
130: if (rootNode.expectedSubnodes > 0) {
131: stack.push(rootNode);
132: linkNodes(nodes, stack, 1);
133: }
134:
135: return;
136: }
137:
138: // general case
139: XDerivationNode aNode = (XDerivationNode) nodes
140: .elementAt(index);
141: XDerivationNode previousNode = (XDerivationNode) stack.peek();
142: previousNode.addSubNode(aNode);
143:
144: if (aNode.isFailed()) {
145: if (aNode.isFailedLeave) {
146: removeAllFailedNodes(stack);
147: } else {
148: if (aNode.expectedSubnodes > 0) {
149: stack.push(aNode);
150: }
151: }
152: } else {
153: previousNode.expectedSubnodes = previousNode.expectedSubnodes - 1;
154:
155: if (previousNode.expectedSubnodes == 0) {
156: stack.pop();
157: }
158:
159: if (aNode.expectedSubnodes > 0) {
160: stack.push(aNode);
161: }
162: }
163:
164: linkNodes(nodes, stack, index + 1);
165: }
166:
167: /**
168: * Remove all failed nodes from a stack.
169: * @param stack the stack of nodes
170: */
171: private void removeAllFailedNodes(Stack stack) {
172: if (stack.size() == 0)
173: return;
174: XDerivationNode top = (XDerivationNode) stack.peek();
175: if (top.isFailed()) {
176: stack.pop();
177: removeAllFailedNodes(stack);
178: }
179:
180: return;
181: }
182: }
|