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