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