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 }