1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/xul/templates/src/nsTreeRows.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,482 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "nsString.h"
1.10 +#include "nsTreeRows.h"
1.11 +#include <algorithm>
1.12 +
1.13 +nsTreeRows::Subtree*
1.14 +nsTreeRows::EnsureSubtreeFor(Subtree* aParent,
1.15 + int32_t aChildIndex)
1.16 +{
1.17 + Subtree* subtree = GetSubtreeFor(aParent, aChildIndex);
1.18 +
1.19 + if (! subtree) {
1.20 + subtree = aParent->mRows[aChildIndex].mSubtree = new Subtree(aParent);
1.21 + InvalidateCachedRow();
1.22 + }
1.23 +
1.24 + return subtree;
1.25 +}
1.26 +
1.27 +nsTreeRows::Subtree*
1.28 +nsTreeRows::GetSubtreeFor(const Subtree* aParent,
1.29 + int32_t aChildIndex,
1.30 + int32_t* aSubtreeSize)
1.31 +{
1.32 + NS_PRECONDITION(aParent, "no parent");
1.33 + NS_PRECONDITION(aChildIndex >= 0, "bad child index");
1.34 +
1.35 + Subtree* result = nullptr;
1.36 +
1.37 + if (aChildIndex < aParent->mCount)
1.38 + result = aParent->mRows[aChildIndex].mSubtree;
1.39 +
1.40 + if (aSubtreeSize)
1.41 + *aSubtreeSize = result ? result->mSubtreeSize : 0;
1.42 +
1.43 + return result;
1.44 +}
1.45 +
1.46 +void
1.47 +nsTreeRows::RemoveSubtreeFor(Subtree* aParent, int32_t aChildIndex)
1.48 +{
1.49 + NS_PRECONDITION(aParent, "no parent");
1.50 + NS_PRECONDITION(aChildIndex >= 0 && aChildIndex < aParent->mCount, "bad child index");
1.51 +
1.52 + Row& row = aParent->mRows[aChildIndex];
1.53 +
1.54 + if (row.mSubtree) {
1.55 + int32_t subtreeSize = row.mSubtree->GetSubtreeSize();
1.56 +
1.57 + delete row.mSubtree;
1.58 + row.mSubtree = nullptr;
1.59 +
1.60 + for (Subtree* subtree = aParent; subtree != nullptr; subtree = subtree->mParent)
1.61 + subtree->mSubtreeSize -= subtreeSize;
1.62 + }
1.63 +
1.64 + InvalidateCachedRow();
1.65 +}
1.66 +
1.67 +nsTreeRows::iterator
1.68 +nsTreeRows::First()
1.69 +{
1.70 + iterator result;
1.71 + result.Append(&mRoot, 0);
1.72 + result.SetRowIndex(0);
1.73 + return result;
1.74 +}
1.75 +
1.76 +nsTreeRows::iterator
1.77 +nsTreeRows::Last()
1.78 +{
1.79 + iterator result;
1.80 +
1.81 + // Build up a path along the rightmost edge of the tree
1.82 + Subtree* current = &mRoot;
1.83 + int32_t count = current->Count();
1.84 + do {
1.85 + int32_t last = count - 1;
1.86 + result.Append(current, last);
1.87 + current = count ? GetSubtreeFor(current, last) : nullptr;
1.88 + } while (current && ((count = current->Count()) != 0));
1.89 +
1.90 + // Now, at the bottom rightmost leaf, advance us one off the end.
1.91 + result.GetTop().mChildIndex++;
1.92 +
1.93 + // Our row index will be the size of the root subree, plus one.
1.94 + result.SetRowIndex(mRoot.GetSubtreeSize() + 1);
1.95 +
1.96 + return result;
1.97 +}
1.98 +
1.99 +nsTreeRows::iterator
1.100 +nsTreeRows::operator[](int32_t aRow)
1.101 +{
1.102 + // See if we're just lucky, and end up with something
1.103 + // nearby. (This tends to happen a lot due to the way that we get
1.104 + // asked for rows n' stuff.)
1.105 + int32_t last = mLastRow.GetRowIndex();
1.106 + if (last != -1) {
1.107 + if (aRow == last)
1.108 + return mLastRow;
1.109 + else if (last + 1 == aRow)
1.110 + return ++mLastRow;
1.111 + else if (last - 1 == aRow)
1.112 + return --mLastRow;
1.113 + }
1.114 +
1.115 + // Nope. Construct a path to the specified index. This is a little
1.116 + // bit better than O(n), because we can skip over subtrees. (So it
1.117 + // ends up being approximately linear in the subtree size, instead
1.118 + // of the entire view size. But, most of the time, big views are
1.119 + // flat. Oh well.)
1.120 + iterator result;
1.121 + Subtree* current = &mRoot;
1.122 +
1.123 + int32_t index = 0;
1.124 + result.SetRowIndex(aRow);
1.125 +
1.126 + do {
1.127 + int32_t subtreeSize;
1.128 + Subtree* subtree = GetSubtreeFor(current, index, &subtreeSize);
1.129 +
1.130 + if (subtreeSize >= aRow) {
1.131 + result.Append(current, index);
1.132 + current = subtree;
1.133 + index = 0;
1.134 + --aRow;
1.135 + }
1.136 + else {
1.137 + ++index;
1.138 + aRow -= subtreeSize + 1;
1.139 + }
1.140 + } while (aRow >= 0);
1.141 +
1.142 + mLastRow = result;
1.143 + return result;
1.144 +}
1.145 +
1.146 +nsTreeRows::iterator
1.147 +nsTreeRows::FindByResource(nsIRDFResource* aResource)
1.148 +{
1.149 + // XXX Mmm, scan through the rows one-by-one...
1.150 + iterator last = Last();
1.151 + iterator iter;
1.152 +
1.153 + nsresult rv;
1.154 + nsAutoString resourceid;
1.155 + bool stringmode = false;
1.156 +
1.157 + for (iter = First(); iter != last; ++iter) {
1.158 + if (!stringmode) {
1.159 + nsCOMPtr<nsIRDFResource> findres;
1.160 + rv = iter->mMatch->mResult->GetResource(getter_AddRefs(findres));
1.161 + if (NS_FAILED(rv)) return last;
1.162 +
1.163 + if (findres == aResource)
1.164 + break;
1.165 +
1.166 + if (! findres) {
1.167 + const char *uri;
1.168 + aResource->GetValueConst(&uri);
1.169 + CopyUTF8toUTF16(uri, resourceid);
1.170 +
1.171 + // set stringmode and fall through
1.172 + stringmode = true;
1.173 + }
1.174 + }
1.175 +
1.176 + // additional check because previous block could change stringmode
1.177 + if (stringmode) {
1.178 + nsAutoString findid;
1.179 + rv = iter->mMatch->mResult->GetId(findid);
1.180 + if (NS_FAILED(rv)) return last;
1.181 +
1.182 + if (resourceid.Equals(findid))
1.183 + break;
1.184 + }
1.185 + }
1.186 +
1.187 + return iter;
1.188 +}
1.189 +
1.190 +nsTreeRows::iterator
1.191 +nsTreeRows::Find(nsIXULTemplateResult *aResult)
1.192 +{
1.193 + // XXX Mmm, scan through the rows one-by-one...
1.194 + iterator last = Last();
1.195 + iterator iter;
1.196 +
1.197 + for (iter = First(); iter != last; ++iter) {
1.198 + if (aResult == iter->mMatch->mResult)
1.199 + break;
1.200 + }
1.201 +
1.202 + return iter;
1.203 +}
1.204 +
1.205 +void
1.206 +nsTreeRows::Clear()
1.207 +{
1.208 + mRoot.Clear();
1.209 + InvalidateCachedRow();
1.210 +}
1.211 +
1.212 +//----------------------------------------------------------------------
1.213 +//
1.214 +// nsTreeRows::Subtree
1.215 +//
1.216 +
1.217 +nsTreeRows::Subtree::~Subtree()
1.218 +{
1.219 + Clear();
1.220 +}
1.221 +
1.222 +void
1.223 +nsTreeRows::Subtree::Clear()
1.224 +{
1.225 + for (int32_t i = mCount - 1; i >= 0; --i)
1.226 + delete mRows[i].mSubtree;
1.227 +
1.228 + delete[] mRows;
1.229 +
1.230 + mRows = nullptr;
1.231 + mCount = mCapacity = mSubtreeSize = 0;
1.232 +}
1.233 +
1.234 +nsTreeRows::iterator
1.235 +nsTreeRows::Subtree::InsertRowAt(nsTemplateMatch* aMatch, int32_t aIndex)
1.236 +{
1.237 + if (mCount >= mCapacity || aIndex >= mCapacity) {
1.238 + int32_t newCapacity = std::max(mCapacity * 2, aIndex + 1);
1.239 + Row* newRows = new Row[newCapacity];
1.240 + if (! newRows)
1.241 + return iterator();
1.242 +
1.243 + for (int32_t i = mCount - 1; i >= 0; --i)
1.244 + newRows[i] = mRows[i];
1.245 +
1.246 + delete[] mRows;
1.247 +
1.248 + mRows = newRows;
1.249 + mCapacity = newCapacity;
1.250 + }
1.251 +
1.252 + for (int32_t i = mCount - 1; i >= aIndex; --i)
1.253 + mRows[i + 1] = mRows[i];
1.254 +
1.255 + mRows[aIndex].mMatch = aMatch;
1.256 + mRows[aIndex].mContainerType = eContainerType_Unknown;
1.257 + mRows[aIndex].mContainerState = eContainerState_Unknown;
1.258 + mRows[aIndex].mContainerFill = eContainerFill_Unknown;
1.259 + mRows[aIndex].mSubtree = nullptr;
1.260 + ++mCount;
1.261 +
1.262 + // Now build an iterator that points to the newly inserted element.
1.263 + int32_t rowIndex = 0;
1.264 + iterator result;
1.265 + result.Push(this, aIndex);
1.266 +
1.267 + for ( ; --aIndex >= 0; ++rowIndex) {
1.268 + // Account for open subtrees in the absolute row index.
1.269 + const Subtree *subtree = mRows[aIndex].mSubtree;
1.270 + if (subtree)
1.271 + rowIndex += subtree->mSubtreeSize;
1.272 + }
1.273 +
1.274 + Subtree *subtree = this;
1.275 + do {
1.276 + // Note that the subtree's size has expanded.
1.277 + ++subtree->mSubtreeSize;
1.278 +
1.279 + Subtree *parent = subtree->mParent;
1.280 + if (! parent)
1.281 + break;
1.282 +
1.283 + // Account for open subtrees in the absolute row index.
1.284 + int32_t count = parent->Count();
1.285 + for (aIndex = 0; aIndex < count; ++aIndex, ++rowIndex) {
1.286 + const Subtree *child = (*parent)[aIndex].mSubtree;
1.287 + if (subtree == child)
1.288 + break;
1.289 +
1.290 + if (child)
1.291 + rowIndex += child->mSubtreeSize;
1.292 + }
1.293 +
1.294 + NS_ASSERTION(aIndex < count, "couldn't find subtree in parent");
1.295 +
1.296 + result.Push(parent, aIndex);
1.297 + subtree = parent;
1.298 + ++rowIndex; // One for the parent row.
1.299 + } while (1);
1.300 +
1.301 + result.SetRowIndex(rowIndex);
1.302 + return result;
1.303 +}
1.304 +
1.305 +void
1.306 +nsTreeRows::Subtree::RemoveRowAt(int32_t aIndex)
1.307 +{
1.308 + NS_PRECONDITION(aIndex >= 0 && aIndex < Count(), "bad index");
1.309 + if (aIndex < 0 || aIndex >= Count())
1.310 + return;
1.311 +
1.312 + // How big is the subtree we're going to be removing?
1.313 + int32_t subtreeSize = mRows[aIndex].mSubtree
1.314 + ? mRows[aIndex].mSubtree->GetSubtreeSize()
1.315 + : 0;
1.316 +
1.317 + ++subtreeSize;
1.318 +
1.319 + delete mRows[aIndex].mSubtree;
1.320 +
1.321 + for (int32_t i = aIndex + 1; i < mCount; ++i)
1.322 + mRows[i - 1] = mRows[i];
1.323 +
1.324 + --mCount;
1.325 +
1.326 + for (Subtree* subtree = this; subtree != nullptr; subtree = subtree->mParent)
1.327 + subtree->mSubtreeSize -= subtreeSize;
1.328 +}
1.329 +
1.330 +//----------------------------------------------------------------------
1.331 +//
1.332 +// nsTreeRows::iterator
1.333 +//
1.334 +
1.335 +nsTreeRows::iterator::iterator(const iterator& aIterator)
1.336 + : mRowIndex(aIterator.mRowIndex),
1.337 + mLink(aIterator.mLink)
1.338 +{
1.339 +}
1.340 +
1.341 +nsTreeRows::iterator&
1.342 +nsTreeRows::iterator::operator=(const iterator& aIterator)
1.343 +{
1.344 + mRowIndex = aIterator.mRowIndex;
1.345 + mLink = aIterator.mLink;
1.346 + return *this;
1.347 +}
1.348 +
1.349 +void
1.350 +nsTreeRows::iterator::Append(Subtree* aParent, int32_t aChildIndex)
1.351 +{
1.352 + Link *link = mLink.AppendElement();
1.353 + if (link) {
1.354 + link->mParent = aParent;
1.355 + link->mChildIndex = aChildIndex;
1.356 + }
1.357 + else
1.358 + NS_ERROR("out of memory");
1.359 +}
1.360 +
1.361 +void
1.362 +nsTreeRows::iterator::Push(Subtree *aParent, int32_t aChildIndex)
1.363 +{
1.364 + Link *link = mLink.InsertElementAt(0);
1.365 + if (link) {
1.366 + link->mParent = aParent;
1.367 + link->mChildIndex = aChildIndex;
1.368 + }
1.369 + else
1.370 + NS_ERROR("out of memory");
1.371 +}
1.372 +
1.373 +bool
1.374 +nsTreeRows::iterator::operator==(const iterator& aIterator) const
1.375 +{
1.376 + if (GetDepth() != aIterator.GetDepth())
1.377 + return false;
1.378 +
1.379 + if (GetDepth() == 0)
1.380 + return true;
1.381 +
1.382 + return GetTop() == aIterator.GetTop();
1.383 +}
1.384 +
1.385 +void
1.386 +nsTreeRows::iterator::Next()
1.387 +{
1.388 + NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");
1.389 +
1.390 + // Increment the absolute row index
1.391 + ++mRowIndex;
1.392 +
1.393 + Link& top = GetTop();
1.394 +
1.395 + // Is there a child subtree? If so, descend into the child
1.396 + // subtree.
1.397 + Subtree* subtree = top.GetRow().mSubtree;
1.398 +
1.399 + if (subtree && subtree->Count()) {
1.400 + Append(subtree, 0);
1.401 + return;
1.402 + }
1.403 +
1.404 + // Have we exhausted the current subtree?
1.405 + if (top.mChildIndex >= top.mParent->Count() - 1) {
1.406 + // Yep. See if we've just iterated path the last element in
1.407 + // the tree, period. Walk back up the stack, looking for any
1.408 + // unfinished subtrees.
1.409 + int32_t unfinished;
1.410 + for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {
1.411 + const Link& link = mLink[unfinished];
1.412 + if (link.mChildIndex < link.mParent->Count() - 1)
1.413 + break;
1.414 + }
1.415 +
1.416 + // If there are no unfinished subtrees in the stack, then this
1.417 + // iterator is exhausted. Leave it in the same state that
1.418 + // Last() does.
1.419 + if (unfinished < 0) {
1.420 + top.mChildIndex++;
1.421 + return;
1.422 + }
1.423 +
1.424 + // Otherwise, we ran off the end of one of the inner
1.425 + // subtrees. Pop up to the next unfinished level in the stack.
1.426 + mLink.SetLength(unfinished + 1);
1.427 + }
1.428 +
1.429 + // Advance to the next child in this subtree
1.430 + ++(GetTop().mChildIndex);
1.431 +}
1.432 +
1.433 +void
1.434 +nsTreeRows::iterator::Prev()
1.435 +{
1.436 + NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");
1.437 +
1.438 + // Decrement the absolute row index
1.439 + --mRowIndex;
1.440 +
1.441 + // Move to the previous child in this subtree
1.442 + --(GetTop().mChildIndex);
1.443 +
1.444 + // Have we exhausted the current subtree?
1.445 + if (GetTop().mChildIndex < 0) {
1.446 + // Yep. See if we've just iterated back to the first element
1.447 + // in the tree, period. Walk back up the stack, looking for
1.448 + // any unfinished subtrees.
1.449 + int32_t unfinished;
1.450 + for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {
1.451 + const Link& link = mLink[unfinished];
1.452 + if (link.mChildIndex >= 0)
1.453 + break;
1.454 + }
1.455 +
1.456 + // If there are no unfinished subtrees in the stack, then this
1.457 + // iterator is exhausted. Leave it in the same state that
1.458 + // First() does.
1.459 + if (unfinished < 0)
1.460 + return;
1.461 +
1.462 + // Otherwise, we ran off the end of one of the inner
1.463 + // subtrees. Pop up to the next unfinished level in the stack.
1.464 + mLink.SetLength(unfinished + 1);
1.465 + return;
1.466 + }
1.467 +
1.468 + // Is there a child subtree immediately prior to our current
1.469 + // position? If so, descend into it, grovelling down to the
1.470 + // deepest, rightmost left edge.
1.471 + Subtree* parent = GetTop().GetParent();
1.472 + int32_t index = GetTop().GetChildIndex();
1.473 +
1.474 + Subtree* subtree = (*parent)[index].mSubtree;
1.475 +
1.476 + if (subtree && subtree->Count()) {
1.477 + do {
1.478 + index = subtree->Count() - 1;
1.479 + Append(subtree, index);
1.480 +
1.481 + parent = subtree;
1.482 + subtree = (*parent)[index].mSubtree;
1.483 + } while (subtree && subtree->Count());
1.484 + }
1.485 +}
