mirror of
https://github.com/classilla/tenfourfox.git
synced 2024-06-17 06:29:30 +00:00
483 lines
13 KiB
C++
483 lines
13 KiB
C++
/* -*- 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());
|
|
}
|
|
}
|