1 /*
   2  * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
   3  * @LastModified: Oct 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.axes;
  23 
  24 import com.sun.org.apache.xml.internal.dtm.DTM;
  25 import com.sun.org.apache.xml.internal.dtm.DTMFilter;
  26 import com.sun.org.apache.xml.internal.dtm.DTMIterator;
  27 import com.sun.org.apache.xml.internal.dtm.DTMManager;
  28 import com.sun.org.apache.xml.internal.utils.NodeVector;
  29 import com.sun.org.apache.xml.internal.utils.QName;
  30 import com.sun.org.apache.xpath.internal.NodeSetDTM;
  31 import com.sun.org.apache.xpath.internal.XPathContext;
  32 import com.sun.org.apache.xpath.internal.objects.XObject;
  33 import java.util.List;
  34 
  35 /**
  36  * This class is the dynamic wrapper for a Xalan DTMIterator instance, and
  37  * provides random access capabilities.
  38  */
  39 public class NodeSequence extends XObject
  40   implements DTMIterator, Cloneable, PathComponent
  41 {
  42     static final long serialVersionUID = 3866261934726581044L;
  43   /** The index of the last node in the iteration. */
  44   protected int m_last = -1;
  45 
  46   /**
  47    * The index of the next node to be fetched.  Useful if this
  48    * is a cached iterator, and is being used as random access
  49    * NodeList.
  50    */
  51   protected int m_next = 0;
  52 
  53   /**
  54    * A cache of a list of nodes obtained from the iterator so far.
  55    * This list is appended to until the iterator is exhausted and
  56    * the cache is complete.
  57    * <p>
  58    * Multiple NodeSequence objects may share the same cache.
  59    */
  60   private IteratorCache m_cache;
  61 
  62   /**
  63    * If this iterator needs to cache nodes that are fetched, they
  64    * are stored in the Vector in the generic object.
  65    */
  66   protected NodeVector getVector() {
  67       NodeVector nv = (m_cache != null) ?  m_cache.getVector() : null;
  68       return nv;
  69   }
  70 
  71   /**
  72    * Get the cache (if any) of nodes obtained from
  73    * the iterator so far. Note that the cache keeps
  74    * growing until the iterator is walked to exhaustion,
  75    * at which point the cache is "complete".
  76    */
  77   private IteratorCache getCache() {
  78       return m_cache;
  79   }
  80 
  81   /**
  82    * Set the vector where nodes will be cached.
  83    */
  84   protected void SetVector(NodeVector v)
  85   {
  86         setObject(v);
  87   }
  88 
  89 
  90   /**
  91    * If the iterator needs to cache nodes as they are fetched,
  92    * then this method returns true.
  93    */
  94   public boolean hasCache()
  95   {
  96     final NodeVector nv = getVector();
  97         return (nv != null);
  98   }
  99 
 100   /**
 101    * If this NodeSequence has a cache, and that cache is
 102    * fully populated then this method returns true, otherwise
 103    * if there is no cache or it is not complete it returns false.
 104    */
 105   private boolean cacheComplete() {
 106       final boolean complete;
 107       if (m_cache != null) {
 108           complete = m_cache.isComplete();
 109       } else {
 110           complete = false;
 111       }
 112       return complete;
 113   }
 114 
 115   /**
 116    * If this NodeSequence has a cache, mark that it is complete.
 117    * This method should be called after the iterator is exhausted.
 118    */
 119   private void markCacheComplete() {
 120       NodeVector nv = getVector();
 121       if (nv != null) {
 122           m_cache.setCacheComplete(true);
 123       }
 124   }
 125 
 126 
 127   /**
 128    * The functional iterator that fetches nodes.
 129    */
 130   protected DTMIterator m_iter;
 131 
 132   /**
 133    * Set the functional iterator that fetches nodes.
 134    * @param iter The iterator that is to be contained.
 135    */
 136   public final void setIter(DTMIterator iter)
 137   {
 138         m_iter = iter;
 139   }
 140 
 141   /**
 142    * Get the functional iterator that fetches nodes.
 143    * @return The contained iterator.
 144    */
 145   public final DTMIterator getContainedIter()
 146   {
 147         return m_iter;
 148   }
 149 
 150   /**
 151    * The DTMManager to use if we're using a NodeVector only.
 152    * We may well want to do away with this, and store it in the NodeVector.
 153    */
 154   protected DTMManager m_dtmMgr;
 155 
 156   // ==== Constructors ====
 157 
 158   /**
 159    * Create a new NodeSequence from a (already cloned) iterator.
 160    *
 161    * @param iter Cloned (not static) DTMIterator.
 162    * @param context The initial context node.
 163    * @param xctxt The execution context.
 164    * @param shouldCacheNodes True if this sequence can random access.
 165    */
 166   private NodeSequence(DTMIterator iter, int context, XPathContext xctxt, boolean shouldCacheNodes)
 167   {
 168         setIter(iter);
 169         setRoot(context, xctxt);
 170         setShouldCacheNodes(shouldCacheNodes);
 171   }
 172 
 173   /**
 174    * Create a new NodeSequence from a (already cloned) iterator.
 175    *
 176    * @param nodeVector
 177    */
 178   public NodeSequence(Object nodeVector)
 179   {
 180         super(nodeVector);
 181     if (nodeVector instanceof NodeVector) {
 182         SetVector((NodeVector) nodeVector);
 183     }
 184         if(null != nodeVector)
 185         {
 186                 assertion(nodeVector instanceof NodeVector,
 187                         "Must have a NodeVector as the object for NodeSequence!");
 188                 if(nodeVector instanceof DTMIterator)
 189                 {
 190                         setIter((DTMIterator)nodeVector);
 191                         m_last = ((DTMIterator)nodeVector).getLength();
 192                 }
 193 
 194         }
 195   }
 196 
 197   /**
 198    * Construct an empty XNodeSet object.  This is used to create a mutable
 199    * nodeset to which random nodes may be added.
 200    */
 201   private NodeSequence(DTMManager dtmMgr)
 202   {
 203     super(new NodeVector());
 204     m_last = 0;
 205     m_dtmMgr = dtmMgr;
 206   }
 207 
 208 
 209   /**
 210    * Create a new NodeSequence in an invalid (null) state.
 211    */
 212   public NodeSequence()
 213   {
 214       return;
 215   }
 216 
 217 
 218   /**
 219    * @see DTMIterator#getDTM(int)
 220    */
 221   public DTM getDTM(int nodeHandle)
 222   {
 223         DTMManager mgr = getDTMManager();
 224         if(null != mgr)
 225         return getDTMManager().getDTM(nodeHandle);
 226     else
 227     {
 228         assertion(false, "Can not get a DTM Unless a DTMManager has been set!");
 229         return null;
 230     }
 231   }
 232 
 233   /**
 234    * @see DTMIterator#getDTMManager()
 235    */
 236   public DTMManager getDTMManager()
 237   {
 238     return m_dtmMgr;
 239   }
 240 
 241   /**
 242    * @see DTMIterator#getRoot()
 243    */
 244   public int getRoot()
 245   {
 246         if(null != m_iter)
 247         return m_iter.getRoot();
 248         else
 249         {
 250                 // NodeSetDTM will call this, and so it's not a good thing to throw
 251                 // an assertion here.
 252                 // assertion(false, "Can not get the root from a non-iterated NodeSequence!");
 253                 return DTM.NULL;
 254         }
 255   }
 256 
 257   /**
 258    * @see DTMIterator#setRoot(int, Object)
 259    */
 260   public void setRoot(int nodeHandle, Object environment)
 261   {
 262         // If root is DTM.NULL, then something's wrong with the context
 263         if (nodeHandle == DTM.NULL)
 264         {
 265             throw new RuntimeException("Unable to evaluate expression using " +
 266                     "this context");
 267         }
 268 
 269         if(null != m_iter)
 270         {
 271                 XPathContext xctxt = (XPathContext)environment;
 272                 m_dtmMgr = xctxt.getDTMManager();
 273                 m_iter.setRoot(nodeHandle, environment);
 274                 if(!m_iter.isDocOrdered())
 275                 {
 276                         if(!hasCache())
 277                                 setShouldCacheNodes(true);
 278                         runTo(-1);
 279                         m_next=0;
 280                 }
 281         }
 282         else
 283                 assertion(false, "Can not setRoot on a non-iterated NodeSequence!");
 284   }
 285 
 286   /**
 287    * @see DTMIterator#reset()
 288    */
 289   public void reset()
 290   {
 291         m_next = 0;
 292         // not resetting the iterator on purpose!!!
 293   }
 294 
 295   /**
 296    * @see DTMIterator#getWhatToShow()
 297    */
 298   public int getWhatToShow()
 299   {
 300     return hasCache() ? (DTMFilter.SHOW_ALL & ~DTMFilter.SHOW_ENTITY_REFERENCE)
 301         : m_iter.getWhatToShow();
 302   }
 303 
 304   /**
 305    * @see DTMIterator#getExpandEntityReferences()
 306    */
 307   public boolean getExpandEntityReferences()
 308   {
 309         if(null != m_iter)
 310                 return m_iter.getExpandEntityReferences();
 311         else
 312         return true;
 313   }
 314 
 315   /**
 316    * @see DTMIterator#nextNode()
 317    */
 318   public int nextNode()
 319   {
 320     // If the cache is on, and the node has already been found, then
 321     // just return from the list.
 322     NodeVector vec = getVector();
 323     if (null != vec)
 324     {
 325         // There is a cache
 326         if(m_next < vec.size())
 327         {
 328             // The node is in the cache, so just return it.
 329                         int next = vec.elementAt(m_next);
 330                 m_next++;
 331                 return next;
 332         }
 333         else if(cacheComplete() || (-1 != m_last) || (null == m_iter))
 334         {
 335                 m_next++;
 336                 return DTM.NULL;
 337         }
 338     }
 339 
 340   if (null == m_iter)
 341     return DTM.NULL;
 342 
 343         int next = m_iter.nextNode();
 344     if(DTM.NULL != next)
 345     {
 346         if(hasCache())
 347         {
 348                 if(m_iter.isDocOrdered())
 349             {
 350                         getVector().addElement(next);
 351                         m_next++;
 352                 }
 353                 else
 354                 {
 355                         int insertIndex = addNodeInDocOrder(next);
 356                         if(insertIndex >= 0)
 357                                 m_next++;
 358                 }
 359         }
 360         else
 361                 m_next++;
 362     }
 363     else
 364     {
 365         // We have exhausted the iterator, and if there is a cache
 366         // it must have all nodes in it by now, so let the cache
 367         // know that it is complete.
 368         markCacheComplete();
 369 
 370         m_last = m_next;
 371         m_next++;
 372     }
 373 
 374     return next;
 375   }
 376 
 377   /**
 378    * @see DTMIterator#previousNode()
 379    */
 380   public int previousNode()
 381   {
 382         if(hasCache())
 383         {
 384                 if(m_next <= 0)
 385                         return DTM.NULL;
 386                 else
 387                 {
 388                         m_next--;
 389                         return item(m_next);
 390                 }
 391         }
 392         else
 393         {
 394             int n = m_iter.previousNode();
 395             m_next = m_iter.getCurrentPos();
 396             return m_next;
 397         }
 398   }
 399 
 400   /**
 401    * @see DTMIterator#detach()
 402    */
 403   public void detach()
 404   {
 405         if(null != m_iter)
 406                 m_iter.detach();
 407         super.detach();
 408   }
 409 
 410   /**
 411    * Calling this with a value of false will cause the nodeset
 412    * to be cached.
 413    * @see DTMIterator#allowDetachToRelease(boolean)
 414    */
 415   public void allowDetachToRelease(boolean allowRelease)
 416   {
 417         if((false == allowRelease) && !hasCache())
 418         {
 419                 setShouldCacheNodes(true);
 420         }
 421 
 422         if(null != m_iter)
 423                 m_iter.allowDetachToRelease(allowRelease);
 424         super.allowDetachToRelease(allowRelease);
 425   }
 426 
 427   /**
 428    * @see DTMIterator#getCurrentNode()
 429    */
 430   public int getCurrentNode()
 431   {
 432         if(hasCache())
 433         {
 434                 int currentIndex = m_next-1;
 435                 NodeVector vec = getVector();
 436                 if((currentIndex >= 0) && (currentIndex < vec.size()))
 437                         return vec.elementAt(currentIndex);
 438                 else
 439                         return DTM.NULL;
 440         }
 441 
 442         if(null != m_iter)
 443         {
 444         return m_iter.getCurrentNode();
 445         }
 446         else
 447                 return DTM.NULL;
 448   }
 449 
 450   /**
 451    * @see DTMIterator#isFresh()
 452    */
 453   public boolean isFresh()
 454   {
 455     return (0 == m_next);
 456   }
 457 
 458   /**
 459    * @see DTMIterator#setShouldCacheNodes(boolean)
 460    */
 461   public void setShouldCacheNodes(boolean b)
 462   {
 463     if (b)
 464     {
 465       if(!hasCache())
 466       {
 467         SetVector(new NodeVector());
 468       }
 469 //        else
 470 //          getVector().RemoveAllNoClear();  // Is this good?
 471     }
 472     else
 473       SetVector(null);
 474   }
 475 
 476   /**
 477    * @see DTMIterator#isMutable()
 478    */
 479   public boolean isMutable()
 480   {
 481     return hasCache(); // though may be surprising if it also has an iterator!
 482   }
 483 
 484   /**
 485    * @see DTMIterator#getCurrentPos()
 486    */
 487   public int getCurrentPos()
 488   {
 489     return m_next;
 490   }
 491 
 492   /**
 493    * @see DTMIterator#runTo(int)
 494    */
 495   public void runTo(int index)
 496   {
 497     int n;
 498 
 499     if (-1 == index)
 500     {
 501       int pos = m_next;
 502       while (DTM.NULL != (n = nextNode()));
 503       m_next = pos;
 504     }
 505     else if(m_next == index)
 506     {
 507       return;
 508     }
 509     else if(hasCache() && index < getVector().size())
 510     {
 511       m_next = index;
 512     }
 513     else if((null == getVector()) && (index < m_next))
 514     {
 515       while ((m_next >= index) && DTM.NULL != (n = previousNode()));
 516     }
 517     else
 518     {
 519       while ((m_next < index) && DTM.NULL != (n = nextNode()));
 520     }
 521 
 522   }
 523 
 524   /**
 525    * @see DTMIterator#setCurrentPos(int)
 526    */
 527   public void setCurrentPos(int i)
 528   {
 529         runTo(i);
 530   }
 531 
 532   /**
 533    * @see DTMIterator#item(int)
 534    */
 535   public int item(int index)
 536   {
 537         setCurrentPos(index);
 538         int n = nextNode();
 539         m_next = index;
 540         return n;
 541   }
 542 
 543   /**
 544    * @see DTMIterator#setItem(int, int)
 545    */
 546   public void setItem(int node, int index)
 547   {
 548         NodeVector vec = getVector();
 549         if(null != vec)
 550         {
 551         int oldNode = vec.elementAt(index);
 552         if (oldNode != node && m_cache.useCount() > 1) {
 553             /* If we are going to set the node at the given index
 554              * to a different value, and the cache is shared
 555              * (has a use count greater than 1)
 556              * then make a copy of the cache and use it
 557              * so we don't overwrite the value for other
 558              * users of the cache.
 559              */
 560             IteratorCache newCache = new IteratorCache();
 561             final NodeVector nv;
 562             try {
 563                 nv = (NodeVector) vec.clone();
 564             } catch (CloneNotSupportedException e) {
 565                 // This should never happen
 566                 e.printStackTrace();
 567                 RuntimeException rte = new RuntimeException(e.getMessage());
 568                 throw rte;
 569             }
 570             newCache.setVector(nv);
 571             newCache.setCacheComplete(true);
 572             m_cache = newCache;
 573             vec = nv;
 574 
 575             // Keep our superclass informed of the current NodeVector
 576             super.setObject(nv);
 577 
 578             /* When we get to here the new cache has
 579              * a use count of 1 and when setting a
 580              * bunch of values on the same NodeSequence,
 581              * such as when sorting, we will keep setting
 582              * values in that same copy which has a use count of 1.
 583              */
 584         }
 585                 vec.setElementAt(node, index);
 586                 m_last = vec.size();
 587         }
 588         else
 589                 m_iter.setItem(node, index);
 590   }
 591 
 592   /**
 593    * @see DTMIterator#getLength()
 594    */
 595   public int getLength()
 596   {
 597     IteratorCache cache = getCache();
 598 
 599         if(cache != null)
 600         {
 601         // Nodes from the iterator are cached
 602         if (cache.isComplete()) {
 603             // All of the nodes from the iterator are cached
 604             // so just return the number of nodes in the cache
 605             NodeVector nv = cache.getVector();
 606             return nv.size();
 607         }
 608 
 609         // If this NodeSequence wraps a mutable nodeset, then
 610         // m_last will not reflect the size of the nodeset if
 611         // it has been mutated...
 612         if (m_iter instanceof NodeSetDTM)
 613         {
 614             return m_iter.getLength();
 615         }
 616 
 617                 if(-1 == m_last)
 618                 {
 619                         int pos = m_next;
 620                         runTo(-1);
 621                         m_next = pos;
 622                 }
 623             return m_last;
 624         }
 625         else
 626         {
 627                 return (-1 == m_last) ? (m_last = m_iter.getLength()) : m_last;
 628         }
 629   }
 630 
 631   /**
 632    * Note: Not a deep clone.
 633    * @see DTMIterator#cloneWithReset()
 634    */
 635   public DTMIterator cloneWithReset() throws CloneNotSupportedException
 636   {
 637         NodeSequence seq = (NodeSequence)super.clone();
 638     seq.m_next = 0;
 639     if (m_cache != null) {
 640         // In making this clone of an iterator we are making
 641         // another NodeSequence object it has a reference
 642         // to the same IteratorCache object as the original
 643         // so we need to remember that more than one
 644         // NodeSequence object shares the cache.
 645         m_cache.increaseUseCount();
 646     }
 647 
 648     return seq;
 649   }
 650 
 651   /**
 652    * Get a clone of this iterator, but don't reset the iteration in the
 653    * process, so that it may be used from the current position.
 654    * Note: Not a deep clone.
 655    *
 656    * @return A clone of this object.
 657    *
 658    * @throws CloneNotSupportedException
 659    */
 660   public Object clone() throws CloneNotSupportedException
 661   {
 662           NodeSequence clone = (NodeSequence) super.clone();
 663           if (null != m_iter) clone.m_iter = (DTMIterator) m_iter.clone();
 664           if (m_cache != null) {
 665               // In making this clone of an iterator we are making
 666               // another NodeSequence object it has a reference
 667               // to the same IteratorCache object as the original
 668               // so we need to remember that more than one
 669               // NodeSequence object shares the cache.
 670               m_cache.increaseUseCount();
 671           }
 672 
 673           return clone;
 674   }
 675 
 676 
 677   /**
 678    * @see DTMIterator#isDocOrdered()
 679    */
 680   public boolean isDocOrdered()
 681   {
 682         if(null != m_iter)
 683                 return m_iter.isDocOrdered();
 684         else
 685         return true; // can't be sure?
 686   }
 687 
 688   /**
 689    * @see DTMIterator#getAxis()
 690    */
 691   public int getAxis()
 692   {
 693         if(null != m_iter)
 694         return m_iter.getAxis();
 695     else
 696     {
 697         assertion(false, "Can not getAxis from a non-iterated node sequence!");
 698         return 0;
 699     }
 700   }
 701 
 702   /**
 703    * @see PathComponent#getAnalysisBits()
 704    */
 705   public int getAnalysisBits()
 706   {
 707         if((null != m_iter) && (m_iter instanceof PathComponent))
 708         return ((PathComponent)m_iter).getAnalysisBits();
 709     else
 710         return 0;
 711   }
 712 
 713   /**
 714    * @see org.apache.xpath.Expression#fixupVariables(Vector, int)
 715    */
 716   public void fixupVariables(List<QName> vars, int globalsSize)
 717   {
 718         super.fixupVariables(vars, globalsSize);
 719   }
 720 
 721   /**
 722    * Add the node into a vector of nodes where it should occur in
 723    * document order.
 724    * @param node The node to be added.
 725    * @return insertIndex.
 726    * @throws RuntimeException thrown if this NodeSetDTM is not of
 727    * a mutable type.
 728    */
 729    protected int addNodeInDocOrder(int node)
 730    {
 731       assertion(hasCache(), "addNodeInDocOrder must be done on a mutable sequence!");
 732 
 733       int insertIndex = -1;
 734 
 735       NodeVector vec = getVector();
 736 
 737       // This needs to do a binary search, but a binary search
 738       // is somewhat tough because the sequence test involves
 739       // two nodes.
 740       int size = vec.size(), i;
 741 
 742       for (i = size - 1; i >= 0; i--)
 743       {
 744         int child = vec.elementAt(i);
 745 
 746         if (child == node)
 747         {
 748           i = -2; // Duplicate, suppress insert
 749 
 750           break;
 751         }
 752 
 753         DTM dtm = m_dtmMgr.getDTM(node);
 754         if (!dtm.isNodeAfter(node, child))
 755         {
 756           break;
 757         }
 758       }
 759 
 760       if (i != -2)
 761       {
 762         insertIndex = i + 1;
 763 
 764         vec.insertElementAt(node, insertIndex);
 765       }
 766 
 767       // checkDups();
 768       return insertIndex;
 769     } // end addNodeInDocOrder(List<QName> v, Object obj)
 770 
 771    /**
 772     * It used to be that many locations in the code simply
 773     * did an assignment to this.m_obj directly, rather than
 774     * calling the setObject(Object) method. The problem is
 775     * that our super-class would be updated on what the
 776     * cache associated with this NodeSequence, but
 777     * we wouldn't know ourselves.
 778     * <p>
 779     * All setting of m_obj is done through setObject() now,
 780     * and this method over-rides the super-class method.
 781     * So now we are in the loop have an opportunity
 782     * to update some caching information.
 783     *
 784     */
 785    protected void setObject(Object obj) {
 786        if (obj instanceof NodeVector) {
 787            // Keep our superclass informed of the current NodeVector
 788            // ... if we don't the smoketest fails (don't know why).
 789            super.setObject(obj);
 790 
 791            // A copy of the code of what SetVector() would do.
 792            NodeVector v = (NodeVector)obj;
 793            if (m_cache != null) {
 794                m_cache.setVector(v);
 795            } else if (v!=null) {
 796                m_cache = new IteratorCache();
 797                m_cache.setVector(v);
 798            }
 799        } else if (obj instanceof IteratorCache) {
 800            IteratorCache cache = (IteratorCache) obj;
 801            m_cache = cache;
 802            m_cache.increaseUseCount();
 803 
 804            // Keep our superclass informed of the current NodeVector
 805            super.setObject(cache.getVector());
 806        } else {
 807            super.setObject(obj);
 808        }
 809 
 810    }
 811 
 812    /**
 813     * Each NodeSequence object has an iterator which is "walked".
 814     * As an iterator is walked one obtains nodes from it.
 815     * As those nodes are obtained they may be cached, making
 816     * the next walking of a copy or clone of the iterator faster.
 817     * This field (m_cache) is a reference to such a cache,
 818     * which is populated as the iterator is walked.
 819     * <p>
 820     * Note that multiple NodeSequence objects may hold a
 821     * reference to the same cache, and also
 822     * (and this is important) the same iterator.
 823     * The iterator and its cache may be shared among
 824     * many NodeSequence objects.
 825     * <p>
 826     * If one of the NodeSequence objects walks ahead
 827     * of the others it fills in the cache.
 828     * As the others NodeSequence objects catch up they
 829     * get their values from
 830     * the cache rather than the iterator itself, so
 831     * the iterator is only ever walked once and everyone
 832     * benefits from the cache.
 833     * <p>
 834     * At some point the cache may be
 835     * complete due to walking to the end of one of
 836     * the copies of the iterator, and the cache is
 837     * then marked as "complete".
 838     * and the cache will have no more nodes added to it.
 839     * <p>
 840     * Its use-count is the number of NodeSequence objects that use it.
 841     */
 842    private final static class IteratorCache {
 843        /**
 844         * A list of nodes already obtained from the iterator.
 845         * As the iterator is walked the nodes obtained from
 846         * it are appended to this list.
 847         * <p>
 848         * Both an iterator and its corresponding cache can
 849         * be shared by multiple NodeSequence objects.
 850         * <p>
 851         * For example, consider three NodeSequence objects
 852         * ns1, ns2 and ns3 doing such sharing, and the
 853         * nodes to be obtaind from the iterator being
 854         * the sequence { 33, 11, 44, 22, 55 }.
 855         * <p>
 856         * If ns3.nextNode() is called 3 times the the
 857         * underlying iterator will have walked through
 858         * 33, 11, 55 and these three nodes will have been put
 859         * in the cache.
 860         * <p>
 861         * If ns2.nextNode() is called 2 times it will return
 862         * 33 and 11 from the cache, leaving the iterator alone.
 863         * <p>
 864         * If ns1.nextNode() is called 6 times it will return
 865         * 33 and 11 from the cache, then get 44, 22, 55 from
 866         * the iterator, and appending 44, 22, 55 to the cache.
 867         * On the sixth call it is found that the iterator is
 868         * exhausted and the cache is marked complete.
 869         * <p>
 870         * Should ns2 or ns3 have nextNode() called they will
 871         * know that the cache is complete, and they will
 872         * obtain all subsequent nodes from the cache.
 873         * <p>
 874         * Note that the underlying iterator, though shared
 875         * is only ever walked once.
 876         */
 877         private NodeVector m_vec2;
 878 
 879         /**
 880          * true if the associated iterator is exhausted and
 881          * all nodes obtained from it are in the cache.
 882          */
 883         private boolean m_isComplete2;
 884 
 885         private int m_useCount2;
 886 
 887         IteratorCache() {
 888             m_vec2 = null;
 889             m_isComplete2 = false;
 890             m_useCount2 = 1;
 891             return;
 892         }
 893 
 894         /**
 895          * Returns count of how many NodeSequence objects share this
 896          * IteratorCache object.
 897          */
 898         private int useCount() {
 899             return m_useCount2;
 900         }
 901 
 902         /**
 903          * This method is called when yet another
 904          * NodeSequence object uses, or shares
 905          * this same cache.
 906          *
 907          */
 908         private void increaseUseCount() {
 909             if (m_vec2 != null)
 910                 m_useCount2++;
 911 
 912         }
 913 
 914         /**
 915          * Sets the NodeVector that holds the
 916          * growing list of nodes as they are appended
 917          * to the cached list.
 918          */
 919         private void setVector(NodeVector nv) {
 920             m_vec2 = nv;
 921             m_useCount2 = 1;
 922         }
 923 
 924         /**
 925          * Get the cached list of nodes obtained from
 926          * the iterator so far.
 927          */
 928         private NodeVector getVector() {
 929             return m_vec2;
 930         }
 931 
 932         /**
 933          * Call this method with 'true' if the
 934          * iterator is exhausted and the cached list
 935          * is complete, or no longer growing.
 936          */
 937         private void setCacheComplete(boolean b) {
 938             m_isComplete2 = b;
 939 
 940         }
 941 
 942         /**
 943          * Returns true if no cache is complete
 944          * and immutable.
 945          */
 946         private boolean isComplete() {
 947             return m_isComplete2;
 948         }
 949     }
 950 
 951     /**
 952      * Get the cached list of nodes appended with
 953      * values obtained from the iterator as
 954      * a NodeSequence is walked when its
 955      * nextNode() method is called.
 956      */
 957     protected IteratorCache getIteratorCache() {
 958         return m_cache;
 959     }
 960 }