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