michael@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef nsTreeRows_h__
michael@0: #define nsTreeRows_h__
michael@0: 
michael@0: #include "nsCOMPtr.h"
michael@0: #include "nsTArray.h"
michael@0: #include "pldhash.h"
michael@0: #include "nsIXULTemplateResult.h"
michael@0: #include "nsTemplateMatch.h"
michael@0: #include "nsIRDFResource.h"
michael@0: 
michael@0: 
michael@0: /**
michael@0:  * This class maintains the state of the XUL tree builder's
michael@0:  * rows. It maps a row number to the nsTemplateMatch object that
michael@0:  * populates the row.
michael@0:  */
michael@0: class nsTreeRows
michael@0: {
michael@0: public:
michael@0:     class iterator;
michael@0:     friend class iterator;
michael@0: 
michael@0:     enum Direction { eDirection_Forwards = +1, eDirection_Backwards = -1 };
michael@0: 
michael@0:     enum ContainerType {
michael@0:         eContainerType_Unknown      =  0,
michael@0:         eContainerType_Noncontainer =  1,
michael@0:         eContainerType_Container    =  2
michael@0:     };
michael@0: 
michael@0:     enum ContainerState {
michael@0:         eContainerState_Unknown     =  0,
michael@0:         eContainerState_Open        =  1,
michael@0:         eContainerState_Closed      =  2
michael@0:     };
michael@0: 
michael@0:     enum ContainerFill {
michael@0:         eContainerFill_Unknown      =  0,
michael@0:         eContainerFill_Empty        =  1,
michael@0:         eContainerFill_Nonempty     =  2
michael@0:     };
michael@0: 
michael@0:     class Subtree;
michael@0: 
michael@0:     /**
michael@0:      * A row in the tree. Contains the match that the row
michael@0:      * corresponds to, and a pointer to the row's subtree, if there
michael@0:      * are any.
michael@0:      */
michael@0:     struct Row {
michael@0:         nsTemplateMatch* mMatch;
michael@0:         ContainerType    mContainerType  : 4;
michael@0:         ContainerState   mContainerState : 4;
michael@0:         ContainerFill    mContainerFill  : 4;
michael@0:         
michael@0:         Subtree*         mSubtree; // XXX eventually move to hashtable
michael@0:     };
michael@0: 
michael@0:     /**
michael@0:      * A subtree in the tree. A subtree contains rows, which may
michael@0:      * contain other subtrees.
michael@0:      */
michael@0:     class Subtree {
michael@0:     protected:
michael@0:         friend class nsTreeRows; // so that it can access members, for now
michael@0: 
michael@0:         /**
michael@0:          * The parent subtree; null if we're the root
michael@0:          */
michael@0:         Subtree* mParent;
michael@0: 
michael@0:         /**
michael@0:          * The number of immediate children in this subtree
michael@0:          */
michael@0:         int32_t mCount;
michael@0: 
michael@0:         /**
michael@0:          * The capacity of the subtree
michael@0:          */
michael@0:         int32_t mCapacity;
michael@0: 
michael@0:         /**
michael@0:          * The total number of rows in this subtree, recursively
michael@0:          * including child subtrees.
michael@0:          */
michael@0:         int32_t mSubtreeSize;
michael@0: 
michael@0:         /**
michael@0:          * The array of rows in the subtree
michael@0:          */
michael@0:         Row* mRows;
michael@0: 
michael@0:     public:
michael@0:         /**
michael@0:          * Creates a subtree with the specified parent.
michael@0:          */
michael@0:         Subtree(Subtree* aParent)
michael@0:             : mParent(aParent),
michael@0:               mCount(0),
michael@0:               mCapacity(0),
michael@0:               mSubtreeSize(0),
michael@0:               mRows(nullptr) {}
michael@0: 
michael@0:         ~Subtree();
michael@0: 
michael@0:         /**
michael@0:          * Return the number of immediate child rows in the subtree
michael@0:          */
michael@0:         int32_t Count() const { return mCount; }
michael@0: 
michael@0:         /**
michael@0:          * Return the number of rows in this subtree, as well as all
michael@0:          * the subtrees it contains.
michael@0:          */
michael@0:         int32_t GetSubtreeSize() const { return mSubtreeSize; }
michael@0: 
michael@0:         /**
michael@0:          * Retrieve the immediate child row at the specified index.
michael@0:          */
michael@0:         const Row& operator[](int32_t aIndex) const {
michael@0:             NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
michael@0:             return mRows[aIndex]; }
michael@0: 
michael@0:         /**
michael@0:          * Retrieve the immediate row at the specified index.
michael@0:          */
michael@0:         Row& operator[](int32_t aIndex) {
michael@0:             NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
michael@0:             return mRows[aIndex]; }
michael@0: 
michael@0:         /**
michael@0:          * Remove all rows from the subtree.
michael@0:          */
michael@0:         void Clear();
michael@0: 
michael@0:     protected:
michael@0:         /**
michael@0:          * Insert an immediate child row at the specified index.
michael@0:          */
michael@0:         iterator InsertRowAt(nsTemplateMatch* aMatch, int32_t aIndex);
michael@0: 
michael@0:         /**
michael@0:          * Remove an immediate child row from the specified index.
michael@0:          */
michael@0:         void RemoveRowAt(int32_t aChildIndex);
michael@0:     };
michael@0: 
michael@0:     friend class Subtree;
michael@0: 
michael@0: protected:
michael@0:     /**
michael@0:      * A link in the path through the view's tree.
michael@0:      */
michael@0:     struct Link {
michael@0:         Subtree* mParent;
michael@0:         int32_t  mChildIndex;
michael@0: 
michael@0:         Link&
michael@0:         operator=(const Link& aLink) {
michael@0:             mParent = aLink.mParent;
michael@0:             mChildIndex = aLink.mChildIndex;
michael@0:             return *this; }
michael@0: 
michael@0:         bool
michael@0:         operator==(const Link& aLink) const {
michael@0:             return (mParent == aLink.mParent)
michael@0:                 && (mChildIndex == aLink.mChildIndex); }
michael@0: 
michael@0:         Subtree* GetParent() { return mParent; }
michael@0:         const Subtree* GetParent() const { return mParent; }
michael@0: 
michael@0:         int32_t GetChildIndex() const { return mChildIndex; }
michael@0: 
michael@0:         Row& GetRow() { return (*mParent)[mChildIndex]; }
michael@0:         const Row& GetRow() const { return (*mParent)[mChildIndex]; }
michael@0:     };
michael@0: 
michael@0: public:
michael@0:     /**
michael@0:      * An iterator that can be used to traverse the tree view.
michael@0:      */
michael@0:     class iterator {
michael@0:     protected:
michael@0:         int32_t mRowIndex;
michael@0:         nsAutoTArray<Link, 8> mLink;
michael@0: 
michael@0:         void Next();
michael@0:         void Prev();
michael@0: 
michael@0:         friend class Subtree; // so InsertRowAt can initialize us
michael@0:         friend class nsTreeRows; // so nsTreeRows can initialize us
michael@0: 
michael@0:         /**
michael@0:          * Used by operator[]() to initialize an iterator.
michael@0:          */
michael@0:         void Append(Subtree* aParent, int32_t aChildIndex);
michael@0: 
michael@0:         /**
michael@0:          * Used by InsertRowAt() to initialize an iterator.
michael@0:          */
michael@0:         void Push(Subtree *aParent, int32_t aChildIndex);
michael@0: 
michael@0:         /**
michael@0:          * Used by operator[]() and InsertRowAt() to initialize an iterator.
michael@0:          */
michael@0:         void SetRowIndex(int32_t aRowIndex) { mRowIndex = aRowIndex; }
michael@0: 
michael@0:         /**
michael@0:          * Handy accessors to the top element.
michael@0:          */
michael@0:         Link& GetTop() { return mLink[mLink.Length() - 1]; }
michael@0:         const Link& GetTop() const { return mLink[mLink.Length() - 1]; }
michael@0: 
michael@0:     public:
michael@0:         iterator() : mRowIndex(-1) {}
michael@0: 
michael@0:         iterator(const iterator& aIterator);
michael@0:         iterator& operator=(const iterator& aIterator);
michael@0: 
michael@0:         bool operator==(const iterator& aIterator) const;
michael@0: 
michael@0:         bool operator!=(const iterator& aIterator) const {
michael@0:             return !aIterator.operator==(*this); }
michael@0: 
michael@0:         const Row& operator*() const { return GetTop().GetRow(); }
michael@0:         Row& operator*() { return GetTop().GetRow(); }
michael@0: 
michael@0:         const Row* operator->() const { return &(GetTop().GetRow()); }
michael@0:         Row* operator->() { return &(GetTop().GetRow()); }
michael@0: 
michael@0:         iterator& operator++() { Next(); return *this; }
michael@0:         iterator operator++(int) { iterator temp(*this); Next(); return temp; }
michael@0:         iterator& operator--() { Prev(); return *this; }
michael@0:         iterator operator--(int) { iterator temp(*this); Prev(); return temp; }
michael@0: 
michael@0:         /**
michael@0:          * Return the current parent link
michael@0:          */
michael@0:         Subtree* GetParent() { return GetTop().GetParent(); }
michael@0: 
michael@0:         const Subtree* GetParent() const { return GetTop().GetParent(); }
michael@0: 
michael@0:         /**
michael@0:          * Return the current child index
michael@0:          */
michael@0:         int32_t GetChildIndex() const { return GetTop().GetChildIndex(); }
michael@0: 
michael@0:         /**
michael@0:          * Return the depth of the path the iterator is maintaining
michael@0:          * into the tree.
michael@0:          */
michael@0:         int32_t GetDepth() const { return mLink.Length(); }
michael@0: 
michael@0:         /**
michael@0:          * Return the current row index of the iterator
michael@0:          */
michael@0:         int32_t GetRowIndex() const { return mRowIndex; }
michael@0: 
michael@0:         /**
michael@0:          * Pop the iterator up a level.
michael@0:          */
michael@0:         iterator& Pop() { mLink.SetLength(GetDepth() - 1); return *this; }
michael@0:     };
michael@0: 
michael@0:     /**
michael@0:      * Retrieve the first element in the view
michael@0:      */
michael@0:     iterator First();
michael@0: 
michael@0:     /**
michael@0:      * Retrieve (one past) the last element in the view
michael@0:      */
michael@0:     iterator Last();
michael@0: 
michael@0:     /**
michael@0:      * Find the row that contains the given resource
michael@0:      */
michael@0:     iterator FindByResource(nsIRDFResource* aResource);
michael@0: 
michael@0:     /**
michael@0:      * Find the row that contains the result
michael@0:      */
michael@0:     iterator Find(nsIXULTemplateResult* aResult);
michael@0: 
michael@0:     /**
michael@0:      * Retrieve the ith element in the view
michael@0:      */
michael@0:     iterator operator[](int32_t aIndex);
michael@0: 
michael@0:     nsTreeRows() : mRoot(nullptr) {}
michael@0:     ~nsTreeRows() {}
michael@0: 
michael@0:     /**
michael@0:      * Ensure that a child subtree exists within the specified parent
michael@0:      * at the specified child index within the parent. (In other
michael@0:      * words, create a subtree if one doesn't already exist.)
michael@0:      */
michael@0:     Subtree*
michael@0:     EnsureSubtreeFor(Subtree* aParent, int32_t aChildIndex);
michael@0: 
michael@0:     /**
michael@0:      * Ensure that a child subtree exists at the iterator's position.
michael@0:      */
michael@0:     Subtree*
michael@0:     EnsureSubtreeFor(iterator& aIterator) {
michael@0:         return EnsureSubtreeFor(aIterator.GetParent(),
michael@0:                                 aIterator.GetChildIndex()); }
michael@0: 
michael@0:     /**
michael@0:      * Get the child subtree for the specified parent at the specified
michael@0:      * child index. Optionally return the child subtree's size. Will
michael@0:      * return `null' if no subtree exists.
michael@0:      */
michael@0:     Subtree*
michael@0:     GetSubtreeFor(const Subtree* aParent,
michael@0:                   int32_t aChildIndex,
michael@0:                   int32_t* aSubtreeSize = nullptr);
michael@0: 
michael@0:     /**
michael@0:      * Retrieve the size of the subtree within the specified parent.
michael@0:      */
michael@0:     int32_t
michael@0:     GetSubtreeSizeFor(const Subtree* aParent,
michael@0:                       int32_t aChildIndex) {
michael@0:         int32_t size;
michael@0:         GetSubtreeFor(aParent, aChildIndex, &size);
michael@0:         return size; }
michael@0: 
michael@0:     /**
michael@0:      * Retrieve the size of the subtree within the specified parent.
michael@0:      */
michael@0:     int32_t
michael@0:     GetSubtreeSizeFor(const iterator& aIterator) {
michael@0:         int32_t size;
michael@0:         GetSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex(), &size);
michael@0:         return size; }
michael@0: 
michael@0:     /**
michael@0:      * Remove the specified subtree for a row, leaving the row itself
michael@0:      * intact.
michael@0:      */
michael@0:     void
michael@0:     RemoveSubtreeFor(Subtree* aParent, int32_t aChildIndex);
michael@0: 
michael@0:     /**
michael@0:      * Remove the specified subtree for a row, leaving the row itself
michael@0:      * intact.
michael@0:      */
michael@0:     void
michael@0:     RemoveSubtreeFor(iterator& aIterator) {
michael@0:         RemoveSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex()); }
michael@0: 
michael@0:     /**
michael@0:      * Remove the specified row from the view
michael@0:      */
michael@0:     int32_t
michael@0:     RemoveRowAt(iterator& aIterator) {
michael@0:         iterator temp = aIterator--;
michael@0:         Subtree* parent = temp.GetParent();
michael@0:         parent->RemoveRowAt(temp.GetChildIndex());
michael@0:         InvalidateCachedRow();
michael@0:         return parent->Count(); }
michael@0: 
michael@0:     /**
michael@0:      * Insert a new match into the view
michael@0:      */
michael@0:     iterator
michael@0:     InsertRowAt(nsTemplateMatch* aMatch, Subtree* aSubtree, int32_t aChildIndex) {
michael@0:         InvalidateCachedRow();
michael@0:         return aSubtree->InsertRowAt(aMatch, aChildIndex); }
michael@0: 
michael@0:     /**
michael@0:      * Raw access to the rows; e.g., for sorting.
michael@0:      */
michael@0:     Row*
michael@0:     GetRowsFor(Subtree* aSubtree) { return aSubtree->mRows; }
michael@0: 
michael@0:     /**
michael@0:      * Remove all of the rows
michael@0:      */
michael@0:     void Clear();
michael@0: 
michael@0:     /**
michael@0:      * Return the total number of rows in the tree view.
michael@0:      */
michael@0:     int32_t Count() const { return mRoot.GetSubtreeSize(); }
michael@0: 
michael@0:     /**
michael@0:      * Retrieve the root subtree
michael@0:      */
michael@0:     Subtree* GetRoot() { return &mRoot; }
michael@0: 
michael@0:     /**
michael@0:      * Set the root resource for the view
michael@0:      */
michael@0:     void SetRootResource(nsIRDFResource* aResource) {
michael@0:         mRootResource = aResource; }
michael@0: 
michael@0:     /**
michael@0:      * Retrieve the root resource for the view
michael@0:      */
michael@0:     nsIRDFResource* GetRootResource() {
michael@0:         return mRootResource.get(); }
michael@0: 
michael@0:     /**
michael@0:      * Invalidate the cached row; e.g., because the view has changed
michael@0:      * in a way that would corrupt the iterator.
michael@0:      */
michael@0:     void
michael@0:     InvalidateCachedRow() { mLastRow = iterator(); }
michael@0: 
michael@0: protected:
michael@0:     /**
michael@0:      * The root subtree.
michael@0:      */
michael@0:     Subtree mRoot;
michael@0: 
michael@0:     /**
michael@0:      * The root resource for the view
michael@0:      */
michael@0:     nsCOMPtr<nsIRDFResource> mRootResource;
michael@0: 
michael@0:     /**
michael@0:      * The last row that was asked for by operator[]. By remembering
michael@0:      * this, we can usually avoid the O(n) search through the row
michael@0:      * array to find the row at the specified index.
michael@0:      */
michael@0:     iterator mLastRow;
michael@0: };
michael@0: 
michael@0: 
michael@0: #endif // nsTreeRows_h__