source: icXML/icXML-devel/src/xercesc/dom/impl/DOMRangeImpl.cpp @ 2722

Last change on this file since 2722 was 2722, checked in by cameron, 6 years ago

Original Xerces files with import mods for icxercesc

File size: 61.5 KB
Line 
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements.  See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License.  You may obtain a copy of the License at
8 *
9 *      http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18/*
19 * $Id: DOMRangeImpl.cpp 676911 2008-07-15 13:27:32Z amassari $
20 */
21
22#include "DOMRangeImpl.hpp"
23#include "DOMDocumentImpl.hpp"
24#include "DOMDocumentFragmentImpl.hpp"
25#include "DOMCommentImpl.hpp"
26#include "DOMProcessingInstructionImpl.hpp"
27#include "DOMCasts.hpp"
28
29#include <xercesc/dom/DOMException.hpp>
30#include <xercesc/dom/DOMDocument.hpp>
31#include <xercesc/dom/DOMRangeException.hpp>
32#include <xercesc/dom/DOMText.hpp>
33#include <xercesc/dom/DOMProcessingInstruction.hpp>
34
35#include <icxercesc/framework/XMLBuffer.hpp>
36#include <xercesc/util/Janitor.hpp>
37
38XERCES_CPP_NAMESPACE_BEGIN
39
40
41//---------------------
42// C'tor and D'tor
43//---------------------
44
45DOMRangeImpl::DOMRangeImpl(DOMDocument* doc, MemoryManager* const manager)
46
47    :   fStartContainer(doc),     
48        fStartOffset(0),
49        fEndContainer(doc),
50        fEndOffset(0),       
51        fCollapsed(true),
52        fDocument(doc),   
53        fDetached(false),
54        fRemoveChild(0),
55        fMemoryManager(manager)
56{
57}
58
59DOMRangeImpl::DOMRangeImpl(const DOMRangeImpl& other)
60:   DOMRange(other),
61    fStartContainer(other.fStartContainer),
62    fStartOffset(other.fStartOffset),
63    fEndContainer(other.fEndContainer),
64    fEndOffset(other.fEndOffset),
65    fCollapsed(other.fCollapsed),
66    fDocument(other.fDocument),
67    fDetached(other.fDetached),
68    fRemoveChild(other.fRemoveChild),
69    fMemoryManager(other.fMemoryManager)
70{
71}
72
73DOMRangeImpl::~DOMRangeImpl()
74{
75}
76
77
78//-------------------------------
79// Public getter functions
80//-------------------------------
81
82
83DOMNode* DOMRangeImpl::getStartContainer() const
84{
85    if (fDetached)
86    {
87        throw DOMException(
88            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
89    }
90
91    return fStartContainer;
92}
93
94XMLSize_t DOMRangeImpl::getStartOffset() const
95{
96    if (fDetached)
97    {
98        throw DOMException(
99            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
100    }
101
102    return fStartOffset;
103}
104
105DOMNode* DOMRangeImpl::getEndContainer() const
106{
107    if (fDetached)
108    {
109        throw DOMException(
110            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
111    }
112
113    return fEndContainer;
114}
115
116XMLSize_t DOMRangeImpl::getEndOffset() const
117{
118    if (fDetached)
119    {
120        throw DOMException(
121            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
122    }
123
124    return fEndOffset;
125}
126
127
128
129bool DOMRangeImpl::getCollapsed() const
130{
131    if (fDetached)
132    {
133        throw DOMException(
134            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
135    }
136
137    return ((fStartContainer == fEndContainer)
138             && (fStartOffset == fEndOffset));
139}
140
141//-------------------------------
142// Public setter functions
143//-------------------------------
144
145void DOMRangeImpl::setStartContainer(const DOMNode* node)
146{
147    if (fDetached)
148    {
149        throw DOMException(
150            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
151    }
152
153    fStartContainer = (DOMNode*) node;
154}
155
156void DOMRangeImpl::setStartOffset(XMLSize_t offset)
157{
158    if (fDetached)
159    {
160        throw DOMException(
161            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
162    }
163
164    fStartOffset = offset;
165}
166
167void DOMRangeImpl::setEndContainer(const DOMNode* node)
168{
169    if (fDetached)
170    {
171        throw DOMException(
172            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
173    }
174
175    fEndContainer = (DOMNode*) node;
176
177}
178
179void DOMRangeImpl::setEndOffset(XMLSize_t offset)
180{
181    if (fDetached)
182    {
183        throw DOMException(
184            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
185    }
186
187    fEndOffset = offset;
188}
189
190void DOMRangeImpl::setStart(const DOMNode* refNode, XMLSize_t offset)
191{
192    validateNode(refNode);
193    checkIndex(refNode, offset);
194
195    // error if not the same owner document
196    if (fDocument != refNode->getOwnerDocument()) {
197        if ( refNode != fDocument ) {
198            collapse(true); //collapse the range positions to start
199            fCollapsed = true;
200            throw DOMException(
201                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
202        }
203    }
204
205    fStartContainer = (DOMNode*) refNode;
206    fStartOffset    = offset;
207
208    // they may be of same document, but not same root container
209    // collapse if not the same root container
210    if (!commonAncestorOf(refNode, fEndContainer))
211        collapse(true);
212
213    //compare the start and end boundary point
214    //collapse if start point is after the end point
215    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
216        collapse(true); //collapse the range positions to start
217    else
218        fCollapsed = false;
219}
220
221void DOMRangeImpl::setEnd(const DOMNode* refNode, XMLSize_t offset)
222{
223    validateNode(refNode);
224    checkIndex(refNode, offset);
225
226    // error if not the same owner document
227    if (fDocument != refNode->getOwnerDocument()) {
228        if ( refNode != fDocument ) {
229            collapse(false); //collapse the range positions to end
230            fCollapsed = true;
231            throw DOMException(
232                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
233        }
234    }
235
236    fEndContainer   = (DOMNode*) refNode;
237    fEndOffset      = offset;
238
239    // they may be of same document, but not same root container
240    // collapse if not the same root container
241    if (!commonAncestorOf(refNode, fStartContainer))
242        collapse(false);
243
244    //compare the start and end boundary point
245    //collapse if start point is after the end point
246    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
247        collapse(false); //collapse the range positions to end
248    else
249        fCollapsed = false;
250}
251
252void DOMRangeImpl::setStartBefore(const DOMNode* refNode)
253{
254    if( fDetached) {
255        throw DOMException(
256            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
257    }
258    if ( !hasLegalRootContainer(refNode) || !isLegalContainedNode(refNode)) {
259        throw DOMRangeException(
260            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
261    }
262
263    // error if not the same owner document
264    if (fDocument != refNode->getOwnerDocument()) {
265        if ( refNode != fDocument ) {
266            collapse(true); //collapse the range positions to start
267            fCollapsed = true;
268            throw DOMException(
269                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
270        }
271    }
272
273    fStartContainer = refNode->getParentNode();
274   XMLSize_t i = 0;
275    for (DOMNode* n = (DOMNode*) refNode; n!=0; n = n->getPreviousSibling()) {
276        i++;
277    }
278    if (i == 0)
279        fStartOffset = 0;
280    else
281        fStartOffset = i-1;
282
283    // they may be of same document, but not same root container
284    // collapse if not the same root container
285    if (!commonAncestorOf(refNode, fEndContainer))
286        collapse(true);
287
288    //compare the start and end boundary point
289    //collapse if start point is after the end point
290    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
291        collapse(true); //collapse the range positions to start
292    else
293        fCollapsed = false;
294}
295
296void DOMRangeImpl::setStartAfter(const DOMNode* refNode)
297{
298    if( fDetached) {
299        throw DOMException(
300            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
301    }
302    if ( !hasLegalRootContainer(refNode) || !isLegalContainedNode(refNode)) {
303        throw DOMRangeException(
304            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
305    }
306
307    // error if not the same owner document
308    if (fDocument != refNode->getOwnerDocument()) {
309        if ( refNode != fDocument ) {
310            collapse(true); //collapse the range positions to start
311            fCollapsed = true;
312            throw DOMException(
313                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
314        }
315    }
316
317    fStartContainer = refNode->getParentNode();
318    XMLSize_t i = 0;
319    for (DOMNode* n = (DOMNode*) refNode; n!=0; n = n->getPreviousSibling()) {
320        i++;
321    }
322
323    fStartOffset = i;
324
325    // they may be of same document, but not same root container
326    // collapse if not the same root container
327    if (!commonAncestorOf(refNode, fEndContainer))
328        collapse(true);
329
330    //compare the start and end boundary point
331    //collapse if start point is after the end point
332    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
333        collapse(true); //collapse the range positions to start
334    else
335        fCollapsed = false;
336}
337
338void DOMRangeImpl::setEndBefore(const DOMNode* refNode)
339{
340    if( fDetached) {
341        throw DOMException(
342            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
343    }
344    if ( !hasLegalRootContainer(refNode) || !isLegalContainedNode(refNode)) {
345        throw DOMRangeException(
346            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
347    }
348
349    // error if not the same owner document
350    if (fDocument != refNode->getOwnerDocument()) {
351        if ( refNode != fDocument ) {
352            collapse(false); //collapse the range positions to end
353            fCollapsed = true;
354            throw DOMException(
355                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
356        }
357    }
358
359    fEndContainer = refNode->getParentNode();
360    XMLSize_t i = 0;
361    for (DOMNode* n = (DOMNode*) refNode; n!=0; n = n->getPreviousSibling(), i++) ;
362
363    if (i< 1)
364        fEndOffset = 0;
365    else
366        fEndOffset = i-1;
367
368    // they may be of same document, but not same root container
369    // collapse if not the same root container
370    if (!commonAncestorOf(refNode, fStartContainer))
371        collapse(false);
372
373    //compare the start and end boundary point
374    //collapse if start point is after the end point
375    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
376        collapse(false); //collapse the range positions to end
377    else
378        fCollapsed = false;
379}
380
381void DOMRangeImpl::setEndAfter(const DOMNode* refNode)
382{
383    if( fDetached) {
384        throw DOMException(
385            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
386    }
387    if ( !hasLegalRootContainer(refNode) || !isLegalContainedNode(refNode)) {
388        throw DOMRangeException(
389            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
390    }
391
392    // error if not the same owner document
393    if (fDocument != refNode->getOwnerDocument()) {
394        if ( refNode != fDocument ) {
395            collapse(false); //collapse the range positions to end
396            fCollapsed = true;
397            throw DOMException(
398                DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
399        }
400    }
401
402    fEndContainer = refNode->getParentNode();
403    XMLSize_t i = 0;
404    for (DOMNode* n = (DOMNode*) refNode; n!=0; n = n->getPreviousSibling(), i++) ;
405
406    if (i ==0)
407        fEndOffset = 0;
408    else
409        fEndOffset = i;
410
411    // they may be of same document, but not same root container
412    // collapse if not the same root container
413    if (!commonAncestorOf(refNode, fStartContainer))
414        collapse(false);
415
416    //compare the start and end boundary point
417    //collapse if start point is after the end point
418    if(compareBoundaryPoints(DOMRange::END_TO_START, this) == 1)
419        collapse(false); //collapse the range positions to end
420    else
421        fCollapsed = false;
422}
423//-------------------------------
424// Public Misc. functions
425//-------------------------------
426void DOMRangeImpl::detach()
427{
428    if( fDetached) {
429        throw DOMException(
430            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
431    }
432
433    ((DOMDocumentImpl *)fDocument)->removeRange(this);
434
435    fDetached = true;
436
437    //0ify nodes
438    fStartContainer = 0;
439    fStartOffset    = 0;
440    fEndContainer   = 0;
441    fEndOffset      = 0;
442    fCollapsed      = true;
443
444    fRemoveChild    = 0;
445}
446
447void DOMRangeImpl::collapse(bool toStart)
448{
449    if( fDetached) {
450        throw DOMException(
451            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
452    }
453
454    if (toStart) {
455        fEndContainer = fStartContainer;
456        fEndOffset = fStartOffset;
457    } else {
458        fStartContainer = fEndContainer;
459        fStartOffset = fEndOffset;
460    }
461    fCollapsed = true;
462}
463
464void DOMRangeImpl::selectNode(const DOMNode* refNode)
465{
466    validateNode(refNode);
467    if ( !isLegalContainedNode(refNode)) {
468        throw DOMRangeException(
469            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
470    }
471    //First check for the text type node
472    short type = refNode->getNodeType();
473    if((type == DOMNode::TEXT_NODE
474        || type == DOMNode::CDATA_SECTION_NODE
475        || type == DOMNode::COMMENT_NODE
476        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
477    {
478        //The node itself is the container.
479        fStartContainer = (DOMNode*) refNode;
480        fEndContainer   = (DOMNode*) refNode;
481
482        //Select all the contents of the node
483        fStartOffset = 0;
484        if (type == DOMNode::PROCESSING_INSTRUCTION_NODE)
485            fEndOffset = XMLString::stringLen(((DOMProcessingInstruction*)refNode)->getData());
486        else
487            fEndOffset = ((DOMText *)refNode)->getLength();
488        return;
489    }
490
491    DOMNode* parent = refNode->getParentNode();
492    if (parent != 0 ) // REVIST: what to do if it IS 0?
493    {
494        fStartContainer = parent;
495        fEndContainer = parent;
496
497        XMLSize_t i = 0;
498        for (DOMNode* n = parent->getFirstChild(); n!=0 && n!=refNode; n = n->getNextSibling()) {
499            i++;
500        }
501
502        fStartOffset = i;
503        fEndOffset = fStartOffset+1;
504    }
505}
506
507void DOMRangeImpl::selectNodeContents(const DOMNode* node)
508{
509    validateNode(node);
510
511    fStartContainer = (DOMNode*) node;
512    fEndContainer = (DOMNode*) node;
513
514    fStartOffset = 0;
515    short type = node->getNodeType();
516
517    if((type == DOMNode::TEXT_NODE
518        || type == DOMNode::CDATA_SECTION_NODE
519        || type == DOMNode::COMMENT_NODE)) {
520
521        fEndOffset = ((DOMText *)node)->getLength();
522        return;
523    }
524    if (type == DOMNode::PROCESSING_INSTRUCTION_NODE) {
525        fEndOffset = XMLString::stringLen(((DOMProcessingInstruction*)node)->getData());
526        return;
527    }
528
529    DOMNode* first = node->getFirstChild();
530    if (first == 0) {
531        fEndOffset = 0;
532        return;
533    }
534    XMLSize_t i = 0;
535    for (DOMNode* n = first; n!=0; n = n->getNextSibling()) {
536        i++;
537    }
538    fEndOffset = i;
539}
540
541void DOMRangeImpl::surroundContents(DOMNode* newParent)
542{
543    if (newParent==0) return;
544
545    //check for elimination criteria
546    if( fDetached) {
547        throw DOMException(
548            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
549    }
550
551    if (newParent->getOwnerDocument() !=fDocument) {
552        throw DOMException(
553            DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
554    }
555
556    int type = newParent->getNodeType();
557    if ( !isLegalContainedNode(newParent)
558        || type == DOMNode::DOCUMENT_TYPE_NODE)
559    {
560        throw DOMRangeException(
561            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
562    }
563
564    DOMNode* realStart = fStartContainer;
565    DOMNode* realEnd = fEndContainer;
566
567    type = fStartContainer->getNodeType();
568    if((type == DOMNode::TEXT_NODE
569        || type == DOMNode::CDATA_SECTION_NODE
570        || type == DOMNode::COMMENT_NODE
571        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
572        realStart = fStartContainer->getParentNode();
573    }
574    type = fEndContainer->getNodeType();
575    if((type == DOMNode::TEXT_NODE
576        || type == DOMNode::CDATA_SECTION_NODE
577        || type == DOMNode::COMMENT_NODE
578        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
579        realEnd = fEndContainer->getParentNode();
580    }
581
582    if (realStart != realEnd) {
583        throw DOMRangeException(
584            DOMRangeException::BAD_BOUNDARYPOINTS_ERR, 0, fMemoryManager);
585    }
586
587    DOMDocumentFragment* frag = (DOMDocumentFragment*) extractContents();
588    insertNode(newParent);
589    newParent->appendChild(frag);
590    selectNode(newParent);
591}
592
593
594short DOMRangeImpl::compareBoundaryPoints(DOMRange::CompareHow how, const DOMRange* srcRange) const
595{
596    if (fDocument != ((DOMRangeImpl*)srcRange)->fDocument) {
597        throw DOMException(
598            DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
599    }
600    if( fDetached) {
601        throw DOMException(
602            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
603    }
604
605    DOMNode* pointA;
606    DOMNode* pointB;
607    XMLSize_t offsetA, offsetB;
608
609    switch (how)
610    {
611    case (DOMRange::START_TO_START) :
612        pointB = srcRange->getStartContainer();
613        pointA = fStartContainer;
614        offsetB = srcRange->getStartOffset();
615        offsetA = fStartOffset;
616        break;
617    case (DOMRange::START_TO_END) :
618        pointB = srcRange->getStartContainer();
619        pointA = fEndContainer;
620        offsetB = srcRange->getStartOffset();
621        offsetA = fEndOffset;
622        break;
623    case (DOMRange::END_TO_START) :
624        pointB = srcRange->getEndContainer();
625        pointA = fStartContainer;
626        offsetB = srcRange->getEndOffset();
627        offsetA = fStartOffset;
628        break;
629    case (DOMRange::END_TO_END) :
630        pointB = srcRange->getEndContainer();
631        pointA = fEndContainer;
632        offsetB = srcRange->getEndOffset();
633        offsetA = fEndOffset;
634        break;
635    default:
636        throw DOMException(
637            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
638    }
639
640    // case 1: same container
641    if (pointA == pointB) {
642        if (offsetA < offsetB) return -1; //A before B
643        if (offsetA == offsetB) return 0; //A equal to B
644        return 1; // A after B
645    }
646    // case 2: Child C of container A is ancestor of B
647    for (DOMNode* node = pointA->getFirstChild(); node != 0; node=node->getNextSibling()) {
648        if (isAncestorOf(node, pointB)) {
649            XMLSize_t index = indexOf(node, pointA);
650            if (offsetA <=  index) return -1;
651            return 1;
652        }
653    }
654    // case 3: Child C of container B is ancestor of A
655    for (DOMNode* nd = pointB->getFirstChild(); nd != 0; nd=nd->getNextSibling()) {
656        if (isAncestorOf(nd, pointA)) {
657            XMLSize_t index = indexOf(nd, pointB);
658            if (index < offsetB ) return -1;
659            return 1; //B strictly before A
660        }
661    }
662
663    // case 4: preorder traversal of context tree.
664    // Instead of literally walking the context tree in pre-order,
665    // we use relative node depth walking which is usually faster
666
667    int depthDiff = 0;
668    DOMNode* n = 0;
669    for ( n = pointB; n != 0; n = n->getParentNode() )
670        depthDiff++;
671    for ( n = pointA; n != 0; n = n->getParentNode() )
672        depthDiff--;
673    while (depthDiff > 0) {
674        pointB = pointB->getParentNode();
675        depthDiff--;
676    }
677    while (depthDiff < 0) {
678        pointA = pointA->getParentNode();
679        depthDiff++;
680    }
681    for (DOMNode* pB = pointB->getParentNode(),
682         *pA = pointA->getParentNode();
683         pB != pA;
684         pB = pB->getParentNode(), pA = pA->getParentNode() )
685    {
686        pointB = pB;
687        pointA = pA;
688    }
689    for ( n = pointB->getNextSibling();
690         n != 0;
691         n = n->getNextSibling() )
692    {
693        if (n == pointA) {
694            return 1;
695        }
696    }
697    return -1;
698}
699
700
701void DOMRangeImpl:: deleteContents()
702{
703    traverseContents(DELETE_CONTENTS);
704}
705
706DOMDocumentFragment* DOMRangeImpl::extractContents()
707{
708    checkReadOnly(fStartContainer, fEndContainer, fStartOffset, fEndOffset);
709    return traverseContents(EXTRACT_CONTENTS);
710}
711
712DOMDocumentFragment* DOMRangeImpl::cloneContents() const
713{
714    // cast off const.
715    return ((DOMRangeImpl *)this)->traverseContents(CLONE_CONTENTS);
716}
717
718
719void DOMRangeImpl::insertNode(DOMNode* newNode)
720{
721    if (newNode == 0) return; //don't have to do anything
722
723    if( fDetached) {
724        throw DOMException(
725            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
726    }
727
728    int type = newNode->getNodeType();
729    if (type == DOMNode::ATTRIBUTE_NODE
730        || type == DOMNode::ENTITY_NODE
731        || type == DOMNode::NOTATION_NODE
732        || type == DOMNode::DOCUMENT_NODE)
733    {
734        throw DOMRangeException(
735            DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
736    }
737
738    // Prevent cycles in the tree.
739    //isKidOK() is not checked here as its taken care by insertBefore() function
740    if (isAncestorOf( newNode, fStartContainer)) {
741        throw DOMException(
742            DOMException::HIERARCHY_REQUEST_ERR, 0, fMemoryManager);
743    }
744
745    for (DOMNode* aNode = fStartContainer; aNode!=0; aNode = aNode->getParentNode()) {
746        if (castToNodeImpl(newNode)->isReadOnly()) {
747        throw DOMException(
748            DOMException::NO_MODIFICATION_ALLOWED_ERR, 0, fMemoryManager);
749    }
750    }
751
752    if (fDocument != newNode->getOwnerDocument()) {
753        throw DOMException(
754            DOMException::WRONG_DOCUMENT_ERR, 0, fMemoryManager);
755    }
756
757
758    DOMNode* parent;
759    DOMNode* next;
760
761    type = fStartContainer->getNodeType();
762    if((type == DOMNode::TEXT_NODE
763        || type == DOMNode::CDATA_SECTION_NODE
764        || type == DOMNode::COMMENT_NODE
765        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
766
767        //set 'parent' and 'next' here
768        parent = fStartContainer->getParentNode();
769
770        //split the text nodes
771       if (fStartOffset > 0) {
772           if (type == DOMNode::COMMENT_NODE)
773               ((DOMCommentImpl*)fStartContainer)->splitText(fStartOffset);
774           else if (type == DOMNode::PROCESSING_INSTRUCTION_NODE)
775               ((DOMProcessingInstructionImpl*)fStartContainer)->splitText(fStartOffset);
776           else
777               ((DOMText*)fStartContainer)->splitText(fStartOffset);
778       }
779
780        //update the new start information later. After inserting the first newNode
781        if (fStartOffset == 0)
782            next = fStartContainer;
783        else
784            next = fStartContainer->getNextSibling();
785
786    } // end of text handling
787    else {
788        parent = fStartContainer;
789
790        next = fStartContainer->getFirstChild();
791        for(XMLSize_t i = 0; (i < fStartOffset) && (next != 0); i++) {
792            next=next->getNextSibling();
793        }
794    }
795
796    if (parent != 0) {
797        if (next != 0)
798            parent->insertBefore(newNode, next);
799        else
800            parent->appendChild(newNode);
801    }
802}
803
804DOMRange* DOMRangeImpl::cloneRange() const
805{
806    if( fDetached) {
807        throw DOMException(
808            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
809    }
810
811    DOMRange* range = fDocument->createRange();
812    range->setStart(fStartContainer, fStartOffset);
813    range->setEnd(fEndContainer, fEndOffset);
814
815    return range;
816}
817
818const XMLCh* DOMRangeImpl::toString() const
819{
820    if( fDetached) {
821        throw DOMException(
822            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
823    }
824
825    if ((fStartContainer == fEndContainer) && (fEndOffset == fStartOffset))
826        return XMLUni::fgZeroLenString;
827
828    DOMNode* node = fStartContainer;
829    DOMNode* stopNode = fEndContainer;
830
831    XMLBuffer retStringBuf(1023, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
832    short type = fStartContainer->getNodeType();
833    if((type == DOMNode::TEXT_NODE
834        || type == DOMNode::CDATA_SECTION_NODE
835        || type == DOMNode::COMMENT_NODE
836        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
837        if (fStartContainer == fEndContainer) {
838            XMLCh* tempString;
839            XMLCh temp[4000];
840            if ((fEndOffset-fStartOffset) >= 3999)
841                tempString = (XMLCh*) fMemoryManager->allocate
842                (
843                    (fEndOffset - fStartOffset + 1) * sizeof(XMLCh)
844                );//new XMLCh[fEndOffset-fStartOffset+1];
845            else
846                tempString = temp;
847
848            XMLString::subString(tempString, fStartContainer->getNodeValue(), fStartOffset, fEndOffset, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
849            const XMLCh* retString = ((DOMDocumentImpl *)fDocument)->getPooledString(tempString);
850
851            if ((fEndOffset-fStartOffset) >= 3999)
852                fMemoryManager->deallocate(tempString);//delete[] tempString;
853
854            return retString;
855        } else {
856            XMLSize_t length = XMLString::stringLen(fStartContainer->getNodeValue());
857            if (length != fStartOffset) {
858
859                XMLCh* tempString;
860                XMLCh temp[4000];
861                if ((length - fStartOffset) >= 3999)
862                    tempString = (XMLCh*) fMemoryManager->allocate
863                    (
864                        (length - fStartOffset + 1) * sizeof(XMLCh)
865                    );//new XMLCh[length - fStartOffset+1];
866                else
867                    tempString = temp;
868
869                XMLString::subString(tempString, fStartContainer->getNodeValue(), fStartOffset, length, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
870                retStringBuf.append(tempString);
871
872                if ((length - fStartOffset) >= 3999)
873                    fMemoryManager->deallocate(tempString);//delete[] tempString;
874            }
875
876            node = nextNode(node, true);
877        }
878    }else { //fStartContainer is not a TextNode
879        node=node->getFirstChild();
880        if (fStartOffset>0) { //find a first node within a range, specified by fStartOffset
881            XMLSize_t counter = 0;
882            while (counter<fStartOffset && node!=0) {
883                node=node->getNextSibling();
884                counter++;
885            }
886        }
887        if (node == 0) {
888            node = nextNode(fStartContainer,false);
889        }
890    }
891
892    type = fEndContainer->getNodeType();
893    if((type != DOMNode::TEXT_NODE
894        && type != DOMNode::CDATA_SECTION_NODE
895        && type != DOMNode::COMMENT_NODE
896        && type != DOMNode::PROCESSING_INSTRUCTION_NODE)) {
897        int i=(int)fEndOffset;
898        stopNode = fEndContainer->getFirstChild();
899        while( i>0 && stopNode!=0 ){
900            --i;
901            stopNode = stopNode->getNextSibling();
902        }
903        if ( stopNode == 0 )
904            stopNode = nextNode( fEndContainer, false );
905    }
906
907    while (node != stopNode) {  //look into all kids of the Range
908        if (node == 0) break;
909        type = node->getNodeType();
910
911        if((type == DOMNode::TEXT_NODE
912            || type == DOMNode::CDATA_SECTION_NODE
913            || type == DOMNode::COMMENT_NODE
914            || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
915            retStringBuf.append(node->getNodeValue());
916        }
917        node = nextNode(node, true);
918    }
919
920    type = fEndContainer->getNodeType();
921    if((type == DOMNode::TEXT_NODE
922        || type == DOMNode::CDATA_SECTION_NODE
923        || type == DOMNode::COMMENT_NODE
924        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
925
926        if (fEndOffset != 0) {
927
928            XMLCh* tempString;
929            XMLCh temp[4000];
930            if (fEndOffset >= 3999)
931                tempString = (XMLCh*) fMemoryManager->allocate
932                (
933                    (fEndOffset+1) * sizeof(XMLCh)
934                );//new XMLCh[fEndOffset+1];
935            else
936                tempString = temp;
937
938            XMLString::subString(tempString, fEndContainer->getNodeValue(), 0, fEndOffset, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
939            retStringBuf.append(tempString);
940
941            if (fEndOffset >= 3999)
942                fMemoryManager->deallocate(tempString);//delete[] tempString;
943        }
944    }
945    return ((DOMDocumentImpl *)fDocument)->getPooledString(retStringBuf.getRawBuffer());
946}
947
948DOMDocument* DOMRangeImpl::getDocument()
949{
950    return fDocument;
951}
952
953const DOMNode* DOMRangeImpl::getCommonAncestorContainer() const
954{
955     return commonAncestorOf(fStartContainer, fEndContainer);
956
957}
958
959void DOMRangeImpl::release()
960{
961    detach();
962    // for performance reason, do not recycle pointer
963    // chance that this is allocated again and again is not usual
964}
965
966//---------------------
967//private functions
968//---------------------
969
970bool DOMRangeImpl::isValidAncestorType(const DOMNode* node) const
971{
972    for (DOMNode* aNode = (DOMNode*) node; aNode!=0; aNode = aNode->getParentNode()) {
973        short type = aNode->getNodeType();
974        if ( type == DOMNode::ENTITY_NODE
975            || type == DOMNode::NOTATION_NODE
976            || type == DOMNode::DOCUMENT_TYPE_NODE)
977            return false;
978    }
979    return true;
980}
981
982bool DOMRangeImpl::isAncestorOf(const DOMNode* a, const DOMNode* b) {
983    for (DOMNode* node = (DOMNode*) b; node != 0; node=node->getParentNode()) {
984        if  (node == a) return true;
985    }
986    return false;
987}
988
989bool DOMRangeImpl::hasLegalRootContainer(const DOMNode* node) const {
990    if ( node==0 )
991        return false;
992
993    DOMNode* rootContainer = (DOMNode*)node;
994    for (; rootContainer->getParentNode()!=0; rootContainer = rootContainer->getParentNode())
995        ;
996
997    switch( rootContainer->getNodeType() ) {
998        case DOMNode::ATTRIBUTE_NODE:
999        case DOMNode::DOCUMENT_NODE:
1000        case DOMNode::DOCUMENT_FRAGMENT_NODE:
1001            return true;
1002        default:
1003            return false;
1004    }
1005}
1006
1007bool DOMRangeImpl::isLegalContainedNode(const DOMNode* node ) const {
1008   if ( node==0 )
1009       return false;
1010   switch( node->getNodeType() )
1011   {
1012       case DOMNode::DOCUMENT_NODE:
1013       case DOMNode::DOCUMENT_FRAGMENT_NODE:
1014       case DOMNode::ATTRIBUTE_NODE:
1015       case DOMNode::ENTITY_NODE:
1016       case DOMNode::NOTATION_NODE:
1017            return false;
1018       default:
1019            return true;
1020   }   
1021}
1022
1023XMLSize_t DOMRangeImpl::indexOf(const DOMNode* child, const DOMNode* parent) const
1024{
1025    XMLSize_t i = 0;
1026    if (child->getParentNode() != parent) return (XMLSize_t)-1;
1027    for(DOMNode* node = child->getPreviousSibling(); node!= 0; node=node->getPreviousSibling()) {
1028        i++;
1029    }
1030    return i;
1031}
1032
1033void DOMRangeImpl::validateNode(const DOMNode* node) const
1034{
1035    if( fDetached) {
1036        throw DOMException(
1037            DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
1038    }
1039
1040    if ( !isValidAncestorType(node)) {
1041        throw DOMRangeException(DOMRangeException::INVALID_NODE_TYPE_ERR, 0, fMemoryManager);
1042    }
1043}
1044
1045
1046const DOMNode* DOMRangeImpl::commonAncestorOf(const DOMNode* pointA, const DOMNode* pointB) const
1047{
1048    if (fDetached)
1049        throw DOMException(DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
1050
1051    //if the containers are same then it itself is its common ancestor.
1052    if (pointA == pointB)
1053        return pointA;
1054
1055    typedef RefVectorOf<DOMNode> VectorNodes;
1056    VectorNodes startV(1, false, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
1057    DOMNode* node;
1058
1059    for (node=(DOMNode*)pointA; node != 0; node=node->getParentNode())
1060    {
1061        startV.addElement(node);
1062    }
1063    VectorNodes endV(1, false, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
1064    for (node=(DOMNode*)pointB; node != 0; node=node->getParentNode())
1065    {
1066        endV.addElement(node);
1067    }
1068
1069    XMLSize_t s = startV.size();
1070    XMLSize_t e = endV.size();
1071
1072    DOMNode* commonAncestor = 0;
1073
1074    while (s>0 && e>0) {
1075        if (startV.elementAt(s-1) == endV.elementAt(e-1)) {
1076            commonAncestor = startV.elementAt(s-1);
1077        }
1078        else  break;
1079        --s;
1080        --e;
1081    }
1082
1083    return commonAncestor;
1084}
1085
1086void DOMRangeImpl::checkIndex(const DOMNode* node, XMLSize_t offset) const
1087{
1088    short type = node->getNodeType();
1089
1090    if((type == DOMNode::TEXT_NODE
1091        || type == DOMNode::CDATA_SECTION_NODE
1092        || type == DOMNode::COMMENT_NODE
1093        || type == DOMNode::PROCESSING_INSTRUCTION_NODE)) {
1094        if (offset > XMLString::stringLen(node->getNodeValue()))
1095            throw DOMException( DOMException::INDEX_SIZE_ERR, 0, fMemoryManager );
1096        else  return;
1097    }
1098
1099    DOMNode* child = node->getFirstChild();
1100    XMLSize_t i = 0;
1101    for (; child != 0; i++) {
1102        child = child->getNextSibling();
1103    }
1104    if (i < offset) {
1105        throw DOMException( DOMException::INDEX_SIZE_ERR, 0, fMemoryManager );
1106    }
1107
1108}
1109
1110DOMNode* DOMRangeImpl::nextNode(const DOMNode* node, bool visitChildren) const
1111{
1112
1113    if (node == 0) return 0;
1114
1115    DOMNode* result;
1116    if (visitChildren) {
1117        result = node->getFirstChild();
1118        if (result != 0) {
1119            return result;
1120        }
1121    }
1122
1123    // if hasSibling, return sibling
1124    result = node->getNextSibling();
1125    if (result != 0) {
1126        return result;
1127    }
1128
1129
1130    // return parent's 1st sibling.
1131    DOMNode* parent = node->getParentNode();
1132
1133
1134    while ( (parent != 0) && (parent != fDocument) )
1135    {
1136        result = parent->getNextSibling();
1137        if (result != 0) {
1138            return result;
1139        } else {
1140            parent = parent->getParentNode();
1141        }
1142
1143    }
1144    // end of list, return 0
1145    return 0;
1146}
1147
1148
1149/** This is the master routine invoked to visit the nodes
1150*   selected by this range.  For each such node, different
1151*   actions are taken depending on the value of the TraversalType argument.
1152*/
1153DOMDocumentFragment* DOMRangeImpl::traverseContents(TraversalType how)
1154{
1155    if (fDetached)
1156            throw DOMException(DOMException::INVALID_STATE_ERR, 0, fMemoryManager);
1157
1158    if (fStartContainer == 0 || fEndContainer == 0) {
1159        return 0; // REVIST: Throw exception?
1160    }
1161
1162    /* Traversal is accomplished by first determining the
1163       relationship between the endpoints of the range.
1164       For each of four significant relationships, we will
1165       delegate the traversal call to a method that
1166       can make appropriate assumptions.
1167    */
1168
1169    // case 1: same container
1170    if ( fStartContainer == fEndContainer )
1171        return traverseSameContainer( how );
1172
1173    // case 2: Child C of start container is ancestor of end container
1174    // This can be quickly tested by walking the parent chain of
1175    // end container
1176    int endContainerDepth = 0;
1177    for ( DOMNode* c = fEndContainer, *p = c->getParentNode();
1178             p != 0;
1179             c = p, p = p->getParentNode())
1180        {
1181            if (p == fStartContainer)
1182                return traverseCommonStartContainer( c, how );
1183            ++endContainerDepth;
1184        }
1185
1186    // case 3: Child C of end container  is ancestor of start container
1187    // This can be quickly tested by walking the parent chain of A
1188    int startContainerDepth = 0;
1189    for ( DOMNode* c2 = fStartContainer, *p2 = c2->getParentNode();
1190         p2 != 0;
1191         c2 = p2, p2 = p2->getParentNode())
1192    {
1193        if (p2 == fEndContainer)
1194            return traverseCommonEndContainer( c2, how );
1195        ++startContainerDepth;
1196    }
1197
1198    // case 4: There is a common ancestor container.  Find the
1199    // ancestor siblings that are children of that container.
1200    int depthDiff = startContainerDepth - endContainerDepth;
1201
1202    DOMNode* startNode = fStartContainer;
1203    while (depthDiff > 0) {
1204        startNode = startNode->getParentNode();
1205        depthDiff--;
1206    }
1207
1208    DOMNode* endNode = fEndContainer;
1209    while (depthDiff < 0) {
1210        endNode = endNode->getParentNode();
1211        depthDiff++;
1212    }
1213
1214    // ascend the ancestor hierarchy until we have a common parent.
1215    for( DOMNode* sp = startNode->getParentNode(), *ep = endNode->getParentNode();
1216         sp!=ep;
1217         sp = sp->getParentNode(), ep = ep->getParentNode() )
1218    {
1219        startNode = sp;
1220        endNode = ep;
1221    }
1222    return traverseCommonAncestors( startNode, endNode, how );
1223    }
1224
1225/**
1226 * Visits the nodes selected by this range when we know
1227 * a-priori that the start and end containers are the same.
1228 *
1229 */
1230DOMDocumentFragment* DOMRangeImpl::traverseSameContainer( int how )
1231{
1232    DOMDocumentFragment* frag = 0;
1233    if ( how!=DELETE_CONTENTS)
1234        frag = fDocument->createDocumentFragment();
1235
1236    // If selection is empty, just return the fragment
1237    if ( fStartOffset==fEndOffset )
1238            return frag;
1239
1240    DOMNode* cloneCurrent = 0;
1241
1242    // Text node needs special case handling
1243    short type = fStartContainer->getNodeType();
1244    if((type == DOMNode::TEXT_NODE
1245        || type == DOMNode::CDATA_SECTION_NODE
1246        || type == DOMNode::COMMENT_NODE
1247        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1248    {
1249        cloneCurrent = fStartContainer->cloneNode(false);
1250        if (fEndOffset == fStartOffset) {
1251            cloneCurrent->setNodeValue(XMLUni::fgZeroLenString);
1252        }
1253        else {
1254            XMLCh* tempString;
1255            XMLCh temp[4000];
1256            if (fEndOffset >= 3999)
1257                tempString = (XMLCh*) fMemoryManager->allocate
1258                (
1259                    (fEndOffset+1) * sizeof(XMLCh)
1260                );//new XMLCh[fEndOffset+1];
1261            else
1262                tempString = temp;
1263
1264            XMLString::subString(tempString, cloneCurrent->getNodeValue(), fStartOffset, fEndOffset, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
1265            cloneCurrent->setNodeValue(((DOMDocumentImpl *)fDocument)->getPooledString(tempString));
1266
1267            if (fEndOffset >= 3999)
1268                fMemoryManager->deallocate(tempString);//delete[] tempString;
1269        }
1270
1271        // set the original text node to its new value
1272        if ( how != CLONE_CONTENTS ) {
1273            if(type == DOMNode::PROCESSING_INSTRUCTION_NODE) {
1274                ((DOMProcessingInstructionImpl*)fStartContainer)->deleteData(fStartOffset, fEndOffset-fStartOffset);
1275            }
1276            else
1277                ((DOMCharacterData*)fStartContainer)->deleteData(fStartOffset, fEndOffset-fStartOffset);
1278        }
1279        if ( how != DELETE_CONTENTS)
1280            frag->appendChild(cloneCurrent);
1281    }
1282    else {
1283        // Copy nodes between the start/end offsets.
1284        DOMNode* n = getSelectedNode( fStartContainer, (int)fStartOffset );
1285        int cnt = (int)fEndOffset - (int)fStartOffset;
1286        while( cnt > 0 && n)
1287        {
1288            DOMNode* sibling = n->getNextSibling();
1289            DOMNode* xferNode = traverseFullySelected( n, how );
1290            if ( frag!=0 )
1291                frag->appendChild( xferNode );
1292            --cnt;
1293            n = sibling;
1294        }
1295    }
1296
1297    // Nothing is partially selected, so collapse to start point
1298    if ( how != CLONE_CONTENTS )
1299            collapse(true);
1300    return frag;
1301}
1302
1303/**
1304 * Visits the nodes selected by this range when we know
1305 * a-priori that the start and end containers are not the
1306 * same, but the start container is an ancestor of the end container
1307 *
1308 */
1309DOMDocumentFragment* DOMRangeImpl::traverseCommonStartContainer( DOMNode*endAncestor, int how )
1310{
1311    DOMDocumentFragment* frag = 0;
1312    if ( how!=DELETE_CONTENTS)
1313        frag = fDocument->createDocumentFragment();
1314    DOMNode*n = traverseRightBoundary( endAncestor, how );
1315    if ( frag!=0 )
1316        frag->appendChild( n );
1317
1318    XMLSize_t endIdx = indexOf( endAncestor, fStartContainer );
1319    if ( endIdx <= fStartOffset )
1320    {
1321        // Collapse to just before the endAncestor, which
1322        // is partially selected.
1323        if ( how != CLONE_CONTENTS )
1324        {
1325            setEndBefore( endAncestor );
1326            collapse( false );
1327        }
1328        return frag;
1329    }
1330
1331    n = endAncestor->getPreviousSibling();
1332    int cnt = (int)endIdx - (int)fStartOffset;
1333    while( cnt > 0 )
1334    {
1335        DOMNode* sibling = n->getPreviousSibling();
1336        DOMNode* xferNode = traverseFullySelected( n, how );
1337        if ( frag!=0 )
1338            frag->insertBefore( xferNode, frag->getFirstChild() );
1339        --cnt;
1340        n = sibling;
1341    }
1342    // Collapse to just before the endAncestor, which
1343    // is partially selected.
1344    if ( how != CLONE_CONTENTS )
1345    {
1346        setEndBefore( endAncestor );
1347        collapse( false );
1348    }
1349    return frag;
1350}
1351
1352/**
1353 * Visits the nodes selected by this range when we know
1354 * a-priori that the start and end containers are not the
1355 * same, but the end container is an ancestor of the start container
1356 *
1357 */
1358DOMDocumentFragment* DOMRangeImpl::traverseCommonEndContainer( DOMNode*startAncestor, int how )
1359{
1360    DOMDocumentFragment* frag = 0;
1361    if ( how!=DELETE_CONTENTS)
1362        frag = fDocument->createDocumentFragment();
1363    DOMNode* n = traverseLeftBoundary( startAncestor, how );
1364    if ( frag!=0 )
1365        frag->appendChild( n );
1366    XMLSize_t startIdx = indexOf( startAncestor, fEndContainer );
1367    ++startIdx;  // Because we already traversed it....
1368
1369    int cnt = (int)fEndOffset - (int)startIdx;
1370    n = startAncestor->getNextSibling();
1371    while( cnt > 0 )
1372    {
1373        DOMNode* sibling = n->getNextSibling();
1374        DOMNode* xferNode = traverseFullySelected( n, how );
1375        if ( frag!=0 )
1376            frag->appendChild( xferNode );
1377        --cnt;
1378        n = sibling;
1379    }
1380
1381    if ( how != CLONE_CONTENTS )
1382    {
1383        setStartAfter( startAncestor );
1384        collapse( true );
1385    }
1386
1387    return frag;
1388}
1389
1390/**
1391 * Visits the nodes selected by this range when we know
1392 * a-priori that the start and end containers are not
1393 * the same, and we also know that neither the start
1394 * nor end container is an ancestor of the other.
1395 */
1396DOMDocumentFragment* DOMRangeImpl::traverseCommonAncestors( DOMNode*startAncestor, DOMNode*endAncestor, int how )
1397{
1398    DOMDocumentFragment* frag = 0;
1399    if ( how!=DELETE_CONTENTS)
1400        frag = fDocument->createDocumentFragment();
1401
1402    DOMNode*n = traverseLeftBoundary( startAncestor, how );
1403    if ( frag!=0 )
1404        frag->appendChild( n );
1405
1406    DOMNode*commonParent = startAncestor->getParentNode();
1407    XMLSize_t startOffset = indexOf( startAncestor, commonParent );
1408    XMLSize_t endOffset = indexOf( endAncestor, commonParent );
1409    ++startOffset;
1410
1411    int cnt = (int)endOffset - (int)startOffset;
1412    DOMNode* sibling = startAncestor->getNextSibling();
1413
1414    while( cnt > 0 )
1415    {
1416        DOMNode* nextSibling = sibling->getNextSibling();
1417        n = traverseFullySelected( sibling, how );
1418        if ( frag!=0 )
1419            frag->appendChild( n );
1420        sibling = nextSibling;
1421        --cnt;
1422    }
1423
1424    n = traverseRightBoundary( endAncestor, how );
1425    if ( frag!=0 )
1426        frag->appendChild( n );
1427
1428    if ( how != CLONE_CONTENTS )
1429    {
1430        setStartAfter( startAncestor );
1431        collapse( true );
1432    }
1433    return frag;
1434}
1435
1436/**
1437 * Traverses the "right boundary" of this range and
1438 * operates on each "boundary node" according to the
1439 * how parameter.  It is a-priori assumed
1440 * by this method that the right boundary does
1441 * not contain the range's start container.
1442 *
1443 * A "right boundary" is best visualized by thinking
1444 * of a sample tree:
1445 *                 A
1446 *                /|\
1447 *               / | \
1448 *              /  |  \
1449 *             B   C   D
1450 *            /|\     /|\
1451 *           E F G   H I J
1452 *
1453 * Imagine first a range that begins between the
1454 * "E" and "F" nodes and ends between the
1455 * "I" and "J" nodes.  The start container is
1456 * "B" and the end container is "D".  Given this setup,
1457 * the following applies:
1458 *
1459 * Partially Selected Nodes: B, D<br>
1460 * Fully Selected Nodes: F, G, C, H, I
1461 *
1462 * The "right boundary" is the highest subtree node
1463 * that contains the ending container.  The root of
1464 * this subtree is always partially selected.
1465 *
1466 * In this example, the nodes that are traversed
1467 * as "right boundary" nodes are: H, I, and D.
1468 *
1469 */
1470DOMNode* DOMRangeImpl::traverseRightBoundary( DOMNode*root, int how )
1471{
1472    DOMNode*next = getSelectedNode( fEndContainer, (int)fEndOffset-1 );
1473    bool isFullySelected = ( next!=fEndContainer );
1474
1475    if ( next==root )
1476        return traverseNode( next, isFullySelected, false, how );
1477
1478    DOMNode*parent = next->getParentNode();
1479    DOMNode*clonedParent = traverseNode( parent, false, false, how );
1480
1481    while( parent!=0 )
1482    {
1483        while( next!=0 )
1484        {
1485            DOMNode* prevSibling = next->getPreviousSibling();
1486            DOMNode* clonedChild =
1487                traverseNode( next, isFullySelected, false, how );
1488            if ( how!=DELETE_CONTENTS )
1489            {
1490                clonedParent->insertBefore(
1491                    clonedChild,
1492                    clonedParent->getFirstChild()
1493                );
1494            }
1495            isFullySelected = true;
1496            next = prevSibling;
1497        }
1498        if ( parent==root )
1499            return clonedParent;
1500
1501        next = parent->getPreviousSibling();
1502        parent = parent->getParentNode();
1503        DOMNode* clonedGrandParent = traverseNode( parent, false, false, how );
1504        if ( how!=DELETE_CONTENTS )
1505            clonedGrandParent->appendChild( clonedParent );
1506        clonedParent = clonedGrandParent;
1507
1508    }
1509
1510    // should never occur
1511    return 0;
1512}
1513
1514/**
1515 * Traverses the "left boundary" of this range and
1516 * operates on each "boundary node" according to the
1517 * how parameter.  It is a-priori assumed
1518 * by this method that the left boundary does
1519 * not contain the range's end container.
1520 *
1521 * A "left boundary" is best visualized by thinking
1522 * of a sample tree:
1523 *
1524 *                 A
1525 *                /|\
1526 *               / | \
1527 *              /  |  \
1528 *             B   C   D
1529 *            /|\     /|\
1530 *           E F G   H I J
1531 *
1532 * Imagine first a range that begins between the
1533 * "E" and "F" nodes and ends between the
1534 * "I" and "J" nodes.  The start container is
1535 * "B" and the end container is "D".  Given this setup,
1536 * the following applies:
1537 *
1538 * Partially Selected Nodes: B, D<br>
1539 * Fully Selected Nodes: F, G, C, H, I
1540 *
1541 * The "left boundary" is the highest subtree node
1542 * that contains the starting container.  The root of
1543 * this subtree is always partially selected.
1544 *
1545 * In this example, the nodes that are traversed
1546 * as "left boundary" nodes are: F, G, and B.
1547 *
1548 */
1549DOMNode* DOMRangeImpl::traverseLeftBoundary( DOMNode*root, int how )
1550{
1551    DOMNode*next = getSelectedNode( getStartContainer(), (int)getStartOffset() );
1552    bool isFullySelected = ( next!=getStartContainer() );
1553
1554    if ( next==root )
1555        return traverseNode( next, isFullySelected, true, how );
1556
1557    DOMNode* parent = next->getParentNode();
1558    DOMNode* clonedParent = traverseNode( parent, false, true, how );
1559
1560    while( parent!=0 )
1561    {
1562        while( next!=0 )
1563        {
1564            DOMNode* nextSibling = next->getNextSibling();
1565            DOMNode* clonedChild =
1566                traverseNode( next, isFullySelected, true, how );
1567            if ( how!=DELETE_CONTENTS )
1568                clonedParent->appendChild(clonedChild);
1569            isFullySelected = true;
1570            next = nextSibling;
1571        }
1572        if ( parent==root )
1573            return clonedParent;
1574
1575        next = parent->getNextSibling();
1576        parent = parent->getParentNode();
1577        DOMNode* clonedGrandParent = traverseNode( parent, false, true, how );
1578        if ( how!=DELETE_CONTENTS )
1579            clonedGrandParent->appendChild( clonedParent );
1580        clonedParent = clonedGrandParent;
1581
1582    }
1583
1584    // should never occur
1585    return 0;
1586
1587}
1588
1589/**
1590 * Utility method for traversing a single node.
1591 * Does not properly handle a text node containing both the
1592 * start and end offsets.  Such nodes should
1593 * have been previously detected and been routed to traverseTextNode.
1594 *
1595 */
1596DOMNode* DOMRangeImpl::traverseNode( DOMNode* n, bool isFullySelected, bool isLeft, int how )
1597{
1598    if ( isFullySelected )
1599        return traverseFullySelected( n, how );
1600
1601    short type = n->getNodeType();
1602
1603    if((type == DOMNode::TEXT_NODE
1604        || type == DOMNode::CDATA_SECTION_NODE
1605        || type == DOMNode::COMMENT_NODE
1606        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1607        return traverseTextNode( n, isLeft, how );
1608
1609    return traversePartiallySelected( n, how );
1610}
1611
1612/**
1613 * Utility method for traversing a single node when
1614 * we know a-priori that the node if fully
1615 * selected.
1616 *
1617 */
1618DOMNode* DOMRangeImpl::traverseFullySelected( DOMNode* n, int how )
1619{
1620    switch( how )
1621    {
1622    case CLONE_CONTENTS:
1623        return n->cloneNode( true );
1624    case EXTRACT_CONTENTS:
1625        return n;
1626    case DELETE_CONTENTS:
1627        // revisit:
1628        //   should I release the removed node?
1629        //   not released in case user still referencing it externally
1630        n->getParentNode()->removeChild(n);
1631        return 0;
1632    }
1633    return 0;
1634}
1635
1636/**
1637 * Utility method for traversing a single node when
1638 * we know a-priori that the node if partially
1639 * selected and is not a text node.
1640 *
1641 */
1642DOMNode* DOMRangeImpl::traversePartiallySelected( DOMNode*n, int how )
1643{
1644    switch( how )
1645    {
1646    case DELETE_CONTENTS:
1647        return 0;
1648    case CLONE_CONTENTS:
1649    case EXTRACT_CONTENTS:
1650        return n->cloneNode( false );
1651    }
1652    return 0;
1653}
1654
1655/**
1656 * Utility method for traversing a text node that we know
1657 * a-priori to be on a left or right boundary of the range.
1658 * This method does not properly handle text nodes that contain
1659 * both the start and end points of the range.
1660 *
1661 */
1662DOMNode* DOMRangeImpl::traverseTextNode( DOMNode*n, bool isLeft, int how )
1663{
1664    XMLCh* txtValue = XMLString::replicate(n->getNodeValue(), fMemoryManager);
1665    ArrayJanitor<XMLCh> janValue(txtValue, fMemoryManager);
1666
1667    if ( isLeft )
1668    {
1669        XMLSize_t startLen = XMLString::stringLen(fStartContainer->getNodeValue());
1670        XMLSize_t offset = getStartOffset();
1671
1672        if (offset == 0) {
1673            if ( how != CLONE_CONTENTS )
1674                n->setNodeValue(XMLUni::fgZeroLenString);
1675        }
1676        else {
1677            XMLCh* oldNodeValue;
1678            XMLCh oldTemp[4000];
1679
1680            if (offset >= 3999)  {
1681                oldNodeValue = (XMLCh*) fMemoryManager->allocate
1682                (
1683                    (offset+1) * sizeof(XMLCh)
1684                );//new XMLCh[offset+1];
1685            }
1686            else {
1687                oldNodeValue = oldTemp;
1688            }
1689            XMLString::subString(oldNodeValue, txtValue, 0, offset, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
1690
1691            if ( how != CLONE_CONTENTS )
1692                n->setNodeValue( ((DOMDocumentImpl *)fDocument)->getPooledString(oldNodeValue) );
1693
1694            if (offset>= 3999)
1695                fMemoryManager->deallocate(oldNodeValue);//delete[] oldNodeValue;
1696        }
1697
1698        if ( how==DELETE_CONTENTS )
1699            return 0;
1700
1701        DOMNode* newNode = n->cloneNode( false );
1702
1703        if (startLen == offset) {
1704            newNode->setNodeValue(XMLUni::fgZeroLenString);
1705        }
1706        else {
1707            XMLCh* newNodeValue;
1708            XMLCh newTemp[4000];
1709
1710            if (offset >= 3999)  {
1711                newNodeValue = (XMLCh*) fMemoryManager->allocate
1712                (
1713                    (offset+1) * sizeof(XMLCh)
1714                );//new XMLCh[offset+1];
1715            }
1716            else {
1717                newNodeValue = newTemp;
1718            }
1719            XMLString::subString(newNodeValue, txtValue, offset, startLen, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
1720            newNode->setNodeValue( ((DOMDocumentImpl *)fDocument)->getPooledString(newNodeValue) );
1721
1722            if (offset>= 3999)
1723                fMemoryManager->deallocate(newNodeValue);//delete[] newNodeValue;
1724
1725        }
1726        return newNode;
1727    }
1728    else
1729    {
1730        XMLSize_t endLen = XMLString::stringLen(fEndContainer->getNodeValue());
1731        XMLSize_t offset = getEndOffset();
1732
1733        if (endLen == offset) {
1734            if ( how != CLONE_CONTENTS )
1735                n->setNodeValue(XMLUni::fgZeroLenString);
1736        }
1737        else {
1738            XMLCh* oldNodeValue;
1739            XMLCh oldTemp[4000];
1740
1741            if (offset >= 3999)  {
1742                oldNodeValue = (XMLCh*) fMemoryManager->allocate
1743                (
1744                    (offset+1) * sizeof(XMLCh)
1745                );//new XMLCh[offset+1];
1746            }
1747            else {
1748                oldNodeValue = oldTemp;
1749            }
1750            XMLString::subString(oldNodeValue, txtValue, offset, endLen, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
1751
1752            if ( how != CLONE_CONTENTS )
1753                n->setNodeValue( ((DOMDocumentImpl *)fDocument)->getPooledString(oldNodeValue) );
1754
1755            if (offset>= 3999)
1756                fMemoryManager->deallocate(oldNodeValue);//delete[] oldNodeValue;
1757        }
1758
1759        if ( how==DELETE_CONTENTS )
1760            return 0;
1761
1762        DOMNode* newNode = n->cloneNode( false );
1763
1764        if (offset == 0) {
1765            newNode->setNodeValue(XMLUni::fgZeroLenString);
1766        }
1767        else {
1768            XMLCh* newNodeValue;
1769            XMLCh newTemp[4000];
1770
1771            if (offset >= 3999)  {
1772                newNodeValue = (XMLCh*) fMemoryManager->allocate
1773                (
1774                    (offset+1) * sizeof(XMLCh)
1775                );//new XMLCh[offset+1];
1776            }
1777            else {
1778                newNodeValue = newTemp;
1779            }
1780            XMLString::subString(newNodeValue, txtValue, 0, offset, ((DOMDocumentImpl *)fDocument)->getMemoryManager());
1781            newNode->setNodeValue( ((DOMDocumentImpl *)fDocument)->getPooledString(newNodeValue) );
1782
1783            if (offset>= 3999)
1784                fMemoryManager->deallocate(newNodeValue);//delete[] newNodeValue;
1785
1786        }
1787        return newNode;
1788    }
1789}
1790
1791/**
1792 * Utility method to retrieve a child node by index.  This method
1793 * assumes the caller is trying to find out which node is
1794 * selected by the given index.  Note that if the index is
1795 * greater than the number of children, this implies that the
1796 * first node selected is the parent node itself.
1797 *
1798 */
1799DOMNode* DOMRangeImpl::getSelectedNode( DOMNode*container, int offset )
1800{
1801    short type = container->getNodeType();
1802    if((type == DOMNode::TEXT_NODE
1803        || type == DOMNode::CDATA_SECTION_NODE
1804        || type == DOMNode::COMMENT_NODE
1805        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1806        return container;
1807
1808    // This case is an important convenience for
1809    // traverseRightBoundary()
1810    if ( offset<0 )
1811        return container;
1812
1813    DOMNode*child = container->getFirstChild();
1814    while( child!=0 && offset > 0 )
1815    {
1816        --offset;
1817        child = child->getNextSibling();
1818    }
1819    if ( child!=0 )
1820        return child;
1821    return container;
1822}
1823
1824void DOMRangeImpl::checkReadOnly(DOMNode* start, DOMNode* end,
1825                              XMLSize_t startOffset, XMLSize_t endOffset)
1826{
1827    if ((start == 0) || (end == 0) ) return;
1828    DOMNode*sNode = 0;
1829
1830    short type = start->getNodeType();
1831    if ( type == DOMNode::DOCUMENT_TYPE_NODE )
1832    {
1833        throw DOMException(
1834            DOMException::HIERARCHY_REQUEST_ERR, 0, fMemoryManager);
1835    }
1836
1837    if((type == DOMNode::TEXT_NODE
1838        || type == DOMNode::CDATA_SECTION_NODE
1839        || type == DOMNode::COMMENT_NODE
1840        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1841    {
1842        if (castToNodeImpl(start)->isReadOnly()) {
1843            throw DOMException(
1844                DOMException::NO_MODIFICATION_ALLOWED_ERR, 0, fMemoryManager);
1845        }
1846        //if both start and end are text check and return
1847        if (start == end)
1848            return;
1849
1850        sNode = start;
1851    } else {
1852        //set the start and end nodes to check
1853        sNode = start->getFirstChild();
1854        for(XMLSize_t i = 0; i<startOffset; i++)
1855            sNode = sNode->getNextSibling();
1856    }
1857
1858    DOMNode* eNode;
1859    type = end->getNodeType();
1860    if ( type == DOMNode::DOCUMENT_TYPE_NODE )
1861    {
1862        throw DOMException(
1863            DOMException::HIERARCHY_REQUEST_ERR, 0, fMemoryManager);
1864    }
1865
1866    if((type == DOMNode::TEXT_NODE
1867        || type == DOMNode::CDATA_SECTION_NODE
1868        || type == DOMNode::COMMENT_NODE
1869        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1870    {
1871        eNode = end; //need to check only till this node
1872    }
1873    else { //need to check all the kids that fall before the end offset value
1874        eNode = end->getFirstChild();
1875        if (endOffset > 0)  {
1876            for (XMLSize_t i = 0; i<endOffset-1; i++)
1877                eNode = eNode->getNextSibling();
1878        }
1879    }
1880    //recursivly search if any node is readonly
1881    recurseTreeAndCheck(sNode, eNode);
1882}
1883
1884void DOMRangeImpl::recurseTreeAndCheck(DOMNode* start, DOMNode* end)
1885{
1886    for(DOMNode* node=start; node != 0 && node !=end; node=node->getNextSibling())
1887    {
1888        if ( node->getNodeType()== DOMNode::DOCUMENT_TYPE_NODE )
1889        {
1890            throw DOMException(
1891                DOMException::HIERARCHY_REQUEST_ERR, 0, fMemoryManager);
1892        }
1893
1894        if (castToNodeImpl(node)->isReadOnly()) {
1895            throw DOMException(
1896                DOMException::NO_MODIFICATION_ALLOWED_ERR, 0, fMemoryManager);
1897        }
1898
1899        if (node->hasChildNodes()) {
1900            node = node->getFirstChild();
1901            recurseTreeAndCheck(node, end);
1902        }
1903    }
1904}
1905
1906
1907DOMNode* DOMRangeImpl::removeChild(DOMNode* parent, DOMNode* child)
1908{
1909    fRemoveChild = child; //only a precaution measure not to update this range data before removal
1910    DOMNode*n = parent->removeChild(child);
1911    fRemoveChild = 0;
1912    return n;
1913}
1914
1915
1916//
1917// Mutation functions
1918//
1919
1920
1921/* This function is called from DOM.
1922*  The  text has already been replaced.
1923*  Fix-up any offsets.
1924*/
1925void DOMRangeImpl::receiveReplacedText(DOMNode* node)
1926{
1927    if (node == 0) return;
1928
1929    short type = fStartContainer->getNodeType();
1930    if (node == fStartContainer
1931        && (type == DOMNode::TEXT_NODE
1932        || type == DOMNode::CDATA_SECTION_NODE
1933        || type == DOMNode::COMMENT_NODE
1934        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1935    {
1936        fStartOffset = 0;
1937    }
1938    type = fEndContainer->getNodeType();
1939    if (node == fEndContainer
1940        && (type == DOMNode::TEXT_NODE
1941        || type == DOMNode::CDATA_SECTION_NODE
1942        || type == DOMNode::COMMENT_NODE
1943        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1944    {
1945        fEndOffset = 0;
1946    }
1947}
1948
1949
1950/** This function is called from DOM.
1951*  The  text has already been deleted.
1952*  Fix-up any offsets.
1953*/
1954void DOMRangeImpl::updateRangeForDeletedText(DOMNode* node, XMLSize_t offset, XMLSize_t count)
1955{
1956    if (node == 0) return;
1957
1958    short type = fStartContainer->getNodeType();
1959    if (node == fStartContainer
1960        && (type == DOMNode::TEXT_NODE
1961        || type == DOMNode::CDATA_SECTION_NODE
1962        || type == DOMNode::COMMENT_NODE
1963        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1964    {
1965        if (fStartOffset > offset+count) {
1966            fStartOffset = fStartOffset-count;
1967        } else if (fStartOffset > offset) {
1968            fStartOffset = offset;
1969        }
1970    }
1971    type = fEndContainer->getNodeType();
1972    if (node == fEndContainer
1973        && (type == DOMNode::TEXT_NODE
1974        || type == DOMNode::CDATA_SECTION_NODE
1975        || type == DOMNode::COMMENT_NODE
1976        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
1977    {
1978        if (fEndOffset > offset+count) {
1979            fEndOffset = fEndOffset-count;
1980        } else if (fEndOffset > offset) {
1981            fEndOffset = offset;
1982        }
1983    }
1984}
1985
1986
1987
1988/** This function is called from DOM.
1989*  The  text has already beeen inserted.
1990*  Fix-up any offsets.
1991*/
1992void DOMRangeImpl::updateRangeForInsertedText(DOMNode* node, XMLSize_t offset, XMLSize_t count)
1993{
1994    if (node == 0) return;
1995
1996    short type = fStartContainer->getNodeType();
1997    if (node == fStartContainer
1998        && (type == DOMNode::TEXT_NODE
1999        || type == DOMNode::CDATA_SECTION_NODE
2000        || type == DOMNode::COMMENT_NODE
2001        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
2002    {
2003        if (fStartOffset > offset) {
2004            fStartOffset = offset;
2005        }
2006    }
2007    type = fEndContainer->getNodeType();
2008    if (node == fEndContainer
2009        && (type == DOMNode::TEXT_NODE
2010        || type == DOMNode::CDATA_SECTION_NODE
2011        || type == DOMNode::COMMENT_NODE
2012        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
2013    {
2014        if (fEndOffset > offset) {
2015            fEndOffset = fEndOffset+count;
2016        }
2017    }
2018}
2019
2020
2021
2022/** This function must be called by the DOM _BEFORE_
2023*  a node is deleted, because at that time it is
2024*  connected in the DOM tree, which we depend on.
2025*/
2026void DOMRangeImpl::updateRangeForDeletedNode(DOMNode* node)
2027{
2028
2029    if (node == 0) return;
2030    if (fRemoveChild == node) return;
2031
2032    if (node->getParentNode() == fStartContainer) {
2033        XMLSize_t index = indexOf(node, fStartContainer);
2034        if ( fStartOffset > index) {
2035            fStartOffset--;
2036        }
2037    }
2038
2039    if (node->getParentNode() == fEndContainer) {
2040        XMLSize_t index = indexOf(node, fEndContainer);
2041        if ( fEndOffset > index) {
2042            fEndOffset--;
2043        }
2044    }
2045
2046    if (node->getParentNode() != fStartContainer
2047        ||  node->getParentNode() != fEndContainer) {
2048        if (isAncestorOf(node, fStartContainer)) {
2049            DOMNode* tpNode = node->getParentNode();
2050            setStartContainer( tpNode );
2051            fStartOffset = indexOf( node, tpNode);
2052        }
2053        if (isAncestorOf(node, fEndContainer)) {
2054            DOMNode* tpNode = node->getParentNode();
2055            setEndContainer( tpNode );
2056            fEndOffset = indexOf( node, tpNode);
2057        }
2058    }
2059
2060}
2061
2062void DOMRangeImpl::updateRangeForInsertedNode(DOMNode* node) {
2063    if (node == 0) return;
2064
2065    if (node->getParentNode() == fStartContainer) {
2066        XMLSize_t index = indexOf(node, fStartContainer);
2067        if (index < fStartOffset) {
2068            fStartOffset++;
2069        }
2070    }
2071
2072    if (node->getParentNode() == fEndContainer) {
2073        XMLSize_t index = indexOf(node, fEndContainer);
2074        if (index < fEndOffset) {
2075            fEndOffset++;
2076        }
2077    }
2078}
2079
2080
2081void DOMRangeImpl::updateSplitInfo(DOMNode* oldNode, DOMNode* startNode, XMLSize_t offset)
2082{
2083    if (startNode == 0) return;
2084
2085    short type = fStartContainer->getNodeType();
2086    if (oldNode == fStartContainer
2087        && (type == DOMNode::TEXT_NODE
2088        || type == DOMNode::CDATA_SECTION_NODE
2089        || type == DOMNode::COMMENT_NODE
2090        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
2091    {
2092        if (fStartOffset > offset) {
2093            fStartOffset = fStartOffset - offset;
2094            fStartContainer = startNode;
2095        }
2096    }
2097
2098    type = fEndContainer->getNodeType();
2099    if (oldNode == fEndContainer
2100        && (type == DOMNode::TEXT_NODE
2101        || type == DOMNode::CDATA_SECTION_NODE
2102        || type == DOMNode::COMMENT_NODE
2103        || type == DOMNode::PROCESSING_INSTRUCTION_NODE))
2104    {
2105        if (fEndOffset > offset) {
2106            fEndContainer = startNode;
2107           fEndOffset = fEndOffset - offset;
2108        }
2109    }
2110}
2111
2112
2113
2114XERCES_CPP_NAMESPACE_END
2115
Note: See TracBrowser for help on using the repository browser.