1 /*
   2  * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.

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