Back to index

lightning-sunbird  0.9+nobinonly
nsTreeRows.h
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 #ifndef nsTreeRows_h__
00040 #define nsTreeRows_h__
00041 
00042 #include "nsCOMPtr.h"
00043 #include "nsIRDFResource.h"
00044 #include "pldhash.h"
00045 class nsConflictSet;
00046 class nsTemplateMatch;
00047 
00053 class nsTreeRows
00054 {
00055 public:
00056     class iterator;
00057     friend class iterator;
00058 
00059     enum Direction { eDirection_Forwards = +1, eDirection_Backwards = -1 };
00060 
00061     // N.B. these values are chosen to avoid problems with
00062     // sign-extension from the bit-packed Row structure.
00063     enum ContainerType {
00064         eContainerType_Unknown      =  0,
00065         eContainerType_Noncontainer =  1,
00066         eContainerType_Container    = -2
00067     };
00068 
00069     enum ContainerState {
00070         eContainerState_Unknown     =  0,
00071         eContainerState_Open        =  1,
00072         eContainerState_Closed      = -2
00073     };
00074 
00075     enum ContainerFill {
00076         eContainerFill_Unknown      =  0,
00077         eContainerFill_Empty        =  1,
00078         eContainerFill_Nonempty     = -2
00079     };
00080 
00081     class Subtree;
00082 
00088     struct Row {
00089         nsTemplateMatch* mMatch;
00090         ContainerType    mContainerType  : 2;
00091         ContainerState   mContainerState : 2;
00092         ContainerFill    mContainerFill  : 2;
00093         
00094         Subtree*         mSubtree; // XXX eventually move to hashtable
00095     };
00096 
00101     class Subtree {
00102     protected:
00103         friend class nsTreeRows; // so that it can access members, for now
00104 
00108         Subtree* mParent;
00109 
00113         PRInt32 mCount;
00114 
00118         PRInt32 mCapacity;
00119 
00124         PRInt32 mSubtreeSize;
00125 
00129         Row* mRows;
00130 
00131     public:
00135         Subtree(Subtree* aParent)
00136             : mParent(aParent),
00137               mCount(0),
00138               mCapacity(0),
00139               mSubtreeSize(0),
00140               mRows(nsnull) {}
00141 
00142         ~Subtree();
00143 
00147         PRInt32 Count() const { return mCount; }
00148 
00153         PRInt32 GetSubtreeSize() const { return mSubtreeSize; }
00154 
00158         const Row& operator[](PRInt32 aIndex) const {
00159             NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
00160             return mRows[aIndex]; }
00161 
00165         Row& operator[](PRInt32 aIndex) {
00166             NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
00167             return mRows[aIndex]; }
00168 
00172         void Clear();
00173 
00174     protected:
00178         iterator InsertRowAt(nsTemplateMatch* aMatch, PRInt32 aIndex);
00179 
00183         void RemoveRowAt(PRInt32 aChildIndex);
00184     };
00185 
00186     friend class Subtree;
00187 
00188     enum { kMaxDepth = 32 };
00189 
00190 protected:
00194     struct Link {
00195         Subtree* mParent;
00196         PRInt32  mChildIndex;
00197 
00198         Link&
00199         operator=(const Link& aLink) {
00200             mParent = aLink.mParent;
00201             mChildIndex = aLink.mChildIndex;
00202             return *this; }
00203 
00204         PRBool
00205         operator==(const Link& aLink) const {
00206             return (mParent == aLink.mParent)
00207                 && (mChildIndex == aLink.mChildIndex); }
00208 
00209         Subtree* GetParent() { return mParent; }
00210         const Subtree* GetParent() const { return mParent; }
00211 
00212         PRInt32 GetChildIndex() const { return mChildIndex; }
00213 
00214         Row& GetRow() { return (*mParent)[mChildIndex]; }
00215         const Row& GetRow() const { return (*mParent)[mChildIndex]; }
00216     };
00217 
00218 public:
00222     class iterator {
00223     protected:
00224         PRInt32 mTop;
00225         PRInt32 mRowIndex;
00226         Link    mLink[kMaxDepth];
00227 
00228         void Next();
00229         void Prev();
00230 
00231         friend class Subtree; // so InsertRowAt can initialize us
00232         friend class nsTreeRows; // so nsTreeRows can initialize us
00233 
00237         void Append(Subtree* aParent, PRInt32 aChildIndex);
00238 
00242         void Push(Subtree *aParent, PRInt32 aChildIndex);
00243 
00247         void SetRowIndex(PRInt32 aRowIndex) { mRowIndex = aRowIndex; }
00248 
00249     public:
00250         iterator() : mTop(-1), mRowIndex(-1) {}
00251 
00252         iterator(const iterator& aIterator);
00253         iterator& operator=(const iterator& aIterator);
00254 
00255         PRBool operator==(const iterator& aIterator) const;
00256 
00257         PRBool operator!=(const iterator& aIterator) const {
00258             return !aIterator.operator==(*this); }
00259 
00260         const Row& operator*() const { return mLink[mTop].GetRow(); }
00261         Row& operator*() { return mLink[mTop].GetRow(); }
00262 
00263         const Row* operator->() const { return &(mLink[mTop].GetRow()); }
00264         Row* operator->() { return &(mLink[mTop].GetRow()); }
00265 
00266         iterator& operator++() { Next(); return *this; }
00267         iterator operator++(int) { iterator temp(*this); Next(); return temp; }
00268         iterator& operator--() { Prev(); return *this; }
00269         iterator operator--(int) { iterator temp(*this); Prev(); return temp; }
00270 
00274         Subtree* GetParent() {
00275             return mLink[mTop].GetParent(); }
00276 
00277         const Subtree* GetParent() const {
00278             return mLink[mTop].GetParent(); }
00279 
00283         PRInt32 GetChildIndex() const {
00284             return mLink[mTop].GetChildIndex(); }
00285 
00290         PRInt32 GetDepth() const { return mTop + 1; }
00291 
00295         PRInt32 GetRowIndex() const { return mRowIndex; }
00296 
00300         iterator& Pop() { --mTop; return *this; }
00301     };
00302 
00306     iterator First();
00307 
00311     iterator Last();
00312 
00317     iterator Find(nsConflictSet& aConflictSet, nsIRDFResource* aMember);
00318 
00322     iterator operator[](PRInt32 aIndex);
00323 
00324     nsTreeRows() : mRoot(nsnull), mRootResource(nsnull) {}
00325     ~nsTreeRows() {}
00326 
00332     Subtree*
00333     EnsureSubtreeFor(Subtree* aParent, PRInt32 aChildIndex);
00334 
00338     Subtree*
00339     EnsureSubtreeFor(iterator& aIterator) {
00340         return EnsureSubtreeFor(aIterator.GetParent(),
00341                                 aIterator.GetChildIndex()); }
00342 
00348     Subtree*
00349     GetSubtreeFor(const Subtree* aParent,
00350                   PRInt32 aChildIndex,
00351                   PRInt32* aSubtreeSize = nsnull);
00352 
00356     PRInt32
00357     GetSubtreeSizeFor(const Subtree* aParent,
00358                       PRInt32 aChildIndex) {
00359         PRInt32 size;
00360         GetSubtreeFor(aParent, aChildIndex, &size);
00361         return size; }
00362 
00366     PRInt32
00367     GetSubtreeSizeFor(const iterator& aIterator) {
00368         PRInt32 size;
00369         GetSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex(), &size);
00370         return size; }
00371 
00376     void
00377     RemoveSubtreeFor(Subtree* aParent, PRInt32 aChildIndex);
00378 
00383     void
00384     RemoveSubtreeFor(iterator& aIterator) {
00385         RemoveSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex()); }
00386 
00390     PRInt32
00391     RemoveRowAt(iterator& aIterator) {
00392         iterator temp = aIterator--;
00393         Subtree* parent = temp.GetParent();
00394         parent->RemoveRowAt(temp.GetChildIndex());
00395         InvalidateCachedRow();
00396         return parent->Count(); }
00397 
00401     iterator
00402     InsertRowAt(nsTemplateMatch* aMatch, Subtree* aSubtree, PRInt32 aChildIndex) {
00403         InvalidateCachedRow();
00404         return aSubtree->InsertRowAt(aMatch, aChildIndex); }
00405 
00409     Row*
00410     GetRowsFor(Subtree* aSubtree) { return aSubtree->mRows; }
00411 
00415     void Clear();
00416 
00420     PRInt32 Count() const { return mRoot.GetSubtreeSize(); }
00421 
00425     Subtree* GetRoot() { return &mRoot; }
00426 
00430     void SetRootResource(nsIRDFResource* aResource) {
00431         mRootResource = aResource; }
00432 
00436     nsIRDFResource* GetRootResource() {
00437         return mRootResource.get(); }
00438 
00443     void
00444     InvalidateCachedRow() { mLastRow = iterator(); }
00445 
00446 protected:
00450     Subtree mRoot;
00451 
00455     nsCOMPtr<nsIRDFResource> mRootResource;
00456 
00462     iterator mLastRow;
00463 };
00464 
00465 
00466 #endif // nsTreeRows_h__