001: package org.ofbiz.rules.parse.tokens;
002:
003: import java.util.*;
004: import java.io.*;
005:
006: /**
007: * <p><b>Title:</b> Symbol Node
008: * <p><b>Description:</b> None
009: * <p>Copyright (c) 2000 Steven J. Metsker.
010: * <p>Copyright (c) 2001 The Open For Business Project - www.ofbiz.org
011: *
012: * <p>Permission is hereby granted, free of charge, to any person obtaining a
013: * copy of this software and associated documentation files (the "Software"),
014: * to deal in the Software without restriction, including without limitation
015: * the rights to use, copy, modify, merge, publish, distribute, sublicense,
016: * and/or sell copies of the Software, and to permit persons to whom the
017: * Software is furnished to do so, subject to the following conditions:
018: *
019: * <p>The above copyright notice and this permission notice shall be included
020: * in all copies or substantial portions of the Software.
021: *
022: * <p>THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
023: * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
024: * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
025: * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
026: * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
027: * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
028: * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
029: *
030: * <br>
031: * A <code>SymbolNode</code> object is a member of a tree that
032: * contains all possible prefixes of allowable symbols. Multi-
033: * character symbols appear in a <code>SymbolNode</code> tree
034: * with one node for each character.
035: *
036: * For example, the symbol <code>=:~</code> will appear in a
037: * tree as three nodes. The first node contains an equals sign,
038: * and has a child; that child contains a colon and has a
039: * child; this third child contains a tilde, and has no
040: * children of its own. If the colon node had another child
041: * for a dollar sign character, then the tree would contain
042: * the symbol <code>=:$</code>.
043: *
044: * A tree of <code>SymbolNode</code> objects collaborate to
045: * read a (potentially multi-character) symbol from an input
046: * stream. A root node with no character of its own finds an
047: * initial node that represents the first character in the
048: * input. This node looks to see if the next character in the
049: * stream matches one of its children. If so, the node
050: * delegates its reading task to its child. This approach
051: * walks down the tree, pulling symbols from the input that
052: * match the path down the tree.
053: *
054: * When a node does not have a child that matches the next
055: * character, we will have read the longest possible symbol
056: * prefix. This prefix may or may not be a valid symbol.
057: * Consider a tree that has had <code>=:~</code> added and has
058: * not had <code>=:</code> added. In this tree, of the three
059: * nodes that contain <code>=:~</code>, only the first and
060: * third contain complete symbols. If, say, the input contains
061: * <code>=:a</code>, the colon node will not have a child that
062: * matches the 'a' and so it will stop reading. The colon node
063: * has to "unread": it must push back its character, and ask
064: * its parent to unread. Unreading continues until it reaches
065: * an ancestor that represents a valid symbol.
066: *
067: * @author Steven J. Metsker
068: * @version 1.0
069: */
070: public class SymbolNode {
071: protected char myChar;
072: protected List children = new ArrayList(); // of Node
073: protected boolean valid = false;
074: protected SymbolNode parent;
075:
076: /**
077: * Constructs a SymbolNode with the given parent, representing
078: * the given character.
079: *
080: * @param SymbolNode this node's parent
081: *
082: * @param char this node's character
083: */
084: public SymbolNode(SymbolNode parent, char myChar) {
085: this .parent = parent;
086: this .myChar = myChar;
087: }
088:
089: /**
090: * Add a line of descendants that represent the characters
091: * in the given string.
092: */
093: protected void addDescendantLine(String s) {
094: if (s.length() > 0) {
095: char c = s.charAt(0);
096: SymbolNode n = ensureChildWithChar(c);
097:
098: n.addDescendantLine(s.substring(1));
099: }
100: }
101:
102: /**
103: * Show the symbol this node represents.
104: *
105: * @return the symbol this node represents
106: */
107: public String ancestry() {
108: return parent.ancestry() + myChar;
109: }
110:
111: /**
112: * Find the descendant that takes as many characters as
113: * possible from the input.
114: */
115: protected SymbolNode deepestRead(PushbackReader r)
116: throws IOException {
117:
118: char c = (char) r.read();
119: SymbolNode n = findChildWithChar(c);
120:
121: if (n == null) {
122: r.unread(c);
123: return this ;
124: }
125: return n.deepestRead(r);
126: }
127:
128: /**
129: * Find or create a child for the given character.
130: */
131: protected SymbolNode ensureChildWithChar(char c) {
132: SymbolNode n = findChildWithChar(c);
133:
134: if (n == null) {
135: n = new SymbolNode(this , c);
136: children.add(n);
137: }
138: return n;
139: }
140:
141: /**
142: * Find a child with the given character.
143: */
144: protected SymbolNode findChildWithChar(char c) {
145: Enumeration e = Collections.enumeration(children);
146:
147: while (e.hasMoreElements()) {
148: SymbolNode n = (SymbolNode) e.nextElement();
149:
150: if (n.myChar == c) {
151: return n;
152: }
153: }
154: return null;
155: }
156:
157: /**
158: * Find a descendant which is down the path the given string
159: * indicates.
160: */
161: protected SymbolNode findDescendant(String s) {
162: char c = s.charAt(0);
163: SymbolNode n = findChildWithChar(c);
164:
165: if (s.length() == 1) {
166: return n;
167: }
168: return n.findDescendant(s.substring(1));
169: }
170:
171: /**
172: * Mark this node as valid, which means its ancestry is a
173: * complete symbol, not just a prefix.
174: */
175: protected void setValid(boolean b) {
176: valid = b;
177: }
178:
179: /**
180: * Give a string representation of this node.
181: *
182: * @return a string representation of this node
183: */
184: public String toString() {
185: return "" + myChar + '(' + valid + ')';
186: }
187:
188: /**
189: * Unwind to a valid node; this node is "valid" if its
190: * ancestry represents a complete symbol. If this node is
191: * not valid, put back the character and ask the parent to
192: * unwind.
193: */
194: protected SymbolNode unreadToValid(PushbackReader r)
195: throws IOException {
196:
197: if (valid) {
198: return this;
199: }
200: r.unread(myChar);
201: return parent.unreadToValid(r);
202: }
203: }
|