/*
 * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
 */
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.sun.org.apache.xerces.internal.dom;

import java.util.ArrayList;
import java.util.List;
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.
 
 Please see the API documentation for the interface classes
 and use the interfaces in your client programs.
@xerces.internal
@LastModified
: Oct 2017/** 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
 *
 * @LastModified: Oct 2017
 */
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.
/** 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));
        }
        List<Node> startV = new ArrayList<>();
        Node node;
        for (node=fStartContainer; node != null;
             node=node.getParentNode())
        {
            startV.add(node);
        }
        List<Node> endV = new ArrayList<>();
        for (node=fEndContainer; node != null;
             node=node.getParentNode())
        {
            endV.add(node);
        }
        int s = startV.size()-1;
        int e = endV.size()-1;
        Node result = null;
        while (s>=0 && e>=0) {
            if (startV.get(s) == endV.get(e)) {
                result = startV.get(s);
            } else {
                break;
            }
            --s;
            --e;
        }
        return 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.
/** 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.
/** 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.
/** 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.
/** 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.
/** 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.
/** 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.
/** 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.
/** 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.
/** 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.
/** 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
how argument.
Params:
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will produce
              a document fragment containing the range's content.
              Partially selected nodes are copied, but fully
              selected nodes are moved.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but sill
              produced cloned content in a document fragment
              
DELETE_CONTENTS - will delete from
              the context tree of the range, all fully selected
              nodes.
              
Returns:
Returns a document fragment containing any
        copied or extracted nodes.  If the how
        parameter was DELETE_CONTENTS, the
        return value is null./**
     * 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 traverse
method.
Params:
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will produce
              a document fragment containing the range's content.
              Partially selected nodes are copied, but fully
              selected nodes are moved.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but sill
              produced cloned content in a document fragment
              
DELETE_CONTENTS - will delete from
              the context tree of the range, all fully selected
              nodes.
              
Returns:
Returns a document fragment containing any
        copied or extracted nodes.  If the how
        parameter was DELETE_CONTENTS, the
        return value is null./**
     * 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
traverse method.
Params:
endAncestor – 
              The ancestor of the end container that is a direct child
              of the start container.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will produce
              a document fragment containing the range's content.
              Partially selected nodes are copied, but fully
              selected nodes are moved.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but sill
              produced cloned content in a document fragment
              
DELETE_CONTENTS - will delete from
              the context tree of the range, all fully selected
              nodes.
              
Returns:
Returns a document fragment containing any
        copied or extracted nodes.  If the how
        parameter was DELETE_CONTENTS, the
        return value is null./**
     * 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
traverse method.
Params:
startAncestor – 
              The ancestor of the start container that is a direct
              child of the end container.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will produce
              a document fragment containing the range's content.
              Partially selected nodes are copied, but fully
              selected nodes are moved.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but sill
              produced cloned content in a document fragment
              
DELETE_CONTENTS - will delete from
              the context tree of the range, all fully selected
              nodes.
              
Returns:
Returns a document fragment containing any
        copied or extracted nodes.  If the how
        parameter was DELETE_CONTENTS, the
        return value is null./**
     * 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 traverse method.
Params:
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.
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.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will produce
              a document fragment containing the range's content.
              Partially selected nodes are copied, but fully
              selected nodes are moved.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but sill
              produced cloned content in a document fragment
              
DELETE_CONTENTS - will delete from
              the context tree of the range, all fully selected
              nodes.
              
Returns:
Returns a document fragment containing any
        copied or extracted nodes.  If the how
        parameter was DELETE_CONTENTS, the
        return value is null./**
     * 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
how parameter.  It is a-priori assumed
by this method that the right boundary does
not contain the range's start container.

A "right boundary" is best visualized by thinking
of a sample tree:
                A
               /|\
              / | \
             /  |  \
            B   C   D
           /|\     /|\
          E F G   H I J

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:

Partially Selected Nodes: B, D

Fully Selected Nodes: F, G, C, H, I

The "right boundary" is the highest subtree node
that contains the ending container.  The root of
this subtree is always partially selected.

In this example, the nodes that are traversed
as "right boundary" nodes are: H, I, and D.
Params:
root –   The node that is the root of the "right boundary" subtree.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will produce
              a node containing the boundaries content.
              Partially selected nodes are copied, but fully
              selected nodes are moved.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but will
              produced cloned content.
              
DELETE_CONTENTS - will delete from
              the context tree of the range, all fully selected
              nodes within the boundary.
              
Returns:
Returns a node that is the result of visiting nodes.
        If the traversal operation is
        DELETE_CONTENTS the return value is null./**
     * 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
how parameter.  It is a-priori assumed
by this method that the left boundary does
not contain the range's end container.

A "left boundary" is best visualized by thinking
of a sample tree:
                A
               /|\
              / | \
             /  |  \
            B   C   D
           /|\     /|\
          E F G   H I J

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:

Partially Selected Nodes: B, D

Fully Selected Nodes: F, G, C, H, I

The "left boundary" is the highest subtree node
that contains the starting container.  The root of
this subtree is always partially selected.

In this example, the nodes that are traversed
as "left boundary" nodes are: F, G, and B.
Params:
root –   The node that is the root of the "left boundary" subtree.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will produce
              a node containing the boundaries content.
              Partially selected nodes are copied, but fully
              selected nodes are moved.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but will
              produced cloned content.
              
DELETE_CONTENTS - will delete from
              the context tree of the range, all fully selected
              nodes within the boundary.
              
Returns:
Returns a node that is the result of visiting nodes.
        If the traversal operation is
        DELETE_CONTENTS the return value is 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.
Params:
n –      The node to be traversed.
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.
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.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will simply
              return the original node.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but will
              return a cloned node.
              
DELETE_CONTENTS - will delete the
              node from it's parent, but will return null.
              
Returns:
Returns a node that is the result of visiting the node.
        If the traversal operation is
        DELETE_CONTENTS the return value is 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.
Params:
n –      The node to be traversed.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will simply
              return the original node.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but will
              return a cloned node.
              
DELETE_CONTENTS - will delete the
              node from it's parent, but will return null.
              
Returns:
Returns a node that is the result of visiting the node.
        If the traversal operation is
        DELETE_CONTENTS the return value is null./**
     * 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.
Params:
n –      The node to be traversed.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will simply
              return the original node.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but will
              return a cloned node.
              
DELETE_CONTENTS - will delete the
              node from it's parent, but will return null.
              
Returns:
Returns a node that is the result of visiting the node.
        If the traversal operation is
        DELETE_CONTENTS the return value is 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.
Params:
n –      The node to be traversed.
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.
how –    Specifies what type of traversal is being
              requested (extract, clone, or delete).
              Legal values for this argument are:
              

              
EXTRACT_CONTENTS - will simply
              return the original node.
              
CLONE_CONTENTS - will leave the
              context tree of the range undisturbed, but will
              return a cloned node.
              
DELETE_CONTENTS - will delete the
              node from it's parent, but will return null.
              
Returns:
Returns a node that is the result of visiting the node.
        If the traversal operation is
        DELETE_CONTENTS the return value is 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.
/**
         * 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.
/**
         * 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.
/**
         * 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.
/**
         * 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 ? /** 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 /** 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.
Params:
container – A container node
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.
Returns:
Returns either a child node of the container or the
        container itself./**
     * 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;
    }

}