content/xul/templates/src/nsTreeRows.h

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   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 Communicator client 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  *   Chris Waterson <waterson@netscape.com>
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either of the GNU General Public License Version 2 or later (the "GPL"),
  27  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 #ifndef nsTreeRows_h__
  40 #define nsTreeRows_h__
  41
  42 #include "nsCOMPtr.h"
  43 #include "nsTArray.h"
  44 #include "pldhash.h"
  45 #include "nsIXULTemplateResult.h"
  46 #include "nsTemplateMatch.h"
  47 #include "nsIRDFResource.h"
  48
  49
  50 /**
  51  * This class maintains the state of the XUL tree builder's
  52  * rows. It maps a row number to the nsTemplateMatch object that
  53  * populates the row.
  54  */
  55 class nsTreeRows
  56 {
  57 public:
  58     class iterator;
  59     friend class iterator;
  60
  61     enum Direction { eDirection_Forwards = +1, eDirection_Backwards = -1 };
  62
  63     enum ContainerType {
  64         eContainerType_Unknown      =  0,
  65         eContainerType_Noncontainer =  1,
  66         eContainerType_Container    =  2
  67     };
  68
  69     enum ContainerState {
  70         eContainerState_Unknown     =  0,
  71         eContainerState_Open        =  1,
  72         eContainerState_Closed      =  2
  73     };
  74
  75     enum ContainerFill {
  76         eContainerFill_Unknown      =  0,
  77         eContainerFill_Empty        =  1,
  78         eContainerFill_Nonempty     =  2
  79     };
  80
  81     class Subtree;
  82
  83     /**
  84      * A row in the tree. Contains the match that the row
  85      * corresponds to, and a pointer to the row's subtree, if there
  86      * are any.
  87      */
  88     struct Row {
  89         nsTemplateMatch* mMatch;
  90         ContainerType    mContainerType  : 4;
  91         ContainerState   mContainerState : 4;
  92         ContainerFill    mContainerFill  : 4;
  93
  94         Subtree*         mSubtree; // XXX eventually move to hashtable
  95     };
  96
  97     /**
  98      * A subtree in the tree. A subtree contains rows, which may
  99      * contain other subtrees.
 100      */
 101     class Subtree {
 102     protected:
 103         friend class nsTreeRows; // so that it can access members, for now
 104
 105         /**
 106          * The parent subtree; null if we're the root
 107          */
 108         Subtree* mParent;
 109
 110         /**
 111          * The number of immediate children in this subtree
 112          */
 113         PRInt32 mCount;
 114
 115         /**
 116          * The capacity of the subtree
 117          */
 118         PRInt32 mCapacity;
 119
 120         /**
 121          * The total number of rows in this subtree, recursively
 122          * including child subtrees.
 123          */
 124         PRInt32 mSubtreeSize;
 125
 126         /**
 127          * The array of rows in the subtree
 128          */
 129         Row* mRows;
 130
 131     public:
 132         /**
 133          * Creates a subtree with the specified parent.
 134          */
 135         Subtree(Subtree* aParent)
 136             : mParent(aParent),
 137               mCount(0),
 138               mCapacity(0),
 139               mSubtreeSize(0),
 140               mRows(nsnull) {}
 141
 142         ~Subtree();
 143
 144         /**
 145          * Return the number of immediate child rows in the subtree
 146          */
 147         PRInt32 Count() const { return mCount; }
 148
 149         /**
 150          * Return the number of rows in this subtree, as well as all
 151          * the subtrees it contains.
 152          */
 153         PRInt32 GetSubtreeSize() const { return mSubtreeSize; }
 154
 155         /**
 156          * Retrieve the immediate child row at the specified index.
 157          */
 158         const Row& operator[](PRInt32 aIndex) const {
 159             NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
 160             return mRows[aIndex]; }
 161
 162         /**
 163          * Retrieve the immediate row at the specified index.
 164          */
 165         Row& operator[](PRInt32 aIndex) {
 166             NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
 167             return mRows[aIndex]; }
 168
 169         /**
 170          * Remove all rows from the subtree.
 171          */
 172         void Clear();
 173
 174     protected:
 175         /**
 176          * Insert an immediate child row at the specified index.
 177          */
 178         iterator InsertRowAt(nsTemplateMatch* aMatch, PRInt32 aIndex);
 179
 180         /**
 181          * Remove an immediate child row from the specified index.
 182          */
 183         void RemoveRowAt(PRInt32 aChildIndex);
 184     };
 185
 186     friend class Subtree;
 187
 188 protected:
 189     /**
 190      * A link in the path through the view's tree.
 191      */
 192     struct Link {
 193         Subtree* mParent;
 194         PRInt32  mChildIndex;
 195
 196         Link&
 197         operator=(const Link& aLink) {
 198             mParent = aLink.mParent;
 199             mChildIndex = aLink.mChildIndex;
 200             return *this; }
 201
 202         PRBool
 203         operator==(const Link& aLink) const {
 204             return (mParent == aLink.mParent)
 205                 && (mChildIndex == aLink.mChildIndex); }
 206
 207         Subtree* GetParent() { return mParent; }
 208         const Subtree* GetParent() const { return mParent; }
 209
 210         PRInt32 GetChildIndex() const { return mChildIndex; }
 211
 212         Row& GetRow() { return (*mParent)[mChildIndex]; }
 213         const Row& GetRow() const { return (*mParent)[mChildIndex]; }
 214     };
 215
 216 public:
 217     /**
 218      * An iterator that can be used to traverse the tree view.
 219      */
 220     class iterator {
 221     protected:
 222         PRInt32 mRowIndex;
 223         nsAutoTArray<Link, 8> mLink;
 224
 225         void Next();
 226         void Prev();
 227
 228         friend class Subtree; // so InsertRowAt can initialize us
 229         friend class nsTreeRows; // so nsTreeRows can initialize us
 230
 231         /**
 232          * Used by operator[]() to initialize an iterator.
 233          */
 234         void Append(Subtree* aParent, PRInt32 aChildIndex);
 235
 236         /**
 237          * Used by InsertRowAt() to initialize an iterator.
 238          */
 239         void Push(Subtree *aParent, PRInt32 aChildIndex);
 240
 241         /**
 242          * Used by operator[]() and InsertRowAt() to initialize an iterator.
 243          */
 244         void SetRowIndex(PRInt32 aRowIndex) { mRowIndex = aRowIndex; }
 245
 246         /**
 247          * Handy accessors to the top element.
 248          */
 249         Link& GetTop() { return mLink[mLink.Length() - 1]; }
 250         const Link& GetTop() const { return mLink[mLink.Length() - 1]; }
 251
 252     public:
 253         iterator() : mRowIndex(-1) {}
 254
 255         iterator(const iterator& aIterator);
 256         iterator& operator=(const iterator& aIterator);
 257
 258         PRBool operator==(const iterator& aIterator) const;
 259
 260         PRBool operator!=(const iterator& aIterator) const {
 261             return !aIterator.operator==(*this); }
 262
 263         const Row& operator*() const { return GetTop().GetRow(); }
 264         Row& operator*() { return GetTop().GetRow(); }
 265
 266         const Row* operator->() const { return &(GetTop().GetRow()); }
 267         Row* operator->() { return &(GetTop().GetRow()); }
 268
 269         iterator& operator++() { Next(); return *this; }
 270         iterator operator++(int) { iterator temp(*this); Next(); return temp; }
 271         iterator& operator--() { Prev(); return *this; }
 272         iterator operator--(int) { iterator temp(*this); Prev(); return temp; }
 273
 274         /**
 275          * Return the current parent link
 276          */
 277         Subtree* GetParent() { return GetTop().GetParent(); }
 278
 279         const Subtree* GetParent() const { return GetTop().GetParent(); }
 280
 281         /**
 282          * Return the current child index
 283          */
 284         PRInt32 GetChildIndex() const { return GetTop().GetChildIndex(); }
 285
 286         /**
 287          * Return the depth of the path the iterator is maintaining
 288          * into the tree.
 289          */
 290         PRInt32 GetDepth() const { return mLink.Length(); }
 291
 292         /**
 293          * Return the current row index of the iterator
 294          */
 295         PRInt32 GetRowIndex() const { return mRowIndex; }
 296
 297         /**
 298          * Pop the iterator up a level.
 299          */
 300         iterator& Pop() { mLink.SetLength(GetDepth() - 1); return *this; }
 301     };
 302
 303     /**
 304      * Retrieve the first element in the view
 305      */
 306     iterator First();
 307
 308     /**
 309      * Retrieve (one past) the last element in the view
 310      */
 311     iterator Last();
 312
 313     /**
 314      * Find the row that contains the given resource
 315      */
 316     iterator FindByResource(nsIRDFResource* aResource);
 317
 318     /**
 319      * Find the row that contains the result
 320      */
 321     iterator Find(nsIXULTemplateResult* aResult);
 322
 323     /**
 324      * Retrieve the ith element in the view
 325      */
 326     iterator operator[](PRInt32 aIndex);
 327
 328     nsTreeRows() : mRoot(nsnull) {}
 329     ~nsTreeRows() {}
 330
 331     /**
 332      * Ensure that a child subtree exists within the specified parent
 333      * at the specified child index within the parent. (In other
 334      * words, create a subtree if one doesn't already exist.)
 335      */
 336     Subtree*
 337     EnsureSubtreeFor(Subtree* aParent, PRInt32 aChildIndex);
 338
 339     /**
 340      * Ensure that a child subtree exists at the iterator's position.
 341      */
 342     Subtree*
 343     EnsureSubtreeFor(iterator& aIterator) {
 344         return EnsureSubtreeFor(aIterator.GetParent(),
 345                                 aIterator.GetChildIndex()); }
 346
 347     /**
 348      * Get the child subtree for the specified parent at the specified
 349      * child index. Optionally return the child subtree's size. Will
 350      * return `null' if no subtree exists.
 351      */
 352     Subtree*
 353     GetSubtreeFor(const Subtree* aParent,
 354                   PRInt32 aChildIndex,
 355                   PRInt32* aSubtreeSize = nsnull);
 356
 357     /**
 358      * Retrieve the size of the subtree within the specified parent.
 359      */
 360     PRInt32
 361     GetSubtreeSizeFor(const Subtree* aParent,
 362                       PRInt32 aChildIndex) {
 363         PRInt32 size;
 364         GetSubtreeFor(aParent, aChildIndex, &size);
 365         return size; }
 366
 367     /**
 368      * Retrieve the size of the subtree within the specified parent.
 369      */
 370     PRInt32
 371     GetSubtreeSizeFor(const iterator& aIterator) {
 372         PRInt32 size;
 373         GetSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex(), &size);
 374         return size; }
 375
 376     /**
 377      * Remove the specified subtree for a row, leaving the row itself
 378      * intact.
 379      */
 380     void
 381     RemoveSubtreeFor(Subtree* aParent, PRInt32 aChildIndex);
 382
 383     /**
 384      * Remove the specified subtree for a row, leaving the row itself
 385      * intact.
 386      */
 387     void
 388     RemoveSubtreeFor(iterator& aIterator) {
 389         RemoveSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex()); }
 390
 391     /**
 392      * Remove the specified row from the view
 393      */
 394     PRInt32
 395     RemoveRowAt(iterator& aIterator) {
 396         iterator temp = aIterator--;
 397         Subtree* parent = temp.GetParent();
 398         parent->RemoveRowAt(temp.GetChildIndex());
 399         InvalidateCachedRow();
 400         return parent->Count(); }
 401
 402     /**
 403      * Insert a new match into the view
 404      */
 405     iterator
 406     InsertRowAt(nsTemplateMatch* aMatch, Subtree* aSubtree, PRInt32 aChildIndex) {
 407         InvalidateCachedRow();
 408         return aSubtree->InsertRowAt(aMatch, aChildIndex); }
 409
 410     /**
 411      * Raw access to the rows; e.g., for sorting.
 412      */
 413     Row*
 414     GetRowsFor(Subtree* aSubtree) { return aSubtree->mRows; }
 415
 416     /**
 417      * Remove all of the rows
 418      */
 419     void Clear();
 420
 421     /**
 422      * Return the total number of rows in the tree view.
 423      */
 424     PRInt32 Count() const { return mRoot.GetSubtreeSize(); }
 425
 426     /**
 427      * Retrieve the root subtree
 428      */
 429     Subtree* GetRoot() { return &mRoot; }
 430
 431     /**
 432      * Set the root resource for the view
 433      */
 434     void SetRootResource(nsIRDFResource* aResource) {
 435         mRootResource = aResource; }
 436
 437     /**
 438      * Retrieve the root resource for the view
 439      */
 440     nsIRDFResource* GetRootResource() {
 441         return mRootResource.get(); }
 442
 443     /**
 444      * Invalidate the cached row; e.g., because the view has changed
 445      * in a way that would corrupt the iterator.
 446      */
 447     void
 448     InvalidateCachedRow() { mLastRow = iterator(); }
 449
 450 protected:
 451     /**
 452      * The root subtree.
 453      */
 454     Subtree mRoot;
 455
 456     /**
 457      * The root resource for the view
 458      */
 459     nsCOMPtr<nsIRDFResource> mRootResource;
 460
 461     /**
 462      * The last row that was asked for by operator[]. By remembering
 463      * this, we can usually avoid the O(n) search through the row
 464      * array to find the row at the specified index.
 465      */
 466     iterator mLastRow;
 467 };
 468
 469
 470 #endif // nsTreeRows_h__