Source code: com/aendvari/common/osm/QueryOsmPath.java
1 /*
2 * QueryOsmPath.java
3 *
4 * Copyright (c) 2001, 2002 Aendvari, Ltd. All Rights Reserved.
5 *
6 * See the file LICENSE for terms of use.
7 *
8 */
9
10 package com.aendvari.common.osm;
11
12 import java.util.ArrayList;
13 import java.util.Collection;
14 import java.util.Iterator;
15 import java.util.List;
16 import java.util.StringTokenizer;
17
18 import com.aendvari.common.osm.OsmNode;
19 import com.aendvari.common.osm.OsmException;
20
21 /**
22 * <p>Provides the ability to access nodes within an Object Space Model
23 * using an expression.</p>
24 *
25 * <p>This class allows the selection of single and multiple nodes.</p>
26 *
27 * @author Trevor Milne
28 *
29 */
30
31 public class QueryOsmPath
32 {
33 /* Attributes. */
34
35
36 /** Contains the compiled query expression. */
37 private List operations;
38
39
40 /* Constructors. */
41
42
43 /**
44 * Constructs an <code>QueryOsmPath</code> instance.
45 *
46 * @param expression Query expression for node selection.
47 *
48 */
49
50 public QueryOsmPath(String expression)
51 {
52 // compile the query expression
53 compile(expression);
54 }
55
56
57 /* Expressions. */
58
59
60 /**
61 * Selects a single node using the compiled expression.
62 *
63 * @param context The context node specifying the root of the expression.
64 *
65 * @return The node found using the expression, null if a node cannot be found.
66 *
67 */
68
69 public OsmNode selectNode(OsmNode context)
70 {
71 // select node using expression
72 return selectNode(context, 0);
73 }
74
75 /**
76 * Selects a multiple nodes using the compiled expression.
77 *
78 * @param context The context node specifying the root of the expression.
79 *
80 * @return A <code>Collection</code> of the selected {@link OsmNode OsmNodes}. Will not be null.
81 *
82 */
83
84 public Collection selectNodes(OsmNode context)
85 {
86 ArrayList nodes = new ArrayList();
87
88 // select nodes
89 selectNodes(context, 0, nodes);
90
91 return nodes;
92 }
93
94 /**
95 * Uses the expression to select a single node.
96 *
97 * @param context The context node specifying the root of the expression.
98 * @param expression Query expression to select the node.
99 *
100 * @return The node found using the expression, null if a node cannot be found.
101 *
102 */
103
104 public static OsmNode selectNode(OsmNode context, String expression)
105 {
106 QueryOsmPath query = new QueryOsmPath(expression);
107
108 return query.selectNode(context);
109 }
110
111 /**
112 * Uses the expression to select multiple nodes.
113 *
114 * @param context The context node specifying the root of the expression.
115 * @param expression Query expression to select the nodes.
116 *
117 * @return A <code>Collection</code> of the selected {@link OsmNode OsmNodes}. Can not be null.
118 *
119 */
120
121 public static Collection selectNodes(OsmNode context, String expression)
122 {
123 QueryOsmPath query = new QueryOsmPath(expression);
124
125 return query.selectNodes(context);
126 }
127
128
129 /* Single selection */
130
131
132 /**
133 * Selects a child node based on its name.
134 *
135 * @param operator The current operation.
136 * @param context The node being searched.
137 * @param operationIndex The current operation.
138 *
139 */
140
141 protected OsmNode selectNodeByName(Operator operator, OsmNode context, int operationIndex)
142 {
143 String segment = operator.stringParameter;
144 boolean any = segment.equals("*");
145
146 // get array of children
147 OsmNode children[] = new OsmNode[context.children.size()];
148 context.children.toArray(children);
149
150 // search children for name
151 int childIndex;
152 for (childIndex = 0; childIndex < children.length; childIndex++)
153 {
154 OsmNode child = children[childIndex];
155
156 // pick either the first in the group, or the first name match
157 if (any || child.name.equals(segment))
158 {
159 // continue evaluating expression on the selected node
160 return selectNode(child, (operationIndex + 1));
161 }
162 }
163
164 // no match found
165 return null;
166 }
167
168 /**
169 * Selects a child node based on its position.
170 *
171 * @param operator The current operation.
172 * @param context The node being searched.
173 * @param operationIndex The current operation.
174 *
175 */
176
177 protected OsmNode selectNodeByIndex(Operator operator, OsmNode context, int operationIndex)
178 {
179 String segment = operator.stringParameter;
180
181 // find the n'th node
182 int nodeIndex = 1;
183
184 // get array of children
185 OsmNode children[] = new OsmNode[context.children.size()];
186 context.children.toArray(children);
187
188 // search children for name
189 int childIndex;
190 for (childIndex = 0; childIndex < children.length; childIndex++)
191 {
192 OsmNode child = children[childIndex];
193
194 // check each node matching the segment
195 if (child.name.equals(segment))
196 {
197 // continue until the n'th named node is found
198 if (nodeIndex == operator.intParameter)
199 {
200 // continue evaluating expression on the selected node
201 return selectNode(child, (operationIndex + 1));
202 }
203
204 nodeIndex++;
205 }
206 }
207
208 // no match found
209 return null;
210 }
211
212 /**
213 * Performs the query expression operations for a single node selection.
214 *
215 * @param context The node being searched.
216 * @param operationIndex The current operation.
217 *
218 */
219
220 protected OsmNode selectNode(OsmNode context, int operationIndex)
221 {
222 // if at the end of the expression, select the context node
223 if (operationIndex == operations.size())
224 {
225 return context;
226 }
227
228 // get the next operator
229 Operator operator = (Operator)operations.get(operationIndex);
230
231 // select by name
232 if (operator.type == Operator.Type.SelectNode)
233 {
234 return selectNodeByName(operator, context, operationIndex);
235 }
236 else
237 // select by index
238 if (operator.type == Operator.Type.SelectIndex)
239 {
240 return selectNodeByIndex(operator, context, operationIndex);
241 }
242
243 // bad operation
244 return null;
245 }
246
247
248 /* Multiple selection */
249
250
251 /**
252 * Selects child nodes based on their name.
253 *
254 * @param operator The current operation.
255 * @param context The node being searched.
256 * @param operationIndex The current operation.
257 * @param nodes The collection to store selected nodes.
258 *
259 */
260
261 protected void selectNodesByName(Operator operator, OsmNode context, int operationIndex, Collection nodes)
262 {
263 String segment = operator.stringParameter;
264 boolean any = segment.equals("*");
265
266 // get array of children
267 OsmNode children[] = new OsmNode[context.children.size()];
268 context.children.toArray(children);
269
270 // search children for name
271 int childIndex;
272 for (childIndex = 0; childIndex < children.length; childIndex++)
273 {
274 OsmNode child = children[childIndex];
275
276 // traverse down each node matching the segment
277 if (any || child.name.equals(segment))
278 {
279 // continue evaluating expression on the selected node
280 selectNodes(child, (operationIndex + 1), nodes);
281 }
282 }
283 }
284
285 /**
286 * Selects a child node based on its position.
287 *
288 * @param operator The current operation.
289 * @param context The node being searched.
290 * @param operationIndex The current operation.
291 * @param nodes The collection to store selected nodes.
292 *
293 */
294
295 protected void selectNodesByIndex(Operator operator, OsmNode context, int operationIndex, Collection nodes)
296 {
297 String segment = operator.stringParameter;
298
299 // find the n'th node
300 int nodeIndex = 1;
301
302 // get array of children
303 OsmNode children[] = new OsmNode[context.children.size()];
304 context.children.toArray(children);
305
306 // search children for name
307 int childIndex;
308 for (childIndex = 0; childIndex < children.length; childIndex++)
309 {
310 OsmNode child = children[childIndex];
311
312 // check each node matching the segment
313 if (child.name.equals(segment))
314 {
315 // continue until the n'th named node is found
316 if (nodeIndex == operator.intParameter)
317 {
318 // continue evaluating expression on the selected node
319 selectNodes(child, (operationIndex + 1), nodes);
320
321 break;
322 }
323
324 nodeIndex++;
325 }
326 }
327 }
328
329 /**
330 * Performs the query expression operations for multiple node selection.
331 *
332 * @param context The node being searched.
333 * @param operationIndex The current operation.
334 * @param nodes The collection to store selected nodes.
335 *
336 */
337
338 protected void selectNodes(OsmNode context, int operationIndex, Collection nodes)
339 {
340 // if at the end of the expression, select the context node
341 if (operationIndex == operations.size())
342 {
343 nodes.add(context);
344 return;
345 }
346
347 // get the next operator
348 Operator operator = (Operator)operations.get(operationIndex);
349
350 // select by name
351 if (operator.type == Operator.Type.SelectNode)
352 {
353 selectNodesByName(operator, context, operationIndex, nodes);
354 }
355 else
356 // select by index
357 if (operator.type == Operator.Type.SelectIndex)
358 {
359 selectNodesByIndex(operator, context, operationIndex, nodes);
360 }
361 }
362
363
364 /* Expression compiling. */
365
366
367 /**
368 * Represents a single operation to perform during expression evaluation.
369 *
370 */
371
372 protected static class Operator
373 {
374 /** The operation to perform. */
375 public int type;
376
377 /** A string parameter for the operation. */
378 public String stringParameter;
379
380 /** An integer parameter for the operation. */
381 public int intParameter;
382
383 /* Constants. */
384
385
386 /** Defines the constants for the operation <code>type</code>. */
387 public interface Type
388 {
389 /** Select a node by its name. */
390 public static final int SelectNode = 1;
391
392 /** Select a node by its position. */
393 public static final int SelectIndex = 2;
394 }
395
396
397 /* Constructors. */
398
399
400 /**
401 * Creates an <code>Operator</code> instance.
402 *
403 */
404
405 public Operator(int setType, String setStringParameter, int setIntParameter)
406 {
407 type = setType;
408 stringParameter = setStringParameter;
409 intParameter = setIntParameter;
410 }
411 }
412
413 /**
414 * Parses a query expressions.
415 *
416 */
417
418 protected static class Parser
419 {
420 /** The current position in the string. */
421 protected int position;
422
423 /** The string to parse. */
424 protected String expression;
425
426
427 /* Constants. */
428
429
430 /** Constants for operator tokens. */
431 public interface Operators
432 {
433 /** Null operation. */
434 final static char Null = 'n';
435
436 /** Node select operation. */
437 final static char SelectNodeDot = '.';
438
439 /** Wilcard select operation. */
440 final static char SelectNodeWild = '*';
441
442 /** Node select operation. */
443 final static char SelectNodeSlash = '/';
444
445 /** Node index operation, start. */
446 final static char SelectIndexStart = '[';
447
448 /** Node index operation, end. */
449 final static char SelectIndexEnd = ']';
450 }
451
452
453 /* Construction */
454
455
456 /**
457 * Creates a <code>Tokenizer</code> to parse the supplied string.
458 *
459 * @param setExpression The expression to parse.
460 *
461 */
462
463 Parser(String setExpression)
464 {
465 expression = setExpression;
466 position = 0;
467 }
468
469
470 /* Parsing */
471
472 /**
473 * Returns true if more tokens are available.
474 *
475 * @return True if more tokens, false otherwise.
476 *
477 */
478
479 boolean hasMoreTokens()
480 {
481 // check for end of value
482 return (position < expression.length());
483 }
484
485 /**
486 * Returns the next available string.
487 *
488 * @return The next available string token, null if no tokens remain.
489 *
490 */
491
492 String getStringToken()
493 {
494 // check for end of value
495 if (position >= expression.length()) return null;
496
497 // search for end of next token
498 int nextPosition = position;
499
500 while (nextPosition < expression.length())
501 {
502 char letter = expression.charAt(nextPosition);
503
504 // check for operator
505 if ((letter == Operators.SelectNodeDot) ||
506 (letter == Operators.SelectNodeSlash) ||
507 (letter == Operators.SelectIndexStart) ||
508 (letter == Operators.SelectIndexEnd))
509 {
510 break;
511 }
512
513 nextPosition++;
514 }
515
516 // extract token
517 String token = expression.substring(position, nextPosition);
518
519 // start next token search at this delimiter
520 position = nextPosition;
521
522 return token;
523 }
524
525 /**
526 * Returns the next available operator.
527 *
528 * @return The next available operator token, null if no tokens remain.
529 *
530 */
531
532 char getOperatorToken()
533 {
534 // check for end of value
535 if (position >= expression.length()) return Operators.Null;
536
537 // retrieve operator
538 char token = expression.charAt(position);
539 position++;
540
541 return token;
542 }
543 }
544
545 /**
546 * Parses an index selection operator.
547 *
548 * @param parser The {@link Parser} being used for the expression.
549 * @param segment The segment that the index belongs to.
550 *
551 */
552
553 protected void parseIndexOperator(Parser parser, String segment)
554 {
555 // set to index operator
556 int type = Operator.Type.SelectIndex;
557
558 // get index, [n]
559 int index = Integer.parseInt(parser.getStringToken());
560
561 // get closing ']'
562 char op = parser.getOperatorToken();
563
564 // get next operator, if any
565 parser.getOperatorToken();
566
567 // create operator
568 operations.add(new Operator(type, segment, index));
569 }
570
571 /**
572 * Compiles the supplied query expression.
573 *
574 * @param expression Query expression to select the nodes.
575 *
576 */
577
578 protected void compile(String expression)
579 {
580 // create storage for compiled expression
581 operations = new ArrayList();
582
583 // initialize parser
584 Parser parser = new Parser(expression);
585
586 // check for initial operator
587 char start = expression.charAt(0);
588
589 if ((start == '.') || (start == '/'))
590 {
591 parser.getOperatorToken();
592 }
593
594 // parse expression
595 while (parser.hasMoreTokens())
596 {
597 // get node name
598 String segment = parser.getStringToken();
599
600 int type = Operator.Type.SelectNode;
601 int index = 0;
602
603 // read next operator
604 if (parser.hasMoreTokens())
605 {
606 char operator = parser.getOperatorToken();
607
608 // check if index operator follows
609 if (operator == Parser.Operators.SelectIndexStart)
610 {
611 parseIndexOperator(parser, segment);
612 }
613 else
614 {
615 // create "node" operator for previous operator
616 operations.add(new Operator(type, segment, index));
617 }
618 }
619 else
620 {
621 // create "node" operator for last operator
622 operations.add(new Operator(type, segment, index));
623 }
624 }
625 }
626 }
627