/*
 * The Apache Software License, Version 1.1
 *
 *
 * Copyright (c) 1999-2001 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Xerces" and "Apache Software Foundation" must
 *    not be used to endorse or promote products derived from this
 *    software without prior written permission. For written
 *    permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache",
 *    nor may "Apache" appear in their name, without prior written
 *    permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation and was
 * originally based on software copyright (c) 1999, International
 * Business Machines, Inc., http://www.apache.org.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */

package org.apache.xerces.dom;

import org.w3c.dom.Element;
import org.w3c.dom.Node;

import org.apache.xerces.xni.XMLAttributes;
import java.util.Vector;

/**
 * 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.
 *
 * @version $Id$
 * @since  PR-DOM-Level-1-19980818.
 */
public class DeferredDocumentImpl
    extends DocumentImpl
    implements DeferredNode {

    //
    // Constants
    //

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

    // debugging

    /** 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. */
    private static final boolean DEBUG_PRINT_TABLES = false;

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

    // protected

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

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

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

    /** 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. */
    protected transient int fNodeCount = 0;

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

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

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

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

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

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

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

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

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

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

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

    /** 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 StringBuffer fBufferStr = new StringBuffer();
    private transient final Vector fStrChunks = new Vector();

    //
    // Constructors
    //

    /**
     * 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.
     */
    public DeferredDocumentImpl(boolean namespacesEnabled) {
        this(namespacesEnabled, false);
    } // <init>(boolean)

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

        needsSyncData(true);
        needsSyncChildren(true);

        fNamespacesEnabled = namespaces;

    } // <init>(boolean,boolean)

    //
    // Public methods
    //

    /** 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. */
    public int createDeferredDocument() {
        int nodeIndex = createNode(Node.DOCUMENT_NODE);
        return nodeIndex;
    }

    /** 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;

        // added for DOM2: createDoctype factory method includes
        // name, publicID, systemID

        // create extra data node
        int extraDataIndex = createNode((short)0); // node type unimportant
        int echunk = extraDataIndex >> CHUNK_SHIFT;
        int eindex = extraDataIndex & CHUNK_MASK;

        // save name, public id, system id
        setChunkValue(fNodeName, rootElementName, chunk, index);
        setChunkValue(fNodeValue, publicId, chunk, index);
        setChunkValue(fNodeURI, systemId, chunk, index);
        setChunkIndex(fNodeExtra, extraDataIndex, 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;
        int extraDataIndex = fNodeExtra[chunk][index];
        int echunk = extraDataIndex >> CHUNK_SHIFT;
        int eindex = extraDataIndex & CHUNK_MASK;
        setChunkValue(fNodeValue, subset, echunk, eindex);
    }

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

        // create node
        int nodeIndex = createNode(Node.NOTATION_NODE);
        int chunk     = nodeIndex >> CHUNK_SHIFT;
        int index     = nodeIndex & 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);

        // return node index
        return nodeIndex;

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

    /** Creates an entity in the table. */
    public int createDeferredEntity(String entityName, String publicId,
                                    String systemId, String notationName) {
        // 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((short)0); // node type unimportant
        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);

        setChunkValue(fNodeName, notationName, echunk, eindex);

        // initialize encoding and version for DOM Level 3 - el
        setChunkValue(fNodeValue, null, echunk, eindex);
        setChunkValue(fNodeURI, null, echunk, eindex);
        // return node index
        return nodeIndex;

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

    // DOM Level 3 - el
    // 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);
        }
    }

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

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

        // return node index
        return nodeIndex;

    } // createDeferredEntityReference(String):int

    /** Creates an element node in the table. */
    public int createDeferredElement(String elementName,
                                     XMLAttributes attrList) {
        return createDeferredElement(null, elementName, attrList);
    }

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

        // 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);

        // create attributes
        int attrCount = attrList.getLength();
        int lastAttrNodeIndex = -1;
        int lastAttrChunk = -1;
        int lastAttrIndex = -1;
        for (int i = 0; i < attrCount; i++) {
            // create attribute
            int attrNodeIndex =
                createDeferredAttribute(attrList.getQName(i),
                                        attrList.getURI(i),
                                        attrList.getValue(i),
                                        attrList.isSpecified(i));
            int attrChunk = attrNodeIndex >> CHUNK_SHIFT;
            int attrIndex  = attrNodeIndex & CHUNK_MASK;

            setChunkIndex(fNodeParent, elementNodeIndex, attrChunk, attrIndex);

            // add links
            if (i == 0) {
                // from element to first attribute
                setChunkIndex(fNodeExtra, attrNodeIndex,
                              elementChunk, elementIndex);
            }
            else {
                // from last attribute to new attribute
                setChunkIndex(fNodePrevSib, attrNodeIndex,
                              lastAttrChunk, lastAttrIndex);
            }

            // save last chunk and index
            lastAttrNodeIndex = attrNodeIndex;
            lastAttrChunk     = attrChunk;
            lastAttrIndex     = attrIndex;
        }
 
        // return node index
        return elementNodeIndex;

    } // createDeferredElement(String,XMLAttributes):int

    /** 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. */
    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);
        setChunkIndex(fNodeExtra, specified ? 1 : 0, chunk, index);

        // return node index
        return nodeIndex;

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

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

    /** 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. */
    public void setAsLastChild(int parentIndex, int childIndex) {

        int pchunk = parentIndex >> CHUNK_SHIFT;
        int pindex = parentIndex & CHUNK_MASK;
        int chunk = childIndex >> CHUNK_SHIFT;
        int index = childIndex & CHUNK_MASK;
        setChunkIndex(fNodeLastChild, childIndex, pchunk, pindex);
    } // setAsLastChild(int,int)

    /**
     * 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.
     * @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. */
    public int getLastChild(int nodeIndex) {
        return getLastChild(nodeIndex, true);
    }

    /**
     * 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.
     */
    public int getPrevSibling(int nodeIndex) {
        return getPrevSibling(nodeIndex, true);
    }

    /**
     * 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 <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 <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.
     */
    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 (getChunkValue(fNodeName, nchunk, nindex) == elementName) {
                    return index;
                }
            }
        }

        return -1;

    } // lookupElementDefinition(String):int

    /** 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);
		}

                // save the document element node
                if (docElement == null) {
                    docElement = (ElementImpl)node;
                }

                // 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. */
    public String getNodeName(int nodeIndex) {
        return getNodeName(nodeIndex, true);
    } // getNodeNameString(int):String

    /**
     * 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. */
    public String getNodeValueString(int nodeIndex) {
        return getNodeValueString(nodeIndex, true);
    } // getNodeValueString(int):String

    /**
     * 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.addElement(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.addElement(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((String)fStrChunks.elementAt(i));
                }
                
                value = fBufferStr.toString();
                fStrChunks.removeAllElements();
                fBufferStr.setLength(0);
                return value;
            }
        }
        else if (type == Node.CDATA_SECTION_NODE) {
            // append data that is stored in fNodeValue
            fBufferStr.append(value);
            // find if any other data stored in children
            int child = getLastChild(nodeIndex, false);
            if (child !=-1) {
                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.addElement(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((String)fStrChunks.elementAt(i));
                }
                                                         
                value = fBufferStr.toString();
                fStrChunks.setSize(0);
                fBufferStr.setLength(0);
                return value;
            }
        }

        return value;

    } // getNodeValueString(int,boolean):String

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

    /**
     * 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).
     */
    public int getNodeExtra(int nodeIndex) {
        return getNodeExtra(nodeIndex, true);
    }

    /**
     * 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. */
    public short getNodeType(int nodeIndex) {
        return getNodeType(nodeIndex, true);
    }

    /**
     * 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. */
    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. */
    public String getNodeURI(int nodeIndex) {
        return getNodeURI(nodeIndex, true);
    }

    /**
     * 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. */
    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. */
    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; }
                        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; }
                    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(getChunkValue(fNodeValue, 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. */
    public int getNodeIndex() {
        return 0;
    }

    //
    // Protected methods
    //

    /** 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.
     */
    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.
     */
    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.
     */
    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. */
    protected boolean ensureCapacity(int chunk, int index) {

        // create buffers
        if (fNodeType == null) {
            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][];
        }

        // return true if table is already big enough
        try {
            return fNodeType[chunk][index] != 0;
        }

        // resize the tables
        catch (ArrayIndexOutOfBoundsException ex) {
            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;
        }

        catch (NullPointerException ex) {
            // ignore
        }

        // create 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);

        // success
        return true;

    } // ensureCapacity(int,int):boolean

    /** 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, index);

        // 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.
     *
     * @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) / 2;
            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
    //

    /** 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];
        for (int i = 0; i < CHUNK_SIZE; i++) {
            data[chunk][i] = -1;
        }
    }

    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.
     *
     * @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 ovalue = data[chunk][index];
        if (ovalue == -1) {
            data[chunk][CHUNK_SIZE]++;
        }
        data[chunk][index] = value;
        return ovalue;
    }
    private final String setChunkValue(Object data[][], Object value,
                                       int chunk, int index) {
        if (value == null) {
            return clearChunkValue(data, chunk, index);
        }
        String ovalue = (String) data[chunk][index];
        if (ovalue == null) {
            RefCount c = (RefCount) data[chunk][CHUNK_SIZE];
            c.fCount++;
        }
        data[chunk][index] = value;
        return ovalue;
    }

    /**
     * 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;
    }

    /**
     * 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.
     */
    private final void putIdentifier0(String idName, Element element) {

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

        // create hashtable
        if (identifiers == null) {
            identifiers = new java.util.Hashtable();
        }

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

    } // putIdentifier0(String,Element)

    /** 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.
     */
    static class IntVector {

        //
        // Data
        //

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

        /** Size. */
        private int size;

        //
        // Public methods
        //

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

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

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

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

        //
        // Private methods
        //

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