← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/content/base/src/nsContentIterator.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
mozilla/content/base/src/nsContentIterator.cpp
 
1
/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
 
2
/* ***** BEGIN LICENSE BLOCK *****
 
3
 * Version: NPL 1.1/GPL 2.0/LGPL 2.1
 
4
 *
 
5
 * The contents of this file are subject to the Netscape Public License
 
6
 * Version 1.1 (the "License"); you may not use this file except in
 
7
 * compliance with the License. You may obtain a copy of the License at
 
8
 * http://www.mozilla.org/NPL/
 
9
 *
 
10
 * Software distributed under the License is distributed on an "AS IS" basis,
 
11
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 
12
 * for the specific language governing rights and limitations under the
 
13
 * License.
 
14
 *
 
15
 * The Original Code is mozilla.org code.
 
16
 *
 
17
 * The Initial Developer of the Original Code is 
 
18
 * Netscape Communications Corporation.
 
19
 * Portions created by the Initial Developer are Copyright (C) 1998
 
20
 * the Initial Developer. All Rights Reserved.
 
21
 *
 
22
 * Contributor(s):
 
23
 *   Pierre Phaneuf <pp@ludusdesign.com>
 
24
 *
 
25
 *
 
26
 * Alternatively, the contents of this file may be used under the terms of
 
27
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 
28
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 
29
 * in which case the provisions of the GPL or the LGPL are applicable instead
 
30
 * of those above. If you wish to allow use of your version of this file only
 
31
 * under the terms of either the GPL or the LGPL, and not to allow others to
 
32
 * use your version of this file under the terms of the NPL, indicate your
 
33
 * decision by deleting the provisions above and replace them with the notice
 
34
 * and other provisions required by the GPL or the LGPL. If you do not delete
 
35
 * the provisions above, a recipient may use your version of this file under
 
36
 * the terms of any one of the NPL, the GPL or the LGPL.
 
37
 *
 
38
 * ***** END LICENSE BLOCK ***** */
 
39
 
 
40
/*
 
41
 * nsContentIterator.cpp: Implementation of the nsContentIterator object.
 
42
 * This ite
 
43
 */
 
44
 
 
45
#include "nsISupports.h"
 
46
#include "nsIDOMNodeList.h"
 
47
#include "nsIContentIterator.h"
 
48
#include "nsRange.h"
 
49
#include "nsIContent.h"
 
50
#include "nsIDOMText.h"
 
51
#include "nsISupportsArray.h"
 
52
#include "nsIFocusTracker.h"
 
53
#include "nsCOMPtr.h"
 
54
#include "nsIPresContext.h"
 
55
#include "nsIComponentManager.h"
 
56
#include "nsContentCID.h"
 
57
#include "nsLayoutCID.h"
 
58
#include "nsVoidArray.h"
 
59
#include "nsContentUtils.h"
 
60
 
 
61
static NS_DEFINE_IID(kISupportsIID, NS_ISUPPORTS_IID);
 
62
 
 
63
// couple of utility static functs
 
64
 
 
65
///////////////////////////////////////////////////////////////////////////
 
66
// GetNumChildren: returns the number of things inside aNode. 
 
67
//
 
68
static PRUint32
 
69
GetNumChildren(nsIDOMNode *aNode) 
 
70
{
 
71
  if (!aNode)
 
72
    return 0;
 
73
 
 
74
  PRUint32 numChildren = 0;
 
75
  PRBool hasChildNodes;
 
76
  aNode->HasChildNodes(&hasChildNodes);
 
77
  if (hasChildNodes)
 
78
  {
 
79
    nsCOMPtr<nsIContent> content(do_QueryInterface(aNode));
 
80
 
 
81
    if (content)
 
82
      return content->GetChildCount();
 
83
 
 
84
    nsCOMPtr<nsIDOMNodeList>nodeList;
 
85
    aNode->GetChildNodes(getter_AddRefs(nodeList));
 
86
    if (nodeList) 
 
87
      nodeList->GetLength(&numChildren);
 
88
  }
 
89
 
 
90
  return numChildren;
 
91
}
 
92
 
 
93
///////////////////////////////////////////////////////////////////////////
 
94
// GetChildAt: returns the node at this position index in the parent
 
95
//
 
96
static nsCOMPtr<nsIDOMNode> 
 
97
GetChildAt(nsIDOMNode *aParent, PRInt32 aOffset)
 
98
{
 
99
  nsCOMPtr<nsIDOMNode> resultNode;
 
100
 
 
101
  if (!aParent) 
 
102
    return resultNode;
 
103
 
 
104
  nsCOMPtr<nsIContent> content(do_QueryInterface(aParent));
 
105
 
 
106
  if (content) {
 
107
    resultNode = do_QueryInterface(content->GetChildAt(aOffset));
 
108
  } else if (aParent) {
 
109
    PRBool hasChildNodes;
 
110
    aParent->HasChildNodes(&hasChildNodes);
 
111
    if (hasChildNodes)
 
112
    {
 
113
      nsCOMPtr<nsIDOMNodeList>nodeList;
 
114
      aParent->GetChildNodes(getter_AddRefs(nodeList));
 
115
      if (nodeList) 
 
116
        nodeList->Item(aOffset, getter_AddRefs(resultNode));
 
117
    }
 
118
  }
 
119
  
 
120
  return resultNode;
 
121
}
 
122
  
 
123
///////////////////////////////////////////////////////////////////////////
 
124
// ContentHasChildren: returns true if the content has children
 
125
//
 
126
static inline PRBool
 
127
ContentHasChildren(nsIContent *aContent)
 
128
{
 
129
  return aContent->GetChildCount() > 0;
 
130
}
 
131
 
 
132
///////////////////////////////////////////////////////////////////////////
 
133
// ContentToParentOffset: returns the content node's parent and offset.
 
134
//
 
135
 
 
136
static void
 
137
ContentToParentOffset(nsIContent *aContent, nsIDOMNode **aParent,
 
138
                      PRInt32 *aOffset)
 
139
{
 
140
  *aParent = nsnull;
 
141
  *aOffset  = 0;
 
142
 
 
143
  nsIContent* parent = aContent->GetParent();
 
144
 
 
145
  if (!parent)
 
146
    return;
 
147
 
 
148
  *aOffset = parent->IndexOf(aContent);
 
149
 
 
150
  CallQueryInterface(parent, aParent);
 
151
}
 
152
 
 
153
///////////////////////////////////////////////////////////////////////////
 
154
// ContentIsInTraversalRange: returns true if content is visited during
 
155
// the traversal of the range in the specified mode.
 
156
//
 
157
static PRBool
 
158
ContentIsInTraversalRange(nsIContent *aContent,   PRBool aIsPreMode,
 
159
                          nsIDOMNode *aStartNode, PRInt32 aStartOffset,
 
160
                          nsIDOMNode *aEndNode,   PRInt32 aEndOffset)
 
161
{
 
162
  if (!aStartNode || !aEndNode || !aContent)
 
163
    return PR_FALSE;
 
164
 
 
165
  nsCOMPtr<nsIDOMCharacterData> cData(do_QueryInterface(aContent));
 
166
 
 
167
  if (cData)
 
168
  {
 
169
    // If a chardata node contains an end point of the traversal range,
 
170
    // it is always in the traversal range.
 
171
 
 
172
    nsCOMPtr<nsIContent> startContent(do_QueryInterface(aStartNode));
 
173
    nsCOMPtr<nsIContent> endContent(do_QueryInterface(aEndNode));
 
174
 
 
175
    if (aContent == startContent || aContent == endContent)
 
176
      return PR_TRUE;
 
177
  }
 
178
 
 
179
  nsCOMPtr<nsIDOMNode> parentNode;
 
180
  PRInt32 indx = 0;
 
181
 
 
182
  ContentToParentOffset(aContent, getter_AddRefs(parentNode), &indx);
 
183
 
 
184
  if (!parentNode)
 
185
    return PR_FALSE;
 
186
 
 
187
  if (!aIsPreMode)
 
188
    ++indx;
 
189
 
 
190
  return (ComparePoints(aStartNode, aStartOffset, parentNode, indx) <= 0) &&
 
191
         (ComparePoints(aEndNode,   aEndOffset,   parentNode, indx) >= 0);
 
192
}
 
193
 
 
194
 
 
195
 
 
196
/*
 
197
 *  A simple iterator class for traversing the content in "close tag" order
 
198
 */
 
199
class nsContentIterator : public nsIContentIterator //, public nsIEnumerator
 
200
{
 
201
public:
 
202
  NS_DECL_ISUPPORTS
 
203
 
 
204
  nsContentIterator();
 
205
  virtual ~nsContentIterator();
 
206
 
 
207
  // nsIContentIterator interface methods ------------------------------
 
208
 
 
209
  virtual nsresult Init(nsIContent* aRoot);
 
210
 
 
211
  virtual nsresult Init(nsIDOMRange* aRange);
 
212
 
 
213
  virtual void First();
 
214
 
 
215
  virtual void Last();
 
216
  
 
217
  virtual void Next();
 
218
 
 
219
  virtual void Prev();
 
220
 
 
221
  virtual nsIContent *GetCurrentNode();
 
222
 
 
223
  virtual PRBool IsDone();
 
224
 
 
225
  virtual nsresult PositionAt(nsIContent* aCurNode);
 
226
 
 
227
  // nsIEnumertor interface methods ------------------------------
 
228
  
 
229
  //NS_IMETHOD CurrentItem(nsISupports **aItem);
 
230
 
 
231
protected:
 
232
 
 
233
  nsIContent *GetDeepFirstChild(nsIContent *aRoot, nsVoidArray *aIndexes);
 
234
  nsIContent *GetDeepLastChild(nsIContent *aRoot, nsVoidArray *aIndexes);
 
235
 
 
236
  nsIContent *GetNextSibling(nsIContent *aNode, nsVoidArray *aIndexes);
 
237
  nsIContent *GetPrevSibling(nsIContent *aNode, nsVoidArray *aIndexes);
 
238
 
 
239
  nsIContent *NextNode(nsIContent *aNode, nsVoidArray *aIndexes);
 
240
  nsIContent *PrevNode(nsIContent *aNode, nsVoidArray *aIndexes);
 
241
 
 
242
  // WARNING: This function is expensive
 
243
  nsresult RebuildIndexStack();
 
244
 
 
245
  void MakeEmpty();
 
246
  
 
247
  nsCOMPtr<nsIContent> mCurNode;
 
248
  nsCOMPtr<nsIContent> mFirst;
 
249
  nsCOMPtr<nsIContent> mLast;
 
250
  nsCOMPtr<nsIContent> mCommonParent;
 
251
 
 
252
  // used by nsContentIterator to cache indices
 
253
  nsAutoVoidArray mIndexes;
 
254
 
 
255
  // used by nsSubtreeIterator to cache indices.  Why put them in the base class?
 
256
  // Because otherwise I have to duplicate the routines GetNextSibling etc across both classes,
 
257
  // with slight variations for caching.  Or alternately, create a base class for the cache
 
258
  // itself and have all the cache manipulation go through a vptr.
 
259
  // I think this is the best space and speed combo, even though it's ugly.
 
260
  PRInt32 mCachedIndex;
 
261
  // another note about mCachedIndex: why should the subtree iterator use a trivial cached index
 
262
  // instead of the mre robust array of indicies (which is what the basic content iterator uses)?
 
263
  // The reason is that subtree iterators do not do much transitioning between parents and children.
 
264
  // They tend to stay at the same level.  In fact, you can prove (though I won't attempt it here)
 
265
  // that they change levels at most n+m times, where n is the height of the parent heirarchy from the 
 
266
  // range start to the common ancestor, and m is the the height of the parent heirarchy from the 
 
267
  // range end to the common ancestor.  If we used the index array, we would pay the price up front
 
268
  // for n, and then pay the cost for m on the fly later on.  With the simple cache, we only "pay
 
269
  // as we go".  Either way, we call IndexOf() once for each change of level in the heirarchy.
 
270
  // Since a trivial index is much simpler, we use it for the subtree iterator.
 
271
  
 
272
  PRBool mIsDone;
 
273
  PRBool mPre;
 
274
  
 
275
private:
 
276
 
 
277
  // no copy's or assigns  FIX ME
 
278
  nsContentIterator(const nsContentIterator&);
 
279
  nsContentIterator& operator=(const nsContentIterator&);
 
280
 
 
281
};
 
282
 
 
283
 
 
284
/*
 
285
 *  A simple iterator class for traversing the content in "open tag" order
 
286
 */
 
287
 
 
288
class nsPreContentIterator : public nsContentIterator
 
289
{
 
290
public:
 
291
  nsPreContentIterator() { mPre = PR_TRUE; }
 
292
};
 
293
 
 
294
 
 
295
 
 
296
/******************************************************
 
297
 * repository cruft
 
298
 ******************************************************/
 
299
 
 
300
nsresult NS_NewContentIterator(nsIContentIterator** aInstancePtrResult)
 
301
{
 
302
  nsContentIterator * iter = new nsContentIterator();
 
303
  if (!iter) {
 
304
    return NS_ERROR_OUT_OF_MEMORY;
 
305
  }
 
306
 
 
307
  NS_ADDREF(*aInstancePtrResult = iter);
 
308
 
 
309
  return NS_OK;
 
310
}
 
311
 
 
312
 
 
313
nsresult NS_NewPreContentIterator(nsIContentIterator** aInstancePtrResult)
 
314
{
 
315
  nsContentIterator * iter = new nsPreContentIterator();
 
316
  if (!iter) {
 
317
    return NS_ERROR_OUT_OF_MEMORY;
 
318
  }
 
319
 
 
320
  NS_ADDREF(*aInstancePtrResult = iter);
 
321
 
 
322
  return NS_OK;
 
323
}
 
324
 
 
325
 
 
326
/******************************************************
 
327
 * XPCOM cruft
 
328
 ******************************************************/
 
329
 
 
330
NS_IMPL_ISUPPORTS1(nsContentIterator, nsIContentIterator)
 
331
 
 
332
 
 
333
/******************************************************
 
334
 * constructor/destructor
 
335
 ******************************************************/
 
336
 
 
337
nsContentIterator::nsContentIterator() :
 
338
  // don't need to explicitly initialize |nsCOMPtr|s, they will automatically be NULL
 
339
  mCachedIndex(0), mIsDone(PR_FALSE), mPre(PR_FALSE)
 
340
{
 
341
}
 
342
 
 
343
 
 
344
nsContentIterator::~nsContentIterator()
 
345
{
 
346
}
 
347
 
 
348
 
 
349
/******************************************************
 
350
 * Init routines
 
351
 ******************************************************/
 
352
 
 
353
 
 
354
nsresult
 
355
nsContentIterator::Init(nsIContent* aRoot)
 
356
{
 
357
  if (!aRoot) 
 
358
    return NS_ERROR_NULL_POINTER; 
 
359
  mIsDone = PR_FALSE;
 
360
  mIndexes.Clear();
 
361
  
 
362
  if (mPre)
 
363
  {
 
364
    mFirst = aRoot;
 
365
    mLast  = GetDeepLastChild(aRoot, nsnull);
 
366
  }
 
367
  else
 
368
  {
 
369
    mFirst = GetDeepFirstChild(aRoot, nsnull); 
 
370
    mLast  = aRoot;
 
371
  }
 
372
 
 
373
  mCommonParent = aRoot;
 
374
  mCurNode = mFirst;
 
375
  RebuildIndexStack();
 
376
  return NS_OK;
 
377
}
 
378
 
 
379
 
 
380
nsresult
 
381
nsContentIterator::Init(nsIDOMRange* aRange)
 
382
{
 
383
  if (!aRange) 
 
384
    return NS_ERROR_NULL_POINTER; 
 
385
 
 
386
  nsCOMPtr<nsIDOMNode> dN;
 
387
 
 
388
  nsCOMPtr<nsIContent> startCon;
 
389
  nsCOMPtr<nsIDOMNode> startDOM;
 
390
  nsCOMPtr<nsIContent> endCon;
 
391
  nsCOMPtr<nsIDOMNode> endDOM;
 
392
  PRInt32 startIndx;
 
393
  PRInt32 endIndx;
 
394
  
 
395
  mIsDone = PR_FALSE;
 
396
 
 
397
  // get common content parent
 
398
  if (NS_FAILED(aRange->GetCommonAncestorContainer(getter_AddRefs(dN))) || !dN)
 
399
    return NS_ERROR_FAILURE;
 
400
  mCommonParent = do_QueryInterface(dN);
 
401
 
 
402
  // get the start node and offset, convert to nsIContent
 
403
  aRange->GetStartContainer(getter_AddRefs(startDOM));
 
404
  if (!startDOM) 
 
405
    return NS_ERROR_ILLEGAL_VALUE;
 
406
  startCon = do_QueryInterface(startDOM);
 
407
  if (!startCon) 
 
408
    return NS_ERROR_FAILURE;
 
409
  
 
410
  aRange->GetStartOffset(&startIndx);
 
411
  
 
412
  // get the end node and offset, convert to nsIContent
 
413
  aRange->GetEndContainer(getter_AddRefs(endDOM));
 
414
  if (!endDOM) 
 
415
    return NS_ERROR_ILLEGAL_VALUE;
 
416
  endCon = do_QueryInterface(endDOM);
 
417
  if (!endCon) 
 
418
    return NS_ERROR_FAILURE;
 
419
 
 
420
  aRange->GetEndOffset(&endIndx);
 
421
  
 
422
  nsCOMPtr<nsIDOMCharacterData> cData(do_QueryInterface(startCon));
 
423
 
 
424
  // short circuit when start node == end node
 
425
  if (startDOM == endDOM)
 
426
  {
 
427
    // Check to see if we have a collapsed range, if so,
 
428
    // there is nothing to iterate over.
 
429
    //
 
430
    // XXX: CharacterDataNodes (text nodes) are currently an exception,
 
431
    //      since we always want to be able to iterate text nodes at
 
432
    //      the end points of a range.
 
433
 
 
434
    if (!cData && startIndx == endIndx)
 
435
    {
 
436
      MakeEmpty();
 
437
      return NS_OK;
 
438
    }
 
439
 
 
440
    if (cData)
 
441
    {
 
442
      // It's a textnode.
 
443
 
 
444
      mFirst   = startCon;
 
445
      mLast    = startCon;
 
446
      mCurNode = startCon;
 
447
 
 
448
      RebuildIndexStack();
 
449
      return NS_OK;
 
450
    }
 
451
  }
 
452
  
 
453
  // Find first node in range.
 
454
 
 
455
  nsIContent *cChild = nsnull;
 
456
 
 
457
  if (!cData && ContentHasChildren(startCon))
 
458
    cChild = startCon->GetChildAt(startIndx);
 
459
 
 
460
  if (!cChild) // no children, must be a text node
 
461
  {
 
462
    if (mPre)
 
463
    {
 
464
      // XXX: In the future, if start offset is after the last
 
465
      //      character in the cdata node, should we set mFirst to
 
466
      //      the next sibling?
 
467
 
 
468
      if (!cData)
 
469
      {
 
470
        mFirst = GetNextSibling(startCon, nsnull);
 
471
 
 
472
        // Does mFirst node really intersect the range?
 
473
        // The range could be 'degenerate', ie not collapsed 
 
474
        // but still contain no content.
 
475
  
 
476
        if (mFirst && !ContentIsInTraversalRange(mFirst, mPre, startDOM, startIndx, endDOM, endIndx))
 
477
          mFirst = nsnull;
 
478
      }
 
479
      else
 
480
        mFirst = startCon;
 
481
    }
 
482
    else // post-order
 
483
      mFirst = startCon;
 
484
  }
 
485
  else
 
486
  {
 
487
    if (mPre)
 
488
      mFirst = cChild;
 
489
    else // post-order
 
490
    {
 
491
      mFirst = GetDeepFirstChild(cChild, nsnull);
 
492
 
 
493
      // Does mFirst node really intersect the range?
 
494
      // The range could be 'degenerate', ie not collapsed 
 
495
      // but still contain no content.
 
496
  
 
497
      if (mFirst && !ContentIsInTraversalRange(mFirst, mPre, startDOM, startIndx, endDOM, endIndx))
 
498
        mFirst = nsnull;
 
499
    }
 
500
  }
 
501
 
 
502
 
 
503
  // Find last node in range.
 
504
 
 
505
  cData = do_QueryInterface(endCon);
 
506
 
 
507
  if (cData || !ContentHasChildren(endCon) || endIndx == 0)
 
508
  {
 
509
    if (mPre)
 
510
      mLast = endCon;
 
511
    else // post-order
 
512
    {
 
513
      // XXX: In the future, if end offset is before the first
 
514
      //      character in the cdata node, should we set mLast to
 
515
      //      the prev sibling?
 
516
 
 
517
      if (!cData)
 
518
      {
 
519
        mLast = GetPrevSibling(endCon, nsnull);
 
520
 
 
521
        if (!ContentIsInTraversalRange(mLast, mPre, startDOM, startIndx, endDOM, endIndx))
 
522
          mLast = nsnull;
 
523
      }
 
524
      else
 
525
        mLast = endCon;
 
526
    }
 
527
  }
 
528
  else
 
529
  {
 
530
    PRInt32 indx = endIndx;
 
531
 
 
532
    cChild = endCon->GetChildAt(--indx);
 
533
 
 
534
    if (!cChild)  // No child at offset!
 
535
    {
 
536
      NS_NOTREACHED("nsContentIterator::nsContentIterator");
 
537
      return NS_ERROR_FAILURE; 
 
538
    }
 
539
 
 
540
    if (mPre)
 
541
    {
 
542
      mLast  = GetDeepLastChild(cChild, nsnull);
 
543
 
 
544
      if (!ContentIsInTraversalRange(mLast, mPre, startDOM, startIndx, endDOM, endIndx))
 
545
        mLast = nsnull;
 
546
    }
 
547
    else // post-order
 
548
      mLast = cChild;
 
549
  }
 
550
 
 
551
  // If either first or last is null, they both
 
552
  // have to be null!
 
553
 
 
554
  if (!mFirst || !mLast)
 
555
  {
 
556
    mFirst = nsnull;
 
557
    mLast  = nsnull;
 
558
  }
 
559
  
 
560
  mCurNode = mFirst;
 
561
  mIsDone  = !mCurNode;
 
562
 
 
563
  if (!mCurNode)
 
564
    mIndexes.Clear();
 
565
  else
 
566
    RebuildIndexStack();
 
567
 
 
568
  return NS_OK;
 
569
}
 
570
 
 
571
 
 
572
/******************************************************
 
573
 * Helper routines
 
574
 ******************************************************/
 
575
// WARNING: This function is expensive
 
576
nsresult nsContentIterator::RebuildIndexStack()
 
577
{
 
578
  // Make sure we start at the right indexes on the stack!  Build array up
 
579
  // to common parent of start and end.  Perhaps it's too many entries, but
 
580
  // thats far better than too few.
 
581
  nsIContent* parent;
 
582
  nsIContent* current;
 
583
 
 
584
  mIndexes.Clear();
 
585
  current = mCurNode;
 
586
  if (!current) {
 
587
    return NS_OK;
 
588
  }
 
589
 
 
590
  while (current != mCommonParent)
 
591
  {
 
592
    parent = current->GetParent();
 
593
    
 
594
    if (!parent)
 
595
      return NS_ERROR_FAILURE;
 
596
  
 
597
    mIndexes.InsertElementAt(NS_INT32_TO_PTR(parent->IndexOf(current)), 0);
 
598
 
 
599
    current = parent;
 
600
  }
 
601
  return NS_OK;
 
602
}
 
603
 
 
604
void
 
605
nsContentIterator::MakeEmpty()
 
606
{
 
607
  mCurNode      = nsnull;
 
608
  mFirst        = nsnull;
 
609
  mLast         = nsnull;
 
610
  mCommonParent = nsnull;
 
611
  mIsDone       = PR_TRUE;
 
612
  mIndexes.Clear();
 
613
}
 
614
 
 
615
nsIContent *
 
616
nsContentIterator::GetDeepFirstChild(nsIContent *aRoot, nsVoidArray *aIndexes)
 
617
{
 
618
  if (!aRoot) {
 
619
    return nsnull;
 
620
  }
 
621
 
 
622
  nsIContent *cN = aRoot;
 
623
  nsIContent *cChild = cN->GetChildAt(0);
 
624
 
 
625
  while (cChild)
 
626
  {
 
627
    if (aIndexes)
 
628
    {
 
629
      // Add this node to the stack of indexes
 
630
      aIndexes->AppendElement(NS_INT32_TO_PTR(0));
 
631
    }
 
632
    cN = cChild;
 
633
    cChild = cN->GetChildAt(0);
 
634
  }
 
635
 
 
636
  return cN;
 
637
}
 
638
 
 
639
nsIContent *
 
640
nsContentIterator::GetDeepLastChild(nsIContent *aRoot, nsVoidArray *aIndexes)
 
641
{
 
642
  if (!aRoot) {
 
643
    return nsnull;
 
644
  }
 
645
 
 
646
  nsIContent *deepLastChild = aRoot;
 
647
 
 
648
  nsIContent *cN = aRoot;
 
649
  PRInt32 numChildren = cN->GetChildCount();
 
650
 
 
651
  while (numChildren)
 
652
  {
 
653
    nsIContent *cChild = cN->GetChildAt(--numChildren);
 
654
 
 
655
    if (aIndexes)
 
656
    {
 
657
      // Add this node to the stack of indexes
 
658
      aIndexes->AppendElement(NS_INT32_TO_PTR(numChildren));
 
659
    }
 
660
    numChildren = cChild->GetChildCount();
 
661
    cN = cChild;
 
662
 
 
663
    deepLastChild = cN;
 
664
  }
 
665
 
 
666
  return deepLastChild;
 
667
}
 
668
 
 
669
// Get the next sibling, or parents next sibling, or grandpa's next sibling...
 
670
nsIContent *
 
671
nsContentIterator::GetNextSibling(nsIContent *aNode, 
 
672
                                  nsVoidArray *aIndexes)
 
673
{
 
674
  if (!aNode) 
 
675
    return nsnull;
 
676
 
 
677
  nsIContent *parent = aNode->GetParent();
 
678
  if (!parent)
 
679
    return nsnull;
 
680
 
 
681
  PRInt32 indx;
 
682
 
 
683
  if (aIndexes)
 
684
  {
 
685
    NS_ASSERTION(aIndexes->Count() > 0, "ContentIterator stack underflow");
 
686
    // use the last entry on the Indexes array for the current index
 
687
    indx = NS_PTR_TO_INT32((*aIndexes)[aIndexes->Count()-1]);
 
688
  }
 
689
  else
 
690
    indx = mCachedIndex;
 
691
 
 
692
  // reverify that the index of the current node hasn't changed.
 
693
  // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
 
694
  // ignore result this time - the index may now be out of range.
 
695
  nsIContent *sib = parent->GetChildAt(indx);
 
696
  if (sib != aNode)
 
697
  {
 
698
    // someone changed our index - find the new index the painful way
 
699
    indx = parent->IndexOf(aNode);
 
700
  }
 
701
 
 
702
  // indx is now canonically correct
 
703
  if ((sib = parent->GetChildAt(++indx)))
 
704
  {
 
705
    // update index cache
 
706
    if (aIndexes)
 
707
    {
 
708
      aIndexes->ReplaceElementAt(NS_INT32_TO_PTR(indx),aIndexes->Count()-1);
 
709
    }
 
710
    else mCachedIndex = indx;
 
711
  }
 
712
  else
 
713
  {
 
714
    if (parent != mCommonParent)
 
715
    {
 
716
      if (aIndexes)
 
717
      {
 
718
        // pop node off the stack, go up one level and return parent or fail.
 
719
        // Don't leave the index empty, especially if we're
 
720
        // returning NULL.  This confuses other parts of the code.
 
721
        if (aIndexes->Count() > 1)
 
722
          aIndexes->RemoveElementAt(aIndexes->Count()-1);
 
723
      }
 
724
    }
 
725
 
 
726
    // ok to leave cache out of date here if parent == mCommonParent?
 
727
    sib = GetNextSibling(parent, aIndexes);
 
728
  }
 
729
  
 
730
  return sib;
 
731
}
 
732
 
 
733
// Get the prev sibling, or parents prev sibling, or grandpa's prev sibling...
 
734
nsIContent *
 
735
nsContentIterator::GetPrevSibling(nsIContent *aNode, 
 
736
                                  nsVoidArray *aIndexes)
 
737
{
 
738
  if (!aNode)
 
739
    return nsnull;
 
740
 
 
741
  nsIContent *parent = aNode->GetParent();
 
742
  if (!parent)
 
743
    return nsnull;
 
744
 
 
745
  PRInt32 indx;
 
746
 
 
747
  if (aIndexes)
 
748
  {
 
749
    NS_ASSERTION(aIndexes->Count() > 0, "ContentIterator stack underflow");
 
750
    // use the last entry on the Indexes array for the current index
 
751
    indx = NS_PTR_TO_INT32((*aIndexes)[aIndexes->Count()-1]);
 
752
  }
 
753
  else
 
754
    indx = mCachedIndex;
 
755
 
 
756
  // reverify that the index of the current node hasn't changed
 
757
  // ignore result this time - the index may now be out of range.
 
758
  nsIContent *sib = parent->GetChildAt(indx);
 
759
  if (sib != aNode)
 
760
  {
 
761
    // someone changed our index - find the new index the painful way
 
762
    indx = parent->IndexOf(aNode);
 
763
  }
 
764
 
 
765
  // indx is now canonically correct
 
766
  if (indx > 0 && (sib = parent->GetChildAt(--indx)))
 
767
  {
 
768
    // update index cache
 
769
    if (aIndexes)
 
770
    {
 
771
      aIndexes->ReplaceElementAt(NS_INT32_TO_PTR(indx),aIndexes->Count()-1);
 
772
    }
 
773
    else mCachedIndex = indx;
 
774
  }
 
775
  else if (parent != mCommonParent)
 
776
  {
 
777
    if (aIndexes)
 
778
    {
 
779
      // pop node off the stack, go up one level and try again.
 
780
      aIndexes->RemoveElementAt(aIndexes->Count()-1);
 
781
    }
 
782
    return GetPrevSibling(parent, aIndexes);
 
783
  }
 
784
 
 
785
  return sib;
 
786
}
 
787
 
 
788
nsIContent *
 
789
nsContentIterator::NextNode(nsIContent *aNode, nsVoidArray *aIndexes)
 
790
{
 
791
  nsIContent *cN = aNode;
 
792
  nsIContent *nextNode = nsnull;
 
793
 
 
794
  if (mPre)  // if we are a Pre-order iterator, use pre-order
 
795
  {
 
796
    // if it has children then next node is first child
 
797
    if (ContentHasChildren(cN))
 
798
    {
 
799
      nsIContent *cFirstChild = cN->GetChildAt(0);
 
800
 
 
801
      // update cache
 
802
      if (aIndexes)
 
803
      {
 
804
        // push an entry on the index stack
 
805
        aIndexes->AppendElement(NS_INT32_TO_PTR(0));
 
806
      }
 
807
      else mCachedIndex = 0;
 
808
      
 
809
      return cFirstChild;
 
810
    }
 
811
 
 
812
    // else next sibling is next
 
813
    nextNode = GetNextSibling(cN, aIndexes);
 
814
  }
 
815
  else  // post-order
 
816
  {
 
817
    nsIContent *parent = cN->GetParent();
 
818
    nsIContent *cSibling = nsnull;
 
819
    PRInt32 indx;
 
820
 
 
821
    // get the cached index
 
822
    if (aIndexes)
 
823
    {
 
824
      NS_ASSERTION(aIndexes->Count() > 0, "ContentIterator stack underflow");
 
825
      // use the last entry on the Indexes array for the current index
 
826
      indx = NS_PTR_TO_INT32((*aIndexes)[aIndexes->Count()-1]);
 
827
    }
 
828
    else indx = mCachedIndex;
 
829
 
 
830
    // reverify that the index of the current node hasn't changed.
 
831
    // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
 
832
    // ignore result this time - the index may now be out of range.
 
833
    if (indx >= 0)
 
834
      cSibling = parent->GetChildAt(indx);
 
835
    if (cSibling != cN)
 
836
    {
 
837
      // someone changed our index - find the new index the painful way
 
838
      indx = parent->IndexOf(cN);
 
839
    }
 
840
 
 
841
    // indx is now canonically correct
 
842
    cSibling = parent->GetChildAt(++indx);
 
843
    if (cSibling)
 
844
    {
 
845
      // update cache
 
846
      if (aIndexes)
 
847
      {
 
848
        // replace an entry on the index stack
 
849
        aIndexes->ReplaceElementAt(NS_INT32_TO_PTR(indx),aIndexes->Count()-1);
 
850
      }
 
851
      else mCachedIndex = indx;
 
852
      
 
853
      // next node is siblings "deep left" child
 
854
      return GetDeepFirstChild(cSibling, aIndexes); 
 
855
    }
 
856
  
 
857
    // else it's the parent
 
858
    // update cache
 
859
    if (aIndexes)
 
860
    {
 
861
      // pop an entry off the index stack
 
862
      // Don't leave the index empty, especially if we're
 
863
      // returning NULL.  This confuses other parts of the code.
 
864
      if (aIndexes->Count() > 1)
 
865
        aIndexes->RemoveElementAt(aIndexes->Count()-1);
 
866
    }
 
867
    else mCachedIndex = 0;   // this might be wrong, but we are better off guessing
 
868
    nextNode = parent;
 
869
  }
 
870
 
 
871
  return nextNode;
 
872
}
 
873
 
 
874
nsIContent *
 
875
nsContentIterator::PrevNode(nsIContent *aNode, nsVoidArray *aIndexes)
 
876
{
 
877
  nsIContent *prevNode = nsnull;
 
878
  nsIContent *cN = aNode;
 
879
   
 
880
  if (mPre)  // if we are a Pre-order iterator, use pre-order
 
881
  {
 
882
    nsIContent *parent = cN->GetParent();
 
883
    nsIContent *cSibling = nsnull;
 
884
    PRInt32 indx;
 
885
 
 
886
    // get the cached index
 
887
    if (aIndexes)
 
888
    {
 
889
      NS_ASSERTION(aIndexes->Count() > 0, "ContentIterator stack underflow");
 
890
      // use the last entry on the Indexes array for the current index
 
891
      indx = NS_PTR_TO_INT32((*aIndexes)[aIndexes->Count()-1]);
 
892
    }
 
893
    else indx = mCachedIndex;
 
894
 
 
895
    // reverify that the index of the current node hasn't changed.
 
896
    // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
 
897
    // ignore result this time - the index may now be out of range.
 
898
    if (indx >= 0)
 
899
      cSibling = parent->GetChildAt(indx);
 
900
 
 
901
    if (cSibling != cN)
 
902
    {
 
903
      // someone changed our index - find the new index the painful way
 
904
      indx = parent->IndexOf(cN);
 
905
    }
 
906
 
 
907
    // indx is now canonically correct
 
908
    if (indx && (cSibling = parent->GetChildAt(--indx)))
 
909
    {
 
910
      // update cache
 
911
      if (aIndexes)
 
912
      {
 
913
        // replace an entry on the index stack
 
914
        aIndexes->ReplaceElementAt(NS_INT32_TO_PTR(indx),aIndexes->Count()-1);
 
915
      }
 
916
      else mCachedIndex = indx;
 
917
      
 
918
      // prev node is siblings "deep right" child
 
919
      return GetDeepLastChild(cSibling, aIndexes); 
 
920
    }
 
921
  
 
922
    // else it's the parent
 
923
    // update cache
 
924
    if (aIndexes)
 
925
    {
 
926
      // pop an entry off the index stack
 
927
      aIndexes->RemoveElementAt(aIndexes->Count()-1);
 
928
    }
 
929
    else mCachedIndex = 0;   // this might be wrong, but we are better off guessing
 
930
    prevNode = parent;
 
931
  }
 
932
  else  // post-order
 
933
  {
 
934
    PRInt32 numChildren = cN->GetChildCount();
 
935
  
 
936
    // if it has children then prev node is last child
 
937
    if (numChildren)
 
938
    {
 
939
      nsIContent *cLastChild = cN->GetChildAt(--numChildren);
 
940
 
 
941
      // update cache
 
942
      if (aIndexes)
 
943
      {
 
944
        // push an entry on the index stack
 
945
        aIndexes->AppendElement(NS_INT32_TO_PTR(numChildren));
 
946
      }
 
947
      else mCachedIndex = numChildren;
 
948
      
 
949
      return cLastChild;
 
950
    }
 
951
 
 
952
    // else prev sibling is previous
 
953
    prevNode = GetPrevSibling(cN, aIndexes);
 
954
  }
 
955
 
 
956
  return prevNode;
 
957
}
 
958
 
 
959
/******************************************************
 
960
 * ContentIterator routines
 
961
 ******************************************************/
 
962
 
 
963
void
 
964
nsContentIterator::First()
 
965
{
 
966
  NS_ASSERTION(mFirst, "No first node!");
 
967
 
 
968
  if (mFirst) {
 
969
#ifdef DEBUG
 
970
    nsresult rv =
 
971
#endif
 
972
    PositionAt(mFirst);
 
973
 
 
974
    NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
 
975
  }
 
976
 
 
977
  mIsDone = mFirst == nsnull;
 
978
}
 
979
 
 
980
 
 
981
void
 
982
nsContentIterator::Last()
 
983
{
 
984
  NS_ASSERTION(mLast, "No last node!");
 
985
 
 
986
  if (mLast) {
 
987
#ifdef DEBUG
 
988
    nsresult rv =
 
989
#endif
 
990
    PositionAt(mLast);
 
991
 
 
992
    NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
 
993
  }
 
994
 
 
995
  mIsDone = mLast == nsnull;
 
996
}
 
997
 
 
998
 
 
999
void
 
1000
nsContentIterator::Next()
 
1001
{
 
1002
  if (mIsDone || !mCurNode) 
 
1003
    return;
 
1004
 
 
1005
  if (mCurNode == mLast) 
 
1006
  {
 
1007
    mIsDone = PR_TRUE;
 
1008
    return;
 
1009
  }
 
1010
 
 
1011
  mCurNode = NextNode(mCurNode, &mIndexes);
 
1012
}
 
1013
 
 
1014
 
 
1015
void
 
1016
nsContentIterator::Prev()
 
1017
{
 
1018
  if (mIsDone || !mCurNode) 
 
1019
    return;
 
1020
 
 
1021
  if (mCurNode == mFirst) 
 
1022
  {
 
1023
    mIsDone = PR_TRUE;
 
1024
    return;
 
1025
  }
 
1026
 
 
1027
  mCurNode = PrevNode(mCurNode, &mIndexes);
 
1028
}
 
1029
 
 
1030
 
 
1031
PRBool
 
1032
nsContentIterator::IsDone()
 
1033
{
 
1034
  return mIsDone;
 
1035
}
 
1036
 
 
1037
 
 
1038
// Keeping arrays of indexes for the stack of nodes makes PositionAt
 
1039
// interesting...
 
1040
nsresult
 
1041
nsContentIterator::PositionAt(nsIContent* aCurNode)
 
1042
{
 
1043
  if (!aCurNode)
 
1044
    return NS_ERROR_NULL_POINTER;
 
1045
 
 
1046
  nsIContent *newCurNode = aCurNode;
 
1047
  nsIContent *tempNode = mCurNode;
 
1048
 
 
1049
  mCurNode = aCurNode;
 
1050
  // take an early out if this doesn't actually change the position
 
1051
  if (mCurNode == tempNode)
 
1052
  {
 
1053
    mIsDone = PR_FALSE;  // paranoia
 
1054
    return NS_OK;
 
1055
  }
 
1056
 
 
1057
  // Check to see if the node falls within the traversal range.
 
1058
 
 
1059
  nsCOMPtr<nsIDOMNode> firstNode(do_QueryInterface(mFirst));
 
1060
  nsCOMPtr<nsIDOMNode> lastNode(do_QueryInterface(mLast));
 
1061
  PRInt32 firstOffset=0, lastOffset=0;
 
1062
 
 
1063
  if (firstNode && lastNode)
 
1064
  {
 
1065
    PRUint32 numChildren;
 
1066
 
 
1067
    if (mPre)
 
1068
    {
 
1069
      ContentToParentOffset(mFirst, getter_AddRefs(firstNode), &firstOffset);
 
1070
 
 
1071
      numChildren = GetNumChildren(lastNode);
 
1072
 
 
1073
      if (numChildren)
 
1074
        lastOffset = 0;
 
1075
      else
 
1076
      {
 
1077
        ContentToParentOffset(mLast, getter_AddRefs(lastNode), &lastOffset);
 
1078
        ++lastOffset;
 
1079
      }
 
1080
    }
 
1081
    else
 
1082
    {
 
1083
      numChildren = GetNumChildren(firstNode);
 
1084
 
 
1085
      if (numChildren)
 
1086
        firstOffset = numChildren;
 
1087
      else
 
1088
        ContentToParentOffset(mFirst, getter_AddRefs(firstNode), &firstOffset);
 
1089
 
 
1090
      ContentToParentOffset(mLast, getter_AddRefs(lastNode), &lastOffset);
 
1091
      ++lastOffset;
 
1092
    }
 
1093
  }
 
1094
 
 
1095
  if (!firstNode || !lastNode ||
 
1096
      !ContentIsInTraversalRange(mCurNode, mPre, firstNode, firstOffset,
 
1097
                                 lastNode, lastOffset))
 
1098
  {
 
1099
    mIsDone = PR_TRUE;
 
1100
    return NS_ERROR_FAILURE;
 
1101
  }
 
1102
 
 
1103
  // We can be at ANY node in the sequence.
 
1104
  // Need to regenerate the array of indexes back to the root or common parent!
 
1105
  nsAutoVoidArray      oldParentStack;
 
1106
  nsAutoVoidArray      newIndexes;
 
1107
 
 
1108
  // Get a list of the parents up to the root, then compare the new node
 
1109
  // with entries in that array until we find a match (lowest common
 
1110
  // ancestor).  If no match, use IndexOf, take the parent, and repeat.
 
1111
  // This avoids using IndexOf() N times on possibly large arrays.  We
 
1112
  // still end up doing it a fair bit.  It's better to use Clone() if
 
1113
  // possible.
 
1114
 
 
1115
  // we know the depth we're down (though we may not have started at the
 
1116
  // top).
 
1117
  if (!oldParentStack.SizeTo(mIndexes.Count()+1))
 
1118
    return NS_ERROR_FAILURE;
 
1119
 
 
1120
  // plus one for the node we're currently on.
 
1121
  for (PRInt32 i = mIndexes.Count()+1; i > 0 && tempNode; i--)
 
1122
  {
 
1123
    // Insert at head since we're walking up
 
1124
    oldParentStack.InsertElementAt(tempNode,0);
 
1125
 
 
1126
    nsIContent *parent = tempNode->GetParent();
 
1127
 
 
1128
    if (!parent)  // this node has no parent, and thus no index
 
1129
      break;
 
1130
 
 
1131
    if (parent == mCurNode)
 
1132
    {
 
1133
      // The position was moved to a parent of the current position. 
 
1134
      // All we need to do is drop some indexes.  Shortcut here.
 
1135
      mIndexes.RemoveElementsAt(mIndexes.Count() - (oldParentStack.Count()+1),
 
1136
                                oldParentStack.Count());
 
1137
      mIsDone = PR_FALSE;
 
1138
      return NS_OK;
 
1139
    }
 
1140
    tempNode = parent;
 
1141
  }
 
1142
 
 
1143
  // Ok.  We have the array of old parents.  Look for a match.
 
1144
  while (newCurNode)
 
1145
  {
 
1146
    nsIContent *parent = newCurNode->GetParent();
 
1147
 
 
1148
    if (!parent)  // this node has no parent, and thus no index
 
1149
      break;
 
1150
 
 
1151
    PRInt32 indx = parent->IndexOf(newCurNode);
 
1152
 
 
1153
    // insert at the head!
 
1154
    newIndexes.InsertElementAt(NS_INT32_TO_PTR(indx),0);
 
1155
 
 
1156
    // look to see if the parent is in the stack
 
1157
    indx = oldParentStack.IndexOf(parent);
 
1158
    if (indx >= 0)
 
1159
    {
 
1160
      // ok, the parent IS on the old stack!  Rework things.
 
1161
      // we want newIndexes to replace all nodes equal to or below the match
 
1162
      // Note that index oldParentStack.Count()-1 is the last node, which is
 
1163
      // one BELOW the last index in the mIndexes stack.
 
1164
      PRInt32 numToDrop = oldParentStack.Count()-(1+indx);
 
1165
      if (numToDrop > 0)
 
1166
        mIndexes.RemoveElementsAt(mIndexes.Count() - numToDrop,numToDrop);
 
1167
      mIndexes.InsertElementsAt(newIndexes,mIndexes.Count());
 
1168
 
 
1169
      break;
 
1170
    }
 
1171
    newCurNode = parent;
 
1172
  }
 
1173
 
 
1174
  // phew!
 
1175
 
 
1176
  mIsDone = PR_FALSE;
 
1177
  return NS_OK;
 
1178
}
 
1179
 
 
1180
 
 
1181
nsIContent *
 
1182
nsContentIterator::GetCurrentNode()
 
1183
{
 
1184
  if (mIsDone) {
 
1185
    return nsnull;
 
1186
  }
 
1187
 
 
1188
  NS_ASSERTION(mCurNode, "Null current node in an iterator that's not done!");
 
1189
 
 
1190
  return mCurNode;
 
1191
}
 
1192
 
 
1193
 
 
1194
 
 
1195
 
 
1196
 
 
1197
/*====================================================================================*/
 
1198
/*====================================================================================*/
 
1199
 
 
1200
 
 
1201
 
 
1202
 
 
1203
 
 
1204
 
 
1205
/******************************************************
 
1206
 * nsContentSubtreeIterator
 
1207
 ******************************************************/
 
1208
 
 
1209
 
 
1210
/*
 
1211
 *  A simple iterator class for traversing the content in "top subtree" order
 
1212
 */
 
1213
class nsContentSubtreeIterator : public nsContentIterator 
 
1214
{
 
1215
public:
 
1216
  nsContentSubtreeIterator() {};
 
1217
  virtual ~nsContentSubtreeIterator() {};
 
1218
 
 
1219
  // nsContentIterator overrides ------------------------------
 
1220
 
 
1221
  virtual nsresult Init(nsIContent* aRoot);
 
1222
 
 
1223
  virtual nsresult Init(nsIDOMRange* aRange);
 
1224
 
 
1225
  virtual void Next();
 
1226
 
 
1227
  virtual void Prev();
 
1228
 
 
1229
  virtual nsresult PositionAt(nsIContent* aCurNode);
 
1230
 
 
1231
  // Must override these because we don't do PositionAt
 
1232
  virtual void First();
 
1233
 
 
1234
  // Must override these because we don't do PositionAt
 
1235
  virtual void Last();
 
1236
 
 
1237
protected:
 
1238
 
 
1239
  nsresult GetTopAncestorInRange(nsIContent *aNode,
 
1240
                                 nsCOMPtr<nsIContent> *outAnestor);
 
1241
 
 
1242
  // no copy's or assigns  FIX ME
 
1243
  nsContentSubtreeIterator(const nsContentSubtreeIterator&);
 
1244
  nsContentSubtreeIterator& operator=(const nsContentSubtreeIterator&);
 
1245
 
 
1246
  nsCOMPtr<nsIDOMRange> mRange;
 
1247
  // these arrays all typically are used and have elements
 
1248
#if 0
 
1249
  nsAutoVoidArray mStartNodes;
 
1250
  nsAutoVoidArray mStartOffsets;
 
1251
#endif
 
1252
 
 
1253
  nsAutoVoidArray mEndNodes;
 
1254
  nsAutoVoidArray mEndOffsets;
 
1255
};
 
1256
 
 
1257
nsresult NS_NewContentSubtreeIterator(nsIContentIterator** aInstancePtrResult);
 
1258
 
 
1259
 
 
1260
 
 
1261
 
 
1262
/******************************************************
 
1263
 * repository cruft
 
1264
 ******************************************************/
 
1265
 
 
1266
nsresult NS_NewContentSubtreeIterator(nsIContentIterator** aInstancePtrResult)
 
1267
{
 
1268
  nsContentIterator * iter = new nsContentSubtreeIterator();
 
1269
  if (!iter) {
 
1270
    return NS_ERROR_OUT_OF_MEMORY;
 
1271
  }
 
1272
 
 
1273
  NS_ADDREF(*aInstancePtrResult = iter);
 
1274
 
 
1275
  return NS_OK;
 
1276
}
 
1277
 
 
1278
 
 
1279
 
 
1280
/******************************************************
 
1281
 * Init routines
 
1282
 ******************************************************/
 
1283
 
 
1284
 
 
1285
nsresult nsContentSubtreeIterator::Init(nsIContent* aRoot)
 
1286
{
 
1287
  return NS_ERROR_NOT_IMPLEMENTED;
 
1288
}
 
1289
 
 
1290
 
 
1291
nsresult nsContentSubtreeIterator::Init(nsIDOMRange* aRange)
 
1292
{
 
1293
  if (!aRange) 
 
1294
    return NS_ERROR_NULL_POINTER; 
 
1295
 
 
1296
  mIsDone = PR_FALSE;
 
1297
 
 
1298
  mRange = aRange;
 
1299
  
 
1300
  // get the start node and offset, convert to nsIContent
 
1301
  nsCOMPtr<nsIDOMNode> commonParent;
 
1302
  nsCOMPtr<nsIDOMNode> startParent;
 
1303
  nsCOMPtr<nsIDOMNode> endParent;
 
1304
  nsCOMPtr<nsIContent> cStartP;
 
1305
  nsCOMPtr<nsIContent> cEndP;
 
1306
  nsCOMPtr<nsIContent> cN;
 
1307
  nsIContent *firstCandidate = nsnull;
 
1308
  nsIContent *lastCandidate = nsnull;
 
1309
  nsCOMPtr<nsIDOMNode> dChild;
 
1310
  nsCOMPtr<nsIContent> cChild;
 
1311
  PRInt32 indx, startIndx, endIndx;
 
1312
  PRInt32 numChildren;
 
1313
 
 
1314
  // get common content parent
 
1315
  if (NS_FAILED(aRange->GetCommonAncestorContainer(getter_AddRefs(commonParent))) || !commonParent)
 
1316
    return NS_ERROR_FAILURE;
 
1317
  mCommonParent = do_QueryInterface(commonParent);
 
1318
 
 
1319
  // get start content parent
 
1320
  if (NS_FAILED(aRange->GetStartContainer(getter_AddRefs(startParent))) || !startParent)
 
1321
    return NS_ERROR_FAILURE;
 
1322
  cStartP = do_QueryInterface(startParent);
 
1323
  aRange->GetStartOffset(&startIndx);
 
1324
 
 
1325
  // get end content parent
 
1326
  if (NS_FAILED(aRange->GetEndContainer(getter_AddRefs(endParent))) || !endParent)
 
1327
    return NS_ERROR_FAILURE;
 
1328
  cEndP = do_QueryInterface(endParent);
 
1329
  aRange->GetEndOffset(&endIndx);
 
1330
  
 
1331
  // short circuit when start node == end node
 
1332
  if (startParent == endParent)
 
1333
  {
 
1334
    cChild = cStartP->GetChildAt(0);
 
1335
  
 
1336
    if (!cChild) // no children, must be a text node or empty container
 
1337
    {
 
1338
      // all inside one text node - empty subtree iterator
 
1339
      MakeEmpty();
 
1340
      return NS_OK;
 
1341
    }
 
1342
    else
 
1343
    {
 
1344
      if (startIndx == endIndx)  // collapsed range
 
1345
      {
 
1346
        MakeEmpty();
 
1347
        return NS_OK;
 
1348
      }
 
1349
    }
 
1350
  }
 
1351
  
 
1352
  // cache ancestors
 
1353
#if 0
 
1354
  nsContentUtils::GetAncestorsAndOffsets(startParent, startIndx,
 
1355
                                         &mStartNodes, &mStartOffsets);
 
1356
#endif
 
1357
  nsContentUtils::GetAncestorsAndOffsets(endParent, endIndx,
 
1358
                                         &mEndNodes, &mEndOffsets);
 
1359
 
 
1360
  // find first node in range
 
1361
  aRange->GetStartOffset(&indx);
 
1362
  numChildren = GetNumChildren(startParent);
 
1363
  
 
1364
  if (!numChildren) // no children, must be a text node
 
1365
  {
 
1366
    cN = cStartP; 
 
1367
  }
 
1368
  else
 
1369
  {
 
1370
    dChild = GetChildAt(startParent, indx);
 
1371
    cChild = do_QueryInterface(dChild);
 
1372
    if (!cChild)  // offset after last child
 
1373
    {
 
1374
      cN = cStartP;
 
1375
    }
 
1376
    else
 
1377
    {
 
1378
      firstCandidate = cChild;
 
1379
    }
 
1380
  }
 
1381
  
 
1382
  if (!firstCandidate)
 
1383
  {
 
1384
    // then firstCandidate is next node after cN
 
1385
    firstCandidate = GetNextSibling(cN, nsnull);
 
1386
 
 
1387
    if (!firstCandidate)
 
1388
    {
 
1389
      MakeEmpty();
 
1390
      return NS_OK;
 
1391
    }
 
1392
  }
 
1393
  
 
1394
  firstCandidate = GetDeepFirstChild(firstCandidate, nsnull);
 
1395
  
 
1396
  // confirm that this first possible contained node
 
1397
  // is indeed contained.  Else we have a range that
 
1398
  // does not fully contain any node.
 
1399
  
 
1400
  PRBool nodeBefore, nodeAfter;
 
1401
  if (NS_FAILED(nsRange::CompareNodeToRange(firstCandidate, aRange,
 
1402
                                            &nodeBefore, &nodeAfter)))
 
1403
    return NS_ERROR_FAILURE;
 
1404
 
 
1405
  if (nodeBefore || nodeAfter)
 
1406
  {
 
1407
    MakeEmpty();
 
1408
    return NS_OK;
 
1409
  }
 
1410
 
 
1411
  // cool, we have the first node in the range.  Now we walk
 
1412
  // up it's ancestors to find the most senior that is still
 
1413
  // in the range.  That's the real first node.
 
1414
  if (NS_FAILED(GetTopAncestorInRange(firstCandidate, address_of(mFirst))))
 
1415
    return NS_ERROR_FAILURE;
 
1416
 
 
1417
  // now to find the last node
 
1418
  aRange->GetEndOffset(&indx);
 
1419
  numChildren = GetNumChildren(endParent);
 
1420
 
 
1421
  if (indx > numChildren) indx = numChildren;
 
1422
  if (!indx)
 
1423
  {
 
1424
    cN = cEndP;
 
1425
  }
 
1426
  else
 
1427
  {
 
1428
    if (!numChildren) // no children, must be a text node
 
1429
    {
 
1430
      cN = cEndP; 
 
1431
    }
 
1432
    else
 
1433
    {
 
1434
      dChild = GetChildAt(endParent, --indx);
 
1435
      cChild = do_QueryInterface(dChild);
 
1436
      if (!cChild)  // shouldn't happen
 
1437
      {
 
1438
        NS_ASSERTION(0,"tree traversal trouble in nsContentSubtreeIterator::Init");
 
1439
        return NS_ERROR_FAILURE;
 
1440
      }
 
1441
      else
 
1442
      {
 
1443
        lastCandidate = cChild;
 
1444
      }
 
1445
    }
 
1446
  }
 
1447
  
 
1448
  if (!lastCandidate)
 
1449
  {
 
1450
    // then lastCandidate is prev node before cN
 
1451
    lastCandidate = GetPrevSibling(cN, nsnull);
 
1452
  }
 
1453
  
 
1454
  lastCandidate = GetDeepLastChild(lastCandidate, nsnull);
 
1455
  
 
1456
  // confirm that this last possible contained node
 
1457
  // is indeed contained.  Else we have a range that
 
1458
  // does not fully contain any node.
 
1459
  
 
1460
  if (NS_FAILED(nsRange::CompareNodeToRange(lastCandidate, aRange, &nodeBefore,
 
1461
                                            &nodeAfter)))
 
1462
    return NS_ERROR_FAILURE;
 
1463
 
 
1464
  if (nodeBefore || nodeAfter)
 
1465
  {
 
1466
    MakeEmpty();
 
1467
    return NS_OK;
 
1468
  }
 
1469
 
 
1470
  // cool, we have the last node in the range.  Now we walk
 
1471
  // up it's ancestors to find the most senior that is still
 
1472
  // in the range.  That's the real first node.
 
1473
  if (NS_FAILED(GetTopAncestorInRange(lastCandidate, address_of(mLast))))
 
1474
    return NS_ERROR_FAILURE;
 
1475
  
 
1476
  mCurNode = mFirst;
 
1477
 
 
1478
  return NS_OK;
 
1479
}
 
1480
 
 
1481
 
 
1482
/****************************************************************
 
1483
 * nsContentSubtreeIterator overrides of ContentIterator routines
 
1484
 ****************************************************************/
 
1485
 
 
1486
// we can't call PositionAt in a subtree iterator...
 
1487
void
 
1488
nsContentSubtreeIterator::First()
 
1489
{
 
1490
  mIsDone = mFirst == nsnull;
 
1491
 
 
1492
  mCurNode = mFirst;
 
1493
}
 
1494
 
 
1495
// we can't call PositionAt in a subtree iterator...
 
1496
void
 
1497
nsContentSubtreeIterator::Last()
 
1498
{
 
1499
  mIsDone = mLast == nsnull;
 
1500
 
 
1501
  mCurNode = mLast;
 
1502
}
 
1503
 
 
1504
 
 
1505
void
 
1506
nsContentSubtreeIterator::Next()
 
1507
{
 
1508
  if (mIsDone || !mCurNode) 
 
1509
    return;
 
1510
 
 
1511
  if (mCurNode == mLast) 
 
1512
  {
 
1513
    mIsDone = PR_TRUE;
 
1514
    return;
 
1515
  }
 
1516
 
 
1517
  nsIContent *nextNode = GetNextSibling(mCurNode, nsnull);
 
1518
  NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
 
1519
 
 
1520
/*
 
1521
  nextNode = GetDeepFirstChild(nextNode);
 
1522
  return GetTopAncestorInRange(nextNode, address_of(mCurNode));
 
1523
*/
 
1524
  PRInt32 i = mEndNodes.IndexOf(nextNode);
 
1525
  while (i != -1)
 
1526
  {
 
1527
    // as long as we are finding ancestors of the endpoint of the range,
 
1528
    // dive down into their children
 
1529
    nextNode = nextNode->GetChildAt(0);
 
1530
    NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
 
1531
 
 
1532
    // should be impossible to get a null pointer.  If we went all the way
 
1533
    // down the child chain to the bottom without finding an interior node, 
 
1534
    // then the previous node should have been the last, which was
 
1535
    // was tested at top of routine.
 
1536
    i = mEndNodes.IndexOf(nextNode);
 
1537
  }
 
1538
 
 
1539
  mCurNode = nextNode;
 
1540
 
 
1541
  // This shouldn't be needed, but since our selection code can put us
 
1542
  // in a situation where mLast is in generated content, we need this
 
1543
  // to stop the iterator when we've walked past past the last node!
 
1544
  mIsDone = mCurNode == nsnull;
 
1545
 
 
1546
  return;
 
1547
}
 
1548
 
 
1549
 
 
1550
void
 
1551
nsContentSubtreeIterator::Prev()
 
1552
{
 
1553
  // Prev should be optimized to use the mStartNodes, just as Next
 
1554
  // uses mEndNodes.
 
1555
  if (mIsDone || !mCurNode) 
 
1556
    return;
 
1557
 
 
1558
  if (mCurNode == mFirst) 
 
1559
  {
 
1560
    mIsDone = PR_TRUE;
 
1561
    return;
 
1562
  }
 
1563
 
 
1564
  nsIContent *prevNode = PrevNode(GetDeepFirstChild(mCurNode, nsnull), nsnull);
 
1565
 
 
1566
  prevNode = GetDeepLastChild(prevNode, nsnull);
 
1567
  
 
1568
  GetTopAncestorInRange(prevNode, address_of(mCurNode));
 
1569
 
 
1570
  // This shouldn't be needed, but since our selection code can put us
 
1571
  // in a situation where mFirst is in generated content, we need this
 
1572
  // to stop the iterator when we've walked past past the first node!
 
1573
  mIsDone = mCurNode == nsnull;
 
1574
}
 
1575
 
 
1576
 
 
1577
nsresult
 
1578
nsContentSubtreeIterator::PositionAt(nsIContent* aCurNode)
 
1579
{
 
1580
  NS_ERROR("Not implemented!");
 
1581
 
 
1582
  return NS_ERROR_NOT_IMPLEMENTED;
 
1583
}
 
1584
 
 
1585
/****************************************************************
 
1586
 * nsContentSubtreeIterator helper routines
 
1587
 ****************************************************************/
 
1588
 
 
1589
nsresult
 
1590
nsContentSubtreeIterator::GetTopAncestorInRange(nsIContent *aNode,
 
1591
                                                nsCOMPtr<nsIContent> *outAnestor)
 
1592
{
 
1593
  if (!aNode) 
 
1594
    return NS_ERROR_NULL_POINTER;
 
1595
  if (!outAnestor) 
 
1596
    return NS_ERROR_NULL_POINTER;
 
1597
  
 
1598
  
 
1599
  // sanity check: aNode is itself in the range
 
1600
  PRBool nodeBefore, nodeAfter;
 
1601
  if (NS_FAILED(nsRange::CompareNodeToRange(aNode, mRange, &nodeBefore,
 
1602
                                            &nodeAfter)))
 
1603
    return NS_ERROR_FAILURE;
 
1604
 
 
1605
  if (nodeBefore || nodeAfter)
 
1606
    return NS_ERROR_FAILURE;
 
1607
  
 
1608
  nsCOMPtr<nsIContent> parent, tmp;
 
1609
  while (aNode)
 
1610
  {
 
1611
    parent = aNode->GetParent();
 
1612
    if (!parent)
 
1613
    {
 
1614
      if (tmp)
 
1615
      {
 
1616
        *outAnestor = tmp;
 
1617
        return NS_OK;
 
1618
      }
 
1619
      else return NS_ERROR_FAILURE;
 
1620
    }
 
1621
    if (NS_FAILED(nsRange::CompareNodeToRange(parent, mRange, &nodeBefore,
 
1622
                                              &nodeAfter)))
 
1623
      return NS_ERROR_FAILURE;
 
1624
 
 
1625
    if (nodeBefore || nodeAfter)
 
1626
    {
 
1627
      *outAnestor = aNode;
 
1628
      return NS_OK;
 
1629
    }
 
1630
    tmp = aNode;
 
1631
    aNode = parent;
 
1632
  }
 
1633
  return NS_ERROR_FAILURE;
 
1634
}
 
1635