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: #include "nsString.h"
michael@0: #include "nsTreeRows.h"
michael@0: #include <algorithm>
michael@0: 
michael@0: nsTreeRows::Subtree*
michael@0: nsTreeRows::EnsureSubtreeFor(Subtree* aParent,
michael@0:                              int32_t aChildIndex)
michael@0: {
michael@0:     Subtree* subtree = GetSubtreeFor(aParent, aChildIndex);
michael@0: 
michael@0:     if (! subtree) {
michael@0:         subtree = aParent->mRows[aChildIndex].mSubtree = new Subtree(aParent);
michael@0:         InvalidateCachedRow();
michael@0:     }
michael@0: 
michael@0:     return subtree;
michael@0: }
michael@0: 
michael@0: nsTreeRows::Subtree*
michael@0: nsTreeRows::GetSubtreeFor(const Subtree* aParent,
michael@0:                               int32_t aChildIndex,
michael@0:                               int32_t* aSubtreeSize)
michael@0: {
michael@0:     NS_PRECONDITION(aParent, "no parent");
michael@0:     NS_PRECONDITION(aChildIndex >= 0, "bad child index");
michael@0: 
michael@0:     Subtree* result = nullptr;
michael@0: 
michael@0:     if (aChildIndex < aParent->mCount)
michael@0:         result = aParent->mRows[aChildIndex].mSubtree;
michael@0: 
michael@0:     if (aSubtreeSize)
michael@0:         *aSubtreeSize = result ? result->mSubtreeSize : 0;
michael@0: 
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: void
michael@0: nsTreeRows::RemoveSubtreeFor(Subtree* aParent, int32_t aChildIndex)
michael@0: {
michael@0:     NS_PRECONDITION(aParent, "no parent");
michael@0:     NS_PRECONDITION(aChildIndex >= 0 && aChildIndex < aParent->mCount, "bad child index");
michael@0: 
michael@0:     Row& row = aParent->mRows[aChildIndex];
michael@0: 
michael@0:     if (row.mSubtree) {
michael@0:         int32_t subtreeSize = row.mSubtree->GetSubtreeSize();
michael@0: 
michael@0:         delete row.mSubtree;
michael@0:         row.mSubtree = nullptr;
michael@0: 
michael@0:         for (Subtree* subtree = aParent; subtree != nullptr; subtree = subtree->mParent)
michael@0:             subtree->mSubtreeSize -= subtreeSize;
michael@0:     }
michael@0: 
michael@0:     InvalidateCachedRow();
michael@0: }
michael@0: 
michael@0: nsTreeRows::iterator
michael@0: nsTreeRows::First()
michael@0: {
michael@0:     iterator result;
michael@0:     result.Append(&mRoot, 0);
michael@0:     result.SetRowIndex(0);
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: nsTreeRows::iterator
michael@0: nsTreeRows::Last()
michael@0: {
michael@0:     iterator result;
michael@0: 
michael@0:     // Build up a path along the rightmost edge of the tree
michael@0:     Subtree* current = &mRoot;
michael@0:     int32_t count = current->Count();
michael@0:     do  {
michael@0:         int32_t last = count - 1;
michael@0:         result.Append(current, last);
michael@0:         current = count ? GetSubtreeFor(current, last) : nullptr;
michael@0:     } while (current && ((count = current->Count()) != 0));
michael@0: 
michael@0:     // Now, at the bottom rightmost leaf, advance us one off the end.
michael@0:     result.GetTop().mChildIndex++;
michael@0: 
michael@0:     // Our row index will be the size of the root subree, plus one.
michael@0:     result.SetRowIndex(mRoot.GetSubtreeSize() + 1);
michael@0: 
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: nsTreeRows::iterator
michael@0: nsTreeRows::operator[](int32_t aRow)
michael@0: {
michael@0:     // See if we're just lucky, and end up with something
michael@0:     // nearby. (This tends to happen a lot due to the way that we get
michael@0:     // asked for rows n' stuff.)
michael@0:     int32_t last = mLastRow.GetRowIndex();
michael@0:     if (last != -1) {
michael@0:         if (aRow == last)
michael@0:             return mLastRow;
michael@0:         else if (last + 1 == aRow)
michael@0:             return ++mLastRow;
michael@0:         else if (last - 1 == aRow)
michael@0:             return --mLastRow;
michael@0:     }
michael@0: 
michael@0:     // Nope. Construct a path to the specified index. This is a little
michael@0:     // bit better than O(n), because we can skip over subtrees. (So it
michael@0:     // ends up being approximately linear in the subtree size, instead
michael@0:     // of the entire view size. But, most of the time, big views are
michael@0:     // flat. Oh well.)
michael@0:     iterator result;
michael@0:     Subtree* current = &mRoot;
michael@0: 
michael@0:     int32_t index = 0;
michael@0:     result.SetRowIndex(aRow);
michael@0: 
michael@0:     do {
michael@0:         int32_t subtreeSize;
michael@0:         Subtree* subtree = GetSubtreeFor(current, index, &subtreeSize);
michael@0: 
michael@0:         if (subtreeSize >= aRow) {
michael@0:             result.Append(current, index);
michael@0:             current = subtree;
michael@0:             index = 0;
michael@0:             --aRow;
michael@0:         }
michael@0:         else {
michael@0:             ++index;
michael@0:             aRow -= subtreeSize + 1;
michael@0:         }
michael@0:     } while (aRow >= 0);
michael@0: 
michael@0:     mLastRow = result;
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: nsTreeRows::iterator
michael@0: nsTreeRows::FindByResource(nsIRDFResource* aResource)
michael@0: {
michael@0:     // XXX Mmm, scan through the rows one-by-one...
michael@0:     iterator last = Last();
michael@0:     iterator iter;
michael@0: 
michael@0:     nsresult rv;
michael@0:     nsAutoString resourceid;
michael@0:     bool stringmode = false;
michael@0: 
michael@0:     for (iter = First(); iter != last; ++iter) {
michael@0:         if (!stringmode) {
michael@0:             nsCOMPtr<nsIRDFResource> findres;
michael@0:             rv = iter->mMatch->mResult->GetResource(getter_AddRefs(findres));
michael@0:             if (NS_FAILED(rv)) return last;
michael@0: 
michael@0:             if (findres == aResource)
michael@0:                 break;
michael@0: 
michael@0:             if (! findres) {
michael@0:                 const char *uri;
michael@0:                 aResource->GetValueConst(&uri);
michael@0:                 CopyUTF8toUTF16(uri, resourceid);
michael@0: 
michael@0:                 // set stringmode and fall through
michael@0:                 stringmode = true;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // additional check because previous block could change stringmode
michael@0:         if (stringmode) {
michael@0:             nsAutoString findid;
michael@0:             rv = iter->mMatch->mResult->GetId(findid);
michael@0:             if (NS_FAILED(rv)) return last;
michael@0: 
michael@0:             if (resourceid.Equals(findid))
michael@0:                 break;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return iter;
michael@0: }
michael@0: 
michael@0: nsTreeRows::iterator
michael@0: nsTreeRows::Find(nsIXULTemplateResult *aResult)
michael@0: {
michael@0:     // XXX Mmm, scan through the rows one-by-one...
michael@0:     iterator last = Last();
michael@0:     iterator iter;
michael@0: 
michael@0:     for (iter = First(); iter != last; ++iter) {
michael@0:         if (aResult == iter->mMatch->mResult)
michael@0:           break;
michael@0:     }
michael@0: 
michael@0:     return iter;
michael@0: }
michael@0: 
michael@0: void
michael@0: nsTreeRows::Clear()
michael@0: {
michael@0:     mRoot.Clear();
michael@0:     InvalidateCachedRow();
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: //
michael@0: // nsTreeRows::Subtree
michael@0: //
michael@0: 
michael@0: nsTreeRows::Subtree::~Subtree()
michael@0: {
michael@0:     Clear();
michael@0: }
michael@0: 
michael@0: void
michael@0: nsTreeRows::Subtree::Clear()
michael@0: {
michael@0:     for (int32_t i = mCount - 1; i >= 0; --i)
michael@0:         delete mRows[i].mSubtree;
michael@0: 
michael@0:     delete[] mRows;
michael@0: 
michael@0:     mRows = nullptr;
michael@0:     mCount = mCapacity = mSubtreeSize = 0;
michael@0: }
michael@0: 
michael@0: nsTreeRows::iterator
michael@0: nsTreeRows::Subtree::InsertRowAt(nsTemplateMatch* aMatch, int32_t aIndex)
michael@0: {
michael@0:     if (mCount >= mCapacity || aIndex >= mCapacity) {
michael@0:         int32_t newCapacity = std::max(mCapacity * 2, aIndex + 1);
michael@0:         Row* newRows = new Row[newCapacity];
michael@0:         if (! newRows)
michael@0:             return iterator();
michael@0: 
michael@0:         for (int32_t i = mCount - 1; i >= 0; --i)
michael@0:             newRows[i] = mRows[i];
michael@0: 
michael@0:         delete[] mRows;
michael@0: 
michael@0:         mRows = newRows;
michael@0:         mCapacity = newCapacity;
michael@0:     }
michael@0: 
michael@0:     for (int32_t i = mCount - 1; i >= aIndex; --i)
michael@0:         mRows[i + 1] = mRows[i];
michael@0: 
michael@0:     mRows[aIndex].mMatch = aMatch;
michael@0:     mRows[aIndex].mContainerType = eContainerType_Unknown;
michael@0:     mRows[aIndex].mContainerState = eContainerState_Unknown;
michael@0:     mRows[aIndex].mContainerFill = eContainerFill_Unknown;
michael@0:     mRows[aIndex].mSubtree = nullptr;
michael@0:     ++mCount;
michael@0: 
michael@0:     // Now build an iterator that points to the newly inserted element.
michael@0:     int32_t rowIndex = 0;
michael@0:     iterator result;
michael@0:     result.Push(this, aIndex);
michael@0: 
michael@0:     for ( ; --aIndex >= 0; ++rowIndex) {
michael@0:         // Account for open subtrees in the absolute row index.
michael@0:         const Subtree *subtree = mRows[aIndex].mSubtree;
michael@0:         if (subtree)
michael@0:             rowIndex += subtree->mSubtreeSize;
michael@0:     }
michael@0: 
michael@0:     Subtree *subtree = this;
michael@0:     do {
michael@0:         // Note that the subtree's size has expanded.
michael@0:         ++subtree->mSubtreeSize;
michael@0: 
michael@0:         Subtree *parent = subtree->mParent;
michael@0:         if (! parent)
michael@0:             break;
michael@0: 
michael@0:         // Account for open subtrees in the absolute row index.
michael@0:         int32_t count = parent->Count();
michael@0:         for (aIndex = 0; aIndex < count; ++aIndex, ++rowIndex) {
michael@0:             const Subtree *child = (*parent)[aIndex].mSubtree;
michael@0:             if (subtree == child)
michael@0:                 break;
michael@0: 
michael@0:             if (child)
michael@0:                 rowIndex += child->mSubtreeSize;
michael@0:         }
michael@0: 
michael@0:         NS_ASSERTION(aIndex < count, "couldn't find subtree in parent");
michael@0: 
michael@0:         result.Push(parent, aIndex);
michael@0:         subtree = parent;
michael@0:         ++rowIndex; // One for the parent row.
michael@0:     } while (1);
michael@0: 
michael@0:     result.SetRowIndex(rowIndex);
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: void
michael@0: nsTreeRows::Subtree::RemoveRowAt(int32_t aIndex)
michael@0: {
michael@0:     NS_PRECONDITION(aIndex >= 0 && aIndex < Count(), "bad index");
michael@0:     if (aIndex < 0 || aIndex >= Count())
michael@0:         return;
michael@0: 
michael@0:     // How big is the subtree we're going to be removing?
michael@0:     int32_t subtreeSize = mRows[aIndex].mSubtree
michael@0:         ? mRows[aIndex].mSubtree->GetSubtreeSize()
michael@0:         : 0;
michael@0: 
michael@0:     ++subtreeSize;
michael@0: 
michael@0:     delete mRows[aIndex].mSubtree;
michael@0: 
michael@0:     for (int32_t i = aIndex + 1; i < mCount; ++i)
michael@0:         mRows[i - 1] = mRows[i];
michael@0: 
michael@0:     --mCount;
michael@0: 
michael@0:     for (Subtree* subtree = this; subtree != nullptr; subtree = subtree->mParent)
michael@0:         subtree->mSubtreeSize -= subtreeSize;
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: //
michael@0: // nsTreeRows::iterator
michael@0: //
michael@0: 
michael@0: nsTreeRows::iterator::iterator(const iterator& aIterator)
michael@0:     : mRowIndex(aIterator.mRowIndex),
michael@0:       mLink(aIterator.mLink)
michael@0: {
michael@0: }
michael@0: 
michael@0: nsTreeRows::iterator&
michael@0: nsTreeRows::iterator::operator=(const iterator& aIterator)
michael@0: {
michael@0:     mRowIndex = aIterator.mRowIndex;
michael@0:     mLink = aIterator.mLink;
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: void
michael@0: nsTreeRows::iterator::Append(Subtree* aParent, int32_t aChildIndex)
michael@0: {
michael@0:     Link *link = mLink.AppendElement();
michael@0:     if (link) {
michael@0:         link->mParent     = aParent;
michael@0:         link->mChildIndex = aChildIndex;
michael@0:     }
michael@0:     else
michael@0:         NS_ERROR("out of memory");
michael@0: }
michael@0: 
michael@0: void
michael@0: nsTreeRows::iterator::Push(Subtree *aParent, int32_t aChildIndex)
michael@0: {
michael@0:     Link *link = mLink.InsertElementAt(0);
michael@0:     if (link) {
michael@0:         link->mParent     = aParent;
michael@0:         link->mChildIndex = aChildIndex;
michael@0:     }
michael@0:     else
michael@0:         NS_ERROR("out of memory");
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsTreeRows::iterator::operator==(const iterator& aIterator) const
michael@0: {
michael@0:     if (GetDepth() != aIterator.GetDepth())
michael@0:         return false;
michael@0: 
michael@0:     if (GetDepth() == 0)
michael@0:         return true;
michael@0: 
michael@0:     return GetTop() == aIterator.GetTop();
michael@0: }
michael@0: 
michael@0: void
michael@0: nsTreeRows::iterator::Next()
michael@0: {
michael@0:     NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");
michael@0: 
michael@0:     // Increment the absolute row index
michael@0:     ++mRowIndex;
michael@0: 
michael@0:     Link& top = GetTop();
michael@0: 
michael@0:     // Is there a child subtree? If so, descend into the child
michael@0:     // subtree.
michael@0:     Subtree* subtree = top.GetRow().mSubtree;
michael@0: 
michael@0:     if (subtree && subtree->Count()) {
michael@0:         Append(subtree, 0);
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // Have we exhausted the current subtree?
michael@0:     if (top.mChildIndex >= top.mParent->Count() - 1) {
michael@0:         // Yep. See if we've just iterated path the last element in
michael@0:         // the tree, period. Walk back up the stack, looking for any
michael@0:         // unfinished subtrees.
michael@0:         int32_t unfinished;
michael@0:         for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {
michael@0:             const Link& link = mLink[unfinished];
michael@0:             if (link.mChildIndex < link.mParent->Count() - 1)
michael@0:                 break;
michael@0:         }
michael@0: 
michael@0:         // If there are no unfinished subtrees in the stack, then this
michael@0:         // iterator is exhausted. Leave it in the same state that
michael@0:         // Last() does.
michael@0:         if (unfinished < 0) {
michael@0:             top.mChildIndex++;
michael@0:             return;
michael@0:         }
michael@0: 
michael@0:         // Otherwise, we ran off the end of one of the inner
michael@0:         // subtrees. Pop up to the next unfinished level in the stack.
michael@0:         mLink.SetLength(unfinished + 1);
michael@0:     }
michael@0: 
michael@0:     // Advance to the next child in this subtree
michael@0:     ++(GetTop().mChildIndex);
michael@0: }
michael@0: 
michael@0: void
michael@0: nsTreeRows::iterator::Prev()
michael@0: {
michael@0:     NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");
michael@0: 
michael@0:     // Decrement the absolute row index
michael@0:     --mRowIndex;
michael@0: 
michael@0:     // Move to the previous child in this subtree
michael@0:     --(GetTop().mChildIndex);
michael@0: 
michael@0:     // Have we exhausted the current subtree?
michael@0:     if (GetTop().mChildIndex < 0) {
michael@0:         // Yep. See if we've just iterated back to the first element
michael@0:         // in the tree, period. Walk back up the stack, looking for
michael@0:         // any unfinished subtrees.
michael@0:         int32_t unfinished;
michael@0:         for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {
michael@0:             const Link& link = mLink[unfinished];
michael@0:             if (link.mChildIndex >= 0)
michael@0:                 break;
michael@0:         }
michael@0: 
michael@0:         // If there are no unfinished subtrees in the stack, then this
michael@0:         // iterator is exhausted. Leave it in the same state that
michael@0:         // First() does.
michael@0:         if (unfinished < 0)
michael@0:             return;
michael@0: 
michael@0:         // Otherwise, we ran off the end of one of the inner
michael@0:         // subtrees. Pop up to the next unfinished level in the stack.
michael@0:         mLink.SetLength(unfinished + 1);
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // Is there a child subtree immediately prior to our current
michael@0:     // position? If so, descend into it, grovelling down to the
michael@0:     // deepest, rightmost left edge.
michael@0:     Subtree* parent = GetTop().GetParent();
michael@0:     int32_t index = GetTop().GetChildIndex();
michael@0: 
michael@0:     Subtree* subtree = (*parent)[index].mSubtree;
michael@0: 
michael@0:     if (subtree && subtree->Count()) {
michael@0:         do {
michael@0:             index = subtree->Count() - 1;
michael@0:             Append(subtree, index);
michael@0: 
michael@0:             parent = subtree;
michael@0:             subtree = (*parent)[index].mSubtree;
michael@0:         } while (subtree && subtree->Count());
michael@0:     }
michael@0: }