/*

 */

/*

 * 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.

 */

package com.sun.org.apache.xml.internal.dtm.ref;

import com.sun.org.apache.xml.internal.dtm.*;

import com.sun.org.apache.xml.internal.utils.BoolStack;

import com.sun.org.apache.xml.internal.utils.XMLString;

import com.sun.org.apache.xml.internal.utils.XMLStringFactory;

import java.io.*; // for dumpDTM

/**

 * The <code>DTMDefaultBase</code> class serves as a helper base for DTMs.

 * It sets up structures for navigation and type, while leaving data

 * management and construction to the derived classes.

 */

public abstract class DTMDefaultBase implements DTM

{

    static final boolean JJK_DEBUG=false;

  // This constant is likely to be removed in the future. Use the

  // getDocument() method instead of ROOTNODE to get at the root

  // node of a DTM.

  /** The identity of the root node. */

  public static final int ROOTNODE = 0;

  /**

   * The number of nodes, which is also used to determine the next

   *  node index.

   */

  protected int m_size = 0;

  /** The expanded names, one array element for each node. */

  protected SuballocatedIntVector m_exptype;

  /** First child values, one array element for each node. */

  protected SuballocatedIntVector m_firstch;

  /** Next sibling values, one array element for each node. */

  protected SuballocatedIntVector m_nextsib;

  /** Previous sibling values, one array element for each node. */

  protected SuballocatedIntVector m_prevsib;

  /** Previous sibling values, one array element for each node. */

  protected SuballocatedIntVector m_parent;

  /** Vector of SuballocatedIntVectors of NS decl sets */

  /** SuballocatedIntVector  of elements at which corresponding

   * namespaceDeclSets were defined */

  protected SuballocatedIntVector m_namespaceDeclSetElements = null;

  /**

   * These hold indexes to elements based on namespace and local name.

   * The base lookup is the the namespace.  The second lookup is the local

   * name, and the last array contains the the first free element

   * at the start, and the list of element handles following.

   */

  protected int[][][] m_elemIndexes;

  /** The default block size of the node arrays */

  public static final int DEFAULT_BLOCKSIZE = 512;  // favor small docs.

  /** The number of blocks for the node arrays */

  public static final int DEFAULT_NUMBLOCKS = 32;

  /** The number of blocks used for small documents & RTFs */

  public static final int DEFAULT_NUMBLOCKS_SMALL = 4;

  /** The block size of the node arrays */

  //protected final int m_blocksize;

  /**

   * The value to use when the information has not been built yet.

   */

  protected static final int NOTPROCESSED = DTM.NULL - 1;

  /**

   * The DTM manager who "owns" this DTM.

   */

  public DTMManager m_mgr;

  /**

   * m_mgr cast to DTMManagerDefault, or null if it isn't an instance

   * (Efficiency hook)

   */

  protected DTMManagerDefault m_mgrDefault=null;

  /** The document identity number(s). If we have overflowed the addressing

   * range of the first that was assigned to us, we may add others. */

  protected SuballocatedIntVector m_dtmIdent;

  /** The mask for the identity.

      %REVIEW% Should this really be set to the _DEFAULT? What if

      a particular DTM wanted to use another value? */

  //protected final static int m_mask = DTMManager.IDENT_NODE_DEFAULT;

  /** The base URI for this document. */

  protected String m_documentBaseURI;

  /**

   * The whitespace filter that enables elements to strip whitespace or not.

   */

  protected DTMWSFilter m_wsfilter;

  /** Flag indicating whether to strip whitespace nodes */

  protected boolean m_shouldStripWS = false;

  /** Stack of flags indicating whether to strip whitespace nodes */

  protected BoolStack m_shouldStripWhitespaceStack;

  /** The XMLString factory for creating XMLStrings. */

  protected XMLStringFactory m_xstrf;

  /**

   * The table for exandedNameID lookups.  This may or may not be the same

   * table as is contained in the DTMManagerDefault.

   */

  protected ExpandedNameTable m_expandedNameTable;

  /** true if indexing is turned on. */

  protected boolean m_indexing;

  /**

   * Construct a DTMDefaultBase object using the default block size.

   *

   * @param mgr The DTMManager who owns this DTM.

   * @param source The object that is used to specify the construction source.

   * @param dtmIdentity The DTM identity ID for this DTM.

   * @param whiteSpaceFilter The white space filter for this DTM, which may

   *                         be null.

   * @param xstringfactory The factory to use for creating XMLStrings.

   * @param doIndexing true if the caller considers it worth it to use

   *                   indexing schemes.

   */

  public DTMDefaultBase(DTMManager mgr, Source source, int dtmIdentity,

                        DTMWSFilter whiteSpaceFilter,

                        XMLStringFactory xstringfactory, boolean doIndexing)

  {

    this(mgr, source, dtmIdentity, whiteSpaceFilter, xstringfactory,

         doIndexing, DEFAULT_BLOCKSIZE, true, false);

  }

  /**

   * Construct a DTMDefaultBase object from a DOM node.

   *

   * @param mgr The DTMManager who owns this DTM.

   * @param source The object that is used to specify the construction source.

   * @param dtmIdentity The DTM identity ID for this DTM.

   * @param whiteSpaceFilter The white space filter for this DTM, which may

   *                         be null.

   * @param xstringfactory The factory to use for creating XMLStrings.

   * @param doIndexing true if the caller considers it worth it to use

   *                   indexing schemes.

   * @param blocksize The block size of the DTM.

   * @param usePrevsib true if we want to build the previous sibling node array.

   * @param newNameTable true if we want to use a new ExpandedNameTable for this DTM.

   */

  public DTMDefaultBase(DTMManager mgr, Source source, int dtmIdentity,

                        DTMWSFilter whiteSpaceFilter,

                        XMLStringFactory xstringfactory, boolean doIndexing,

                        int blocksize, boolean usePrevsib,

                        boolean newNameTable)

  {

    // Use smaller sizes for the internal node arrays if the block size

    // is small.

    int numblocks;

    if (blocksize <= 64)

    {

      numblocks = DEFAULT_NUMBLOCKS_SMALL;

      m_dtmIdent= new SuballocatedIntVector(4, 1);

    }

    else

    {

      numblocks = DEFAULT_NUMBLOCKS;

      m_dtmIdent= new SuballocatedIntVector(32);

    }

    m_exptype = new SuballocatedIntVector(blocksize, numblocks);

    m_firstch = new SuballocatedIntVector(blocksize, numblocks);

    m_nextsib = new SuballocatedIntVector(blocksize, numblocks);

    m_parent  = new SuballocatedIntVector(blocksize, numblocks);

    // Only create the m_prevsib array if the usePrevsib flag is true.

    // Some DTM implementations (e.g. SAXImpl) do not need this array.

    // We can save the time to build it in those cases.

    if (usePrevsib)

      m_prevsib = new SuballocatedIntVector(blocksize, numblocks);

    m_mgr = mgr;

    if(mgr instanceof DTMManagerDefault)

      m_mgrDefault=(DTMManagerDefault)mgr;

    m_documentBaseURI = (null != source) ? source.getSystemId() : null;

    m_dtmIdent.setElementAt(dtmIdentity,0);

    m_wsfilter = whiteSpaceFilter;

    m_xstrf = xstringfactory;

    m_indexing = doIndexing;

    if (doIndexing)

    {

      m_expandedNameTable = new ExpandedNameTable();

    }

    else

    {

      // Note that this fails if we aren't talking to an instance of

      // DTMManagerDefault

      m_expandedNameTable = m_mgrDefault.getExpandedNameTable(this);

    }

    if (null != whiteSpaceFilter)

    {

      m_shouldStripWhitespaceStack = new BoolStack();

      pushShouldStripWhitespace(false);

    }

  }

  /**

   * Ensure that the size of the element indexes can hold the information.

   *

   * @param namespaceID Namespace ID index.

   * @param LocalNameID Local name ID.

   */

  protected void ensureSizeOfIndex(int namespaceID, int LocalNameID)

  {

    if (null == m_elemIndexes)

    {

      m_elemIndexes = new int[namespaceID + 20][][];

    }

    else if (m_elemIndexes.length <= namespaceID)

    {

      int[][][] indexes = m_elemIndexes;

      m_elemIndexes = new int[namespaceID + 20][][];

      System.arraycopy(indexes, 0, m_elemIndexes, 0, indexes.length);

    }

    int[][] localNameIndex = m_elemIndexes[namespaceID];

    if (null == localNameIndex)

    {

      localNameIndex = new int[LocalNameID + 100][];

      m_elemIndexes[namespaceID] = localNameIndex;

    }

    else if (localNameIndex.length <= LocalNameID)

    {

      int[][] indexes = localNameIndex;

      localNameIndex = new int[LocalNameID + 100][];

      System.arraycopy(indexes, 0, localNameIndex, 0, indexes.length);

      m_elemIndexes[namespaceID] = localNameIndex;

    }

    int[] elemHandles = localNameIndex[LocalNameID];

    if (null == elemHandles)

    {

      elemHandles = new int[128];

      localNameIndex[LocalNameID] = elemHandles;

      elemHandles[0] = 1;

    }

    else if (elemHandles.length <= elemHandles[0] + 1)

    {

      int[] indexes = elemHandles;

      elemHandles = new int[elemHandles[0] + 1024];

      System.arraycopy(indexes, 0, elemHandles, 0, indexes.length);

      localNameIndex[LocalNameID] = elemHandles;

    }

  }

  /**

   * Add a node to the element indexes. The node will not be added unless

   * it's an element.

   *

   * @param expandedTypeID The expanded type ID of the node.

   * @param identity The node identity index.

   */

  protected void indexNode(int expandedTypeID, int identity)

  {

    ExpandedNameTable ent = m_expandedNameTable;

    short type = ent.getType(expandedTypeID);

    if (DTM.ELEMENT_NODE == type)

    {

      int namespaceID = ent.getNamespaceID(expandedTypeID);

      int localNameID = ent.getLocalNameID(expandedTypeID);

      ensureSizeOfIndex(namespaceID, localNameID);

      int[] index = m_elemIndexes[namespaceID][localNameID];

      index[index[0]] = identity;

      index[0]++;

    }

  }

  /**

   * Find the first index that occurs in the list that is greater than or

   * equal to the given value.

   *

   * @param list A list of integers.

   * @param start The start index to begin the search.

   * @param len The number of items to search.

   * @param value Find the slot that has a value that is greater than or

   * identical to this argument.

   *

   * @return The index in the list of the slot that is higher or identical

   * to the identity argument, or -1 if no node is higher or equal.

   */

  protected int findGTE(int[] list, int start, int len, int value)

  {

    int low = start;

    int high = start + (len - 1);

    int end = high;

    while (low <= high)

    {

      int mid = (low + high) / 2;

      int c = list[mid];

      if (c > value)

        high = mid - 1;

      else if (c < value)

        low = mid + 1;

      else

        return mid;

    }

    return (low <= end && list[low] > value) ? low : -1;

  }

  /**

   * Find the first matching element from the index at or after the

   * given node.

   *

   * @param nsIndex The namespace index lookup.

   * @param lnIndex The local name index lookup.

   * @param firstPotential The first potential match that is worth looking at.

   *

   * @return The first node that is greater than or equal to the

   *         firstPotential argument, or DTM.NOTPROCESSED if not found.

   */

  int findElementFromIndex(int nsIndex, int lnIndex, int firstPotential)

  {

    int[][][] indexes = m_elemIndexes;

    if (null != indexes && nsIndex < indexes.length)

    {

      int[][] lnIndexs = indexes[nsIndex];

      if (null != lnIndexs && lnIndex < lnIndexs.length)

      {

        int[] elems = lnIndexs[lnIndex];

        if (null != elems)

        {

          int pos = findGTE(elems, 1, elems[0], firstPotential);

          if (pos > -1)

          {

            return elems[pos];

          }

        }

      }

    }

    return NOTPROCESSED;

  }

  /**

   * Get the next node identity value in the list, and call the iterator

   * if it hasn't been added yet.

   *

   * @param identity The node identity (index).

   * @return identity+1, or DTM.NULL.

   */

  protected abstract int getNextNodeIdentity(int identity);

  /**

   * This method should try and build one or more nodes in the table.

   *

   * @return The true if a next node is found or false if

   *         there are no more nodes.

   */

  protected abstract boolean nextNode();

  /**

   * Get the number of nodes that have been added.

   *

   * @return the number of nodes that have been mapped.

   */

  protected abstract int getNumberOfNodes();

  /** Stateless axis traversers, lazely built. */

  protected DTMAxisTraverser[] m_traversers;

//    /**

//     * Ensure that the size of the information arrays can hold another entry

//     * at the given index.

//     *

//     * @param index On exit from this function, the information arrays sizes must be

//     * at least index+1.

//     */

//    protected void ensureSize(int index)

//    {

//        // We've cut over to Suballocated*Vector, which are self-sizing.

//    }

  /**

   * Get the simple type ID for the given node identity.

   *

   * @param identity The node identity.

   *

   * @return The simple type ID, or DTM.NULL.

   */

  protected short _type(int identity)

  {

    int info = _exptype(identity);

    if (NULL != info)

      return m_expandedNameTable.getType(info);

    else

      return NULL;

  }

  /**

   * Get the expanded type ID for the given node identity.

   *

   * @param identity The node identity.

   *

   * @return The expanded type ID, or DTM.NULL.

   */

  protected int _exptype(int identity)

  {

        if (identity == DTM.NULL)

        return NULL;

    // Reorganized test and loop into single flow

    // Tiny performance improvement, saves a few bytes of code, clearer.

    // %OPT% Other internal getters could be treated simliarly

    while (identity>=m_size)

    {

      if (!nextNode() && identity >= m_size)

        return NULL;

    }

    return m_exptype.elementAt(identity);

  }

  /**

   * Get the level in the tree for the given node identity.

   *

   * @param identity The node identity.

   *

   * @return The tree level, or DTM.NULL.

   */

  protected int _level(int identity)

  {

    while (identity>=m_size)

    {

      boolean isMore = nextNode();

      if (!isMore && identity >= m_size)

        return NULL;

    }

    int i=0;

    while(NULL != (identity=_parent(identity)))

      ++i;

    return i;

  }

  /**

   * Get the first child for the given node identity.

   *

   * @param identity The node identity.

   *

   * @return The first child identity, or DTM.NULL.

   */

  protected int _firstch(int identity)

  {

    // Boiler-plate code for each of the _xxx functions, except for the array.

    int info = (identity >= m_size) ? NOTPROCESSED : m_firstch.elementAt(identity);

    // Check to see if the information requested has been processed, and,

    // if not, advance the iterator until we the information has been

    // processed.