internal/dom/RangeImpl.java

/*
 * reserved comment block
 * DO NOT REMOVE OR ALTER!
 */
/*
 * 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.Vector;

import org.w3c.dom.CharacterData;
import org.w3c.dom.DOMException;
import org.w3c.dom.DocumentFragment;
import org.w3c.dom.Node;
import org.w3c.dom.ranges.Range;
import org.w3c.dom.ranges.RangeException;


/** The RangeImpl class implements the org.w3c.dom.range.Range interface.
 *  <p> Please see the API documentation for the interface classes
 *  and use the interfaces in your client programs.
 *
 * @xerces.internal
 *
 */
public class RangeImpl  implements Range {

    //
    // Constants
    //


    //
    // Data
    //

    DocumentImpl fDocument;
    Node fStartContainer;
    Node fEndContainer;
    int fStartOffset;
    int fEndOffset;
    boolean fIsCollapsed;
    boolean fDetach = false;
    Node fInsertNode = null;
    Node fDeleteNode = null;
    Node fSplitNode = null;
    // Was the Node inserted from the Range or the Document
    boolean fInsertedFromRange = false;

    /** The constructor. Clients must use DocumentRange.createRange(),
     *  because it registers the Range with the document, so it can
     *  be fixed-up.
     */
    public RangeImpl(DocumentImpl document) {
        fDocument = document;
        fStartContainer = document;
        fEndContainer = document;
        fStartOffset = 0;
        fEndOffset = 0;
        fDetach = false;
    }

    public Node getStartContainer() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return fStartContainer;
    }

    public int getStartOffset() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return fStartOffset;
    }

    public Node getEndContainer() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return fEndContainer;
    }

    public int getEndOffset() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return fEndOffset;
    }

    public boolean getCollapsed() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return (fStartContainer == fEndContainer
             && fStartOffset == fEndOffset);
    }

    public Node getCommonAncestorContainer() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        Vector startV = new Vector();
        Node node;
        for (node=fStartContainer; node != null;
             node=node.getParentNode())
        {
            startV.addElement(node);
        }
        Vector endV = new Vector();
        for (node=fEndContainer; node != null;
             node=node.getParentNode())
        {
            endV.addElement(node);
        }
        int s = startV.size()-1;
        int e = endV.size()-1;
        Object result = null;
        while (s>=0 && e>=0) {
            if (startV.elementAt(s) == endV.elementAt(e)) {
                result = startV.elementAt(s);
            } else {
                break;
            }
            --s;
            --e;
        }
        return (Node)result;
    }


    public void setStart(Node refNode, int offset)
                         throws RangeException, DOMException
    {
        if (fDocument.errorChecking) {
            if ( fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( !isLegalContainer(refNode)) {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
            if ( fDocument != refNode.getOwnerDocument() && fDocument != refNode) {
                throw new DOMException(
                        DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }

        checkIndex(refNode, offset);

        fStartContainer = refNode;
        fStartOffset = offset;

        // If one boundary-point of a Range is set to have a root container
        // other
        // than the current one for the Range, the Range should be collapsed to
        // the new position.
        // The start position of a Range should never be after the end position.
        if (getCommonAncestorContainer() == null
                || (fStartContainer == fEndContainer && fEndOffset < fStartOffset)) {
            collapse(true);
        }
    }

    public void setEnd(Node refNode, int offset)
                       throws RangeException, DOMException
    {
        if (fDocument.errorChecking) {
            if (fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( !isLegalContainer(refNode)) {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
            if ( fDocument != refNode.getOwnerDocument() && fDocument != refNode) {
                throw new DOMException(
                        DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }

        checkIndex(refNode, offset);

        fEndContainer = refNode;
        fEndOffset = offset;

        // If one boundary-point of a Range is set to have a root container
        // other
        // than the current one for the Range, the Range should be collapsed to
        // the new position.
        // The start position of a Range should never be after the end position.
        if (getCommonAncestorContainer() == null
                || (fStartContainer == fEndContainer && fEndOffset < fStartOffset)) {
            collapse(false);
        }
    }

    public void setStartBefore(Node refNode)
        throws RangeException
    {
        if (fDocument.errorChecking) {
            if (fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( !hasLegalRootContainer(refNode) ||
                    !isLegalContainedNode(refNode) )
            {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
            if ( fDocument != refNode.getOwnerDocument() && fDocument != refNode) {
                throw new DOMException(
                        DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }

        fStartContainer = refNode.getParentNode();
        int i = 0;
        for (Node n = refNode; n!=null; n = n.getPreviousSibling()) {
            i++;
        }
        fStartOffset = i-1;

        // If one boundary-point of a Range is set to have a root container
        // other
        // than the current one for the Range, the Range should be collapsed to
        // the new position.
        // The start position of a Range should never be after the end position.
        if (getCommonAncestorContainer() == null
                || (fStartContainer == fEndContainer && fEndOffset < fStartOffset)) {
            collapse(true);
        }
    }

    public void setStartAfter(Node refNode)
        throws RangeException
    {
        if (fDocument.errorChecking) {
            if (fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( !hasLegalRootContainer(refNode) ||
                    !isLegalContainedNode(refNode)) {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
            if ( fDocument != refNode.getOwnerDocument() && fDocument != refNode) {
                throw new DOMException(
                        DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }
        fStartContainer = refNode.getParentNode();
        int i = 0;
        for (Node n = refNode; n!=null; n = n.getPreviousSibling()) {
            i++;
        }
        fStartOffset = i;

        // If one boundary-point of a Range is set to have a root container
        // other
        // than the current one for the Range, the Range should be collapsed to
        // the new position.
        // The start position of a Range should never be after the end position.
        if (getCommonAncestorContainer() == null
                || (fStartContainer == fEndContainer && fEndOffset < fStartOffset)) {
            collapse(true);
        }
    }

    public void setEndBefore(Node refNode)
        throws RangeException
    {
        if (fDocument.errorChecking) {
            if (fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( !hasLegalRootContainer(refNode) ||
                    !isLegalContainedNode(refNode)) {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
            if ( fDocument != refNode.getOwnerDocument() && fDocument != refNode) {
                throw new DOMException(
                        DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }
        fEndContainer = refNode.getParentNode();
        int i = 0;
        for (Node n = refNode; n!=null; n = n.getPreviousSibling()) {
            i++;
        }
        fEndOffset = i-1;

        // If one boundary-point of a Range is set to have a root container
        // other
        // than the current one for the Range, the Range should be collapsed to
        // the new position.
        // The start position of a Range should never be after the end position.
        if (getCommonAncestorContainer() == null
                || (fStartContainer == fEndContainer && fEndOffset < fStartOffset)) {
            collapse(false);
        }
    }

    public void setEndAfter(Node refNode)
        throws RangeException
    {
        if (fDocument.errorChecking) {
            if( fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( !hasLegalRootContainer(refNode) ||
                    !isLegalContainedNode(refNode)) {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
            if ( fDocument != refNode.getOwnerDocument() && fDocument != refNode) {
                throw new DOMException(
                        DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }
        fEndContainer = refNode.getParentNode();
        int i = 0;
        for (Node n = refNode; n!=null; n = n.getPreviousSibling()) {
            i++;
        }
        fEndOffset = i;

        // If one boundary-point of a Range is set to have a root container
        // other
        // than the current one for the Range, the Range should be collapsed to
        // the new position.
        // The start position of a Range should never be after the end position.
        if (getCommonAncestorContainer() == null
                || (fStartContainer == fEndContainer && fEndOffset < fStartOffset)) {
            collapse(false);
        }
    }

    public void collapse(boolean toStart) {

        if( fDetach) {
                throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }

        if (toStart) {
            fEndContainer = fStartContainer;
            fEndOffset = fStartOffset;
        } else {
            fStartContainer = fEndContainer;
            fStartOffset = fEndOffset;
        }
    }

    public void selectNode(Node refNode)
        throws RangeException
    {
        if (fDocument.errorChecking) {
            if (fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( !isLegalContainer( refNode.getParentNode() ) ||
                    !isLegalContainedNode( refNode ) ) {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
            if ( fDocument != refNode.getOwnerDocument() && fDocument != refNode) {
                throw new DOMException(
                        DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }
        Node parent = refNode.getParentNode();
        if (parent != null ) // REVIST: what to do if it IS null?
        {
            fStartContainer = parent;
            fEndContainer = parent;
            int i = 0;
            for (Node n = refNode; n!=null; n = n.getPreviousSibling()) {
                i++;
            }
            fStartOffset = i-1;
            fEndOffset = fStartOffset+1;
        }
    }

    public void selectNodeContents(Node refNode)
        throws RangeException
    {
        if (fDocument.errorChecking) {
            if( fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( !isLegalContainer(refNode)) {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
            if ( fDocument != refNode.getOwnerDocument() && fDocument != refNode) {
                throw new DOMException(
                        DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }
        fStartContainer = refNode;
        fEndContainer = refNode;
        Node first = refNode.getFirstChild();
        fStartOffset = 0;
        if (first == null) {
            fEndOffset = 0;
        } else {
            int i = 0;
            for (Node n = first; n!=null; n = n.getNextSibling()) {
                i++;
            }
            fEndOffset = i;
        }

    }

    public short compareBoundaryPoints(short how, Range sourceRange)
        throws DOMException
    {
        if (fDocument.errorChecking) {
            if( fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            // WRONG_DOCUMENT_ERR: Raised if the two Ranges are not in the same Document or DocumentFragment.
            if ((fDocument != sourceRange.getStartContainer().getOwnerDocument()
                    && fDocument != sourceRange.getStartContainer()
                    && sourceRange.getStartContainer() != null)
                    || (fDocument != sourceRange.getEndContainer().getOwnerDocument()
                            && fDocument != sourceRange.getEndContainer()
                            && sourceRange.getStartContainer() != null)) {
                throw new DOMException(DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage( DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }
        }

        Node endPointA;
        Node endPointB;
        int offsetA;
        int offsetB;

        if (how == START_TO_START) {
            endPointA = sourceRange.getStartContainer();
            endPointB = fStartContainer;
            offsetA = sourceRange.getStartOffset();
            offsetB = fStartOffset;
        } else
        if (how == START_TO_END) {
            endPointA = sourceRange.getStartContainer();
            endPointB = fEndContainer;
            offsetA = sourceRange.getStartOffset();
            offsetB = fEndOffset;
        } else
        if (how == END_TO_START) {
            endPointA = sourceRange.getEndContainer();
            endPointB = fStartContainer;
            offsetA = sourceRange.getEndOffset();
            offsetB = fStartOffset;
        } else {
            endPointA = sourceRange.getEndContainer();
            endPointB = fEndContainer;
            offsetA = sourceRange.getEndOffset();
            offsetB = fEndOffset;
        }

        // The DOM Spec outlines four cases that need to be tested
        // to compare two range boundary points:
        //   case 1: same container
        //   case 2: Child C of container A is ancestor of B
        //   case 3: Child C of container B is ancestor of A
        //   case 4: preorder traversal of context tree.

        // case 1: same container
        if (endPointA == endPointB) {
            if (offsetA < offsetB) return 1;
            if (offsetA == offsetB) return 0;
            return -1;
        }
        // case 2: Child C of container A is ancestor of B
        // This can be quickly tested by walking the parent chain of B
        for ( Node c = endPointB, p = c.getParentNode();
             p != null;
             c = p, p = p.getParentNode())
        {
            if (p == endPointA) {
                int index = indexOf(c, endPointA);
                if (offsetA <= index) return 1;
                return -1;
            }
        }

        // case 3: Child C of container B is ancestor of A
        // This can be quickly tested by walking the parent chain of A
        for ( Node c = endPointA, p = c.getParentNode();
             p != null;
             c = p, p = p.getParentNode())
        {
            if (p == endPointB) {
                int index = indexOf(c, endPointB);
                if (index < offsetB) return 1;
                return -1;
            }
        }

        // case 4: preorder traversal of context tree.
        // Instead of literally walking the context tree in pre-order,
        // we use relative node depth walking which is usually faster

        int depthDiff = 0;
        for ( Node n = endPointA; n != null; n = n.getParentNode() )
            depthDiff++;
        for ( Node n = endPointB; n != null; n = n.getParentNode() )
            depthDiff--;
        while (depthDiff > 0) {
            endPointA = endPointA.getParentNode();
            depthDiff--;
        }
        while (depthDiff < 0) {
            endPointB = endPointB.getParentNode();
            depthDiff++;
        }
        for (Node pA = endPointA.getParentNode(),
             pB = endPointB.getParentNode();
             pA != pB;
             pA = pA.getParentNode(), pB = pB.getParentNode() )
        {
            endPointA = pA;
            endPointB = pB;
        }
        for ( Node n = endPointA.getNextSibling();
             n != null;
             n = n.getNextSibling() )
        {
            if (n == endPointB) {
                return 1;
            }
        }
        return -1;
    }

    public void deleteContents()
        throws DOMException
    {
        traverseContents(DELETE_CONTENTS);
    }

    public DocumentFragment extractContents()
        throws DOMException
    {
        return traverseContents(EXTRACT_CONTENTS);
    }

    public DocumentFragment cloneContents()
        throws DOMException
    {
        return traverseContents(CLONE_CONTENTS);
    }

    public void insertNode(Node newNode)
        throws DOMException, RangeException
    {
        if ( newNode == null ) return; //throw exception?

        int type = newNode.getNodeType();

        if (fDocument.errorChecking) {
            if (fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if ( fDocument != newNode.getOwnerDocument() ) {
                throw new DOMException(DOMException.WRONG_DOCUMENT_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null));
            }

            if (type == Node.ATTRIBUTE_NODE
                    || type == Node.ENTITY_NODE
                    || type == Node.NOTATION_NODE
                    || type == Node.DOCUMENT_NODE)
            {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
        }
        Node cloneCurrent;
        Node current;
        int currentChildren = 0;
        fInsertedFromRange = true;

        //boolean MULTIPLE_MODE = false;
        if (fStartContainer.getNodeType() == Node.TEXT_NODE) {

            Node parent = fStartContainer.getParentNode();
            currentChildren = parent.getChildNodes().getLength(); //holds number of kids before insertion
            // split text node: results is 3 nodes..
            cloneCurrent = fStartContainer.cloneNode(false);
            ((TextImpl)cloneCurrent).setNodeValueInternal(
                    (cloneCurrent.getNodeValue()).substring(fStartOffset));
            ((TextImpl)fStartContainer).setNodeValueInternal(
                    (fStartContainer.getNodeValue()).substring(0,fStartOffset));
            Node next = fStartContainer.getNextSibling();
            if (next != null) {
                    if (parent !=  null) {
                        parent.insertBefore(newNode, next);
                        parent.insertBefore(cloneCurrent, next);
                    }
            } else {
                    if (parent != null) {
                        parent.appendChild(newNode);
                        parent.appendChild(cloneCurrent);
                    }
            }
             //update ranges after the insertion
             if ( fEndContainer == fStartContainer) {
                  fEndContainer = cloneCurrent; //endContainer is the new Node created
                  fEndOffset -= fStartOffset;
             }
             else if ( fEndContainer == parent ) {    //endContainer was not a text Node.
                  //endOffset + = number_of_children_added
                   fEndOffset += (parent.getChildNodes().getLength() - currentChildren);
             }

             // signal other Ranges to update their start/end containers/offsets
             signalSplitData(fStartContainer, cloneCurrent, fStartOffset);


        } else { // ! TEXT_NODE
            if ( fEndContainer == fStartContainer )      //need to remember number of kids
                currentChildren= fEndContainer.getChildNodes().getLength();

            current = fStartContainer.getFirstChild();
            int i = 0;
            for(i = 0; i < fStartOffset && current != null; i++) {
                current=current.getNextSibling();
            }
            if (current != null) {
                fStartContainer.insertBefore(newNode, current);
            } else {
                fStartContainer.appendChild(newNode);
            }
            //update fEndOffset. ex:<body><p/></body>. Range(start;end): body,0; body,1
            // insert <h1>: <body></h1><p/></body>. Range(start;end): body,0; body,2
            if ( fEndContainer == fStartContainer && fEndOffset != 0 ) {     //update fEndOffset if not 0
                fEndOffset += (fEndContainer.getChildNodes().getLength() - currentChildren);
            }
        }
        fInsertedFromRange = false;
    }

    public void surroundContents(Node newParent)
        throws DOMException, RangeException
    {
        if (newParent==null) return;
        int type = newParent.getNodeType();

        if (fDocument.errorChecking) {
            if (fDetach) {
                throw new DOMException(
                        DOMException.INVALID_STATE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
            }
            if (type == Node.ATTRIBUTE_NODE
                    || type == Node.ENTITY_NODE
                    || type == Node.NOTATION_NODE
                    || type == Node.DOCUMENT_TYPE_NODE
                    || type == Node.DOCUMENT_NODE
                    || type == Node.DOCUMENT_FRAGMENT_NODE)
            {
                throw new RangeExceptionImpl(
                        RangeException.INVALID_NODE_TYPE_ERR,
                        DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_NODE_TYPE_ERR", null));
            }
        }

        Node realStart = fStartContainer;
        Node realEnd = fEndContainer;
        if (fStartContainer.getNodeType() == Node.TEXT_NODE) {
            realStart = fStartContainer.getParentNode();
        }
        if (fEndContainer.getNodeType() == Node.TEXT_NODE) {
            realEnd = fEndContainer.getParentNode();
        }

        if (realStart != realEnd) {
                throw new RangeExceptionImpl(
                RangeException.BAD_BOUNDARYPOINTS_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "BAD_BOUNDARYPOINTS_ERR", null));
        }

        DocumentFragment frag = extractContents();
        insertNode(newParent);
        newParent.appendChild(frag);
        selectNode(newParent);
    }

    public Range cloneRange(){
        if( fDetach) {
                throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }

        Range range = fDocument.createRange();
        range.setStart(fStartContainer, fStartOffset);
        range.setEnd(fEndContainer, fEndOffset);
        return range;
    }

    public String toString(){
        if( fDetach) {
                throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }

        Node node = fStartContainer;
        Node stopNode = fEndContainer;
        StringBuffer sb = new StringBuffer();
        if (fStartContainer.getNodeType() == Node.TEXT_NODE
         || fStartContainer.getNodeType() == Node.CDATA_SECTION_NODE
        ) {
            if (fStartContainer == fEndContainer) {
                sb.append(fStartContainer.getNodeValue().substring(fStartOffset, fEndOffset));
                return sb.toString();
            }
            sb.append(fStartContainer.getNodeValue().substring(fStartOffset));
            node=nextNode (node,true); //fEndContainer!=fStartContainer

        }
        else {  //fStartContainer is not a TextNode
            node=node.getFirstChild();
            if (fStartOffset>0) { //find a first node within a range, specified by fStartOffset
               int counter=0;
               while (counter<fStartOffset && node!=null) {
                   node=node.getNextSibling();
                   counter++;
               }
            }
            if (node == null) {
                   node = nextNode(fStartContainer,false);
            }
        }
        if ( fEndContainer.getNodeType()!= Node.TEXT_NODE &&
             fEndContainer.getNodeType()!= Node.CDATA_SECTION_NODE ){
             int i=fEndOffset;
             stopNode = fEndContainer.getFirstChild();
             while( i>0 && stopNode!=null ){
                 --i;
                 stopNode = stopNode.getNextSibling();
             }
             if ( stopNode == null )
                 stopNode = nextNode( fEndContainer, false );
         }
         while (node != stopNode) {  //look into all kids of the Range
             if (node == null) break;
             if (node.getNodeType() == Node.TEXT_NODE
             ||  node.getNodeType() == Node.CDATA_SECTION_NODE) {
                 sb.append(node.getNodeValue());
             }

             node = nextNode(node, true);
         }

        if (fEndContainer.getNodeType() == Node.TEXT_NODE
         || fEndContainer.getNodeType() == Node.CDATA_SECTION_NODE) {
            sb.append(fEndContainer.getNodeValue().substring(0,fEndOffset));
        }
        return sb.toString();
    }

    public void detach() {
        if( fDetach) {
            throw new DOMException(
            DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        fDetach = true;
        fDocument.removeRange(this);
    }

    //
    // Mutation functions
    //

    /** Signal other Ranges to update their start/end
     *  containers/offsets. The data has already been split
     *  into the two Nodes.
     */
    void signalSplitData(Node node, Node newNode, int offset) {
        fSplitNode = node;
        // notify document
        fDocument.splitData(node, newNode, offset);
        fSplitNode = null;
    }

    /** Fix up this Range if another Range has split a Text Node
     *  into 2 Nodes.
     */
    void receiveSplitData(Node node, Node newNode, int offset) {
        if (node == null || newNode == null) return;
        if (fSplitNode == node) return;

        if (node == fStartContainer
        && fStartContainer.getNodeType() == Node.TEXT_NODE) {
            if (fStartOffset > offset) {
                fStartOffset = fStartOffset - offset;
                fStartContainer = newNode;
            }
        }
        if (node == fEndContainer
        && fEndContainer.getNodeType() == Node.TEXT_NODE) {
            if (fEndOffset > offset) {
                fEndOffset = fEndOffset-offset;
                fEndContainer = newNode;
            }
        }

    }

    /** This function inserts text into a Node and invokes
     *  a method to fix-up all other Ranges.
     */
    void deleteData(CharacterData node, int offset, int count) {
        fDeleteNode = node;
        node.deleteData( offset,  count);
        fDeleteNode = null;
    }


    /** This function is called from DOM.
     *  The  text has already beeen inserted.
     *  Fix-up any offsets.
     */
    void receiveDeletedText(Node node, int offset, int count) {
        if (node == null) return;
        if (fDeleteNode == node) return;
        if (node == fStartContainer
        && fStartContainer.getNodeType() == Node.TEXT_NODE) {
            if (fStartOffset > offset+count) {
                fStartOffset = offset+(fStartOffset-(offset+count));
            } else
            if (fStartOffset > offset) {
                fStartOffset = offset;
            }
        }
        if (node == fEndContainer
        && fEndContainer.getNodeType() == Node.TEXT_NODE) {
            if (fEndOffset > offset+count) {
                fEndOffset = offset+(fEndOffset-(offset+count));
            } else
            if (fEndOffset > offset) {
                fEndOffset = offset;
            }
        }

    }

    /** This function inserts text into a Node and invokes
     *  a method to fix-up all other Ranges.
     */
    void insertData(CharacterData node, int index, String insert) {
        fInsertNode = node;
        node.insertData( index,  insert);
        fInsertNode = null;
    }


    /** This function is called from DOM.
     *  The  text has already beeen inserted.
     *  Fix-up any offsets.
     */
    void receiveInsertedText(Node node, int index, int len) {
        if (node == null) return;
        if (fInsertNode == node) return;
        if (node == fStartContainer
        && fStartContainer.getNodeType() == Node.TEXT_NODE) {
            if (index < fStartOffset) {
                fStartOffset = fStartOffset+len;
            }
        }
        if (node == fEndContainer
        && fEndContainer.getNodeType() == Node.TEXT_NODE) {
            if (index < fEndOffset) {
                fEndOffset = fEndOffset+len;
            }
        }

    }

    /** This function is called from DOM.
     *  The  text has already beeen replaced.
     *  Fix-up any offsets.
     */
    void receiveReplacedText(Node node) {
        if (node == null) return;
        if (node == fStartContainer
        && fStartContainer.getNodeType() == Node.TEXT_NODE) {
            fStartOffset = 0;
        }
        if (node == fEndContainer
        && fEndContainer.getNodeType() == Node.TEXT_NODE) {
            fEndOffset = 0;
        }

    }

    /** This function is called from the DOM.
     *  This node has already been inserted into the DOM.
     *  Fix-up any offsets.
     */
    public void insertedNodeFromDOM(Node node) {
        if (node == null) return;
        if (fInsertNode == node) return;
        if (fInsertedFromRange) return; // Offsets are adjusted in Range.insertNode

        Node parent = node.getParentNode();

        if (parent == fStartContainer) {
            int index = indexOf(node, fStartContainer);
            if (index < fStartOffset) {
                fStartOffset++;
            }
        }

        if (parent == fEndContainer) {
            int index = indexOf(node, fEndContainer);
            if (index < fEndOffset) {
                fEndOffset++;
            }
        }

    }

    /** This function is called within Range
     *  instead of Node.removeChild,
     *  so that the range can remember that it is actively
     *  removing this child.
     */

    Node fRemoveChild = null;
    Node removeChild(Node parent, Node child) {
        fRemoveChild = child;
        Node n = parent.removeChild(child);
        fRemoveChild = null;
        return n;
    }

    /** This function must be called by the DOM _BEFORE_
     *  a node is deleted, because at that time it is
     *  connected in the DOM tree, which we depend on.
     */
    void removeNode(Node node) {
        if (node == null) return;
        if (fRemoveChild == node) return;

        Node parent = node.getParentNode();

        if (parent == fStartContainer) {
            int index = indexOf(node, fStartContainer);
            if (index < fStartOffset) {
                fStartOffset--;
            }
        }

        if (parent == fEndContainer) {
            int index = indexOf(node, fEndContainer);
            if (index < fEndOffset) {
                fEndOffset--;
            }
        }
        //startContainer or endContainer or both is/are the ancestor(s) of the Node to be deleted
        if (parent != fStartContainer
        ||  parent != fEndContainer) {
            if (isAncestorOf(node, fStartContainer)) {
                fStartContainer = parent;
                fStartOffset = indexOf( node, parent);
            }
            if (isAncestorOf(node, fEndContainer)) {
                fEndContainer = parent;
                fEndOffset = indexOf( node, parent);
            }
        }

    }

    //
    // Utility functions.
    //

    // parameters for traverseContents(int)
    //REVIST: use boolean, since there are only 2 now...
    static final int EXTRACT_CONTENTS = 1;
    static final int CLONE_CONTENTS = 2;
    static final int DELETE_CONTENTS = 3;

    /**
     * This is the master routine invoked to visit the nodes
     * selected by this range.  For each such node, different
     * actions are taken depending on the value of the
     * <code>how</code> argument.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete from
     *               the context tree of the range, all fully selected
     *               nodes.
     *               </ol>
     *
     * @return Returns a document fragment containing any
     *         copied or extracted nodes.  If the <code>how</code>
     *         parameter was <code>DELETE_CONTENTS</code>, the
     *         return value is null.
     */
    private DocumentFragment traverseContents( int how )
        throws DOMException
    {
        if (fStartContainer == null || fEndContainer == null) {
            return null; // REVIST: Throw exception?
        }

        //Check for a detached range.
        if( fDetach) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }

        /*
          Traversal is accomplished by first determining the
          relationship between the endpoints of the range.
          For each of four significant relationships, we will
          delegate the traversal call to a method that
          can make appropriate assumptions.
         */

        // case 1: same container
        if ( fStartContainer == fEndContainer )
            return traverseSameContainer( how );


        // case 2: Child C of start container is ancestor of end container
        // This can be quickly tested by walking the parent chain of
        // end container
        int endContainerDepth = 0;
        for ( Node c = fEndContainer, p = c.getParentNode();
             p != null;
             c = p, p = p.getParentNode())
        {
            if (p == fStartContainer)
                return traverseCommonStartContainer( c, how );
            ++endContainerDepth;
        }

        // case 3: Child C of container B is ancestor of A
        // This can be quickly tested by walking the parent chain of A
        int startContainerDepth = 0;
        for ( Node c = fStartContainer, p = c.getParentNode();
             p != null;
             c = p, p = p.getParentNode())
        {
            if (p == fEndContainer)
                return traverseCommonEndContainer( c, how );
            ++startContainerDepth;
        }

        // case 4: There is a common ancestor container.  Find the
        // ancestor siblings that are children of that container.
        int depthDiff = startContainerDepth - endContainerDepth;

        Node startNode = fStartContainer;
        while (depthDiff > 0) {
            startNode = startNode.getParentNode();
            depthDiff--;
        }

        Node endNode = fEndContainer;
        while (depthDiff < 0) {
            endNode = endNode.getParentNode();
            depthDiff++;
        }

        // ascend the ancestor hierarchy until we have a common parent.
        for( Node sp = startNode.getParentNode(), ep = endNode.getParentNode();
             sp!=ep;
             sp = sp.getParentNode(), ep = ep.getParentNode() )
        {
            startNode = sp;
            endNode = ep;
        }
        return traverseCommonAncestors( startNode, endNode, how );
    }

    /**
     * Visits the nodes selected by this range when we know
     * a-priori that the start and end containers are the same.
     * This method is invoked by the generic <code>traverse</code>
     * method.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete from
     *               the context tree of the range, all fully selected
     *               nodes.
     *               </ol>
     *
     * @return Returns a document fragment containing any
     *         copied or extracted nodes.  If the <code>how</code>
     *         parameter was <code>DELETE_CONTENTS</code>, the
     *         return value is null.
     */
    private DocumentFragment traverseSameContainer( int how )
    {
        DocumentFragment frag = null;
        if ( how!=DELETE_CONTENTS)
            frag = fDocument.createDocumentFragment();

        // If selection is empty, just return the fragment
        if ( fStartOffset==fEndOffset )
            return frag;

        // Text node needs special case handling
        if ( fStartContainer.getNodeType()==Node.TEXT_NODE )
        {
            // get the substring
            String s = fStartContainer.getNodeValue();
            String sub = s.substring( fStartOffset, fEndOffset );

            // set the original text node to its new value
            if ( how != CLONE_CONTENTS )
            {
                ((TextImpl)fStartContainer).deleteData(fStartOffset,
                     fEndOffset-fStartOffset) ;
                // Nothing is partially selected, so collapse to start point
                collapse( true );
            }
            if ( how==DELETE_CONTENTS)
                return null;
            frag.appendChild( fDocument.createTextNode(sub) );
            return frag;
        }

        // Copy nodes between the start/end offsets.
        Node n = getSelectedNode( fStartContainer, fStartOffset );
        int cnt = fEndOffset - fStartOffset;
        while( cnt > 0 )
        {
            Node sibling = n.getNextSibling();
            Node xferNode = traverseFullySelected( n, how );
            if ( frag!=null )
                frag.appendChild( xferNode );
            --cnt;
            n = sibling;
        }

        // Nothing is partially selected, so collapse to start point
        if ( how != CLONE_CONTENTS )
            collapse( true );
        return frag;
    }

    /**
     * Visits the nodes selected by this range when we know
     * a-priori that the start and end containers are not the
     * same, but the start container is an ancestor of the
     * end container. This method is invoked by the generic
     * <code>traverse</code> method.
     *
     * @param endAncestor
     *               The ancestor of the end container that is a direct child
     *               of the start container.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete from
     *               the context tree of the range, all fully selected
     *               nodes.
     *               </ol>
     *
     * @return Returns a document fragment containing any
     *         copied or extracted nodes.  If the <code>how</code>
     *         parameter was <code>DELETE_CONTENTS</code>, the
     *         return value is null.
     */
    private DocumentFragment
        traverseCommonStartContainer( Node endAncestor, int how )
    {
        DocumentFragment frag = null;
        if ( how!=DELETE_CONTENTS)
            frag = fDocument.createDocumentFragment();
        Node n = traverseRightBoundary( endAncestor, how );
        if ( frag!=null )
            frag.appendChild( n );

        int endIdx = indexOf( endAncestor, fStartContainer );
        int cnt = endIdx - fStartOffset;
        if ( cnt <=0 )
        {
            // Collapse to just before the endAncestor, which
            // is partially selected.
            if ( how != CLONE_CONTENTS )
            {
                setEndBefore( endAncestor );
                collapse( false );
            }
            return frag;
        }

        n = endAncestor.getPreviousSibling();
        while( cnt > 0 )
        {
            Node sibling = n.getPreviousSibling();
            Node xferNode = traverseFullySelected( n, how );
            if ( frag!=null )
                frag.insertBefore( xferNode, frag.getFirstChild() );
            --cnt;
            n = sibling;
        }
        // Collapse to just before the endAncestor, which
        // is partially selected.
        if ( how != CLONE_CONTENTS )
        {
            setEndBefore( endAncestor );
            collapse( false );
        }
        return frag;
    }

    /**
     * Visits the nodes selected by this range when we know
     * a-priori that the start and end containers are not the
     * same, but the end container is an ancestor of the
     * start container. This method is invoked by the generic
     * <code>traverse</code> method.
     *
     * @param startAncestor
     *               The ancestor of the start container that is a direct
     *               child of the end container.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete from
     *               the context tree of the range, all fully selected
     *               nodes.
     *               </ol>
     *
     * @return Returns a document fragment containing any
     *         copied or extracted nodes.  If the <code>how</code>
     *         parameter was <code>DELETE_CONTENTS</code>, the
     *         return value is null.
     */
    private DocumentFragment
        traverseCommonEndContainer( Node startAncestor, int how )
    {
        DocumentFragment frag = null;
        if ( how!=DELETE_CONTENTS)
            frag = fDocument.createDocumentFragment();
        Node n = traverseLeftBoundary( startAncestor, how );
        if ( frag!=null )
            frag.appendChild( n );
        int startIdx = indexOf( startAncestor, fEndContainer );
        ++startIdx;  // Because we already traversed it....

        int cnt = fEndOffset - startIdx;
        n = startAncestor.getNextSibling();
        while( cnt > 0 )
        {
            Node sibling = n.getNextSibling();
            Node xferNode = traverseFullySelected( n, how );
            if ( frag!=null )
                frag.appendChild( xferNode );
            --cnt;
            n = sibling;
        }

        if ( how != CLONE_CONTENTS )
        {
            setStartAfter( startAncestor );
            collapse( true );
        }

        return frag;
    }

    /**
     * Visits the nodes selected by this range when we know
     * a-priori that the start and end containers are not
     * the same, and we also know that neither the start
     * nor end container is an ancestor of the other.
     * This method is invoked by
     * the generic <code>traverse</code> method.
     *
     * @param startAncestor
     *               Given a common ancestor of the start and end containers,
     *               this parameter is the ancestor (or self) of the start
     *               container that is a direct child of the common ancestor.
     *
     * @param endAncestor
     *               Given a common ancestor of the start and end containers,
     *               this parameter is the ancestor (or self) of the end
     *               container that is a direct child of the common ancestor.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete from
     *               the context tree of the range, all fully selected
     *               nodes.
     *               </ol>
     *
     * @return Returns a document fragment containing any
     *         copied or extracted nodes.  If the <code>how</code>
     *         parameter was <code>DELETE_CONTENTS</code>, the
     *         return value is null.
     */
    private DocumentFragment
        traverseCommonAncestors( Node startAncestor, Node endAncestor, int how )
    {
        DocumentFragment frag = null;
        if ( how!=DELETE_CONTENTS)
            frag = fDocument.createDocumentFragment();

        Node n = traverseLeftBoundary( startAncestor, how );
        if ( frag!=null )
            frag.appendChild( n );

        Node commonParent = startAncestor.getParentNode();
        int startOffset = indexOf( startAncestor, commonParent );
        int endOffset = indexOf( endAncestor, commonParent );
        ++startOffset;

        int cnt = endOffset - startOffset;
        Node sibling = startAncestor.getNextSibling();

        while( cnt > 0 )
        {
            Node nextSibling = sibling.getNextSibling();
            n = traverseFullySelected( sibling, how );
            if ( frag!=null )
                frag.appendChild( n );
            sibling = nextSibling;
            --cnt;
        }

        n = traverseRightBoundary( endAncestor, how );
        if ( frag!=null )
            frag.appendChild( n );

        if ( how != CLONE_CONTENTS )
        {
            setStartAfter( startAncestor );
            collapse( true );
        }
        return frag;
    }

    /**
     * Traverses the "right boundary" of this range and
     * operates on each "boundary node" according to the
     * <code>how</code> parameter.  It is a-priori assumed
     * by this method that the right boundary does
     * not contain the range's start container.
     * <p>
     * A "right boundary" is best visualized by thinking
     * of a sample tree:<pre>
     *                 A
     *                /|\
     *               / | \
     *              /  |  \
     *             B   C   D
     *            /|\     /|\
     *           E F G   H I J
     * </pre>
     * Imagine first a range that begins between the
     * "E" and "F" nodes and ends between the
     * "I" and "J" nodes.  The start container is
     * "B" and the end container is "D".  Given this setup,
     * the following applies:
     * <p>
     * Partially Selected Nodes: B, D<br>
     * Fully Selected Nodes: F, G, C, H, I
     * <p>
     * The "right boundary" is the highest subtree node
     * that contains the ending container.  The root of
     * this subtree is always partially selected.
     * <p>
     * In this example, the nodes that are traversed
     * as "right boundary" nodes are: H, I, and D.
     *
     * @param root   The node that is the root of the "right boundary" subtree.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will produce
     *               a node containing the boundaries content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but will
     *               produced cloned content.
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete from
     *               the context tree of the range, all fully selected
     *               nodes within the boundary.
     *               </ol>
     *
     * @return Returns a node that is the result of visiting nodes.
     *         If the traversal operation is
     *         <code>DELETE_CONTENTS</code> the return value is null.
     */
    private Node traverseRightBoundary( Node root, int how )
    {
        Node next = getSelectedNode( fEndContainer, fEndOffset-1 );
        boolean isFullySelected = ( next!=fEndContainer );

        if ( next==root )
            return traverseNode( next, isFullySelected, false, how );

        Node parent = next.getParentNode();
        Node clonedParent = traverseNode( parent, false, false, how );

        while( parent!=null )
        {
            while( next!=null )
            {
                Node prevSibling = next.getPreviousSibling();
                Node clonedChild =
                    traverseNode( next, isFullySelected, false, how );
                if ( how!=DELETE_CONTENTS )
                {
                    clonedParent.insertBefore(
                        clonedChild,
                        clonedParent.getFirstChild()
                    );
                }
                isFullySelected = true;
                next = prevSibling;
            }
            if ( parent==root )
                return clonedParent;

            next = parent.getPreviousSibling();
            parent = parent.getParentNode();
            Node clonedGrandParent = traverseNode( parent, false, false, how );
            if ( how!=DELETE_CONTENTS )
                clonedGrandParent.appendChild( clonedParent );
            clonedParent = clonedGrandParent;

        }

        // should never occur
        return null;
    }

    /**
     * Traverses the "left boundary" of this range and
     * operates on each "boundary node" according to the
     * <code>how</code> parameter.  It is a-priori assumed
     * by this method that the left boundary does
     * not contain the range's end container.
     * <p>
     * A "left boundary" is best visualized by thinking
     * of a sample tree:<pre>
     *
     *                 A
     *                /|\
     *               / | \
     *              /  |  \
     *             B   C   D
     *            /|\     /|\
     *           E F G   H I J
     * </pre>
     * Imagine first a range that begins between the
     * "E" and "F" nodes and ends between the
     * "I" and "J" nodes.  The start container is
     * "B" and the end container is "D".  Given this setup,
     * the following applies:
     * <p>
     * Partially Selected Nodes: B, D<br>
     * Fully Selected Nodes: F, G, C, H, I
     * <p>
     * The "left boundary" is the highest subtree node
     * that contains the starting container.  The root of
     * this subtree is always partially selected.
     * <p>
     * In this example, the nodes that are traversed
     * as "left boundary" nodes are: F, G, and B.
     *
     * @param root   The node that is the root of the "left boundary" subtree.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will produce
     *               a node containing the boundaries content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but will
     *               produced cloned content.
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete from
     *               the context tree of the range, all fully selected
     *               nodes within the boundary.
     *               </ol>
     *
     * @return Returns a node that is the result of visiting nodes.
     *         If the traversal operation is
     *         <code>DELETE_CONTENTS</code> the return value is null.
     */
    private Node traverseLeftBoundary( Node root, int how )
    {
        Node next = getSelectedNode( getStartContainer(), getStartOffset() );
        boolean isFullySelected = ( next!=getStartContainer() );

        if ( next==root )
            return traverseNode( next, isFullySelected, true, how );

        Node parent = next.getParentNode();
        Node clonedParent = traverseNode( parent, false, true, how );

        while( parent!=null )
        {
            while( next!=null )
            {
                Node nextSibling = next.getNextSibling();
                Node clonedChild =
                    traverseNode( next, isFullySelected, true, how );
                if ( how!=DELETE_CONTENTS )
                    clonedParent.appendChild(clonedChild);
                isFullySelected = true;
                next = nextSibling;
            }
            if ( parent==root )
                return clonedParent;

            next = parent.getNextSibling();
            parent = parent.getParentNode();
            Node clonedGrandParent = traverseNode( parent, false, true, how );
            if ( how!=DELETE_CONTENTS )
                clonedGrandParent.appendChild( clonedParent );
            clonedParent = clonedGrandParent;

        }

        // should never occur
        return null;

    }

    /**
     * Utility method for traversing a single node.
     * Does not properly handle a text node containing both the
     * start and end offsets.  Such nodes should
     * have been previously detected and been routed to traverseTextNode.
     *
     * @param n      The node to be traversed.
     *
     * @param isFullySelected
     *               Set to true if the node is fully selected.  Should be
     *               false otherwise.
     *               Note that although the DOM 2 specification says that a
     *               text node that is boththe start and end container is not
     *               selected, we treat it here as if it were partially
     *               selected.
     *
     * @param isLeft Is true if we are traversing the node as part of navigating
     *               the "left boundary" of the range.  If this value is false,
     *               it implies we are navigating the "right boundary" of the
     *               range.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will simply
     *               return the original node.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but will
     *               return a cloned node.
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete the
     *               node from it's parent, but will return null.
     *               </ol>
     *
     * @return Returns a node that is the result of visiting the node.
     *         If the traversal operation is
     *         <code>DELETE_CONTENTS</code> the return value is null.
     */
    private Node traverseNode( Node n, boolean isFullySelected, boolean isLeft, int how )
    {
        if ( isFullySelected )
            return traverseFullySelected( n, how );
        if ( n.getNodeType()==Node.TEXT_NODE )
            return traverseTextNode( n, isLeft, how );
        return traversePartiallySelected( n, how );
    }

    /**
     * Utility method for traversing a single node when
     * we know a-priori that the node if fully
     * selected.
     *
     * @param n      The node to be traversed.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will simply
     *               return the original node.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but will
     *               return a cloned node.
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete the
     *               node from it's parent, but will return null.
     *               </ol>
     *
     * @return Returns a node that is the result of visiting the node.
     *         If the traversal operation is
     *         <code>DELETE_CONTENTS</code> the return value is null.
     */
    private Node traverseFullySelected( Node n, int how )
    {
        switch( how )
        {
        case CLONE_CONTENTS:
            return n.cloneNode( true );
        case EXTRACT_CONTENTS:
            if ( n.getNodeType()==Node.DOCUMENT_TYPE_NODE )
            {
                // TBD: This should be a HIERARCHY_REQUEST_ERR
                throw new DOMException(
                        DOMException.HIERARCHY_REQUEST_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "HIERARCHY_REQUEST_ERR", null));
            }
            return n;
        case DELETE_CONTENTS:
            n.getParentNode().removeChild(n);
            return null;
        }
        return null;
    }

    /**
     * Utility method for traversing a single node when
     * we know a-priori that the node if partially
     * selected and is not a text node.
     *
     * @param n      The node to be traversed.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will simply
     *               return the original node.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but will
     *               return a cloned node.
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete the
     *               node from it's parent, but will return null.
     *               </ol>
     *
     * @return Returns a node that is the result of visiting the node.
     *         If the traversal operation is
     *         <code>DELETE_CONTENTS</code> the return value is null.
     */
    private Node traversePartiallySelected( Node n, int how )
    {
        switch( how )
        {
        case DELETE_CONTENTS:
            return null;
        case CLONE_CONTENTS:
        case EXTRACT_CONTENTS:
            return n.cloneNode( false );
        }
        return null;
    }

    /**
     * Utility method for traversing a text node that we know
     * a-priori to be on a left or right boundary of the range.
     * This method does not properly handle text nodes that contain
     * both the start and end points of the range.
     *
     * @param n      The node to be traversed.
     *
     * @param isLeft Is true if we are traversing the node as part of navigating
     *               the "left boundary" of the range.  If this value is false,
     *               it implies we are navigating the "right boundary" of the
     *               range.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will simply
     *               return the original node.
     *
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but will
     *               return a cloned node.
     *
     *               <li><code>DELETE_CONTENTS</code> - will delete the
     *               node from it's parent, but will return null.
     *               </ol>
     *
     * @return Returns a node that is the result of visiting the node.
     *         If the traversal operation is
     *         <code>DELETE_CONTENTS</code> the return value is null.
     */
    private Node traverseTextNode( Node n, boolean isLeft, int how )
    {
        String txtValue = n.getNodeValue();
        String newNodeValue;
        String oldNodeValue;

        if ( isLeft )
        {
            int offset = getStartOffset();
            newNodeValue = txtValue.substring( offset );
            oldNodeValue = txtValue.substring( 0, offset );
        }
        else
        {
            int offset = getEndOffset();
            newNodeValue = txtValue.substring( 0, offset );
            oldNodeValue = txtValue.substring( offset );
        }

        if ( how != CLONE_CONTENTS )
            n.setNodeValue( oldNodeValue );
        if ( how==DELETE_CONTENTS )
            return null;
        Node newNode = n.cloneNode( false );
        newNode.setNodeValue( newNodeValue );
        return newNode;
    }

    void checkIndex(Node refNode, int offset) throws DOMException
    {
        if (offset < 0) {
            throw new DOMException(
                DOMException.INDEX_SIZE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INDEX_SIZE_ERR", null));
        }

        int type = refNode.getNodeType();

        // If the node contains text, ensure that the
        // offset of the range is <= to the length of the text
        if (type == Node.TEXT_NODE
            || type == Node.CDATA_SECTION_NODE
            || type == Node.COMMENT_NODE
            || type == Node.PROCESSING_INSTRUCTION_NODE) {
            if (offset > refNode.getNodeValue().length()) {
                throw new DOMException(DOMException.INDEX_SIZE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INDEX_SIZE_ERR", null));
            }
        }
        else {
            // Since the node is not text, ensure that the offset
            // is valid with respect to the number of child nodes
            if (offset > refNode.getChildNodes().getLength()) {
                throw new DOMException(DOMException.INDEX_SIZE_ERR,
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INDEX_SIZE_ERR", null));
            }
        }
    }

        /**
         * Given a node, calculate what the Range's root container
         * for that node would be.
         */
        private Node getRootContainer( Node node )
        {
                if ( node==null )
                        return null;

                while( node.getParentNode()!=null )
                        node = node.getParentNode();
                return node;
        }

        /**
         * Returns true IFF the given node can serve as a container
         * for a range's boundary points.
         */
        private boolean isLegalContainer( Node node )
        {
                if ( node==null )
                        return false;

                while( node!=null )
                {
                        switch( node.getNodeType() )
                        {
                        case Node.ENTITY_NODE:
                        case Node.NOTATION_NODE:
                        case Node.DOCUMENT_TYPE_NODE:
                                return false;
                        }
                        node = node.getParentNode();
                }

                return true;
        }


        /**
         * Finds the root container for the given node and determines
         * if that root container is legal with respect to the
         * DOM 2 specification.  At present, that means the root
         * container must be either an attribute, a document,
         * or a document fragment.
         */
        private boolean hasLegalRootContainer( Node node )
        {
                if ( node==null )
                        return false;

                Node rootContainer = getRootContainer( node );
                switch( rootContainer.getNodeType() )
                {
                case Node.ATTRIBUTE_NODE:
                case Node.DOCUMENT_NODE:
                case Node.DOCUMENT_FRAGMENT_NODE:
                        return true;
                }
                return false;
        }

        /**
         * Returns true IFF the given node can be contained by
         * a range.
         */
        private boolean isLegalContainedNode( Node node )
        {
                if ( node==null )
                        return false;
                switch( node.getNodeType() )
                {
                case Node.DOCUMENT_NODE:
                case Node.DOCUMENT_FRAGMENT_NODE:
                case Node.ATTRIBUTE_NODE:
                case Node.ENTITY_NODE:
                case Node.NOTATION_NODE:
                        return false;
                }
                return true;
        }

    Node nextNode(Node node, boolean visitChildren) {

        if (node == null) return null;

        Node result;
        if (visitChildren) {
            result = node.getFirstChild();
            if (result != null) {
                return result;
            }
        }

        // if hasSibling, return sibling
        result = node.getNextSibling();
        if (result != null) {
            return result;
        }


        // return parent's 1st sibling.
        Node parent = node.getParentNode();
        while (parent != null
               && parent != fDocument
                ) {
            result = parent.getNextSibling();
            if (result != null) {
                return result;
            } else {
                parent = parent.getParentNode();
            }

        } // while (parent != null && parent != fRoot) {

        // end of list, return null
        return null;
    }

    /** is a an ancestor of b ? */
    boolean isAncestorOf(Node a, Node b) {
        for (Node node=b; node != null; node=node.getParentNode()) {
            if (node == a) return true;
        }
        return false;
    }

    /** what is the index of the child in the parent */
    int indexOf(Node child, Node parent) {
        if (child.getParentNode() != parent) return -1;
        int i = 0;
        for(Node node = parent.getFirstChild(); node!= child; node=node.getNextSibling()) {
            i++;
        }
        return i;
    }

    /**
     * Utility method to retrieve a child node by index.  This method
     * assumes the caller is trying to find out which node is
     * selected by the given index.  Note that if the index is
     * greater than the number of children, this implies that the
     * first node selected is the parent node itself.
     *
     * @param container A container node
     *
     * @param offset    An offset within the container for which a selected node should
     *                  be computed.  If the offset is less than zero, or if the offset
     *                  is greater than the number of children, the container is returned.
     *
     * @return Returns either a child node of the container or the
     *         container itself.
     */
    private Node getSelectedNode( Node container, int offset )
    {
        if ( container.getNodeType() == Node.TEXT_NODE )
            return container;

        // This case is an important convenience for
        // traverseRightBoundary()
        if ( offset<0 )
            return container;

        Node child = container.getFirstChild();
        while( child!=null && offset > 0 )
        {
            --offset;
            child = child.getNextSibling();
        }
        if ( child!=null )
            return child;
        return container;
    }

}