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

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

import java.util.Vector;

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


/** The RangeImpl class implements the org.w3c.dom.range.Range interface.
 *  <p> Please see the API documentation for the interface classes  
 *  and use the interfaces in your client programs.
 *
 * @version $Id: RangeImpl.java,v 1.28 2003/11/02 15:07:58 mrglavas Exp $
 */
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;
    
    
    /** The constructor. Clients must use DocumentRange.createRange(),
     *  because it registers the Range with the document, so it can 
     *  be fixed-up.
     */
    public RangeImpl(DocumentImpl document) {
        fDocument = document;
        fStartContainer = document;
        fEndContainer = document;
        fStartOffset = 0;
        fEndOffset = 0;
        fDetach = false;
    }
    
    public Node getStartContainer() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return fStartContainer;
    }
    
    public int getStartOffset() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return fStartOffset;
    }
    
    public Node getEndContainer() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return fEndContainer;
    }
    
    public int getEndOffset() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }    
        return fEndOffset;
    }
    
    public boolean getCollapsed() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        return (fStartContainer == fEndContainer 
             && fStartOffset == fEndOffset);
    }
    
    public Node getCommonAncestorContainer() {
        if ( fDetach ) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }
        Vector startV = new Vector();
        Node node;
        for (node=fStartContainer; node != null; 
             node=node.getParentNode()) 
        {
            startV.addElement(node);
        }
        Vector endV = new Vector();
        for (node=fEndContainer; node != null; 
             node=node.getParentNode()) 
        {
            endV.addElement(node);
        }
        int s = startV.size()-1;
        int e = endV.size()-1;
        Object result = null;
        while (s>=0 && e>=0) {
            if (startV.elementAt(s) == endV.elementAt(e)) {
                result = startV.elementAt(s);
            } else {
                break;
            }
            --s;
            --e;
        }
        return (Node)result; 
    }
    
    
    public void setStart(Node refNode, int offset)
                         throws RangeException, DOMException
    {
    	if( 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;
    }
    
    public void setEnd(Node refNode, int offset)
                       throws RangeException, DOMException
    {
    	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;
    }

    public void setStartBefore(Node refNode) 
        throws RangeException 
    {
    	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;
    }
    
    public void setStartAfter(Node refNode)
        throws RangeException
    {
    	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;
    }
    
    public void setEndBefore(Node refNode)
        throws RangeException
    {
    	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;
    }
                                            
    public void setEndAfter(Node refNode)
        throws RangeException
    {
    	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;
    }
    
    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( 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( 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( fDetach) {
    		throw new DOMException(
    		DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_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?
        
        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));
        }
       
        int type = newNode.getNodeType();
        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;

        //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 ) {     //update fEndOffset
                fEndOffset += (fEndContainer.getChildNodes().getLength() - currentChildren);
            }

        } 
    }
    
    public void surroundContents(Node newParent)
        throws DOMException, RangeException
    {
        if (newParent==null) return;
        
    	if( fDetach) {
    		throw new DOMException(
    		DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
    	}
        int type = newParent.getNodeType();
        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 root = getCommonAncestorContainer();
        
        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() {
        fDetach = true;
        fDocument.removeRange(this);
    }
    
    // 
    // Mutation functions
    //
    
    /** Signal other Ranges to update their start/end 
     *  containers/offsets. The data has already been split
     *  into the two Nodes.
     */
    void signalSplitData(Node node, Node newNode, int offset) {
        fSplitNode = node;
        // notify document
        fDocument.splitData(node, newNode, offset);
        fSplitNode = null;
    }
    
    /** Fix up this Range if another Range has split a Text Node
     *  into 2 Nodes.
     */
    void receiveSplitData(Node node, Node newNode, int offset) {
        if (node == null || newNode == null) return;
        if (fSplitNode == node) return;
        
        if (node == fStartContainer 
        && fStartContainer.getNodeType() == Node.TEXT_NODE) {
            if (fStartOffset > offset) {
                fStartOffset = fStartOffset - offset;
                fStartContainer = newNode;
            }
        }
        if (node == fEndContainer 
        && fEndContainer.getNodeType() == Node.TEXT_NODE) {
            if (fEndOffset > offset) {
                fEndOffset = fEndOffset-offset;
                fEndContainer = newNode;
            }
        }
        
    }
   
    /** This function inserts text into a Node and invokes
     *  a method to fix-up all other Ranges.
     */
    void deleteData(CharacterData node, int offset, int count) {
        fDeleteNode = node;
        node.deleteData( offset,  count);
        fDeleteNode = null;
    }
    
    
    /** This function is called from DOM.
     *  The  text has already beeen inserted.
     *  Fix-up any offsets.
     */
    void receiveDeletedText(Node node, int offset, int count) {
        if (node == null) return;
        if (fDeleteNode == node) return;
        if (node == fStartContainer 
        && fStartContainer.getNodeType() == Node.TEXT_NODE) {
            if (fStartOffset > offset+count) {
                fStartOffset = offset+(fStartOffset-(offset+count));
            } else 
            if (fStartOffset > offset) {
                fStartOffset = offset;
            }  
        }
        if (node == fEndContainer 
        && fEndContainer.getNodeType() == Node.TEXT_NODE) {
            if (fEndOffset > offset+count) {
                fEndOffset = offset+(fEndOffset-(offset+count));
            } else 
            if (fEndOffset > offset) {
                fEndOffset = offset;
            }  
        }
        
    }
   
    /** This function inserts text into a Node and invokes
     *  a method to fix-up all other Ranges.
     */
    void insertData(CharacterData node, int index, String insert) {
        fInsertNode = node;
        node.insertData( index,  insert);
        fInsertNode = null;
    }
    
    
    /** This function is called from DOM.
     *  The  text has already beeen inserted.
     *  Fix-up any offsets.
     */
    void receiveInsertedText(Node node, int index, int len) {
        if (node == null) return;
        if (fInsertNode == node) return;
        if (node == fStartContainer 
        && fStartContainer.getNodeType() == Node.TEXT_NODE) {
            if (index < fStartOffset) {
                fStartOffset = fStartOffset+len;
            }
        }
        if (node == fEndContainer 
        && fEndContainer.getNodeType() == Node.TEXT_NODE) {
            if (index < fEndOffset) {
                fEndOffset = fEndOffset+len;
            }
        }
        
    }
   
    /** This function is called from DOM.
     *  The  text has already beeen replaced.
     *  Fix-up any offsets.
     */
    void receiveReplacedText(Node node) {
        if (node == null) return;
        if (node == fStartContainer 
        && fStartContainer.getNodeType() == Node.TEXT_NODE) {
            fStartOffset = 0;
        }
        if (node == fEndContainer 
        && fEndContainer.getNodeType() == Node.TEXT_NODE) {
            fEndOffset = 0;
        }
        
    }
    
    /** This function is called from the DOM.
     *  This node has already been inserted into the DOM.
     *  Fix-up any offsets.
     */
    public void insertedNodeFromDOM(Node node) {
        if (node == null) return;
        if (fInsertNode == node) return;
        
        Node parent = node.getParentNode();
        
        if (parent == fStartContainer) {
            int index = indexOf(node, fStartContainer);
            if (index < fStartOffset) {
                fStartOffset++;
            }
        }
        
        if (parent == fEndContainer) {
            int index = indexOf(node, fEndContainer);
            if (index < fEndOffset) {
                fEndOffset++;
            }
        }
        
    }
    
    /** This function is called within Range 
     *  instead of Node.removeChild,
     *  so that the range can remember that it is actively
     *  removing this child.
     */
     
    Node fRemoveChild = null;
    Node removeChild(Node parent, Node child) {
        fRemoveChild = child;
        Node n = parent.removeChild(child);
        fRemoveChild = null;
        return n;
    }
    
    /** This function must be called by the DOM _BEFORE_
     *  a node is deleted, because at that time it is
     *  connected in the DOM tree, which we depend on.
     */
    void removeNode(Node node) {
        if (node == null) return;
        if (fRemoveChild == node) return;
        
        Node parent = node.getParentNode();
        
        if (parent == fStartContainer) {
            int index = indexOf(node, fStartContainer);
            if (index < fStartOffset) {
                fStartOffset--;
            }
        }
        
        if (parent == fEndContainer) {
            int index = indexOf(node, fEndContainer);
            if (index < fEndOffset) {
                fEndOffset--;
            }
        }
        //startContainer or endContainer or both is/are the ancestor(s) of the Node to be deleted
        if (parent != fStartContainer 
        ||  parent != fEndContainer) {
            if (isAncestorOf(node, fStartContainer)) {
                fStartContainer = parent;
                fStartOffset = indexOf( node, parent);
            }   
            if (isAncestorOf(node, fEndContainer)) {
                fEndContainer = parent;
                fEndOffset = indexOf( node, parent);
            }
        } 
        
    }
        
    //
    // Utility functions.
    //
    
    // parameters for traverseContents(int)
    //REVIST: use boolean, since there are only 2 now...
    static final int EXTRACT_CONTENTS = 1;
    static final int CLONE_CONTENTS = 2;
    static final int DELETE_CONTENTS = 3;
    
    /**
     * This is the master routine invoked to visit the nodes
     * selected by this range.  For each such node, different
     * actions are taken depending on the value of the
     * <code>how</code> argument.
     * 
     * @param how    Specifies what type of traversal is being
     *               requested (extract, clone, or delete).
     *               Legal values for this argument are:
     * 
     *               <ol>
     *               <li><code>EXTRACT_CONTENTS</code> - will produce
     *               a document fragment containing the range's content.
     *               Partially selected nodes are copied, but fully
     *               selected nodes are moved.
     *               
     *               <li><code>CLONE_CONTENTS</code> - will leave the
     *               context tree of the range undisturbed, but sill
     *               produced cloned content in a document fragment
     *               
     *               <li><code>DELETE_CONTENTS</code> - will delete from
     *               the context tree of the range, all fully selected
     *               nodes.
     *               </ol>
     * 
     * @return Returns a document fragment containing any
     *         copied or extracted nodes.  If the <code>how</code>
     *         parameter was <code>DELETE_CONTENTS</code>, the
     *         return value is null.
     */
    private DocumentFragment traverseContents( int how )
        throws DOMException
    {
        if (fStartContainer == null || fEndContainer == null) {
            return null; // REVIST: Throw exception?
        }
        
        //Check for a detached range.
        if( fDetach) {
            throw new DOMException(
                DOMException.INVALID_STATE_ERR, 
                DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
        }

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        return frag;
    }

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

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

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

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

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

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

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

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

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

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

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

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

        } 

        // should never occur
        return null;
    }

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

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

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

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

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

        } 

        // should never occur
        return null;

    }

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

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

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

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

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

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

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

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

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

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

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

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

		return true;
	}


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

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

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

    Node nextNode(Node node, boolean visitChildren) {
            
        if (node == null) return null;

        Node result;
        if (visitChildren) {
            result = node.getFirstChild();
            if (result != null) {
                return result;
            }
        }
            
        // if hasSibling, return sibling
        result = node.getNextSibling();
        if (result != null) {
            return result;
        }
        
                
        // return parent's 1st sibling.
        Node parent = node.getParentNode();
        while (parent != null
               && parent != fDocument
                ) {
            result = parent.getNextSibling();
            if (result != null) {
                return result;
            } else {
                parent = parent.getParentNode();
            }
                            
        } // while (parent != null && parent != fRoot) {
        
        // end of list, return null
        return null;            
    }
    
    /** is a an ancestor of b ? */
    boolean isAncestorOf(Node a, Node b) {
        for (Node node=b; node != null; node=node.getParentNode()) {
            if (node == a) return true;
        }
        return false;
    }

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

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

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

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

}