PrefetchTreeNode


1   /*****************************************************************
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   ****************************************************************/
19  
20  package org.apache.cayenne.query;
21  
22  import java.io.ObjectStreamException  ;
23  import java.io.Serializable  ;
24  import java.util.ArrayList  ;
25  import java.util.Collection  ;
26  import java.util.Collections  ;
27  import java.util.Iterator  ;
28  import java.util.StringTokenizer  ;
29  
30  import org.apache.cayenne.map.Entity;
31  import org.apache.cayenne.util.Util;
32  import org.apache.cayenne.util.XMLEncoder;
33  import org.apache.cayenne.util.XMLSerializable;
34  
35  /**
36   * Defines a node in a prefetch tree.
37   * 
38   * @since 1.2
39   * @author Andrus Adamchik
40   */
41  public class PrefetchTreeNode implements Serializable  , XMLSerializable {
42  
43      public static final int UNDEFINED_SEMANTICS = 0;
44      public static final int JOINT_PREFETCH_SEMANTICS = 1;
45      public static final int DISJOINT_PREFETCH_SEMANTICS = 2;
46  
47      protected String   name;
48      protected boolean phantom;
49      protected int semantics;
50  
51      // transient parent allows cloning parts of the tree via serialization
52      protected transient PrefetchTreeNode parent;
53  
54      // Using Collection instead of Map for children storage (even though there cases of
55      // lookup by segment) is a reasonable tradeoff considering that
56      // each node has no more than a few children and lookup by name doesn't happen on
57      // traversal, only during creation.
58      protected Collection   children;
59  
60      /**
61       * Creates a root node of the prefetch tree. Children can be added to the parent by
62       * calling "addPath".
63       */
64      public PrefetchTreeNode() {
65          this(null, null);
66      }
67  
68      /**
69       * Creates a phantom PrefetchTreeNode, initializing it with parent node and a name of
70       * a relationship segment connecting this node with the parent.
71       */
72      protected PrefetchTreeNode(PrefetchTreeNode parent, String   segmentPath) {
73          this.parent = parent;
74          this.name = segmentPath;
75          this.phantom = true;
76          this.semantics = UNDEFINED_SEMANTICS;
77      }
78  
79      public void encodeAsXML(XMLEncoder encoder) {
80          traverse(new XMLEncoderOperation(encoder));
81      }
82  
83      /**
84       * Returns the root of the node tree. Root is the topmost parent node that itself has
85       * no parent set.
86       */
87      public PrefetchTreeNode getRoot() {
88          return (parent != null) ? parent.getRoot() : this;
89      }
90  
91      /**
92       * Returns full prefetch path, that is a dot separated String of node names starting
93       * from root and up to and including this node. Note that root "name" is considered to
94       * be an empty string.
95       */
96      public String   getPath() {
97          return getPath(null);
98      }
99  
100     public String   getPath(PrefetchTreeNode upTillParent) {
101         if (parent == null || upTillParent == this) {
102             return "";
103         }
104 
105         StringBuffer   path = new StringBuffer  (getName());
106         PrefetchTreeNode node = this.getParent();
107 
108         // root node has no path
109         while (node.getParent() != null && node != upTillParent) {
110             path.insert(0, node.getName() + ".");
111             node = node.getParent();
112         }
113 
114         return path.toString();
115     }
116 
117     /**
118      * Returns a subset of nodes with "joint" semantics that are to be prefetched in the
119      * same query as the current node. Result excludes this node, regardless of its
120      * semantics.
121      */
122     public Collection   adjacentJointNodes() {
123         Collection   c = new ArrayList  ();
124         traverse(new AdjacentJoinsOperation(c));
125         return c;
126     }
127 
128     /**
129      * Returns a collection of PrefetchTreeNodes in this tree with joint semantics.
130      */
131     public Collection   jointNodes() {
132         Collection   c = new ArrayList  ();
133         traverse(new CollectionBuilderOperation(c, false, true, false, false));
134         return c;
135     }
136 
137     /**
138      * Returns a collection of PrefetchTreeNodes with disjoint semantics.
139      */
140     public Collection   disjointNodes() {
141         Collection   c = new ArrayList  ();
142         traverse(new CollectionBuilderOperation(c, true, false, false, false));
143         return c;
144     }
145 
146     /**
147      * Returns a collection of PrefetchTreeNodes that are not phantoms.
148      */
149     public Collection   nonPhantomNodes() {
150         Collection   c = new ArrayList  ();
151         traverse(new CollectionBuilderOperation(c, true, true, true, false));
152         return c;
153     }
154 
155     /**
156      * Traverses the tree depth-first, invoking callback methods of the processor when
157      * passing through the nodes.
158      */
159     public void traverse(PrefetchProcessor processor) {
160 
161         boolean result = false;
162 
163         if (isPhantom()) {
164             result = processor.startPhantomPrefetch(this);
165         }
166         else if (isDisjointPrefetch()) {
167             result = processor.startDisjointPrefetch(this);
168         }
169         else if (isJointPrefetch()) {
170             result = processor.startJointPrefetch(this);
171         }
172         else {
173             result = processor.startUnknownPrefetch(this);
174         }
175 
176         // process children unless processing is blocked...
177         if (result && children != null) {
178             Iterator   it = children.iterator();
179             while (it.hasNext()) {
180                 ((PrefetchTreeNode) it.next()).traverse(processor);
181             }
182         }
183 
184         // call finish regardless of whether children were processed
185         processor.finishPrefetch(this);
186     }
187 
188     /**
189      * Looks up an existing node in the tree desribed by the dot-separated path. Will
190      * return null if no matching child exists.
191      */
192     public PrefetchTreeNode getNode(String   path) {
193         if (Util.isEmptyString(path)) {
194             throw new IllegalArgumentException  ("Empty path: " + path);
195         }
196 
197         PrefetchTreeNode node = this;
198         StringTokenizer   toks = new StringTokenizer  (path, Entity.PATH_SEPARATOR);
199         while (toks.hasMoreTokens() && node != null) {
200             String   segment = toks.nextToken();
201             node = node.getChild(segment);
202         }
203 
204         return node;
205     }
206 
207     /**
208      * Adds a "path" with specified semantics to this prefetch node. All yet non-existent
209      * nodes in the created path will be marked as phantom.
210      * 
211      * @return the last segment in the created path.
212      */
213     public PrefetchTreeNode addPath(String   path) {
214         if (Util.isEmptyString(path)) {
215             throw new IllegalArgumentException  ("Empty path: " + path);
216         }
217 
218         PrefetchTreeNode node = this;
219         StringTokenizer   toks = new StringTokenizer  (path, Entity.PATH_SEPARATOR);
220         while (toks.hasMoreTokens()) {
221             String   segment = toks.nextToken();
222 
223             PrefetchTreeNode child = node.getChild(segment);
224             if (child == null) {
225                 child = new PrefetchTreeNode(node, segment);
226                 node.addChild(child);
227             }
228 
229             node = child;
230         }
231 
232         return node;
233     }
234 
235     /**
236      * Removes or makes phantom a node defined by this path. If the node for this path
237      * doesn't have any children, it is removed, otherwise it is made phantom.
238      */
239     public void removePath(String   path) {
240 
241         PrefetchTreeNode node = getNode(path);
242         while (node != null) {
243 
244             if (node.children != null) {
245                 node.setPhantom(true);
246                 break;
247             }
248 
249             String   segment = node.getName();
250 
251             node = node.getParent();
252 
253             if (node != null) {
254                 node.removeChild(segment);
255             }
256         }
257     }
258 
259     public void addChild(PrefetchTreeNode child) {
260 
261         if (Util.isEmptyString(child.getName())) {
262             throw new IllegalArgumentException  ("Child has no segmentPath: " + child);
263         }
264 
265         if (child.getParent() != this) {
266             child.getParent().removeChild(child.getName());
267             child.parent = this;
268         }
269 
270         if (children == null) {
271             children = new ArrayList  (4);
272         }
273 
274         children.add(child);
275     }
276 
277     public void removeChild(PrefetchTreeNode child) {
278         if (children != null && child != null) {
279             children.remove(child);
280             child.parent = null;
281         }
282     }
283 
284     protected void removeChild(String   segment) {
285         if (children != null) {
286             PrefetchTreeNode child = getChild(segment);
287             if (child != null) {
288                 children.remove(child);
289                 child.parent = null;
290             }
291         }
292     }
293 
294     protected PrefetchTreeNode getChild(String   segment) {
295         if (children != null) {
296             Iterator   it = children.iterator();
297             while (it.hasNext()) {
298                 PrefetchTreeNode next = (PrefetchTreeNode) it.next();
299                 if (segment.equals(next.getName())) {
300                     return next;
301                 }
302             }
303         }
304 
305         return null;
306     }
307 
308     public PrefetchTreeNode getParent() {
309         return parent;
310     }
311 
312     /**
313      * Returns an unmodifiable collection of children.
314      */
315     public Collection   getChildren() {
316         return children == null ? Collections.EMPTY_SET : Collections
317                 .unmodifiableCollection(children);
318     }
319 
320     public boolean hasChildren() {
321         return children != null && !children.isEmpty();
322     }
323 
324     public String   getName() {
325         return name;
326     }
327 
328     public boolean isPhantom() {
329         return phantom;
330     }
331 
332     public void setPhantom(boolean phantom) {
333         this.phantom = phantom;
334     }
335 
336     public int getSemantics() {
337         return semantics;
338     }
339 
340     public void setSemantics(int semantics) {
341         this.semantics = semantics;
342     }
343 
344     public boolean isJointPrefetch() {
345         return semantics == JOINT_PREFETCH_SEMANTICS;
346     }
347 
348     public boolean isDisjointPrefetch() {
349         return semantics == DISJOINT_PREFETCH_SEMANTICS;
350     }
351 
352     // **** custom serialization that supports serializing subtrees...
353 
354     // implementing 'readResolve' instead of 'readObject' so that this would work with
355     // hessian
356     private Object   readResolve() throws ObjectStreamException   {
357 
358         if (hasChildren()) {
359             Iterator   it = children.iterator();
360             while (it.hasNext()) {
361                 PrefetchTreeNode child = (PrefetchTreeNode) it.next();
362                 child.parent = this;
363             }
364         }
365 
366         return this;
367     }
368 
369     // **** common tree operations
370 
371     // An operation that encodes prefetch tree as XML.
372     class XMLEncoderOperation implements PrefetchProcessor {
373 
374         XMLEncoder encoder;
375 
376         XMLEncoderOperation(XMLEncoder encoder) {
377             this.encoder = encoder;
378         }
379 
380         public boolean startPhantomPrefetch(PrefetchTreeNode node) {
381             // don't encode phantoms
382             return true;
383         }
384 
385         public boolean startDisjointPrefetch(PrefetchTreeNode node) {
386             encoder.print("<prefetch type=\"disjoint\">");
387             encoder.print(node.getPath());
388             encoder.println("</prefetch>");
389             return true;
390         }
391 
392         public boolean startJointPrefetch(PrefetchTreeNode node) {
393             encoder.print("<prefetch type=\"joint\">");
394             encoder.print(node.getPath());
395             encoder.println("</prefetch>");
396             return true;
397         }
398 
399         public boolean startUnknownPrefetch(PrefetchTreeNode node) {
400             encoder.print("<prefetch>");
401             encoder.print(node.getPath());
402             encoder.println("</prefetch>");
403 
404             return true;
405         }
406 
407         public void finishPrefetch(PrefetchTreeNode node) {
408             // noop
409         }
410     }
411 
412     // An operation that collects all nodes in a single collection.
413     class CollectionBuilderOperation implements PrefetchProcessor {
414 
415         Collection   nodes;
416         boolean includePhantom;
417         boolean includeDisjoint;
418         boolean includeJoint;
419         boolean includeUnknown;
420 
421         CollectionBuilderOperation(Collection   nodes, boolean includeDisjoint,
422                 boolean includeJoint, boolean includeUnknown, boolean includePhantom) {
423             this.nodes = nodes;
424 
425             this.includeDisjoint = includeDisjoint;
426             this.includeJoint = includeJoint;
427             this.includeUnknown = includeUnknown;
428             this.includePhantom = includePhantom;
429         }
430 
431         public boolean startPhantomPrefetch(PrefetchTreeNode node) {
432             if (includePhantom) {
433                 nodes.add(node);
434             }
435 
436             return true;
437         }
438 
439         public boolean startDisjointPrefetch(PrefetchTreeNode node) {
440             if (includeDisjoint) {
441                 nodes.add(node);
442             }
443             return true;
444         }
445 
446         public boolean startJointPrefetch(PrefetchTreeNode node) {
447             if (includeJoint) {
448                 nodes.add(node);
449             }
450             return true;
451         }
452 
453         public boolean startUnknownPrefetch(PrefetchTreeNode node) {
454             if (includeUnknown) {
455                 nodes.add(node);
456             }
457             return true;
458         }
459 
460         public void finishPrefetch(PrefetchTreeNode node) {
461         }
462     }
463 
464     class AdjacentJoinsOperation implements PrefetchProcessor {
465 
466         Collection   nodes;
467 
468         AdjacentJoinsOperation(Collection   nodes) {
469             this.nodes = nodes;
470         }
471 
472         public boolean startPhantomPrefetch(PrefetchTreeNode node) {
473             return true;
474         }
475 
476         public boolean startDisjointPrefetch(PrefetchTreeNode node) {
477             return node == PrefetchTreeNode.this;
478         }
479 
480         public boolean startJointPrefetch(PrefetchTreeNode node) {
481             if (node != PrefetchTreeNode.this) {
482                 nodes.add(node);
483             }
484             return true;
485         }
486 
487         public boolean startUnknownPrefetch(PrefetchTreeNode node) {
488             return node == PrefetchTreeNode.this;
489         }
490 
491         public void finishPrefetch(PrefetchTreeNode node) {
492         }
493     }
494 }
495
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags