symbolnode.java

国外的一套开源CRM

package org.ofbiz.rules.parse.tokens;


import java.util.*;
import java.io.*;


/**
 * <p><b>Title:</b> Symbol Node
 * <p><b>Description:</b> None
 * <p>Copyright (c) 2000 Steven J. Metsker.
 * <p>Copyright (c) 2001 The Open For Business Project - www.ofbiz.org
 *
 * <p>Permission is hereby granted, free of charge, to any person obtaining a
 *  copy of this software and associated documentation files (the "Software"),
 *  to deal in the Software without restriction, including without limitation
 *  the rights to use, copy, modify, merge, publish, distribute, sublicense,
 *  and/or sell copies of the Software, and to permit persons to whom the
 *  Software is furnished to do so, subject to the following conditions:
 *
 * <p>The above copyright notice and this permission notice shall be included
 *  in all copies or substantial portions of the Software.
 *
 * <p>THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 *  OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 *  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 *  CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
 *  OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
 *  THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * <br>
 * A <code>SymbolNode</code> object is a member of a tree that
 * contains all possible prefixes of allowable symbols. Multi-
 * character symbols appear in a <code>SymbolNode</code> tree
 * with one node for each character.
 *
 * For example, the symbol <code>=:~</code> will appear in a
 * tree as three nodes. The first node contains an equals sign,
 * and has a child; that child contains a colon and has a
 * child; this third child contains a tilde, and has no
 * children of its own. If the colon node had another child
 * for a dollar sign character, then the tree would contain
 * the symbol <code>=:$</code>.
 *
 * A tree of <code>SymbolNode</code> objects collaborate to
 * read a (potentially multi-character) symbol from an input
 * stream. A root node with no character of its own finds an
 * initial node that represents the first character in the
 * input. This node looks to see if the next character in the
 * stream matches one of its children. If so, the node
 * delegates its reading task to its child. This approach
 * walks down the tree, pulling symbols from the input that
 * match the path down the tree.
 *
 * When a node does not have a child that matches the next
 * character, we will have read the longest possible symbol
 * prefix. This prefix may or may not be a valid symbol.
 * Consider a tree that has had <code>=:~</code> added and has
 * not had <code>=:</code> added. In this tree, of the three
 * nodes that contain <code>=:~</code>, only the first and
 * third contain complete symbols. If, say, the input contains
 * <code>=:a</code>, the colon node will not have a child that
 * matches the 'a' and so it will stop reading. The colon node
 * has to "unread": it must push back its character, and ask
 * its parent to unread. Unreading continues until it reaches
 * an ancestor that represents a valid symbol.
 *
 * @author Steven J. Metsker
 * @version 1.0
 */
public class SymbolNode {
    protected char myChar;
    protected List children = new ArrayList(); // of Node
    protected boolean valid = false;
    protected SymbolNode parent;

    /**
     * Constructs a SymbolNode with the given parent, representing
     * the given character.
     *
     * @param   SymbolNode   this node's parent
     *
     * @param   char   this node's character
     */
    public SymbolNode(SymbolNode parent, char myChar) {
        this.parent = parent;
        this.myChar = myChar;
    }

    /**
     * Add a line of descendants that represent the characters
     * in the given string.
     */
    protected void addDescendantLine(String s) {
        if (s.length() > 0) {
            char c = s.charAt(0);
            SymbolNode n = ensureChildWithChar(c);

            n.addDescendantLine(s.substring(1));
        }
    }

    /**
     * Show the symbol this node represents.
     *
     * @return the symbol this node represents
     */
    public String ancestry() {
        return parent.ancestry() + myChar;
    }

    /**
     * Find the descendant that takes as many characters as
     * possible from the input.
     */
    protected SymbolNode deepestRead(PushbackReader r)
        throws IOException {

        char c = (char) r.read();
        SymbolNode n = findChildWithChar(c);

        if (n == null) {
            r.unread(c);
            return this;
        }
        return n.deepestRead(r);
    }

    /**
     * Find or create a child for the given character.
     */
    protected SymbolNode ensureChildWithChar(char c) {
        SymbolNode n = findChildWithChar(c);

        if (n == null) {
            n = new SymbolNode(this, c);
            children.add(n);
        }
        return n;
    }

    /**
     * Find a child with the given character.
     */
    protected SymbolNode findChildWithChar(char c) {
        Enumeration e = Collections.enumeration(children);

        while (e.hasMoreElements()) {
            SymbolNode n = (SymbolNode) e.nextElement();

            if (n.myChar == c) {
                return n;
            }
        }
        return null;
    }

    /**
     * Find a descendant which is down the path the given string
     * indicates.
     */
    protected SymbolNode findDescendant(String s) {
        char c = s.charAt(0);
        SymbolNode n = findChildWithChar(c);

        if (s.length() == 1) {
            return n;
        }
        return n.findDescendant(s.substring(1));
    }

    /**
     * Mark this node as valid, which means its ancestry is a
     * complete symbol, not just a prefix.
     */
    protected void setValid(boolean b) {
        valid = b;
    }

    /**
     * Give a string representation of this node.
     *
     * @return a string representation of this node
     */
    public String toString() {
        return "" + myChar + '(' + valid + ')';
    }

    /**
     * Unwind to a valid node; this node is "valid" if its
     * ancestry represents a complete symbol. If this node is
     * not valid, put back the character and ask the parent to
     * unwind.
     */
    protected SymbolNode unreadToValid(PushbackReader r)
        throws IOException {

        if (valid) {
            return this;
        }
        r.unread(myChar);
        return parent.unreadToValid(r);
    }
}