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: KeyIndex.java 468651 2006-10-28 07:04:25Z minchau $
020     */
021    
022    package org.apache.xalan.xsltc.dom;
023    
024    import java.util.StringTokenizer;
025    
026    import org.apache.xalan.xsltc.DOM;
027    import org.apache.xalan.xsltc.DOMEnhancedForDTM;
028    import org.apache.xalan.xsltc.runtime.BasisLibrary;
029    import org.apache.xalan.xsltc.runtime.Hashtable;
030    import org.apache.xalan.xsltc.util.IntegerArray;
031    
032    import org.apache.xml.dtm.Axis;
033    import org.apache.xml.dtm.DTM;
034    import org.apache.xml.dtm.DTMAxisIterator;
035    import org.apache.xml.dtm.ref.DTMAxisIteratorBase;
036    
037    /**
038     * Stores mappings of key values or IDs to DTM nodes.
039     * <em>Use of an instance of this class as a {@link DTMAxisIterator} is
040     * <b>deprecated.</b></em>
041     * @author Morten Jorgensen
042     * @author Santiago Pericas-Geertsen
043     */
044    public class KeyIndex extends DTMAxisIteratorBase {
045    
046        /**
047         * A mapping between values and nodesets for the current document.  Used
048         * only while building keys.
049         */
050        private Hashtable _index;
051    
052        /**
053         * The document node currently being processed.  Used only while building
054         * keys.
055         */
056        private int _currentDocumentNode = DTM.NULL;
057    
058        /**
059         * A mapping from a document node to the mapping between values and nodesets
060         */
061        private Hashtable _rootToIndexMap = new Hashtable();
062    
063        /**
064         * The node set associated to the current value passed
065         * to lookupKey();
066         */
067        private IntegerArray _nodes = null;
068    
069        /**
070         * The XSLTC DOM object if this KeyIndex is being used to implement the
071         * id() function.
072         */
073        private DOM        _dom;
074        
075        private DOMEnhancedForDTM    _enhancedDOM;
076    
077        /**
078         * Store position after call to setMark()
079         */
080        private int _markedPosition = 0;
081    
082        public KeyIndex(int dummy) {
083        }
084    
085        public void setRestartable(boolean flag) {
086        }
087    
088        /**
089         * Adds a node to the node list for a given value. Nodes will
090         * always be added in document order.
091         */
092        public void add(Object value, int node, int rootNode) {
093            if (_currentDocumentNode != rootNode) {
094                _currentDocumentNode = rootNode;
095                _index = new Hashtable();
096                _rootToIndexMap.put(new Integer(rootNode), _index);
097            }
098    
099            IntegerArray nodes = (IntegerArray) _index.get(value);
100    
101            if (nodes == null) {
102                 nodes = new IntegerArray();
103                _index.put(value, nodes);
104                nodes.add(node);
105    
106            // Because nodes are added in document order,
107            // duplicates can be eliminated easily at this stage.
108            } else if (node != nodes.at(nodes.cardinality() - 1)) {
109                nodes.add(node);
110            }
111        }
112    
113        /**
114         * Merge the current value's nodeset set by lookupKey() with _nodes.
115         * @deprecated
116         */
117        public void merge(KeyIndex other) {
118            if (other == null) return;
119    
120            if (other._nodes != null) {
121                if (_nodes == null) {
122                    _nodes = (IntegerArray)other._nodes.clone();
123                }
124                else {
125                    _nodes.merge(other._nodes);
126                }
127            }
128        }
129    
130        /**
131         * This method must be called by the code generated by the id() function
132         * prior to returning the node iterator. The lookup code for key() and
133         * id() differ in the way the lookup value can be whitespace separated
134         * list of tokens for the id() function, but a single string for the
135         * key() function.
136         * @deprecated
137         */
138        public void lookupId(Object value) {
139            // Clear _nodes array
140            _nodes = null;
141    
142            final StringTokenizer values = new StringTokenizer((String) value,
143                                                               " \n\t");
144            while (values.hasMoreElements()) {
145                final String token = (String) values.nextElement();
146                IntegerArray nodes = (IntegerArray) _index.get(token);
147    
148                if (nodes == null && _enhancedDOM != null
149                    && _enhancedDOM.hasDOMSource()) {
150                    nodes = getDOMNodeById(token);
151                }
152    
153                if (nodes == null) continue;
154    
155                if (_nodes == null) {
156                     nodes = (IntegerArray)nodes.clone();
157                    _nodes = nodes;
158                }
159                else {
160                    _nodes.merge(nodes);
161                }
162            }
163        }
164    
165        /**
166         * Return an IntegerArray for the DOM Node which has the given id.
167         * 
168         * @param id The id
169         * @return A IntegerArray representing the Node whose id is the given value.
170         */
171        public IntegerArray getDOMNodeById(String id) {
172            IntegerArray nodes = null;
173    
174            if (_enhancedDOM != null) {
175                int ident = _enhancedDOM.getElementById(id);
176    
177                if (ident != DTM.NULL) {
178                    Integer root = new Integer(_enhancedDOM.getDocument());
179                    Hashtable index = (Hashtable) _rootToIndexMap.get(root);
180    
181                    if (index == null) {
182                        index = new Hashtable();
183                        _rootToIndexMap.put(root, index);
184                    } else {
185                        nodes = (IntegerArray) index.get(id);
186                    }
187    
188                    if (nodes == null) {
189                        nodes = new IntegerArray();
190                        index.put(id, nodes);
191                    }
192    
193                    nodes.add(_enhancedDOM.getNodeHandle(ident));
194                }
195            }
196    
197            return nodes;
198        }
199        
200        /**
201         * <p>This method must be called by the code generated by the key() function
202         * prior to returning the node iterator.</p>
203         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
204         * <b>deprecated.</b></em></p>
205         * @deprecated
206         */
207        public void lookupKey(Object value) {
208            IntegerArray nodes = (IntegerArray) _index.get(value);
209            _nodes = (nodes != null) ? (IntegerArray) nodes.clone() : null;
210            _position = 0;
211        }
212    
213        /** 
214         * <p>Callers should not call next() after it returns END.</p>
215         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
216         * <b>deprecated.</b></em></p>
217         * @deprecated
218         */
219        public int next() {
220            if (_nodes == null) return DTMAxisIterator.END;
221    
222            return (_position < _nodes.cardinality()) ? 
223                _dom.getNodeHandle(_nodes.at(_position++)) : DTMAxisIterator.END;
224        }
225    
226        /**
227         * Given a context node and the argument to the XPath <code>id</code>
228         * function, checks whether the context node is in the set of nodes that
229         * results from that reference to the <code>id</code> function.  This is
230         * used in the implementation of <code>id</code> patterns.
231         *
232         * @param node The context node
233         * @param value The argument to the <code>id</code> function
234         * @return <code>1</code> if the context node is in the set of nodes
235         *         returned by the reference to the <code>id</code> function;
236         *         <code>0</code>, otherwise
237         */
238        public int containsID(int node, Object value) {
239            final String string = (String)value;
240            int rootHandle = _dom.getAxisIterator(Axis.ROOT)
241                                     .setStartNode(node).next();
242    
243            // Get the mapping table for the document containing the context node
244            Hashtable index =
245                (Hashtable) _rootToIndexMap.get(new Integer(rootHandle));
246    
247            // Split argument to id function into XML whitespace separated tokens
248            final StringTokenizer values = new StringTokenizer(string, " \n\t");
249    
250            while (values.hasMoreElements()) {
251                final String token = (String) values.nextElement();
252                IntegerArray nodes = null;
253    
254                if (index != null) {
255                    nodes = (IntegerArray) index.get(token);
256                }
257    
258                // If input was from W3C DOM, use DOM's getElementById to do
259                // the look-up.
260                if (nodes == null && _enhancedDOM != null
261                    && _enhancedDOM.hasDOMSource()) {
262                    nodes = getDOMNodeById(token);  
263                }
264    
265                // Did we find the context node in the set of nodes?
266                if (nodes != null && nodes.indexOf(node) >= 0) {
267                    return 1;
268                }
269            }
270    
271            // Didn't find the context node in the set of nodes returned by id
272            return 0;
273        }
274    
275        /**
276         * <p>Given a context node and the second argument to the XSLT
277         * <code>key</code> function, checks whether the context node is in the
278         * set of nodes that results from that reference to the <code>key</code>
279         * function.  This is used in the implementation of key patterns.</p>
280         * <p>This particular {@link KeyIndex} object is the result evaluating the
281         * first argument to the <code>key</code> function, so it's not taken into
282         * any further account.</p>
283         *
284         * @param node The context node
285         * @param value The second argument to the <code>key</code> function
286         * @return <code>1</code> if and only if the context node is in the set of
287         *         nodes returned by the reference to the <code>key</code> function;
288         *         <code>0</code>, otherwise
289         */
290        public int containsKey(int node, Object value) {
291            int rootHandle = _dom.getAxisIterator(Axis.ROOT)
292                                     .setStartNode(node).next();
293    
294            // Get the mapping table for the document containing the context node
295            Hashtable index =
296                        (Hashtable) _rootToIndexMap.get(new Integer(rootHandle));
297    
298            // Check whether the context node is present in the set of nodes
299            // returned by the key function
300            if (index != null) {
301                final IntegerArray nodes = (IntegerArray) index.get(value);
302                return (nodes != null && nodes.indexOf(node) >= 0) ? 1 : 0;
303            }
304    
305            // The particular key name identifies no nodes in this document
306            return 0;
307        }
308    
309        /**
310         * <p>Resets the iterator to the last start node.</p>
311         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
312         * <b>deprecated.</b></em></p>
313         * @deprecated
314         */
315        public DTMAxisIterator reset() {
316            _position = 0;
317            return this;
318        }
319    
320        /**
321         * <p>Returns the number of elements in this iterator.</p>
322         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
323         * <b>deprecated.</b></em></p>
324         * @deprecated
325         */
326        public int getLast() {
327            return (_nodes == null) ? 0 : _nodes.cardinality();
328        }
329    
330        /**
331         * <p>Returns the position of the current node in the set.</p>
332         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
333         * <b>deprecated.</b></em></p>
334         * @deprecated
335         */
336        public int getPosition() {
337            return _position;
338        }
339    
340        /**
341         * <p>Remembers the current node for the next call to gotoMark().</p>
342         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
343         * <b>deprecated.</b></em></p>
344         * @deprecated
345         */
346        public void setMark() {
347            _markedPosition = _position;
348        }
349    
350        /**
351         * <p>Restores the current node remembered by setMark().</p>
352         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
353         * <b>deprecated.</b></em></p>
354         * @deprecated
355         */
356        public void gotoMark() {
357            _position = _markedPosition;
358        }
359    
360        /** 
361         * <p>Set start to END should 'close' the iterator, 
362         * i.e. subsequent call to next() should return END.</p>
363         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
364         * <b>deprecated.</b></em></p>
365         * @deprecated
366         */
367        public DTMAxisIterator setStartNode(int start) {
368            if (start == DTMAxisIterator.END) {
369                _nodes = null;
370            }
371            else if (_nodes != null) {
372                _position = 0;
373            }
374            return (DTMAxisIterator) this;
375        }
376        
377        /** 
378         * <p>Get start to END should 'close' the iterator, 
379         * i.e. subsequent call to next() should return END.</p>
380         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
381         * <b>deprecated.</b></em></p>
382         * @deprecated
383         */
384        public int getStartNode() {      
385            return 0;
386        }
387    
388        /**
389         * <p>True if this iterator has a reversed axis.</p>
390         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
391         * <b>deprecated.</b></em></p>
392         * @deprecated
393         */
394        public boolean isReverse() {
395            return(false);
396        }
397    
398        /**
399         * <p>Returns a deep copy of this iterator.</p>
400         * <p><em>Use of an instance of this class as a {@link DTMAxisIterator} is
401         * <b>deprecated.</b></em></p>
402         * @deprecated
403         */
404        public DTMAxisIterator cloneIterator() {
405            KeyIndex other = new KeyIndex(0);
406            other._index = _index;
407            other._rootToIndexMap = _rootToIndexMap;
408            other._nodes = _nodes;
409            other._position = _position;
410            return (DTMAxisIterator) other;
411        }
412        
413        public void setDom(DOM dom) {
414            _dom = dom;
415            if (dom instanceof DOMEnhancedForDTM) {
416                _enhancedDOM = (DOMEnhancedForDTM)dom;
417            }
418            else if (dom instanceof DOMAdapter) {
419                DOM idom = ((DOMAdapter)dom).getDOMImpl();
420                if (idom instanceof DOMEnhancedForDTM) {
421                    _enhancedDOM = (DOMEnhancedForDTM)idom;
422                }
423            }
424        }
425    
426        /**
427         * Create a {@link KeyIndexIterator} that iterates over the nodes that
428         * result from a reference to the XSLT <code>key</code> function or
429         * XPath <code>id</code> function.
430         *
431         * @param keyValue A string or iterator representing the key values or id
432         *                 references
433         * @param isKeyCall A <code>boolean</code> indicating whether the iterator
434         *                 is being created for a reference <code>key</code> or
435         *                 <code>id</code>
436         */
437        public KeyIndexIterator getKeyIndexIterator(Object keyValue,
438                                                    boolean isKeyCall) {
439            if (keyValue instanceof DTMAxisIterator) {
440                return getKeyIndexIterator((DTMAxisIterator) keyValue, isKeyCall);
441            } else {
442                return getKeyIndexIterator(BasisLibrary.stringF(keyValue, _dom),
443                                           isKeyCall);
444            }
445        }
446    
447        /**
448         * Create a {@link KeyIndexIterator} that iterates over the nodes that
449         * result from a reference to the XSLT <code>key</code> function or
450         * XPath <code>id</code> function.
451         *
452         * @param keyValue A string representing the key values or id
453         *                 references
454         * @param isKeyCall A <code>boolean</code> indicating whether the iterator
455         *                 is being created for a reference <code>key</code> or
456         *                 <code>id</code>
457         */
458        public KeyIndexIterator getKeyIndexIterator(String keyValue,
459                                                    boolean isKeyCall) {
460            return new KeyIndexIterator(keyValue, isKeyCall);
461        }
462    
463        /**
464         * Create a {@link KeyIndexIterator} that iterates over the nodes that
465         * result from a reference to the XSLT <code>key</code> function or
466         * XPath <code>id</code> function.
467         *
468         * @param keyValue An iterator representing the key values or id
469         *                 references
470         * @param isKeyCall A <code>boolean</code> indicating whether the iterator
471         *                 is being created for a reference <code>key</code> or
472         *                 <code>id</code>
473         */
474        public KeyIndexIterator getKeyIndexIterator(DTMAxisIterator keyValue,
475                                                    boolean isKeyCall) {
476            return new KeyIndexIterator(keyValue, isKeyCall);
477        }
478    
479        /**
480         * Used to represent an empty node set.
481         */
482        final private static IntegerArray EMPTY_NODES = new IntegerArray(0);
483    
484    
485        /**
486         * An iterator representing the result of a reference to either the
487         * XSLT <code>key</code> function or the XPath <code>id</code> function.
488         */
489        public class KeyIndexIterator extends MultiValuedNodeHeapIterator {
490    
491            /**
492             * <p>A reference to the <code>key</code> function that only has one
493             * key value or to the <code>id</code> function that has only one string
494             * argument can be optimized to ignore the multi-valued heap.  This
495             * field will be <code>null</code> otherwise.
496             */
497            private IntegerArray _nodes;
498    
499            /**
500             * <p>This field contains the iterator representing a node set key value
501             * argument to the <code>key</code> function or a node set argument
502             * to the <code>id</code> function.</p>
503             *
504             * <p>Exactly one of this field and {@link #_keyValue} must be
505             * <code>null</code>.</p>
506             */
507            private DTMAxisIterator _keyValueIterator;
508    
509            /**
510             * <p>This field contains the iterator representing a non-node-set key
511             * value argument to the <code>key</code> function or a non-node-set
512             * argument to the <code>id</code> function.</p>
513             *
514             * <p>Exactly one of this field and {@link #_keyValueIterator} must be
515             * <code>null</code>.</p>
516             */
517            private String _keyValue;
518    
519            /**
520             * Indicates whether this object represents the result of a reference
521             * to the <code>key</code> function (<code>true</code>) or the
522             * <code>id</code> function (<code>false</code>).
523             */
524            private boolean _isKeyIterator;
525    
526            /**
527             * Represents the DTM nodes retrieved for one key value or one string
528             * argument to <code>id</code> for use as one heap node in a
529             * {@link MultiValuedNodeHeapIterator}.
530             */
531            protected class KeyIndexHeapNode
532                    extends MultiValuedNodeHeapIterator.HeapNode
533            {
534                /**
535                 * {@link IntegerArray} of DTM nodes retrieved for one key value.
536                 * Must contain no duplicates and be stored in document order.
537                 */
538                private IntegerArray _nodes;
539    
540                /**
541                 * Position in {@link #_nodes} array of next node to return from
542                 * this heap node.
543                 */
544                private int _position = 0;
545    
546                /**
547                 * Marked position.  Used by {@link #setMark()} and
548                 * {@link #gotoMark()}
549                 */
550                private int _markPosition = -1;
551    
552                /**
553                 * Create a heap node representing DTM nodes retrieved for one
554                 * key value in a reference to the <code>key</code> function
555                 * or string argument to the <code>id</code> function.
556                 */
557                KeyIndexHeapNode(IntegerArray nodes) {
558                    _nodes = nodes;
559                }
560    
561                /**
562                 * Advance to the next node represented by this {@link HeapNode}
563                 *
564                 * @return the next DTM node.
565                 */
566                public int step() {
567                    if (_position < _nodes.cardinality()) {
568                        _node = _nodes.at(_position);
569                        _position++;
570                    } else {
571                        _node = DTMAxisIterator.END;
572                    }
573    
574                    return _node;
575                }
576    
577                /**
578                 * Creates a deep copy of this {@link HeapNode}.  The clone is not
579                 * reset from the current position of the original.
580                 *
581                 * @return the cloned heap node
582                 */
583                public HeapNode cloneHeapNode() {
584                    KeyIndexHeapNode clone =
585                            (KeyIndexHeapNode) super.cloneHeapNode();
586    
587                    clone._nodes = _nodes;
588                    clone._position = _position;
589                    clone._markPosition = _markPosition;
590    
591                    return clone;
592                }
593    
594                /**
595                 * Remembers the current node for the next call to
596                 * {@link #gotoMark()}.
597                 */
598                public void setMark() {
599                    _markPosition = _position;
600                }
601    
602                /**
603                 * Restores the current node remembered by {@link #setMark()}.
604                 */
605                public void gotoMark() {
606                    _position = _markPosition;
607                }
608    
609                /**
610                 * Performs a comparison of the two heap nodes
611                 *
612                 * @param heapNode the heap node against which to compare
613                 * @return <code>true</code> if and only if the current node for
614                 *         this heap node is before the current node of the
615                 *         argument heap node in document order.
616                 */
617                public boolean isLessThan(HeapNode heapNode) {
618                    return _node < heapNode._node;
619                }
620    
621                /**
622                 * <p>Sets context with respect to which this heap node is
623                 * evaluated.</p>
624                 * <p>This has no real effect on this kind of heap node.  Instead,
625                 * the {@link KeyIndexIterator#setStartNode(int)} method should
626                 * create new instances of this class to represent the effect of
627                 * changing the context.</p>
628                 */
629                public HeapNode setStartNode(int node) {
630                    return this;
631                }
632    
633                /**
634                 * Reset the heap node back to its beginning.
635                 */
636                public HeapNode reset() {
637                    _position = 0;
638                    return this;
639                }
640            }
641    
642            /**
643             * Constructor used when the argument to <code>key</code> or
644             * <code>id</code> is not a node set.
645             *
646             * @param keyValue the argument to <code>key</code> or <code>id</code>
647             *                 cast to a <code>String</code>
648             * @param isKeyIterator indicates whether the constructed iterator
649             *                represents a reference to <code>key</code> or
650             *                <code>id</code>.
651             */
652            KeyIndexIterator(String keyValue, boolean isKeyIterator) {
653                _isKeyIterator = isKeyIterator;
654                _keyValue = keyValue;
655            }
656    
657            /**
658             * Constructor used when the argument to <code>key</code> or
659             * <code>id</code> is a node set.
660             *
661             * @param keyValues the argument to <code>key</code> or <code>id</code>
662             * @param isKeyIterator indicates whether the constructed iterator
663             *                represents a reference to <code>key</code> or
664             *                <code>id</code>.
665             */
666            KeyIndexIterator(DTMAxisIterator keyValues, boolean isKeyIterator) {
667                _keyValueIterator = keyValues;
668                _isKeyIterator = isKeyIterator;
669            }
670    
671            /**
672             * Retrieve nodes for a particular key value or a particular id 
673             * argument value.
674             *
675             * @param root The root node of the document containing the context node
676             * @param keyValue The key value of id string argument value
677             * @return an {@link IntegerArray} of the resulting nodes
678             */
679            protected IntegerArray lookupNodes(int root, String keyValue) {
680                IntegerArray result = null;
681    
682                // Get mapping from key values/IDs to DTM nodes for this document
683                Hashtable index = (Hashtable)_rootToIndexMap.get(new Integer(root));
684    
685                if (!_isKeyIterator) {
686                    // For id function, tokenize argument as whitespace separated
687                    // list of values and look up nodes identified by each ID.
688                    final StringTokenizer values =
689                            new StringTokenizer(keyValue, " \n\t");
690    
691                    while (values.hasMoreElements()) {
692                        final String token = (String) values.nextElement();
693                        IntegerArray nodes = null;
694    
695                        // Does the ID map to any node in the document?
696                        if (index != null) {
697                            nodes = (IntegerArray) index.get(token);
698                        }
699    
700                        // If input was from W3C DOM, use DOM's getElementById to do
701                        // the look-up.
702                        if (nodes == null && _enhancedDOM != null
703                                && _enhancedDOM.hasDOMSource()) {
704                            nodes = getDOMNodeById(token);
705                        }
706    
707                        // If we found any nodes, merge them into the cumulative
708                        // result
709                        if (nodes != null) {
710                            if (result == null) {
711                                result = (IntegerArray)nodes.clone();
712                            } else {
713                                result.merge(nodes);
714                            }
715                        }
716                    }
717                } else if (index != null) {
718                    // For key function, map key value to nodes
719                    result = (IntegerArray) index.get(keyValue);
720                }
721    
722                return result;
723            }
724    
725            /**
726             * Set context node for the iterator.  This will cause the iterator
727             * to reset itself, reevaluate arguments to the function, look up
728             * nodes in the input and reinitialize its internal heap.
729             *
730             * @param node the context node
731             * @return A {@link DTMAxisIterator} set to the start of the iteration.
732             */
733            public DTMAxisIterator setStartNode(int node) {
734                _startNode = node;
735    
736                // If the arugment to the function is a node set, set the
737                // context node on it.
738                if (_keyValueIterator != null) {
739                    _keyValueIterator = _keyValueIterator.setStartNode(node);
740                }
741    
742                init();
743    
744                return super.setStartNode(node);
745            }
746    
747            /**
748             * Get the next node in the iteration.
749             *
750             * @return The next node handle in the iteration, or END.
751             */
752            public int next() {
753                int nodeHandle;
754    
755                // If at most one key value or at most one string argument to id
756                // resulted in nodes being returned, use the IntegerArray
757                // stored at _nodes directly.  This relies on the fact that the
758                // IntegerArray never includes duplicate nodes and is always stored
759                // in document order.
760                if (_nodes != null) {
761                    if (_position < _nodes.cardinality()) {
762                        nodeHandle = returnNode(_nodes.at(_position));
763                    } else {
764                        nodeHandle = DTMAxisIterator.END;
765                    }
766                } else {
767                    nodeHandle = super.next();
768                }
769    
770                return nodeHandle;
771            }
772    
773            /**
774             * Resets the iterator to the last start node.
775             *
776             * @return A DTMAxisIterator, which may or may not be the same as this
777             *         iterator.
778             */
779            public DTMAxisIterator reset() {
780                if (_nodes == null) {
781                    init();
782                } else {
783                    super.reset();
784                }
785    
786                return resetPosition();
787            }
788    
789            /**
790             * Evaluate the reference to the <code>key</code> or <code>id</code>
791             * function with the context specified by {@link #setStartNode(int)}
792             * and set up this iterator to iterate over the DTM nodes that are
793             * to be returned.
794             */
795            protected void init() {
796                super.init();
797                _position = 0;
798    
799                // All nodes retrieved are in the same document
800                int rootHandle = _dom.getAxisIterator(Axis.ROOT)
801                                          .setStartNode(_startNode).next();
802    
803                // Is the argument not a node set?
804                if (_keyValueIterator == null) {
805                    // Look up nodes returned for the single string argument
806                    _nodes = lookupNodes(rootHandle, _keyValue);
807    
808                    if (_nodes == null) {
809                        _nodes = EMPTY_NODES;
810                    }
811                } else {
812                    DTMAxisIterator keyValues = _keyValueIterator.reset();
813                    int retrievedKeyValueIdx = 0;
814                    boolean foundNodes = false;
815    
816                    _nodes = null;
817    
818                    // For each node in the node set argument, get the string value
819                    // and look up the nodes returned by key or id for that string
820                    // value.  If at most one string value has nodes associated,
821                    // the nodes will be stored in _nodes; otherwise, the nodes
822                    // will be placed in a heap.
823                    for (int keyValueNode = keyValues.next();
824                         keyValueNode != DTMAxisIterator.END;
825                         keyValueNode = keyValues.next()) {
826    
827                        String keyValue = BasisLibrary.stringF(keyValueNode, _dom);
828    
829                        IntegerArray nodes = lookupNodes(rootHandle, keyValue);
830    
831                        if (nodes != null) {
832                            if (!foundNodes) {
833                                _nodes = nodes;
834                                foundNodes = true;
835                            } else {
836                                if (_nodes != null) {
837                                    addHeapNode(new KeyIndexHeapNode(_nodes));
838                                    _nodes = null;
839                                }
840                                addHeapNode(new KeyIndexHeapNode(nodes));
841                            }
842                        }
843                    }
844    
845                    if (!foundNodes) {
846                        _nodes = EMPTY_NODES;
847                    }
848                }
849            }
850    
851            /**
852             * Returns the number of nodes in this iterator.
853             *
854             * @return the number of nodes
855             */
856            public int getLast() {
857                // If nodes are stored in _nodes, take advantage of the fact that
858                // there are no duplicates.  Otherwise, fall back to the base heap
859                // implementaiton and hope it does a good job with this.
860                return (_nodes != null) ? _nodes.cardinality() : super.getLast();
861            }
862    
863            /**
864             * Return the node at the given position.
865             *
866             * @param position The position
867             * @return The node at the given position.
868             */
869            public int getNodeByPosition(int position) {
870                int node = DTMAxisIterator.END;
871    
872                // If nodes are stored in _nodes, take advantage of the fact that
873                // there are no duplicates and they are stored in document order.
874                // Otherwise, fall back to the base heap implementation to do a
875                // good job with this.
876                if (_nodes != null) {
877                    if (position > 0) {
878                        if (position <= _nodes.cardinality()) {
879                            _position = position;
880                            node = _nodes.at(position-1);
881                        } else {
882                            _position = _nodes.cardinality();
883                        }
884                    }
885                } else {
886                    node = super.getNodeByPosition(position);
887                }
888    
889                return node;
890            }
891        }
892    }