XTreeNode


1   /*
2    * This file belongs to the XQuark distribution.
3    * Copyright (C) 2003 Universite de Versailles Saint-Quentin.
4    * 
5    * This program is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This program is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this program; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307.
18   * You can also get it at http://www.gnu.org/licenses/lgpl.html
19   * 
20   * For more information on this software, see http://www.xquark.org.
21   */
22  
23  package org.xquark.xpath;
24  
25  import java.util.*;
26  
27  import org.xml.sax.ContentHandler  ;
28  import org.xml.sax.SAXException  ;
29  
30  /**
31   * Abstract XTree node.
32   *
33   */
34  public abstract class XTreeNode implements Cloneable   {
35      private static final String   RCSRevision = "$Revision: 1.2 $";
36      private static final String   RCSName = "$Name:  $";
37      /** */
38      protected XTree tree;
39  
40      protected XNode XModelNode;
41      // not designed by heritage, because XNode overrides
42      // equals (to be able to be used as a key in the local children map)
43  
44      protected XTreeNode parent;
45  
46      private HashMap children;
47  
48      protected PathExpr location = null;
49  
50      /**
51       * Constructor for element and attributes nodes.
52       * Performs registration of the node to its parent node, sets the owner
53       * XTree but does not perform registration of the node to the tree.
54       * This constructor should be called by implementors.
55       * @param tree the owner tree
56       * @param parent the parent node
57       * @param namespace the namespace URI of the new node
58       * @param localName the local name of the new node
59       * @param the type of the new node
60       */
61      protected XTreeNode(XTree tree, XTreeNode parent, String   namespace, String   localName, byte type) {
62          XModelNode = new XNode(namespace, localName, type);
63          set(tree, parent);
64      }
65  
66      /**
67       * Accessor to the parent node.
68       * @return the parent node (normally set at construction time except for
69       * root).
70       */
71      public XTreeNode getParent() {
72          return parent;
73      }
74  
75      /**
76       * Accessor to the owner tree.
77       * @return the owner tree.
78       */
79      public XTree getTree() {
80          return tree;
81      }
82  
83      /**
84       * Accessor to node's children.
85       * @return a collection of XTreeNode objects. null if the node is a leaf.
86       */
87      public Collection getChildren() {
88          if (children == null)
89              return null;
90          return children.values();
91      }
92  
93      /**
94       * Returns the canonical "expanded" name of this step. The returned string
95       * matches the following formatting rules:
96       * <code>{namespace}localName</code> if the namespace is not null and
97       * <code>localName</code> if the namespace is null.
98       * @return the expanded name of the node.
99       */
100     public final String   getExpandedName() {
101         return XModelNode.getExpandedName();
102     }
103 
104     /**
105      * Accessor to the local name of the node.
106      * @return the local name of the node.
107      */
108     public final String   getLocalName() {
109         return XModelNode.getLocalName();
110     }
111 
112     /**
113      * Accessor to the namespace uri of the node.
114      * @return the namespace uri of the node or null if node has no namespace.
115      */
116     public String   getNamespace() {
117         return XModelNode.getNamespace();
118     }
119 
120     /**
121      * Accessor to the XPath type of the node.
122      * @return a value defined in {@link Type}.
123      */
124     public byte getType() {
125         return XModelNode.getType();
126     }
127 
128     /**
129      * Returns an object used as a key for the node in its parent children map.
130      * @return the data model node of the current tree node.
131      */
132     public XNode getHashKey() {
133         return XModelNode;
134     }
135 
136     /**
137      * Whether the node is a leaf, i.e. has no child node.
138      * @return true if the node has no child.
139      */
140     public boolean isLeaf() {
141         return (children == null);
142     }
143 
144     /**
145      * Get the depth of the node in the metadata tree.
146      * @return an int value where the tree root has 0 value.
147      */
148     public int getDepth() {
149         if (location == null)
150             return 0;
151         else
152             return getLocation().getSteps().size();
153     }
154 
155     /**
156      * Add a node to the children set. No order is garanteed within the
157      * children.
158      * @param child the node that will become a child node of this node.
159      */
160     public final void addChild(XTreeNode child) {
161         if (children == null) // to avoid to make a base class for leaf nodes
162             children = new HashMap();
163         children.put(child.getHashKey(), child);
164         child.setParent(this);
165     }
166 
167     /**
168      * Merges a given subtree with the current subtree which root is the
169      * current node.
170      * @param node the root of the subtree to merge to the current subtree.
171      */
172     public final void merge(XTreeNode node) {
173         if (node.children != null) {
174             Iterator it = node.children.keySet().iterator();
175             while (it.hasNext()) {
176                 XNode key = ((XTreeNode) it.next()).getHashKey();
177                 XTreeNode child = getChild(key);
178                 if (child == null)
179                     this.addChild(node.getChild(key));
180                 else
181                     child.merge(node.getChild(key));
182             }
183         }
184     }
185 
186     /**
187      * Remove a given child node.
188      * @param pattern the "signature" of the children to remove.
189      */
190     public final XTreeNode removeChild(XNode pattern) {
191         if (children != null)
192             return (XTreeNode) children.remove(getChild(pattern));
193         return null;
194     }
195 
196     /**
197      * Detach the node from its tree.
198      */
199     public final void remove() {
200         if (parent != null)
201             parent.removeChild(XModelNode);
202     }
203 
204     /**
205      * retrieves a particular child.
206      * @param pattern the "signature" of the children to retrieve.
207      * @return the searched node or null if not found.
208      */
209     public final XTreeNode getChild(XNode pattern) {
210         if (children == null)
211             return null;
212         return (XTreeNode) children.get(pattern);
213     }
214 
215     /**
216      * Returns a <code>LocationExpression</code> corresponding to the
217      * given <code>Tree</code>.
218      * @return null if the node has no parent (ROOT or unregistered, i.e.
219      * not attached to the XTree, node)
220      */
221     public final PathExpr getLocation() {
222         if (location == null) {
223             if (getParent() == null) // the root case or an unregistered node
224                 return null;
225             location = new PathExprImpl();
226         } else // cache
227             return location;
228 
229         // construction
230         for (XTreeNode node = this; node.getType() != NodeKind.NONE; node = (XTreeNode) node.getParent()) {
231             switch (node.getType()) {
232                 case NodeKind.NAMESPACE :
233                     location.getSteps().add(0, new StepExprImpl(Axis.NAMESPACE, node.getHashKey()));
234                     break;
235                 case NodeKind.ATTRIBUTE :
236                     location.getSteps().add(0, new StepExprImpl(Axis.ATTRIBUTE, node.getHashKey()));
237                     break;
238                 default : // CHILD
239                     location.getSteps().add(0, new StepExprImpl(node.getHashKey()));
240             }
241         }
242         return location;
243     }
244 
245     /**
246      * Performs a navigation specified by the step expression.
247      * @param step the step that defines the elementary navigation
248      * @return the set of qualified nodes
249      */
250     public final Collection navigate(StepExpr step) {
251         Collection result = null;
252 
253         byte axis = step.getAxis();
254 
255         switch (axis) {
256             case Axis.SELF :
257                 result = new ArrayList(1);
258                 if (step.match(XModelNode))
259                     result.add(this);
260                 break;
261 
262             case Axis.NONE :
263             case Axis.CHILD :
264             case Axis.ATTRIBUTE :
265             case Axis.NAMESPACE :
266                 return getChildren(step);
267 
268             case Axis.PARENT :
269                 result = new ArrayList(1);
270                 result.add(getParent());
271                 break;
272 
273             case Axis.ANCESTOR_OR_SELF :
274                 result = getAncestors(step);
275                 if (step.match(XModelNode))
276                     result.add(this);
277                 break;
278 
279             case Axis.ANCESTOR :
280                 return getAncestors(step);
281 
282             case Axis.DESCENDANT :
283                 return getDescendants(step);
284 
285             case Axis.DESCENDANT_OR_SELF :
286                 result = getDescendants(step);
287                 if (step.match(XModelNode))
288                     result.add(this);
289                 break;
290 
291             case Axis.PRECEDING :
292                 return getPreceding(step);
293 
294             case Axis.PRECEDING_SIBLING :
295                 return getPrecedingSibling(step);
296 
297             case Axis.FOLLOWING :
298                 return getFollowing(step);
299 
300             case Axis.FOLLOWING_SIBLING :
301                 return getFollowingSibling(step);
302 
303 //          default :
304 //              System.out.println("Attention � la marche: " + axis);
305         }
306 
307         return result;
308     }
309 
310     /**
311      * Compute the LocationExpressions matching given regular location
312      * expression.
313      * @param location a location expression
314      * @return a collection containing XTreeNode objects matching the regular
315      * expression.
316      */
317     public final Collection prune(ArrayList location) {
318         /*
319         Set result = new HashSet();
320          
321         if(location.size() == 0)
322         {
323         //System.out.println("adding self: "+declaration.getName());
324         //result.add(this);
325                 Set r = new HashSet();
326                 r.add (this) ;
327                 result.add (r) ;
328         return result;
329         }
330          
331         Collection set = navigate((StepExpr)location.get(0));
332          
333         //System.out.println(getDeclaration().getName()+" navigate "+location.toStringBuffer(0));
334         //System.out.println(set);
335          
336         LocationExpression l = (LocationExpression) location.clone();
337          
338         if(l.size() > 0)
339         l.remove(0);
340         else
341         {
342         if(set != null)
343         result.addAll(set);
344         return result;
345         }
346          
347         Object[] nodes = set.toArray();
348         for(int i=0; i < nodes.length; i++)
349         {
350         XTreeNode node = (XTreeNode)nodes[i];
351         //System.out.println(node.getDeclaration().getName()+" -> "+l.toStringBuffer(0));
352         result.addAll(node.prune(l));
353         //result.add(node.prune(l));
354         }
355         return result;
356          */
357 
358         //org.xquark.xml.misc.Printing.print(location);
359         //System.out.println(getNamespace()+":"+getLocalName()+" => "+location.toString(0));
360 
361         /*
362         LocationExpression x = getLocation();
363         String id = null;
364         if(x!=null){
365         id = x.toString(0);
366         }
367         else{
368         id = "ROOT";
369         }
370         System.err.println(id+"  SEEK "+location.toString(0));
371          */
372 
373         Set result = new HashSet();
374 
375         if (location.size() == 0) {
376             if (this.getType() != NodeKind.NONE)
377                 result.add(this);
378             //System.err.println(" RESULT "+result);
379             return result;
380         }
381 
382         Collection set = navigate((StepExpr) location.get(0));
383 
384         //System.out.println(getNamespace()+":"+getLocalName()+" navigate "+location.toString(0));
385         //System.out.println("SET: " +set);
386 
387         ArrayList l = (ArrayList) location.clone();
388 
389         if (l.size() > 0)
390             l.remove(0);
391         else {
392             if (set != null)
393                 result.addAll(set);
394             //System.out.println("RESULT2: "+result);
395             return result;
396         }
397 
398         Object  [] nodes = set.toArray();
399         for (int i = 0; i < nodes.length; i++) {
400             XTreeNode node = (XTreeNode) nodes[i];
401             //System.out.println(node.getNamespace()+":"+node.getLocalName()+" -> "+l.toString(0));
402             Collection tmp = node.prune(l);
403             result.addAll(tmp);
404         }
405         //System.err.println("RESULT3 "+result);
406         return result;
407     }
408 
409     /**
410      * Compute the LocationExpressions matching given regular location
411      * expression building a collection of collections in order to
412      * regroup same level (for using in PathResolver and next for typing))
413      * @param location a location expression
414      * @return a collection collection of collections containing XTreeNode
415      * objects matching the regular expression. First collection are results
416      * for the level of the current node.
417      */
418     public final Collection pruneGroup(ArrayList location) {
419         Set result = new HashSet();
420         Set group = new HashSet();
421 
422         if (location.size() == 0) {
423             //System.out.println("adding self: "+declaration.getName());
424             /*
425             group.add (this) ;
426             result.add (group);
427              */
428             result.add(this); // SR 4/11/02 result is a Collection of Collections : why adding the current node ?
429             //        System.out.println("THIS " + this);
430             return result;
431         }
432 
433         Collection set = navigate((StepExpr) location.get(0));
434 
435         //System.out.println(getDeclaration().getName()+" navigate "+location.toStringBuffer(0));
436         //       System.out.println("SET" + set);
437 
438         ArrayList l = (ArrayList) location.clone();
439 
440         if (l.size() > 0)
441             l.remove(0);
442         else {
443             if (set != null) {
444                 group.add(set);
445                 result.add(group);
446             }
447             return result;
448         }
449 
450         Object  [] nodes = set.toArray();
451         for (int i = 0; i < nodes.length; i++) {
452             XTreeNode node = (XTreeNode) nodes[i];
453             //System.out.println(node.getDeclaration().getName()+" -> "+l.toStringBuffer(0));
454             if (node != null);
455             {
456                 Collection c = node.pruneGroup(l);
457                 if ((c != null) && (c.size() > 0))
458                     result.add(node.pruneGroup(l));
459             }
460         }
461         return result;
462     }
463 
464     /**
465      * Return a string representation of this node an its descendants.
466      *
467      * @param indent the size of indentation.
468      * @return the string representation of the current subtree.
469      */
470     private static final String   LS = System.getProperty("line.separator");
471     public final String   toString(int indent) {
472         StringBuffer   sb = new StringBuffer  ();
473         sb.append(LS);
474         for (int i=0;i<indent;i++) sb.append(' ');
475         sb.append(this.getNamespace());
476         sb.append(":");
477         sb.append(this.getLocalName());
478         sb.append("   ");
479         sb.append(toString());
480 
481         if (children != null) {
482             Iterator it = getChildren().iterator();
483 
484             while (it.hasNext()) {
485                 XTreeNode child = (XTreeNode) it.next();
486                 sb.append(child.toString(indent + 1));
487             }
488         }
489         return sb.toString();
490     }
491 
492     /**
493      * Perform an in depth copy of the subtree which the current node is the
494      * root
495      * @return the new XTreeNode.
496      */
497     public Object   clone() {
498         XTreeNode node = null;
499         try {
500             node = (XTreeNode) super.clone();
501             node.XModelNode = (XNode) XModelNode.clone();
502             if (children != null) {
503                 node.children = new HashMap();
504                 Iterator it = children.values().iterator();
505                 while (it.hasNext()) {
506                     node.addChild((XTreeNode) ((XTreeNode) it.next()).clone());
507                 }
508             }
509         } catch (CloneNotSupportedException   e) {}
510         return node;
511     }
512 
513     /**
514      * Create an homothetic copy of the subtree which the current node is the
515      * root using a given tree builder.
516      * @param root the root of the new subtree.
517      * @param factory the tree builder used to produce the new subtree.
518      * @return the root of the new subtree.
519      */
520     public XTreeNode duplicate(XTreeNode root, XTreeBuilder factory) {
521         if (children != null) {
522             Iterator it = children.values().iterator();
523             XTreeNode child;
524             while (it.hasNext()) {
525                 child = (XTreeNode) it.next();
526                 XTreeNode duplicate = factory.createNamedNode(root, child.getNamespace(), child.getLocalName(), child.getType()).customizeDuplicate(child);
527                 child.duplicate(duplicate, factory);
528                 // recursivity must be performed
529                 // after customization because children may need parent info
530             }
531         }
532         return root;
533     }
534 
535     /**
536      * Add customization to the nodes created with {@link #duplicate(XTreeNode, XTreeBuilder)}
537      * @param original the node which this node is a copy
538      * @return this node customized
539      */
540     protected XTreeNode customizeDuplicate(XTreeNode original) {
541         // nop by default
542         return this;
543     }
544 
545     /**
546      * Method call by {@link XTreeReader} to generate SAX events describing
547      * the node contents.
548      * This method is a base implementation that sends the result of toString()
549      * in a characters() SAX event.
550      * @param handler the content handler that will receive SAX events.
551      * @throws SAXException handler exception
552      */
553     protected void toXML(ContentHandler   handler) throws SAXException   {
554         String   display = toString();
555         handler.characters(display.toCharArray(), 0, display.length());
556     }
557 
558     /**
559      * Returns the descendant accessible from this node via the given
560      * LocationExpression.
561      *
562      * This method allows only fully qualified access paths, i.e. in the
563      * LocationExpression passed in the argument, the steps should
564      * always have CHILD, ATTRIBUTE, SELF OR PARENT as axis and there should not
565      * be any wildcards in the namespaces and localnames. In another word
566      * each step should qualify only one node.
567      * @param e relative location expression from this node to the node to
568      * retrieve.
569      * @return the node specified by the location expression
570      */
571     public XTreeNode getDescendant(PathExpr e) {
572         if (e == null) {
573             return this;
574         }
575 
576         XTreeNode result = this;
577 
578         for (int i = 0; i < e.getSteps().size(); i++) {
579             StepExpr step = e.getStep(i);
580             byte axis = step.getAxis();
581             switch (axis) {
582                 case Axis.ATTRIBUTE :
583                 case Axis.CHILD :
584                     result = result.getChild(step.getXNode());
585                     break;
586 
587                 case Axis.SELF :
588                     break;
589 
590                 case Axis.PARENT :
591                     result = result.getParent();
592                     break;
593 
594                 default :
595                     throw new RuntimeException  ("Navigation axis [" + axis + "] not handled by this method.");
596             }
597 
598             if (result == null) {
599                 break;
600             }
601         }
602         return result;
603     }
604 
605     ///////////////////////////////////////////////////////////////////////////
606     //                          PRIVATE UTILITIES
607     ///////////////////////////////////////////////////////////////////////////
608     private void set(XTree tree, XTreeNode parent) {
609         this.tree = tree;
610         if (parent != null)
611             parent.addChild(this);
612     }
613 
614     private void setParent(XTreeNode parent) {
615         this.parent = parent;
616         location = null;
617     }
618 
619     /* Override XNode and carry out problems when navigating : compare LocationExpressions instead
620        Carried out an infinite loop when calling equals() for LocationExpression
621         public boolean equals(Object o)
622         {
623             return (o instanceof XTreeNode) && getLocation().equals(((XTreeNode)o).getLocation());
624         }
625      */
626     //
627     //              STEP NAVIGATION
628     //
629 
630     /**
631      * Returns the list of children matching the given step expression.
632      */
633     private Collection getChildren(StepExpr step) {
634         ArrayList set = new ArrayList();
635         if (children == null)
636             return set;
637         Iterator it = children.values().iterator();
638         while (it.hasNext()) {
639             XTreeNode child = (XTreeNode) it.next();
640             if (step.match(child.getHashKey()))
641                 set.add(child);
642         }
643         return set;
644     }
645 
646     /**
647      * Returns the list of ancestors matching the given step expression.
648      */
649     private Collection getAncestors(StepExpr step) {
650         ArrayList ancestors = new ArrayList();
651 
652         XTreeNode ancestor = (XTreeNode) getParent();
653         while (ancestor != null) {
654             if (ancestor.getHashKey().match(step))
655                 ancestors.add(ancestor);
656             ancestor = (XTreeNode) ancestor.getParent();
657         }
658         return ancestors;
659     }
660 
661     /**
662      * Returns the list of descendants matching the given step expression.
663      */
664     private Collection getDescendants(StepExpr step) {
665         ArrayList descendants = new ArrayList();
666         if (children == null)
667             return descendants;
668 
669         Iterator it = children.values().iterator();
670         while (it.hasNext()) {
671             XTreeNode child = (XTreeNode) it.next();
672 
673             if (child.XModelNode.type != NodeKind.ELEMENT) {
674                 continue;
675             }
676 
677             if (step.match(child.getHashKey())) {
678                 descendants.add(child);
679             }
680             descendants.addAll(child.getDescendants(step));
681         }
682         //System.out.println("DESC="+descendants);
683         return descendants;
684     }
685 
686     /**
687      * In a dynamic tree, PRECEDING, PRECEDING_SIBLING, FOLLOWING,
688      * and FOLLOWING_SIBLING are considered not well defined, since all
689      * nodes can be considered being optional.
690      */
691     private Collection getPreceding(StepExpr step) {
692         throw new UnsupportedOperationException  ();
693     }
694 
695     private Collection getPrecedingSibling(StepExpr step) {
696         throw new UnsupportedOperationException  ();
697     }
698 
699     private Collection getFollowing(StepExpr step) {
700         throw new UnsupportedOperationException  ();
701     }
702 
703     private Collection getFollowingSibling(StepExpr step) {
704         throw new UnsupportedOperationException  ();
705     }
706 
707 }
708
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags