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