1 /*
2 * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
3 * @LastModified: Nov 2017
4 */
5 /*
6 * Licensed to the Apache Software Foundation (ASF) under one or more
7 * contributor license agreements. See the NOTICE file distributed with
8 * this work for additional information regarding copyright ownership.
9 * The ASF licenses this file to You under the Apache License, Version 2.0
10 * (the "License"); you may not use this file except in compliance with
11 * the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 */
21
22 package com.sun.org.apache.xpath.internal;
23
24 import com.sun.org.apache.xalan.internal.res.XSLMessages;
25 import com.sun.org.apache.xml.internal.utils.DOM2Helper;
26 import com.sun.org.apache.xpath.internal.axes.ContextNodeList;
27 import com.sun.org.apache.xpath.internal.res.XPATHErrorResources;
28
29 import org.w3c.dom.DOMException;
30 import org.w3c.dom.Node;
31 import org.w3c.dom.NodeList;
32 import org.w3c.dom.traversal.NodeFilter;
33 import org.w3c.dom.traversal.NodeIterator;
34
35
36 /**
37 * <p>The NodeSet class can act as either a NodeVector,
38 * NodeList, or NodeIterator. However, in order for it to
39 * act as a NodeVector or NodeList, it's required that
40 * setShouldCacheNodes(true) be called before the first
41 * nextNode() is called, in order that nodes can be added
42 * as they are fetched. Derived classes that implement iterators
43 * must override runTo(int index), in order that they may
44 * run the iteration to the given index. </p>
45 *
46 * <p>Note that we directly implement the DOM's NodeIterator
47 * interface. We do not emulate all the behavior of the
48 * standard NodeIterator. In particular, we do not guarantee
49 * to present a "live view" of the document ... but in XSLT,
50 * the source document should never be mutated, so this should
51 * never be an issue.</p>
52 *
53 * <p>Thought: Should NodeSet really implement NodeList and NodeIterator,
54 * or should there be specific subclasses of it which do so? The
55 * advantage of doing it all here is that all NodeSets will respond
56 * to the same calls; the disadvantage is that some of them may return
57 * less-than-enlightening results when you do so.</p>
58 * @xsl.usage advanced
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 }