View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /*
6    * Copyright 1999-2004 The Apache Software Foundation.
7    *
8    * Licensed under the Apache License, Version 2.0 (the "License");
9    * you may not use this file except in compliance with the License.
10   * You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  /*
21   * $Id: NodeSet.java,v 1.2.4.1 2005/09/10 17:39:49 jeffsuttor Exp $
22   */
23  package com.sun.org.apache.xpath.internal;
24  
25  import com.sun.org.apache.xalan.internal.res.XSLMessages;
26  import com.sun.org.apache.xml.internal.utils.DOM2Helper;
27  import com.sun.org.apache.xpath.internal.axes.ContextNodeList;
28  import com.sun.org.apache.xpath.internal.res.XPATHErrorResources;
29  
30  import org.w3c.dom.DOMException;
31  import org.w3c.dom.Node;
32  import org.w3c.dom.NodeList;
33  import org.w3c.dom.traversal.NodeFilter;
34  import org.w3c.dom.traversal.NodeIterator;
35  
36  
37  /**
38   * <p>The NodeSet class can act as either a NodeVector,
39   * NodeList, or NodeIterator.  However, in order for it to
40   * act as a NodeVector or NodeList, it's required that
41   * setShouldCacheNodes(true) be called before the first
42   * nextNode() is called, in order that nodes can be added
43   * as they are fetched.  Derived classes that implement iterators
44   * must override runTo(int index), in order that they may
45   * run the iteration to the given index. </p>
46   *
47   * <p>Note that we directly implement the DOM's NodeIterator
48   * interface. We do not emulate all the behavior of the
49   * standard NodeIterator. In particular, we do not guarantee
50   * to present a "live view" of the document ... but in XSLT,
51   * the source document should never be mutated, so this should
52   * never be an issue.</p>
53   *
54   * <p>Thought: Should NodeSet really implement NodeList and NodeIterator,
55   * or should there be specific subclasses of it which do so? The
56   * advantage of doing it all here is that all NodeSets will respond
57   * to the same calls; the disadvantage is that some of them may return
58   * less-than-enlightening results when you do so.</p>
59   * @xsl.usage advanced
60   */
61  public class NodeSet
62          implements NodeList, NodeIterator, Cloneable, ContextNodeList
63  {
64  
65    /**
66     * Create an empty nodelist.
67     */
68    public NodeSet()
69    {
70      m_blocksize = 32;
71      m_mapSize = 0;
72    }
73  
74    /**
75     * Create an empty, using the given block size.
76     *
77     * @param blocksize Size of blocks to allocate
78     */
79    public NodeSet(int blocksize)
80    {
81      m_blocksize = blocksize;
82      m_mapSize = 0;
83    }
84  
85    /**
86     * Create a NodeSet, and copy the members of the
87     * given nodelist into it.
88     *
89     * @param nodelist List of Nodes to be made members of the new set.
90     */
91    public NodeSet(NodeList nodelist)
92    {
93  
94      this(32);
95  
96      addNodes(nodelist);
97    }
98  
99    /**
100    * Create a NodeSet, and copy the members of the
101    * given NodeSet into it.
102    *
103    * @param nodelist Set of Nodes to be made members of the new set.
104    */
105   public NodeSet(NodeSet nodelist)
106   {
107 
108     this(32);
109 
110     addNodes((NodeIterator) nodelist);
111   }
112 
113   /**
114    * Create a NodeSet, and copy the members of the
115    * given NodeIterator into it.
116    *
117    * @param ni Iterator which yields Nodes to be made members of the new set.
118    */
119   public NodeSet(NodeIterator ni)
120   {
121 
122     this(32);
123 
124     addNodes(ni);
125   }
126 
127   /**
128    * Create a NodeSet which contains the given Node.
129    *
130    * @param node Single node to be added to the new set.
131    */
132   public NodeSet(Node node)
133   {
134 
135     this(32);
136 
137     addNode(node);
138   }
139 
140   /**
141    * @return The root node of the Iterator, as specified when it was created.
142    * For non-Iterator NodeSets, this will be null.
143    */
144   public Node getRoot()
145   {
146     return null;
147   }
148 
149   /**
150    * Get a cloned Iterator, and reset its state to the beginning of the
151    * iteration.
152    *
153    * @return a new NodeSet of the same type, having the same state...
154    * except that the reset() operation has been called.
155    *
156    * @throws CloneNotSupportedException if this subclass of NodeSet
157    * does not support the clone() operation.
158    */
159   public NodeIterator cloneWithReset() throws CloneNotSupportedException
160   {
161 
162     NodeSet clone = (NodeSet) clone();
163 
164     clone.reset();
165 
166     return clone;
167   }
168 
169   /**
170    * Reset the iterator. May have no effect on non-iterator Nodesets.
171    */
172   public void reset()
173   {
174     m_next = 0;
175   }
176 
177   /**
178    *  This attribute determines which node types are presented via the
179    * iterator. The available set of constants is defined in the
180    * <code>NodeFilter</code> interface. For NodeSets, the mask has been
181    * hardcoded to show all nodes except EntityReference nodes, which have
182    * no equivalent in the XPath data model.
183    *
184    * @return integer used as a bit-array, containing flags defined in
185    * the DOM's NodeFilter class. The value will be
186    * <code>SHOW_ALL & ~SHOW_ENTITY_REFERENCE</code>, meaning that
187    * only entity references are suppressed.
188    */
189   public int getWhatToShow()
190   {
191     return NodeFilter.SHOW_ALL & ~NodeFilter.SHOW_ENTITY_REFERENCE;
192   }
193 
194   /**
195    * The filter object used to screen nodes. Filters are applied to
196    * further reduce (and restructure) the NodeIterator's view of the
197    * document. In our case, we will be using hardcoded filters built
198    * into our iterators... but getFilter() is part of the DOM's
199    * NodeIterator interface, so we have to support it.
200    *
201    * @return null, which is slightly misleading. True, there is no
202    * user-written filter object, but in fact we are doing some very
203    * sophisticated custom filtering. A DOM purist might suggest
204    * returning a placeholder object just to indicate that this is
205    * not going to return all nodes selected by whatToShow.
206    */
207   public NodeFilter getFilter()
208   {
209     return null;
210   }
211 
212   /**
213    *  The value of this flag determines whether the children of entity
214    * reference nodes are visible to the iterator. If false, they will be
215    * skipped over.
216    * <br> To produce a view of the document that has entity references
217    * expanded and does not expose the entity reference node itself, use the
218    * whatToShow flags to hide the entity reference node and set
219    * expandEntityReferences to true when creating the iterator. To produce
220    * a view of the document that has entity reference nodes but no entity
221    * expansion, use the whatToShow flags to show the entity reference node
222    * and set expandEntityReferences to false.
223    *
224    * @return true for all iterators based on NodeSet, meaning that the
225    * contents of EntityRefrence nodes may be returned (though whatToShow
226    * says that the EntityReferences themselves are not shown.)
227    */
228   public boolean getExpandEntityReferences()
229   {
230     return true;
231   }
232 
233   /**
234    *  Returns the next node in the set and advances the position of the
235    * iterator in the set. After a NodeIterator is created, the first call
236    * to nextNode() returns the first node in the set.
237    * @return  The next <code>Node</code> in the set being iterated over, or
238    *   <code>null</code> if there are no more members in that set.
239    * @throws DOMException
240    *    INVALID_STATE_ERR: Raised if this method is called after the
241    *   <code>detach</code> method was invoked.
242    */
243   public Node nextNode() throws DOMException
244   {
245 
246     if ((m_next) < this.size())
247     {
248       Node next = this.elementAt(m_next);
249 
250       m_next++;
251 
252       return next;
253     }
254     else
255       return null;
256   }
257 
258   /**
259    *  Returns the previous node in the set and moves the position of the
260    * iterator backwards in the set.
261    * @return  The previous <code>Node</code> in the set being iterated over,
262    *   or<code>null</code> if there are no more members in that set.
263    * @throws DOMException
264    *    INVALID_STATE_ERR: Raised if this method is called after the
265    *   <code>detach</code> method was invoked.
266    * @throws RuntimeException thrown if this NodeSet is not of
267    * a cached type, and hence doesn't know what the previous node was.
268    */
269   public Node previousNode() throws DOMException
270   {
271 
272     if (!m_cacheNodes)
273       throw new RuntimeException(
274         XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_CANNOT_ITERATE, null)); //"This NodeSet can not iterate to a previous node!");
275 
276     if ((m_next - 1) > 0)
277     {
278       m_next--;
279 
280       return this.elementAt(m_next);
281     }
282     else
283       return null;
284   }
285 
286   /**
287    * Detaches the iterator from the set which it iterated over, releasing
288    * any computational resources and placing the iterator in the INVALID
289    * state. After<code>detach</code> has been invoked, calls to
290    * <code>nextNode</code> or<code>previousNode</code> will raise the
291    * exception INVALID_STATE_ERR.
292    * <p>
293    * This operation is a no-op in NodeSet, and will not cause
294    * INVALID_STATE_ERR to be raised by later operations.
295    * </p>
296    */
297   public void detach(){}
298 
299   /**
300    * Tells if this NodeSet is "fresh", in other words, if
301    * the first nextNode() that is called will return the
302    * first node in the set.
303    *
304    * @return true if nextNode() would return the first node in the set,
305    * false if it would return a later one.
306    */
307   public boolean isFresh()
308   {
309     return (m_next == 0);
310   }
311 
312   /**
313    * If an index is requested, NodeSet will call this method
314    * to run the iterator to the index.  By default this sets
315    * m_next to the index.  If the index argument is -1, this
316    * signals that the iterator should be run to the end.
317    *
318    * @param index Position to advance (or retreat) to, with
319    * 0 requesting the reset ("fresh") position and -1 (or indeed
320    * any out-of-bounds value) requesting the final position.
321    * @throws RuntimeException thrown if this NodeSet is not
322    * one of the types which supports indexing/counting.
323    */
324   public void runTo(int index)
325   {
326 
327     if (!m_cacheNodes)
328       throw new RuntimeException(
329         XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_CANNOT_INDEX, null)); //"This NodeSet can not do indexing or counting functions!");
330 
331     if ((index >= 0) && (m_next < m_firstFree))
332       m_next = index;
333     else
334       m_next = m_firstFree - 1;
335   }
336 
337   /**
338    * Returns the <code>index</code>th item in the collection. If
339    * <code>index</code> is greater than or equal to the number of nodes in
340    * the list, this returns <code>null</code>.
341    *
342    * TODO: What happens if index is out of range?
343    *
344    * @param index Index into the collection.
345    * @return The node at the <code>index</code>th position in the
346    *   <code>NodeList</code>, or <code>null</code> if that is not a valid
347    *   index.
348    */
349   public Node item(int index)
350   {
351 
352     runTo(index);
353 
354     return (Node) this.elementAt(index);
355   }
356 
357   /**
358    * The number of nodes in the list. The range of valid child node indices is
359    * 0 to <code>length-1</code> inclusive. Note that this operation requires
360    * finding all the matching nodes, which may defeat attempts to defer
361    * that work.
362    *
363    * @return integer indicating how many nodes are represented by this list.
364    */
365   public int getLength()
366   {
367 
368     runTo(-1);
369 
370     return this.size();
371   }
372 
373   /**
374    * Add a node to the NodeSet. Not all types of NodeSets support this
375    * operation
376    *
377    * @param n Node to be added
378    * @throws RuntimeException thrown if this NodeSet is not of
379    * a mutable type.
380    */
381   public void addNode(Node n)
382   {
383 
384     if (!m_mutable)
385       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
386 
387     this.addElement(n);
388   }
389 
390   /**
391    * Insert a node at a given position.
392    *
393    * @param n Node to be added
394    * @param pos Offset at which the node is to be inserted,
395    * with 0 being the first position.
396    * @throws RuntimeException thrown if this NodeSet is not of
397    * a mutable type.
398    */
399   public void insertNode(Node n, int pos)
400   {
401 
402     if (!m_mutable)
403       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
404 
405     insertElementAt(n, pos);
406   }
407 
408   /**
409    * Remove a node.
410    *
411    * @param n Node to be added
412    * @throws RuntimeException thrown if this NodeSet is not of
413    * a mutable type.
414    */
415   public void removeNode(Node n)
416   {
417 
418     if (!m_mutable)
419       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
420 
421     this.removeElement(n);
422   }
423 
424   /**
425    * Copy NodeList members into this nodelist, adding in
426    * document order.  If a node is null, don't add it.
427    *
428    * @param nodelist List of nodes which should now be referenced by
429    * this NodeSet.
430    * @throws RuntimeException thrown if this NodeSet is not of
431    * a mutable type.
432    */
433   public void addNodes(NodeList nodelist)
434   {
435 
436     if (!m_mutable)
437       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
438 
439     if (null != nodelist)  // defensive to fix a bug that Sanjiva reported.
440     {
441       int nChildren = nodelist.getLength();
442 
443       for (int i = 0; i < nChildren; i++)
444       {
445         Node obj = nodelist.item(i);
446 
447         if (null != obj)
448         {
449           addElement(obj);
450         }
451       }
452     }
453 
454     // checkDups();
455   }
456 
457   /**
458    * <p>Copy NodeList members into this nodelist, adding in
459    * document order.  Only genuine node references will be copied;
460    * nulls appearing in the source NodeSet will
461    * not be added to this one. </p>
462    *
463    * <p> In case you're wondering why this function is needed: NodeSet
464    * implements both NodeIterator and NodeList. If this method isn't
465    * provided, Java can't decide which of those to use when addNodes()
466    * is invoked. Providing the more-explicit match avoids that
467    * ambiguity.)</p>
468    *
469    * @param ns NodeSet whose members should be merged into this NodeSet.
470    * @throws RuntimeException thrown if this NodeSet is not of
471    * a mutable type.
472    */
473   public void addNodes(NodeSet ns)
474   {
475 
476     if (!m_mutable)
477       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
478 
479     addNodes((NodeIterator) ns);
480   }
481 
482   /**
483    * Copy NodeList members into this nodelist, adding in
484    * document order.  Null references are not added.
485    *
486    * @param iterator NodeIterator which yields the nodes to be added.
487    * @throws RuntimeException thrown if this NodeSet is not of
488    * a mutable type.
489    */
490   public void addNodes(NodeIterator iterator)
491   {
492 
493     if (!m_mutable)
494       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
495 
496     if (null != iterator)  // defensive to fix a bug that Sanjiva reported.
497     {
498       Node obj;
499 
500       while (null != (obj = iterator.nextNode()))
501       {
502         addElement(obj);
503       }
504     }
505 
506     // checkDups();
507   }
508 
509   /**
510    * Copy NodeList members into this nodelist, adding in
511    * document order.  If a node is null, don't add it.
512    *
513    * @param nodelist List of nodes to be added
514    * @param support The XPath runtime context.
515    * @throws RuntimeException thrown if this NodeSet is not of
516    * a mutable type.
517    */
518   public void addNodesInDocOrder(NodeList nodelist, XPathContext support)
519   {
520 
521     if (!m_mutable)
522       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
523 
524     int nChildren = nodelist.getLength();
525 
526     for (int i = 0; i < nChildren; i++)
527     {
528       Node node = nodelist.item(i);
529 
530       if (null != node)
531       {
532         addNodeInDocOrder(node, support);
533       }
534     }
535   }
536 
537   /**
538    * Copy NodeList members into this nodelist, adding in
539    * document order.  If a node is null, don't add it.
540    *
541    * @param iterator NodeIterator which yields the nodes to be added.
542    * @param support The XPath runtime context.
543    * @throws RuntimeException thrown if this NodeSet is not of
544    * a mutable type.
545    */
546   public void addNodesInDocOrder(NodeIterator iterator, XPathContext support)
547   {
548 
549     if (!m_mutable)
550       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
551 
552     Node node;
553 
554     while (null != (node = iterator.nextNode()))
555     {
556       addNodeInDocOrder(node, support);
557     }
558   }
559 
560   /**
561    * Add the node list to this node set in document order.
562    *
563    * @param start index.
564    * @param end index.
565    * @param testIndex index.
566    * @param nodelist The nodelist to add.
567    * @param support The XPath runtime context.
568    *
569    * @return false always.
570    * @throws RuntimeException thrown if this NodeSet is not of
571    * a mutable type.
572    */
573   private boolean addNodesInDocOrder(int start, int end, int testIndex,
574                                      NodeList nodelist, XPathContext support)
575   {
576 
577     if (!m_mutable)
578       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
579 
580     boolean foundit = false;
581     int i;
582     Node node = nodelist.item(testIndex);
583 
584     for (i = end; i >= start; i--)
585     {
586       Node child = (Node) elementAt(i);
587 
588       if (child == node)
589       {
590         i = -2;  // Duplicate, suppress insert
591 
592         break;
593       }
594 
595       if (!DOM2Helper.isNodeAfter(node, child))
596       {
597         insertElementAt(node, i + 1);
598 
599         testIndex--;
600 
601         if (testIndex > 0)
602         {
603           boolean foundPrev = addNodesInDocOrder(0, i, testIndex, nodelist,
604                                                  support);
605 
606           if (!foundPrev)
607           {
608             addNodesInDocOrder(i, size() - 1, testIndex, nodelist, support);
609           }
610         }
611 
612         break;
613       }
614     }
615 
616     if (i == -1)
617     {
618       insertElementAt(node, 0);
619     }
620 
621     return foundit;
622   }
623 
624   /**
625    * Add the node into a vector of nodes where it should occur in
626    * document order.
627    * @param node The node to be added.
628    * @param test true if we should test for doc order
629    * @param support The XPath runtime context.
630    * @return insertIndex.
631    * @throws RuntimeException thrown if this NodeSet is not of
632    * a mutable type.
633    */
634   public int addNodeInDocOrder(Node node, boolean test, XPathContext support)
635   {
636 
637     if (!m_mutable)
638       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
639 
640     int insertIndex = -1;
641 
642     if (test)
643     {
644 
645       // This needs to do a binary search, but a binary search
646       // is somewhat tough because the sequence test involves
647       // two nodes.
648       int size = size(), i;
649 
650       for (i = size - 1; i >= 0; i--)
651       {
652         Node child = (Node) elementAt(i);
653 
654         if (child == node)
655         {
656           i = -2;  // Duplicate, suppress insert
657 
658           break;
659         }
660 
661         if (!DOM2Helper.isNodeAfter(node, child))
662         {
663           break;
664         }
665       }
666 
667       if (i != -2)
668       {
669         insertIndex = i + 1;
670 
671         insertElementAt(node, insertIndex);
672       }
673     }
674     else
675     {
676       insertIndex = this.size();
677 
678       boolean foundit = false;
679 
680       for (int i = 0; i < insertIndex; i++)
681       {
682         if (this.item(i).equals(node))
683         {
684           foundit = true;
685 
686           break;
687         }
688       }
689 
690       if (!foundit)
691         addElement(node);
692     }
693 
694     // checkDups();
695     return insertIndex;
696   }  // end addNodeInDocOrder(Vector v, Object obj)
697 
698   /**
699    * Add the node into a vector of nodes where it should occur in
700    * document order.
701    * @param node The node to be added.
702    * @param support The XPath runtime context.
703    *
704    * @return The index where it was inserted.
705    * @throws RuntimeException thrown if this NodeSet is not of
706    * a mutable type.
707    */
708   public int addNodeInDocOrder(Node node, XPathContext support)
709   {
710 
711     if (!m_mutable)
712       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
713 
714     return addNodeInDocOrder(node, true, support);
715   }  // end addNodeInDocOrder(Vector v, Object obj)
716 
717 
718   /** If this node is being used as an iterator, the next index that nextNode()
719    *  will return.  */
720   transient protected int m_next = 0;
721 
722   /**
723    * Get the current position, which is one less than
724    * the next nextNode() call will retrieve.  i.e. if
725    * you call getCurrentPos() and the return is 0, the next
726    * fetch will take place at index 1.
727    *
728    * @return The the current position index.
729    */
730   public int getCurrentPos()
731   {
732     return m_next;
733   }
734 
735   /**
736    * Set the current position in the node set.
737    * @param i Must be a valid index.
738    * @throws RuntimeException thrown if this NodeSet is not of
739    * a cached type, and thus doesn't permit indexed access.
740    */
741   public void setCurrentPos(int i)
742   {
743 
744     if (!m_cacheNodes)
745       throw new RuntimeException(
746         XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_CANNOT_INDEX, null)); //"This NodeSet can not do indexing or counting functions!");
747 
748     m_next = i;
749   }
750 
751   /**
752    * Return the last fetched node.  Needed to support the UnionPathIterator.
753    *
754    * @return the last fetched node.
755    * @throws RuntimeException thrown if this NodeSet is not of
756    * a cached type, and thus doesn't permit indexed access.
757    */
758   public Node getCurrentNode()
759   {
760 
761     if (!m_cacheNodes)
762       throw new RuntimeException(
763         XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_CANNOT_INDEX, null)); //"This NodeSet can not do indexing or counting functions!");
764 
765     int saved = m_next;
766     Node n = (m_next < m_firstFree) ? elementAt(m_next) : null;
767     m_next = saved; // HACK: I think this is a bit of a hack.  -sb
768     return n;
769   }
770 
771   /** True if this list can be mutated.  */
772   transient protected boolean m_mutable = true;
773 
774   /** True if this list is cached.
775    *  @serial  */
776   transient protected boolean m_cacheNodes = true;
777 
778   /**
779    * Get whether or not this is a cached node set.
780    *
781    *
782    * @return True if this list is cached.
783    */
784   public boolean getShouldCacheNodes()
785   {
786     return m_cacheNodes;
787   }
788 
789   /**
790    * If setShouldCacheNodes(true) is called, then nodes will
791    * be cached.  They are not cached by default. This switch must
792    * be set before the first call to nextNode is made, to ensure
793    * that all nodes are cached.
794    *
795    * @param b true if this node set should be cached.
796    * @throws RuntimeException thrown if an attempt is made to
797    * request caching after we've already begun stepping through the
798    * nodes in this set.
799   */
800   public void setShouldCacheNodes(boolean b)
801   {
802 
803     if (!isFresh())
804       throw new RuntimeException(
805         XSLMessages.createXPATHMessage(XPATHErrorResources.ER_CANNOT_CALL_SETSHOULDCACHENODE, null)); //"Can not call setShouldCacheNodes after nextNode has been called!");
806 
807     m_cacheNodes = b;
808     m_mutable = true;
809   }
810 
811 
812   transient private int m_last = 0;
813 
814   public int getLast()
815   {
816     return m_last;
817   }
818 
819   public void setLast(int last)
820   {
821     m_last = last;
822   }
823 
824   /** Size of blocks to allocate.
825    *  @serial          */
826   private int m_blocksize;
827 
828   /** Array of nodes this points to.
829    *  @serial          */
830   Node m_map[];
831 
832   /** Number of nodes in this NodeVector.
833    *  @serial          */
834   protected int m_firstFree = 0;
835 
836   /** Size of the array this points to.
837    *  @serial           */
838   private int m_mapSize;  // lazy initialization
839 
840   /**
841    * Get a cloned LocPathIterator.
842    *
843    * @return A clone of this
844    *
845    * @throws CloneNotSupportedException
846    */
847   public Object clone() throws CloneNotSupportedException
848   {
849 
850     NodeSet clone = (NodeSet) super.clone();
851 
852     if ((null != this.m_map) && (this.m_map == clone.m_map))
853     {
854       clone.m_map = new Node[this.m_map.length];
855 
856       System.arraycopy(this.m_map, 0, clone.m_map, 0, this.m_map.length);
857     }
858 
859     return clone;
860   }
861 
862   /**
863    * Get the length of the list.
864    *
865    * @return Number of nodes in this NodeVector
866    */
867   public int size()
868   {
869     return m_firstFree;
870   }
871 
872   /**
873    * Append a Node onto the vector.
874    *
875    * @param value Node to add to the vector
876    */
877   public void addElement(Node value)
878   {
879     if (!m_mutable)
880       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
881 
882     if ((m_firstFree + 1) >= m_mapSize)
883     {
884       if (null == m_map)
885       {
886         m_map = new Node[m_blocksize];
887         m_mapSize = m_blocksize;
888       }
889       else
890       {
891         m_mapSize += m_blocksize;
892 
893         Node newMap[] = new Node[m_mapSize];
894 
895         System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
896 
897         m_map = newMap;
898       }
899     }
900 
901     m_map[m_firstFree] = value;
902 
903     m_firstFree++;
904   }
905 
906   /**
907    * Append a Node onto the vector.
908    *
909    * @param value Node to add to the vector
910    */
911   public final void push(Node value)
912   {
913 
914     int ff = m_firstFree;
915 
916     if ((ff + 1) >= m_mapSize)
917     {
918       if (null == m_map)
919       {
920         m_map = new Node[m_blocksize];
921         m_mapSize = m_blocksize;
922       }
923       else
924       {
925         m_mapSize += m_blocksize;
926 
927         Node newMap[] = new Node[m_mapSize];
928 
929         System.arraycopy(m_map, 0, newMap, 0, ff + 1);
930 
931         m_map = newMap;
932       }
933     }
934 
935     m_map[ff] = value;
936 
937     ff++;
938 
939     m_firstFree = ff;
940   }
941 
942   /**
943    * Pop a node from the tail of the vector and return the result.
944    *
945    * @return the node at the tail of the vector
946    */
947   public final Node pop()
948   {
949 
950     m_firstFree--;
951 
952     Node n = m_map[m_firstFree];
953 
954     m_map[m_firstFree] = null;
955 
956     return n;
957   }
958 
959   /**
960    * Pop a node from the tail of the vector and return the
961    * top of the stack after the pop.
962    *
963    * @return The top of the stack after it's been popped
964    */
965   public final Node popAndTop()
966   {
967 
968     m_firstFree--;
969 
970     m_map[m_firstFree] = null;
971 
972     return (m_firstFree == 0) ? null : m_map[m_firstFree - 1];
973   }
974 
975   /**
976    * Pop a node from the tail of the vector.
977    */
978   public final void popQuick()
979   {
980 
981     m_firstFree--;
982 
983     m_map[m_firstFree] = null;
984   }
985 
986   /**
987    * Return the node at the top of the stack without popping the stack.
988    * Special purpose method for TransformerImpl, pushElemTemplateElement.
989    * Performance critical.
990    *
991    * @return Node at the top of the stack or null if stack is empty.
992    */
993   public final Node peepOrNull()
994   {
995     return ((null != m_map) && (m_firstFree > 0))
996            ? m_map[m_firstFree - 1] : null;
997   }
998 
999   /**
1000    * Push a pair of nodes into the stack.
1001    * Special purpose method for TransformerImpl, pushElemTemplateElement.
1002    * Performance critical.
1003    *
1004    * @param v1 First node to add to vector
1005    * @param v2 Second node to add to vector
1006    */
1007   public final void pushPair(Node v1, Node v2)
1008   {
1009 
1010     if (null == m_map)
1011     {
1012       m_map = new Node[m_blocksize];
1013       m_mapSize = m_blocksize;
1014     }
1015     else
1016     {
1017       if ((m_firstFree + 2) >= m_mapSize)
1018       {
1019         m_mapSize += m_blocksize;
1020 
1021         Node newMap[] = new Node[m_mapSize];
1022 
1023         System.arraycopy(m_map, 0, newMap, 0, m_firstFree);
1024 
1025         m_map = newMap;
1026       }
1027     }
1028 
1029     m_map[m_firstFree] = v1;
1030     m_map[m_firstFree + 1] = v2;
1031     m_firstFree += 2;
1032   }
1033 
1034   /**
1035    * Pop a pair of nodes from the tail of the stack.
1036    * Special purpose method for TransformerImpl, pushElemTemplateElement.
1037    * Performance critical.
1038    */
1039   public final void popPair()
1040   {
1041 
1042     m_firstFree -= 2;
1043     m_map[m_firstFree] = null;
1044     m_map[m_firstFree + 1] = null;
1045   }
1046 
1047   /**
1048    * Set the tail of the stack to the given node.
1049    * Special purpose method for TransformerImpl, pushElemTemplateElement.
1050    * Performance critical.
1051    *
1052    * @param n Node to set at the tail of vector
1053    */
1054   public final void setTail(Node n)
1055   {
1056     m_map[m_firstFree - 1] = n;
1057   }
1058 
1059   /**
1060    * Set the given node one position from the tail.
1061    * Special purpose method for TransformerImpl, pushElemTemplateElement.
1062    * Performance critical.
1063    *
1064    * @param n Node to set
1065    */
1066   public final void setTailSub1(Node n)
1067   {
1068     m_map[m_firstFree - 2] = n;
1069   }
1070 
1071   /**
1072    * Return the node at the tail of the vector without popping
1073    * Special purpose method for TransformerImpl, pushElemTemplateElement.
1074    * Performance critical.
1075    *
1076    * @return Node at the tail of the vector
1077    */
1078   public final Node peepTail()
1079   {
1080     return m_map[m_firstFree - 1];
1081   }
1082 
1083   /**
1084    * Return the node one position from the tail without popping.
1085    * Special purpose method for TransformerImpl, pushElemTemplateElement.
1086    * Performance critical.
1087    *
1088    * @return Node one away from the tail
1089    */
1090   public final Node peepTailSub1()
1091   {
1092     return m_map[m_firstFree - 2];
1093   }
1094 
1095   /**
1096    * Inserts the specified node in this vector at the specified index.
1097    * Each component in this vector with an index greater or equal to
1098    * the specified index is shifted upward to have an index one greater
1099    * than the value it had previously.
1100    *
1101    * @param value Node to insert
1102    * @param at Position where to insert
1103    */
1104   public void insertElementAt(Node value, int at)
1105   {
1106     if (!m_mutable)
1107       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
1108 
1109     if (null == m_map)
1110     {
1111       m_map = new Node[m_blocksize];
1112       m_mapSize = m_blocksize;
1113     }
1114     else if ((m_firstFree + 1) >= m_mapSize)
1115     {
1116       m_mapSize += m_blocksize;
1117 
1118       Node newMap[] = new Node[m_mapSize];
1119 
1120       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
1121 
1122       m_map = newMap;
1123     }
1124 
1125     if (at <= (m_firstFree - 1))
1126     {
1127       System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at);
1128     }
1129 
1130     m_map[at] = value;
1131 
1132     m_firstFree++;
1133   }
1134 
1135   /**
1136    * Append the nodes to the list.
1137    *
1138    * @param nodes NodeVector to append to this list
1139    */
1140   public void appendNodes(NodeSet nodes)
1141   {
1142 
1143     int nNodes = nodes.size();
1144 
1145     if (null == m_map)
1146     {
1147       m_mapSize = nNodes + m_blocksize;
1148       m_map = new Node[m_mapSize];
1149     }
1150     else if ((m_firstFree + nNodes) >= m_mapSize)
1151     {
1152       m_mapSize += (nNodes + m_blocksize);
1153 
1154       Node newMap[] = new Node[m_mapSize];
1155 
1156       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + nNodes);
1157 
1158       m_map = newMap;
1159     }
1160 
1161     System.arraycopy(nodes.m_map, 0, m_map, m_firstFree, nNodes);
1162 
1163     m_firstFree += nNodes;
1164   }
1165 
1166   /**
1167    * Inserts the specified node in this vector at the specified index.
1168    * Each component in this vector with an index greater or equal to
1169    * the specified index is shifted upward to have an index one greater
1170    * than the value it had previously.
1171    */
1172   public void removeAllElements()
1173   {
1174 
1175     if (null == m_map)
1176       return;
1177 
1178     for (int i = 0; i < m_firstFree; i++)
1179     {
1180       m_map[i] = null;
1181     }
1182 
1183     m_firstFree = 0;
1184   }
1185 
1186   /**
1187    * Removes the first occurrence of the argument from this vector.
1188    * If the object is found in this vector, each component in the vector
1189    * with an index greater or equal to the object's index is shifted
1190    * downward to have an index one smaller than the value it had
1191    * previously.
1192    *
1193    * @param s Node to remove from the list
1194    *
1195    * @return True if the node was successfully removed
1196    */
1197   public boolean removeElement(Node s)
1198   {
1199     if (!m_mutable)
1200       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
1201 
1202     if (null == m_map)
1203       return false;
1204 
1205     for (int i = 0; i < m_firstFree; i++)
1206     {
1207       Node node = m_map[i];
1208 
1209       if ((null != node) && node.equals(s))
1210       {
1211         if (i < m_firstFree - 1)
1212           System.arraycopy(m_map, i + 1, m_map, i, m_firstFree - i - 1);
1213 
1214         m_firstFree--;
1215         m_map[m_firstFree] = null;
1216 
1217         return true;
1218       }
1219     }
1220 
1221     return false;
1222   }
1223 
1224   /**
1225    * Deletes the component at the specified index. Each component in
1226    * this vector with an index greater or equal to the specified
1227    * index is shifted downward to have an index one smaller than
1228    * the value it had previously.
1229    *
1230    * @param i Index of node to remove
1231    */
1232   public void removeElementAt(int i)
1233   {
1234 
1235     if (null == m_map)
1236       return;
1237 
1238     if (i >= m_firstFree)
1239       throw new ArrayIndexOutOfBoundsException(i + " >= " + m_firstFree);
1240     else if (i < 0)
1241       throw new ArrayIndexOutOfBoundsException(i);
1242 
1243     if (i < m_firstFree - 1)
1244       System.arraycopy(m_map, i + 1, m_map, i, m_firstFree - i - 1);
1245 
1246     m_firstFree--;
1247     m_map[m_firstFree] = null;
1248   }
1249 
1250   /**
1251    * Sets the component at the specified index of this vector to be the
1252    * specified object. The previous component at that position is discarded.
1253    *
1254    * The index must be a value greater than or equal to 0 and less
1255    * than the current size of the vector.
1256    *
1257    * @param node Node to set
1258    * @param index Index of where to set the node
1259    */
1260   public void setElementAt(Node node, int index)
1261   {
1262     if (!m_mutable)
1263       throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");
1264 
1265     if (null == m_map)
1266     {
1267       m_map = new Node[m_blocksize];
1268       m_mapSize = m_blocksize;
1269     }
1270 
1271     m_map[index] = node;
1272   }
1273 
1274   /**
1275    * Get the nth element.
1276    *
1277    * @param i Index of node to get
1278    *
1279    * @return Node at specified index
1280    */
1281   public Node elementAt(int i)
1282   {
1283 
1284     if (null == m_map)
1285       return null;
1286 
1287     return m_map[i];
1288   }
1289 
1290   /**
1291    * Tell if the table contains the given node.
1292    *
1293    * @param s Node to look for
1294    *
1295    * @return True if the given node was found.
1296    */
1297   public boolean contains(Node s)
1298   {
1299     runTo(-1);
1300 
1301     if (null == m_map)
1302       return false;
1303 
1304     for (int i = 0; i < m_firstFree; i++)
1305     {
1306       Node node = m_map[i];
1307 
1308       if ((null != node) && node.equals(s))
1309         return true;
1310     }
1311 
1312     return false;
1313   }
1314 
1315   /**
1316    * Searches for the first occurence of the given argument,
1317    * beginning the search at index, and testing for equality
1318    * using the equals method.
1319    *
1320    * @param elem Node to look for
1321    * @param index Index of where to start the search
1322    * @return the index of the first occurrence of the object
1323    * argument in this vector at position index or later in the
1324    * vector; returns -1 if the object is not found.
1325    */
1326   public int indexOf(Node elem, int index)
1327   {
1328     runTo(-1);
1329 
1330     if (null == m_map)
1331       return -1;
1332 
1333     for (int i = index; i < m_firstFree; i++)
1334     {
1335       Node node = m_map[i];
1336 
1337       if ((null != node) && node.equals(elem))
1338         return i;
1339     }
1340 
1341     return -1;
1342   }
1343 
1344   /**
1345    * Searches for the first occurence of the given argument,
1346    * beginning the search at index, and testing for equality
1347    * using the equals method.
1348    *
1349    * @param elem Node to look for
1350    * @return the index of the first occurrence of the object
1351    * argument in this vector at position index or later in the
1352    * vector; returns -1 if the object is not found.
1353    */
1354   public int indexOf(Node elem)
1355   {
1356     runTo(-1);
1357 
1358     if (null == m_map)
1359       return -1;
1360 
1361     for (int i = 0; i < m_firstFree; i++)
1362     {
1363       Node node = m_map[i];
1364 
1365       if ((null != node) && node.equals(elem))
1366         return i;
1367     }
1368 
1369     return -1;
1370   }
1371 
1372 }