Java example source code file (RangeImpl.java)

This example Java source code file (RangeImpl.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

clone_contents, delete_contents, documentfragment, dom, domexception, extract_contents, index_size_err, invalid_node_type_err, invalid_state_err, node, rangeexceptionimpl, revist, string, util, vector, wrong_document_err

The RangeImpl.java Java example source code

/*
 * reserved comment block
 * DO NOT REMOVE OR ALTER!
 */
/*
 * Copyright 1999-2005 The Apache Software Foundation.
 *
 * Licensed 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>
. Range(start;end): body,0; body,1
            // insert <h1>: 
. 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 argument.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li>EXTRACT_CONTENTS - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li>DELETE_CONTENTS - 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
     *         parameter was <code>DELETE_CONTENTS, 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
     * method.
     *
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     *
     *               <ol>
     *               <li>EXTRACT_CONTENTS - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li>DELETE_CONTENTS - 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
     *         parameter was <code>DELETE_CONTENTS, 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 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>EXTRACT_CONTENTS - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li>DELETE_CONTENTS - 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
     *         parameter was <code>DELETE_CONTENTS, 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 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>EXTRACT_CONTENTS - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li>DELETE_CONTENTS - 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
     *         parameter was <code>DELETE_CONTENTS, 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 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>EXTRACT_CONTENTS - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *
     *               <li>DELETE_CONTENTS - 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
     *         parameter was <code>DELETE_CONTENTS, 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 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>EXTRACT_CONTENTS - will produce
     *               a node containing the boundaries content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but will
     *               produced cloned content.
     *
     *               <li>DELETE_CONTENTS - 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 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 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>EXTRACT_CONTENTS - will produce
     *               a node containing the boundaries content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but will
     *               produced cloned content.
     *
     *               <li>DELETE_CONTENTS - 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 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>EXTRACT_CONTENTS - will simply
     *               return the original node.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but will
     *               return a cloned node.
     *
     *               <li>DELETE_CONTENTS - 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 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>EXTRACT_CONTENTS - will simply
     *               return the original node.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but will
     *               return a cloned node.
     *
     *               <li>DELETE_CONTENTS - 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 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>EXTRACT_CONTENTS - will simply
     *               return the original node.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but will
     *               return a cloned node.
     *
     *               <li>DELETE_CONTENTS - 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 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>EXTRACT_CONTENTS - will simply
     *               return the original node.
     *
     *               <li>CLONE_CONTENTS - will leave the
     *               context tree of the range undisturbed, but will
     *               return a cloned node.
     *
     *               <li>DELETE_CONTENTS - 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 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;
    }

}