View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /*
6    * Copyright 1999-2004 The Apache Software Foundation.
7    *
8    * Licensed under the Apache License, Version 2.0 (the "License");
9    * you may not use this file except in compliance with the License.
10   * You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  /*
21   * $Id: DTMDefaultBaseTraversers.java,v 1.2.4.1 2005/09/15 08:15:00 suresh_emailid Exp $
22   */
23  package com.sun.org.apache.xml.internal.dtm.ref;
24  
25  import com.sun.org.apache.xml.internal.dtm.*;
26  
27  import javax.xml.transform.Source;
28  
29  import com.sun.org.apache.xml.internal.utils.XMLStringFactory;
30  
31  import com.sun.org.apache.xml.internal.res.XMLErrorResources;
32  import com.sun.org.apache.xml.internal.res.XMLMessages;
33  import com.sun.org.apache.xalan.internal.xsltc.dom.NodeCounter;
34  
35  /**
36   * This class implements the traversers for DTMDefaultBase.
37   *
38   * PLEASE NOTE that the public interface for all traversers should be
39   * in terms of DTM Node Handles... but they may use the internal node
40   * identity indices within their logic, for efficiency's sake. Be very
41   * careful to avoid confusing these when maintaining this code.
42   * */
43  public abstract class DTMDefaultBaseTraversers extends DTMDefaultBase
44  {
45  
46    /**
47     * Construct a DTMDefaultBaseTraversers object from a DOM node.
48     *
49     * @param mgr The DTMManager who owns this DTM.
50     * @param source The object that is used to specify the construction source.
51     * @param dtmIdentity The DTM identity ID for this DTM.
52     * @param whiteSpaceFilter The white space filter for this DTM, which may
53     *                         be null.
54     * @param xstringfactory The factory to use for creating XMLStrings.
55     * @param doIndexing true if the caller considers it worth it to use
56     *                   indexing schemes.
57     */
58    public DTMDefaultBaseTraversers(DTMManager mgr, Source source,
59                                    int dtmIdentity,
60                                    DTMWSFilter whiteSpaceFilter,
61                                    XMLStringFactory xstringfactory,
62                                    boolean doIndexing)
63    {
64      super(mgr, source, dtmIdentity, whiteSpaceFilter, xstringfactory,
65            doIndexing);
66    }
67  
68    /**
69     * Construct a DTMDefaultBaseTraversers object from a DOM node.
70     *
71     * @param mgr The DTMManager who owns this DTM.
72     * @param source The object that is used to specify the construction source.
73     * @param dtmIdentity The DTM identity ID for this DTM.
74     * @param whiteSpaceFilter The white space filter for this DTM, which may
75     *                         be null.
76     * @param xstringfactory The factory to use for creating XMLStrings.
77     * @param doIndexing true if the caller considers it worth it to use
78     *                   indexing schemes.
79     * @param blocksize The block size of the DTM.
80     * @param usePrevsib true if we want to build the previous sibling node array.
81     * @param newNameTable true if we want to use a new ExpandedNameTable for this DTM.
82     */
83    public DTMDefaultBaseTraversers(DTMManager mgr, Source source,
84                                    int dtmIdentity,
85                                    DTMWSFilter whiteSpaceFilter,
86                                    XMLStringFactory xstringfactory,
87                                    boolean doIndexing,
88                                    int blocksize,
89                                    boolean usePrevsib,
90                                    boolean newNameTable)
91    {
92      super(mgr, source, dtmIdentity, whiteSpaceFilter, xstringfactory,
93            doIndexing, blocksize, usePrevsib, newNameTable);
94    }
95  
96    /**
97     * This returns a stateless "traverser", that can navigate
98     * over an XPath axis, though perhaps not in document order.
99     *
100    * @param axis One of Axes.ANCESTORORSELF, etc.
101    *
102    * @return A DTMAxisTraverser, or null if the given axis isn't supported.
103    */
104   public DTMAxisTraverser getAxisTraverser(final int axis)
105   {
106 
107     DTMAxisTraverser traverser;
108 
109     if (null == m_traversers)  // Cache of stateless traversers for this DTM
110     {
111       m_traversers = new DTMAxisTraverser[Axis.getNamesLength()];
112       traverser = null;
113     }
114     else
115     {
116       traverser = m_traversers[axis];  // Share/reuse existing traverser
117 
118       if (traverser != null)
119         return traverser;
120     }
121 
122     switch (axis)  // Generate new traverser
123     {
124     case Axis.ANCESTOR :
125       traverser = new AncestorTraverser();
126       break;
127     case Axis.ANCESTORORSELF :
128       traverser = new AncestorOrSelfTraverser();
129       break;
130     case Axis.ATTRIBUTE :
131       traverser = new AttributeTraverser();
132       break;
133     case Axis.CHILD :
134       traverser = new ChildTraverser();
135       break;
136     case Axis.DESCENDANT :
137       traverser = new DescendantTraverser();
138       break;
139     case Axis.DESCENDANTORSELF :
140       traverser = new DescendantOrSelfTraverser();
141       break;
142     case Axis.FOLLOWING :
143       traverser = new FollowingTraverser();
144       break;
145     case Axis.FOLLOWINGSIBLING :
146       traverser = new FollowingSiblingTraverser();
147       break;
148     case Axis.NAMESPACE :
149       traverser = new NamespaceTraverser();
150       break;
151     case Axis.NAMESPACEDECLS :
152       traverser = new NamespaceDeclsTraverser();
153       break;
154     case Axis.PARENT :
155       traverser = new ParentTraverser();
156       break;
157     case Axis.PRECEDING :
158       traverser = new PrecedingTraverser();
159       break;
160     case Axis.PRECEDINGSIBLING :
161       traverser = new PrecedingSiblingTraverser();
162       break;
163     case Axis.SELF :
164       traverser = new SelfTraverser();
165       break;
166     case Axis.ALL :
167       traverser = new AllFromRootTraverser();
168       break;
169     case Axis.ALLFROMNODE :
170       traverser = new AllFromNodeTraverser();
171       break;
172     case Axis.PRECEDINGANDANCESTOR :
173       traverser = new PrecedingAndAncestorTraverser();
174       break;
175     case Axis.DESCENDANTSFROMROOT :
176       traverser = new DescendantFromRootTraverser();
177       break;
178     case Axis.DESCENDANTSORSELFFROMROOT :
179       traverser = new DescendantOrSelfFromRootTraverser();
180       break;
181     case Axis.ROOT :
182       traverser = new RootTraverser();
183       break;
184     case Axis.FILTEREDLIST :
185       return null; // Don't want to throw an exception for this one.
186     default :
187       throw new DTMException(XMLMessages.createXMLMessage(XMLErrorResources.ER_UNKNOWN_AXIS_TYPE, new Object[]{Integer.toString(axis)})); //"Unknown axis traversal type: "+axis);
188     }
189 
190     if (null == traverser)
191       throw new DTMException(XMLMessages.createXMLMessage(XMLErrorResources.ER_AXIS_TRAVERSER_NOT_SUPPORTED, new Object[]{Axis.getNames(axis)}));
192       // "Axis traverser not supported: "
193       //                       + Axis.names[axis]);
194 
195     m_traversers[axis] = traverser;
196 
197     return traverser;
198   }
199 
200   /**
201    * Implements traversal of the Ancestor access, in reverse document order.
202    */
203   private class AncestorTraverser extends DTMAxisTraverser
204   {
205 
206     /**
207      * Traverse to the next node after the current node.
208      *
209      * @param context The context node if this iteration.
210      * @param current The current node of the iteration.
211      *
212      * @return the next node in the iteration, or DTM.NULL.
213      */
214     public int next(int context, int current)
215     {
216                         return getParent(current);
217     }
218 
219     /**
220      * Traverse to the next node after the current node that is matched
221      * by the expanded type ID.
222      *
223      * @param context The context node of this iteration.
224      * @param current The current node of the iteration.
225      * @param expandedTypeID The expanded type ID that must match.
226      *
227      * @return the next node in the iteration, or DTM.NULL.
228      */
229     public int next(int context, int current, int expandedTypeID)
230     {
231                         // Process using identities
232       current = makeNodeIdentity(current);
233 
234       while (DTM.NULL != (current = m_parent.elementAt(current)))
235       {
236         if (m_exptype.elementAt(current) == expandedTypeID)
237           return makeNodeHandle(current);
238       }
239 
240       return NULL;
241     }
242   }
243 
244   /**
245    * Implements traversal of the Ancestor access, in reverse document order.
246    */
247   private class AncestorOrSelfTraverser extends AncestorTraverser
248   {
249 
250     /**
251      * By the nature of the stateless traversal, the context node can not be
252      * returned or the iteration will go into an infinate loop.  To see if
253      * the self node should be processed, use this function.
254      *
255      * @param context The context node of this traversal.
256      *
257      * @return the first node in the traversal.
258      */
259     public int first(int context)
260     {
261       return context;
262     }
263 
264     /**
265      * By the nature of the stateless traversal, the context node can not be
266      * returned or the iteration will go into an infinate loop.  To see if
267      * the self node should be processed, use this function.  If the context
268      * node does not match the expanded type ID, this function will return
269      * false.
270      *
271      * @param context The context node of this traversal.
272      * @param expandedTypeID The expanded type ID that must match.
273      *
274      * @return the first node in the traversal.
275      */
276     public int first(int context, int expandedTypeID)
277     {
278                         return (getExpandedTypeID(context) == expandedTypeID)
279              ? context : next(context, context, expandedTypeID);
280     }
281   }
282 
283   /**
284    * Implements traversal of the Attribute access
285    */
286   private class AttributeTraverser extends DTMAxisTraverser
287   {
288 
289     /**
290      * Traverse to the next node after the current node.
291      *
292      * @param context The context node of this iteration.
293      * @param current The current node of the iteration.
294      *
295      * @return the next node in the iteration, or DTM.NULL.
296      */
297     public int next(int context, int current)
298     {
299       return (context == current)
300              ? getFirstAttribute(context) : getNextAttribute(current);
301     }
302 
303     /**
304      * Traverse to the next node after the current node that is matched
305      * by the expanded type ID.
306      *
307      * @param context The context node of this iteration.
308      * @param current The current node of the iteration.
309      * @param expandedTypeID The expanded type ID that must match.
310      *
311      * @return the next node in the iteration, or DTM.NULL.
312      */
313     public int next(int context, int current, int expandedTypeID)
314     {
315 
316       current = (context == current)
317                 ? getFirstAttribute(context) : getNextAttribute(current);
318 
319       do
320       {
321         if (getExpandedTypeID(current) == expandedTypeID)
322           return current;
323       }
324       while (DTM.NULL != (current = getNextAttribute(current)));
325 
326       return NULL;
327     }
328   }
329 
330   /**
331    * Implements traversal of the Ancestor access, in reverse document order.
332    */
333   private class ChildTraverser extends DTMAxisTraverser
334   {
335 
336     /**
337      * Get the next indexed node that matches the expanded type ID.  Before
338      * calling this function, one should first call
339      * {@link #isIndexed(int) isIndexed} to make sure that the index can
340      * contain nodes that match the given expanded type ID.
341      *
342      * @param axisRoot The root identity of the axis.
343      * @param nextPotential The node found must match or occur after this node.
344      * @param expandedTypeID The expanded type ID for the request.
345      *
346      * @return The node ID or NULL if not found.
347      */
348     protected int getNextIndexed(int axisRoot, int nextPotential,
349                                  int expandedTypeID)
350     {
351 
352       int nsIndex = m_expandedNameTable.getNamespaceID(expandedTypeID);
353       int lnIndex = m_expandedNameTable.getLocalNameID(expandedTypeID);
354 
355       for (; ; )
356       {
357         int nextID = findElementFromIndex(nsIndex, lnIndex, nextPotential);
358 
359         if (NOTPROCESSED != nextID)
360         {
361           int parentID = m_parent.elementAt(nextID);
362 
363           // Is it a child?
364           if(parentID == axisRoot)
365             return nextID;
366 
367           // If the parent occured before the subtree root, then
368           // we know it is past the child axis.
369           if(parentID < axisRoot)
370               return NULL;
371 
372           // Otherwise, it could be a descendant below the subtree root
373           // children, or it could be after the subtree root.  So we have
374           // to climb up until the parent is less than the subtree root, in
375           // which case we return NULL, or until it is equal to the subtree
376           // root, in which case we continue to look.
377           do
378           {
379             parentID = m_parent.elementAt(parentID);
380             if(parentID < axisRoot)
381               return NULL;
382           }
383             while(parentID > axisRoot);
384 
385           // System.out.println("Found node via index: "+first);
386           nextPotential = nextID+1;
387           continue;
388         }
389 
390         nextNode();
391 
392         if(!(m_nextsib.elementAt(axisRoot) == NOTPROCESSED))
393           break;
394       }
395 
396       return DTM.NULL;
397     }
398 
399     /**
400      * By the nature of the stateless traversal, the context node can not be
401      * returned or the iteration will go into an infinate loop.  So to traverse
402      * an axis, the first function must be used to get the first node.
403      *
404      * <p>This method needs to be overloaded only by those axis that process
405      * the self node. <\p>
406      *
407      * @param context The context node of this traversal. This is the point
408      * that the traversal starts from.
409      * @return the first node in the traversal.
410      */
411     public int first(int context)
412     {
413       return getFirstChild(context);
414     }
415 
416     /**
417      * By the nature of the stateless traversal, the context node can not be
418      * returned or the iteration will go into an infinate loop.  So to traverse
419      * an axis, the first function must be used to get the first node.
420      *
421      * <p>This method needs to be overloaded only by those axis that process
422      * the self node. <\p>
423      *
424      * @param context The context node of this traversal. This is the point
425      * of origin for the traversal -- its "root node" or starting point.
426      * @param expandedTypeID The expanded type ID that must match.
427      *
428      * @return the first node in the traversal.
429      */
430     public int first(int context, int expandedTypeID)
431     {
432       if(true)
433       {
434         int identity = makeNodeIdentity(context);
435 
436         int firstMatch = getNextIndexed(identity, _firstch(identity),
437                                  expandedTypeID);
438 
439         return makeNodeHandle(firstMatch);
440       }
441       else
442       {
443                                 // %REVIEW% Dead code. Eliminate?
444         for (int current = _firstch(makeNodeIdentity(context));
445              DTM.NULL != current;
446              current = _nextsib(current))
447         {
448           if (m_exptype.elementAt(current) == expandedTypeID)
449               return makeNodeHandle(current);
450         }
451         return NULL;
452       }
453     }
454 
455     /**
456      * Traverse to the next node after the current node.
457      *
458      * @param context The context node of this iteration.
459      * @param current The current node of the iteration.
460      *
461      * @return the next node in the iteration, or DTM.NULL.
462      */
463     public int next(int context, int current)
464     {
465       return getNextSibling(current);
466     }
467 
468     /**
469      * Traverse to the next node after the current node that is matched
470      * by the expanded type ID.
471      *
472      * @param context The context node of this iteration.
473      * @param current The current node of the iteration.
474      * @param expandedTypeID The expanded type ID that must match.
475      *
476      * @return the next node in the iteration, or DTM.NULL.
477      */
478     public int next(int context, int current, int expandedTypeID)
479     {
480                         // Process in Identifier space
481       for (current = _nextsib(makeNodeIdentity(current));
482            DTM.NULL != current;
483            current = _nextsib(current))
484       {
485         if (m_exptype.elementAt(current) == expandedTypeID)
486             return makeNodeHandle(current);
487       }
488 
489       return NULL;
490     }
491   }
492 
493   /**
494    * Super class for derived classes that want a convenient way to access
495    * the indexing mechanism.
496    */
497   private abstract class IndexedDTMAxisTraverser extends DTMAxisTraverser
498   {
499 
500     /**
501      * Tell if the indexing is on and the given expanded type ID matches
502      * what is in the indexes.  Derived classes should call this before
503      * calling {@link #getNextIndexed(int, int, int) getNextIndexed} method.
504      *
505      * @param expandedTypeID The expanded type ID being requested.
506      *
507      * @return true if it is OK to call the
508      *         {@link #getNextIndexed(int, int, int) getNextIndexed} method.
509      */
510     protected final boolean isIndexed(int expandedTypeID)
511     {
512       return (m_indexing
513               && ExpandedNameTable.ELEMENT
514                  == m_expandedNameTable.getType(expandedTypeID));
515     }
516 
517     /**
518      * Tell if a node is outside the axis being traversed.  This method must be
519      * implemented by derived classes, and must be robust enough to handle any
520      * node that occurs after the axis root.
521      *
522      * @param axisRoot The root identity of the axis.
523      * @param identity The node in question.
524      *
525      * @return true if the given node falls outside the axis being traversed.
526      */
527     protected abstract boolean isAfterAxis(int axisRoot, int identity);
528 
529     /**
530      * Tell if the axis has been fully processed to tell if a the wait for
531      * an arriving node should terminate.  This method must be implemented
532      * be a derived class.
533      *
534      * @param axisRoot The root identity of the axis.
535      *
536      * @return true if the axis has been fully processed.
537      */
538     protected abstract boolean axisHasBeenProcessed(int axisRoot);
539 
540     /**
541      * Get the next indexed node that matches the expanded type ID.  Before
542      * calling this function, one should first call
543      * {@link #isIndexed(int) isIndexed} to make sure that the index can
544      * contain nodes that match the given expanded type ID.
545      *
546      * @param axisRoot The root identity of the axis.
547      * @param nextPotential The node found must match or occur after this node.
548      * @param expandedTypeID The expanded type ID for the request.
549      *
550      * @return The node ID or NULL if not found.
551      */
552     protected int getNextIndexed(int axisRoot, int nextPotential,
553                                  int expandedTypeID)
554     {
555 
556       int nsIndex = m_expandedNameTable.getNamespaceID(expandedTypeID);
557       int lnIndex = m_expandedNameTable.getLocalNameID(expandedTypeID);
558 
559       while(true)
560       {
561         int next = findElementFromIndex(nsIndex, lnIndex, nextPotential);
562 
563         if (NOTPROCESSED != next)
564         {
565           if (isAfterAxis(axisRoot, next))
566             return NULL;
567 
568           // System.out.println("Found node via index: "+first);
569           return next;
570         }
571         else if(axisHasBeenProcessed(axisRoot))
572           break;
573 
574         nextNode();
575       }
576 
577       return DTM.NULL;
578     }
579   }
580 
581   /**
582    * Implements traversal of the Ancestor access, in reverse document order.
583    */
584   private class DescendantTraverser extends IndexedDTMAxisTraverser
585   {
586     /**
587      * Get the first potential identity that can be returned.  This should
588      * be overridded by classes that need to return the self node.
589      *
590      * @param identity The node identity of the root context of the traversal.
591      *
592      * @return The first potential node that can be in the traversal.
593      */
594     protected int getFirstPotential(int identity)
595     {
596       return identity + 1;
597     }
598 
599     /**
600      * Tell if the axis has been fully processed to tell if a the wait for
601      * an arriving node should terminate.
602      *
603      * @param axisRoot The root identity of the axis.
604      *
605      * @return true if the axis has been fully processed.
606      */
607     protected boolean axisHasBeenProcessed(int axisRoot)
608     {
609       return !(m_nextsib.elementAt(axisRoot) == NOTPROCESSED);
610     }
611 
612     /**
613      * Get the subtree root identity from the handle that was passed in by
614      * the caller.  Derived classes may override this to change the root
615      * context of the traversal.
616      *
617      * @param handle handle to the root context.
618      * @return identity of the root of the subtree.
619      */
620     protected int getSubtreeRoot(int handle)
621     {
622       return makeNodeIdentity(handle);
623     }
624 
625     /**
626      * Tell if this node identity is a descendant.  Assumes that
627      * the node info for the element has already been obtained.
628      *
629      * %REVIEW% This is really parentFollowsRootInDocumentOrder ...
630      * which fails if the parent starts after the root ends.
631      * May be sufficient for this class's logic, but misleadingly named!
632      *
633      * @param subtreeRootIdentity The root context of the subtree in question.
634      * @param identity The index number of the node in question.
635      * @return true if the index is a descendant of _startNode.
636      */
637     protected boolean isDescendant(int subtreeRootIdentity, int identity)
638     {
639       return _parent(identity) >= subtreeRootIdentity;
640     }
641 
642     /**
643      * Tell if a node is outside the axis being traversed.  This method must be
644      * implemented by derived classes, and must be robust enough to handle any
645      * node that occurs after the axis root.
646      *
647      * @param axisRoot The root identity of the axis.
648      * @param identity The node in question.
649      *
650      * @return true if the given node falls outside the axis being traversed.
651      */
652     protected boolean isAfterAxis(int axisRoot, int identity)
653     {
654       // %REVIEW% Is there *any* cheaper way to do this?
655                         // Yes. In ID space, compare to axisRoot's successor
656                         // (next-sib or ancestor's-next-sib). Probably shallower search.
657       do
658       {
659         if(identity == axisRoot)
660           return false;
661         identity = m_parent.elementAt(identity);
662       }
663         while(identity >= axisRoot);
664 
665       return true;
666     }
667 
668     /**
669      * By the nature of the stateless traversal, the context node can not be
670      * returned or the iteration will go into an infinate loop.  So to traverse
671      * an axis, the first function must be used to get the first node.
672      *
673      * <p>This method needs to be overloaded only by those axis that process
674      * the self node. <\p>
675      *
676      * @param context The context node of this traversal. This is the point
677      * of origin for the traversal -- its "root node" or starting point.
678      * @param expandedTypeID The expanded type ID that must match.
679      *
680      * @return the first node in the traversal.
681      */
682     public int first(int context, int expandedTypeID)
683     {
684 
685       if (isIndexed(expandedTypeID))
686       {
687         int identity = getSubtreeRoot(context);
688         int firstPotential = getFirstPotential(identity);
689 
690         return makeNodeHandle(getNextIndexed(identity, firstPotential, expandedTypeID));
691       }
692 
693       return next(context, context, expandedTypeID);
694     }
695 
696     /**
697      * Traverse to the next node after the current node.
698      *
699      * @param context The context node of this iteration.
700      * @param current The current node of the iteration.
701      *
702      * @return the next node in the iteration, or DTM.NULL.
703      */
704     public int next(int context, int current)
705     {
706 
707       int subtreeRootIdent = getSubtreeRoot(context);
708 
709       for (current = makeNodeIdentity(current) + 1; ; current++)
710       {
711         int type = _type(current);  // may call nextNode()
712 
713         if (!isDescendant(subtreeRootIdent, current))
714           return NULL;
715 
716         if (ATTRIBUTE_NODE == type || NAMESPACE_NODE == type)
717           continue;
718 
719         return makeNodeHandle(current);  // make handle.
720       }
721     }
722 
723     /**
724      * Traverse to the next node after the current node that is matched
725      * by the expanded type ID.
726      *
727      * @param context The context node of this iteration.
728      * @param current The current node of the iteration.
729      * @param expandedTypeID The expanded type ID that must match.
730      *
731      * @return the next node in the iteration, or DTM.NULL.
732      */
733     public int next(int context, int current, int expandedTypeID)
734     {
735 
736       int subtreeRootIdent = getSubtreeRoot(context);
737 
738       current = makeNodeIdentity(current) + 1;
739 
740       if (isIndexed(expandedTypeID))
741       {
742         return makeNodeHandle(getNextIndexed(subtreeRootIdent, current, expandedTypeID));
743       }
744 
745       for (; ; current++)
746       {
747         int exptype = _exptype(current);  // may call nextNode()
748 
749         if (!isDescendant(subtreeRootIdent, current))
750           return NULL;
751 
752         if (exptype != expandedTypeID)
753           continue;
754 
755         return makeNodeHandle(current);  // make handle.
756       }
757     }
758   }
759 
760   /**
761    * Implements traversal of the Ancestor access, in reverse document order.
762    */
763   private class DescendantOrSelfTraverser extends DescendantTraverser
764   {
765 
766     /**
767      * Get the first potential identity that can be returned, which is the
768      * axis context, in this case.
769      *
770      * @param identity The node identity of the root context of the traversal.
771      *
772      * @return The axis context.
773      */
774     protected int getFirstPotential(int identity)
775     {
776       return identity;
777     }
778 
779     /**
780      * By the nature of the stateless traversal, the context node can not be
781      * returned or the iteration will go into an infinate loop.  To see if
782      * the self node should be processed, use this function.
783      *
784      * @param context The context node of this traversal.
785      *
786      * @return the first node in the traversal.
787      */
788     public int first(int context)
789     {
790       return context;
791     }
792   }
793 
794   /**
795    * Implements traversal of the entire subtree, including the root node.
796    */
797   private class AllFromNodeTraverser extends DescendantOrSelfTraverser
798   {
799 
800     /**
801      * Traverse to the next node after the current node.
802      *
803      * @param context The context node of this iteration.
804      * @param current The current node of the iteration.
805      *
806      * @return the next node in the iteration, or DTM.NULL.
807      */
808     public int next(int context, int current)
809     {
810 
811       int subtreeRootIdent = makeNodeIdentity(context);
812 
813       for (current = makeNodeIdentity(current) + 1; ; current++)
814       {
815         // Trickological code: _exptype() has the side-effect of
816         // running nextNode until the specified node has been loaded,
817         // and thus can be used to ensure that incremental construction of
818         // the DTM has gotten this far. Using it just for that side-effect
819         // is quite a kluge...
820         _exptype(current);  // make sure it's here.
821 
822         if (!isDescendant(subtreeRootIdent, current))
823           return NULL;
824 
825         return makeNodeHandle(current);  // make handle.
826       }
827     }
828   }
829 
830   /**
831    * Implements traversal of the following access, in document order.
832    */
833   private class FollowingTraverser extends DescendantTraverser
834   {
835 
836     /**
837      * Get the first of the following.
838      *
839      * @param context The context node of this traversal. This is the point
840      * that the traversal starts from.
841      * @return the first node in the traversal.
842      */
843     public int first(int context)
844     {
845                         // Compute in ID space
846                         context=makeNodeIdentity(context);
847 
848       int first;
849       int type = _type(context);
850 
851       if ((DTM.ATTRIBUTE_NODE == type) || (DTM.NAMESPACE_NODE == type))
852       {
853         context = _parent(context);
854         first = _firstch(context);
855 
856         if (NULL != first)
857           return makeNodeHandle(first);
858       }
859 
860       do
861       {
862         first = _nextsib(context);
863 
864         if (NULL == first)
865           context = _parent(context);
866       }
867       while (NULL == first && NULL != context);
868 
869       return makeNodeHandle(first);
870     }
871 
872     /**
873      * Get the first of the following.
874      *
875      * @param context The context node of this traversal. This is the point
876      * of origin for the traversal -- its "root node" or starting point.
877      * @param expandedTypeID The expanded type ID that must match.
878      *
879      * @return the first node in the traversal.
880      */
881     public int first(int context, int expandedTypeID)
882     {
883                         // %REVIEW% This looks like it might want shift into identity space
884                         // to avoid repeated conversion in the individual functions
885       int first;
886       int type = getNodeType(context);
887 
888       if ((DTM.ATTRIBUTE_NODE == type) || (DTM.NAMESPACE_NODE == type))
889       {
890         context = getParent(context);
891         first = getFirstChild(context);
892 
893         if (NULL != first)
894         {
895           if (getExpandedTypeID(first) == expandedTypeID)
896             return first;
897           else
898             return next(context, first, expandedTypeID);
899         }
900       }
901 
902       do
903       {
904         first = getNextSibling(context);
905 
906         if (NULL == first)
907           context = getParent(context);
908         else
909         {
910           if (getExpandedTypeID(first) == expandedTypeID)
911             return first;
912           else
913             return next(context, first, expandedTypeID);
914         }
915       }
916       while (NULL == first && NULL != context);
917 
918       return first;
919     }
920 
921     /**
922      * Traverse to the next node after the current node.
923      *
924      * @param context The context node of this iteration.
925      * @param current The current node of the iteration.
926      *
927      * @return the next node in the iteration, or DTM.NULL.
928      */
929     public int next(int context, int current)
930     {
931                         // Compute in identity space
932                         current=makeNodeIdentity(current);
933 
934       while (true)
935       {
936         current++; // Only works on IDs, not handles.
937 
938                                 // %REVIEW% Are we using handles or indexes?
939         int type = _type(current);  // may call nextNode()
940 
941         if (NULL == type)
942           return NULL;
943 
944         if (ATTRIBUTE_NODE == type || NAMESPACE_NODE == type)
945           continue;
946 
947         return makeNodeHandle(current);  // make handle.
948       }
949     }
950 
951     /**
952      * Traverse to the next node after the current node that is matched
953      * by the expanded type ID.
954      *
955      * @param context The context node of this iteration.
956      * @param current The current node of the iteration.
957      * @param expandedTypeID The expanded type ID that must match.
958      *
959      * @return the next node in the iteration, or DTM.NULL.
960      */
961     public int next(int context, int current, int expandedTypeID)
962     {
963                         // Compute in ID space
964                         current=makeNodeIdentity(current);
965 
966       while (true)
967       {
968         current++;
969 
970         int etype = _exptype(current);  // may call nextNode()
971 
972         if (NULL == etype)
973           return NULL;
974 
975         if (etype != expandedTypeID)
976           continue;
977 
978         return makeNodeHandle(current);  // make handle.
979       }
980     }
981   }
982 
983   /**
984    * Implements traversal of the Ancestor access, in reverse document order.
985    */
986   private class FollowingSiblingTraverser extends DTMAxisTraverser
987   {
988 
989     /**
990      * Traverse to the next node after the current node.
991      *
992      * @param context The context node of this iteration.
993      * @param current The current node of the iteration.
994      *
995      * @return the next node in the iteration, or DTM.NULL.
996      */
997     public int next(int context, int current)
998     {
999       return getNextSibling(current);
1000     }
1001 
1002     /**
1003      * Traverse to the next node after the current node that is matched
1004      * by the expanded type ID.
1005      *
1006      * @param context The context node of this iteration.
1007      * @param current The current node of the iteration.
1008      * @param expandedTypeID The expanded type ID that must match.
1009      *
1010      * @return the next node in the iteration, or DTM.NULL.
1011      */
1012     public int next(int context, int current, int expandedTypeID)
1013     {
1014 
1015       while (DTM.NULL != (current = getNextSibling(current)))
1016       {
1017         if (getExpandedTypeID(current) == expandedTypeID)
1018           return current;
1019       }
1020 
1021       return NULL;
1022     }
1023   }
1024 
1025   /**
1026    * Implements traversal of the Ancestor access, in reverse document order.
1027    */
1028   private class NamespaceDeclsTraverser extends DTMAxisTraverser
1029   {
1030 
1031     /**
1032      * Traverse to the next node after the current node.
1033      *
1034      * @param context The context node of this iteration.
1035      * @param current The current node of the iteration.
1036      *
1037      * @return the next node in the iteration, or DTM.NULL.
1038      */
1039     public int next(int context, int current)
1040     {
1041 
1042       return (context == current)
1043              ? getFirstNamespaceNode(context, false)
1044              : getNextNamespaceNode(context, current, false);
1045     }
1046 
1047     /**
1048      * Traverse to the next node after the current node that is matched
1049      * by the expanded type ID.
1050      *
1051      * @param context The context node of this iteration.
1052      * @param current The current node of the iteration.
1053      * @param expandedTypeID The expanded type ID that must match.
1054      *
1055      * @return the next node in the iteration, or DTM.NULL.
1056      */
1057     public int next(int context, int current, int expandedTypeID)
1058     {
1059 
1060       current = (context == current)
1061                 ? getFirstNamespaceNode(context, false)
1062                 : getNextNamespaceNode(context, current, false);
1063 
1064       do
1065       {
1066         if (getExpandedTypeID(current) == expandedTypeID)
1067           return current;
1068       }
1069       while (DTM.NULL
1070              != (current = getNextNamespaceNode(context, current, false)));
1071 
1072       return NULL;
1073     }
1074   }
1075 
1076   /**
1077    * Implements traversal of the Ancestor access, in reverse document order.
1078    */
1079   private class NamespaceTraverser extends DTMAxisTraverser
1080   {
1081 
1082     /**
1083      * Traverse to the next node after the current node.
1084      *
1085      * @param context The context node of this iteration.
1086      * @param current The current node of the iteration.
1087      *
1088      * @return the next node in the iteration, or DTM.NULL.
1089      */
1090     public int next(int context, int current)
1091     {
1092 
1093       return (context == current)
1094              ? getFirstNamespaceNode(context, true)
1095              : getNextNamespaceNode(context, current, true);
1096     }
1097 
1098     /**
1099      * Traverse to the next node after the current node that is matched
1100      * by the expanded type ID.
1101      *
1102      * @param context The context node of this iteration.
1103      * @param current The current node of the iteration.
1104      * @param expandedTypeID The expanded type ID that must match.
1105      *
1106      * @return the next node in the iteration, or DTM.NULL.
1107      */
1108     public int next(int context, int current, int expandedTypeID)
1109     {
1110 
1111       current = (context == current)
1112                 ? getFirstNamespaceNode(context, true)
1113                 : getNextNamespaceNode(context, current, true);
1114 
1115       do
1116       {
1117         if (getExpandedTypeID(current) == expandedTypeID)
1118           return current;
1119       }
1120       while (DTM.NULL
1121              != (current = getNextNamespaceNode(context, current, true)));
1122 
1123       return NULL;
1124     }
1125   }
1126 
1127   /**
1128    * Implements traversal of the Ancestor access, in reverse document order.
1129    */
1130   private class ParentTraverser extends DTMAxisTraverser
1131   {
1132     /**
1133      * By the nature of the stateless traversal, the context node can not be
1134      * returned or the iteration will go into an infinate loop.  So to traverse
1135      * an axis, the first function must be used to get the first node.
1136      *
1137      * <p>This method needs to be overloaded only by those axis that process
1138      * the self node. <\p>
1139      *
1140      * @param context The context node of this traversal. This is the point
1141      * that the traversal starts from.
1142      * @return the first node in the traversal.
1143      */
1144     public int first(int context)
1145     {
1146       return getParent(context);
1147     }
1148 
1149     /**
1150      * By the nature of the stateless traversal, the context node can not be
1151      * returned or the iteration will go into an infinate loop.  So to traverse
1152      * an axis, the first function must be used to get the first node.
1153      *
1154      * <p>This method needs to be overloaded only by those axis that process
1155      * the self node. <\p>
1156      *
1157      * @param context The context node of this traversal. This is the point
1158      * of origin for the traversal -- its "root node" or starting point.
1159      * @param expandedTypeID The expanded type ID that must match.
1160      *
1161      * @return the first node in the traversal.
1162      */
1163     public int first(int current, int expandedTypeID)
1164     {
1165                         // Compute in ID space
1166       current = makeNodeIdentity(current);
1167 
1168       while (NULL != (current = m_parent.elementAt(current)))
1169       {
1170         if (m_exptype.elementAt(current) == expandedTypeID)
1171           return makeNodeHandle(current);
1172       }
1173 
1174       return NULL;
1175     }
1176 
1177 
1178     /**
1179      * Traverse to the next node after the current node.
1180      *
1181      * @param context The context node of this iteration.
1182      * @param current The current node of the iteration.
1183      *
1184      * @return the next node in the iteration, or DTM.NULL.
1185      */
1186     public int next(int context, int current)
1187     {
1188 
1189       return NULL;
1190     }
1191 
1192 
1193 
1194     /**
1195      * Traverse to the next node after the current node that is matched
1196      * by the expanded type ID.
1197      *
1198      * @param context The context node of this iteration.
1199      * @param current The current node of the iteration.
1200      * @param expandedTypeID The expanded type ID that must match.
1201      *
1202      * @return the next node in the iteration, or DTM.NULL.
1203      */
1204     public int next(int context, int current, int expandedTypeID)
1205     {
1206 
1207       return NULL;
1208     }
1209   }
1210 
1211   /**
1212    * Implements traversal of the Ancestor access, in reverse document order.
1213    */
1214   private class PrecedingTraverser extends DTMAxisTraverser
1215   {
1216 
1217     /**
1218      * Tell if the current identity is an ancestor of the context identity.
1219      * This is an expensive operation, made worse by the stateless traversal.
1220      * But the preceding axis is used fairly infrequently.
1221      *
1222      * @param contextIdent The context node of the axis traversal.
1223      * @param currentIdent The node in question.
1224      * @return true if the currentIdent node is an ancestor of contextIdent.
1225      */
1226     protected boolean isAncestor(int contextIdent, int currentIdent)
1227     {
1228                         // %REVIEW% See comments in IsAfterAxis; using the "successor" of
1229                         // contextIdent is probably more efficient.
1230       for (contextIdent = m_parent.elementAt(contextIdent); DTM.NULL != contextIdent;
1231               contextIdent = m_parent.elementAt(contextIdent))
1232       {
1233         if (contextIdent == currentIdent)
1234           return true;
1235       }
1236 
1237       return false;
1238     }
1239 
1240     /**
1241      * Traverse to the next node after the current node.
1242      *
1243      * @param context The context node of this iteration.
1244      * @param current The current node of the iteration.
1245      *
1246      * @return the next node in the iteration, or DTM.NULL.
1247      */
1248     public int next(int context, int current)
1249     {
1250                         // compute in ID space
1251       int subtreeRootIdent = makeNodeIdentity(context);
1252 
1253       for (current = makeNodeIdentity(current) - 1; current >= 0; current--)
1254       {
1255         short type = _type(current);
1256 
1257         if (ATTRIBUTE_NODE == type || NAMESPACE_NODE == type
1258                 || isAncestor(subtreeRootIdent, current))
1259           continue;
1260 
1261         return makeNodeHandle(current);  // make handle.
1262       }
1263 
1264       return NULL;
1265     }
1266 
1267     /**
1268      * Traverse to the next node after the current node that is matched
1269      * by the expanded type ID.
1270      *
1271      * @param context The context node of this iteration.
1272      * @param current The current node of the iteration.
1273      * @param expandedTypeID The expanded type ID that must match.
1274      *
1275      * @return the next node in the iteration, or DTM.NULL.
1276      */
1277     public int next(int context, int current, int expandedTypeID)
1278     {
1279                         // Compute in ID space
1280       int subtreeRootIdent = makeNodeIdentity(context);
1281 
1282       for (current = makeNodeIdentity(current) - 1; current >= 0; current--)
1283       {
1284         int exptype = m_exptype.elementAt(current);
1285 
1286         if (exptype != expandedTypeID
1287                 || isAncestor(subtreeRootIdent, current))
1288           continue;
1289 
1290         return makeNodeHandle(current);  // make handle.
1291       }
1292 
1293       return NULL;
1294     }
1295   }
1296 
1297   /**
1298    * Implements traversal of the Ancestor and the Preceding axis,
1299    * in reverse document order.
1300    */
1301   private class PrecedingAndAncestorTraverser extends DTMAxisTraverser
1302   {
1303 
1304     /**
1305      * Traverse to the next node after the current node.
1306      *
1307      * @param context The context node of this iteration.
1308      * @param current The current node of the iteration.
1309      *
1310      * @return the next node in the iteration, or DTM.NULL.
1311      */
1312     public int next(int context, int current)
1313     {
1314                         // Compute in ID space
1315       int subtreeRootIdent = makeNodeIdentity(context );
1316 
1317       for (current = makeNodeIdentity(current) - 1; current >= 0; current--)
1318       {
1319         short type = _type(current);
1320 
1321         if (ATTRIBUTE_NODE == type || NAMESPACE_NODE == type)
1322           continue;
1323 
1324         return makeNodeHandle(current);  // make handle.
1325       }
1326 
1327       return NULL;
1328     }
1329 
1330     /**
1331      * Traverse to the next node after the current node that is matched
1332      * by the expanded type ID.
1333      *
1334      * @param context The context node of this iteration.
1335      * @param current The current node of the iteration.
1336      * @param expandedTypeID The expanded type ID that must match.
1337      *
1338      * @return the next node in the iteration, or DTM.NULL.
1339      */
1340     public int next(int context, int current, int expandedTypeID)
1341     {
1342                         // Compute in ID space
1343       int subtreeRootIdent = makeNodeIdentity(context);
1344 
1345       for (current = makeNodeIdentity(current) - 1; current >= 0; current--)
1346       {
1347         int exptype = m_exptype.elementAt(current);
1348 
1349         if (exptype != expandedTypeID)
1350           continue;
1351 
1352         return makeNodeHandle(current);  // make handle.
1353       }
1354 
1355       return NULL;
1356     }
1357   }
1358 
1359   /**
1360    * Implements traversal of the Ancestor access, in reverse document order.
1361    */
1362   private class PrecedingSiblingTraverser extends DTMAxisTraverser
1363   {
1364 
1365     /**
1366      * Traverse to the next node after the current node.
1367      *
1368      * @param context The context node of this iteration.
1369      * @param current The current node of the iteration.
1370      *
1371      * @return the next node in the iteration, or DTM.NULL.
1372      */
1373     public int next(int context, int current)
1374     {
1375       return getPreviousSibling(current);
1376     }
1377 
1378     /**
1379      * Traverse to the next node after the current node that is matched
1380      * by the expanded type ID.
1381      *
1382      * @param context The context node of this iteration.
1383      * @param current The current node of the iteration.
1384      * @param expandedTypeID The expanded type ID that must match.
1385      *
1386      * @return the next node in the iteration, or DTM.NULL.
1387      */
1388     public int next(int context, int current, int expandedTypeID)
1389     {
1390 
1391       while (DTM.NULL != (current = getPreviousSibling(current)))
1392       {
1393         if (getExpandedTypeID(current) == expandedTypeID)
1394           return current;
1395       }
1396 
1397       return NULL;
1398     }
1399   }
1400 
1401   /**
1402    * Implements traversal of the Self axis.
1403    */
1404   private class SelfTraverser extends DTMAxisTraverser
1405   {
1406 
1407     /**
1408      * By the nature of the stateless traversal, the context node can not be
1409      * returned or the iteration will go into an infinate loop.  To see if
1410      * the self node should be processed, use this function.
1411      *
1412      * @param context The context node of this traversal.
1413      *
1414      * @return the first node in the traversal.
1415      */
1416     public int first(int context)
1417     {
1418       return context;
1419     }
1420 
1421     /**
1422      * By the nature of the stateless traversal, the context node can not be
1423      * returned or the iteration will go into an infinate loop.  To see if
1424      * the self node should be processed, use this function.  If the context
1425      * node does not match the expanded type ID, this function will return
1426      * false.
1427      *
1428      * @param context The context node of this traversal.
1429      * @param expandedTypeID The expanded type ID that must match.
1430      *
1431      * @return the first node in the traversal.
1432      */
1433     public int first(int context, int expandedTypeID)
1434     {
1435       return (getExpandedTypeID(context) == expandedTypeID) ? context : NULL;
1436     }
1437 
1438     /**
1439      * Traverse to the next node after the current node.
1440      *
1441      * @param context The context node of this iteration.
1442      * @param current The current node of the iteration.
1443      *
1444      * @return Always return NULL for this axis.
1445      */
1446     public int next(int context, int current)
1447     {
1448       return NULL;
1449     }
1450 
1451     /**
1452      * Traverse to the next node after the current node that is matched
1453      * by the expanded type ID.
1454      *
1455      * @param context The context node of this iteration.
1456      * @param current The current node of the iteration.
1457      * @param expandedTypeID The expanded type ID that must match.
1458      *
1459      * @return the next node in the iteration, or DTM.NULL.
1460      */
1461     public int next(int context, int current, int expandedTypeID)
1462     {
1463       return NULL;
1464     }
1465   }
1466 
1467   /**
1468    * Implements traversal of the Ancestor access, in reverse document order.
1469    */
1470   private class AllFromRootTraverser extends AllFromNodeTraverser
1471   {
1472 
1473     /**
1474      * Return the root.
1475      *
1476      * @param context The context node of this traversal.
1477      *
1478      * @return the first node in the traversal.
1479      */
1480     public int first(int context)
1481     {
1482       return getDocumentRoot(context);
1483     }
1484 
1485     /**
1486      * Return the root if it matches the expanded type ID.
1487      *
1488      * @param context The context node of this traversal.
1489      * @param expandedTypeID The expanded type ID that must match.
1490      *
1491      * @return the first node in the traversal.
1492      */
1493     public int first(int context, int expandedTypeID)
1494     {
1495       return (getExpandedTypeID(getDocumentRoot(context)) == expandedTypeID)
1496              ? context : next(context, context, expandedTypeID);
1497     }
1498 
1499     /**
1500      * Traverse to the next node after the current node.
1501      *
1502      * @param context The context node of this iteration.
1503      * @param current The current node of the iteration.
1504      *
1505      * @return the next node in the iteration, or DTM.NULL.
1506      */
1507     public int next(int context, int current)
1508     {
1509                         // Compute in ID space
1510       int subtreeRootIdent = makeNodeIdentity(context);
1511 
1512       for (current = makeNodeIdentity(current) + 1; ; current++)
1513       {
1514                                 // Kluge test: Just make sure +1 yielded a real node
1515         int type = _type(current);  // may call nextNode()
1516         if (type == NULL)
1517           return NULL;
1518 
1519         return makeNodeHandle(current);  // make handle.
1520       }
1521     }
1522 
1523     /**
1524      * Traverse to the next node after the current node that is matched
1525      * by the expanded type ID.
1526      *
1527      * @param context The context node of this iteration.
1528      * @param current The current node of the iteration.
1529      * @param expandedTypeID The expanded type ID that must match.
1530      *
1531      * @return the next node in the iteration, or DTM.NULL.
1532      */
1533     public int next(int context, int current, int expandedTypeID)
1534     {
1535                         // Compute in ID space
1536       int subtreeRootIdent = makeNodeIdentity(context);
1537 
1538       for (current = makeNodeIdentity(current) + 1; ; current++)
1539       {
1540         int exptype = _exptype(current);  // may call nextNode()
1541 
1542         if (exptype == NULL)
1543           return NULL;
1544 
1545         if (exptype != expandedTypeID)
1546           continue;
1547 
1548         return makeNodeHandle(current);  // make handle.
1549       }
1550     }
1551   }
1552 
1553   /**
1554    * Implements traversal of the Self axis.
1555    */
1556   private class RootTraverser extends AllFromRootTraverser
1557   {
1558     /**
1559      * Return the root if it matches the expanded type ID,
1560      * else return null (nothing found)
1561      *
1562      * @param context The context node of this traversal.
1563      * @param expandedTypeID The expanded type ID that must match.
1564      *
1565      * @return the first node in the traversal.
1566      */
1567     public int first(int context, int expandedTypeID)
1568     {
1569       int root=getDocumentRoot(context);
1570       return (getExpandedTypeID(root) == expandedTypeID)
1571         ? root : NULL;
1572     }
1573 
1574     /**
1575      * Traverse to the next node after the current node.
1576      *
1577      * @param context The context node of this iteration.
1578      * @param current The current node of the iteration.
1579      *
1580      * @return Always return NULL for this axis.
1581      */
1582     public int next(int context, int current)
1583     {
1584       return NULL;
1585     }
1586 
1587     /**
1588      * Traverse to the next node after the current node that is matched
1589      * by the expanded type ID.
1590      *
1591      * @param context The context node of this iteration.
1592      * @param current The current node of the iteration.
1593      * @param expandedTypeID The expanded type ID that must match.
1594      *
1595      * @return the next node in the iteration, or DTM.NULL.
1596      */
1597     public int next(int context, int current, int expandedTypeID)
1598     {
1599       return NULL;
1600     }
1601   }
1602 
1603   /**
1604    * A non-xpath axis, returns all nodes that aren't namespaces or attributes,
1605    * from and including the root.
1606    */
1607   private class DescendantOrSelfFromRootTraverser extends DescendantTraverser
1608   {
1609 
1610     /**
1611      * Get the first potential identity that can be returned, which is the axis
1612      * root context in this case.
1613      *
1614      * @param identity The node identity of the root context of the traversal.
1615      *
1616      * @return The identity argument.
1617      */
1618     protected int getFirstPotential(int identity)
1619     {
1620       return identity;
1621     }
1622 
1623     /**
1624      * Get the first potential identity that can be returned.
1625      * @param handle handle to the root context.
1626      * @return identity of the root of the subtree.
1627      */
1628     protected int getSubtreeRoot(int handle)
1629     {
1630                         // %REVIEW% Shouldn't this always be 0?
1631       return makeNodeIdentity(getDocument());
1632     }
1633 
1634     /**
1635      * Return the root.
1636      *
1637      * @param context The context node of this traversal.
1638      *
1639      * @return the first node in the traversal.
1640      */
1641     public int first(int context)
1642     {
1643       return getDocumentRoot(context);
1644     }
1645 
1646     /**
1647      * By the nature of the stateless traversal, the context node can not be
1648      * returned or the iteration will go into an infinate loop.  So to traverse
1649      * an axis, the first function must be used to get the first node.
1650      *
1651      * <p>This method needs to be overloaded only by those axis that process
1652      * the self node. <\p>
1653      *
1654      * @param context The context node of this traversal. This is the point
1655      * of origin for the traversal -- its "root node" or starting point.
1656      * @param expandedTypeID The expanded type ID that must match.
1657      *
1658      * @return the first node in the traversal.
1659      */
1660     public int first(int context, int expandedTypeID)
1661     {
1662       if (isIndexed(expandedTypeID))
1663       {
1664         int identity = 0;
1665         int firstPotential = getFirstPotential(identity);
1666 
1667         return makeNodeHandle(getNextIndexed(identity, firstPotential, expandedTypeID));
1668       }
1669 
1670       int root = first(context);
1671       return next(root, root, expandedTypeID);
1672     }
1673   }
1674 
1675   /**
1676    * A non-xpath axis, returns all nodes that aren't namespaces or attributes,
1677    * from but not including the root.
1678    */
1679   private class DescendantFromRootTraverser extends DescendantTraverser
1680   {
1681 
1682     /**
1683      * Get the first potential identity that can be returned, which is the axis
1684      * root context in this case.
1685      *
1686      * @param identity The node identity of the root context of the traversal.
1687      *
1688      * @return The identity argument.
1689      */
1690     protected int getFirstPotential(int identity)
1691     {
1692       return _firstch(0);
1693     }
1694 
1695     /**
1696      * Get the first potential identity that can be returned.
1697      * @param handle handle to the root context.
1698      * @return identity of the root of the subtree.
1699      */
1700     protected int getSubtreeRoot(int handle)
1701     {
1702       return 0;
1703     }
1704 
1705     /**
1706      * Return the root.
1707      *
1708      * @param context The context node of this traversal.
1709      *
1710      * @return the first node in the traversal.
1711      */
1712     public int first(int context)
1713     {
1714       return makeNodeHandle(_firstch(0));
1715     }
1716 
1717     /**
1718      * By the nature of the stateless traversal, the context node can not be
1719      * returned or the iteration will go into an infinate loop.  So to traverse
1720      * an axis, the first function must be used to get the first node.
1721      *
1722      * <p>This method needs to be overloaded only by those axis that process
1723      * the self node. <\p>
1724      *
1725      * @param context The context node of this traversal. This is the point
1726      * of origin for the traversal -- its "root node" or starting point.
1727      * @param expandedTypeID The expanded type ID that must match.
1728      *
1729      * @return the first node in the traversal.
1730      */
1731     public int first(int context, int expandedTypeID)
1732     {
1733       if (isIndexed(expandedTypeID))
1734       {
1735         int identity = 0;
1736         int firstPotential = getFirstPotential(identity);
1737 
1738         return makeNodeHandle(getNextIndexed(identity, firstPotential, expandedTypeID));
1739       }
1740 
1741       int root = getDocumentRoot(context);
1742       return next(root, root, expandedTypeID);
1743     }
1744 
1745   }
1746 
1747 }