android-platform-libcore/luni/src/main/java/org/apache/xpath/axes/NodeSequence.java - nest-cam/4320010/android-platform-libcore - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements. See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership. The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the  "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 /*
  * $Id: NodeSequence.java 469367 2006-10-31 04:41:08Z minchau $
  */
 package org.apache.xpath.axes;

 import java.util.Vector;

 import org.apache.xml.dtm.DTM;
 import org.apache.xml.dtm.DTMFilter;
 import org.apache.xml.dtm.DTMIterator;
 import org.apache.xml.dtm.DTMManager;
 import org.apache.xml.utils.NodeVector;
 import org.apache.xpath.NodeSetDTM;
 import org.apache.xpath.XPathContext;
 import org.apache.xpath.objects.XObject;

 /**
  * This class is the dynamic wrapper for a Xalan DTMIterator instance, and
  * provides random access capabilities.
  */
 public class NodeSequence extends XObject
   implements DTMIterator, Cloneable, PathComponent
 {
     static final long serialVersionUID = 3866261934726581044L;
   /** The index of the last node in the iteration. */
   protected int m_last = -1;

   /**
    * The index of the next node to be fetched.  Useful if this
    * is a cached iterator, and is being used as random access
    * NodeList.
    */
   protected int m_next = 0;

   /**
    * A cache of a list of nodes obtained from the iterator so far.
    * This list is appended to until the iterator is exhausted and
    * the cache is complete.
    * <p>
    * Multiple NodeSequence objects may share the same cache.
    */
   private IteratorCache m_cache;

   /**
    * If this iterator needs to cache nodes that are fetched, they
    * are stored in the Vector in the generic object.
    */
   protected NodeVector getVector() {
       NodeVector nv = (m_cache != null) ?  m_cache.getVector() : null;
       return nv;
   }

   /**
    * Get the cache (if any) of nodes obtained from
    * the iterator so far. Note that the cache keeps
    * growing until the iterator is walked to exhaustion,
    * at which point the cache is "complete".
    */
   private IteratorCache getCache() {
       return m_cache;
   }

   /**
    * Set the vector where nodes will be cached.
    */
   protected void SetVector(NodeVector v)
   {
   	setObject(v);
   }


   /**
    * If the iterator needs to cache nodes as they are fetched,
    * then this method returns true.
    */
   public boolean hasCache()
   {
     final NodeVector nv = getVector();
   	return (nv != null);
   }

   /**
    * If this NodeSequence has a cache, and that cache is
    * fully populated then this method returns true, otherwise
    * if there is no cache or it is not complete it returns false.
    */
   private boolean cacheComplete() {
       final boolean complete;
       if (m_cache != null) {
           complete = m_cache.isComplete();
       } else {
           complete = false;
       }
       return complete;
   }

   /**
    * If this NodeSequence has a cache, mark that it is complete.
    * This method should be called after the iterator is exhausted.
    */
   private void markCacheComplete() {
       NodeVector nv = getVector();
       if (nv != null) {
           m_cache.setCacheComplete(true);
       }
   }


   /**
    * The functional iterator that fetches nodes.
    */
   protected DTMIterator m_iter;

   /**
    * Set the functional iterator that fetches nodes.
    * @param iter The iterator that is to be contained.
    */
   public final void setIter(DTMIterator iter)
   {
   	m_iter = iter;
   }

   /**
    * Get the functional iterator that fetches nodes.
    * @return The contained iterator.
    */
   public final DTMIterator getContainedIter()
   {
   	return m_iter;
   }

   /**
    * The DTMManager to use if we're using a NodeVector only.
    * We may well want to do away with this, and store it in the NodeVector.
    */
   protected DTMManager m_dtmMgr;

   // ==== Constructors ====

   /**
    * Create a new NodeSequence from a (already cloned) iterator.
    *
    * @param iter Cloned (not static) DTMIterator.
    * @param context The initial context node.
    * @param xctxt The execution context.
    * @param shouldCacheNodes True if this sequence can random access.
    */
   private NodeSequence(DTMIterator iter, int context, XPathContext xctxt, boolean shouldCacheNodes)
   {
   	setIter(iter);
   	setRoot(context, xctxt);
   	setShouldCacheNodes(shouldCacheNodes);
   }

   /**
    * Create a new NodeSequence from a (already cloned) iterator.
    *
    * @param nodeVector
    */
   public NodeSequence(Object nodeVector)
   {
   	super(nodeVector);
     if (nodeVector instanceof NodeVector) {
         SetVector((NodeVector) nodeVector);
     }
   	if(null != nodeVector)
   	{
   		assertion(nodeVector instanceof NodeVector,
   			"Must have a NodeVector as the object for NodeSequence!");
   		if(nodeVector instanceof DTMIterator)
   		{
   			setIter((DTMIterator)nodeVector);
   			m_last = ((DTMIterator)nodeVector).getLength();
   		}

   	}
   }

   /**
    * Construct an empty XNodeSet object.  This is used to create a mutable
    * nodeset to which random nodes may be added.
    */
   private NodeSequence(DTMManager dtmMgr)
   {
     super(new NodeVector());
     m_last = 0;
     m_dtmMgr = dtmMgr;
   }


   /**
    * Create a new NodeSequence in an invalid (null) state.
    */
   public NodeSequence()
   {
       return;
   }


   /**
    * @see DTMIterator#getDTM(int)
    */
   public DTM getDTM(int nodeHandle)
   {
   	DTMManager mgr = getDTMManager();
   	if(null != mgr)
     	return getDTMManager().getDTM(nodeHandle);
     else
     {
     	assertion(false, "Can not get a DTM Unless a DTMManager has been set!");
     	return null;
     }
   }

   /**
    * @see DTMIterator#getDTMManager()
    */
   public DTMManager getDTMManager()
   {
     return m_dtmMgr;
   }

   /**
    * @see DTMIterator#getRoot()
    */
   public int getRoot()
   {
   	if(null != m_iter)
     	return m_iter.getRoot();
   	else
   	{
   		// NodeSetDTM will call this, and so it's not a good thing to throw
   		// an assertion here.
   		// assertion(false, "Can not get the root from a non-iterated NodeSequence!");
   		return DTM.NULL;
   	}
   }

   /**
    * @see DTMIterator#setRoot(int, Object)
    */
   public void setRoot(int nodeHandle, Object environment)
   {
   	if(null != m_iter)
   	{
   		XPathContext xctxt = (XPathContext)environment;
   		m_dtmMgr = xctxt.getDTMManager();
   		m_iter.setRoot(nodeHandle, environment);
   		if(!m_iter.isDocOrdered())
   		{
   			if(!hasCache())
   				setShouldCacheNodes(true);
   			runTo(-1);
   			m_next=0;
   		}
   	}
   	else
   		assertion(false, "Can not setRoot on a non-iterated NodeSequence!");
   }

   /**
    * @see DTMIterator#reset()
    */
   public void reset()
   {
   	m_next = 0;
   	// not resetting the iterator on purpose!!!
   }

   /**
    * @see DTMIterator#getWhatToShow()
    */
   public int getWhatToShow()
   {
     return hasCache() ? (DTMFilter.SHOW_ALL & ~DTMFilter.SHOW_ENTITY_REFERENCE)
     	: m_iter.getWhatToShow();
   }

   /**
    * @see DTMIterator#getExpandEntityReferences()
    */
   public boolean getExpandEntityReferences()
   {
   	if(null != m_iter)
   		return m_iter.getExpandEntityReferences();
   	else
     	return true;
   }

   /**
    * @see DTMIterator#nextNode()
    */
   public int nextNode()
   {
     // If the cache is on, and the node has already been found, then
     // just return from the list.
     NodeVector vec = getVector();
     if (null != vec)
     {
         // There is a cache
     	if(m_next < vec.size())
     	{
             // The node is in the cache, so just return it.
 			int next = vec.elementAt(m_next);
 	    	m_next++;
 	    	return next;
     	}
     	else if(cacheComplete() || (-1 != m_last) || (null == m_iter))
     	{
     		m_next++;
     		return DTM.NULL;
     	}
     }

   if (null == m_iter)
     return DTM.NULL;

  	int next = m_iter.nextNode();
     if(DTM.NULL != next)
     {
     	if(hasCache())
     	{
     		if(m_iter.isDocOrdered())
     	    {
     			getVector().addElement(next);
     			m_next++;
     		}
     		else
     		{
     			int insertIndex = addNodeInDocOrder(next);
     			if(insertIndex >= 0)
     				m_next++;
     		}
     	}
     	else
     		m_next++;
     }
     else
     {
         // We have exhausted the iterator, and if there is a cache
         // it must have all nodes in it by now, so let the cache
         // know that it is complete.
         markCacheComplete();

     	m_last = m_next;
     	m_next++;
     }

     return next;
   }

   /**
    * @see DTMIterator#previousNode()
    */
   public int previousNode()
   {
   	if(hasCache())
   	{
   		if(m_next <= 0)
   			return DTM.NULL;
   		else
   		{
   			m_next--;
   			return item(m_next);
   		}
   	}
   	else
   	{
 	    int n = m_iter.previousNode();
 	    m_next = m_iter.getCurrentPos();
 	    return m_next;
   	}
   }

   /**
    * @see DTMIterator#detach()
    */
   public void detach()
   {
   	if(null != m_iter)
   		m_iter.detach();
   	super.detach();
   }

   /**
    * Calling this with a value of false will cause the nodeset
    * to be cached.
    * @see DTMIterator#allowDetachToRelease(boolean)
    */
   public void allowDetachToRelease(boolean allowRelease)
   {
   	if((false == allowRelease) && !hasCache())
   	{
   		setShouldCacheNodes(true);
   	}

   	if(null != m_iter)
   		m_iter.allowDetachToRelease(allowRelease);
   	super.allowDetachToRelease(allowRelease);
   }

   /**
    * @see DTMIterator#getCurrentNode()
    */
   public int getCurrentNode()
   {
   	if(hasCache())
   	{
   		int currentIndex = m_next-1;
   		NodeVector vec = getVector();
   		if((currentIndex >= 0) && (currentIndex < vec.size()))
   			return vec.elementAt(currentIndex);
   		else
   			return DTM.NULL;
   	}

   	if(null != m_iter)
   	{
     	return m_iter.getCurrentNode();
   	}
   	else
   		return DTM.NULL;
   }

   /**
    * @see DTMIterator#isFresh()
    */
   public boolean isFresh()
   {
     return (0 == m_next);
   }

   /**
    * @see DTMIterator#setShouldCacheNodes(boolean)
    */
   public void setShouldCacheNodes(boolean b)
   {
     if (b)
     {
       if(!hasCache())
       {
         SetVector(new NodeVector());
       }
 //	  else
 //	    getVector().RemoveAllNoClear();  // Is this good?
     }
     else
       SetVector(null);
   }

   /**
    * @see DTMIterator#isMutable()
    */
   public boolean isMutable()
   {
     return hasCache(); // though may be surprising if it also has an iterator!
   }

   /**
    * @see DTMIterator#getCurrentPos()
    */
   public int getCurrentPos()
   {
     return m_next;
   }

   /**
    * @see DTMIterator#runTo(int)
    */
   public void runTo(int index)
   {
     int n;

     if (-1 == index)
     {
       int pos = m_next;
       while (DTM.NULL != (n = nextNode()));
       m_next = pos;
     }
     else if(m_next == index)
     {
       return;
     }
     else if(hasCache() && m_next < getVector().size())
     {
       m_next = index;
     }
     else if((null == getVector()) && (index < m_next))
     {
       while ((m_next >= index) && DTM.NULL != (n = previousNode()));
     }
     else
     {
       while ((m_next < index) && DTM.NULL != (n = nextNode()));
     }

   }

   /**
    * @see DTMIterator#setCurrentPos(int)
    */
   public void setCurrentPos(int i)
   {
   	runTo(i);
   }

   /**
    * @see DTMIterator#item(int)
    */
   public int item(int index)
   {
   	setCurrentPos(index);
   	int n = nextNode();
   	m_next = index;
   	return n;
   }

   /**
    * @see DTMIterator#setItem(int, int)
    */
   public void setItem(int node, int index)
   {
   	NodeVector vec = getVector();
   	if(null != vec)
   	{
         int oldNode = vec.elementAt(index);
         if (oldNode != node && m_cache.useCount() > 1) {
             /* If we are going to set the node at the given index
              * to a different value, and the cache is shared
              * (has a use count greater than 1)
              * then make a copy of the cache and use it
              * so we don't overwrite the value for other
              * users of the cache.
              */
             IteratorCache newCache = new IteratorCache();
             final NodeVector nv;
             try {
                 nv = (NodeVector) vec.clone();
             } catch (CloneNotSupportedException e) {
                 // This should never happen
                 e.printStackTrace();
                 RuntimeException rte = new RuntimeException(e.getMessage());
                 throw rte;
             }
             newCache.setVector(nv);
             newCache.setCacheComplete(true);
             m_cache = newCache;
             vec = nv;

             // Keep our superclass informed of the current NodeVector
             super.setObject(nv);

             /* When we get to here the new cache has
              * a use count of 1 and when setting a
              * bunch of values on the same NodeSequence,
              * such as when sorting, we will keep setting
              * values in that same copy which has a use count of 1.
              */
         }
   		vec.setElementAt(node, index);
   		m_last = vec.size();
   	}
   	else
   		m_iter.setItem(node, index);
   }

   /**
    * @see DTMIterator#getLength()
    */
   public int getLength()
   {
     IteratorCache cache = getCache();

   	if(cache != null)
   	{
         // Nodes from the iterator are cached
         if (cache.isComplete()) {
             // All of the nodes from the iterator are cached
             // so just return the number of nodes in the cache
             NodeVector nv = cache.getVector();
             return nv.size();
         }

         // If this NodeSequence wraps a mutable nodeset, then
         // m_last will not reflect the size of the nodeset if
         // it has been mutated...
         if (m_iter instanceof NodeSetDTM)
         {
             return m_iter.getLength();
         }

 	  	if(-1 == m_last)
 	  	{
 	  		int pos = m_next;
 	  		runTo(-1);
 	  		m_next = pos;
 	  	}
 	    return m_last;
   	}
   	else
   	{
   		return (-1 == m_last) ? (m_last = m_iter.getLength()) : m_last;
   	}
   }

   /**
    * Note: Not a deep clone.
    * @see DTMIterator#cloneWithReset()
    */
   public DTMIterator cloneWithReset() throws CloneNotSupportedException
   {
   	NodeSequence seq = (NodeSequence)super.clone();
     seq.m_next = 0;
     if (m_cache != null) {
         // In making this clone of an iterator we are making
         // another NodeSequence object it has a reference
         // to the same IteratorCache object as the original
         // so we need to remember that more than one
         // NodeSequence object shares the cache.
         m_cache.increaseUseCount();
     }

     return seq;
   }

   /**
    * Get a clone of this iterator, but don't reset the iteration in the
    * process, so that it may be used from the current position.
    * Note: Not a deep clone.
    *
    * @return A clone of this object.
    *
    * @throws CloneNotSupportedException
    */
   public Object clone() throws CloneNotSupportedException
   {
           NodeSequence clone = (NodeSequence) super.clone();
           if (null != m_iter) clone.m_iter = (DTMIterator) m_iter.clone();
           if (m_cache != null) {
               // In making this clone of an iterator we are making
               // another NodeSequence object it has a reference
               // to the same IteratorCache object as the original
               // so we need to remember that more than one
               // NodeSequence object shares the cache.
               m_cache.increaseUseCount();
           }

           return clone;
   }


   /**
    * @see DTMIterator#isDocOrdered()
    */
   public boolean isDocOrdered()
   {
   	if(null != m_iter)
   		return m_iter.isDocOrdered();
   	else
     	return true; // can't be sure?
   }

   /**
    * @see DTMIterator#getAxis()
    */
   public int getAxis()
   {
   	if(null != m_iter)
     	return m_iter.getAxis();
     else
     {
     	assertion(false, "Can not getAxis from a non-iterated node sequence!");
     	return 0;
     }
   }

   /**
    * @see PathComponent#getAnalysisBits()
    */
   public int getAnalysisBits()
   {
   	if((null != m_iter) && (m_iter instanceof PathComponent))
     	return ((PathComponent)m_iter).getAnalysisBits();
     else
     	return 0;
   }

   /**
    * @see org.apache.xpath.Expression#fixupVariables(Vector, int)
    */
   public void fixupVariables(Vector vars, int globalsSize)
   {
   	super.fixupVariables(vars, globalsSize);
   }

   /**
    * Add the node into a vector of nodes where it should occur in
    * document order.
    * @param node The node to be added.
    * @return insertIndex.
    * @throws RuntimeException thrown if this NodeSetDTM is not of
    * a mutable type.
    */
    protected int addNodeInDocOrder(int node)
    {
       assertion(hasCache(), "addNodeInDocOrder must be done on a mutable sequence!");

       int insertIndex = -1;

       NodeVector vec = getVector();

       // This needs to do a binary search, but a binary search
       // is somewhat tough because the sequence test involves
       // two nodes.
       int size = vec.size(), i;

       for (i = size - 1; i >= 0; i--)
       {
         int child = vec.elementAt(i);

         if (child == node)
         {
           i = -2; // Duplicate, suppress insert

           break;
         }

         DTM dtm = m_dtmMgr.getDTM(node);
         if (!dtm.isNodeAfter(node, child))
         {
           break;
         }
       }

       if (i != -2)
       {
         insertIndex = i + 1;

         vec.insertElementAt(node, insertIndex);
       }

       // checkDups();
       return insertIndex;
     } // end addNodeInDocOrder(Vector v, Object obj)

    /**
     * It used to be that many locations in the code simply
     * did an assignment to this.m_obj directly, rather than
     * calling the setObject(Object) method. The problem is
     * that our super-class would be updated on what the
     * cache associated with this NodeSequence, but
     * we wouldn't know ourselves.
     * <p>
     * All setting of m_obj is done through setObject() now,
     * and this method over-rides the super-class method.
     * So now we are in the loop have an opportunity
     * to update some caching information.
     *
     */
    protected void setObject(Object obj) {
        if (obj instanceof NodeVector) {
            // Keep our superclass informed of the current NodeVector
            // ... if we don't the smoketest fails (don't know why).
            super.setObject(obj);

            // A copy of the code of what SetVector() would do.
            NodeVector v = (NodeVector)obj;
            if (m_cache != null) {
                m_cache.setVector(v);
            } else if (v!=null) {
                m_cache = new IteratorCache();
                m_cache.setVector(v);
            }
        } else if (obj instanceof IteratorCache) {
            IteratorCache cache = (IteratorCache) obj;
            m_cache = cache;
            m_cache.increaseUseCount();

            // Keep our superclass informed of the current NodeVector
            super.setObject(cache.getVector());
        } else {
            super.setObject(obj);
        }

    }

    /**
     * Each NodeSequence object has an iterator which is "walked".
     * As an iterator is walked one obtains nodes from it.
     * As those nodes are obtained they may be cached, making
     * the next walking of a copy or clone of the iterator faster.
     * This field (m_cache) is a reference to such a cache,
     * which is populated as the iterator is walked.
     * <p>
     * Note that multiple NodeSequence objects may hold a
     * reference to the same cache, and also
     * (and this is important) the same iterator.
     * The iterator and its cache may be shared among
     * many NodeSequence objects.
     * <p>
     * If one of the NodeSequence objects walks ahead
     * of the others it fills in the cache.
     * As the others NodeSequence objects catch up they
     * get their values from
     * the cache rather than the iterator itself, so
     * the iterator is only ever walked once and everyone
     * benefits from the cache.
     * <p>
     * At some point the cache may be
     * complete due to walking to the end of one of
     * the copies of the iterator, and the cache is
     * then marked as "complete".
     * and the cache will have no more nodes added to it.
     * <p>
     * Its use-count is the number of NodeSequence objects that use it.
     */
    private final static class IteratorCache {
        /**
         * A list of nodes already obtained from the iterator.
         * As the iterator is walked the nodes obtained from
         * it are appended to this list.
         * <p>
         * Both an iterator and its corresponding cache can
         * be shared by multiple NodeSequence objects.
         * <p>
         * For example, consider three NodeSequence objects
         * ns1, ns2 and ns3 doing such sharing, and the
         * nodes to be obtaind from the iterator being
         * the sequence { 33, 11, 44, 22, 55 }.
         * <p>
         * If ns3.nextNode() is called 3 times the the
         * underlying iterator will have walked through
         * 33, 11, 55 and these three nodes will have been put
         * in the cache.
         * <p>
         * If ns2.nextNode() is called 2 times it will return
         * 33 and 11 from the cache, leaving the iterator alone.
         * <p>
         * If ns1.nextNode() is called 6 times it will return
         * 33 and 11 from the cache, then get 44, 22, 55 from
         * the iterator, and appending 44, 22, 55 to the cache.
         * On the sixth call it is found that the iterator is
         * exhausted and the cache is marked complete.
         * <p>
         * Should ns2 or ns3 have nextNode() called they will
         * know that the cache is complete, and they will
         * obtain all subsequent nodes from the cache.
         * <p>
         * Note that the underlying iterator, though shared
         * is only ever walked once.
         */
         private NodeVector m_vec2;

         /**
          * true if the associated iterator is exhausted and
          * all nodes obtained from it are in the cache.
          */
         private boolean m_isComplete2;

         private int m_useCount2;

         IteratorCache() {
             m_vec2 = null;
             m_isComplete2 = false;
             m_useCount2 = 1;
             return;
         }

         /**
          * Returns count of how many NodeSequence objects share this
          * IteratorCache object.
          */
         private int useCount() {
             return m_useCount2;
         }

         /**
          * This method is called when yet another
          * NodeSequence object uses, or shares
          * this same cache.
          *
          */
         private void increaseUseCount() {
             if (m_vec2 != null)
                 m_useCount2++;

         }

         /**
          * Sets the NodeVector that holds the
          * growing list of nodes as they are appended
          * to the cached list.
          */
         private void setVector(NodeVector nv) {
             m_vec2 = nv;
             m_useCount2 = 1;
         }

         /**
          * Get the cached list of nodes obtained from
          * the iterator so far.
          */
         private NodeVector getVector() {
             return m_vec2;
         }

         /**
          * Call this method with 'true' if the
          * iterator is exhausted and the cached list
          * is complete, or no longer growing.
          */
         private void setCacheComplete(boolean b) {
             m_isComplete2 = b;

         }

         /**
          * Returns true if no cache is complete
          * and immutable.
          */
         private boolean isComplete() {
             return m_isComplete2;
         }
     }

     /**
      * Get the cached list of nodes appended with
      * values obtained from the iterator as
      * a NodeSequence is walked when its
      * nextNode() method is called.
      */
     protected IteratorCache getIteratorCache() {
         return m_cache;
     }
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	/*
	* $Id: NodeSequence.java 469367 2006-10-31 04:41:08Z minchau $
	*/
	package org.apache.xpath.axes;

	import java.util.Vector;

	import org.apache.xml.dtm.DTM;
	import org.apache.xml.dtm.DTMFilter;
	import org.apache.xml.dtm.DTMIterator;
	import org.apache.xml.dtm.DTMManager;
	import org.apache.xml.utils.NodeVector;
	import org.apache.xpath.NodeSetDTM;
	import org.apache.xpath.XPathContext;
	import org.apache.xpath.objects.XObject;

	/**
	* This class is the dynamic wrapper for a Xalan DTMIterator instance, and
	* provides random access capabilities.
	*/
	public class NodeSequence extends XObject
	implements DTMIterator, Cloneable, PathComponent
	{
	static final long serialVersionUID = 3866261934726581044L;
	/** The index of the last node in the iteration. */
	protected int m_last = -1;

	/**
	* The index of the next node to be fetched. Useful if this
	* is a cached iterator, and is being used as random access
	* NodeList.
	*/
	protected int m_next = 0;

	/**
	* A cache of a list of nodes obtained from the iterator so far.
	* This list is appended to until the iterator is exhausted and
	* the cache is complete.
	* <p>
	* Multiple NodeSequence objects may share the same cache.
	*/
	private IteratorCache m_cache;

	/**
	* If this iterator needs to cache nodes that are fetched, they
	* are stored in the Vector in the generic object.
	*/
	protected NodeVector getVector() {
	NodeVector nv = (m_cache != null) ? m_cache.getVector() : null;
	return nv;
	}

	/**
	* Get the cache (if any) of nodes obtained from
	* the iterator so far. Note that the cache keeps
	* growing until the iterator is walked to exhaustion,
	* at which point the cache is "complete".
	*/
	private IteratorCache getCache() {
	return m_cache;
	}

	/**
	* Set the vector where nodes will be cached.
	*/
	protected void SetVector(NodeVector v)
	{
	setObject(v);
	}


	/**
	* If the iterator needs to cache nodes as they are fetched,
	* then this method returns true.
	*/
	public boolean hasCache()
	{
	final NodeVector nv = getVector();
	return (nv != null);
	}

	/**
	* If this NodeSequence has a cache, and that cache is
	* fully populated then this method returns true, otherwise
	* if there is no cache or it is not complete it returns false.
	*/
	private boolean cacheComplete() {
	final boolean complete;
	if (m_cache != null) {
	complete = m_cache.isComplete();
	} else {
	complete = false;
	}
	return complete;
	}

	/**
	* If this NodeSequence has a cache, mark that it is complete.
	* This method should be called after the iterator is exhausted.
	*/
	private void markCacheComplete() {
	NodeVector nv = getVector();
	if (nv != null) {
	m_cache.setCacheComplete(true);
	}
	}


	/**
	* The functional iterator that fetches nodes.
	*/
	protected DTMIterator m_iter;

	/**
	* Set the functional iterator that fetches nodes.
	* @param iter The iterator that is to be contained.
	*/
	public final void setIter(DTMIterator iter)
	{
	m_iter = iter;
	}

	/**
	* Get the functional iterator that fetches nodes.
	* @return The contained iterator.
	*/
	public final DTMIterator getContainedIter()
	{
	return m_iter;
	}

	/**
	* The DTMManager to use if we're using a NodeVector only.
	* We may well want to do away with this, and store it in the NodeVector.
	*/
	protected DTMManager m_dtmMgr;

	// ==== Constructors ====

	/**
	* Create a new NodeSequence from a (already cloned) iterator.
	*
	* @param iter Cloned (not static) DTMIterator.
	* @param context The initial context node.
	* @param xctxt The execution context.
	* @param shouldCacheNodes True if this sequence can random access.
	*/
	private NodeSequence(DTMIterator iter, int context, XPathContext xctxt, boolean shouldCacheNodes)
	{
	setIter(iter);
	setRoot(context, xctxt);
	setShouldCacheNodes(shouldCacheNodes);
	}

	/**
	* Create a new NodeSequence from a (already cloned) iterator.
	*
	* @param nodeVector
	*/
	public NodeSequence(Object nodeVector)
	{
	super(nodeVector);
	if (nodeVector instanceof NodeVector) {
	SetVector((NodeVector) nodeVector);
	}
	if(null != nodeVector)
	{
	assertion(nodeVector instanceof NodeVector,
	"Must have a NodeVector as the object for NodeSequence!");
	if(nodeVector instanceof DTMIterator)
	{
	setIter((DTMIterator)nodeVector);
	m_last = ((DTMIterator)nodeVector).getLength();
	}

	}
	}

	/**
	* Construct an empty XNodeSet object. This is used to create a mutable
	* nodeset to which random nodes may be added.
	*/
	private NodeSequence(DTMManager dtmMgr)
	{
	super(new NodeVector());
	m_last = 0;
	m_dtmMgr = dtmMgr;
	}


	/**
	* Create a new NodeSequence in an invalid (null) state.
	*/
	public NodeSequence()
	{
	return;
	}


	/**
	* @see DTMIterator#getDTM(int)
	*/
	public DTM getDTM(int nodeHandle)
	{
	DTMManager mgr = getDTMManager();
	if(null != mgr)
	return getDTMManager().getDTM(nodeHandle);
	else
	{
	assertion(false, "Can not get a DTM Unless a DTMManager has been set!");
	return null;
	}
	}

	/**
	* @see DTMIterator#getDTMManager()
	*/
	public DTMManager getDTMManager()
	{
	return m_dtmMgr;
	}

	/**
	* @see DTMIterator#getRoot()
	*/
	public int getRoot()
	{
	if(null != m_iter)
	return m_iter.getRoot();
	else
	{
	// NodeSetDTM will call this, and so it's not a good thing to throw
	// an assertion here.
	// assertion(false, "Can not get the root from a non-iterated NodeSequence!");
	return DTM.NULL;
	}
	}

	/**
	* @see DTMIterator#setRoot(int, Object)
	*/
	public void setRoot(int nodeHandle, Object environment)
	{
	if(null != m_iter)
	{
	XPathContext xctxt = (XPathContext)environment;
	m_dtmMgr = xctxt.getDTMManager();
	m_iter.setRoot(nodeHandle, environment);
	if(!m_iter.isDocOrdered())
	{
	if(!hasCache())
	setShouldCacheNodes(true);
	runTo(-1);
	m_next=0;
	}
	}
	else
	assertion(false, "Can not setRoot on a non-iterated NodeSequence!");
	}

	/**
	* @see DTMIterator#reset()
	*/
	public void reset()
	{
	m_next = 0;
	// not resetting the iterator on purpose!!!
	}

	/**
	* @see DTMIterator#getWhatToShow()
	*/
	public int getWhatToShow()
	{
	return hasCache() ? (DTMFilter.SHOW_ALL & ~DTMFilter.SHOW_ENTITY_REFERENCE)
	: m_iter.getWhatToShow();
	}

	/**
	* @see DTMIterator#getExpandEntityReferences()
	*/
	public boolean getExpandEntityReferences()
	{
	if(null != m_iter)
	return m_iter.getExpandEntityReferences();
	else
	return true;
	}

	/**
	* @see DTMIterator#nextNode()
	*/
	public int nextNode()
	{
	// If the cache is on, and the node has already been found, then
	// just return from the list.
	NodeVector vec = getVector();
	if (null != vec)
	{
	// There is a cache
	if(m_next < vec.size())
	{
	// The node is in the cache, so just return it.
	int next = vec.elementAt(m_next);
	m_next++;
	return next;
	}
	else if(cacheComplete() \|\| (-1 != m_last) \|\| (null == m_iter))
	{
	m_next++;
	return DTM.NULL;
	}
	}

	if (null == m_iter)
	return DTM.NULL;

	int next = m_iter.nextNode();
	if(DTM.NULL != next)
	{
	if(hasCache())
	{
	if(m_iter.isDocOrdered())
	{
	getVector().addElement(next);
	m_next++;
	}
	else
	{
	int insertIndex = addNodeInDocOrder(next);
	if(insertIndex >= 0)
	m_next++;
	}
	}
	else
	m_next++;
	}
	else
	{
	// We have exhausted the iterator, and if there is a cache
	// it must have all nodes in it by now, so let the cache
	// know that it is complete.
	markCacheComplete();

	m_last = m_next;
	m_next++;
	}

	return next;
	}

	/**
	* @see DTMIterator#previousNode()
	*/
	public int previousNode()
	{
	if(hasCache())
	{
	if(m_next <= 0)
	return DTM.NULL;
	else
	{
	m_next--;
	return item(m_next);
	}
	}
	else
	{
	int n = m_iter.previousNode();
	m_next = m_iter.getCurrentPos();
	return m_next;
	}
	}

	/**
	* @see DTMIterator#detach()
	*/
	public void detach()
	{
	if(null != m_iter)
	m_iter.detach();
	super.detach();
	}

	/**
	* Calling this with a value of false will cause the nodeset
	* to be cached.
	* @see DTMIterator#allowDetachToRelease(boolean)
	*/
	public void allowDetachToRelease(boolean allowRelease)
	{
	if((false == allowRelease) && !hasCache())
	{
	setShouldCacheNodes(true);
	}

	if(null != m_iter)
	m_iter.allowDetachToRelease(allowRelease);
	super.allowDetachToRelease(allowRelease);
	}

	/**
	* @see DTMIterator#getCurrentNode()
	*/
	public int getCurrentNode()
	{
	if(hasCache())
	{
	int currentIndex = m_next-1;
	NodeVector vec = getVector();
	if((currentIndex >= 0) && (currentIndex < vec.size()))
	return vec.elementAt(currentIndex);
	else
	return DTM.NULL;
	}

	if(null != m_iter)
	{
	return m_iter.getCurrentNode();
	}
	else
	return DTM.NULL;
	}

	/**
	* @see DTMIterator#isFresh()
	*/
	public boolean isFresh()
	{
	return (0 == m_next);
	}

	/**
	* @see DTMIterator#setShouldCacheNodes(boolean)
	*/
	public void setShouldCacheNodes(boolean b)
	{
	if (b)
	{
	if(!hasCache())
	{
	SetVector(new NodeVector());
	}
	// else
	// getVector().RemoveAllNoClear(); // Is this good?
	}
	else
	SetVector(null);
	}

	/**
	* @see DTMIterator#isMutable()
	*/
	public boolean isMutable()
	{
	return hasCache(); // though may be surprising if it also has an iterator!
	}

	/**
	* @see DTMIterator#getCurrentPos()
	*/
	public int getCurrentPos()
	{
	return m_next;
	}

	/**
	* @see DTMIterator#runTo(int)
	*/
	public void runTo(int index)
	{
	int n;

	if (-1 == index)
	{
	int pos = m_next;
	while (DTM.NULL != (n = nextNode()));
	m_next = pos;
	}
	else if(m_next == index)
	{
	return;
	}
	else if(hasCache() && m_next < getVector().size())
	{
	m_next = index;
	}
	else if((null == getVector()) && (index < m_next))
	{
	while ((m_next >= index) && DTM.NULL != (n = previousNode()));
	}
	else
	{
	while ((m_next < index) && DTM.NULL != (n = nextNode()));
	}

	}

	/**
	* @see DTMIterator#setCurrentPos(int)
	*/
	public void setCurrentPos(int i)
	{
	runTo(i);
	}

	/**
	* @see DTMIterator#item(int)
	*/
	public int item(int index)
	{
	setCurrentPos(index);
	int n = nextNode();
	m_next = index;
	return n;
	}

	/**
	* @see DTMIterator#setItem(int, int)
	*/
	public void setItem(int node, int index)
	{
	NodeVector vec = getVector();
	if(null != vec)
	{
	int oldNode = vec.elementAt(index);
	if (oldNode != node && m_cache.useCount() > 1) {
	/* If we are going to set the node at the given index
	* to a different value, and the cache is shared
	* (has a use count greater than 1)
	* then make a copy of the cache and use it
	* so we don't overwrite the value for other
	* users of the cache.
	*/
	IteratorCache newCache = new IteratorCache();
	final NodeVector nv;
	try {
	nv = (NodeVector) vec.clone();
	} catch (CloneNotSupportedException e) {
	// This should never happen
	e.printStackTrace();
	RuntimeException rte = new RuntimeException(e.getMessage());
	throw rte;
	}
	newCache.setVector(nv);
	newCache.setCacheComplete(true);
	m_cache = newCache;
	vec = nv;

	// Keep our superclass informed of the current NodeVector
	super.setObject(nv);

	/* When we get to here the new cache has
	* a use count of 1 and when setting a
	* bunch of values on the same NodeSequence,
	* such as when sorting, we will keep setting
	* values in that same copy which has a use count of 1.
	*/
	}
	vec.setElementAt(node, index);
	m_last = vec.size();
	}
	else
	m_iter.setItem(node, index);
	}

	/**
	* @see DTMIterator#getLength()
	*/
	public int getLength()
	{
	IteratorCache cache = getCache();

	if(cache != null)
	{
	// Nodes from the iterator are cached
	if (cache.isComplete()) {
	// All of the nodes from the iterator are cached
	// so just return the number of nodes in the cache
	NodeVector nv = cache.getVector();
	return nv.size();
	}

	// If this NodeSequence wraps a mutable nodeset, then
	// m_last will not reflect the size of the nodeset if
	// it has been mutated...
	if (m_iter instanceof NodeSetDTM)
	{
	return m_iter.getLength();
	}

	if(-1 == m_last)
	{
	int pos = m_next;
	runTo(-1);
	m_next = pos;
	}
	return m_last;
	}
	else
	{
	return (-1 == m_last) ? (m_last = m_iter.getLength()) : m_last;
	}
	}

	/**
	* Note: Not a deep clone.
	* @see DTMIterator#cloneWithReset()
	*/
	public DTMIterator cloneWithReset() throws CloneNotSupportedException
	{
	NodeSequence seq = (NodeSequence)super.clone();
	seq.m_next = 0;
	if (m_cache != null) {
	// In making this clone of an iterator we are making
	// another NodeSequence object it has a reference
	// to the same IteratorCache object as the original
	// so we need to remember that more than one
	// NodeSequence object shares the cache.
	m_cache.increaseUseCount();
	}

	return seq;
	}

	/**
	* Get a clone of this iterator, but don't reset the iteration in the
	* process, so that it may be used from the current position.
	* Note: Not a deep clone.
	*
	* @return A clone of this object.
	*
	* @throws CloneNotSupportedException
	*/
	public Object clone() throws CloneNotSupportedException
	{
	NodeSequence clone = (NodeSequence) super.clone();
	if (null != m_iter) clone.m_iter = (DTMIterator) m_iter.clone();
	if (m_cache != null) {
	// In making this clone of an iterator we are making
	// another NodeSequence object it has a reference
	// to the same IteratorCache object as the original
	// so we need to remember that more than one
	// NodeSequence object shares the cache.
	m_cache.increaseUseCount();
	}

	return clone;
	}


	/**
	* @see DTMIterator#isDocOrdered()
	*/
	public boolean isDocOrdered()
	{
	if(null != m_iter)
	return m_iter.isDocOrdered();
	else
	return true; // can't be sure?
	}

	/**
	* @see DTMIterator#getAxis()
	*/
	public int getAxis()
	{
	if(null != m_iter)
	return m_iter.getAxis();
	else
	{
	assertion(false, "Can not getAxis from a non-iterated node sequence!");
	return 0;
	}
	}

	/**
	* @see PathComponent#getAnalysisBits()
	*/
	public int getAnalysisBits()
	{
	if((null != m_iter) && (m_iter instanceof PathComponent))
	return ((PathComponent)m_iter).getAnalysisBits();
	else
	return 0;
	}

	/**
	* @see org.apache.xpath.Expression#fixupVariables(Vector, int)
	*/
	public void fixupVariables(Vector vars, int globalsSize)
	{
	super.fixupVariables(vars, globalsSize);
	}

	/**
	* Add the node into a vector of nodes where it should occur in
	* document order.
	* @param node The node to be added.
	* @return insertIndex.
	* @throws RuntimeException thrown if this NodeSetDTM is not of
	* a mutable type.
	*/
	protected int addNodeInDocOrder(int node)
	{
	assertion(hasCache(), "addNodeInDocOrder must be done on a mutable sequence!");

	int insertIndex = -1;

	NodeVector vec = getVector();

	// This needs to do a binary search, but a binary search
	// is somewhat tough because the sequence test involves
	// two nodes.
	int size = vec.size(), i;

	for (i = size - 1; i >= 0; i--)
	{
	int child = vec.elementAt(i);

	if (child == node)
	{
	i = -2; // Duplicate, suppress insert

	break;
	}

	DTM dtm = m_dtmMgr.getDTM(node);
	if (!dtm.isNodeAfter(node, child))
	{
	break;
	}
	}

	if (i != -2)
	{
	insertIndex = i + 1;

	vec.insertElementAt(node, insertIndex);
	}

	// checkDups();
	return insertIndex;
	} // end addNodeInDocOrder(Vector v, Object obj)

	/**
	* It used to be that many locations in the code simply
	* did an assignment to this.m_obj directly, rather than
	* calling the setObject(Object) method. The problem is
	* that our super-class would be updated on what the
	* cache associated with this NodeSequence, but
	* we wouldn't know ourselves.
	* <p>
	* All setting of m_obj is done through setObject() now,
	* and this method over-rides the super-class method.
	* So now we are in the loop have an opportunity
	* to update some caching information.
	*
	*/
	protected void setObject(Object obj) {
	if (obj instanceof NodeVector) {
	// Keep our superclass informed of the current NodeVector
	// ... if we don't the smoketest fails (don't know why).
	super.setObject(obj);

	// A copy of the code of what SetVector() would do.
	NodeVector v = (NodeVector)obj;
	if (m_cache != null) {
	m_cache.setVector(v);
	} else if (v!=null) {
	m_cache = new IteratorCache();
	m_cache.setVector(v);
	}
	} else if (obj instanceof IteratorCache) {
	IteratorCache cache = (IteratorCache) obj;
	m_cache = cache;
	m_cache.increaseUseCount();

	// Keep our superclass informed of the current NodeVector
	super.setObject(cache.getVector());
	} else {
	super.setObject(obj);
	}

	}

	/**
	* Each NodeSequence object has an iterator which is "walked".
	* As an iterator is walked one obtains nodes from it.
	* As those nodes are obtained they may be cached, making
	* the next walking of a copy or clone of the iterator faster.
	* This field (m_cache) is a reference to such a cache,
	* which is populated as the iterator is walked.
	* <p>
	* Note that multiple NodeSequence objects may hold a
	* reference to the same cache, and also
	* (and this is important) the same iterator.
	* The iterator and its cache may be shared among
	* many NodeSequence objects.
	* <p>
	* If one of the NodeSequence objects walks ahead
	* of the others it fills in the cache.
	* As the others NodeSequence objects catch up they
	* get their values from
	* the cache rather than the iterator itself, so
	* the iterator is only ever walked once and everyone
	* benefits from the cache.
	* <p>
	* At some point the cache may be
	* complete due to walking to the end of one of
	* the copies of the iterator, and the cache is
	* then marked as "complete".
	* and the cache will have no more nodes added to it.
	* <p>
	* Its use-count is the number of NodeSequence objects that use it.
	*/
	private final static class IteratorCache {
	/**
	* A list of nodes already obtained from the iterator.
	* As the iterator is walked the nodes obtained from
	* it are appended to this list.
	* <p>
	* Both an iterator and its corresponding cache can
	* be shared by multiple NodeSequence objects.
	* <p>
	* For example, consider three NodeSequence objects
	* ns1, ns2 and ns3 doing such sharing, and the
	* nodes to be obtaind from the iterator being
	* the sequence { 33, 11, 44, 22, 55 }.
	* <p>
	* If ns3.nextNode() is called 3 times the the
	* underlying iterator will have walked through
	* 33, 11, 55 and these three nodes will have been put
	* in the cache.
	* <p>
	* If ns2.nextNode() is called 2 times it will return
	* 33 and 11 from the cache, leaving the iterator alone.
	* <p>
	* If ns1.nextNode() is called 6 times it will return
	* 33 and 11 from the cache, then get 44, 22, 55 from
	* the iterator, and appending 44, 22, 55 to the cache.
	* On the sixth call it is found that the iterator is
	* exhausted and the cache is marked complete.
	* <p>
	* Should ns2 or ns3 have nextNode() called they will
	* know that the cache is complete, and they will
	* obtain all subsequent nodes from the cache.
	* <p>
	* Note that the underlying iterator, though shared
	* is only ever walked once.
	*/
	private NodeVector m_vec2;

	/**
	* true if the associated iterator is exhausted and
	* all nodes obtained from it are in the cache.
	*/
	private boolean m_isComplete2;

	private int m_useCount2;

	IteratorCache() {
	m_vec2 = null;
	m_isComplete2 = false;
	m_useCount2 = 1;
	return;
	}

	/**
	* Returns count of how many NodeSequence objects share this
	* IteratorCache object.
	*/
	private int useCount() {
	return m_useCount2;
	}

	/**
	* This method is called when yet another
	* NodeSequence object uses, or shares
	* this same cache.
	*
	*/
	private void increaseUseCount() {
	if (m_vec2 != null)
	m_useCount2++;

	}

	/**
	* Sets the NodeVector that holds the
	* growing list of nodes as they are appended
	* to the cached list.
	*/
	private void setVector(NodeVector nv) {
	m_vec2 = nv;
	m_useCount2 = 1;
	}

	/**
	* Get the cached list of nodes obtained from
	* the iterator so far.
	*/
	private NodeVector getVector() {
	return m_vec2;
	}

	/**
	* Call this method with 'true' if the
	* iterator is exhausted and the cached list
	* is complete, or no longer growing.
	*/
	private void setCacheComplete(boolean b) {
	m_isComplete2 = b;

	}

	/**
	* Returns true if no cache is complete
	* and immutable.
	*/
	private boolean isComplete() {
	return m_isComplete2;
	}
	}

	/**
	* Get the cached list of nodes appended with
	* values obtained from the iterator as
	* a NodeSequence is walked when its
	* nextNode() method is called.
	*/
	protected IteratorCache getIteratorCache() {
	return m_cache;
	}
	}