/*
 * Copyright (c) 2015, 2017, Oracle and/or its affiliates. All rights reserved.
 */
/*
 * 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.xerces.internal.dom;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import org.w3c.dom.DOMImplementation;
import org.w3c.dom.Element;
import org.w3c.dom.Node;

The Document interface represents the entire HTML or XML document.
Conceptually, it is the root of the document tree, and provides the
primary access to the document's data.

Since elements, text nodes, comments, processing instructions,
etc. cannot exist outside the context of a Document, the Document
interface also contains the factory methods needed to create these
objects. The Node objects created have a ownerDocument attribute
which associates them with the Document within whose context they
were created.
@xerces.internal
Since:
 PR-DOM-Level-1-19980818.
@LastModified
: Oct 2017/**
 * The Document interface represents the entire HTML or XML document.
 * Conceptually, it is the root of the document tree, and provides the
 * primary access to the document's data.
 * <P>
 * Since elements, text nodes, comments, processing instructions,
 * etc. cannot exist outside the context of a Document, the Document
 * interface also contains the factory methods needed to create these
 * objects. The Node objects created have a ownerDocument attribute
 * which associates them with the Document within whose context they
 * were created.
 *
 * @xerces.internal
 *
 * @since  PR-DOM-Level-1-19980818.
 * @LastModified: Oct 2017
 */
public class DeferredDocumentImpl
    extends DocumentImpl
    implements DeferredNode {

    //
    // Constants
    //

    
Serialization version. /** Serialization version. */
    static final long serialVersionUID = 5186323580749626857L;

    // debugging

    
To include code for printing the ref count tables. /** To include code for printing the ref count tables. */
    private static final boolean DEBUG_PRINT_REF_COUNTS = false;

    
To include code for printing the internal tables. /** To include code for printing the internal tables. */
    private static final boolean DEBUG_PRINT_TABLES = false;

    
To debug identifiers set to true and recompile. /** To debug identifiers set to true and recompile. */
    private static final boolean DEBUG_IDS = false;

    // protected

    
Chunk shift. /** Chunk shift. */
    protected static final int CHUNK_SHIFT = 11;           // 2^11 = 2k

    
Chunk size. /** Chunk size. */
    protected static final int CHUNK_SIZE = (1 << CHUNK_SHIFT);

    
Chunk mask. /** Chunk mask. */
    protected static final int CHUNK_MASK = CHUNK_SIZE - 1;

    
Initial chunk size. /** Initial chunk size. */
    protected static final int INITIAL_CHUNK_COUNT = (1 << (16 - CHUNK_SHIFT));   // 2^16 = 64k

    //
    // Data
    //

    // lazy-eval information
    // To maximize memory consumption the actual semantic of these fields vary
    // depending on the node type.

    
Node count. /** Node count. */
    protected transient int fNodeCount = 0;

    
Node types. /** Node types. */
    protected transient int fNodeType[][];

    
Node names. /** Node names. */
    protected transient Object fNodeName[][];

    
Node values. /** Node values. */
    protected transient Object fNodeValue[][];

    
Node parents. /** Node parents. */
    protected transient int fNodeParent[][];

    
Node first children. /** Node first children. */
    protected transient int fNodeLastChild[][];

    
Node prev siblings. /** Node prev siblings. */
    protected transient int fNodePrevSib[][];

    
Node namespace URI. /** Node namespace URI. */
    protected transient Object fNodeURI[][];

    
Extra data. /** Extra data. */
    protected transient int fNodeExtra[][];

    
Identifier count. /** Identifier count. */
    protected transient int fIdCount;

    
Identifier name indexes. /** Identifier name indexes. */
    protected transient String fIdName[];

    
Identifier element indexes. /** Identifier element indexes. */
    protected transient int fIdElement[];

    
DOM2: For namespace support in the deferred case.
/** DOM2: For namespace support in the deferred case.
     */
    // Implementation Note: The deferred element and attribute must know how to
    // interpret the int representing the qname.
    protected boolean fNamespacesEnabled = false;

    //
    // private data
    //
    private transient final StringBuilder fBufferStr = new StringBuilder();
    private transient final List<String> fStrChunks = new ArrayList<>();

    //
    // Constructors
    //

    
NON-DOM: Actually creating a Document is outside the DOM's spec,
since it has to operate in terms of a particular implementation.
/**
     * NON-DOM: Actually creating a Document is outside the DOM's spec,
     * since it has to operate in terms of a particular implementation.
     */
    public DeferredDocumentImpl() {
        this(false);
    } // <init>()

    
NON-DOM: Actually creating a Document is outside the DOM's spec,
since it has to operate in terms of a particular implementation.
/**
     * NON-DOM: Actually creating a Document is outside the DOM's spec,
     * since it has to operate in terms of a particular implementation.
     */
    public DeferredDocumentImpl(boolean namespacesEnabled) {
        this(namespacesEnabled, false);
    } // <init>(boolean)

    
Experimental constructor. /** Experimental constructor. */
    public DeferredDocumentImpl(boolean namespaces, boolean grammarAccess) {
        super(grammarAccess);

        needsSyncData(true);
        needsSyncChildren(true);

        fNamespacesEnabled = namespaces;

    } // <init>(boolean,boolean)

    //
    // Public methods
    //

    
Retrieve information describing the abilities of this particular
DOM implementation. Intended to support applications that may be
using DOMs retrieved from several different sources, potentially
with different underlying representations.
/**
     * Retrieve information describing the abilities of this particular
     * DOM implementation. Intended to support applications that may be
     * using DOMs retrieved from several different sources, potentially
     * with different underlying representations.
     */
    public DOMImplementation getImplementation() {
        // Currently implemented as a singleton, since it's hardcoded
        // information anyway.
        return DeferredDOMImplementationImpl.getDOMImplementation();
    }

    
Returns the cached parser.getNamespaces() value./** Returns the cached parser.getNamespaces() value.*/
    boolean getNamespacesEnabled() {
        return fNamespacesEnabled;
    }

    void setNamespacesEnabled(boolean enable) {
        fNamespacesEnabled = enable;
    }

    // internal factory methods

    
Creates a document node in the table. /** Creates a document node in the table. */
    public int createDeferredDocument() {
        int nodeIndex = createNode(Node.DOCUMENT_NODE);
        return nodeIndex;
    }

    
Creates a doctype. /** Creates a doctype. */
    public int createDeferredDocumentType(String rootElementName,
                                          String publicId, String systemId) {

        // create node
        int nodeIndex = createNode(Node.DOCUMENT_TYPE_NODE);
        int chunk     = nodeIndex >> CHUNK_SHIFT;
        int index     = nodeIndex & CHUNK_MASK;

        // save name, public id, system id
        setChunkValue(fNodeName, rootElementName, chunk, index);
        setChunkValue(fNodeValue, publicId, chunk, index);
        setChunkValue(fNodeURI, systemId, chunk, index);

        // return node index
        return nodeIndex;

    } // createDeferredDocumentType(String,String,String):int

    public void setInternalSubset(int doctypeIndex, String subset) {
        int chunk     = doctypeIndex >> CHUNK_SHIFT;
        int index     = doctypeIndex & CHUNK_MASK;

        // create extra data node to store internal subset
        int extraDataIndex = createNode(Node.DOCUMENT_TYPE_NODE);
        int echunk = extraDataIndex >> CHUNK_SHIFT;
        int eindex = extraDataIndex & CHUNK_MASK;
        setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
        setChunkValue(fNodeValue, subset, echunk, eindex);
    }

    
Creates a notation in the table. /** Creates a notation in the table. */
    public int createDeferredNotation(String notationName,
                                      String publicId, String systemId, String baseURI) {

        // create node
        int nodeIndex = createNode(Node.NOTATION_NODE);
        int chunk     = nodeIndex >> CHUNK_SHIFT;
        int index     = nodeIndex & CHUNK_MASK;


        // create extra data node
        int extraDataIndex = createNode(Node.NOTATION_NODE);
        int echunk = extraDataIndex >> CHUNK_SHIFT;
        int eindex = extraDataIndex & CHUNK_MASK;

        // save name, public id, system id, and notation name
        setChunkValue(fNodeName, notationName, chunk, index);
        setChunkValue(fNodeValue, publicId, chunk, index);
        setChunkValue(fNodeURI, systemId, chunk, index);

        // in extra data node set baseURI value
        setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
        setChunkValue(fNodeName, baseURI, echunk, eindex);

        // return node index
        return nodeIndex;

    } // createDeferredNotation(String,String,String):int

    
Creates an entity in the table. /** Creates an entity in the table. */
    public int createDeferredEntity(String entityName, String publicId,
                                    String systemId, String notationName,
                                    String baseURI) {
        // create node
        int nodeIndex = createNode(Node.ENTITY_NODE);
        int chunk     = nodeIndex >> CHUNK_SHIFT;
        int index     = nodeIndex & CHUNK_MASK;

        // create extra data node
        int extraDataIndex = createNode(Node.ENTITY_NODE);
        int echunk = extraDataIndex >> CHUNK_SHIFT;
        int eindex = extraDataIndex & CHUNK_MASK;

        // save name, public id, system id, and notation name
        setChunkValue(fNodeName, entityName, chunk, index);
        setChunkValue(fNodeValue, publicId, chunk, index);
        setChunkValue(fNodeURI, systemId, chunk, index);
        setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
        // set other values in the extra chunk
        // notation
        setChunkValue(fNodeName, notationName, echunk, eindex);
        // version  L3
        setChunkValue(fNodeValue, null, echunk, eindex);
        // encoding L3
        setChunkValue(fNodeURI, null, echunk, eindex);


        int extraDataIndex2 = createNode(Node.ENTITY_NODE);
        int echunk2 = extraDataIndex2 >> CHUNK_SHIFT;
        int eindex2 = extraDataIndex2 & CHUNK_MASK;

        setChunkIndex(fNodeExtra, extraDataIndex2, echunk, eindex);

        // baseURI
        setChunkValue(fNodeName, baseURI, echunk2, eindex2);

        // return node index
        return nodeIndex;

    } // createDeferredEntity(String,String,String,String):int

    public String getDeferredEntityBaseURI (int entityIndex){
        if (entityIndex != -1) {
            int extraDataIndex = getNodeExtra(entityIndex, false);
            extraDataIndex = getNodeExtra(extraDataIndex, false);
            return getNodeName (extraDataIndex, false);
        }
        return null;
    }

    // DOM Level 3: setting encoding and version
    public void setEntityInfo(int currentEntityDecl,
                              String version, String encoding){
        int eNodeIndex = getNodeExtra(currentEntityDecl, false);
        if (eNodeIndex !=-1) {
            int echunk = eNodeIndex >> CHUNK_SHIFT;
            int eindex = eNodeIndex & CHUNK_MASK;
            setChunkValue(fNodeValue, version, echunk, eindex);
            setChunkValue(fNodeURI, encoding, echunk, eindex);
        }
    }

    // DOM Level 3: sets element TypeInfo
    public void setTypeInfo(int elementNodeIndex, Object type) {
        int elementChunk     = elementNodeIndex >> CHUNK_SHIFT;
        int elementIndex     = elementNodeIndex & CHUNK_MASK;
        setChunkValue(fNodeValue, type, elementChunk, elementIndex);
    }

    
DOM Internal
An attribute specifying the actual encoding of this document. This is
null otherwise.

 This attribute represents the property [character encoding scheme]
defined in .
/**
     * DOM Internal
     *
     * An attribute specifying the actual encoding of this document. This is
     * <code>null</code> otherwise.
     * <br> This attribute represents the property [character encoding scheme]
     * defined in .
     */
    public void setInputEncoding(int currentEntityDecl, String value){
        // get first extra data chunk
        int nodeIndex = getNodeExtra(currentEntityDecl, false);
        // get second extra data chunk
        int extraDataIndex = getNodeExtra(nodeIndex, false);

        int echunk = extraDataIndex >> CHUNK_SHIFT;
        int eindex = extraDataIndex & CHUNK_MASK;

        setChunkValue(fNodeValue, value, echunk, eindex);

    }

    
Creates an entity reference node in the table. /** Creates an entity reference node in the table. */
    public int createDeferredEntityReference(String name, String baseURI) {

        // create node
        int nodeIndex = createNode(Node.ENTITY_REFERENCE_NODE);
        int chunk     = nodeIndex >> CHUNK_SHIFT;
        int index     = nodeIndex & CHUNK_MASK;
        setChunkValue(fNodeName, name, chunk, index);
        setChunkValue(fNodeValue, baseURI, chunk, index);

        // return node index
        return nodeIndex;

    } // createDeferredEntityReference(String):int


    
Creates an element node with a URI in the table and type information.
Deprecated:
/**
     * Creates an element node with a URI in the table and type information.
     * @deprecated
     */
    @Deprecated
    public int createDeferredElement(String elementURI, String elementName,
                                      Object type) {

        // create node
        int elementNodeIndex = createNode(Node.ELEMENT_NODE);
        int elementChunk     = elementNodeIndex >> CHUNK_SHIFT;
        int elementIndex     = elementNodeIndex & CHUNK_MASK;
        setChunkValue(fNodeName, elementName, elementChunk, elementIndex);
        setChunkValue(fNodeURI, elementURI, elementChunk, elementIndex);
        setChunkValue(fNodeValue, type, elementChunk, elementIndex);

        // return node index
        return elementNodeIndex;

    } // createDeferredElement(String,String,Object):int

    
Creates an element node in the table.
Deprecated:
/**
     * Creates an element node in the table.
     * @deprecated
     */
    @Deprecated
    public int createDeferredElement(String elementName) {
        return createDeferredElement(null, elementName);
    }

    
Creates an element node with a URI in the table.
/**
     * Creates an element node with a URI in the table.
     */
    public int createDeferredElement(String elementURI, String elementName) {

        // create node
        int elementNodeIndex = createNode(Node.ELEMENT_NODE);
        int elementChunk     = elementNodeIndex >> CHUNK_SHIFT;
        int elementIndex     = elementNodeIndex & CHUNK_MASK;
        setChunkValue(fNodeName, elementName, elementChunk, elementIndex);
        setChunkValue(fNodeURI, elementURI, elementChunk, elementIndex);

        // return node index
        return elementNodeIndex;

    } // createDeferredElement(String,String):int


        
This method is used by the DOMParser to create attributes.
Params:
elementNodeIndex – 
attrName – 
attrURI – 
attrValue – 
specified – 
id – 
type – 
Returns:
int/**
         * This method is used by the DOMParser to create attributes.
         * @param elementNodeIndex
         * @param attrName
         * @param attrURI
         * @param attrValue
         * @param specified
         * @param id
         * @param type
         * @return int
         */
        public int setDeferredAttribute(int elementNodeIndex,
                                        String attrName,
                                        String attrURI,
                                        String attrValue,
                                        boolean specified,
                                        boolean id,
                                        Object type) {

                // create attribute
                int attrNodeIndex = createDeferredAttribute(attrName, attrURI, attrValue, specified);
                int attrChunk = attrNodeIndex >> CHUNK_SHIFT;
                int attrIndex = attrNodeIndex & CHUNK_MASK;
                // set attribute's parent to element
                setChunkIndex(fNodeParent, elementNodeIndex, attrChunk, attrIndex);

                int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
                int elementIndex = elementNodeIndex & CHUNK_MASK;

                // get element's last attribute
                int lastAttrNodeIndex = getChunkIndex(fNodeExtra, elementChunk, elementIndex);
                if (lastAttrNodeIndex != 0) {
                        // add link from new attribute to last attribute
                        setChunkIndex(fNodePrevSib, lastAttrNodeIndex, attrChunk, attrIndex);
                }
                // add link from element to new last attribute
                setChunkIndex(fNodeExtra, attrNodeIndex, elementChunk, elementIndex);

                int extra = getChunkIndex(fNodeExtra, attrChunk, attrIndex);
                if (id) {
                        extra = extra | ID;
                        setChunkIndex(fNodeExtra, extra, attrChunk, attrIndex);
                        String value = getChunkValue(fNodeValue, attrChunk, attrIndex);
                        putIdentifier(value, elementNodeIndex);
                }
                // store type information
                if (type != null) {
                        int extraDataIndex = createNode(DeferredNode.TYPE_NODE);
                        int echunk = extraDataIndex >> CHUNK_SHIFT;
                        int eindex = extraDataIndex & CHUNK_MASK;

                        setChunkIndex(fNodeLastChild, extraDataIndex, attrChunk, attrIndex);
                        setChunkValue(fNodeValue, type, echunk, eindex);
                }

                // return node index
                return attrNodeIndex;
        }

    
Creates an attribute in the table. /** Creates an attribute in the table. */
    public int createDeferredAttribute(String attrName, String attrValue,
                                       boolean specified) {
        return createDeferredAttribute(attrName, null, attrValue, specified);
    }

    
Creates an attribute with a URI in the table. /** Creates an attribute with a URI in the table. */
    public int createDeferredAttribute(String attrName, String attrURI,
                                       String attrValue, boolean specified) {

        // create node
        int nodeIndex = createNode(NodeImpl.ATTRIBUTE_NODE);
        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        setChunkValue(fNodeName, attrName, chunk, index);
        setChunkValue(fNodeURI, attrURI, chunk, index);
        setChunkValue(fNodeValue, attrValue, chunk, index);
        int extra = specified ? SPECIFIED : 0;
        setChunkIndex(fNodeExtra, extra, chunk, index);

        // return node index
        return nodeIndex;

    } // createDeferredAttribute(String,String,String,boolean):int

    
Creates an element definition in the table./** Creates an element definition in the table.*/
    public int createDeferredElementDefinition(String elementName) {

        // create node
        int nodeIndex = createNode(NodeImpl.ELEMENT_DEFINITION_NODE);
        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        setChunkValue(fNodeName, elementName, chunk, index);

        // return node index
        return nodeIndex;

    } // createDeferredElementDefinition(String):int

    
Creates a text node in the table. /** Creates a text node in the table. */
    public int createDeferredTextNode(String data,
                                      boolean ignorableWhitespace) {

        // create node
        int nodeIndex = createNode(Node.TEXT_NODE);
        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        setChunkValue(fNodeValue, data, chunk, index);
        // use extra to store ignorableWhitespace info
        setChunkIndex(fNodeExtra, ignorableWhitespace ?  1 : 0, chunk, index);

        // return node index
        return nodeIndex;

    } // createDeferredTextNode(String,boolean):int

    
Creates a CDATA section node in the table. /** Creates a CDATA section node in the table. */
    public int createDeferredCDATASection(String data) {

        // create node
        int nodeIndex = createNode(Node.CDATA_SECTION_NODE);
        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        setChunkValue(fNodeValue, data, chunk, index);

        // return node index
        return nodeIndex;

    } // createDeferredCDATASection(String):int

    
Creates a processing instruction node in the table. /** Creates a processing instruction node in the table. */
    public int createDeferredProcessingInstruction(String target,
                                                   String data) {
        // create node
        int nodeIndex = createNode(Node.PROCESSING_INSTRUCTION_NODE);
        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        setChunkValue(fNodeName, target, chunk, index);
        setChunkValue(fNodeValue, data, chunk, index);
        // return node index
        return nodeIndex;

    } // createDeferredProcessingInstruction(String,String):int

    
Creates a comment node in the table. /** Creates a comment node in the table. */
    public int createDeferredComment(String data) {

        // create node
        int nodeIndex = createNode(Node.COMMENT_NODE);
        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        setChunkValue(fNodeValue, data, chunk, index);

        // return node index
        return nodeIndex;

    } // createDeferredComment(String):int

    
Creates a clone of the specified node. /** Creates a clone of the specified node. */
    public int cloneNode(int nodeIndex, boolean deep) {

        // clone immediate node

        int nchunk = nodeIndex >> CHUNK_SHIFT;
        int nindex = nodeIndex & CHUNK_MASK;
        int nodeType = fNodeType[nchunk][nindex];
        int cloneIndex = createNode((short)nodeType);
        int cchunk = cloneIndex >> CHUNK_SHIFT;
        int cindex = cloneIndex & CHUNK_MASK;
        setChunkValue(fNodeName, fNodeName[nchunk][nindex], cchunk, cindex);
        setChunkValue(fNodeValue, fNodeValue[nchunk][nindex], cchunk, cindex);
        setChunkValue(fNodeURI, fNodeURI[nchunk][nindex], cchunk, cindex);
        int extraIndex = fNodeExtra[nchunk][nindex];
        if (extraIndex != -1) {
            if (nodeType != Node.ATTRIBUTE_NODE && nodeType != Node.TEXT_NODE) {
                extraIndex = cloneNode(extraIndex, false);
            }
            setChunkIndex(fNodeExtra, extraIndex, cchunk, cindex);
        }

        // clone and attach children
        if (deep) {
            int prevIndex = -1;
            int childIndex = getLastChild(nodeIndex, false);
            while (childIndex != -1) {
                int clonedChildIndex = cloneNode(childIndex, deep);
                insertBefore(cloneIndex, clonedChildIndex, prevIndex);
                prevIndex = clonedChildIndex;
                childIndex = getRealPrevSibling(childIndex, false);
            }


        }

        // return cloned node index
        return cloneIndex;

    } // cloneNode(int,boolean):int

    
Appends a child to the specified parent in the table. /** Appends a child to the specified parent in the table. */
    public void appendChild(int parentIndex, int childIndex) {

        // append parent index
        int pchunk = parentIndex >> CHUNK_SHIFT;
        int pindex = parentIndex & CHUNK_MASK;
        int cchunk = childIndex >> CHUNK_SHIFT;
        int cindex = childIndex & CHUNK_MASK;
        setChunkIndex(fNodeParent, parentIndex, cchunk, cindex);

        // set previous sibling of new child
        int olast = getChunkIndex(fNodeLastChild, pchunk, pindex);
        setChunkIndex(fNodePrevSib, olast, cchunk, cindex);

        // update parent's last child
        setChunkIndex(fNodeLastChild, childIndex, pchunk, pindex);

    } // appendChild(int,int)

    
Adds an attribute node to the specified element. /** Adds an attribute node to the specified element. */
    public int setAttributeNode(int elemIndex, int attrIndex) {

        int echunk = elemIndex >> CHUNK_SHIFT;
        int eindex = elemIndex & CHUNK_MASK;
        int achunk = attrIndex >> CHUNK_SHIFT;
        int aindex = attrIndex & CHUNK_MASK;

        // see if this attribute is already here
        String attrName = getChunkValue(fNodeName, achunk, aindex);
        int oldAttrIndex = getChunkIndex(fNodeExtra, echunk, eindex);
        int nextIndex = -1;
        int oachunk = -1;
        int oaindex = -1;
        while (oldAttrIndex != -1) {
            oachunk = oldAttrIndex >> CHUNK_SHIFT;
            oaindex = oldAttrIndex & CHUNK_MASK;
            String oldAttrName = getChunkValue(fNodeName, oachunk, oaindex);
            if (oldAttrName.equals(attrName)) {
                break;
            }
            nextIndex = oldAttrIndex;
            oldAttrIndex = getChunkIndex(fNodePrevSib, oachunk, oaindex);
        }

        // remove old attribute
        if (oldAttrIndex != -1) {

            // patch links
            int prevIndex = getChunkIndex(fNodePrevSib, oachunk, oaindex);
            if (nextIndex == -1) {
                setChunkIndex(fNodeExtra, prevIndex, echunk, eindex);
            }
            else {
                int pchunk = nextIndex >> CHUNK_SHIFT;
                int pindex = nextIndex & CHUNK_MASK;
                setChunkIndex(fNodePrevSib, prevIndex, pchunk, pindex);
            }

            // remove connections to siblings
            clearChunkIndex(fNodeType, oachunk, oaindex);
            clearChunkValue(fNodeName, oachunk, oaindex);
            clearChunkValue(fNodeValue, oachunk, oaindex);
            clearChunkIndex(fNodeParent, oachunk, oaindex);
            clearChunkIndex(fNodePrevSib, oachunk, oaindex);
            int attrTextIndex =
                clearChunkIndex(fNodeLastChild, oachunk, oaindex);
            int atchunk = attrTextIndex >> CHUNK_SHIFT;
            int atindex = attrTextIndex & CHUNK_MASK;
            clearChunkIndex(fNodeType, atchunk, atindex);
            clearChunkValue(fNodeValue, atchunk, atindex);
            clearChunkIndex(fNodeParent, atchunk, atindex);
            clearChunkIndex(fNodeLastChild, atchunk, atindex);
        }

        // add new attribute
        int prevIndex = getChunkIndex(fNodeExtra, echunk, eindex);
        setChunkIndex(fNodeExtra, attrIndex, echunk, eindex);
        setChunkIndex(fNodePrevSib, prevIndex, achunk, aindex);

        // return
        return oldAttrIndex;

    } // setAttributeNode(int,int):int


    
Adds an attribute node to the specified element. /** Adds an attribute node to the specified element. */
    public void setIdAttributeNode(int elemIndex, int attrIndex) {

        int chunk = attrIndex >> CHUNK_SHIFT;
        int index = attrIndex & CHUNK_MASK;
        int extra = getChunkIndex(fNodeExtra, chunk, index);
        extra = extra | ID;
        setChunkIndex(fNodeExtra, extra, chunk, index);

        String value = getChunkValue(fNodeValue, chunk, index);
        putIdentifier(value, elemIndex);
    }


    
Sets type of attribute /** Sets type of attribute */
    public void setIdAttribute(int attrIndex) {

        int chunk = attrIndex >> CHUNK_SHIFT;
        int index = attrIndex & CHUNK_MASK;
        int extra = getChunkIndex(fNodeExtra, chunk, index);
        extra = extra | ID;
        setChunkIndex(fNodeExtra, extra, chunk, index);
    }

    
Inserts a child before the specified node in the table. /** Inserts a child before the specified node in the table. */
    public int insertBefore(int parentIndex, int newChildIndex, int refChildIndex) {

        if (refChildIndex == -1) {
            appendChild(parentIndex, newChildIndex);
            return newChildIndex;
        }

        int nchunk = newChildIndex >> CHUNK_SHIFT;
        int nindex = newChildIndex & CHUNK_MASK;
        int rchunk = refChildIndex >> CHUNK_SHIFT;
        int rindex = refChildIndex & CHUNK_MASK;
        int previousIndex = getChunkIndex(fNodePrevSib, rchunk, rindex);
        setChunkIndex(fNodePrevSib, newChildIndex, rchunk, rindex);
        setChunkIndex(fNodePrevSib, previousIndex, nchunk, nindex);

        return newChildIndex;

    } // insertBefore(int,int,int):int

    
Sets the last child of the parentIndex to childIndex. /** Sets the last child of the parentIndex to childIndex. */
    public void setAsLastChild(int parentIndex, int childIndex) {
        int pchunk = parentIndex >> CHUNK_SHIFT;
        int pindex = parentIndex & CHUNK_MASK;
        setChunkIndex(fNodeLastChild, childIndex, pchunk, pindex);
    } // setAsLastChild(int,int)

    
Returns the parent node of the given node.
Calling this method does not free the parent index.
/**
     * Returns the parent node of the given node.
     * <em>Calling this method does not free the parent index.</em>
     */
    public int getParentNode(int nodeIndex) {
        return getParentNode(nodeIndex, false);
    }

    
Returns the parent node of the given node.
Params:
free – True to free parent node./**
     * Returns the parent node of the given node.
     * @param free True to free parent node.
     */
    public int getParentNode(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return -1;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        return free ? clearChunkIndex(fNodeParent, chunk, index)
                    : getChunkIndex(fNodeParent, chunk, index);

    } // getParentNode(int):int

    
Returns the last child of the given node. /** Returns the last child of the given node. */
    public int getLastChild(int nodeIndex) {
        return getLastChild(nodeIndex, true);
    }

    
Returns the last child of the given node.
Params:
free – True to free child index./**
     * Returns the last child of the given node.
     * @param free True to free child index.
     */
    public int getLastChild(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return -1;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        return free ? clearChunkIndex(fNodeLastChild, chunk, index)
                    : getChunkIndex(fNodeLastChild, chunk, index);

    } // getLastChild(int,boolean):int

    
Returns the prev sibling of the given node.
This is post-normalization of Text Nodes.
/**
     * Returns the prev sibling of the given node.
     * This is post-normalization of Text Nodes.
     */
    public int getPrevSibling(int nodeIndex) {
        return getPrevSibling(nodeIndex, true);
    }

    
Returns the prev sibling of the given node.
Params:
free – True to free sibling index./**
     * Returns the prev sibling of the given node.
     * @param free True to free sibling index.
     */
    public int getPrevSibling(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return -1;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        int type = getChunkIndex(fNodeType, chunk, index);
        if (type == Node.TEXT_NODE) {
            do {
                nodeIndex = getChunkIndex(fNodePrevSib, chunk, index);
                if (nodeIndex == -1) {
                    break;
                }
                chunk = nodeIndex >> CHUNK_SHIFT;
                index = nodeIndex & CHUNK_MASK;
                type = getChunkIndex(fNodeType, chunk, index);
            } while (type == Node.TEXT_NODE);
        }
        else {
            nodeIndex = getChunkIndex(fNodePrevSib, chunk, index);
        }

        return nodeIndex;

    } // getPrevSibling(int,boolean):int

    
Returns the real prev sibling of the given node,
directly from the data structures. Used by TextImpl#getNodeValue()
to normalize values.
/**
     * Returns the <i>real</i> prev sibling of the given node,
     * directly from the data structures. Used by TextImpl#getNodeValue()
     * to normalize values.
     */
    public int getRealPrevSibling(int nodeIndex) {
        return getRealPrevSibling(nodeIndex, true);
    }

    
Returns the real prev sibling of the given node.
Params:
free – True to free sibling index./**
     * Returns the <i>real</i> prev sibling of the given node.
     * @param free True to free sibling index.
     */
    public int getRealPrevSibling(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return -1;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        return free ? clearChunkIndex(fNodePrevSib, chunk, index)
                    : getChunkIndex(fNodePrevSib, chunk, index);

    } // getReadPrevSibling(int,boolean):int

    
Returns the index of the element definition in the table
with the specified name index, or -1 if no such definition
exists.
/**
     * Returns the index of the element definition in the table
     * with the specified name index, or -1 if no such definition
     * exists.
     */
    public int lookupElementDefinition(String elementName) {

        if (fNodeCount > 1) {

            // find doctype
            int docTypeIndex = -1;
            int nchunk = 0;
            int nindex = 0;
            for (int index = getChunkIndex(fNodeLastChild, nchunk, nindex);
                 index != -1;
                 index = getChunkIndex(fNodePrevSib, nchunk, nindex)) {

                nchunk = index >> CHUNK_SHIFT;
                nindex = index  & CHUNK_MASK;
                if (getChunkIndex(fNodeType, nchunk, nindex) == Node.DOCUMENT_TYPE_NODE) {
                    docTypeIndex = index;
                    break;
                }
            }

            // find element definition
            if (docTypeIndex == -1) {
                return -1;
            }
            nchunk = docTypeIndex >> CHUNK_SHIFT;
            nindex = docTypeIndex & CHUNK_MASK;
            for (int index = getChunkIndex(fNodeLastChild, nchunk, nindex);
                 index != -1;
                 index = getChunkIndex(fNodePrevSib, nchunk, nindex)) {

                nchunk = index >> CHUNK_SHIFT;
                nindex = index & CHUNK_MASK;
                if (getChunkIndex(fNodeType, nchunk, nindex) ==
                                           NodeImpl.ELEMENT_DEFINITION_NODE
                 && getChunkValue(fNodeName, nchunk, nindex) == elementName) {
                    return index;
                }
            }
        }

        return -1;

    } // lookupElementDefinition(String):int

    
Instantiates the requested node object. /** Instantiates the requested node object. */
    public DeferredNode getNodeObject(int nodeIndex) {

        // is there anything to do?
        if (nodeIndex == -1) {
            return null;
        }

        // get node type
        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        int type = getChunkIndex(fNodeType, chunk, index);
        if (type != Node.TEXT_NODE && type != Node.CDATA_SECTION_NODE) {
            clearChunkIndex(fNodeType, chunk, index);
        }

        // create new node
        DeferredNode node = null;
        switch (type) {

            //
            // Standard DOM node types
            //

            case Node.ATTRIBUTE_NODE: {
                if (fNamespacesEnabled) {
                    node = new DeferredAttrNSImpl(this, nodeIndex);
                } else {
                    node = new DeferredAttrImpl(this, nodeIndex);
                }
                break;
            }

            case Node.CDATA_SECTION_NODE: {
                node = new DeferredCDATASectionImpl(this, nodeIndex);
                break;
            }

            case Node.COMMENT_NODE: {
                node = new DeferredCommentImpl(this, nodeIndex);
                break;
            }

            // NOTE: Document fragments can never be "fast".
            //
            //       The parser will never ask to create a document
            //       fragment during the parse. Document fragments
            //       are used by the application *after* the parse.
            //
            // case Node.DOCUMENT_FRAGMENT_NODE: { break; }
            case Node.DOCUMENT_NODE: {
                // this node is never "fast"
                node = this;
                break;
            }

            case Node.DOCUMENT_TYPE_NODE: {
                node = new DeferredDocumentTypeImpl(this, nodeIndex);
                // save the doctype node
                docType = (DocumentTypeImpl)node;
                break;
            }

            case Node.ELEMENT_NODE: {

                if (DEBUG_IDS) {
                    System.out.println("getNodeObject(ELEMENT_NODE): "+nodeIndex);
                }

                // create node
                if (fNamespacesEnabled) {
                    node = new DeferredElementNSImpl(this, nodeIndex);
                } else {
                    node = new DeferredElementImpl(this, nodeIndex);
                }

                // check to see if this element needs to be
                // registered for its ID attributes
                if (fIdElement != null) {
                    int idIndex = binarySearch(fIdElement, 0,
                                               fIdCount-1, nodeIndex);
                    while (idIndex != -1) {

                        if (DEBUG_IDS) {
                            System.out.println("  id index: "+idIndex);
                            System.out.println("  fIdName["+idIndex+
                                               "]: "+fIdName[idIndex]);
                        }

                        // register ID
                        String name = fIdName[idIndex];
                        if (name != null) {
                            if (DEBUG_IDS) {
                                System.out.println("  name: "+name);
                                System.out.print("getNodeObject()#");
                            }
                            putIdentifier0(name, (Element)node);
                            fIdName[idIndex] = null;
                        }

                        // continue if there are more IDs for
                        // this element
                        if (idIndex + 1 < fIdCount &&
                            fIdElement[idIndex + 1] == nodeIndex) {
                            idIndex++;
                        }
                        else {
                            idIndex = -1;
                        }
                    }
                }
                break;
            }

            case Node.ENTITY_NODE: {
                node = new DeferredEntityImpl(this, nodeIndex);
                break;
            }

            case Node.ENTITY_REFERENCE_NODE: {
                node = new DeferredEntityReferenceImpl(this, nodeIndex);
                break;
            }

            case Node.NOTATION_NODE: {
                node = new DeferredNotationImpl(this, nodeIndex);
                break;
            }

            case Node.PROCESSING_INSTRUCTION_NODE: {
                node = new DeferredProcessingInstructionImpl(this, nodeIndex);
                break;
            }

            case Node.TEXT_NODE: {
                node = new DeferredTextImpl(this, nodeIndex);
                break;
            }

            //
            // non-standard DOM node types
            //

            case NodeImpl.ELEMENT_DEFINITION_NODE: {
                node = new DeferredElementDefinitionImpl(this, nodeIndex);
                break;
            }

            default: {
                throw new IllegalArgumentException("type: "+type);
            }

        } // switch node type

        // store and return
        if (node != null) {
            return node;
        }

        // error
        throw new IllegalArgumentException();

    } // createNodeObject(int):Node

    
Returns the name of the given node. /** Returns the name of the given node. */
    public String getNodeName(int nodeIndex) {
        return getNodeName(nodeIndex, true);
    } // getNodeNameString(int):String

    
Returns the name of the given node.
Params:
free – True to free the string index./**
     * Returns the name of the given node.
     * @param free True to free the string index.
     */
    public String getNodeName(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return null;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        return free ? clearChunkValue(fNodeName, chunk, index)
                    : getChunkValue(fNodeName, chunk, index);

    } // getNodeName(int,boolean):String

    
Returns the real value of the given node. /** Returns the real value of the given node. */
    public String getNodeValueString(int nodeIndex) {
        return getNodeValueString(nodeIndex, true);
    } // getNodeValueString(int):String

    
Returns the real value of the given node.
Params:
free – True to free the string index./**
     * Returns the real value of the given node.
     * @param free True to free the string index.
     */
    public String getNodeValueString(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return null;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        String value = free ? clearChunkValue(fNodeValue, chunk, index)
                            : getChunkValue(fNodeValue, chunk, index);
        if (value == null) {
            return null;
        }

        int type  = getChunkIndex(fNodeType, chunk, index);
        if (type == Node.TEXT_NODE) {
            int prevSib = getRealPrevSibling(nodeIndex);
            if (prevSib != -1 &&
                getNodeType(prevSib, false) == Node.TEXT_NODE) {
                // append data that is stored in fNodeValue
                // REVISIT: for text nodes it works differently than for CDATA
                //          nodes.
                fStrChunks.add(value);
                do {
                    // go in reverse order: find last child, then
                    // its previous sibling, etc
                    chunk = prevSib >> CHUNK_SHIFT;
                    index = prevSib & CHUNK_MASK;
                    value = getChunkValue(fNodeValue, chunk, index);
                    fStrChunks.add(value);
                    prevSib = getChunkIndex(fNodePrevSib, chunk, index);
                    if (prevSib == -1) {
                        break;
                    }
                } while (getNodeType(prevSib, false) == Node.TEXT_NODE);

                int chunkCount = fStrChunks.size();

                // add to the buffer in the correct order.
                for (int i = chunkCount - 1; i >= 0; i--) {
                    fBufferStr.append(fStrChunks.get(i));
                }

                value = fBufferStr.toString();
                fStrChunks.clear();
                fBufferStr.setLength(0);
                return value;
            }
        }
        else if (type == Node.CDATA_SECTION_NODE) {
            // find if any other data stored in children
            int child = getLastChild(nodeIndex, false);
            if (child !=-1) {
                // append data that is stored in fNodeValue
                fBufferStr.append(value);
                while (child !=-1) {
                    // go in reverse order: find last child, then
                    // its previous sibling, etc
                   chunk = child >> CHUNK_SHIFT;
                    index = child & CHUNK_MASK;
                    value = getChunkValue(fNodeValue, chunk, index);
                    fStrChunks.add(value);
                    child = getChunkIndex(fNodePrevSib, chunk, index);
                }
                // add to the buffer in the correct order.
                for (int i=fStrChunks.size()-1; i>=0; i--) {
                     fBufferStr.append(fStrChunks.get(i));
                }

                value = fBufferStr.toString();
                fStrChunks.clear();
                fBufferStr.setLength(0);
                return value;
            }
        }

        return value;

    } // getNodeValueString(int,boolean):String

    
Returns the value of the given node.
/**
     * Returns the value of the given node.
     */
    public String getNodeValue(int nodeIndex) {
        return getNodeValue(nodeIndex, true);
    }

        
Clears the type info that is stored in the fNodeValue array
Params:
nodeIndex – 
Returns:
Object - type information for the attribute/element node/**
         * Clears the type info that is stored in the fNodeValue array
         * @param nodeIndex
         * @return Object - type information for the attribute/element node
         */
    public Object getTypeInfo(int nodeIndex) {
        if (nodeIndex == -1) {
            return null;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;


        Object value = fNodeValue[chunk] != null ? fNodeValue[chunk][index] : null;
        if (value != null) {
            fNodeValue[chunk][index] = null;
            RefCount c = (RefCount) fNodeValue[chunk][CHUNK_SIZE];
            c.fCount--;
            if (c.fCount == 0) {
                fNodeValue[chunk] = null;
            }
        }
        return value;
    }

    
Returns the value of the given node.
Params:
free – True to free the value index./**
     * Returns the value of the given node.
     * @param free True to free the value index.
     */
    public String getNodeValue(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return null;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        return free ? clearChunkValue(fNodeValue, chunk, index)
                    : getChunkValue(fNodeValue, chunk, index);

    } // getNodeValue(int,boolean):String

    
Returns the extra info of the given node.
Used by AttrImpl to store specified value (1 == true).
/**
     * Returns the extra info of the given node.
     * Used by AttrImpl to store specified value (1 == true).
     */
    public int getNodeExtra(int nodeIndex) {
        return getNodeExtra(nodeIndex, true);
    }

    
Returns the extra info of the given node.
Params:
free – True to free the value index./**
     * Returns the extra info of the given node.
     * @param free True to free the value index.
     */
    public int getNodeExtra(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return -1;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        return free ? clearChunkIndex(fNodeExtra, chunk, index)
                    : getChunkIndex(fNodeExtra, chunk, index);

    } // getNodeExtra(int,boolean):int

    
Returns the type of the given node. /** Returns the type of the given node. */
    public short getNodeType(int nodeIndex) {
        return getNodeType(nodeIndex, true);
    }

    
Returns the type of the given node.
Params:
free – True to free type index./**
     * Returns the type of the given node.
     * @param free True to free type index.
     */
    public short getNodeType(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return -1;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        return free ? (short)clearChunkIndex(fNodeType, chunk, index)
                    : (short)getChunkIndex(fNodeType, chunk, index);

    } // getNodeType(int):int

    
Returns the attribute value of the given name. /** Returns the attribute value of the given name. */
    public String getAttribute(int elemIndex, String name) {
        if (elemIndex == -1 || name == null) {
            return null;
        }
        int echunk = elemIndex >> CHUNK_SHIFT;
        int eindex = elemIndex & CHUNK_MASK;
        int attrIndex = getChunkIndex(fNodeExtra, echunk, eindex);
        while (attrIndex != -1) {
            int achunk = attrIndex >> CHUNK_SHIFT;
            int aindex = attrIndex & CHUNK_MASK;
            if (getChunkValue(fNodeName, achunk, aindex) == name) {
                return getChunkValue(fNodeValue, achunk, aindex);
            }
            attrIndex = getChunkIndex(fNodePrevSib, achunk, aindex);
        }
        return null;
    }

    
Returns the URI of the given node. /** Returns the URI of the given node. */
    public String getNodeURI(int nodeIndex) {
        return getNodeURI(nodeIndex, true);
    }

    
Returns the URI of the given node.
Params:
free – True to free URI index./**
     * Returns the URI of the given node.
     * @param free True to free URI index.
     */
    public String getNodeURI(int nodeIndex, boolean free) {

        if (nodeIndex == -1) {
            return null;
        }

        int chunk = nodeIndex >> CHUNK_SHIFT;
        int index = nodeIndex & CHUNK_MASK;
        return free ? clearChunkValue(fNodeURI, chunk, index)
                    : getChunkValue(fNodeURI, chunk, index);

    } // getNodeURI(int,int):String

    // identifier maintenance

    
Registers an identifier name with a specified element node. /** Registers an identifier name with a specified element node. */
    public void putIdentifier(String name, int elementNodeIndex) {

        if (DEBUG_IDS) {
            System.out.println("putIdentifier(" + name + ", "
                               + elementNodeIndex + ')' + " // " +
                               getChunkValue(fNodeName,
                                             elementNodeIndex >> CHUNK_SHIFT,
                                             elementNodeIndex & CHUNK_MASK));
        }

        // initialize arrays
        if (fIdName == null) {
            fIdName    = new String[64];
            fIdElement = new int[64];
        }

        // resize arrays
        if (fIdCount == fIdName.length) {
            String idName[] = new String[fIdCount * 2];
            System.arraycopy(fIdName, 0, idName, 0, fIdCount);
            fIdName = idName;

            int idElement[] = new int[idName.length];
            System.arraycopy(fIdElement, 0, idElement, 0, fIdCount);
            fIdElement = idElement;
        }

        // store identifier
        fIdName[fIdCount] = name;
        fIdElement[fIdCount] = elementNodeIndex;
        fIdCount++;

    } // putIdentifier(String,int)

    //
    // DEBUG
    //

    
Prints out the tables. /** Prints out the tables. */
    public void print() {

        if (DEBUG_PRINT_REF_COUNTS) {
            System.out.print("num\t");
            System.out.print("type\t");
            System.out.print("name\t");
            System.out.print("val\t");
            System.out.print("par\t");
            System.out.print("lch\t");
            System.out.print("psib");
            System.out.println();
            for (int i = 0; i < fNodeType.length; i++) {
                if (fNodeType[i] != null) {
                    // separator
                    System.out.print("--------");
                    System.out.print("--------");
                    System.out.print("--------");
                    System.out.print("--------");
                    System.out.print("--------");
                    System.out.print("--------");
                    System.out.print("--------");
                    System.out.println();

                    // ref count
                    System.out.print(i);
                    System.out.print('\t');
                    switch (fNodeType[i][CHUNK_SIZE]) {
                        case DocumentImpl.ELEMENT_DEFINITION_NODE: { System.out.print("EDef"); break; }
                        case Node.DOCUMENT_NODE: { System.out.print("Doc"); break; }
                        case Node.DOCUMENT_TYPE_NODE: { System.out.print("DType"); break; }
                        case Node.COMMENT_NODE: { System.out.print("Com"); break; }
                        case Node.PROCESSING_INSTRUCTION_NODE: { System.out.print("PI"); break; }
                        case Node.ELEMENT_NODE: { System.out.print("Elem"); break; }
                        case Node.ENTITY_NODE: { System.out.print("Ent"); break; }
                        case Node.ENTITY_REFERENCE_NODE: { System.out.print("ERef"); break; }
                        case Node.TEXT_NODE: { System.out.print("Text"); break; }
                        case Node.ATTRIBUTE_NODE: { System.out.print("Attr"); break; }
                        case DeferredNode.TYPE_NODE: { System.out.print("TypeInfo"); break; }
                        default: { System.out.print("?"+fNodeType[i][CHUNK_SIZE]); }
                    }
                    System.out.print('\t');
                    System.out.print(fNodeName[i][CHUNK_SIZE]);
                    System.out.print('\t');
                    System.out.print(fNodeValue[i][CHUNK_SIZE]);
                    System.out.print('\t');
                    System.out.print(fNodeURI[i][CHUNK_SIZE]);
                    System.out.print('\t');
                    System.out.print(fNodeParent[i][CHUNK_SIZE]);
                    System.out.print('\t');
                    System.out.print(fNodeLastChild[i][CHUNK_SIZE]);
                    System.out.print('\t');
                    System.out.print(fNodePrevSib[i][CHUNK_SIZE]);
                    System.out.print('\t');
                    System.out.print(fNodeExtra[i][CHUNK_SIZE]);
                    System.out.println();
                }
            }
        }

        if (DEBUG_PRINT_TABLES) {
            // This assumes that the document is small
            System.out.println("# start table");
            for (int i = 0; i < fNodeCount; i++) {
                int chunk = i >> CHUNK_SHIFT;
                int index = i & CHUNK_MASK;
                if (i % 10 == 0) {
                    System.out.print("num\t");
                    System.out.print("type\t");
                    System.out.print("name\t");
                    System.out.print("val\t");
                    System.out.print("uri\t");
                    System.out.print("par\t");
                    System.out.print("lch\t");
                    System.out.print("psib\t");
                    System.out.print("xtra");
                    System.out.println();
                }
                System.out.print(i);
                System.out.print('\t');
                switch (getChunkIndex(fNodeType, chunk, index)) {
                    case DocumentImpl.ELEMENT_DEFINITION_NODE: { System.out.print("EDef"); break; }
                    case Node.DOCUMENT_NODE: { System.out.print("Doc"); break; }
                    case Node.DOCUMENT_TYPE_NODE: { System.out.print("DType"); break; }
                    case Node.COMMENT_NODE: { System.out.print("Com"); break; }
                    case Node.PROCESSING_INSTRUCTION_NODE: { System.out.print("PI"); break; }
                    case Node.ELEMENT_NODE: { System.out.print("Elem"); break; }
                    case Node.ENTITY_NODE: { System.out.print("Ent"); break; }
                    case Node.ENTITY_REFERENCE_NODE: { System.out.print("ERef"); break; }
                    case Node.TEXT_NODE: { System.out.print("Text"); break; }
                    case Node.ATTRIBUTE_NODE: { System.out.print("Attr"); break; }
                    case DeferredNode.TYPE_NODE: { System.out.print("TypeInfo"); break; }
                    default: { System.out.print("?"+getChunkIndex(fNodeType, chunk, index)); }
                }
                System.out.print('\t');
                System.out.print(getChunkValue(fNodeName, chunk, index));
                System.out.print('\t');
                System.out.print(getNodeValue(chunk, index));
                System.out.print('\t');
                System.out.print(getChunkValue(fNodeURI, chunk, index));
                System.out.print('\t');
                System.out.print(getChunkIndex(fNodeParent, chunk, index));
                System.out.print('\t');
                System.out.print(getChunkIndex(fNodeLastChild, chunk, index));
                System.out.print('\t');
                System.out.print(getChunkIndex(fNodePrevSib, chunk, index));
                System.out.print('\t');
                System.out.print(getChunkIndex(fNodeExtra, chunk, index));
                System.out.println();
            }
            System.out.println("# end table");
        }

    } // print()

    //
    // DeferredNode methods
    //

    
Returns the node index. /** Returns the node index. */
    public int getNodeIndex() {
        return 0;
    }

    //
    // Protected methods
    //

    
Synchronizes the node's data. /** Synchronizes the node's data. */
    protected void synchronizeData() {

        // no need to sync in the future
        needsSyncData(false);

        // fluff up enough nodes to fill identifiers hash
        if (fIdElement != null) {

            // REVISIT: There has to be a more efficient way of
            //          doing this. But keep in mind that the
            //          tree can have been altered and re-ordered
            //          before all of the element nodes with ID
            //          attributes have been registered. For now
            //          this is reasonable and safe. -Ac

            IntVector path = new IntVector();
            for (int i = 0; i < fIdCount; i++) {

                // ignore if it's already been registered
                int elementNodeIndex = fIdElement[i];
                String idName      = fIdName[i];
                if (idName == null) {
                    continue;
                }

                // find path from this element to the root
                path.removeAllElements();
                int index = elementNodeIndex;
                do {
                    path.addElement(index);
                    int pchunk = index >> CHUNK_SHIFT;
                    int pindex = index & CHUNK_MASK;
                    index = getChunkIndex(fNodeParent, pchunk, pindex);
                } while (index != -1);

                // Traverse path (backwards), fluffing the elements
                // along the way. When this loop finishes, "place"
                // will contain the reference to the element node
                // we're interested in. -Ac
                Node place = this;
                for (int j = path.size() - 2; j >= 0; j--) {
                    index = path.elementAt(j);
                    Node child = place.getLastChild();
                    while (child != null) {
                        if (child instanceof DeferredNode) {
                            int nodeIndex =
                                ((DeferredNode)child).getNodeIndex();
                            if (nodeIndex == index) {
                                place = child;
                                break;
                            }
                        }
                        child = child.getPreviousSibling();
                    }
                }

                // register the element
                Element element = (Element)place;
                putIdentifier0(idName, element);
                fIdName[i] = null;

                // see if there are more IDs on this element
                while (i + 1 < fIdCount &&
                    fIdElement[i + 1] == elementNodeIndex) {
                    idName = fIdName[++i];
                    if (idName == null) {
                        continue;
                    }
                    putIdentifier0(idName, element);
                }
            }

        } // if identifiers

    } // synchronizeData()

    
Synchronizes the node's children with the internal structure.
Fluffing the children at once solves a lot of work to keep
the two structures in sync. The problem gets worse when
editing the tree -- this makes it a lot easier.
/**
     * Synchronizes the node's children with the internal structure.
     * Fluffing the children at once solves a lot of work to keep
     * the two structures in sync. The problem gets worse when
     * editing the tree -- this makes it a lot easier.
     */
    protected void synchronizeChildren() {

        if (needsSyncData()) {
            synchronizeData();
            /*
             * when we have elements with IDs this method is being recursively
             * called from synchronizeData, in which case we've already gone
             * through the following and we can now simply stop here.
             */
            if (!needsSyncChildren()) {
                return;
            }
        }

        // we don't want to generate any event for this so turn them off
        boolean orig = mutationEvents;
        mutationEvents = false;

        // no need to sync in the future
        needsSyncChildren(false);

        getNodeType(0);

        // create children and link them as siblings
        ChildNode first = null;
        ChildNode last = null;
        for (int index = getLastChild(0);
             index != -1;
             index = getPrevSibling(index)) {

            ChildNode node = (ChildNode)getNodeObject(index);
            if (last == null) {
                last = node;
            }
            else {
                first.previousSibling = node;
            }
            node.ownerNode = this;
            node.isOwned(true);
            node.nextSibling = first;
            first = node;

            // save doctype and document type
            int type = node.getNodeType();
            if (type == Node.ELEMENT_NODE) {
                docElement = (ElementImpl)node;
            }
            else if (type == Node.DOCUMENT_TYPE_NODE) {
                docType = (DocumentTypeImpl)node;
            }
        }

        if (first != null) {
            firstChild = first;
            first.isFirstChild(true);
            lastChild(last);
        }

        // set mutation events flag back to its original value
        mutationEvents = orig;

    } // synchronizeChildren()

    
Synchronizes the node's children with the internal structure.
Fluffing the children at once solves a lot of work to keep
the two structures in sync. The problem gets worse when
editing the tree -- this makes it a lot easier.
This is not directly used in this class but this method is
here so that it can be shared by all deferred subclasses of AttrImpl.
/**
     * Synchronizes the node's children with the internal structure.
     * Fluffing the children at once solves a lot of work to keep
     * the two structures in sync. The problem gets worse when
     * editing the tree -- this makes it a lot easier.
     * This is not directly used in this class but this method is
     * here so that it can be shared by all deferred subclasses of AttrImpl.
     */
    protected final void synchronizeChildren(AttrImpl a, int nodeIndex) {

        // we don't want to generate any event for this so turn them off
        boolean orig = getMutationEvents();
        setMutationEvents(false);

        // no need to sync in the future
        a.needsSyncChildren(false);

        // create children and link them as siblings or simply store the value
        // as a String if all we have is one piece of text
        int last = getLastChild(nodeIndex);
        int prev = getPrevSibling(last);
        if (prev == -1) {
            a.value = getNodeValueString(nodeIndex);
            a.hasStringValue(true);
        }
        else {
            ChildNode firstNode = null;
            ChildNode lastNode = null;
            for (int index = last; index != -1;
                 index = getPrevSibling(index)) {

                ChildNode node = (ChildNode) getNodeObject(index);
                if (lastNode == null) {
                    lastNode = node;
                }
                else {
                    firstNode.previousSibling = node;
                }
                node.ownerNode = a;
                node.isOwned(true);
                node.nextSibling = firstNode;
                firstNode = node;
            }
            if (lastNode != null) {
                a.value = firstNode; // firstChild = firstNode
                firstNode.isFirstChild(true);
                a.lastChild(lastNode);
            }
            a.hasStringValue(false);
        }

        // set mutation events flag back to its original value
        setMutationEvents(orig);

    } // synchronizeChildren(AttrImpl,int):void


    
Synchronizes the node's children with the internal structure.
Fluffing the children at once solves a lot of work to keep
the two structures in sync. The problem gets worse when
editing the tree -- this makes it a lot easier.
This is not directly used in this class but this method is
here so that it can be shared by all deferred subclasses of ParentNode.
/**
     * Synchronizes the node's children with the internal structure.
     * Fluffing the children at once solves a lot of work to keep
     * the two structures in sync. The problem gets worse when
     * editing the tree -- this makes it a lot easier.
     * This is not directly used in this class but this method is
     * here so that it can be shared by all deferred subclasses of ParentNode.
     */
    protected final void synchronizeChildren(ParentNode p, int nodeIndex) {

        // we don't want to generate any event for this so turn them off
        boolean orig = getMutationEvents();
        setMutationEvents(false);

        // no need to sync in the future
        p.needsSyncChildren(false);

        // create children and link them as siblings
        ChildNode firstNode = null;
        ChildNode lastNode = null;
        for (int index = getLastChild(nodeIndex);
             index != -1;
             index = getPrevSibling(index)) {

            ChildNode node = (ChildNode) getNodeObject(index);
            if (lastNode == null) {
                lastNode = node;
            }
            else {
                firstNode.previousSibling = node;
            }
            node.ownerNode = p;
            node.isOwned(true);
            node.nextSibling = firstNode;
            firstNode = node;
        }
        if (lastNode != null) {
            p.firstChild = firstNode;
            firstNode.isFirstChild(true);
            p.lastChild(lastNode);
        }

        // set mutation events flag back to its original value
        setMutationEvents(orig);

    } // synchronizeChildren(ParentNode,int):void

    // utility methods

    
Ensures that the internal tables are large enough. /** Ensures that the internal tables are large enough. */
    protected void ensureCapacity(int chunk) {
        if (fNodeType == null) {
            // create buffers
            fNodeType       = new int[INITIAL_CHUNK_COUNT][];
            fNodeName       = new Object[INITIAL_CHUNK_COUNT][];
            fNodeValue      = new Object[INITIAL_CHUNK_COUNT][];
            fNodeParent     = new int[INITIAL_CHUNK_COUNT][];
            fNodeLastChild  = new int[INITIAL_CHUNK_COUNT][];
            fNodePrevSib    = new int[INITIAL_CHUNK_COUNT][];
            fNodeURI        = new Object[INITIAL_CHUNK_COUNT][];
            fNodeExtra      = new int[INITIAL_CHUNK_COUNT][];
        }
        else if (fNodeType.length <= chunk) {
            // resize the tables
            int newsize = chunk * 2;

            int[][] newArray = new int[newsize][];
            System.arraycopy(fNodeType, 0, newArray, 0, chunk);
            fNodeType = newArray;

            Object[][] newStrArray = new Object[newsize][];
            System.arraycopy(fNodeName, 0, newStrArray, 0, chunk);
            fNodeName = newStrArray;

            newStrArray = new Object[newsize][];
            System.arraycopy(fNodeValue, 0, newStrArray, 0, chunk);
            fNodeValue = newStrArray;

            newArray = new int[newsize][];
            System.arraycopy(fNodeParent, 0, newArray, 0, chunk);
            fNodeParent = newArray;

            newArray = new int[newsize][];
            System.arraycopy(fNodeLastChild, 0, newArray, 0, chunk);
            fNodeLastChild = newArray;

            newArray = new int[newsize][];
            System.arraycopy(fNodePrevSib, 0, newArray, 0, chunk);
            fNodePrevSib = newArray;

            newStrArray = new Object[newsize][];
            System.arraycopy(fNodeURI, 0, newStrArray, 0, chunk);
            fNodeURI = newStrArray;

            newArray = new int[newsize][];
            System.arraycopy(fNodeExtra, 0, newArray, 0, chunk);
            fNodeExtra = newArray;
        }
        else if (fNodeType[chunk] != null) {
            // Done - there's sufficient capacity
            return;
        }

        // create new chunks
        createChunk(fNodeType, chunk);
        createChunk(fNodeName, chunk);
        createChunk(fNodeValue, chunk);
        createChunk(fNodeParent, chunk);
        createChunk(fNodeLastChild, chunk);
        createChunk(fNodePrevSib, chunk);
        createChunk(fNodeURI, chunk);
        createChunk(fNodeExtra, chunk);

        // Done
        return;

    } // ensureCapacity(int,int)

    
Creates a node of the specified type. /** Creates a node of the specified type. */
    protected int createNode(short nodeType) {
        // ensure tables are large enough
        int chunk = fNodeCount >> CHUNK_SHIFT;
        int index = fNodeCount & CHUNK_MASK;
        ensureCapacity(chunk);

        // initialize node
        setChunkIndex(fNodeType, nodeType, chunk, index);

        // return node index number
        return fNodeCount++;

    } // createNode(short):int

    
Performs a binary search for a target value in an array of
values. The array of values must be in ascending sorted order
before calling this method and all array values must be
non-negative.
Params:
values –  The array of values to search.
start –   The starting offset of the search.
end –     The ending offset of the search.
target –  The target value.
Returns:
This function will return the first occurrence
        of the target value, or -1 if the target value cannot
        be found./**
     * Performs a binary search for a target value in an array of
     * values. The array of values must be in ascending sorted order
     * before calling this method and all array values must be
     * non-negative.
     *
     * @param values  The array of values to search.
     * @param start   The starting offset of the search.
     * @param end     The ending offset of the search.
     * @param target  The target value.
     *
     * @return This function will return the <i>first</i> occurrence
     *         of the target value, or -1 if the target value cannot
     *         be found.
     */
    protected static int binarySearch(final int values[],
                                      int start, int end, int target) {

        if (DEBUG_IDS) {
            System.out.println("binarySearch(), target: "+target);
        }

        // look for target value
        while (start <= end) {

            // is this the one we're looking for?
            int middle = (start + end) >>> 1;
            int value  = values[middle];
            if (DEBUG_IDS) {
                System.out.print("  value: "+value+", target: "+target+" // ");
                print(values, start, end, middle, target);
            }
            if (value == target) {
                while (middle > 0 && values[middle - 1] == target) {
                    middle--;
                }
                if (DEBUG_IDS) {
                    System.out.println("FOUND AT "+middle);
                }
                return middle;
            }

            // is this point higher or lower?
            if (value > target) {
                end = middle - 1;
            }
            else {
                start = middle + 1;
            }

        } // while

        // not found
        if (DEBUG_IDS) {
            System.out.println("NOT FOUND!");
        }
        return -1;

    } // binarySearch(int[],int,int,int):int

    //
    // Private methods
    //
    private static final int[] INIT_ARRAY = new int[CHUNK_SIZE + 1];
    static {
        for (int i = 0; i < CHUNK_SIZE; i++) {
            INIT_ARRAY[i] = -1;
        }
    }
    
Creates the specified chunk in the given array of chunks. /** Creates the specified chunk in the given array of chunks. */
    private final void createChunk(int data[][], int chunk) {
        data[chunk] = new int[CHUNK_SIZE + 1];
        System.arraycopy(INIT_ARRAY, 0, data[chunk], 0, CHUNK_SIZE);
    }

    static final class RefCount {
        int fCount;
    }

    private final void createChunk(Object data[][], int chunk) {
        data[chunk] = new Object[CHUNK_SIZE + 1];
        data[chunk][CHUNK_SIZE] = new RefCount();
    }

    
Sets the specified value in the given of data at the chunk and index.
Returns:
Returns the old value./**
     * Sets the specified value in the given of data at the chunk and index.
     *
     * @return Returns the old value.
     */
    private final int setChunkIndex(int data[][], int value,
                                    int chunk, int index) {
        if (value == -1) {
            return clearChunkIndex(data, chunk, index);
        }
        int [] dataChunk = data[chunk];
        // Re-create chunk if it was deleted.
        if (dataChunk == null) {
            createChunk(data, chunk);
            dataChunk = data[chunk];
        }
        int ovalue = dataChunk[index];
        if (ovalue == -1) {
            dataChunk[CHUNK_SIZE]++;
        }
        dataChunk[index] = value;
        return ovalue;
    }
    private final String setChunkValue(Object data[][], Object value,
                                       int chunk, int index) {
        if (value == null) {
            return clearChunkValue(data, chunk, index);
        }
        Object [] dataChunk = data[chunk];
        // Re-create chunk if it was deleted.
        if (dataChunk == null) {
            createChunk(data, chunk);
            dataChunk = data[chunk];
        }
        String ovalue = (String) dataChunk[index];
        if (ovalue == null) {
            RefCount c = (RefCount) dataChunk[CHUNK_SIZE];
            c.fCount++;
        }
        dataChunk[index] = value;
        return ovalue;
    }

    
Returns the specified value in the given data at the chunk and index.
/**
     * Returns the specified value in the given data at the chunk and index.
     */
    private final int getChunkIndex(int data[][], int chunk, int index) {
        return data[chunk] != null ? data[chunk][index] : -1;
    }
    private final String getChunkValue(Object data[][], int chunk, int index) {
        return data[chunk] != null ? (String) data[chunk][index] : null;
    }
    private final String getNodeValue(int chunk, int index) {
        Object data = fNodeValue[chunk][index];
        if (data == null){
            return null;
        }
        else if (data instanceof String){
            return (String)data;
        }
        else {
            // type information
            return data.toString();
        }
    }


    
Clears the specified value in the given data at the chunk and index.
Note that this method will clear the given chunk if the reference
count becomes zero.
Returns:
Returns the old value./**
     * Clears the specified value in the given data at the chunk and index.
     * Note that this method will clear the given chunk if the reference
     * count becomes zero.
     *
     * @return Returns the old value.
     */
    private final int clearChunkIndex(int data[][], int chunk, int index) {
        int value = data[chunk] != null ? data[chunk][index] : -1;
        if (value != -1) {
            data[chunk][CHUNK_SIZE]--;
            data[chunk][index] = -1;
            if (data[chunk][CHUNK_SIZE] == 0) {
                data[chunk] = null;
            }
        }
        return value;
    }
    private final String clearChunkValue(Object data[][],
                                         int chunk, int index) {
        String value = data[chunk] != null ? (String)data[chunk][index] : null;
        if (value != null) {
            data[chunk][index] = null;
            RefCount c = (RefCount) data[chunk][CHUNK_SIZE];
            c.fCount--;
            if (c.fCount == 0) {
                data[chunk] = null;
            }
        }
        return value;
    }

    
This version of putIdentifier is needed to avoid fluffing
all of the paths to ID attributes when a node object is
created that contains an ID attribute.
/**
     * This version of putIdentifier is needed to avoid fluffing
     * all of the paths to ID attributes when a node object is
     * created that contains an ID attribute.
     */
    private final void putIdentifier0(String idName, Element element) {

        if (DEBUG_IDS) {
            System.out.println("putIdentifier0("+
                               idName+", "+
                               element+')');
        }

        // create Map
        if (identifiers == null) {
            identifiers = new HashMap<>();
        }

        // save ID and its associated element
        identifiers.put(idName, element);

    } // putIdentifier0(String,Element)

    
Prints the ID array. /** Prints the ID array. */
    private static void print(int values[], int start, int end,
                              int middle, int target) {

        if (DEBUG_IDS) {
            System.out.print(start);
            System.out.print(" [");
            for (int i = start; i < end; i++) {
                if (middle == i) {
                    System.out.print("!");
                }
                System.out.print(values[i]);
                if (values[i] == target) {
                    System.out.print("*");
                }
                if (i < end - 1) {
                    System.out.print(" ");
                }
            }
            System.out.println("] "+end);
        }

    } // print(int[],int,int,int,int)

    //
    // Classes
    //

    
A simple integer vector.
/**
     * A simple integer vector.
     */
    static final class IntVector {

        //
        // Data
        //

        
Data. /** Data. */
        private int data[];

        
Size. /** Size. */
        private int size;

        //
        // Public methods
        //

        
Returns the length of this vector. /** Returns the length of this vector. */
        public int size() {
            return size;
        }

        
Returns the element at the specified index. /** Returns the element at the specified index. */
        public int elementAt(int index) {
            return data[index];
        }

        
Appends an element to the end of the vector. /** Appends an element to the end of the vector. */
        public void addElement(int element) {
            ensureCapacity(size + 1);
            data[size++] = element;
        }

        
Clears the vector. /** Clears the vector. */
        public void removeAllElements() {
            size = 0;
        }

        //
        // Private methods
        //

        
Makes sure that there is enough storage. /** Makes sure that there is enough storage. */
        private void ensureCapacity(int newsize) {

            if (data == null) {
                data = new int[newsize + 15];
            }
            else if (newsize > data.length) {
                int newdata[] = new int[newsize + 15];
                System.arraycopy(data, 0, newdata, 0, data.length);
                data = newdata;
            }

        } // ensureCapacity(int)

    } // class IntVector

} // class DeferredDocumentImpl