001: /*
002: * Created on 8-Jan-2005
003: *
004: * TODO To change the template for this generated file go to
005: * Window - Preferences - Java - Code Style - Code Templates
006: */
007: package net.refractions.udig.catalog.util;
008:
009: import java.util.LinkedList;
010: import java.util.List;
011: import java.util.ListIterator;
012: import java.util.Stack;
013:
014: /**
015: * @author David Zwiers, Refractions Research
016: */
017: public class ASTFactory {
018: private ASTFactory() {/* not used */
019: }
020:
021: /**
022: * Creates an AST for the pattern The pattern uses the following conventions: use " " to
023: * surround a phase use + to represent 'AND' use - to represent 'OR' use ! to represent 'NOT'
024: * use ( ) to designate scope
025: *
026: * @param pattern Search pattern
027: * @return AST
028: */
029: public static AST parse(String str) {
030: List<String> tokens = tokenize(str);
031: Stack<AST> s = new Stack<AST>();
032: ListIterator<String> li = tokens.listIterator();
033:
034: // create the ast
035: while (li.hasNext())
036: node(s, li);
037: if (s.size() == 1) {
038: return s.pop();
039: }
040: if (s.size() > 1) {
041: // assume they are anded ... TODO balance the tree
042: while (s.size() > 1) {
043: AST p1 = s.pop();
044: AST p2 = s.pop();
045: s.push(new And(p1, p2));
046: }
047: return s.pop();
048: }
049: System.err
050: .println("An internal error creating an AST may have occured"); //$NON-NLS-1$
051: return null;
052: }
053:
054: protected static List<String> tokenize(String pattern) {
055: List<String> l = new LinkedList<String>();
056: for (int i = 0; i < pattern.length(); i++) {
057: char c = pattern.charAt(i);
058: switch (c) {
059: case '(':
060: l.add("("); //$NON-NLS-1$
061: break;
062: case ')':
063: l.add(")"); //$NON-NLS-1$
064: break;
065: case '+':
066: l.add("+"); //$NON-NLS-1$
067: break;
068: case '-':
069: l.add("-"); //$NON-NLS-1$
070: break;
071: case '!':
072: l.add("!"); //$NON-NLS-1$
073: break;
074: case '"':
075: // greedy grab
076: int j = pattern.indexOf('"', i + 1);
077: l.add(pattern.substring(i + 1, j));
078: i = j;
079: break;
080: case ' ':
081: case '\t':
082: case '\n':
083: // skip
084: break;
085: case 'A':// ND
086: if (pattern.charAt(i + 1) == 'N'
087: && pattern.charAt(i + 2) == 'D') {
088: // it's a +
089: l.add("+"); //$NON-NLS-1$
090: i += 2;
091: }
092: break;
093: case 'O':// R
094: if (pattern.charAt(i + 1) == 'R') {
095: // it's a +
096: l.add("-"); //$NON-NLS-1$
097: i += 1;
098: }
099: break;
100: case 'N':// OT
101: if (pattern.charAt(i + 1) == 'O'
102: && pattern.charAt(i + 2) == 'T') {
103: // it's a +
104: l.add("!"); //$NON-NLS-1$
105: i += 2;
106: }
107: default:
108: // greedy grab
109: j = i + 1;
110: while (j < pattern.length() && pattern.charAt(j) != '"'
111: && pattern.charAt(j) != '+'
112: && pattern.charAt(j) != '-'
113: && pattern.charAt(j) != '!'
114: && pattern.charAt(j) != '('
115: && pattern.charAt(j) != ')'
116: && pattern.charAt(j) != ' '
117: && pattern.charAt(j) != '\t'
118: && pattern.charAt(j) != '\n')
119: j++;
120: l.add(pattern.substring(i, j));
121: i = (i == j ? j : j - 1);
122: }
123: }
124: return l;
125: }
126:
127: private static void node(Stack<AST> s, ListIterator<String> li) {
128: if (li.hasNext()) {
129: String token = li.next();
130:
131: char c = token.charAt(0);
132: switch (c) {
133: case '(':
134: // child is what we want
135: node(s, li);
136: break;
137: case ')':
138: // ignore this
139: break;
140: case '+':
141: AST prev = s.pop();
142: node(s, li);
143: AST next = s.pop();
144: s.push(new And(prev, next));
145: break;
146: case '-':
147: prev = s.pop();
148: node(s, li);
149: next = s.pop();
150: s.push(new Or(prev, next));
151: break;
152: case '!':
153: node(s, li);
154: next = s.pop();
155: s.push(new Not(next));
156: break;
157: default:
158: s.push(new Literal(token));
159: }
160: }
161: }
162:
163: private static class And implements AST {
164: private AST left, right;
165:
166: private And() {/* should not be used */
167: }
168:
169: public And(AST left, AST right) {
170: this .left = left;
171: this .right = right;
172: }
173:
174: /**
175: * TODO summary sentence for accept ...
176: *
177: * @see net.refractions.udig.catalog.internal.CatalogImpl.AST#accept(java.lang.String)
178: * @param datum
179: * @return
180: */
181: public boolean accept(String datum) {
182: return left != null && right != null && left.accept(datum)
183: && right.accept(datum);
184: }
185:
186: /**
187: * TODO summary sentence for type ...
188: *
189: * @see net.refractions.udig.catalog.internal.CatalogImpl.AST#type()
190: * @return
191: */
192: public int type() {
193: return AND;
194: }
195:
196: /*
197: * (non-Javadoc)
198: *
199: * @see net.refractions.udig.catalog.util.AST#getLeft()
200: */
201: public AST getLeft() {
202: return left;
203: }
204:
205: /*
206: * (non-Javadoc)
207: *
208: * @see net.refractions.udig.catalog.util.AST#getRight()
209: */
210: public AST getRight() {
211: return right;
212: }
213: }
214:
215: private static class Or implements AST {
216: private AST left, right;
217:
218: private Or() {/* should not be used */
219: }
220:
221: public Or(AST left, AST right) {
222: this .left = left;
223: this .right = right;
224: }
225:
226: /**
227: * TODO summary sentence for accept ...
228: *
229: * @see net.refractions.udig.catalog.internal.CatalogImpl.AST#accept(java.lang.String)
230: * @param datum
231: * @return
232: */
233: public boolean accept(String datum) {
234: return (right != null && right.accept(datum))
235: || (left != null && left.accept(datum));
236: }
237:
238: /**
239: * TODO summary sentence for type ...
240: *
241: * @see net.refractions.udig.catalog.internal.CatalogImpl.AST#type()
242: * @return
243: */
244: public int type() {
245: return OR;
246: }
247:
248: /*
249: * (non-Javadoc)
250: *
251: * @see net.refractions.udig.catalog.util.AST#getLeft()
252: */
253: public AST getLeft() {
254: return left;
255: }
256:
257: /*
258: * (non-Javadoc)
259: *
260: * @see net.refractions.udig.catalog.util.AST#getRight()
261: */
262: public AST getRight() {
263: return right;
264: }
265: }
266:
267: private static class Not implements AST {
268: private AST child;
269:
270: private Not() {/* should not be used */
271: }
272:
273: public Not(AST child) {
274: this .child = child;
275: }
276:
277: /**
278: * TODO summary sentence for accept ...
279: *
280: * @see net.refractions.udig.catalog.internal.CatalogImpl.AST#accept(java.lang.String)
281: * @param datum
282: * @return
283: */
284: public boolean accept(String datum) {
285: return !(child != null && child.accept(datum));
286: }
287:
288: /**
289: * TODO summary sentence for type ...
290: *
291: * @see net.refractions.udig.catalog.internal.CatalogImpl.AST#type()
292: * @return
293: */
294: public int type() {
295: return NOT;
296: }
297:
298: /*
299: * (non-Javadoc)
300: *
301: * @see net.refractions.udig.catalog.util.AST#getLeft()
302: */
303: public AST getLeft() {
304: return child;
305: }
306:
307: /*
308: * (non-Javadoc)
309: *
310: * @see net.refractions.udig.catalog.util.AST#getRight()
311: */
312: public AST getRight() {
313: return null;
314: }
315: }
316:
317: private static class Literal implements AST {
318: private String value;
319:
320: private Literal() {/* should not be used */
321: }
322:
323: public Literal(String value) {
324: this .value = value;
325: }
326:
327: /**
328: * TODO summary sentence for accept ...
329: *
330: * @see net.refractions.udig.catalog.internal.CatalogImpl.AST#accept(java.lang.String)
331: * @param datum
332: * @return
333: */
334: public boolean accept(String datum) {
335: // TODO check this
336: return value != null
337: && datum != null
338: && datum.toUpperCase().indexOf(value.toUpperCase()) > -1;
339: }
340:
341: /**
342: * TODO summary sentence for type ...
343: *
344: * @see net.refractions.udig.catalog.internal.CatalogImpl.AST#type()
345: * @return
346: */
347: public int type() {
348: return LITERAL;
349: }
350:
351: /*
352: * (non-Javadoc)
353: *
354: * @see net.refractions.udig.catalog.util.AST#getLeft()
355: */
356: public AST getLeft() {
357: return null;
358: }
359:
360: /*
361: * (non-Javadoc)
362: *
363: * @see net.refractions.udig.catalog.util.AST#getRight()
364: */
365: public AST getRight() {
366: return null;
367: }
368:
369: public String toString() {
370: return value;
371: }
372: }
373:
374: }
|