1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/xul/templates/src/nsTreeRows.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,437 @@
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 +#ifndef nsTreeRows_h__
1.10 +#define nsTreeRows_h__
1.11 +
1.12 +#include "nsCOMPtr.h"
1.13 +#include "nsTArray.h"
1.14 +#include "pldhash.h"
1.15 +#include "nsIXULTemplateResult.h"
1.16 +#include "nsTemplateMatch.h"
1.17 +#include "nsIRDFResource.h"
1.18 +
1.19 +
1.20 +/**
1.21 + * This class maintains the state of the XUL tree builder's
1.22 + * rows. It maps a row number to the nsTemplateMatch object that
1.23 + * populates the row.
1.24 + */
1.25 +class nsTreeRows
1.26 +{
1.27 +public:
1.28 + class iterator;
1.29 + friend class iterator;
1.30 +
1.31 + enum Direction { eDirection_Forwards = +1, eDirection_Backwards = -1 };
1.32 +
1.33 + enum ContainerType {
1.34 + eContainerType_Unknown = 0,
1.35 + eContainerType_Noncontainer = 1,
1.36 + eContainerType_Container = 2
1.37 + };
1.38 +
1.39 + enum ContainerState {
1.40 + eContainerState_Unknown = 0,
1.41 + eContainerState_Open = 1,
1.42 + eContainerState_Closed = 2
1.43 + };
1.44 +
1.45 + enum ContainerFill {
1.46 + eContainerFill_Unknown = 0,
1.47 + eContainerFill_Empty = 1,
1.48 + eContainerFill_Nonempty = 2
1.49 + };
1.50 +
1.51 + class Subtree;
1.52 +
1.53 + /**
1.54 + * A row in the tree. Contains the match that the row
1.55 + * corresponds to, and a pointer to the row's subtree, if there
1.56 + * are any.
1.57 + */
1.58 + struct Row {
1.59 + nsTemplateMatch* mMatch;
1.60 + ContainerType mContainerType : 4;
1.61 + ContainerState mContainerState : 4;
1.62 + ContainerFill mContainerFill : 4;
1.63 +
1.64 + Subtree* mSubtree; // XXX eventually move to hashtable
1.65 + };
1.66 +
1.67 + /**
1.68 + * A subtree in the tree. A subtree contains rows, which may
1.69 + * contain other subtrees.
1.70 + */
1.71 + class Subtree {
1.72 + protected:
1.73 + friend class nsTreeRows; // so that it can access members, for now
1.74 +
1.75 + /**
1.76 + * The parent subtree; null if we're the root
1.77 + */
1.78 + Subtree* mParent;
1.79 +
1.80 + /**
1.81 + * The number of immediate children in this subtree
1.82 + */
1.83 + int32_t mCount;
1.84 +
1.85 + /**
1.86 + * The capacity of the subtree
1.87 + */
1.88 + int32_t mCapacity;
1.89 +
1.90 + /**
1.91 + * The total number of rows in this subtree, recursively
1.92 + * including child subtrees.
1.93 + */
1.94 + int32_t mSubtreeSize;
1.95 +
1.96 + /**
1.97 + * The array of rows in the subtree
1.98 + */
1.99 + Row* mRows;
1.100 +
1.101 + public:
1.102 + /**
1.103 + * Creates a subtree with the specified parent.
1.104 + */
1.105 + Subtree(Subtree* aParent)
1.106 + : mParent(aParent),
1.107 + mCount(0),
1.108 + mCapacity(0),
1.109 + mSubtreeSize(0),
1.110 + mRows(nullptr) {}
1.111 +
1.112 + ~Subtree();
1.113 +
1.114 + /**
1.115 + * Return the number of immediate child rows in the subtree
1.116 + */
1.117 + int32_t Count() const { return mCount; }
1.118 +
1.119 + /**
1.120 + * Return the number of rows in this subtree, as well as all
1.121 + * the subtrees it contains.
1.122 + */
1.123 + int32_t GetSubtreeSize() const { return mSubtreeSize; }
1.124 +
1.125 + /**
1.126 + * Retrieve the immediate child row at the specified index.
1.127 + */
1.128 + const Row& operator[](int32_t aIndex) const {
1.129 + NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
1.130 + return mRows[aIndex]; }
1.131 +
1.132 + /**
1.133 + * Retrieve the immediate row at the specified index.
1.134 + */
1.135 + Row& operator[](int32_t aIndex) {
1.136 + NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
1.137 + return mRows[aIndex]; }
1.138 +
1.139 + /**
1.140 + * Remove all rows from the subtree.
1.141 + */
1.142 + void Clear();
1.143 +
1.144 + protected:
1.145 + /**
1.146 + * Insert an immediate child row at the specified index.
1.147 + */
1.148 + iterator InsertRowAt(nsTemplateMatch* aMatch, int32_t aIndex);
1.149 +
1.150 + /**
1.151 + * Remove an immediate child row from the specified index.
1.152 + */
1.153 + void RemoveRowAt(int32_t aChildIndex);
1.154 + };
1.155 +
1.156 + friend class Subtree;
1.157 +
1.158 +protected:
1.159 + /**
1.160 + * A link in the path through the view's tree.
1.161 + */
1.162 + struct Link {
1.163 + Subtree* mParent;
1.164 + int32_t mChildIndex;
1.165 +
1.166 + Link&
1.167 + operator=(const Link& aLink) {
1.168 + mParent = aLink.mParent;
1.169 + mChildIndex = aLink.mChildIndex;
1.170 + return *this; }
1.171 +
1.172 + bool
1.173 + operator==(const Link& aLink) const {
1.174 + return (mParent == aLink.mParent)
1.175 + && (mChildIndex == aLink.mChildIndex); }
1.176 +
1.177 + Subtree* GetParent() { return mParent; }
1.178 + const Subtree* GetParent() const { return mParent; }
1.179 +
1.180 + int32_t GetChildIndex() const { return mChildIndex; }
1.181 +
1.182 + Row& GetRow() { return (*mParent)[mChildIndex]; }
1.183 + const Row& GetRow() const { return (*mParent)[mChildIndex]; }
1.184 + };
1.185 +
1.186 +public:
1.187 + /**
1.188 + * An iterator that can be used to traverse the tree view.
1.189 + */
1.190 + class iterator {
1.191 + protected:
1.192 + int32_t mRowIndex;
1.193 + nsAutoTArray<Link, 8> mLink;
1.194 +
1.195 + void Next();
1.196 + void Prev();
1.197 +
1.198 + friend class Subtree; // so InsertRowAt can initialize us
1.199 + friend class nsTreeRows; // so nsTreeRows can initialize us
1.200 +
1.201 + /**
1.202 + * Used by operator[]() to initialize an iterator.
1.203 + */
1.204 + void Append(Subtree* aParent, int32_t aChildIndex);
1.205 +
1.206 + /**
1.207 + * Used by InsertRowAt() to initialize an iterator.
1.208 + */
1.209 + void Push(Subtree *aParent, int32_t aChildIndex);
1.210 +
1.211 + /**
1.212 + * Used by operator[]() and InsertRowAt() to initialize an iterator.
1.213 + */
1.214 + void SetRowIndex(int32_t aRowIndex) { mRowIndex = aRowIndex; }
1.215 +
1.216 + /**
1.217 + * Handy accessors to the top element.
1.218 + */
1.219 + Link& GetTop() { return mLink[mLink.Length() - 1]; }
1.220 + const Link& GetTop() const { return mLink[mLink.Length() - 1]; }
1.221 +
1.222 + public:
1.223 + iterator() : mRowIndex(-1) {}
1.224 +
1.225 + iterator(const iterator& aIterator);
1.226 + iterator& operator=(const iterator& aIterator);
1.227 +
1.228 + bool operator==(const iterator& aIterator) const;
1.229 +
1.230 + bool operator!=(const iterator& aIterator) const {
1.231 + return !aIterator.operator==(*this); }
1.232 +
1.233 + const Row& operator*() const { return GetTop().GetRow(); }
1.234 + Row& operator*() { return GetTop().GetRow(); }
1.235 +
1.236 + const Row* operator->() const { return &(GetTop().GetRow()); }
1.237 + Row* operator->() { return &(GetTop().GetRow()); }
1.238 +
1.239 + iterator& operator++() { Next(); return *this; }
1.240 + iterator operator++(int) { iterator temp(*this); Next(); return temp; }
1.241 + iterator& operator--() { Prev(); return *this; }
1.242 + iterator operator--(int) { iterator temp(*this); Prev(); return temp; }
1.243 +
1.244 + /**
1.245 + * Return the current parent link
1.246 + */
1.247 + Subtree* GetParent() { return GetTop().GetParent(); }
1.248 +
1.249 + const Subtree* GetParent() const { return GetTop().GetParent(); }
1.250 +
1.251 + /**
1.252 + * Return the current child index
1.253 + */
1.254 + int32_t GetChildIndex() const { return GetTop().GetChildIndex(); }
1.255 +
1.256 + /**
1.257 + * Return the depth of the path the iterator is maintaining
1.258 + * into the tree.
1.259 + */
1.260 + int32_t GetDepth() const { return mLink.Length(); }
1.261 +
1.262 + /**
1.263 + * Return the current row index of the iterator
1.264 + */
1.265 + int32_t GetRowIndex() const { return mRowIndex; }
1.266 +
1.267 + /**
1.268 + * Pop the iterator up a level.
1.269 + */
1.270 + iterator& Pop() { mLink.SetLength(GetDepth() - 1); return *this; }
1.271 + };
1.272 +
1.273 + /**
1.274 + * Retrieve the first element in the view
1.275 + */
1.276 + iterator First();
1.277 +
1.278 + /**
1.279 + * Retrieve (one past) the last element in the view
1.280 + */
1.281 + iterator Last();
1.282 +
1.283 + /**
1.284 + * Find the row that contains the given resource
1.285 + */
1.286 + iterator FindByResource(nsIRDFResource* aResource);
1.287 +
1.288 + /**
1.289 + * Find the row that contains the result
1.290 + */
1.291 + iterator Find(nsIXULTemplateResult* aResult);
1.292 +
1.293 + /**
1.294 + * Retrieve the ith element in the view
1.295 + */
1.296 + iterator operator[](int32_t aIndex);
1.297 +
1.298 + nsTreeRows() : mRoot(nullptr) {}
1.299 + ~nsTreeRows() {}
1.300 +
1.301 + /**
1.302 + * Ensure that a child subtree exists within the specified parent
1.303 + * at the specified child index within the parent. (In other
1.304 + * words, create a subtree if one doesn't already exist.)
1.305 + */
1.306 + Subtree*
1.307 + EnsureSubtreeFor(Subtree* aParent, int32_t aChildIndex);
1.308 +
1.309 + /**
1.310 + * Ensure that a child subtree exists at the iterator's position.
1.311 + */
1.312 + Subtree*
1.313 + EnsureSubtreeFor(iterator& aIterator) {
1.314 + return EnsureSubtreeFor(aIterator.GetParent(),
1.315 + aIterator.GetChildIndex()); }
1.316 +
1.317 + /**
1.318 + * Get the child subtree for the specified parent at the specified
1.319 + * child index. Optionally return the child subtree's size. Will
1.320 + * return `null' if no subtree exists.
1.321 + */
1.322 + Subtree*
1.323 + GetSubtreeFor(const Subtree* aParent,
1.324 + int32_t aChildIndex,
1.325 + int32_t* aSubtreeSize = nullptr);
1.326 +
1.327 + /**
1.328 + * Retrieve the size of the subtree within the specified parent.
1.329 + */
1.330 + int32_t
1.331 + GetSubtreeSizeFor(const Subtree* aParent,
1.332 + int32_t aChildIndex) {
1.333 + int32_t size;
1.334 + GetSubtreeFor(aParent, aChildIndex, &size);
1.335 + return size; }
1.336 +
1.337 + /**
1.338 + * Retrieve the size of the subtree within the specified parent.
1.339 + */
1.340 + int32_t
1.341 + GetSubtreeSizeFor(const iterator& aIterator) {
1.342 + int32_t size;
1.343 + GetSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex(), &size);
1.344 + return size; }
1.345 +
1.346 + /**
1.347 + * Remove the specified subtree for a row, leaving the row itself
1.348 + * intact.
1.349 + */
1.350 + void
1.351 + RemoveSubtreeFor(Subtree* aParent, int32_t aChildIndex);
1.352 +
1.353 + /**
1.354 + * Remove the specified subtree for a row, leaving the row itself
1.355 + * intact.
1.356 + */
1.357 + void
1.358 + RemoveSubtreeFor(iterator& aIterator) {
1.359 + RemoveSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex()); }
1.360 +
1.361 + /**
1.362 + * Remove the specified row from the view
1.363 + */
1.364 + int32_t
1.365 + RemoveRowAt(iterator& aIterator) {
1.366 + iterator temp = aIterator--;
1.367 + Subtree* parent = temp.GetParent();
1.368 + parent->RemoveRowAt(temp.GetChildIndex());
1.369 + InvalidateCachedRow();
1.370 + return parent->Count(); }
1.371 +
1.372 + /**
1.373 + * Insert a new match into the view
1.374 + */
1.375 + iterator
1.376 + InsertRowAt(nsTemplateMatch* aMatch, Subtree* aSubtree, int32_t aChildIndex) {
1.377 + InvalidateCachedRow();
1.378 + return aSubtree->InsertRowAt(aMatch, aChildIndex); }
1.379 +
1.380 + /**
1.381 + * Raw access to the rows; e.g., for sorting.
1.382 + */
1.383 + Row*
1.384 + GetRowsFor(Subtree* aSubtree) { return aSubtree->mRows; }
1.385 +
1.386 + /**
1.387 + * Remove all of the rows
1.388 + */
1.389 + void Clear();
1.390 +
1.391 + /**
1.392 + * Return the total number of rows in the tree view.
1.393 + */
1.394 + int32_t Count() const { return mRoot.GetSubtreeSize(); }
1.395 +
1.396 + /**
1.397 + * Retrieve the root subtree
1.398 + */
1.399 + Subtree* GetRoot() { return &mRoot; }
1.400 +
1.401 + /**
1.402 + * Set the root resource for the view
1.403 + */
1.404 + void SetRootResource(nsIRDFResource* aResource) {
1.405 + mRootResource = aResource; }
1.406 +
1.407 + /**
1.408 + * Retrieve the root resource for the view
1.409 + */
1.410 + nsIRDFResource* GetRootResource() {
1.411 + return mRootResource.get(); }
1.412 +
1.413 + /**
1.414 + * Invalidate the cached row; e.g., because the view has changed
1.415 + * in a way that would corrupt the iterator.
1.416 + */
1.417 + void
1.418 + InvalidateCachedRow() { mLastRow = iterator(); }
1.419 +
1.420 +protected:
1.421 + /**
1.422 + * The root subtree.
1.423 + */
1.424 + Subtree mRoot;
1.425 +
1.426 + /**
1.427 + * The root resource for the view
1.428 + */
1.429 + nsCOMPtr<nsIRDFResource> mRootResource;
1.430 +
1.431 + /**
1.432 + * The last row that was asked for by operator[]. By remembering
1.433 + * this, we can usually avoid the O(n) search through the row
1.434 + * array to find the row at the specified index.
1.435 + */
1.436 + iterator mLastRow;
1.437 +};
1.438 +
1.439 +
1.440 +#endif // nsTreeRows_h__
