Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /* This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #ifndef nsTreeRows_h__
7 : #define nsTreeRows_h__
8 :
9 : #include "nsCOMPtr.h"
10 : #include "nsTArray.h"
11 : #include "PLDHashTable.h"
12 : #include "nsIXULTemplateResult.h"
13 : #include "nsIRDFResource.h"
14 :
15 : class nsTemplateMatch;
16 :
17 : /**
18 : * This class maintains the state of the XUL tree builder's
19 : * rows. It maps a row number to the nsTemplateMatch object that
20 : * populates the row.
21 : */
22 : class nsTreeRows
23 : {
24 : public:
25 : class iterator;
26 : friend class iterator;
27 :
28 : enum Direction { eDirection_Forwards = +1, eDirection_Backwards = -1 };
29 :
30 : enum ContainerType {
31 : eContainerType_Unknown = 0,
32 : eContainerType_Noncontainer = 1,
33 : eContainerType_Container = 2
34 : };
35 :
36 : enum ContainerState {
37 : eContainerState_Unknown = 0,
38 : eContainerState_Open = 1,
39 : eContainerState_Closed = 2
40 : };
41 :
42 : enum ContainerFill {
43 : eContainerFill_Unknown = 0,
44 : eContainerFill_Empty = 1,
45 : eContainerFill_Nonempty = 2
46 : };
47 :
48 : class Subtree;
49 :
50 : /**
51 : * A row in the tree. Contains the match that the row
52 : * corresponds to, and a pointer to the row's subtree, if there
53 : * are any.
54 : */
55 : struct Row {
56 : nsTemplateMatch* mMatch;
57 : ContainerType mContainerType : 4;
58 : ContainerState mContainerState : 4;
59 : ContainerFill mContainerFill : 4;
60 :
61 : Subtree* mSubtree; // XXX eventually move to hashtable
62 : };
63 :
64 : /**
65 : * A subtree in the tree. A subtree contains rows, which may
66 : * contain other subtrees.
67 : */
68 : class Subtree {
69 : protected:
70 : friend class nsTreeRows; // so that it can access members, for now
71 :
72 : /**
73 : * The parent subtree; null if we're the root
74 : */
75 : Subtree* mParent;
76 :
77 : /**
78 : * The number of immediate children in this subtree
79 : */
80 : int32_t mCount;
81 :
82 : /**
83 : * The capacity of the subtree
84 : */
85 : int32_t mCapacity;
86 :
87 : /**
88 : * The total number of rows in this subtree, recursively
89 : * including child subtrees.
90 : */
91 : int32_t mSubtreeSize;
92 :
93 : /**
94 : * The array of rows in the subtree
95 : */
96 : Row* mRows;
97 :
98 : public:
99 : /**
100 : * Creates a subtree with the specified parent.
101 : */
102 0 : explicit Subtree(Subtree* aParent)
103 0 : : mParent(aParent),
104 : mCount(0),
105 : mCapacity(0),
106 : mSubtreeSize(0),
107 0 : mRows(nullptr) {}
108 :
109 : ~Subtree();
110 :
111 : /**
112 : * Return the number of immediate child rows in the subtree
113 : */
114 0 : int32_t Count() const { return mCount; }
115 :
116 : /**
117 : * Return the number of rows in this subtree, as well as all
118 : * the subtrees it contains.
119 : */
120 0 : int32_t GetSubtreeSize() const { return mSubtreeSize; }
121 :
122 : /**
123 : * Retrieve the immediate child row at the specified index.
124 : */
125 0 : const Row& operator[](int32_t aIndex) const {
126 0 : NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
127 0 : return mRows[aIndex]; }
128 :
129 : /**
130 : * Retrieve the immediate row at the specified index.
131 : */
132 0 : Row& operator[](int32_t aIndex) {
133 0 : NS_PRECONDITION(aIndex >= 0 && aIndex < mCount, "bad index");
134 0 : return mRows[aIndex]; }
135 :
136 : /**
137 : * Remove all rows from the subtree.
138 : */
139 : void Clear();
140 :
141 : protected:
142 : /**
143 : * Insert an immediate child row at the specified index.
144 : */
145 : iterator InsertRowAt(nsTemplateMatch* aMatch, int32_t aIndex);
146 :
147 : /**
148 : * Remove an immediate child row from the specified index.
149 : */
150 : void RemoveRowAt(int32_t aChildIndex);
151 : };
152 :
153 : friend class Subtree;
154 :
155 : protected:
156 : /**
157 : * A link in the path through the view's tree.
158 : */
159 : struct Link {
160 : Subtree* mParent;
161 : int32_t mChildIndex;
162 :
163 : Link&
164 : operator=(const Link& aLink) {
165 : mParent = aLink.mParent;
166 : mChildIndex = aLink.mChildIndex;
167 : return *this; }
168 :
169 : bool
170 0 : operator==(const Link& aLink) const {
171 0 : return (mParent == aLink.mParent)
172 0 : && (mChildIndex == aLink.mChildIndex); }
173 :
174 0 : Subtree* GetParent() { return mParent; }
175 0 : const Subtree* GetParent() const { return mParent; }
176 :
177 0 : int32_t GetChildIndex() const { return mChildIndex; }
178 :
179 0 : Row& GetRow() { return (*mParent)[mChildIndex]; }
180 : const Row& GetRow() const { return (*mParent)[mChildIndex]; }
181 : };
182 :
183 : public:
184 : /**
185 : * An iterator that can be used to traverse the tree view.
186 : */
187 0 : class iterator {
188 : protected:
189 : int32_t mRowIndex;
190 : AutoTArray<Link, 8> mLink;
191 :
192 : void Next();
193 : void Prev();
194 :
195 : friend class Subtree; // so InsertRowAt can initialize us
196 : friend class nsTreeRows; // so nsTreeRows can initialize us
197 :
198 : /**
199 : * Used by operator[]() to initialize an iterator.
200 : */
201 : void Append(Subtree* aParent, int32_t aChildIndex);
202 :
203 : /**
204 : * Used by InsertRowAt() to initialize an iterator.
205 : */
206 : void Push(Subtree *aParent, int32_t aChildIndex);
207 :
208 : /**
209 : * Used by operator[]() and InsertRowAt() to initialize an iterator.
210 : */
211 0 : void SetRowIndex(int32_t aRowIndex) { mRowIndex = aRowIndex; }
212 :
213 : /**
214 : * Handy accessors to the top element.
215 : */
216 0 : Link& GetTop() { return mLink[mLink.Length() - 1]; }
217 0 : const Link& GetTop() const { return mLink[mLink.Length() - 1]; }
218 :
219 : public:
220 0 : iterator() : mRowIndex(-1) {}
221 :
222 : iterator(const iterator& aIterator);
223 : iterator& operator=(const iterator& aIterator);
224 :
225 : bool operator==(const iterator& aIterator) const;
226 :
227 0 : bool operator!=(const iterator& aIterator) const {
228 0 : return !aIterator.operator==(*this); }
229 :
230 : const Row& operator*() const { return GetTop().GetRow(); }
231 0 : Row& operator*() { return GetTop().GetRow(); }
232 :
233 : const Row* operator->() const { return &(GetTop().GetRow()); }
234 0 : Row* operator->() { return &(GetTop().GetRow()); }
235 :
236 0 : iterator& operator++() { Next(); return *this; }
237 : iterator operator++(int) { iterator temp(*this); Next(); return temp; }
238 0 : iterator& operator--() { Prev(); return *this; }
239 0 : iterator operator--(int) { iterator temp(*this); Prev(); return temp; }
240 :
241 : /**
242 : * Return the current parent link
243 : */
244 0 : Subtree* GetParent() { return GetTop().GetParent(); }
245 :
246 0 : const Subtree* GetParent() const { return GetTop().GetParent(); }
247 :
248 : /**
249 : * Return the current child index
250 : */
251 0 : int32_t GetChildIndex() const { return GetTop().GetChildIndex(); }
252 :
253 : /**
254 : * Return the depth of the path the iterator is maintaining
255 : * into the tree.
256 : */
257 0 : int32_t GetDepth() const { return mLink.Length(); }
258 :
259 : /**
260 : * Return the current row index of the iterator
261 : */
262 0 : int32_t GetRowIndex() const { return mRowIndex; }
263 :
264 : /**
265 : * Pop the iterator up a level.
266 : */
267 0 : iterator& Pop() { mLink.SetLength(GetDepth() - 1); return *this; }
268 : };
269 :
270 : /**
271 : * Retrieve the first element in the view
272 : */
273 : iterator First();
274 :
275 : /**
276 : * Retrieve (one past) the last element in the view
277 : */
278 : iterator Last();
279 :
280 : /**
281 : * Find the row that contains the given resource
282 : */
283 : iterator FindByResource(nsIRDFResource* aResource);
284 :
285 : /**
286 : * Find the row that contains the result
287 : */
288 : iterator Find(nsIXULTemplateResult* aResult);
289 :
290 : /**
291 : * Retrieve the ith element in the view
292 : */
293 : iterator operator[](int32_t aIndex);
294 :
295 0 : nsTreeRows() : mRoot(nullptr) {}
296 0 : ~nsTreeRows() {}
297 :
298 : /**
299 : * Ensure that a child subtree exists within the specified parent
300 : * at the specified child index within the parent. (In other
301 : * words, create a subtree if one doesn't already exist.)
302 : */
303 : Subtree*
304 : EnsureSubtreeFor(Subtree* aParent, int32_t aChildIndex);
305 :
306 : /**
307 : * Ensure that a child subtree exists at the iterator's position.
308 : */
309 : Subtree*
310 0 : EnsureSubtreeFor(iterator& aIterator) {
311 0 : return EnsureSubtreeFor(aIterator.GetParent(),
312 0 : aIterator.GetChildIndex()); }
313 :
314 : /**
315 : * Get the child subtree for the specified parent at the specified
316 : * child index. Optionally return the child subtree's size. Will
317 : * return `null' if no subtree exists.
318 : */
319 : Subtree*
320 : GetSubtreeFor(const Subtree* aParent,
321 : int32_t aChildIndex,
322 : int32_t* aSubtreeSize = nullptr);
323 :
324 : /**
325 : * Retrieve the size of the subtree within the specified parent.
326 : */
327 : int32_t
328 0 : GetSubtreeSizeFor(const Subtree* aParent,
329 : int32_t aChildIndex) {
330 : int32_t size;
331 0 : GetSubtreeFor(aParent, aChildIndex, &size);
332 0 : return size; }
333 :
334 : /**
335 : * Retrieve the size of the subtree within the specified parent.
336 : */
337 : int32_t
338 0 : GetSubtreeSizeFor(const iterator& aIterator) {
339 : int32_t size;
340 0 : GetSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex(), &size);
341 0 : return size; }
342 :
343 : /**
344 : * Remove the specified subtree for a row, leaving the row itself
345 : * intact.
346 : */
347 : void
348 : RemoveSubtreeFor(Subtree* aParent, int32_t aChildIndex);
349 :
350 : /**
351 : * Remove the specified subtree for a row, leaving the row itself
352 : * intact.
353 : */
354 : void
355 0 : RemoveSubtreeFor(iterator& aIterator) {
356 0 : RemoveSubtreeFor(aIterator.GetParent(), aIterator.GetChildIndex()); }
357 :
358 : /**
359 : * Remove the specified row from the view
360 : */
361 : int32_t
362 0 : RemoveRowAt(iterator& aIterator) {
363 0 : iterator temp = aIterator--;
364 0 : Subtree* parent = temp.GetParent();
365 0 : parent->RemoveRowAt(temp.GetChildIndex());
366 0 : InvalidateCachedRow();
367 0 : return parent->Count(); }
368 :
369 : /**
370 : * Insert a new match into the view
371 : */
372 : iterator
373 0 : InsertRowAt(nsTemplateMatch* aMatch, Subtree* aSubtree, int32_t aChildIndex) {
374 0 : InvalidateCachedRow();
375 0 : return aSubtree->InsertRowAt(aMatch, aChildIndex); }
376 :
377 : /**
378 : * Raw access to the rows; e.g., for sorting.
379 : */
380 : Row*
381 0 : GetRowsFor(Subtree* aSubtree) { return aSubtree->mRows; }
382 :
383 : /**
384 : * Remove all of the rows
385 : */
386 : void Clear();
387 :
388 : /**
389 : * Return the total number of rows in the tree view.
390 : */
391 0 : int32_t Count() const { return mRoot.GetSubtreeSize(); }
392 :
393 : /**
394 : * Retrieve the root subtree
395 : */
396 0 : Subtree* GetRoot() { return &mRoot; }
397 :
398 : /**
399 : * Set the root resource for the view
400 : */
401 0 : void SetRootResource(nsIRDFResource* aResource) {
402 0 : mRootResource = aResource; }
403 :
404 : /**
405 : * Retrieve the root resource for the view
406 : */
407 0 : nsIRDFResource* GetRootResource() {
408 0 : return mRootResource.get(); }
409 :
410 : /**
411 : * Invalidate the cached row; e.g., because the view has changed
412 : * in a way that would corrupt the iterator.
413 : */
414 : void
415 0 : InvalidateCachedRow() { mLastRow = iterator(); }
416 :
417 : protected:
418 : /**
419 : * The root subtree.
420 : */
421 : Subtree mRoot;
422 :
423 : /**
424 : * The root resource for the view
425 : */
426 : nsCOMPtr<nsIRDFResource> mRootResource;
427 :
428 : /**
429 : * The last row that was asked for by operator[]. By remembering
430 : * this, we can usually avoid the O(n) search through the row
431 : * array to find the row at the specified index.
432 : */
433 : iterator mLastRow;
434 : };
435 :
436 :
437 : #endif // nsTreeRows_h__
|
