Back to index

lightning-sunbird  0.9+nobinonly
nsContentIterator.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Pierre Phaneuf <pp@ludusdesign.com>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either of the GNU General Public License Version 2 or later (the "GPL"),
00027  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 /*
00040  * nsContentIterator.cpp: Implementation of the nsContentIterator object.
00041  * This ite
00042  */
00043 
00044 #include "nsISupports.h"
00045 #include "nsIDOMNodeList.h"
00046 #include "nsIContentIterator.h"
00047 #include "nsRange.h"
00048 #include "nsIContent.h"
00049 #include "nsIDOMText.h"
00050 #include "nsISupportsArray.h"
00051 #include "nsCOMPtr.h"
00052 #include "nsPresContext.h"
00053 #include "nsIComponentManager.h"
00054 #include "nsContentCID.h"
00055 #include "nsLayoutCID.h"
00056 #include "nsVoidArray.h"
00057 #include "nsContentUtils.h"
00058 
00059 static NS_DEFINE_IID(kISupportsIID, NS_ISUPPORTS_IID);
00060 
00061 // couple of utility static functs
00062 
00064 // GetNumChildren: returns the number of things inside aNode. 
00065 //
00066 static PRUint32
00067 GetNumChildren(nsIDOMNode *aNode) 
00068 {
00069   if (!aNode)
00070     return 0;
00071 
00072   PRUint32 numChildren = 0;
00073   PRBool hasChildNodes;
00074   aNode->HasChildNodes(&hasChildNodes);
00075   if (hasChildNodes)
00076   {
00077     nsCOMPtr<nsIContent> content(do_QueryInterface(aNode));
00078 
00079     if (content)
00080       return content->GetChildCount();
00081 
00082     nsCOMPtr<nsIDOMNodeList>nodeList;
00083     aNode->GetChildNodes(getter_AddRefs(nodeList));
00084     if (nodeList) 
00085       nodeList->GetLength(&numChildren);
00086   }
00087 
00088   return numChildren;
00089 }
00090 
00092 // GetChildAt: returns the node at this position index in the parent
00093 //
00094 static nsCOMPtr<nsIDOMNode> 
00095 GetChildAt(nsIDOMNode *aParent, PRInt32 aOffset)
00096 {
00097   nsCOMPtr<nsIDOMNode> resultNode;
00098 
00099   if (!aParent) 
00100     return resultNode;
00101 
00102   nsCOMPtr<nsIContent> content(do_QueryInterface(aParent));
00103 
00104   if (content) {
00105     resultNode = do_QueryInterface(content->GetChildAt(aOffset));
00106   } else if (aParent) {
00107     PRBool hasChildNodes;
00108     aParent->HasChildNodes(&hasChildNodes);
00109     if (hasChildNodes)
00110     {
00111       nsCOMPtr<nsIDOMNodeList>nodeList;
00112       aParent->GetChildNodes(getter_AddRefs(nodeList));
00113       if (nodeList) 
00114         nodeList->Item(aOffset, getter_AddRefs(resultNode));
00115     }
00116   }
00117   
00118   return resultNode;
00119 }
00120   
00122 // ContentHasChildren: returns true if the content has children
00123 //
00124 static inline PRBool
00125 ContentHasChildren(nsIContent *aContent)
00126 {
00127   return aContent->GetChildCount() > 0;
00128 }
00129 
00131 // ContentToParentOffset: returns the content node's parent and offset.
00132 //
00133 
00134 static void
00135 ContentToParentOffset(nsIContent *aContent, nsIDOMNode **aParent,
00136                       PRInt32 *aOffset)
00137 {
00138   *aParent = nsnull;
00139   *aOffset  = 0;
00140 
00141   nsIContent* parent = aContent->GetParent();
00142 
00143   if (!parent)
00144     return;
00145 
00146   *aOffset = parent->IndexOf(aContent);
00147 
00148   CallQueryInterface(parent, aParent);
00149 }
00150 
00152 // ContentIsInTraversalRange: returns true if content is visited during
00153 // the traversal of the range in the specified mode.
00154 //
00155 static PRBool
00156 ContentIsInTraversalRange(nsIContent *aContent,   PRBool aIsPreMode,
00157                           nsIDOMNode *aStartNode, PRInt32 aStartOffset,
00158                           nsIDOMNode *aEndNode,   PRInt32 aEndOffset)
00159 {
00160   if (!aStartNode || !aEndNode || !aContent)
00161     return PR_FALSE;
00162 
00163   nsCOMPtr<nsIDOMCharacterData> cData(do_QueryInterface(aContent));
00164 
00165   if (cData)
00166   {
00167     // If a chardata node contains an end point of the traversal range,
00168     // it is always in the traversal range.
00169 
00170     nsCOMPtr<nsIContent> startContent(do_QueryInterface(aStartNode));
00171     nsCOMPtr<nsIContent> endContent(do_QueryInterface(aEndNode));
00172 
00173     if (aContent == startContent || aContent == endContent)
00174       return PR_TRUE;
00175   }
00176 
00177   nsCOMPtr<nsIDOMNode> parentNode;
00178   PRInt32 indx = 0;
00179 
00180   ContentToParentOffset(aContent, getter_AddRefs(parentNode), &indx);
00181 
00182   if (!parentNode)
00183     return PR_FALSE;
00184 
00185   if (!aIsPreMode)
00186     ++indx;
00187 
00188   return (nsRange::ComparePoints(aStartNode, aStartOffset,
00189                                  parentNode, indx) <= 0) &&
00190          (nsRange::ComparePoints(aEndNode, aEndOffset, parentNode, indx) >= 0);
00191 }
00192 
00193 
00194 
00195 /*
00196  *  A simple iterator class for traversing the content in "close tag" order
00197  */
00198 class nsContentIterator : public nsIContentIterator //, public nsIEnumerator
00199 {
00200 public:
00201   NS_DECL_ISUPPORTS
00202 
00203   nsContentIterator();
00204   virtual ~nsContentIterator();
00205 
00206   // nsIContentIterator interface methods ------------------------------
00207 
00208   virtual nsresult Init(nsIContent* aRoot);
00209 
00210   virtual nsresult Init(nsIDOMRange* aRange);
00211 
00212   virtual void First();
00213 
00214   virtual void Last();
00215   
00216   virtual void Next();
00217 
00218   virtual void Prev();
00219 
00220   virtual nsIContent *GetCurrentNode();
00221 
00222   virtual PRBool IsDone();
00223 
00224   virtual nsresult PositionAt(nsIContent* aCurNode);
00225 
00226   // nsIEnumertor interface methods ------------------------------
00227   
00228   //NS_IMETHOD CurrentItem(nsISupports **aItem);
00229 
00230 protected:
00231 
00232   nsIContent *GetDeepFirstChild(nsIContent *aRoot, nsVoidArray *aIndexes);
00233   nsIContent *GetDeepLastChild(nsIContent *aRoot, nsVoidArray *aIndexes);
00234 
00235   nsIContent *GetNextSibling(nsIContent *aNode, nsVoidArray *aIndexes);
00236   nsIContent *GetPrevSibling(nsIContent *aNode, nsVoidArray *aIndexes);
00237 
00238   nsIContent *NextNode(nsIContent *aNode, nsVoidArray *aIndexes);
00239   nsIContent *PrevNode(nsIContent *aNode, nsVoidArray *aIndexes);
00240 
00241   // WARNING: This function is expensive
00242   nsresult RebuildIndexStack();
00243 
00244   void MakeEmpty();
00245   
00246   nsCOMPtr<nsIContent> mCurNode;
00247   nsCOMPtr<nsIContent> mFirst;
00248   nsCOMPtr<nsIContent> mLast;
00249   nsCOMPtr<nsIContent> mCommonParent;
00250 
00251   // used by nsContentIterator to cache indices
00252   nsAutoVoidArray mIndexes;
00253 
00254   // used by nsSubtreeIterator to cache indices.  Why put them in the base class?
00255   // Because otherwise I have to duplicate the routines GetNextSibling etc across both classes,
00256   // with slight variations for caching.  Or alternately, create a base class for the cache
00257   // itself and have all the cache manipulation go through a vptr.
00258   // I think this is the best space and speed combo, even though it's ugly.
00259   PRInt32 mCachedIndex;
00260   // another note about mCachedIndex: why should the subtree iterator use a trivial cached index
00261   // instead of the mre robust array of indicies (which is what the basic content iterator uses)?
00262   // The reason is that subtree iterators do not do much transitioning between parents and children.
00263   // They tend to stay at the same level.  In fact, you can prove (though I won't attempt it here)
00264   // that they change levels at most n+m times, where n is the height of the parent heirarchy from the 
00265   // range start to the common ancestor, and m is the the height of the parent heirarchy from the 
00266   // range end to the common ancestor.  If we used the index array, we would pay the price up front
00267   // for n, and then pay the cost for m on the fly later on.  With the simple cache, we only "pay
00268   // as we go".  Either way, we call IndexOf() once for each change of level in the heirarchy.
00269   // Since a trivial index is much simpler, we use it for the subtree iterator.
00270   
00271   PRBool mIsDone;
00272   PRBool mPre;
00273   
00274 private:
00275 
00276   // no copy's or assigns  FIX ME
00277   nsContentIterator(const nsContentIterator&);
00278   nsContentIterator& operator=(const nsContentIterator&);
00279 
00280 };
00281 
00282 
00283 /*
00284  *  A simple iterator class for traversing the content in "open tag" order
00285  */
00286 
00287 class nsPreContentIterator : public nsContentIterator
00288 {
00289 public:
00290   nsPreContentIterator() { mPre = PR_TRUE; }
00291 };
00292 
00293 
00294 
00295 /******************************************************
00296  * repository cruft
00297  ******************************************************/
00298 
00299 nsresult NS_NewContentIterator(nsIContentIterator** aInstancePtrResult)
00300 {
00301   nsContentIterator * iter = new nsContentIterator();
00302   if (!iter) {
00303     return NS_ERROR_OUT_OF_MEMORY;
00304   }
00305 
00306   NS_ADDREF(*aInstancePtrResult = iter);
00307 
00308   return NS_OK;
00309 }
00310 
00311 
00312 nsresult NS_NewPreContentIterator(nsIContentIterator** aInstancePtrResult)
00313 {
00314   nsContentIterator * iter = new nsPreContentIterator();
00315   if (!iter) {
00316     return NS_ERROR_OUT_OF_MEMORY;
00317   }
00318 
00319   NS_ADDREF(*aInstancePtrResult = iter);
00320 
00321   return NS_OK;
00322 }
00323 
00324 
00325 /******************************************************
00326  * XPCOM cruft
00327  ******************************************************/
00328  
00329 NS_IMPL_ISUPPORTS1(nsContentIterator, nsIContentIterator)
00330 
00331 
00332 /******************************************************
00333  * constructor/destructor
00334  ******************************************************/
00335 
00336 nsContentIterator::nsContentIterator() :
00337   // don't need to explicitly initialize |nsCOMPtr|s, they will automatically be NULL
00338   mCachedIndex(0), mIsDone(PR_FALSE), mPre(PR_FALSE)
00339 {
00340 }
00341 
00342 
00343 nsContentIterator::~nsContentIterator()
00344 {
00345 }
00346 
00347 
00348 /******************************************************
00349  * Init routines
00350  ******************************************************/
00351 
00352 
00353 nsresult
00354 nsContentIterator::Init(nsIContent* aRoot)
00355 {
00356   if (!aRoot) 
00357     return NS_ERROR_NULL_POINTER; 
00358   mIsDone = PR_FALSE;
00359   mIndexes.Clear();
00360   
00361   if (mPre)
00362   {
00363     mFirst = aRoot;
00364     mLast  = GetDeepLastChild(aRoot, nsnull);
00365   }
00366   else
00367   {
00368     mFirst = GetDeepFirstChild(aRoot, nsnull); 
00369     mLast  = aRoot;
00370   }
00371 
00372   mCommonParent = aRoot;
00373   mCurNode = mFirst;
00374   RebuildIndexStack();
00375   return NS_OK;
00376 }
00377 
00378 
00379 nsresult
00380 nsContentIterator::Init(nsIDOMRange* aRange)
00381 {
00382   if (!aRange) 
00383     return NS_ERROR_NULL_POINTER; 
00384 
00385   nsCOMPtr<nsIDOMNode> dN;
00386 
00387   nsCOMPtr<nsIContent> startCon;
00388   nsCOMPtr<nsIDOMNode> startDOM;
00389   nsCOMPtr<nsIContent> endCon;
00390   nsCOMPtr<nsIDOMNode> endDOM;
00391   PRInt32 startIndx;
00392   PRInt32 endIndx;
00393   
00394   mIsDone = PR_FALSE;
00395 
00396   // get common content parent
00397   if (NS_FAILED(aRange->GetCommonAncestorContainer(getter_AddRefs(dN))) || !dN)
00398     return NS_ERROR_FAILURE;
00399   mCommonParent = do_QueryInterface(dN);
00400 
00401   // get the start node and offset, convert to nsIContent
00402   aRange->GetStartContainer(getter_AddRefs(startDOM));
00403   if (!startDOM) 
00404     return NS_ERROR_ILLEGAL_VALUE;
00405   startCon = do_QueryInterface(startDOM);
00406   if (!startCon) 
00407     return NS_ERROR_FAILURE;
00408   
00409   aRange->GetStartOffset(&startIndx);
00410   
00411   // get the end node and offset, convert to nsIContent
00412   aRange->GetEndContainer(getter_AddRefs(endDOM));
00413   if (!endDOM) 
00414     return NS_ERROR_ILLEGAL_VALUE;
00415   endCon = do_QueryInterface(endDOM);
00416   if (!endCon) 
00417     return NS_ERROR_FAILURE;
00418 
00419   aRange->GetEndOffset(&endIndx);
00420   
00421   nsCOMPtr<nsIDOMCharacterData> cData(do_QueryInterface(startCon));
00422 
00423   // short circuit when start node == end node
00424   if (startDOM == endDOM)
00425   {
00426     // Check to see if we have a collapsed range, if so,
00427     // there is nothing to iterate over.
00428     //
00429     // XXX: CharacterDataNodes (text nodes) are currently an exception,
00430     //      since we always want to be able to iterate text nodes at
00431     //      the end points of a range.
00432 
00433     if (!cData && startIndx == endIndx)
00434     {
00435       MakeEmpty();
00436       return NS_OK;
00437     }
00438 
00439     if (cData)
00440     {
00441       // It's a textnode.
00442 
00443       mFirst   = startCon;
00444       mLast    = startCon;
00445       mCurNode = startCon;
00446 
00447       RebuildIndexStack();
00448       return NS_OK;
00449     }
00450   }
00451   
00452   // Find first node in range.
00453 
00454   nsIContent *cChild = nsnull;
00455 
00456   if (!cData && ContentHasChildren(startCon))
00457     cChild = startCon->GetChildAt(startIndx);
00458 
00459   if (!cChild) // no children, must be a text node
00460   {
00461     if (mPre)
00462     {
00463       // XXX: In the future, if start offset is after the last
00464       //      character in the cdata node, should we set mFirst to
00465       //      the next sibling?
00466 
00467       if (!cData)
00468       {
00469         mFirst = GetNextSibling(startCon, nsnull);
00470 
00471         // Does mFirst node really intersect the range?
00472         // The range could be 'degenerate', ie not collapsed 
00473         // but still contain no content.
00474   
00475         if (mFirst && !ContentIsInTraversalRange(mFirst, mPre, startDOM, startIndx, endDOM, endIndx))
00476           mFirst = nsnull;
00477       }
00478       else
00479         mFirst = startCon;
00480     }
00481     else // post-order
00482       mFirst = startCon;
00483   }
00484   else
00485   {
00486     if (mPre)
00487       mFirst = cChild;
00488     else // post-order
00489     {
00490       mFirst = GetDeepFirstChild(cChild, nsnull);
00491 
00492       // Does mFirst node really intersect the range?
00493       // The range could be 'degenerate', ie not collapsed 
00494       // but still contain no content.
00495   
00496       if (mFirst && !ContentIsInTraversalRange(mFirst, mPre, startDOM, startIndx, endDOM, endIndx))
00497         mFirst = nsnull;
00498     }
00499   }
00500 
00501 
00502   // Find last node in range.
00503 
00504   cData = do_QueryInterface(endCon);
00505 
00506   if (cData || !ContentHasChildren(endCon) || endIndx == 0)
00507   {
00508     if (mPre)
00509       mLast = endCon;
00510     else // post-order
00511     {
00512       // XXX: In the future, if end offset is before the first
00513       //      character in the cdata node, should we set mLast to
00514       //      the prev sibling?
00515 
00516       if (!cData)
00517       {
00518         mLast = GetPrevSibling(endCon, nsnull);
00519 
00520         if (!ContentIsInTraversalRange(mLast, mPre, startDOM, startIndx, endDOM, endIndx))
00521           mLast = nsnull;
00522       }
00523       else
00524         mLast = endCon;
00525     }
00526   }
00527   else
00528   {
00529     PRInt32 indx = endIndx;
00530 
00531     cChild = endCon->GetChildAt(--indx);
00532 
00533     if (!cChild)  // No child at offset!
00534     {
00535       NS_NOTREACHED("nsContentIterator::nsContentIterator");
00536       return NS_ERROR_FAILURE; 
00537     }
00538 
00539     if (mPre)
00540     {
00541       mLast  = GetDeepLastChild(cChild, nsnull);
00542 
00543       if (!ContentIsInTraversalRange(mLast, mPre, startDOM, startIndx, endDOM, endIndx))
00544         mLast = nsnull;
00545     }
00546     else // post-order
00547       mLast = cChild;
00548   }
00549 
00550   // If either first or last is null, they both
00551   // have to be null!
00552 
00553   if (!mFirst || !mLast)
00554   {
00555     mFirst = nsnull;
00556     mLast  = nsnull;
00557   }
00558   
00559   mCurNode = mFirst;
00560   mIsDone  = !mCurNode;
00561 
00562   if (!mCurNode)
00563     mIndexes.Clear();
00564   else
00565     RebuildIndexStack();
00566 
00567   return NS_OK;
00568 }
00569 
00570 
00571 /******************************************************
00572  * Helper routines
00573  ******************************************************/
00574 // WARNING: This function is expensive
00575 nsresult nsContentIterator::RebuildIndexStack()
00576 {
00577   // Make sure we start at the right indexes on the stack!  Build array up
00578   // to common parent of start and end.  Perhaps it's too many entries, but
00579   // thats far better than too few.
00580   nsIContent* parent;
00581   nsIContent* current;
00582 
00583   mIndexes.Clear();
00584   current = mCurNode;
00585   if (!current) {
00586     return NS_OK;
00587   }
00588 
00589   while (current != mCommonParent)
00590   {
00591     parent = current->GetParent();
00592     
00593     if (!parent)
00594       return NS_ERROR_FAILURE;
00595   
00596     mIndexes.InsertElementAt(NS_INT32_TO_PTR(parent->IndexOf(current)), 0);
00597 
00598     current = parent;
00599   }
00600   return NS_OK;
00601 }
00602 
00603 void
00604 nsContentIterator::MakeEmpty()
00605 {
00606   mCurNode      = nsnull;
00607   mFirst        = nsnull;
00608   mLast         = nsnull;
00609   mCommonParent = nsnull;
00610   mIsDone       = PR_TRUE;
00611   mIndexes.Clear();
00612 }
00613 
00614 nsIContent *
00615 nsContentIterator::GetDeepFirstChild(nsIContent *aRoot, nsVoidArray *aIndexes)
00616 {
00617   if (!aRoot) {
00618     return nsnull;
00619   }
00620 
00621   nsIContent *cN = aRoot;
00622   nsIContent *cChild = cN->GetChildAt(0);
00623 
00624   while (cChild)
00625   {
00626     if (aIndexes)
00627     {
00628       // Add this node to the stack of indexes
00629       aIndexes->AppendElement(NS_INT32_TO_PTR(0));
00630     }
00631     cN = cChild;
00632     cChild = cN->GetChildAt(0);
00633   }
00634 
00635   return cN;
00636 }
00637 
00638 nsIContent *
00639 nsContentIterator::GetDeepLastChild(nsIContent *aRoot, nsVoidArray *aIndexes)
00640 {
00641   if (!aRoot) {
00642     return nsnull;
00643   }
00644 
00645   nsIContent *deepLastChild = aRoot;
00646 
00647   nsIContent *cN = aRoot;
00648   PRInt32 numChildren = cN->GetChildCount();
00649 
00650   while (numChildren)
00651   {
00652     nsIContent *cChild = cN->GetChildAt(--numChildren);
00653 
00654     if (aIndexes)
00655     {
00656       // Add this node to the stack of indexes
00657       aIndexes->AppendElement(NS_INT32_TO_PTR(numChildren));
00658     }
00659     numChildren = cChild->GetChildCount();
00660     cN = cChild;
00661 
00662     deepLastChild = cN;
00663   }
00664 
00665   return deepLastChild;
00666 }
00667 
00668 // Get the next sibling, or parents next sibling, or grandpa's next sibling...
00669 nsIContent *
00670 nsContentIterator::GetNextSibling(nsIContent *aNode, 
00671                                   nsVoidArray *aIndexes)
00672 {
00673   if (!aNode) 
00674     return nsnull;
00675 
00676   nsIContent *parent = aNode->GetParent();
00677   if (!parent)
00678     return nsnull;
00679 
00680   PRInt32 indx;
00681 
00682   if (aIndexes)
00683   {
00684     NS_ASSERTION(aIndexes->Count() > 0, "ContentIterator stack underflow");
00685     // use the last entry on the Indexes array for the current index
00686     indx = NS_PTR_TO_INT32((*aIndexes)[aIndexes->Count()-1]);
00687   }
00688   else
00689     indx = mCachedIndex;
00690 
00691   // reverify that the index of the current node hasn't changed.
00692   // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
00693   // ignore result this time - the index may now be out of range.
00694   nsIContent *sib = parent->GetChildAt(indx);
00695   if (sib != aNode)
00696   {
00697     // someone changed our index - find the new index the painful way
00698     indx = parent->IndexOf(aNode);
00699   }
00700 
00701   // indx is now canonically correct
00702   if ((sib = parent->GetChildAt(++indx)))
00703   {
00704     // update index cache
00705     if (aIndexes)
00706     {
00707       aIndexes->ReplaceElementAt(NS_INT32_TO_PTR(indx),aIndexes->Count()-1);
00708     }
00709     else mCachedIndex = indx;
00710   }
00711   else
00712   {
00713     if (parent != mCommonParent)
00714     {
00715       if (aIndexes)
00716       {
00717         // pop node off the stack, go up one level and return parent or fail.
00718         // Don't leave the index empty, especially if we're
00719         // returning NULL.  This confuses other parts of the code.
00720         if (aIndexes->Count() > 1)
00721           aIndexes->RemoveElementAt(aIndexes->Count()-1);
00722       }
00723     }
00724 
00725     // ok to leave cache out of date here if parent == mCommonParent?
00726     sib = GetNextSibling(parent, aIndexes);
00727   }
00728   
00729   return sib;
00730 }
00731 
00732 // Get the prev sibling, or parents prev sibling, or grandpa's prev sibling...
00733 nsIContent *
00734 nsContentIterator::GetPrevSibling(nsIContent *aNode, 
00735                                   nsVoidArray *aIndexes)
00736 {
00737   if (!aNode)
00738     return nsnull;
00739 
00740   nsIContent *parent = aNode->GetParent();
00741   if (!parent)
00742     return nsnull;
00743 
00744   PRInt32 indx;
00745 
00746   if (aIndexes)
00747   {
00748     NS_ASSERTION(aIndexes->Count() > 0, "ContentIterator stack underflow");
00749     // use the last entry on the Indexes array for the current index
00750     indx = NS_PTR_TO_INT32((*aIndexes)[aIndexes->Count()-1]);
00751   }
00752   else
00753     indx = mCachedIndex;
00754 
00755   // reverify that the index of the current node hasn't changed
00756   // ignore result this time - the index may now be out of range.
00757   nsIContent *sib = parent->GetChildAt(indx);
00758   if (sib != aNode)
00759   {
00760     // someone changed our index - find the new index the painful way
00761     indx = parent->IndexOf(aNode);
00762   }
00763 
00764   // indx is now canonically correct
00765   if (indx > 0 && (sib = parent->GetChildAt(--indx)))
00766   {
00767     // update index cache
00768     if (aIndexes)
00769     {
00770       aIndexes->ReplaceElementAt(NS_INT32_TO_PTR(indx),aIndexes->Count()-1);
00771     }
00772     else mCachedIndex = indx;
00773   }
00774   else if (parent != mCommonParent)
00775   {
00776     if (aIndexes)
00777     {
00778       // pop node off the stack, go up one level and try again.
00779       aIndexes->RemoveElementAt(aIndexes->Count()-1);
00780     }
00781     return GetPrevSibling(parent, aIndexes);
00782   }
00783 
00784   return sib;
00785 }
00786 
00787 nsIContent *
00788 nsContentIterator::NextNode(nsIContent *aNode, nsVoidArray *aIndexes)
00789 {
00790   nsIContent *cN = aNode;
00791   nsIContent *nextNode = nsnull;
00792 
00793   if (mPre)  // if we are a Pre-order iterator, use pre-order
00794   {
00795     // if it has children then next node is first child
00796     if (ContentHasChildren(cN))
00797     {
00798       nsIContent *cFirstChild = cN->GetChildAt(0);
00799 
00800       // update cache
00801       if (aIndexes)
00802       {
00803         // push an entry on the index stack
00804         aIndexes->AppendElement(NS_INT32_TO_PTR(0));
00805       }
00806       else mCachedIndex = 0;
00807       
00808       return cFirstChild;
00809     }
00810 
00811     // else next sibling is next
00812     nextNode = GetNextSibling(cN, aIndexes);
00813   }
00814   else  // post-order
00815   {
00816     nsIContent *parent = cN->GetParent();
00817     nsIContent *cSibling = nsnull;
00818     PRInt32 indx;
00819 
00820     // get the cached index
00821     if (aIndexes)
00822     {
00823       NS_ASSERTION(aIndexes->Count() > 0, "ContentIterator stack underflow");
00824       // use the last entry on the Indexes array for the current index
00825       indx = NS_PTR_TO_INT32((*aIndexes)[aIndexes->Count()-1]);
00826     }
00827     else indx = mCachedIndex;
00828 
00829     // reverify that the index of the current node hasn't changed.
00830     // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
00831     // ignore result this time - the index may now be out of range.
00832     if (indx >= 0)
00833       cSibling = parent->GetChildAt(indx);
00834     if (cSibling != cN)
00835     {
00836       // someone changed our index - find the new index the painful way
00837       indx = parent->IndexOf(cN);
00838     }
00839 
00840     // indx is now canonically correct
00841     cSibling = parent->GetChildAt(++indx);
00842     if (cSibling)
00843     {
00844       // update cache
00845       if (aIndexes)
00846       {
00847         // replace an entry on the index stack
00848         aIndexes->ReplaceElementAt(NS_INT32_TO_PTR(indx),aIndexes->Count()-1);
00849       }
00850       else mCachedIndex = indx;
00851       
00852       // next node is siblings "deep left" child
00853       return GetDeepFirstChild(cSibling, aIndexes); 
00854     }
00855   
00856     // else it's the parent
00857     // update cache
00858     if (aIndexes)
00859     {
00860       // pop an entry off the index stack
00861       // Don't leave the index empty, especially if we're
00862       // returning NULL.  This confuses other parts of the code.
00863       if (aIndexes->Count() > 1)
00864         aIndexes->RemoveElementAt(aIndexes->Count()-1);
00865     }
00866     else mCachedIndex = 0;   // this might be wrong, but we are better off guessing
00867     nextNode = parent;
00868   }
00869 
00870   return nextNode;
00871 }
00872 
00873 nsIContent *
00874 nsContentIterator::PrevNode(nsIContent *aNode, nsVoidArray *aIndexes)
00875 {
00876   nsIContent *prevNode = nsnull;
00877   nsIContent *cN = aNode;
00878    
00879   if (mPre)  // if we are a Pre-order iterator, use pre-order
00880   {
00881     nsIContent *parent = cN->GetParent();
00882     nsIContent *cSibling = nsnull;
00883     PRInt32 indx;
00884 
00885     // get the cached index
00886     if (aIndexes)
00887     {
00888       NS_ASSERTION(aIndexes->Count() > 0, "ContentIterator stack underflow");
00889       // use the last entry on the Indexes array for the current index
00890       indx = NS_PTR_TO_INT32((*aIndexes)[aIndexes->Count()-1]);
00891     }
00892     else indx = mCachedIndex;
00893 
00894     // reverify that the index of the current node hasn't changed.
00895     // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
00896     // ignore result this time - the index may now be out of range.
00897     if (indx >= 0)
00898       cSibling = parent->GetChildAt(indx);
00899 
00900     if (cSibling != cN)
00901     {
00902       // someone changed our index - find the new index the painful way
00903       indx = parent->IndexOf(cN);
00904     }
00905 
00906     // indx is now canonically correct
00907     if (indx && (cSibling = parent->GetChildAt(--indx)))
00908     {
00909       // update cache
00910       if (aIndexes)
00911       {
00912         // replace an entry on the index stack
00913         aIndexes->ReplaceElementAt(NS_INT32_TO_PTR(indx),aIndexes->Count()-1);
00914       }
00915       else mCachedIndex = indx;
00916       
00917       // prev node is siblings "deep right" child
00918       return GetDeepLastChild(cSibling, aIndexes); 
00919     }
00920   
00921     // else it's the parent
00922     // update cache
00923     if (aIndexes)
00924     {
00925       // pop an entry off the index stack
00926       aIndexes->RemoveElementAt(aIndexes->Count()-1);
00927     }
00928     else mCachedIndex = 0;   // this might be wrong, but we are better off guessing
00929     prevNode = parent;
00930   }
00931   else  // post-order
00932   {
00933     PRInt32 numChildren = cN->GetChildCount();
00934   
00935     // if it has children then prev node is last child
00936     if (numChildren)
00937     {
00938       nsIContent *cLastChild = cN->GetChildAt(--numChildren);
00939 
00940       // update cache
00941       if (aIndexes)
00942       {
00943         // push an entry on the index stack
00944         aIndexes->AppendElement(NS_INT32_TO_PTR(numChildren));
00945       }
00946       else mCachedIndex = numChildren;
00947       
00948       return cLastChild;
00949     }
00950 
00951     // else prev sibling is previous
00952     prevNode = GetPrevSibling(cN, aIndexes);
00953   }
00954 
00955   return prevNode;
00956 }
00957 
00958 /******************************************************
00959  * ContentIterator routines
00960  ******************************************************/
00961 
00962 void
00963 nsContentIterator::First()
00964 {
00965   NS_ASSERTION(mFirst, "No first node!");
00966 
00967   if (mFirst) {
00968 #ifdef DEBUG
00969     nsresult rv =
00970 #endif
00971     PositionAt(mFirst);
00972 
00973     NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
00974   }
00975 
00976   mIsDone = mFirst == nsnull;
00977 }
00978 
00979 
00980 void
00981 nsContentIterator::Last()
00982 {
00983   NS_ASSERTION(mLast, "No last node!");
00984 
00985   if (mLast) {
00986 #ifdef DEBUG
00987     nsresult rv =
00988 #endif
00989     PositionAt(mLast);
00990 
00991     NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
00992   }
00993 
00994   mIsDone = mLast == nsnull;
00995 }
00996 
00997 
00998 void
00999 nsContentIterator::Next()
01000 {
01001   if (mIsDone || !mCurNode) 
01002     return;
01003 
01004   if (mCurNode == mLast) 
01005   {
01006     mIsDone = PR_TRUE;
01007     return;
01008   }
01009 
01010   mCurNode = NextNode(mCurNode, &mIndexes);
01011 }
01012 
01013 
01014 void
01015 nsContentIterator::Prev()
01016 {
01017   if (mIsDone || !mCurNode) 
01018     return;
01019 
01020   if (mCurNode == mFirst) 
01021   {
01022     mIsDone = PR_TRUE;
01023     return;
01024   }
01025 
01026   mCurNode = PrevNode(mCurNode, &mIndexes);
01027 }
01028 
01029 
01030 PRBool
01031 nsContentIterator::IsDone()
01032 {
01033   return mIsDone;
01034 }
01035 
01036 
01037 // Keeping arrays of indexes for the stack of nodes makes PositionAt
01038 // interesting...
01039 nsresult
01040 nsContentIterator::PositionAt(nsIContent* aCurNode)
01041 {
01042   if (!aCurNode)
01043     return NS_ERROR_NULL_POINTER;
01044 
01045   nsIContent *newCurNode = aCurNode;
01046   nsIContent *tempNode = mCurNode;
01047 
01048   mCurNode = aCurNode;
01049   // take an early out if this doesn't actually change the position
01050   if (mCurNode == tempNode)
01051   {
01052     mIsDone = PR_FALSE;  // paranoia
01053     return NS_OK;
01054   }
01055 
01056   // Check to see if the node falls within the traversal range.
01057 
01058   nsCOMPtr<nsIDOMNode> firstNode(do_QueryInterface(mFirst));
01059   nsCOMPtr<nsIDOMNode> lastNode(do_QueryInterface(mLast));
01060   PRInt32 firstOffset=0, lastOffset=0;
01061 
01062   if (firstNode && lastNode)
01063   {
01064     PRUint32 numChildren;
01065 
01066     if (mPre)
01067     {
01068       ContentToParentOffset(mFirst, getter_AddRefs(firstNode), &firstOffset);
01069 
01070       numChildren = GetNumChildren(lastNode);
01071 
01072       if (numChildren)
01073         lastOffset = 0;
01074       else
01075       {
01076         ContentToParentOffset(mLast, getter_AddRefs(lastNode), &lastOffset);
01077         ++lastOffset;
01078       }
01079     }
01080     else
01081     {
01082       numChildren = GetNumChildren(firstNode);
01083 
01084       if (numChildren)
01085         firstOffset = numChildren;
01086       else
01087         ContentToParentOffset(mFirst, getter_AddRefs(firstNode), &firstOffset);
01088 
01089       ContentToParentOffset(mLast, getter_AddRefs(lastNode), &lastOffset);
01090       ++lastOffset;
01091     }
01092   }
01093 
01094   if (!firstNode || !lastNode ||
01095       !ContentIsInTraversalRange(mCurNode, mPre, firstNode, firstOffset,
01096                                  lastNode, lastOffset))
01097   {
01098     mIsDone = PR_TRUE;
01099     return NS_ERROR_FAILURE;
01100   }
01101 
01102   // We can be at ANY node in the sequence.
01103   // Need to regenerate the array of indexes back to the root or common parent!
01104   nsAutoVoidArray      oldParentStack;
01105   nsAutoVoidArray      newIndexes;
01106 
01107   // Get a list of the parents up to the root, then compare the new node
01108   // with entries in that array until we find a match (lowest common
01109   // ancestor).  If no match, use IndexOf, take the parent, and repeat.
01110   // This avoids using IndexOf() N times on possibly large arrays.  We
01111   // still end up doing it a fair bit.  It's better to use Clone() if
01112   // possible.
01113 
01114   // we know the depth we're down (though we may not have started at the
01115   // top).
01116   if (!oldParentStack.SizeTo(mIndexes.Count()+1))
01117     return NS_ERROR_FAILURE;
01118 
01119   // We want to loop mIndexes.Count() + 1 times here, because we want to make
01120   // sure we include mCommonParent in the oldParentStack, for use in the next
01121   // for loop, and mIndexes only has entries for nodes from tempNode up through
01122   // an ancestor of tempNode that's a child of mCommonParent.
01123   for (PRInt32 i = mIndexes.Count()+1; i > 0 && tempNode; i--)
01124   {
01125     // Insert at head since we're walking up
01126     oldParentStack.InsertElementAt(tempNode,0);
01127 
01128     nsIContent *parent = tempNode->GetParent();
01129 
01130     if (!parent)  // this node has no parent, and thus no index
01131       break;
01132 
01133     if (parent == mCurNode)
01134     {
01135       // The position was moved to a parent of the current position. 
01136       // All we need to do is drop some indexes.  Shortcut here.
01137       mIndexes.RemoveElementsAt(mIndexes.Count() - oldParentStack.Count(),
01138                                 oldParentStack.Count());
01139       mIsDone = PR_FALSE;
01140       return NS_OK;
01141     }
01142     tempNode = parent;
01143   }
01144 
01145   // Ok.  We have the array of old parents.  Look for a match.
01146   while (newCurNode)
01147   {
01148     nsIContent *parent = newCurNode->GetParent();
01149 
01150     if (!parent)  // this node has no parent, and thus no index
01151       break;
01152 
01153     PRInt32 indx = parent->IndexOf(newCurNode);
01154 
01155     // insert at the head!
01156     newIndexes.InsertElementAt(NS_INT32_TO_PTR(indx),0);
01157 
01158     // look to see if the parent is in the stack
01159     indx = oldParentStack.IndexOf(parent);
01160     if (indx >= 0)
01161     {
01162       // ok, the parent IS on the old stack!  Rework things.
01163       // we want newIndexes to replace all nodes equal to or below the match
01164       // Note that index oldParentStack.Count()-1 is the last node, which is
01165       // one BELOW the last index in the mIndexes stack.  In other words, we
01166       // want to remove elements starting at index (indx+1).
01167       PRInt32 numToDrop = oldParentStack.Count()-(1+indx);
01168       if (numToDrop > 0)
01169         mIndexes.RemoveElementsAt(mIndexes.Count() - numToDrop,numToDrop);
01170       mIndexes.AppendElements(newIndexes);
01171 
01172       break;
01173     }
01174     newCurNode = parent;
01175   }
01176 
01177   // phew!
01178 
01179   mIsDone = PR_FALSE;
01180   return NS_OK;
01181 }
01182 
01183 
01184 nsIContent *
01185 nsContentIterator::GetCurrentNode()
01186 {
01187   if (mIsDone) {
01188     return nsnull;
01189   }
01190 
01191   NS_ASSERTION(mCurNode, "Null current node in an iterator that's not done!");
01192 
01193   return mCurNode;
01194 }
01195 
01196 
01197 
01198 
01199 
01200 /*====================================================================================*/
01201 /*====================================================================================*/
01202 
01203 
01204 
01205 
01206 
01207 
01208 /******************************************************
01209  * nsContentSubtreeIterator
01210  ******************************************************/
01211 
01212 
01213 /*
01214  *  A simple iterator class for traversing the content in "top subtree" order
01215  */
01216 class nsContentSubtreeIterator : public nsContentIterator 
01217 {
01218 public:
01219   nsContentSubtreeIterator() {};
01220   virtual ~nsContentSubtreeIterator() {};
01221 
01222   // nsContentIterator overrides ------------------------------
01223 
01224   virtual nsresult Init(nsIContent* aRoot);
01225 
01226   virtual nsresult Init(nsIDOMRange* aRange);
01227 
01228   virtual void Next();
01229 
01230   virtual void Prev();
01231 
01232   virtual nsresult PositionAt(nsIContent* aCurNode);
01233 
01234   // Must override these because we don't do PositionAt
01235   virtual void First();
01236 
01237   // Must override these because we don't do PositionAt
01238   virtual void Last();
01239 
01240 protected:
01241 
01242   nsresult GetTopAncestorInRange(nsIContent *aNode,
01243                                  nsCOMPtr<nsIContent> *outAnestor);
01244 
01245   // no copy's or assigns  FIX ME
01246   nsContentSubtreeIterator(const nsContentSubtreeIterator&);
01247   nsContentSubtreeIterator& operator=(const nsContentSubtreeIterator&);
01248 
01249   nsCOMPtr<nsIDOMRange> mRange;
01250   // these arrays all typically are used and have elements
01251 #if 0
01252   nsAutoVoidArray mStartNodes;
01253   nsAutoVoidArray mStartOffsets;
01254 #endif
01255 
01256   nsAutoVoidArray mEndNodes;
01257   nsAutoVoidArray mEndOffsets;
01258 };
01259 
01260 nsresult NS_NewContentSubtreeIterator(nsIContentIterator** aInstancePtrResult);
01261 
01262 
01263 
01264 
01265 /******************************************************
01266  * repository cruft
01267  ******************************************************/
01268 
01269 nsresult NS_NewContentSubtreeIterator(nsIContentIterator** aInstancePtrResult)
01270 {
01271   nsContentIterator * iter = new nsContentSubtreeIterator();
01272   if (!iter) {
01273     return NS_ERROR_OUT_OF_MEMORY;
01274   }
01275 
01276   NS_ADDREF(*aInstancePtrResult = iter);
01277 
01278   return NS_OK;
01279 }
01280 
01281 
01282 
01283 /******************************************************
01284  * Init routines
01285  ******************************************************/
01286 
01287 
01288 nsresult nsContentSubtreeIterator::Init(nsIContent* aRoot)
01289 {
01290   return NS_ERROR_NOT_IMPLEMENTED;
01291 }
01292 
01293 
01294 nsresult nsContentSubtreeIterator::Init(nsIDOMRange* aRange)
01295 {
01296   if (!aRange) 
01297     return NS_ERROR_NULL_POINTER; 
01298 
01299   mIsDone = PR_FALSE;
01300 
01301   mRange = aRange;
01302   
01303   // get the start node and offset, convert to nsIContent
01304   nsCOMPtr<nsIDOMNode> commonParent;
01305   nsCOMPtr<nsIDOMNode> startParent;
01306   nsCOMPtr<nsIDOMNode> endParent;
01307   nsCOMPtr<nsIContent> cStartP;
01308   nsCOMPtr<nsIContent> cEndP;
01309   nsCOMPtr<nsIContent> cN;
01310   nsIContent *firstCandidate = nsnull;
01311   nsIContent *lastCandidate = nsnull;
01312   nsCOMPtr<nsIDOMNode> dChild;
01313   nsCOMPtr<nsIContent> cChild;
01314   PRInt32 indx, startIndx, endIndx;
01315   PRInt32 numChildren;
01316 
01317   // get common content parent
01318   if (NS_FAILED(aRange->GetCommonAncestorContainer(getter_AddRefs(commonParent))) || !commonParent)
01319     return NS_ERROR_FAILURE;
01320   mCommonParent = do_QueryInterface(commonParent);
01321 
01322   // get start content parent
01323   if (NS_FAILED(aRange->GetStartContainer(getter_AddRefs(startParent))) || !startParent)
01324     return NS_ERROR_FAILURE;
01325   cStartP = do_QueryInterface(startParent);
01326   aRange->GetStartOffset(&startIndx);
01327 
01328   // get end content parent
01329   if (NS_FAILED(aRange->GetEndContainer(getter_AddRefs(endParent))) || !endParent)
01330     return NS_ERROR_FAILURE;
01331   cEndP = do_QueryInterface(endParent);
01332   aRange->GetEndOffset(&endIndx);
01333 
01334   if (!cStartP || !cEndP)
01335   {
01336     // XXX Hack to account for the fact that not everything QIs to nsIContent.
01337     // See bug 302775
01338     return NS_ERROR_FAILURE;
01339   }
01340   
01341   // short circuit when start node == end node
01342   if (startParent == endParent)
01343   {
01344     cChild = cStartP->GetChildAt(0);
01345   
01346     if (!cChild) // no children, must be a text node or empty container
01347     {
01348       // all inside one text node - empty subtree iterator
01349       MakeEmpty();
01350       return NS_OK;
01351     }
01352     else
01353     {
01354       if (startIndx == endIndx)  // collapsed range
01355       {
01356         MakeEmpty();
01357         return NS_OK;
01358       }
01359     }
01360   }
01361   
01362   // cache ancestors
01363 #if 0
01364   nsContentUtils::GetAncestorsAndOffsets(startParent, startIndx,
01365                                          &mStartNodes, &mStartOffsets);
01366 #endif
01367   nsContentUtils::GetAncestorsAndOffsets(endParent, endIndx,
01368                                          &mEndNodes, &mEndOffsets);
01369 
01370   // find first node in range
01371   aRange->GetStartOffset(&indx);
01372   numChildren = GetNumChildren(startParent);
01373   
01374   if (!numChildren) // no children, must be a text node
01375   {
01376     cN = cStartP; 
01377   }
01378   else
01379   {
01380     dChild = GetChildAt(startParent, indx);
01381     cChild = do_QueryInterface(dChild);
01382     if (!cChild)  // offset after last child
01383     {
01384       cN = cStartP;
01385     }
01386     else
01387     {
01388       firstCandidate = cChild;
01389     }
01390   }
01391   
01392   if (!firstCandidate)
01393   {
01394     // then firstCandidate is next node after cN
01395     firstCandidate = GetNextSibling(cN, nsnull);
01396 
01397     if (!firstCandidate)
01398     {
01399       MakeEmpty();
01400       return NS_OK;
01401     }
01402   }
01403   
01404   firstCandidate = GetDeepFirstChild(firstCandidate, nsnull);
01405   
01406   // confirm that this first possible contained node
01407   // is indeed contained.  Else we have a range that
01408   // does not fully contain any node.
01409   
01410   PRBool nodeBefore, nodeAfter;
01411   if (NS_FAILED(nsRange::CompareNodeToRange(firstCandidate, aRange,
01412                                             &nodeBefore, &nodeAfter)))
01413     return NS_ERROR_FAILURE;
01414 
01415   if (nodeBefore || nodeAfter)
01416   {
01417     MakeEmpty();
01418     return NS_OK;
01419   }
01420 
01421   // cool, we have the first node in the range.  Now we walk
01422   // up it's ancestors to find the most senior that is still
01423   // in the range.  That's the real first node.
01424   if (NS_FAILED(GetTopAncestorInRange(firstCandidate, address_of(mFirst))))
01425     return NS_ERROR_FAILURE;
01426 
01427   // now to find the last node
01428   aRange->GetEndOffset(&indx);
01429   numChildren = GetNumChildren(endParent);
01430 
01431   if (indx > numChildren) indx = numChildren;
01432   if (!indx)
01433   {
01434     cN = cEndP;
01435   }
01436   else
01437   {
01438     if (!numChildren) // no children, must be a text node
01439     {
01440       cN = cEndP; 
01441     }
01442     else
01443     {
01444       dChild = GetChildAt(endParent, --indx);
01445       cChild = do_QueryInterface(dChild);
01446       if (!cChild)  // shouldn't happen
01447       {
01448         NS_ASSERTION(0,"tree traversal trouble in nsContentSubtreeIterator::Init");
01449         return NS_ERROR_FAILURE;
01450       }
01451       else
01452       {
01453         lastCandidate = cChild;
01454       }
01455     }
01456   }
01457   
01458   if (!lastCandidate)
01459   {
01460     // then lastCandidate is prev node before cN
01461     lastCandidate = GetPrevSibling(cN, nsnull);
01462   }
01463   
01464   lastCandidate = GetDeepLastChild(lastCandidate, nsnull);
01465   
01466   // confirm that this last possible contained node
01467   // is indeed contained.  Else we have a range that
01468   // does not fully contain any node.
01469   
01470   if (NS_FAILED(nsRange::CompareNodeToRange(lastCandidate, aRange, &nodeBefore,
01471                                             &nodeAfter)))
01472     return NS_ERROR_FAILURE;
01473 
01474   if (nodeBefore || nodeAfter)
01475   {
01476     MakeEmpty();
01477     return NS_OK;
01478   }
01479 
01480   // cool, we have the last node in the range.  Now we walk
01481   // up it's ancestors to find the most senior that is still
01482   // in the range.  That's the real first node.
01483   if (NS_FAILED(GetTopAncestorInRange(lastCandidate, address_of(mLast))))
01484     return NS_ERROR_FAILURE;
01485   
01486   mCurNode = mFirst;
01487 
01488   return NS_OK;
01489 }
01490 
01491 
01492 /****************************************************************
01493  * nsContentSubtreeIterator overrides of ContentIterator routines
01494  ****************************************************************/
01495 
01496 // we can't call PositionAt in a subtree iterator...
01497 void
01498 nsContentSubtreeIterator::First()
01499 {
01500   mIsDone = mFirst == nsnull;
01501 
01502   mCurNode = mFirst;
01503 }
01504 
01505 // we can't call PositionAt in a subtree iterator...
01506 void
01507 nsContentSubtreeIterator::Last()
01508 {
01509   mIsDone = mLast == nsnull;
01510 
01511   mCurNode = mLast;
01512 }
01513 
01514 
01515 void
01516 nsContentSubtreeIterator::Next()
01517 {
01518   if (mIsDone || !mCurNode) 
01519     return;
01520 
01521   if (mCurNode == mLast) 
01522   {
01523     mIsDone = PR_TRUE;
01524     return;
01525   }
01526 
01527   nsIContent *nextNode = GetNextSibling(mCurNode, nsnull);
01528   NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
01529 
01530 /*
01531   nextNode = GetDeepFirstChild(nextNode);
01532   return GetTopAncestorInRange(nextNode, address_of(mCurNode));
01533 */
01534   PRInt32 i = mEndNodes.IndexOf(nextNode);
01535   while (i != -1)
01536   {
01537     // as long as we are finding ancestors of the endpoint of the range,
01538     // dive down into their children
01539     nextNode = nextNode->GetChildAt(0);
01540     NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
01541 
01542     // should be impossible to get a null pointer.  If we went all the way
01543     // down the child chain to the bottom without finding an interior node, 
01544     // then the previous node should have been the last, which was
01545     // was tested at top of routine.
01546     i = mEndNodes.IndexOf(nextNode);
01547   }
01548 
01549   mCurNode = nextNode;
01550 
01551   // This shouldn't be needed, but since our selection code can put us
01552   // in a situation where mLast is in generated content, we need this
01553   // to stop the iterator when we've walked past past the last node!
01554   mIsDone = mCurNode == nsnull;
01555 
01556   return;
01557 }
01558 
01559 
01560 void
01561 nsContentSubtreeIterator::Prev()
01562 {
01563   // Prev should be optimized to use the mStartNodes, just as Next
01564   // uses mEndNodes.
01565   if (mIsDone || !mCurNode) 
01566     return;
01567 
01568   if (mCurNode == mFirst) 
01569   {
01570     mIsDone = PR_TRUE;
01571     return;
01572   }
01573 
01574   nsIContent *prevNode = PrevNode(GetDeepFirstChild(mCurNode, nsnull), nsnull);
01575 
01576   prevNode = GetDeepLastChild(prevNode, nsnull);
01577   
01578   GetTopAncestorInRange(prevNode, address_of(mCurNode));
01579 
01580   // This shouldn't be needed, but since our selection code can put us
01581   // in a situation where mFirst is in generated content, we need this
01582   // to stop the iterator when we've walked past past the first node!
01583   mIsDone = mCurNode == nsnull;
01584 }
01585 
01586 
01587 nsresult
01588 nsContentSubtreeIterator::PositionAt(nsIContent* aCurNode)
01589 {
01590   NS_ERROR("Not implemented!");
01591 
01592   return NS_ERROR_NOT_IMPLEMENTED;
01593 }
01594 
01595 /****************************************************************
01596  * nsContentSubtreeIterator helper routines
01597  ****************************************************************/
01598 
01599 nsresult
01600 nsContentSubtreeIterator::GetTopAncestorInRange(nsIContent *aNode,
01601                                                 nsCOMPtr<nsIContent> *outAnestor)
01602 {
01603   if (!aNode) 
01604     return NS_ERROR_NULL_POINTER;
01605   if (!outAnestor) 
01606     return NS_ERROR_NULL_POINTER;
01607   
01608   
01609   // sanity check: aNode is itself in the range
01610   PRBool nodeBefore, nodeAfter;
01611   if (NS_FAILED(nsRange::CompareNodeToRange(aNode, mRange, &nodeBefore,
01612                                             &nodeAfter)))
01613     return NS_ERROR_FAILURE;
01614 
01615   if (nodeBefore || nodeAfter)
01616     return NS_ERROR_FAILURE;
01617   
01618   nsCOMPtr<nsIContent> parent, tmp;
01619   while (aNode)
01620   {
01621     parent = aNode->GetParent();
01622     if (!parent)
01623     {
01624       if (tmp)
01625       {
01626         *outAnestor = tmp;
01627         return NS_OK;
01628       }
01629       else return NS_ERROR_FAILURE;
01630     }
01631     if (NS_FAILED(nsRange::CompareNodeToRange(parent, mRange, &nodeBefore,
01632                                               &nodeAfter)))
01633       return NS_ERROR_FAILURE;
01634 
01635     if (nodeBefore || nodeAfter)
01636     {
01637       *outAnestor = aNode;
01638       return NS_OK;
01639     }
01640     tmp = aNode;
01641     aNode = parent;
01642   }
01643   return NS_ERROR_FAILURE;
01644 }
01645