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 : #include "nsString.h"
7 : #include "nsTreeRows.h"
8 : #include <algorithm>
9 :
10 : nsTreeRows::Subtree*
11 0 : nsTreeRows::EnsureSubtreeFor(Subtree* aParent,
12 : int32_t aChildIndex)
13 : {
14 0 : Subtree* subtree = GetSubtreeFor(aParent, aChildIndex);
15 :
16 0 : if (! subtree) {
17 0 : subtree = aParent->mRows[aChildIndex].mSubtree = new Subtree(aParent);
18 0 : InvalidateCachedRow();
19 : }
20 :
21 0 : return subtree;
22 : }
23 :
24 : nsTreeRows::Subtree*
25 0 : nsTreeRows::GetSubtreeFor(const Subtree* aParent,
26 : int32_t aChildIndex,
27 : int32_t* aSubtreeSize)
28 : {
29 0 : NS_PRECONDITION(aParent, "no parent");
30 0 : NS_PRECONDITION(aChildIndex >= 0, "bad child index");
31 :
32 0 : Subtree* result = nullptr;
33 :
34 0 : if (aChildIndex < aParent->mCount)
35 0 : result = aParent->mRows[aChildIndex].mSubtree;
36 :
37 0 : if (aSubtreeSize)
38 0 : *aSubtreeSize = result ? result->mSubtreeSize : 0;
39 :
40 0 : return result;
41 : }
42 :
43 : void
44 0 : nsTreeRows::RemoveSubtreeFor(Subtree* aParent, int32_t aChildIndex)
45 : {
46 0 : NS_PRECONDITION(aParent, "no parent");
47 0 : NS_PRECONDITION(aChildIndex >= 0 && aChildIndex < aParent->mCount, "bad child index");
48 :
49 0 : Row& row = aParent->mRows[aChildIndex];
50 :
51 0 : if (row.mSubtree) {
52 0 : int32_t subtreeSize = row.mSubtree->GetSubtreeSize();
53 :
54 0 : delete row.mSubtree;
55 0 : row.mSubtree = nullptr;
56 :
57 0 : for (Subtree* subtree = aParent; subtree != nullptr; subtree = subtree->mParent)
58 0 : subtree->mSubtreeSize -= subtreeSize;
59 : }
60 :
61 0 : InvalidateCachedRow();
62 0 : }
63 :
64 : nsTreeRows::iterator
65 0 : nsTreeRows::First()
66 : {
67 0 : iterator result;
68 0 : result.Append(&mRoot, 0);
69 0 : result.SetRowIndex(0);
70 0 : return result;
71 : }
72 :
73 : nsTreeRows::iterator
74 0 : nsTreeRows::Last()
75 : {
76 0 : iterator result;
77 :
78 : // Build up a path along the rightmost edge of the tree
79 0 : Subtree* current = &mRoot;
80 0 : int32_t count = current->Count();
81 0 : do {
82 0 : int32_t last = count - 1;
83 0 : result.Append(current, last);
84 0 : current = count ? GetSubtreeFor(current, last) : nullptr;
85 0 : } while (current && ((count = current->Count()) != 0));
86 :
87 : // Now, at the bottom rightmost leaf, advance us one off the end.
88 0 : result.GetTop().mChildIndex++;
89 :
90 : // Our row index will be the size of the root subree, plus one.
91 0 : result.SetRowIndex(mRoot.GetSubtreeSize() + 1);
92 :
93 0 : return result;
94 : }
95 :
96 : nsTreeRows::iterator
97 0 : nsTreeRows::operator[](int32_t aRow)
98 : {
99 : // See if we're just lucky, and end up with something
100 : // nearby. (This tends to happen a lot due to the way that we get
101 : // asked for rows n' stuff.)
102 0 : int32_t last = mLastRow.GetRowIndex();
103 0 : if (last != -1) {
104 0 : if (aRow == last)
105 0 : return mLastRow;
106 0 : else if (last + 1 == aRow)
107 0 : return ++mLastRow;
108 0 : else if (last - 1 == aRow)
109 0 : return --mLastRow;
110 : }
111 :
112 : // Nope. Construct a path to the specified index. This is a little
113 : // bit better than O(n), because we can skip over subtrees. (So it
114 : // ends up being approximately linear in the subtree size, instead
115 : // of the entire view size. But, most of the time, big views are
116 : // flat. Oh well.)
117 0 : iterator result;
118 0 : Subtree* current = &mRoot;
119 :
120 0 : int32_t index = 0;
121 0 : result.SetRowIndex(aRow);
122 :
123 0 : do {
124 : int32_t subtreeSize;
125 0 : Subtree* subtree = GetSubtreeFor(current, index, &subtreeSize);
126 :
127 0 : if (subtreeSize >= aRow) {
128 0 : result.Append(current, index);
129 0 : current = subtree;
130 0 : index = 0;
131 0 : --aRow;
132 : }
133 : else {
134 0 : ++index;
135 0 : aRow -= subtreeSize + 1;
136 : }
137 0 : } while (aRow >= 0);
138 :
139 0 : mLastRow = result;
140 0 : return result;
141 : }
142 :
143 : nsTreeRows::iterator
144 0 : nsTreeRows::FindByResource(nsIRDFResource* aResource)
145 : {
146 : // XXX Mmm, scan through the rows one-by-one...
147 0 : iterator last = Last();
148 0 : iterator iter;
149 :
150 : nsresult rv;
151 0 : nsAutoString resourceid;
152 0 : bool stringmode = false;
153 :
154 0 : for (iter = First(); iter != last; ++iter) {
155 0 : if (!stringmode) {
156 0 : nsCOMPtr<nsIRDFResource> findres;
157 0 : rv = iter->mMatch->mResult->GetResource(getter_AddRefs(findres));
158 0 : if (NS_FAILED(rv)) return last;
159 :
160 0 : if (findres == aResource)
161 0 : break;
162 :
163 0 : if (! findres) {
164 : const char *uri;
165 0 : aResource->GetValueConst(&uri);
166 0 : CopyUTF8toUTF16(uri, resourceid);
167 :
168 : // set stringmode and fall through
169 0 : stringmode = true;
170 : }
171 : }
172 :
173 : // additional check because previous block could change stringmode
174 0 : if (stringmode) {
175 0 : nsAutoString findid;
176 0 : rv = iter->mMatch->mResult->GetId(findid);
177 0 : if (NS_FAILED(rv)) return last;
178 :
179 0 : if (resourceid.Equals(findid))
180 0 : break;
181 : }
182 : }
183 :
184 0 : return iter;
185 : }
186 :
187 : nsTreeRows::iterator
188 0 : nsTreeRows::Find(nsIXULTemplateResult *aResult)
189 : {
190 : // XXX Mmm, scan through the rows one-by-one...
191 0 : iterator last = Last();
192 0 : iterator iter;
193 :
194 0 : for (iter = First(); iter != last; ++iter) {
195 0 : if (aResult == iter->mMatch->mResult)
196 0 : break;
197 : }
198 :
199 0 : return iter;
200 : }
201 :
202 : void
203 0 : nsTreeRows::Clear()
204 : {
205 0 : mRoot.Clear();
206 0 : InvalidateCachedRow();
207 0 : }
208 :
209 : //----------------------------------------------------------------------
210 : //
211 : // nsTreeRows::Subtree
212 : //
213 :
214 0 : nsTreeRows::Subtree::~Subtree()
215 : {
216 0 : Clear();
217 0 : }
218 :
219 : void
220 0 : nsTreeRows::Subtree::Clear()
221 : {
222 0 : for (int32_t i = mCount - 1; i >= 0; --i)
223 0 : delete mRows[i].mSubtree;
224 :
225 0 : delete[] mRows;
226 :
227 0 : mRows = nullptr;
228 0 : mCount = mCapacity = mSubtreeSize = 0;
229 0 : }
230 :
231 : nsTreeRows::iterator
232 0 : nsTreeRows::Subtree::InsertRowAt(nsTemplateMatch* aMatch, int32_t aIndex)
233 : {
234 0 : if (mCount >= mCapacity || aIndex >= mCapacity) {
235 0 : int32_t newCapacity = std::max(mCapacity * 2, aIndex + 1);
236 0 : Row* newRows = new Row[newCapacity];
237 0 : if (! newRows)
238 0 : return iterator();
239 :
240 0 : for (int32_t i = mCount - 1; i >= 0; --i)
241 0 : newRows[i] = mRows[i];
242 :
243 0 : delete[] mRows;
244 :
245 0 : mRows = newRows;
246 0 : mCapacity = newCapacity;
247 : }
248 :
249 0 : for (int32_t i = mCount - 1; i >= aIndex; --i)
250 0 : mRows[i + 1] = mRows[i];
251 :
252 0 : mRows[aIndex].mMatch = aMatch;
253 0 : mRows[aIndex].mContainerType = eContainerType_Unknown;
254 0 : mRows[aIndex].mContainerState = eContainerState_Unknown;
255 0 : mRows[aIndex].mContainerFill = eContainerFill_Unknown;
256 0 : mRows[aIndex].mSubtree = nullptr;
257 0 : ++mCount;
258 :
259 : // Now build an iterator that points to the newly inserted element.
260 0 : int32_t rowIndex = 0;
261 0 : iterator result;
262 0 : result.Push(this, aIndex);
263 :
264 0 : for ( ; --aIndex >= 0; ++rowIndex) {
265 : // Account for open subtrees in the absolute row index.
266 0 : const Subtree *subtree = mRows[aIndex].mSubtree;
267 0 : if (subtree)
268 0 : rowIndex += subtree->mSubtreeSize;
269 : }
270 :
271 0 : Subtree *subtree = this;
272 : do {
273 : // Note that the subtree's size has expanded.
274 0 : ++subtree->mSubtreeSize;
275 :
276 0 : Subtree *parent = subtree->mParent;
277 0 : if (! parent)
278 0 : break;
279 :
280 : // Account for open subtrees in the absolute row index.
281 0 : int32_t count = parent->Count();
282 0 : for (aIndex = 0; aIndex < count; ++aIndex, ++rowIndex) {
283 0 : const Subtree *child = (*parent)[aIndex].mSubtree;
284 0 : if (subtree == child)
285 0 : break;
286 :
287 0 : if (child)
288 0 : rowIndex += child->mSubtreeSize;
289 : }
290 :
291 0 : NS_ASSERTION(aIndex < count, "couldn't find subtree in parent");
292 :
293 0 : result.Push(parent, aIndex);
294 0 : subtree = parent;
295 0 : ++rowIndex; // One for the parent row.
296 : } while (1);
297 :
298 0 : result.SetRowIndex(rowIndex);
299 0 : return result;
300 : }
301 :
302 : void
303 0 : nsTreeRows::Subtree::RemoveRowAt(int32_t aIndex)
304 : {
305 0 : NS_PRECONDITION(aIndex >= 0 && aIndex < Count(), "bad index");
306 0 : if (aIndex < 0 || aIndex >= Count())
307 0 : return;
308 :
309 : // How big is the subtree we're going to be removing?
310 0 : int32_t subtreeSize = mRows[aIndex].mSubtree
311 0 : ? mRows[aIndex].mSubtree->GetSubtreeSize()
312 0 : : 0;
313 :
314 0 : ++subtreeSize;
315 :
316 0 : delete mRows[aIndex].mSubtree;
317 :
318 0 : for (int32_t i = aIndex + 1; i < mCount; ++i)
319 0 : mRows[i - 1] = mRows[i];
320 :
321 0 : --mCount;
322 :
323 0 : for (Subtree* subtree = this; subtree != nullptr; subtree = subtree->mParent)
324 0 : subtree->mSubtreeSize -= subtreeSize;
325 : }
326 :
327 : //----------------------------------------------------------------------
328 : //
329 : // nsTreeRows::iterator
330 : //
331 :
332 0 : nsTreeRows::iterator::iterator(const iterator& aIterator)
333 0 : : mRowIndex(aIterator.mRowIndex),
334 0 : mLink(aIterator.mLink)
335 : {
336 0 : }
337 :
338 : nsTreeRows::iterator&
339 0 : nsTreeRows::iterator::operator=(const iterator& aIterator)
340 : {
341 0 : mRowIndex = aIterator.mRowIndex;
342 0 : mLink = aIterator.mLink;
343 0 : return *this;
344 : }
345 :
346 : void
347 0 : nsTreeRows::iterator::Append(Subtree* aParent, int32_t aChildIndex)
348 : {
349 0 : Link *link = mLink.AppendElement();
350 0 : if (link) {
351 0 : link->mParent = aParent;
352 0 : link->mChildIndex = aChildIndex;
353 : }
354 : else
355 0 : NS_ERROR("out of memory");
356 0 : }
357 :
358 : void
359 0 : nsTreeRows::iterator::Push(Subtree *aParent, int32_t aChildIndex)
360 : {
361 0 : Link *link = mLink.InsertElementAt(0);
362 0 : if (link) {
363 0 : link->mParent = aParent;
364 0 : link->mChildIndex = aChildIndex;
365 : }
366 : else
367 0 : NS_ERROR("out of memory");
368 0 : }
369 :
370 : bool
371 0 : nsTreeRows::iterator::operator==(const iterator& aIterator) const
372 : {
373 0 : if (GetDepth() != aIterator.GetDepth())
374 0 : return false;
375 :
376 0 : if (GetDepth() == 0)
377 0 : return true;
378 :
379 0 : return GetTop() == aIterator.GetTop();
380 : }
381 :
382 : void
383 0 : nsTreeRows::iterator::Next()
384 : {
385 0 : NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");
386 :
387 : // Increment the absolute row index
388 0 : ++mRowIndex;
389 :
390 0 : Link& top = GetTop();
391 :
392 : // Is there a child subtree? If so, descend into the child
393 : // subtree.
394 0 : Subtree* subtree = top.GetRow().mSubtree;
395 :
396 0 : if (subtree && subtree->Count()) {
397 0 : Append(subtree, 0);
398 0 : return;
399 : }
400 :
401 : // Have we exhausted the current subtree?
402 0 : if (top.mChildIndex >= top.mParent->Count() - 1) {
403 : // Yep. See if we've just iterated path the last element in
404 : // the tree, period. Walk back up the stack, looking for any
405 : // unfinished subtrees.
406 : int32_t unfinished;
407 0 : for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {
408 0 : const Link& link = mLink[unfinished];
409 0 : if (link.mChildIndex < link.mParent->Count() - 1)
410 0 : break;
411 : }
412 :
413 : // If there are no unfinished subtrees in the stack, then this
414 : // iterator is exhausted. Leave it in the same state that
415 : // Last() does.
416 0 : if (unfinished < 0) {
417 0 : top.mChildIndex++;
418 0 : return;
419 : }
420 :
421 : // Otherwise, we ran off the end of one of the inner
422 : // subtrees. Pop up to the next unfinished level in the stack.
423 0 : mLink.SetLength(unfinished + 1);
424 : }
425 :
426 : // Advance to the next child in this subtree
427 0 : ++(GetTop().mChildIndex);
428 : }
429 :
430 : void
431 0 : nsTreeRows::iterator::Prev()
432 : {
433 0 : NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");
434 :
435 : // Decrement the absolute row index
436 0 : --mRowIndex;
437 :
438 : // Move to the previous child in this subtree
439 0 : --(GetTop().mChildIndex);
440 :
441 : // Have we exhausted the current subtree?
442 0 : if (GetTop().mChildIndex < 0) {
443 : // Yep. See if we've just iterated back to the first element
444 : // in the tree, period. Walk back up the stack, looking for
445 : // any unfinished subtrees.
446 : int32_t unfinished;
447 0 : for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {
448 0 : const Link& link = mLink[unfinished];
449 0 : if (link.mChildIndex >= 0)
450 0 : break;
451 : }
452 :
453 : // If there are no unfinished subtrees in the stack, then this
454 : // iterator is exhausted. Leave it in the same state that
455 : // First() does.
456 0 : if (unfinished < 0)
457 0 : return;
458 :
459 : // Otherwise, we ran off the end of one of the inner
460 : // subtrees. Pop up to the next unfinished level in the stack.
461 0 : mLink.SetLength(unfinished + 1);
462 0 : return;
463 : }
464 :
465 : // Is there a child subtree immediately prior to our current
466 : // position? If so, descend into it, grovelling down to the
467 : // deepest, rightmost left edge.
468 0 : Subtree* parent = GetTop().GetParent();
469 0 : int32_t index = GetTop().GetChildIndex();
470 :
471 0 : Subtree* subtree = (*parent)[index].mSubtree;
472 :
473 0 : if (subtree && subtree->Count()) {
474 0 : do {
475 0 : index = subtree->Count() - 1;
476 0 : Append(subtree, index);
477 :
478 0 : parent = subtree;
479 0 : subtree = (*parent)[index].mSubtree;
480 0 : } while (subtree && subtree->Count());
481 : }
482 : }
|
