DOMRangeImpl.cpp

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

/*
 * $Id$
 */

#include "DOMRangeImpl.hpp"
#include "DOMDocumentImpl.hpp"
#include "DOMDocumentFragmentImpl.hpp"
#include "DOMCommentImpl.hpp"
#include "DOMProcessingInstructionImpl.hpp"
#include "DOMCasts.hpp"

#include <xercesc/dom/DOMException.hpp>
#include <xercesc/dom/DOMDocument.hpp>
#include <xercesc/dom/DOMRangeException.hpp>
#include <xercesc/dom/DOMText.hpp>
#include <xercesc/dom/DOMProcessingInstruction.hpp>

#include <xercesc/framework/XMLBuffer.hpp>
#include <xercesc/util/Janitor.hpp>

XERCES_CPP_NAMESPACE_BEGIN


//---------------------
// C'tor and D'tor
//---------------------

DOMRangeImpl::DOMRangeImpl(DOMDocument* doc, MemoryManager* const manager)

    :   fStartContainer(doc),     
        fStartOffset(0),
        fEndContainer(doc),
        fEndOffset(0),        
        fCollapsed(true),
        fDocument(doc),   
        fDetached(false),
        fRemoveChild(0),
        fMemoryManager(manager)
{
}

DOMRangeImpl::DOMRangeImpl(const DOMRangeImpl& other)
:   DOMRange(other),
    fStartContainer(other.fStartContainer),
    fStartOffset(other.fStartOffset),
    fEndContainer(other.fEndContainer),
    fEndOffset(other.fEndOffset),
    fCollapsed(other.fCollapsed),
    fDocument(other.fDocument),
    fDetached(other.fDetached),
    fRemoveChild(other.fRemoveChild),
    fMemoryManager(other.fMemoryManager)
{
}

DOMRangeImpl::~DOMRangeImpl()
{
}


//-------------------------------
// Public getter functions
//-------------------------------


DOMNode* DOMRangeImpl::getStartContainer() const
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    return fStartContainer;
}

XMLSize_t DOMRangeImpl::getStartOffset() const
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    return fStartOffset;
}

DOMNode* DOMRangeImpl::getEndContainer() const
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    return fEndContainer;
}

XMLSize_t DOMRangeImpl::getEndOffset() const
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    return fEndOffset;
}



bool DOMRangeImpl::getCollapsed() const
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    return ((fStartContainer == fEndContainer)
             && (fStartOffset == fEndOffset));
}

//-------------------------------
// Public setter functions
//-------------------------------

void DOMRangeImpl::setStartContainer(const DOMNode* node)
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    fStartContainer = (DOMNode*) node;
}

void DOMRangeImpl::setStartOffset(XMLSize_t offset)
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    fStartOffset = offset;
}

void DOMRangeImpl::setEndContainer(const DOMNode* node)
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    fEndContainer = (DOMNode*) node;

}

void DOMRangeImpl::setEndOffset(XMLSize_t offset)
{
    if (fDetached)
    {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    fEndOffset = offset;
}

void DOMRangeImpl::setStart(const DOMNode* refNode, XMLSize_t offset)
{
    validateNode(refNode);
    checkIndex(refNode, offset);

    // error if not the same owner document
    if (fDocument != refNode->getOwnerDocument()) {
        if ( refNode != fDocument ) {
            collapse(true); //collapse the range positions to start
            fCollapsed = true;
            throw DOMException(
                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
        }
    }

    fStartContainer = (DOMNode*) refNode;
    fStartOffset    = offset;

    // they may be of same document, but not same root container
    // collapse if not the same root container
    if (!commonAncestorOf(refNode, fEndContainer))
        collapse(true);

    //compare the start and end boundary point
    //collapse if start point is after the end point
    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
        collapse(true); //collapse the range positions to start
    else
        fCollapsed = false;
}

void DOMRangeImpl::setEnd(const DOMNode* refNode, XMLSize_t offset)
{
    validateNode(refNode);
    checkIndex(refNode, offset);

    // error if not the same owner document
    if (fDocument != refNode->getOwnerDocument()) {
        if ( refNode != fDocument ) {
            collapse(false); //collapse the range positions to end
            fCollapsed = true;
            throw DOMException(
                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
        }
    }

    fEndContainer   = (DOMNode*) refNode;
    fEndOffset      = offset;

    // they may be of same document, but not same root container
    // collapse if not the same root container
    if (!commonAncestorOf(refNode, fStartContainer))
        collapse(false);

    //compare the start and end boundary point
    //collapse if start point is after the end point
    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
        collapse(false); //collapse the range positions to end
    else
        fCollapsed = false;
}

void DOMRangeImpl::setStartBefore(const DOMNode* refNode)
{
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }
    if ( !hasLegalRootContainer(refNode) || !isLegalContainedNode(refNode)) {
        throw DOMRangeException(
            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
    }

    // error if not the same owner document
    if (fDocument != refNode->getOwnerDocument()) {
        if ( refNode != fDocument ) {
            collapse(true); //collapse the range positions to start
            fCollapsed = true;
            throw DOMException(
                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
        }
    }

    fStartContainer = refNode->getParentNode();
   XMLSize_t i = 0;
    for (DOMNode* n = (DOMNode*) refNode; n!=0; n = n->getPreviousSibling()) {
        i++;
    }
    if (i == 0)
        fStartOffset = 0;
    else
        fStartOffset = i-1;

    // they may be of same document, but not same root container
    // collapse if not the same root container
    if (!commonAncestorOf(refNode, fEndContainer))
        collapse(true);

    //compare the start and end boundary point
    //collapse if start point is after the end point
    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
        collapse(true); //collapse the range positions to start
    else
        fCollapsed = false;
}

void DOMRangeImpl::setStartAfter(const DOMNode* refNode)
{
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }
    if ( !hasLegalRootContainer(refNode) || !isLegalContainedNode(refNode)) {
        throw DOMRangeException(
            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
    }

    // error if not the same owner document
    if (fDocument != refNode->getOwnerDocument()) {
        if ( refNode != fDocument ) {
            collapse(true); //collapse the range positions to start
            fCollapsed = true;
            throw DOMException(
                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
        }
    }

    fStartContainer = refNode->getParentNode();
    XMLSize_t i = 0;
    for (DOMNode* n = (DOMNode*) refNode; n!=0; n = n->getPreviousSibling()) {
        i++;
    }

    fStartOffset = i;

    // they may be of same document, but not same root container
    // collapse if not the same root container
    if (!commonAncestorOf(refNode, fEndContainer))
        collapse(true);

    //compare the start and end boundary point
    //collapse if start point is after the end point
    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
        collapse(true); //collapse the range positions to start
    else
        fCollapsed = false;
}

void DOMRangeImpl::setEndBefore(const DOMNode* refNode)
{
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }
    if ( !hasLegalRootContainer(refNode) || !isLegalContainedNode(refNode)) {
        throw DOMRangeException(
            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
    }

    // error if not the same owner document
    if (fDocument != refNode->getOwnerDocument()) {
        if ( refNode != fDocument ) {
            collapse(false); //collapse the range positions to end
            fCollapsed = true;
            throw DOMException(
                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
        }
    }

    fEndContainer = refNode->getParentNode();
    XMLSize_t i = 0;
    for (DOMNode* n = (DOMNode*) refNode; n!=0; n = n->getPreviousSibling(), i++) ;

    if (i< 1)
        fEndOffset = 0;
    else
        fEndOffset = i-1;

    // they may be of same document, but not same root container
    // collapse if not the same root container
    if (!commonAncestorOf(refNode, fStartContainer))
        collapse(false);

    //compare the start and end boundary point
    //collapse if start point is after the end point
    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
        collapse(false); //collapse the range positions to end
    else
        fCollapsed = false;
}

void DOMRangeImpl::setEndAfter(const DOMNode* refNode)
{
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }
    if ( !hasLegalRootContainer(refNode) || !isLegalContainedNode(refNode)) {
        throw DOMRangeException(
            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
    }

    // error if not the same owner document
    if (fDocument != refNode->getOwnerDocument()) {
        if ( refNode != fDocument ) {
            collapse(false); //collapse the range positions to end
            fCollapsed = true;
            throw DOMException(
                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
        }
    }

    fEndContainer = refNode->getParentNode();
    XMLSize_t i = 0;
    for (DOMNode* n = (DOMNode*) refNode; n!=0; n = n->getPreviousSibling(), i++) ;

    if (i ==0)
        fEndOffset = 0;
    else
        fEndOffset = i;

    // they may be of same document, but not same root container
    // collapse if not the same root container
    if (!commonAncestorOf(refNode, fStartContainer))
        collapse(false);

    //compare the start and end boundary point
    //collapse if start point is after the end point
    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
        collapse(false); //collapse the range positions to end
    else
        fCollapsed = false;
}
//-------------------------------
// Public Misc. functions
//-------------------------------
void DOMRangeImpl::detach()
{
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    ((DOMDocumentImpl *)fDocument)->removeRange(this);

    fDetached = true;

    //0ify nodes
    fStartContainer = 0;
    fStartOffset    = 0;
    fEndContainer   = 0;
    fEndOffset      = 0;
    fCollapsed      = true;

    fRemoveChild    = 0;
}

void DOMRangeImpl::collapse(bool toStart)
{
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

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

void DOMRangeImpl::selectNode(const DOMNode* refNode)
{
    validateNode(refNode);
    if ( !isLegalContainedNode(refNode)) {
        throw DOMRangeException(
            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
    }
    //First check for the text type node
    short type = refNode->getNodeType();
    if((type == DOMNode::TEXT_NODE
        || type == DOMNode::CDATA_SECTION_NODE
        || type == DOMNode::COMMENT_NODE
        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
    {
        //The node itself is the container.
        fStartContainer = (DOMNode*) refNode;
        fEndContainer   = (DOMNode*) refNode;

        //Select all the contents of the node
        fStartOffset = 0;
        if (type == DOMNode::PROCESSING_INSTRUCTION_NODE)
            fEndOffset = XMLString::stringLen(((DOMProcessingInstruction*)refNode)->getData());
        else
            fEndOffset = ((DOMText *)refNode)->getLength();
        return;
    }

    DOMNode* parent = refNode->getParentNode();
    if (parent != 0 ) // REVIST: what to do if it IS 0?
    {
        fStartContainer = parent;
        fEndContainer = parent;

        XMLSize_t i = 0;
        for (DOMNode* n = parent->getFirstChild(); n!=0 && n!=refNode; n = n->getNextSibling()) {
            i++;
        }

        fStartOffset = i;
        fEndOffset = fStartOffset+1;
    }
}

void DOMRangeImpl::selectNodeContents(const DOMNode* node)
{
    validateNode(node);

    fStartContainer = (DOMNode*) node;
    fEndContainer = (DOMNode*) node;

    fStartOffset = 0;
    short type = node->getNodeType();

    if((type == DOMNode::TEXT_NODE
        || type == DOMNode::CDATA_SECTION_NODE
        || type == DOMNode::COMMENT_NODE)) {

        fEndOffset = ((DOMText *)node)->getLength();
        return;
    }
    if (type == DOMNode::PROCESSING_INSTRUCTION_NODE) {
        fEndOffset = XMLString::stringLen(((DOMProcessingInstruction*)node)->getData());
        return;
    }

    DOMNode* first = node->getFirstChild();
    if (first == 0) {
        fEndOffset = 0;
        return;
    }
    XMLSize_t i = 0;
    for (DOMNode* n = first; n!=0; n = n->getNextSibling()) {
        i++;
    }
    fEndOffset = i;
}

void DOMRangeImpl::surroundContents(DOMNode* newParent)
{
    if (newParent==0) return;

    //check for elimination criteria
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    if (newParent->getOwnerDocument() !=fDocument) {
        throw DOMException(
            DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
    }

    int type = newParent->getNodeType();
    if ( !isLegalContainedNode(newParent)
        || type == DOMNode::DOCUMENT_TYPE_NODE)
    {
        throw DOMRangeException(
            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
    }

    DOMNode* realStart = fStartContainer;
    DOMNode* realEnd = fEndContainer;

    type = fStartContainer->getNodeType();
    if((type == DOMNode::TEXT_NODE
        || type == DOMNode::CDATA_SECTION_NODE
        || type == DOMNode::COMMENT_NODE
        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
        realStart = fStartContainer->getParentNode();
    }
    type = fEndContainer->getNodeType();
    if((type == DOMNode::TEXT_NODE
        || type == DOMNode::CDATA_SECTION_NODE
        || type == DOMNode::COMMENT_NODE
        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
        realEnd = fEndContainer->getParentNode();
    }

    if (realStart != realEnd) {
        throw DOMRangeException(
            DOMRangeException::BAD_BOUNDARYPOINTS_ERR, 0, fMemoryManager);
    }

    DOMDocumentFragment* frag = (DOMDocumentFragment*) extractContents();
    insertNode(newParent);
    newParent->appendChild(frag);
    selectNode(newParent);
}


short DOMRangeImpl::compareBoundaryPoints(DOMRange::CompareHow how, const DOMRange* srcRange) const
{
    if (fDocument != ((DOMRangeImpl*)srcRange)->fDocument) {
        throw DOMException(
            DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
    }
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    DOMNode* pointA;
    DOMNode* pointB;
    XMLSize_t offsetA, offsetB;

    switch (how)
    {
    case (DOMRange::START_TO_START) :
        pointB = srcRange->getStartContainer();
        pointA = fStartContainer;
        offsetB = srcRange->getStartOffset();
        offsetA = fStartOffset;
        break;
    case (DOMRange::START_TO_END) :
        pointB = srcRange->getStartContainer();
        pointA = fEndContainer;
        offsetB = srcRange->getStartOffset();
        offsetA = fEndOffset;
        break;
    case (DOMRange::END_TO_START) :
        pointB = srcRange->getEndContainer();
        pointA = fStartContainer;
        offsetB = srcRange->getEndOffset();
        offsetA = fStartOffset;
        break;
    case (DOMRange::END_TO_END) :
        pointB = srcRange->getEndContainer();
        pointA = fEndContainer;
        offsetB = srcRange->getEndOffset();
        offsetA = fEndOffset;
        break;
    default:
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    // case 1: same container
    if (pointA == pointB) {
        if (offsetA < offsetB) return -1; //A before B
        if (offsetA == offsetB) return 0; //A equal to B
        return 1; // A after B
    }
    // case 2: Child C of container A is ancestor of B
    for (DOMNode* node = pointA->getFirstChild(); node != 0; node=node->getNextSibling()) {
        if (isAncestorOf(node, pointB)) {
            XMLSize_t index = indexOf(node, pointA);
            if (offsetA <=  index) return -1;
            return 1;
        }
    }
    // case 3: Child C of container B is ancestor of A
    for (DOMNode* nd = pointB->getFirstChild(); nd != 0; nd=nd->getNextSibling()) {
        if (isAncestorOf(nd, pointA)) {
            XMLSize_t index = indexOf(nd, pointB);
            if (index < offsetB ) return -1;
            return 1; //B strictly before A
        }
    }

    // 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;
    DOMNode* n = 0;
    for ( n = pointB; n != 0; n = n->getParentNode() )
        depthDiff++;
    for ( n = pointA; n != 0; n = n->getParentNode() )
        depthDiff--;
    while (depthDiff > 0) {
        pointB = pointB->getParentNode();
        depthDiff--;
    }
    while (depthDiff < 0) {
        pointA = pointA->getParentNode();
        depthDiff++;
    }
    for (DOMNode* pB = pointB->getParentNode(),
         *pA = pointA->getParentNode();
         pB != pA;
         pB = pB->getParentNode(), pA = pA->getParentNode() )
    {
        pointB = pB;
        pointA = pA;
    }
    for ( n = pointB->getNextSibling();
         n != 0;
         n = n->getNextSibling() )
    {
        if (n == pointA) {
            return 1;
        }
    }
    return -1;
}


void DOMRangeImpl:: deleteContents()
{
    traverseContents(DELETE_CONTENTS);
}

DOMDocumentFragment* DOMRangeImpl::extractContents()
{
    checkReadOnly(fStartContainer, fEndContainer, fStartOffset, fEndOffset);
    return traverseContents(EXTRACT_CONTENTS);
}

DOMDocumentFragment* DOMRangeImpl::cloneContents() const
{
    // cast off const.
    return ((DOMRangeImpl *)this)->traverseContents(CLONE_CONTENTS);
}


void DOMRangeImpl::insertNode(DOMNode* newNode)
{
    if (newNode == 0) return; //don't have to do anything

    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    int type = newNode->getNodeType();
    if (type == DOMNode::ATTRIBUTE_NODE
        || type == DOMNode::ENTITY_NODE
        || type == DOMNode::NOTATION_NODE
        || type == DOMNode::DOCUMENT_NODE)
    {
        throw DOMRangeException(
            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
    }

    // Prevent cycles in the tree.
    //isKidOK() is not checked here as its taken care by insertBefore() function
    if (isAncestorOf( newNode, fStartContainer)) {
        throw DOMException(
            DOMException::HIERARCHY_REQUEST_ERR, 0, fMemoryManager);
    }

    for (DOMNode* aNode = fStartContainer; aNode!=0; aNode = aNode->getParentNode()) {
        if (castToNodeImpl(newNode)->isReadOnly()) {
        throw DOMException(
            DOMException::NO_MODIFICATION_ALLOWED_ERR, 0, fMemoryManager);
    }
    }

    if (fDocument != newNode->getOwnerDocument()) {
        throw DOMException(
            DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
    }


    DOMNode* parent;
    DOMNode* next;

    type = fStartContainer->getNodeType();
    if((type == DOMNode::TEXT_NODE
        || type == DOMNode::CDATA_SECTION_NODE
        || type == DOMNode::COMMENT_NODE
        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {

        //set 'parent' and 'next' here
        parent = fStartContainer->getParentNode();

        //split the text nodes
       if (fStartOffset > 0) {
           if (type == DOMNode::COMMENT_NODE)
               ((DOMCommentImpl*)fStartContainer)->splitText(fStartOffset);
           else if (type == DOMNode::PROCESSING_INSTRUCTION_NODE)
               ((DOMProcessingInstructionImpl*)fStartContainer)->splitText(fStartOffset);
           else
               ((DOMText*)fStartContainer)->splitText(fStartOffset);
       }

        //update the new start information later. After inserting the first newNode
        if (fStartOffset == 0)
            next = fStartContainer;
        else
            next = fStartContainer->getNextSibling();

    } // end of text handling
    else {
        parent = fStartContainer;

        next = fStartContainer->getFirstChild();
        for(XMLSize_t i = 0; (i < fStartOffset) && (next != 0); i++) {
            next=next->getNextSibling();
        }
    }

    if (parent != 0) {
        if (next != 0)
            parent->insertBefore(newNode, next);
        else
            parent->appendChild(newNode);
    }
}

DOMRange* DOMRangeImpl::cloneRange() const
{
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    DOMRange* range = fDocument->createRange();
    range->setStart(fStartContainer, fStartOffset);
    range->setEnd(fEndContainer, fEndOffset);

    return range;
}

const XMLCh* DOMRangeImpl::toString() const
{
    if( fDetached) {
        throw DOMException(
            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
    }

    if ((fStartContainer == fEndContainer) && (fEndOffset == fStartOffset))
        return XMLUni::fgZeroLenString;

    DOMNode* node = fStartContainer;
    DOMNode* stopNode = fEndContainer;

    XMLBuffer retStringBuf(1023, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
    short type = fStartContainer->getNodeType();
    if((type == DOMNode::TEXT_NODE
        || type == DOMNode::CDATA_SECTION_NODE
        || type == DOMNode::COMMENT_NODE
        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
        if (fStartContainer == fEndContainer) {
            XMLCh* tempString;
            XMLCh temp[4000];
            if ((fEndOffset-fStartOffset) >= 3999)
                tempString = (XMLCh*) fMemoryManager->allocate
                (
                    (fEndOffset - fStartOffset + 1) * sizeof(XMLCh)
                );//new XMLCh[fEndOffset-fStartOffset+1];
            else
                tempString = temp;

            XMLString::subString(tempString, fStartContainer->getNodeValue(), fStartOffset, fEndOffset, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
            const XMLCh* retString = ((DOMDocumentImpl *)fDocument)->getPooledString(tempString);

            if ((fEndOffset-fStartOffset) >= 3999)
                fMemoryManager->deallocate(tempString);//delete[] tempString;

            return retString;
        } else {
            XMLSize_t length = XMLString::stringLen(fStartContainer->getNodeValue());
            if (length != fStartOffset) {

                XMLCh* tempString;
                XMLCh temp[4000];
                if ((length - fStartOffset) >= 3999)
                    tempString = (XMLCh*) fMemoryManager->allocate
                    (
                        (length - fStartOffset + 1) * sizeof(XMLCh)
                    );//new XMLCh[length - fStartOffset+1];
                else
                    tempString = temp;

                XMLString::subString(tempString, fStartContainer->getNodeValue(), fStartOffset, length, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
                retStringBuf.append(tempString);

                if ((length - fStartOffset) >= 3999)
                    fMemoryManager->deallocate(tempString);//delete[] tempString;
            }

            node = nextNode(node, true);
        }
    }else { //fStartContainer is not a TextNode
        node=node->getFirstChild();
        if (fStartOffset>0) { //find a first node within a range, specified by fStartOffset
            XMLSize_t counter = 0;
            while (counter<fStartOffset && node!=0) {
                node=node->getNextSibling();
                counter++;
            }
        }
        if (node == 0) {
            node = nextNode(fStartContainer,false);
        }
    }

    type = fEndContainer->getNodeType();
    if((type != DOMNode::TEXT_NODE
        && type != DOMNode::CDATA_SECTION_NODE
        && type != DOMNode::COMMENT_NODE
        && type != DOMNode::PROCESSING_INSTRUCTION_NODE)) {
        int i=(int)fEndOffset;
        stopNode = fEndContainer->getFirstChild();
        while( i>0 && stopNode!=0 ){
            --i;
            stopNode = stopNode->getNextSibling();
        }
        if ( stopNode == 0 )
            stopNode = nextNode( fEndContainer, false );
    }

    while (node != stopNode) {  //look into all kids of the Range
        if (node == 0) break;
        type = node->getNodeType();

        if((type == DOMNode::TEXT_NODE
            || type == DOMNode::CDATA_SECTION_NODE
            || type == DOMNode::COMMENT_NODE
            || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
            retStringBuf.append(node->getNodeValue());
        }
        node = nextNode(node, true);
    }

    type = fEndContainer->getNodeType();
    if((type == DOMNode::TEXT_NODE
        || type == DOMNode::CDATA_SECTION_NODE
        || type == DOMNode::COMMENT_NODE
        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {

        if (fEndOffset != 0) {

            XMLCh* tempString;
            XMLCh temp[4000];
            if (fEndOffset >= 3999)
                tempString = (XMLCh*) fMemoryManager->allocate
                (
                    (fEndOffset+1) * sizeof(XMLCh)
                );//new XMLCh[fEndOffset+1];
            else
                tempString = temp;

            XMLString::subString(tempString, fEndContainer->getNodeValue(), 0, fEndOffset, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
            retStringBuf.append(tempString);

            if (fEndOffset >= 3999)
                fMemoryManager->deallocate(tempString);//delete[] tempString;
        }
    }
    return ((DOMDocumentImpl *)fDocument)->getPooledString(retStringBuf.getRawBuffer());
}

DOMDocument* DOMRangeImpl::getDocument()
{
    return fDocument;
}

const DOMNode* DOMRangeImpl::getCommonAncestorContainer() const
{
     return commonAncestorOf(fStartContainer, fEndContainer);

}

void DOMRangeImpl::release()
{
    detach();
    // for performance reason, do not recycle pointer
    // chance that this is allocated again and again is not usual
}

//---------------------
//private functions
//---------------------

bool DOMRangeImpl::isValidAncestorType(const DOMNode* node) const
{
    for (DOMNode* aNode = (DOMNode*) node; aNode!=0; aNode = aNode->getParentNode()) {
        short type = aNode->getNodeType();
        if ( type == DOMNode::ENTITY_NODE
            || type == DOMNode::NOTATION_NODE
            || type == DOMNode::DOCUMENT_TYPE_NODE)
            return false;
    }
    return true;
}

bool DOMRangeImpl::isAncestorOf(const DOMNode* a, const DOMNode* b) {
    for (DOMNode* node = (DOMNode*) b; node != 0; node=node->getParentNode()) {
        if  (node == a) return true;
    }
    return false;
}

bool DOMRangeImpl::hasLegalRootContainer(const DOMNode* node) const {
    if ( node==0 )
        return false;

    DOMNode* rootContainer = (DOMNode*)node;
    for (; rootContainer->getParentNode()!=0; rootContainer = rootContainer->getParentNode())
        ;

    switch( rootContainer->getNodeType() ) {
        case DOMNode::ATTRIBUTE_NODE:
        case DOMNode::DOCUMENT_NODE:
        case DOMNode::DOCUMENT_FRAGMENT_NODE: