Back to index

lightning-sunbird  0.9+nobinonly
nsTreeRows.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
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 Communicator client 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  *   Chris Waterson <waterson@netscape.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 #include "nsTreeRows.h"
00040 #include "nsTemplateMatch.h"
00041 #include "nsTemplateRule.h"
00042 
00043 nsTreeRows::Subtree*
00044 nsTreeRows::EnsureSubtreeFor(Subtree* aParent,
00045                                  PRInt32 aChildIndex)
00046 {
00047     Subtree* subtree = GetSubtreeFor(aParent, aChildIndex);
00048 
00049     if (! subtree) {
00050         subtree = aParent->mRows[aChildIndex].mSubtree = new Subtree(aParent);
00051         InvalidateCachedRow();
00052     }
00053 
00054     return subtree;
00055 }
00056 
00057 nsTreeRows::Subtree*
00058 nsTreeRows::GetSubtreeFor(const Subtree* aParent,
00059                               PRInt32 aChildIndex,
00060                               PRInt32* aSubtreeSize)
00061 {
00062     NS_PRECONDITION(aParent, "no parent");
00063     NS_PRECONDITION(aChildIndex >= 0, "bad child index");
00064 
00065     Subtree* result = nsnull;
00066 
00067     if (aChildIndex < aParent->mCount)
00068         result = aParent->mRows[aChildIndex].mSubtree;
00069 
00070     if (aSubtreeSize)
00071         *aSubtreeSize = result ? result->mSubtreeSize : 0;
00072 
00073     return result;
00074 }
00075 
00076 void
00077 nsTreeRows::RemoveSubtreeFor(Subtree* aParent, PRInt32 aChildIndex)
00078 {
00079     NS_PRECONDITION(aParent, "no parent");
00080     NS_PRECONDITION(aChildIndex >= 0 && aChildIndex < aParent->mCount, "bad child index");
00081 
00082     Row& row = aParent->mRows[aChildIndex];
00083 
00084     if (row.mSubtree) {
00085         PRInt32 subtreeSize = row.mSubtree->GetSubtreeSize();
00086 
00087         delete row.mSubtree;
00088         row.mSubtree = nsnull;
00089 
00090         for (Subtree* subtree = aParent; subtree != nsnull; subtree = subtree->mParent)
00091             subtree->mSubtreeSize -= subtreeSize;
00092     }
00093 
00094     InvalidateCachedRow();
00095 }
00096 
00097 nsTreeRows::iterator
00098 nsTreeRows::First()
00099 {
00100     iterator result;
00101     result.Append(&mRoot, 0);
00102     result.SetRowIndex(0);
00103     return result;
00104 }
00105 
00106 nsTreeRows::iterator
00107 nsTreeRows::Last()
00108 {
00109     iterator result;
00110 
00111     // Build up a path along the rightmost edge of the tree
00112     Subtree* current = &mRoot;
00113     PRInt32 count = current->Count();
00114     do  {
00115         PRInt32 last = count - 1;
00116         result.Append(current, last);
00117         current = count ? GetSubtreeFor(current, last) : nsnull;
00118     } while (current && ((count = current->Count()) != 0));
00119 
00120     // Now, at the bottom rightmost leaf, advance us one off the end.
00121     result.mLink[result.mTop].mChildIndex++;
00122 
00123     // Our row index will be the size of the root subree, plus one.
00124     result.SetRowIndex(mRoot.GetSubtreeSize() + 1);
00125 
00126     return result;
00127 }
00128 
00129 nsTreeRows::iterator
00130 nsTreeRows::operator[](PRInt32 aRow)
00131 {
00132     // See if we're just lucky, and end up with something
00133     // nearby. (This tends to happen a lot due to the way that we get
00134     // asked for rows n' stuff.)
00135     PRInt32 last = mLastRow.GetRowIndex();
00136     if (last != -1) {
00137         if (aRow == last)
00138             return mLastRow;
00139         else if (last + 1 == aRow)
00140             return ++mLastRow;
00141         else if (last - 1 == aRow)
00142             return --mLastRow;
00143     }
00144 
00145     // Nope. Construct a path to the specified index. This is a little
00146     // bit better than O(n), because we can skip over subtrees. (So it
00147     // ends up being approximately linear in the subtree size, instead
00148     // of the entire view size. But, most of the time, big views are
00149     // flat. Oh well.)
00150     iterator result;
00151     Subtree* current = &mRoot;
00152 
00153     PRInt32 index = 0;
00154     result.SetRowIndex(aRow);
00155 
00156     do {
00157         PRInt32 subtreeSize;
00158         Subtree* subtree = GetSubtreeFor(current, index, &subtreeSize);
00159 
00160         if (subtreeSize >= aRow) {
00161             result.Append(current, index);
00162             current = subtree;
00163             index = 0;
00164             --aRow;
00165         }
00166         else {
00167             ++index;
00168             aRow -= subtreeSize + 1;
00169         }
00170     } while (aRow >= 0);
00171 
00172     mLastRow = result;
00173     return result;
00174 }
00175 
00176 nsTreeRows::iterator
00177 nsTreeRows::Find(nsConflictSet& aConflictSet, nsIRDFResource* aMember)
00178 {
00179     // XXX Mmm, scan through the rows one-by-one...
00180     iterator last = Last();
00181     iterator iter;
00182 
00183     for (iter = First(); iter != last; ++iter) {
00184         nsTemplateMatch* match = iter->mMatch;
00185 
00186         Value val;
00187         match->GetAssignmentFor(aConflictSet, match->mRule->GetMemberVariable(), &val);
00188 
00189         if (VALUE_TO_IRDFRESOURCE(val) == aMember)
00190             break;
00191     }
00192 
00193     return iter;
00194 }
00195 
00196 void
00197 nsTreeRows::Clear()
00198 {
00199     mRoot.Clear();
00200     InvalidateCachedRow();
00201 }
00202 
00203 //----------------------------------------------------------------------
00204 //
00205 // nsTreeRows::Subtree
00206 //
00207 
00208 nsTreeRows::Subtree::~Subtree()
00209 {
00210     Clear();
00211 }
00212 
00213 void
00214 nsTreeRows::Subtree::Clear()
00215 {
00216     for (PRInt32 i = mCount - 1; i >= 0; --i)
00217         delete mRows[i].mSubtree;
00218 
00219     delete[] mRows;
00220 
00221     mRows = nsnull;
00222     mCount = mCapacity = mSubtreeSize = 0;
00223 }
00224 
00225 nsTreeRows::iterator
00226 nsTreeRows::Subtree::InsertRowAt(nsTemplateMatch* aMatch, PRInt32 aIndex)
00227 {
00228     if (mCount >= mCapacity || aIndex >= mCapacity) {
00229         PRInt32 newCapacity = NS_MAX(mCapacity * 2, aIndex + 1);
00230         Row* newRows = new Row[newCapacity];
00231         if (! newRows)
00232             return iterator();
00233 
00234         for (PRInt32 i = mCount - 1; i >= 0; --i)
00235             newRows[i] = mRows[i];
00236 
00237         delete[] mRows;
00238 
00239         mRows = newRows;
00240         mCapacity = newCapacity;
00241     }
00242 
00243     for (PRInt32 i = mCount - 1; i >= aIndex; --i)
00244         mRows[i + 1] = mRows[i];
00245 
00246     mRows[aIndex].mMatch = aMatch;
00247     mRows[aIndex].mContainerType = eContainerType_Unknown;
00248     mRows[aIndex].mContainerState = eContainerState_Unknown;
00249     mRows[aIndex].mContainerFill = eContainerFill_Unknown;
00250     mRows[aIndex].mSubtree = nsnull;
00251     ++mCount;
00252 
00253     // Now build an iterator that points to the newly inserted element.
00254     PRInt32 rowIndex = 0;
00255     iterator result;
00256     result.Push(this, aIndex);
00257 
00258     for ( ; --aIndex >= 0; ++rowIndex) {
00259         // Account for open subtrees in the absolute row index.
00260         const Subtree *subtree = mRows[aIndex].mSubtree;
00261         if (subtree)
00262             rowIndex += subtree->mSubtreeSize;
00263     }
00264 
00265     Subtree *subtree = this;
00266     do {
00267         // Note that the subtree's size has expanded.
00268         ++subtree->mSubtreeSize;
00269 
00270         Subtree *parent = subtree->mParent;
00271         if (! parent)
00272             break;
00273 
00274         // Account for open subtrees in the absolute row index.
00275         PRInt32 count = parent->Count();
00276         for (aIndex = 0; aIndex < count; ++aIndex, ++rowIndex) {
00277             const Subtree *child = (*parent)[aIndex].mSubtree;
00278             if (subtree == child)
00279                 break;
00280 
00281             if (child)
00282                 rowIndex += child->mSubtreeSize;
00283         }
00284 
00285         NS_ASSERTION(aIndex < count, "couldn't find subtree in parent");
00286 
00287         result.Push(parent, aIndex);
00288         subtree = parent;
00289         ++rowIndex; // One for the parent row.
00290     } while (1);
00291 
00292     result.SetRowIndex(rowIndex);
00293     return result;
00294 }
00295 
00296 void
00297 nsTreeRows::Subtree::RemoveRowAt(PRInt32 aIndex)
00298 {
00299     NS_PRECONDITION(aIndex >= 0 && aIndex < Count(), "bad index");
00300     if (aIndex < 0 || aIndex >= Count())
00301         return;
00302 
00303     // How big is the subtree we're going to be removing?
00304     PRInt32 subtreeSize = mRows[aIndex].mSubtree
00305         ? mRows[aIndex].mSubtree->GetSubtreeSize()
00306         : 0;
00307 
00308     ++subtreeSize;
00309 
00310     delete mRows[aIndex].mSubtree;
00311 
00312     for (PRInt32 i = aIndex + 1; i < mCount; ++i)
00313         mRows[i - 1] = mRows[i];
00314 
00315     --mCount;
00316 
00317     for (Subtree* subtree = this; subtree != nsnull; subtree = subtree->mParent)
00318         subtree->mSubtreeSize -= subtreeSize;
00319 }
00320 
00321 //----------------------------------------------------------------------
00322 //
00323 // nsTreeRows::iterator
00324 //
00325 
00326 nsTreeRows::iterator::iterator(const iterator& aIterator)
00327     : mTop(aIterator.mTop),
00328       mRowIndex(aIterator.mRowIndex)
00329 {
00330     for (PRInt32 i = mTop; i >= 0; --i)
00331         mLink[i] = aIterator.mLink[i];
00332 }
00333 
00334 nsTreeRows::iterator&
00335 nsTreeRows::iterator::operator=(const iterator& aIterator)
00336 {
00337     mTop = aIterator.mTop;
00338     mRowIndex = aIterator.mRowIndex;
00339     for (PRInt32 i = mTop; i >= 0; --i)
00340         mLink[i] = aIterator.mLink[i];
00341     return *this;
00342 }
00343 
00344 void
00345 nsTreeRows::iterator::Append(Subtree* aParent, PRInt32 aChildIndex)
00346 {
00347     if (mTop < kMaxDepth - 1) {
00348         ++mTop;
00349         mLink[mTop].mParent     = aParent;
00350         mLink[mTop].mChildIndex = aChildIndex;
00351     }
00352     else
00353         NS_ERROR("overflow");
00354 }
00355 
00356 void
00357 nsTreeRows::iterator::Push(Subtree *aParent, PRInt32 aChildIndex)
00358 {
00359     if (mTop < kMaxDepth - 1) {
00360         for (PRInt32 i = mTop; i >= 0; --i)
00361             mLink[i + 1] = mLink[i];
00362 
00363         mLink[0].mParent     = aParent;
00364         mLink[0].mChildIndex = aChildIndex;
00365         ++mTop;
00366     }
00367     else
00368         NS_ERROR("overflow");
00369 }
00370 
00371 PRBool
00372 nsTreeRows::iterator::operator==(const iterator& aIterator) const
00373 {
00374     if (mTop != aIterator.mTop)
00375         return PR_FALSE;
00376 
00377     if (mTop == -1)
00378         return PR_TRUE;
00379 
00380     return PRBool(mLink[mTop] == aIterator.mLink[mTop]);
00381 }
00382 
00383 void
00384 nsTreeRows::iterator::Next()
00385 {
00386     NS_PRECONDITION(mTop >= 0, "cannot increment an uninitialized iterator");
00387 
00388     // Increment the absolute row index
00389     ++mRowIndex;
00390 
00391     Link& top = mLink[mTop];
00392 
00393     // Is there a child subtree? If so, descend into the child
00394     // subtree.
00395     Subtree* subtree = top.GetRow().mSubtree;
00396 
00397     if (subtree && subtree->Count()) {
00398         Append(subtree, 0);
00399         return;
00400     }
00401 
00402     // Have we exhausted the current subtree?
00403     if (top.mChildIndex >= top.mParent->Count() - 1) {
00404         // Yep. See if we've just iterated path the last element in
00405         // the tree, period. Walk back up the stack, looking for any
00406         // unfinished subtrees.
00407         PRInt32 unfinished;
00408         for (unfinished = mTop - 1; unfinished >= 0; --unfinished) {
00409             const Link& link = mLink[unfinished];
00410             if (link.mChildIndex < link.mParent->Count() - 1)
00411                 break;
00412         }
00413 
00414         // If there are no unfinished subtrees in the stack, then this
00415         // iterator is exhausted. Leave it in the same state that
00416         // Last() does.
00417         if (unfinished < 0) {
00418             top.mChildIndex++;
00419             return;
00420         }
00421 
00422         // Otherwise, we ran off the end of one of the inner
00423         // subtrees. Pop up to the next unfinished level in the stack.
00424         mTop = unfinished;
00425     }
00426 
00427     // Advance to the next child in this subtree
00428     ++(mLink[mTop].mChildIndex);
00429 }
00430 
00431 void
00432 nsTreeRows::iterator::Prev()
00433 {
00434     NS_PRECONDITION(mTop >= 0, "cannot increment an uninitialized iterator");
00435 
00436     // Decrement the absolute row index
00437     --mRowIndex;
00438 
00439     // Move to the previous child in this subtree
00440     --(mLink[mTop].mChildIndex);
00441 
00442     // Have we exhausted the current subtree?
00443     if (mLink[mTop].mChildIndex < 0) {
00444         // Yep. See if we've just iterated back to the first element
00445         // in the tree, period. Walk back up the stack, looking for
00446         // any unfinished subtrees.
00447         PRInt32 unfinished;
00448         for (unfinished = mTop - 1; unfinished >= 0; --unfinished) {
00449             const Link& link = mLink[unfinished];
00450             if (link.mChildIndex >= 0)
00451                 break;
00452         }
00453 
00454         // If there are no unfinished subtrees in the stack, then this
00455         // iterator is exhausted. Leave it in the same state that
00456         // First() does.
00457         if (unfinished < 0)
00458             return;
00459 
00460         // Otherwise, we ran off the end of one of the inner
00461         // subtrees. Pop up to the next unfinished level in the stack.
00462         mTop = unfinished;
00463         return;
00464     }
00465 
00466     // Is there a child subtree immediately prior to our current
00467     // position? If so, descend into it, grovelling down to the
00468     // deepest, rightmost left edge.
00469     Subtree* parent = mLink[mTop].GetParent();
00470     PRInt32 index = mLink[mTop].GetChildIndex();
00471 
00472     Subtree* subtree = (*parent)[index].mSubtree;
00473 
00474     if (subtree && subtree->Count()) {
00475         do {
00476             index = subtree->Count() - 1;
00477             Append(subtree, index);
00478 
00479             parent = subtree;
00480             subtree = (*parent)[index].mSubtree;
00481         } while (subtree && subtree->Count());
00482     }
00483 }