Coverage Report

Created: 2018-09-25 14:53

/src/mozilla-central/gfx/tests/gtest/TestTreeTraversal.cpp
Line
Count
Source (jump to first uncovered line)
1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
3
/* This Source Code Form is subject to the terms of the Mozilla Public
4
 * License, v. 2.0. If a copy of the MPL was not distributed with this
5
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7
#include <vector>
8
#include "mozilla/RefPtr.h"
9
#include "gtest/gtest.h"
10
#include "nsRegion.h"
11
#include "nsRect.h"
12
#include "TreeTraversal.h"
13
#include <stack>
14
#include <queue>
15
16
const int PERFORMANCE_TREE_DEPTH = 20;
17
const int PERFORMANCE_TREE_CHILD_COUNT = 2;
18
const int PERFORMANCE_TREE_LEAF_COUNT = 1048576; // 2 ** 20
19
const int PERFORMANCE_REGION_XWRAP = 1024;
20
21
using namespace mozilla::layers;
22
using namespace mozilla;
23
24
enum class SearchNodeType {Needle, Hay};
25
enum class ForEachNodeType {Continue, Skip};
26
27
template <class T>
28
class TestNodeBase {
29
  public:
30
    NS_INLINE_DECL_REFCOUNTING(TestNodeBase<T>);
31
    explicit TestNodeBase(T aType, int aExpectedTraversalRank = -1);
32
    explicit TestNodeBase();
33
    void SetActualTraversalRank(int aRank);
34
    void SetValue(int aValue);
35
    void SetType(T aType);
36
    void SetRegion(nsRegion aRegion);
37
    int GetExpectedTraversalRank();
38
    int GetActualTraversalRank();
39
    int GetValue();
40
    T GetType();
41
    nsRegion GetRegion();
42
    virtual bool IsLeaf() = 0;
43
  private:
44
    MOZ_INIT_OUTSIDE_CTOR int mExpectedTraversalRank;
45
    MOZ_INIT_OUTSIDE_CTOR int mActualTraversalRank;
46
    MOZ_INIT_OUTSIDE_CTOR int mValue;
47
    MOZ_INIT_OUTSIDE_CTOR nsRegion mRegion;
48
    MOZ_INIT_OUTSIDE_CTOR T mType;
49
  protected:
50
0
    virtual ~TestNodeBase<T>() {};
Unexecuted instantiation: TestNodeBase<SearchNodeType>::~TestNodeBase()
Unexecuted instantiation: TestNodeBase<ForEachNodeType>::~TestNodeBase()
51
};
52
53
template <class T>
54
class TestNodeReverse : public TestNodeBase<T> {
55
  public:
56
    explicit TestNodeReverse(T aType, int aExpectedTraversalRank = -1);
57
    explicit TestNodeReverse();
58
    void AddChild(RefPtr<TestNodeReverse<T>> aNode);
59
    TestNodeReverse<T>* GetLastChild();
60
    TestNodeReverse<T>* GetPrevSibling();
61
    bool IsLeaf();
62
  private:
63
    void SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode);
64
    void SetLastChild(RefPtr<TestNodeReverse<T>> aNode);
65
    RefPtr<TestNodeReverse<T>> mSiblingNode;
66
    RefPtr<TestNodeReverse<T>> mLastChildNode;
67
0
    ~TestNodeReverse<T>() {};
Unexecuted instantiation: TestNodeReverse<SearchNodeType>::~TestNodeReverse()
Unexecuted instantiation: TestNodeReverse<ForEachNodeType>::~TestNodeReverse()
68
};
69
70
template <class T>
71
class TestNodeForward : public TestNodeBase<T> {
72
  public:
73
    explicit TestNodeForward(T aType, int aExpectedTraversalRank = -1);
74
    explicit TestNodeForward();
75
    void AddChild(RefPtr<TestNodeForward<T>> aNode);
76
    TestNodeForward<T>* GetFirstChild();
77
    TestNodeForward<T>* GetNextSibling();
78
    bool IsLeaf();
79
  private:
80
    void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
81
    void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
82
    void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
83
    RefPtr<TestNodeForward<T>> mSiblingNode = nullptr;
84
    RefPtr<TestNodeForward<T>> mFirstChildNode = nullptr;
85
    // Track last child to facilitate appending children
86
    RefPtr<TestNodeForward<T>> mLastChildNode = nullptr;
87
0
    ~TestNodeForward<T>() {};
Unexecuted instantiation: TestNodeForward<SearchNodeType>::~TestNodeForward()
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::~TestNodeForward()
88
};
89
90
template <class T>
91
TestNodeReverse<T>::TestNodeReverse(T aType, int aExpectedTraversalRank) :
92
  TestNodeBase<T>(aType, aExpectedTraversalRank)
93
0
{
94
0
95
0
}
Unexecuted instantiation: TestNodeReverse<SearchNodeType>::TestNodeReverse(SearchNodeType, int)
Unexecuted instantiation: TestNodeReverse<ForEachNodeType>::TestNodeReverse(ForEachNodeType, int)
96
97
template <class T>
98
TestNodeReverse<T>::TestNodeReverse() :
99
  TestNodeBase<T>()
100
{
101
102
}
103
104
template <class T>
105
void TestNodeReverse<T>::SetLastChild(RefPtr<TestNodeReverse<T>> aNode)
106
0
{
107
0
  mLastChildNode = aNode;
108
0
}
Unexecuted instantiation: TestNodeReverse<SearchNodeType>::SetLastChild(RefPtr<TestNodeReverse<SearchNodeType> >)
Unexecuted instantiation: TestNodeReverse<ForEachNodeType>::SetLastChild(RefPtr<TestNodeReverse<ForEachNodeType> >)
109
110
template <class T>
111
void TestNodeReverse<T>::AddChild(RefPtr<TestNodeReverse<T>> aNode)
112
0
{
113
0
  aNode->SetPrevSibling(mLastChildNode);
114
0
  SetLastChild(aNode);
115
0
}
Unexecuted instantiation: TestNodeReverse<SearchNodeType>::AddChild(RefPtr<TestNodeReverse<SearchNodeType> >)
Unexecuted instantiation: TestNodeReverse<ForEachNodeType>::AddChild(RefPtr<TestNodeReverse<ForEachNodeType> >)
116
117
template <class T>
118
void TestNodeReverse<T>::SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode)
119
0
{
120
0
  mSiblingNode = aNode;
121
0
}
Unexecuted instantiation: TestNodeReverse<SearchNodeType>::SetPrevSibling(RefPtr<TestNodeReverse<SearchNodeType> >)
Unexecuted instantiation: TestNodeReverse<ForEachNodeType>::SetPrevSibling(RefPtr<TestNodeReverse<ForEachNodeType> >)
122
123
template <class T>
124
TestNodeReverse<T>* TestNodeReverse<T>::GetLastChild()
125
0
{
126
0
  return mLastChildNode;
127
0
}
Unexecuted instantiation: TestNodeReverse<SearchNodeType>::GetLastChild()
Unexecuted instantiation: TestNodeReverse<ForEachNodeType>::GetLastChild()
128
129
template <class T>
130
TestNodeReverse<T>* TestNodeReverse<T>::GetPrevSibling()
131
0
{
132
0
  return mSiblingNode;
133
0
}
Unexecuted instantiation: TestNodeReverse<SearchNodeType>::GetPrevSibling()
Unexecuted instantiation: TestNodeReverse<ForEachNodeType>::GetPrevSibling()
134
135
template <class T>
136
bool TestNodeReverse<T>::IsLeaf()
137
0
{
138
0
  return !mLastChildNode;
139
0
}
Unexecuted instantiation: TestNodeReverse<SearchNodeType>::IsLeaf()
Unexecuted instantiation: TestNodeReverse<ForEachNodeType>::IsLeaf()
140
141
template <class T>
142
TestNodeForward<T>::TestNodeForward(T aType, int aExpectedTraversalRank) :
143
  TestNodeBase<T>(aType, aExpectedTraversalRank)
144
0
{
145
0
146
0
}
Unexecuted instantiation: TestNodeForward<SearchNodeType>::TestNodeForward(SearchNodeType, int)
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::TestNodeForward(ForEachNodeType, int)
147
148
template <class T>
149
TestNodeForward<T>::TestNodeForward() :
150
  TestNodeBase<T>()
151
{
152
153
}
154
155
template <class T>
156
void TestNodeForward<T>::AddChild(RefPtr<TestNodeForward<T>> aNode)
157
0
{
158
0
  if (mFirstChildNode == nullptr) {
159
0
    SetFirstChild(aNode);
160
0
    SetLastChild(aNode);
161
0
  }
162
0
  else {
163
0
    mLastChildNode->SetNextSibling(aNode);
164
0
    SetLastChild(aNode);
165
0
  }
166
0
}
Unexecuted instantiation: TestNodeForward<SearchNodeType>::AddChild(RefPtr<TestNodeForward<SearchNodeType> >)
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::AddChild(RefPtr<TestNodeForward<ForEachNodeType> >)
167
168
template <class T>
169
void TestNodeForward<T>::SetLastChild(RefPtr<TestNodeForward<T>> aNode)
170
0
{
171
0
  mLastChildNode = aNode;
172
0
}
Unexecuted instantiation: TestNodeForward<SearchNodeType>::SetLastChild(RefPtr<TestNodeForward<SearchNodeType> >)
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::SetLastChild(RefPtr<TestNodeForward<ForEachNodeType> >)
173
174
template <class T>
175
void TestNodeForward<T>::SetFirstChild(RefPtr<TestNodeForward<T>> aNode)
176
0
{
177
0
  mFirstChildNode = aNode;
178
0
}
Unexecuted instantiation: TestNodeForward<SearchNodeType>::SetFirstChild(RefPtr<TestNodeForward<SearchNodeType> >)
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::SetFirstChild(RefPtr<TestNodeForward<ForEachNodeType> >)
179
180
template <class T>
181
void TestNodeForward<T>::SetNextSibling(RefPtr<TestNodeForward<T>> aNode)
182
0
{
183
0
  mSiblingNode = aNode;
184
0
}
Unexecuted instantiation: TestNodeForward<SearchNodeType>::SetNextSibling(RefPtr<TestNodeForward<SearchNodeType> >)
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::SetNextSibling(RefPtr<TestNodeForward<ForEachNodeType> >)
185
186
template <class T>
187
bool TestNodeForward<T>::IsLeaf()
188
0
{
189
0
  return !mFirstChildNode;
190
0
}
Unexecuted instantiation: TestNodeForward<SearchNodeType>::IsLeaf()
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::IsLeaf()
191
192
template <class T>
193
TestNodeForward<T>* TestNodeForward<T>::GetFirstChild()
194
0
{
195
0
  return mFirstChildNode;
196
0
}
Unexecuted instantiation: TestNodeForward<SearchNodeType>::GetFirstChild()
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::GetFirstChild()
197
198
template <class T>
199
TestNodeForward<T>* TestNodeForward<T>::GetNextSibling()
200
0
{
201
0
  return mSiblingNode;
202
0
}
Unexecuted instantiation: TestNodeForward<SearchNodeType>::GetNextSibling()
Unexecuted instantiation: TestNodeForward<ForEachNodeType>::GetNextSibling()
203
204
template <class T>
205
TestNodeBase<T>::TestNodeBase(T aType, int aExpectedTraversalRank):
206
    mExpectedTraversalRank(aExpectedTraversalRank),
207
    mActualTraversalRank(-1),
208
    mType(aType)
209
0
{
210
0
}
Unexecuted instantiation: TestNodeBase<SearchNodeType>::TestNodeBase(SearchNodeType, int)
Unexecuted instantiation: TestNodeBase<ForEachNodeType>::TestNodeBase(ForEachNodeType, int)
211
212
template <class T>
213
TestNodeBase<T>::TestNodeBase()
214
{
215
}
216
217
template <class T>
218
int TestNodeBase<T>::GetActualTraversalRank()
219
0
{
220
0
  return mActualTraversalRank;
221
0
}
Unexecuted instantiation: TestNodeBase<SearchNodeType>::GetActualTraversalRank()
Unexecuted instantiation: TestNodeBase<ForEachNodeType>::GetActualTraversalRank()
222
223
template <class T>
224
void TestNodeBase<T>::SetActualTraversalRank(int aRank)
225
0
{
226
0
  mActualTraversalRank = aRank;
227
0
}
Unexecuted instantiation: TestNodeBase<SearchNodeType>::SetActualTraversalRank(int)
Unexecuted instantiation: TestNodeBase<ForEachNodeType>::SetActualTraversalRank(int)
228
229
template <class T>
230
int TestNodeBase<T>::GetExpectedTraversalRank()
231
0
{
232
0
  return mExpectedTraversalRank;
233
0
}
Unexecuted instantiation: TestNodeBase<SearchNodeType>::GetExpectedTraversalRank()
Unexecuted instantiation: TestNodeBase<ForEachNodeType>::GetExpectedTraversalRank()
234
235
template <class T>
236
T TestNodeBase<T>::GetType()
237
0
{
238
0
  return mType;
239
0
}
Unexecuted instantiation: TestNodeBase<SearchNodeType>::GetType()
Unexecuted instantiation: TestNodeBase<ForEachNodeType>::GetType()
240
241
template <class T>
242
void TestNodeBase<T>::SetType(T aType)
243
0
{
244
0
  mType = aType;
245
0
}
246
247
template <class T>
248
nsRegion TestNodeBase<T>::GetRegion()
249
{
250
  return mRegion;
251
}
252
253
template <class T>
254
void TestNodeBase<T>::SetRegion(nsRegion aRegion)
255
0
{
256
0
  mRegion = aRegion;
257
0
}
258
259
template <class T>
260
int TestNodeBase<T>::GetValue()
261
{
262
  return mValue;
263
}
264
265
template <class T>
266
void TestNodeBase<T>::SetValue(int aValue)
267
0
{
268
0
  mValue = aValue;
269
0
}
270
271
typedef TestNodeBase<SearchNodeType> SearchTestNode;
272
typedef TestNodeBase<ForEachNodeType> ForEachTestNode;
273
typedef TestNodeReverse<SearchNodeType> SearchTestNodeReverse;
274
typedef TestNodeReverse<ForEachNodeType> ForEachTestNodeReverse;
275
typedef TestNodeForward<SearchNodeType> SearchTestNodeForward;
276
typedef TestNodeForward<ForEachNodeType> ForEachTestNodeForward;
277
278
TEST(TreeTraversal, DepthFirstSearchNull)
279
0
{
280
0
  RefPtr<SearchTestNodeReverse> nullNode;
281
0
  RefPtr<SearchTestNodeReverse> result = DepthFirstSearch<layers::ReverseIterator>(nullNode.get(),
282
0
      [](SearchTestNodeReverse* aNode)
283
0
      {
284
0
        return aNode->GetType() == SearchNodeType::Needle;
285
0
      });
286
0
  ASSERT_EQ(result.get(), nullptr) << "Null root did not return null search result.";
287
0
}
288
289
TEST(TreeTraversal, DepthFirstSearchValueExists)
290
0
{
291
0
  int visitCount = 0;
292
0
  size_t expectedNeedleTraversalRank = 7;
293
0
  RefPtr<SearchTestNodeForward> needleNode;
294
0
  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
295
0
  nodeList.reserve(10);
296
0
  for (size_t i = 0; i < 10; i++)
297
0
  {
298
0
    if (i == expectedNeedleTraversalRank) {
299
0
      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
300
0
      nodeList.push_back(needleNode);
301
0
    } else if (i < expectedNeedleTraversalRank) {
302
0
      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
303
0
    } else {
304
0
      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
305
0
    }
306
0
  }
307
0
308
0
  RefPtr<SearchTestNodeForward> root = nodeList[0];
309
0
  nodeList[0]->AddChild(nodeList[1]);
310
0
  nodeList[0]->AddChild(nodeList[4]);
311
0
  nodeList[1]->AddChild(nodeList[2]);
312
0
  nodeList[1]->AddChild(nodeList[3]);
313
0
  nodeList[4]->AddChild(nodeList[5]);
314
0
  nodeList[4]->AddChild(nodeList[6]);
315
0
  nodeList[6]->AddChild(nodeList[7]);
316
0
  nodeList[7]->AddChild(nodeList[8]);
317
0
  nodeList[7]->AddChild(nodeList[9]);
318
0
319
0
  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearch<layers::ForwardIterator>(root.get(),
320
0
      [&visitCount](SearchTestNodeForward* aNode)
321
0
      {
322
0
        aNode->SetActualTraversalRank(visitCount);
323
0
        visitCount++;
324
0
        return aNode->GetType() == SearchNodeType::Needle;
325
0
      });
326
0
327
0
  for (size_t i = 0; i < nodeList.size(); i++)
328
0
  {
329
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
330
0
        nodeList[i]->GetActualTraversalRank())
331
0
        << "Node at index " << i << " was hit out of order.";
332
0
  }
333
0
334
0
  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
335
0
  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
336
0
      << "Returned node does not match expected value (something odd happened).";
337
0
}
338
339
TEST(TreeTraversal, DepthFirstSearchValueExistsReverse)
340
0
{
341
0
  int visitCount = 0;
342
0
  size_t expectedNeedleTraversalRank = 7;
343
0
  RefPtr<SearchTestNodeReverse> needleNode;
344
0
  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
345
0
  nodeList.reserve(10);
346
0
  for (size_t i = 0; i < 10; i++)
347
0
  {
348
0
    if (i == expectedNeedleTraversalRank) {
349
0
      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
350
0
      nodeList.push_back(needleNode);
351
0
    } else if (i < expectedNeedleTraversalRank) {
352
0
      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
353
0
    } else {
354
0
      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
355
0
    }
356
0
  }
357
0
358
0
  RefPtr<SearchTestNodeReverse> root = nodeList[0];
359
0
  nodeList[0]->AddChild(nodeList[4]);
360
0
  nodeList[0]->AddChild(nodeList[1]);
361
0
  nodeList[1]->AddChild(nodeList[3]);
362
0
  nodeList[1]->AddChild(nodeList[2]);
363
0
  nodeList[4]->AddChild(nodeList[6]);
364
0
  nodeList[4]->AddChild(nodeList[5]);
365
0
  nodeList[6]->AddChild(nodeList[7]);
366
0
  nodeList[7]->AddChild(nodeList[9]);
367
0
  nodeList[7]->AddChild(nodeList[8]);
368
0
369
0
  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearch<layers::ReverseIterator>(root.get(),
370
0
      [&visitCount](SearchTestNodeReverse* aNode)
371
0
      {
372
0
        aNode->SetActualTraversalRank(visitCount);
373
0
        visitCount++;
374
0
        return aNode->GetType() == SearchNodeType::Needle;
375
0
      });
376
0
377
0
  for (size_t i = 0; i < nodeList.size(); i++)
378
0
  {
379
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
380
0
        nodeList[i]->GetActualTraversalRank())
381
0
        << "Node at index " << i << " was hit out of order.";
382
0
  }
383
0
384
0
  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
385
0
  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
386
0
      << "Returned node does not match expected value (something odd happened).";
387
0
}
388
389
TEST(TreeTraversal, DepthFirstSearchRootIsNeedle)
390
0
{
391
0
  RefPtr<SearchTestNodeReverse> root = new SearchTestNodeReverse(SearchNodeType::Needle, 0);
392
0
  RefPtr<SearchTestNodeReverse> childNode1= new SearchTestNodeReverse(SearchNodeType::Hay);
393
0
  RefPtr<SearchTestNodeReverse> childNode2 = new SearchTestNodeReverse(SearchNodeType::Hay);
394
0
  int visitCount = 0;
395
0
  RefPtr<SearchTestNodeReverse> result = DepthFirstSearch<layers::ReverseIterator>(root.get(),
396
0
      [&visitCount](SearchTestNodeReverse* aNode)
397
0
      {
398
0
        aNode->SetActualTraversalRank(visitCount);
399
0
        visitCount++;
400
0
        return aNode->GetType() == SearchNodeType::Needle;
401
0
      });
402
0
  ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
403
0
  ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
404
0
      << "Search starting at needle did not return needle.";
405
0
  ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
406
0
      childNode1->GetActualTraversalRank())
407
0
      << "Search starting at needle continued past needle.";
408
0
  ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
409
0
      childNode2->GetActualTraversalRank())
410
0
      << "Search starting at needle continued past needle.";
411
0
}
412
413
TEST(TreeTraversal, DepthFirstSearchValueDoesNotExist)
414
0
{
415
0
  int visitCount = 0;
416
0
  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
417
0
  nodeList.reserve(10);
418
0
  for (int i = 0; i < 10; i++)
419
0
  {
420
0
      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
421
0
  }
422
0
423
0
  RefPtr<SearchTestNodeForward> root = nodeList[0];
424
0
  nodeList[0]->AddChild(nodeList[1]);
425
0
  nodeList[0]->AddChild(nodeList[4]);
426
0
  nodeList[1]->AddChild(nodeList[2]);
427
0
  nodeList[1]->AddChild(nodeList[3]);
428
0
  nodeList[4]->AddChild(nodeList[5]);
429
0
  nodeList[4]->AddChild(nodeList[6]);
430
0
  nodeList[6]->AddChild(nodeList[7]);
431
0
  nodeList[7]->AddChild(nodeList[8]);
432
0
  nodeList[7]->AddChild(nodeList[9]);
433
0
434
0
435
0
  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearch<layers::ForwardIterator>(root.get(),
436
0
      [&visitCount](SearchTestNodeForward* aNode)
437
0
      {
438
0
        aNode->SetActualTraversalRank(visitCount);
439
0
        visitCount++;
440
0
        return aNode->GetType() == SearchNodeType::Needle;
441
0
      });
442
0
443
0
  for (int i = 0; i < 10; i++)
444
0
  {
445
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
446
0
        nodeList[i]->GetActualTraversalRank())
447
0
        << "Node at index " << i << " was hit out of order.";
448
0
  }
449
0
450
0
  ASSERT_EQ(foundNode.get(), nullptr)
451
0
      << "Search found something that should not exist.";
452
0
}
453
454
TEST(TreeTraversal, DepthFirstSearchValueDoesNotExistReverse)
455
0
{
456
0
  int visitCount = 0;
457
0
  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
458
0
  nodeList.reserve(10);
459
0
  for (int i = 0; i < 10; i++)
460
0
  {
461
0
      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
462
0
  }
463
0
464
0
  RefPtr<SearchTestNodeReverse> root = nodeList[0];
465
0
  nodeList[0]->AddChild(nodeList[4]);
466
0
  nodeList[0]->AddChild(nodeList[1]);
467
0
  nodeList[1]->AddChild(nodeList[3]);
468
0
  nodeList[1]->AddChild(nodeList[2]);
469
0
  nodeList[4]->AddChild(nodeList[6]);
470
0
  nodeList[4]->AddChild(nodeList[5]);
471
0
  nodeList[6]->AddChild(nodeList[7]);
472
0
  nodeList[7]->AddChild(nodeList[9]);
473
0
  nodeList[7]->AddChild(nodeList[8]);
474
0
475
0
476
0
  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearch<layers::ReverseIterator>(root.get(),
477
0
      [&visitCount](SearchTestNodeReverse* aNode)
478
0
      {
479
0
        aNode->SetActualTraversalRank(visitCount);
480
0
        visitCount++;
481
0
        return aNode->GetType() == SearchNodeType::Needle;
482
0
      });
483
0
484
0
  for (int i = 0; i < 10; i++)
485
0
  {
486
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
487
0
        nodeList[i]->GetActualTraversalRank())
488
0
        << "Node at index " << i << " was hit out of order.";
489
0
  }
490
0
491
0
  ASSERT_EQ(foundNode.get(), nullptr)
492
0
      << "Search found something that should not exist.";
493
0
}
494
495
TEST(TreeTraversal, DepthFirstSearchPostOrderNull)
496
0
{
497
0
  RefPtr<SearchTestNodeReverse> nullNode;
498
0
  RefPtr<SearchTestNodeReverse> result = DepthFirstSearchPostOrder<layers::ReverseIterator>(nullNode.get(),
499
0
      [](SearchTestNodeReverse* aNode)
500
0
      {
501
0
        return aNode->GetType() == SearchNodeType::Needle;
502
0
      });
503
0
  ASSERT_EQ(result.get(), nullptr) << "Null root did not return null search result.";
504
0
}
505
506
TEST(TreeTraversal, DepthFirstSearchPostOrderValueExists)
507
0
{
508
0
  int visitCount = 0;
509
0
  size_t expectedNeedleTraversalRank = 7;
510
0
  RefPtr<SearchTestNodeForward> needleNode;
511
0
  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
512
0
  for (size_t i = 0; i < 10; i++)
513
0
  {
514
0
    if (i == expectedNeedleTraversalRank) {
515
0
      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
516
0
      nodeList.push_back(needleNode);
517
0
    } else if (i < expectedNeedleTraversalRank) {
518
0
      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
519
0
    } else {
520
0
      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
521
0
    }
522
0
  }
523
0
524
0
  RefPtr<SearchTestNodeForward> root = nodeList[9];
525
0
  nodeList[9]->AddChild(nodeList[2]);
526
0
  nodeList[9]->AddChild(nodeList[8]);
527
0
  nodeList[2]->AddChild(nodeList[0]);
528
0
  nodeList[2]->AddChild(nodeList[1]);
529
0
  nodeList[8]->AddChild(nodeList[6]);
530
0
  nodeList[8]->AddChild(nodeList[7]);
531
0
  nodeList[6]->AddChild(nodeList[5]);
532
0
  nodeList[5]->AddChild(nodeList[3]);
533
0
  nodeList[5]->AddChild(nodeList[4]);
534
0
535
0
  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearchPostOrder<layers::ForwardIterator>(root.get(),
536
0
      [&visitCount](SearchTestNodeForward* aNode)
537
0
      {
538
0
        aNode->SetActualTraversalRank(visitCount);
539
0
        visitCount++;
540
0
        return aNode->GetType() == SearchNodeType::Needle;
541
0
      });
542
0
543
0
  for (size_t i = 0; i < nodeList.size(); i++)
544
0
  {
545
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
546
0
        nodeList[i]->GetActualTraversalRank())
547
0
        << "Node at index " << i << " was hit out of order.";
548
0
  }
549
0
550
0
  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
551
0
  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
552
0
      << "Returned node does not match expected value (something odd happened).";
553
0
}
554
555
TEST(TreeTraversal, DepthFirstSearchPostOrderValueExistsReverse)
556
0
{
557
0
  int visitCount = 0;
558
0
  size_t expectedNeedleTraversalRank = 7;
559
0
  RefPtr<SearchTestNodeReverse> needleNode;
560
0
  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
561
0
  for (size_t i = 0; i < 10; i++)
562
0
  {
563
0
    if (i == expectedNeedleTraversalRank) {
564
0
      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
565
0
      nodeList.push_back(needleNode);
566
0
    } else if (i < expectedNeedleTraversalRank) {
567
0
      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
568
0
    } else {
569
0
      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
570
0
    }
571
0
  }
572
0
573
0
  RefPtr<SearchTestNodeReverse> root = nodeList[9];
574
0
  nodeList[9]->AddChild(nodeList[8]);
575
0
  nodeList[9]->AddChild(nodeList[2]);
576
0
  nodeList[2]->AddChild(nodeList[1]);
577
0
  nodeList[2]->AddChild(nodeList[0]);
578
0
  nodeList[8]->AddChild(nodeList[7]);
579
0
  nodeList[8]->AddChild(nodeList[6]);
580
0
  nodeList[6]->AddChild(nodeList[5]);
581
0
  nodeList[5]->AddChild(nodeList[4]);
582
0
  nodeList[5]->AddChild(nodeList[3]);
583
0
584
0
  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearchPostOrder<layers::ReverseIterator>(root.get(),
585
0
      [&visitCount](SearchTestNodeReverse* aNode)
586
0
      {
587
0
        aNode->SetActualTraversalRank(visitCount);
588
0
        visitCount++;
589
0
        return aNode->GetType() == SearchNodeType::Needle;
590
0
      });
591
0
592
0
  for (size_t i = 0; i < nodeList.size(); i++)
593
0
  {
594
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
595
0
        nodeList[i]->GetActualTraversalRank())
596
0
        << "Node at index " << i << " was hit out of order.";
597
0
  }
598
0
599
0
  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
600
0
  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
601
0
      << "Returned node does not match expected value (something odd happened).";
602
0
}
603
604
TEST(TreeTraversal, DepthFirstSearchPostOrderRootIsNeedle)
605
0
{
606
0
  RefPtr<SearchTestNodeReverse> root = new SearchTestNodeReverse(SearchNodeType::Needle, 0);
607
0
  RefPtr<SearchTestNodeReverse> childNode1= new SearchTestNodeReverse(SearchNodeType::Hay);
608
0
  RefPtr<SearchTestNodeReverse> childNode2 = new SearchTestNodeReverse(SearchNodeType::Hay);
609
0
  int visitCount = 0;
610
0
  RefPtr<SearchTestNodeReverse> result = DepthFirstSearchPostOrder<layers::ReverseIterator>(root.get(),
611
0
      [&visitCount](SearchTestNodeReverse* aNode)
612
0
      {
613
0
        aNode->SetActualTraversalRank(visitCount);
614
0
        visitCount++;
615
0
        return aNode->GetType() == SearchNodeType::Needle;
616
0
      });
617
0
  ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
618
0
  ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
619
0
      << "Search starting at needle did not return needle.";
620
0
  ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
621
0
      childNode1->GetActualTraversalRank())
622
0
      << "Search starting at needle continued past needle.";
623
0
  ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
624
0
      childNode2->GetActualTraversalRank())
625
0
      << "Search starting at needle continued past needle.";
626
0
}
627
628
TEST(TreeTraversal, DepthFirstSearchPostOrderValueDoesNotExist)
629
0
{
630
0
  int visitCount = 0;
631
0
  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
632
0
  nodeList.reserve(10);
633
0
  for (int i = 0; i < 10; i++)
634
0
  {
635
0
      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
636
0
  }
637
0
638
0
  RefPtr<SearchTestNodeForward> root = nodeList[9];
639
0
  nodeList[9]->AddChild(nodeList[2]);
640
0
  nodeList[9]->AddChild(nodeList[8]);
641
0
  nodeList[2]->AddChild(nodeList[0]);
642
0
  nodeList[2]->AddChild(nodeList[1]);
643
0
  nodeList[8]->AddChild(nodeList[6]);
644
0
  nodeList[8]->AddChild(nodeList[7]);
645
0
  nodeList[6]->AddChild(nodeList[5]);
646
0
  nodeList[5]->AddChild(nodeList[3]);
647
0
  nodeList[5]->AddChild(nodeList[4]);
648
0
649
0
  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearchPostOrder<layers::ForwardIterator>(root.get(),
650
0
      [&visitCount](SearchTestNodeForward* aNode)
651
0
      {
652
0
        aNode->SetActualTraversalRank(visitCount);
653
0
        visitCount++;
654
0
        return aNode->GetType() == SearchNodeType::Needle;
655
0
      });
656
0
657
0
  for (int i = 0; i < 10; i++)
658
0
  {
659
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
660
0
        nodeList[i]->GetActualTraversalRank())
661
0
        << "Node at index " << i << " was hit out of order.";
662
0
  }
663
0
664
0
  ASSERT_EQ(foundNode.get(), nullptr)
665
0
      << "Search found something that should not exist.";
666
0
}
667
668
TEST(TreeTraversal, DepthFirstSearchPostOrderValueDoesNotExistReverse)
669
0
{
670
0
  int visitCount = 0;
671
0
  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
672
0
  nodeList.reserve(10);
673
0
  for (int i = 0; i < 10; i++)
674
0
  {
675
0
      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
676
0
  }
677
0
678
0
  RefPtr<SearchTestNodeReverse> root = nodeList[9];
679
0
  nodeList[9]->AddChild(nodeList[8]);
680
0
  nodeList[9]->AddChild(nodeList[2]);
681
0
  nodeList[2]->AddChild(nodeList[1]);
682
0
  nodeList[2]->AddChild(nodeList[0]);
683
0
  nodeList[8]->AddChild(nodeList[7]);
684
0
  nodeList[8]->AddChild(nodeList[6]);
685
0
  nodeList[6]->AddChild(nodeList[5]);
686
0
  nodeList[5]->AddChild(nodeList[4]);
687
0
  nodeList[5]->AddChild(nodeList[3]);
688
0
689
0
  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearchPostOrder<layers::ReverseIterator>(root.get(),
690
0
      [&visitCount](SearchTestNodeReverse* aNode)
691
0
      {
692
0
        aNode->SetActualTraversalRank(visitCount);
693
0
        visitCount++;
694
0
        return aNode->GetType() == SearchNodeType::Needle;
695
0
      });
696
0
697
0
  for (int i = 0; i < 10; i++)
698
0
  {
699
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
700
0
        nodeList[i]->GetActualTraversalRank())
701
0
        << "Node at index " << i << " was hit out of order.";
702
0
  }
703
0
704
0
  ASSERT_EQ(foundNode.get(), nullptr)
705
0
      << "Search found something that should not exist.";
706
0
}
707
708
TEST(TreeTraversal, BreadthFirstSearchNull)
709
0
{
710
0
  RefPtr<SearchTestNodeReverse> nullNode;
711
0
  RefPtr<SearchTestNodeReverse> result = BreadthFirstSearch<layers::ReverseIterator>(nullNode.get(),
712
0
      [](SearchTestNodeReverse* aNode)
713
0
      {
714
0
        return aNode->GetType() == SearchNodeType::Needle;
715
0
      });
716
0
  ASSERT_EQ(result.get(), nullptr) << "Null root did not return null search result.";
717
0
}
718
719
TEST(TreeTraversal, BreadthFirstSearchRootIsNeedle)
720
0
{
721
0
  RefPtr<SearchTestNodeReverse> root = new SearchTestNodeReverse(SearchNodeType::Needle, 0);
722
0
  RefPtr<SearchTestNodeReverse> childNode1= new SearchTestNodeReverse(SearchNodeType::Hay);
723
0
  RefPtr<SearchTestNodeReverse> childNode2 = new SearchTestNodeReverse(SearchNodeType::Hay);
724
0
  int visitCount = 0;
725
0
  RefPtr<SearchTestNodeReverse> result = BreadthFirstSearch<layers::ReverseIterator>(root.get(),
726
0
      [&visitCount](SearchTestNodeReverse* aNode)
727
0
      {
728
0
        aNode->SetActualTraversalRank(visitCount);
729
0
        visitCount++;
730
0
        return aNode->GetType() == SearchNodeType::Needle;
731
0
      });
732
0
  ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
733
0
  ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
734
0
      << "Search starting at needle did not return needle.";
735
0
  ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
736
0
      childNode1->GetActualTraversalRank())
737
0
      << "Search starting at needle continued past needle.";
738
0
  ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
739
0
      childNode2->GetActualTraversalRank())
740
0
      << "Search starting at needle continued past needle.";
741
0
}
742
743
TEST(TreeTraversal, BreadthFirstSearchValueExists)
744
0
{
745
0
  int visitCount = 0;
746
0
  size_t expectedNeedleTraversalRank = 7;
747
0
  RefPtr<SearchTestNodeForward> needleNode;
748
0
  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
749
0
  nodeList.reserve(10);
750
0
  for (size_t i = 0; i < 10; i++)
751
0
  {
752
0
    if (i == expectedNeedleTraversalRank) {
753
0
      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
754
0
      nodeList.push_back(needleNode);
755
0
    } else if (i < expectedNeedleTraversalRank) {
756
0
      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
757
0
    } else {
758
0
      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
759
0
    }
760
0
  }
761
0
762
0
  RefPtr<SearchTestNodeForward> root = nodeList[0];
763
0
  nodeList[0]->AddChild(nodeList[1]);
764
0
  nodeList[0]->AddChild(nodeList[2]);
765
0
  nodeList[1]->AddChild(nodeList[3]);
766
0
  nodeList[1]->AddChild(nodeList[4]);
767
0
  nodeList[2]->AddChild(nodeList[5]);
768
0
  nodeList[2]->AddChild(nodeList[6]);
769
0
  nodeList[6]->AddChild(nodeList[7]);
770
0
  nodeList[7]->AddChild(nodeList[8]);
771
0
  nodeList[7]->AddChild(nodeList[9]);
772
0
773
0
  RefPtr<SearchTestNodeForward> foundNode = BreadthFirstSearch<layers::ForwardIterator>(root.get(),
774
0
      [&visitCount](SearchTestNodeForward* aNode)
775
0
      {
776
0
        aNode->SetActualTraversalRank(visitCount);
777
0
        visitCount++;
778
0
        return aNode->GetType() == SearchNodeType::Needle;
779
0
      });
780
0
781
0
  for (size_t i = 0; i < nodeList.size(); i++)
782
0
  {
783
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
784
0
        nodeList[i]->GetActualTraversalRank())
785
0
        << "Node at index " << i << " was hit out of order.";
786
0
  }
787
0
788
0
  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
789
0
  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
790
0
      << "Returned node does not match expected value (something odd happened).";
791
0
}
792
793
TEST(TreeTraversal, BreadthFirstSearchValueExistsReverse)
794
0
{
795
0
  int visitCount = 0;
796
0
  size_t expectedNeedleTraversalRank = 7;
797
0
  RefPtr<SearchTestNodeReverse> needleNode;
798
0
  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
799
0
  nodeList.reserve(10);
800
0
  for (size_t i = 0; i < 10; i++)
801
0
  {
802
0
    if (i == expectedNeedleTraversalRank) {
803
0
      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
804
0
      nodeList.push_back(needleNode);
805
0
    } else if (i < expectedNeedleTraversalRank) {
806
0
      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
807
0
    } else {
808
0
      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
809
0
    }
810
0
  }
811
0
812
0
  RefPtr<SearchTestNodeReverse> root = nodeList[0];
813
0
  nodeList[0]->AddChild(nodeList[2]);
814
0
  nodeList[0]->AddChild(nodeList[1]);
815
0
  nodeList[1]->AddChild(nodeList[4]);
816
0
  nodeList[1]->AddChild(nodeList[3]);
817
0
  nodeList[2]->AddChild(nodeList[6]);
818
0
  nodeList[2]->AddChild(nodeList[5]);
819
0
  nodeList[6]->AddChild(nodeList[7]);
820
0
  nodeList[7]->AddChild(nodeList[9]);
821
0
  nodeList[7]->AddChild(nodeList[8]);
822
0
823
0
  RefPtr<SearchTestNodeReverse> foundNode = BreadthFirstSearch<layers::ReverseIterator>(root.get(),
824
0
      [&visitCount](SearchTestNodeReverse* aNode)
825
0
      {
826
0
        aNode->SetActualTraversalRank(visitCount);
827
0
        visitCount++;
828
0
        return aNode->GetType() == SearchNodeType::Needle;
829
0
      });
830
0
831
0
  for (size_t i = 0; i < nodeList.size(); i++)
832
0
  {
833
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
834
0
        nodeList[i]->GetActualTraversalRank())
835
0
        << "Node at index " << i << " was hit out of order.";
836
0
  }
837
0
838
0
  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
839
0
  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
840
0
      << "Returned node does not match expected value (something odd happened).";
841
0
}
842
843
TEST(TreeTraversal, BreadthFirstSearchValueDoesNotExist)
844
0
{
845
0
  int visitCount = 0;
846
0
  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
847
0
  nodeList.reserve(10);
848
0
  for (int i = 0; i < 10; i++)
849
0
  {
850
0
    nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
851
0
  }
852
0
853
0
  RefPtr<SearchTestNodeForward> root = nodeList[0];
854
0
  nodeList[0]->AddChild(nodeList[1]);
855
0
  nodeList[0]->AddChild(nodeList[2]);
856
0
  nodeList[1]->AddChild(nodeList[3]);
857
0
  nodeList[1]->AddChild(nodeList[4]);
858
0
  nodeList[2]->AddChild(nodeList[5]);
859
0
  nodeList[2]->AddChild(nodeList[6]);
860
0
  nodeList[6]->AddChild(nodeList[7]);
861
0
  nodeList[7]->AddChild(nodeList[8]);
862
0
  nodeList[7]->AddChild(nodeList[9]);
863
0
864
0
865
0
  RefPtr<SearchTestNodeForward> foundNode = BreadthFirstSearch<layers::ForwardIterator>(root.get(),
866
0
      [&visitCount](SearchTestNodeForward* aNode)
867
0
      {
868
0
        aNode->SetActualTraversalRank(visitCount);
869
0
        visitCount++;
870
0
        return aNode->GetType() == SearchNodeType::Needle;
871
0
      });
872
0
873
0
  for (size_t i = 0; i < nodeList.size(); i++)
874
0
  {
875
0
      ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
876
0
          nodeList[i]->GetActualTraversalRank())
877
0
          << "Node at index " << i << " was hit out of order.";
878
0
  }
879
0
880
0
  ASSERT_EQ(foundNode.get(), nullptr)
881
0
      << "Search found something that should not exist.";
882
0
}
883
884
TEST(TreeTraversal, BreadthFirstSearchValueDoesNotExistReverse)
885
0
{
886
0
  int visitCount = 0;
887
0
  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
888
0
  nodeList.reserve(10);
889
0
  for (int i = 0; i < 10; i++)
890
0
  {
891
0
    nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
892
0
  }
893
0
894
0
  RefPtr<SearchTestNodeReverse> root = nodeList[0];
895
0
  nodeList[0]->AddChild(nodeList[2]);
896
0
  nodeList[0]->AddChild(nodeList[1]);
897
0
  nodeList[1]->AddChild(nodeList[4]);
898
0
  nodeList[1]->AddChild(nodeList[3]);
899
0
  nodeList[2]->AddChild(nodeList[6]);
900
0
  nodeList[2]->AddChild(nodeList[5]);
901
0
  nodeList[6]->AddChild(nodeList[7]);
902
0
  nodeList[7]->AddChild(nodeList[9]);
903
0
  nodeList[7]->AddChild(nodeList[8]);
904
0
905
0
906
0
  RefPtr<SearchTestNodeReverse> foundNode = BreadthFirstSearch<layers::ReverseIterator>(root.get(),
907
0
      [&visitCount](SearchTestNodeReverse* aNode)
908
0
      {
909
0
        aNode->SetActualTraversalRank(visitCount);
910
0
        visitCount++;
911
0
        return aNode->GetType() == SearchNodeType::Needle;
912
0
      });
913
0
914
0
  for (size_t i = 0; i < nodeList.size(); i++)
915
0
  {
916
0
      ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
917
0
          nodeList[i]->GetActualTraversalRank())
918
0
          << "Node at index " << i << " was hit out of order.";
919
0
  }
920
0
921
0
  ASSERT_EQ(foundNode.get(), nullptr)
922
0
      << "Search found something that should not exist.";
923
0
}
924
925
TEST(TreeTraversal, ForEachNodeNullStillRuns)
926
0
{
927
0
  RefPtr<ForEachTestNodeReverse> nullNode;
928
0
  ForEachNode<layers::ReverseIterator>(nullNode.get(),
929
0
    [](ForEachTestNodeReverse* aNode)
930
0
    {
931
0
      return TraversalFlag::Continue;
932
0
    });
933
0
}
934
935
TEST(TreeTraversal, ForEachNodeAllEligible)
936
0
{
937
0
  std::vector<RefPtr<ForEachTestNodeForward>> nodeList;
938
0
  int visitCount = 0;
939
0
  nodeList.reserve(10);
940
0
  for (int i = 0; i < 10; i++)
941
0
  {
942
0
    nodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue,i));
943
0
  }
944
0
945
0
  RefPtr<ForEachTestNodeForward> root = nodeList[0];
946
0
  nodeList[0]->AddChild(nodeList[1]);
947
0
  nodeList[0]->AddChild(nodeList[4]);
948
0
  nodeList[1]->AddChild(nodeList[2]);
949
0
  nodeList[1]->AddChild(nodeList[3]);
950
0
  nodeList[4]->AddChild(nodeList[5]);
951
0
  nodeList[4]->AddChild(nodeList[6]);
952
0
  nodeList[6]->AddChild(nodeList[7]);
953
0
  nodeList[7]->AddChild(nodeList[8]);
954
0
  nodeList[7]->AddChild(nodeList[9]);
955
0
956
0
957
0
  ForEachNode<layers::ForwardIterator>(root.get(),
958
0
      [&visitCount](ForEachTestNodeForward* aNode)
959
0
      {
960
0
        aNode->SetActualTraversalRank(visitCount);
961
0
        visitCount++;
962
0
        return aNode->GetType() == ForEachNodeType::Continue
963
0
            ? TraversalFlag::Continue : TraversalFlag::Skip;
964
0
      });
965
0
966
0
  for (size_t i = 0; i < nodeList.size(); i++)
967
0
  {
968
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
969
0
        nodeList[i]->GetActualTraversalRank())
970
0
        << "Node at index " << i << " was hit out of order.";
971
0
  }
972
0
}
973
974
TEST(TreeTraversal, ForEachNodeAllEligibleReverse)
975
0
{
976
0
  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
977
0
  int visitCount = 0;
978
0
  nodeList.reserve(10);
979
0
  for (int i = 0; i < 10; i++)
980
0
  {
981
0
    nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue,i));
982
0
  }
983
0
984
0
  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
985
0
  nodeList[0]->AddChild(nodeList[4]);
986
0
  nodeList[0]->AddChild(nodeList[1]);
987
0
  nodeList[1]->AddChild(nodeList[3]);
988
0
  nodeList[1]->AddChild(nodeList[2]);
989
0
  nodeList[4]->AddChild(nodeList[6]);
990
0
  nodeList[4]->AddChild(nodeList[5]);
991
0
  nodeList[6]->AddChild(nodeList[7]);
992
0
  nodeList[7]->AddChild(nodeList[9]);
993
0
  nodeList[7]->AddChild(nodeList[8]);
994
0
995
0
996
0
  ForEachNode<layers::ReverseIterator>(root.get(),
997
0
      [&visitCount](ForEachTestNodeReverse* aNode)
998
0
      {
999
0
        aNode->SetActualTraversalRank(visitCount);
1000
0
        visitCount++;
1001
0
        return aNode->GetType() == ForEachNodeType::Continue
1002
0
            ? TraversalFlag::Continue : TraversalFlag::Skip;
1003
0
      });
1004
0
1005
0
  for (size_t i = 0; i < nodeList.size(); i++)
1006
0
  {
1007
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
1008
0
        nodeList[i]->GetActualTraversalRank())
1009
0
        << "Node at index " << i << " was hit out of order.";
1010
0
  }
1011
0
}
1012
1013
TEST(TreeTraversal, ForEachNodeSomeIneligibleNodes)
1014
0
{
1015
0
  std::vector<RefPtr<ForEachTestNodeForward>> expectedVisitedNodeList;
1016
0
  std::vector<RefPtr<ForEachTestNodeForward>> expectedSkippedNodeList;
1017
0
  int visitCount = 0;
1018
0
1019
0
  expectedVisitedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue, 0));
1020
0
  expectedVisitedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip, 1));
1021
0
  expectedVisitedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue, 2));
1022
0
  expectedVisitedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip, 3));
1023
0
1024
0
  expectedSkippedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue));
1025
0
  expectedSkippedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue));
1026
0
  expectedSkippedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip));
1027
0
  expectedSkippedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip));
1028
0
1029
0
  RefPtr<ForEachTestNodeForward> root = expectedVisitedNodeList[0];
1030
0
  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[1]);
1031
0
  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
1032
0
  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[0]);
1033
0
  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
1034
0
  expectedVisitedNodeList[2]->AddChild(expectedVisitedNodeList[3]);
1035
0
  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
1036
0
  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[3]);
1037
0
1038
0
  ForEachNode<layers::ForwardIterator>(root.get(),
1039
0
      [&visitCount](ForEachTestNodeForward* aNode)
1040
0
      {
1041
0
        aNode->SetActualTraversalRank(visitCount);
1042
0
        visitCount++;
1043
0
        return aNode->GetType() == ForEachNodeType::Continue
1044
0
            ? TraversalFlag::Continue : TraversalFlag::Skip;
1045
0
      });
1046
0
1047
0
  for (size_t i = 0; i < expectedVisitedNodeList.size(); i++)
1048
0
  {
1049
0
    ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(),
1050
0
        expectedVisitedNodeList[i]->GetActualTraversalRank())
1051
0
        << "Node at index " << i << " was hit out of order.";
1052
0
  }
1053
0
1054
0
  for (size_t i = 0; i < expectedSkippedNodeList.size(); i++)
1055
0
  {
1056
0
    ASSERT_EQ(expectedSkippedNodeList[i]->GetExpectedTraversalRank(),
1057
0
        expectedSkippedNodeList[i]->GetActualTraversalRank())
1058
0
        << "Node at index " << i << "was not expected to be hit.";
1059
0
  }
1060
0
}
1061
1062
TEST(TreeTraversal, ForEachNodeSomeIneligibleNodesReverse)
1063
0
{
1064
0
  std::vector<RefPtr<ForEachTestNodeReverse>> expectedVisitedNodeList;
1065
0
  std::vector<RefPtr<ForEachTestNodeReverse>> expectedSkippedNodeList;
1066
0
  int visitCount = 0;
1067
0
1068
0
  expectedVisitedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue, 0));
1069
0
  expectedVisitedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip, 1));
1070
0
  expectedVisitedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue, 2));
1071
0
  expectedVisitedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip, 3));
1072
0
1073
0
  expectedSkippedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue));
1074
0
  expectedSkippedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue));
1075
0
  expectedSkippedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip));
1076
0
  expectedSkippedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip));
1077
0
1078
0
  RefPtr<ForEachTestNodeReverse> root = expectedVisitedNodeList[0];
1079
0
  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
1080
0
  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[1]);
1081
0
  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
1082
0
  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[0]);
1083
0
  expectedVisitedNodeList[2]->AddChild(expectedVisitedNodeList[3]);
1084
0
  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[3]);
1085
0
  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
1086
0
1087
0
  ForEachNode<layers::ReverseIterator>(root.get(),
1088
0
      [&visitCount](ForEachTestNodeReverse* aNode)
1089
0
      {
1090
0
        aNode->SetActualTraversalRank(visitCount);
1091
0
        visitCount++;
1092
0
        return aNode->GetType() == ForEachNodeType::Continue
1093
0
            ? TraversalFlag::Continue : TraversalFlag::Skip;
1094
0
      });
1095
0
1096
0
  for (size_t i = 0; i < expectedVisitedNodeList.size(); i++)
1097
0
  {
1098
0
    ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(),
1099
0
        expectedVisitedNodeList[i]->GetActualTraversalRank())
1100
0
        << "Node at index " << i << " was hit out of order.";
1101
0
  }
1102
0
1103
0
  for (size_t i = 0; i < expectedSkippedNodeList.size(); i++)
1104
0
  {
1105
0
    ASSERT_EQ(expectedSkippedNodeList[i]->GetExpectedTraversalRank(),
1106
0
        expectedSkippedNodeList[i]->GetActualTraversalRank())
1107
0
        << "Node at index " << i << "was not expected to be hit.";
1108
0
  }
1109
0
}
1110
1111
TEST(TreeTraversal, ForEachNodeIneligibleRoot)
1112
0
{
1113
0
  int visitCount = 0;
1114
0
1115
0
  RefPtr<ForEachTestNodeReverse> root = new ForEachTestNodeReverse(ForEachNodeType::Skip, 0);
1116
0
  RefPtr<ForEachTestNodeReverse> childNode1 = new ForEachTestNodeReverse(ForEachNodeType::Continue);
1117
0
  RefPtr<ForEachTestNodeReverse> chlidNode2 = new ForEachTestNodeReverse(ForEachNodeType::Skip);
1118
0
1119
0
  ForEachNode<layers::ReverseIterator>(root.get(),
1120
0
      [&visitCount](ForEachTestNodeReverse* aNode)
1121
0
      {
1122
0
        aNode->SetActualTraversalRank(visitCount);
1123
0
        visitCount++;
1124
0
        return aNode->GetType() == ForEachNodeType::Continue
1125
0
            ? TraversalFlag::Continue : TraversalFlag::Skip;
1126
0
      });
1127
0
1128
0
  ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
1129
0
      << "Root was hit out of order.";
1130
0
  ASSERT_EQ(childNode1->GetExpectedTraversalRank(), childNode1->GetActualTraversalRank())
1131
0
      << "Eligible child was still hit.";
1132
0
  ASSERT_EQ(chlidNode2->GetExpectedTraversalRank(), chlidNode2->GetActualTraversalRank())
1133
0
      << "Ineligible child was still hit.";
1134
0
}
1135
1136
TEST(TreeTraversal, ForEachNodeLeavesIneligible)
1137
0
{
1138
0
1139
0
  std::vector<RefPtr<ForEachTestNodeForward>> nodeList;
1140
0
  nodeList.reserve(10);
1141
0
  int visitCount = 0;
1142
0
  for (int i = 0; i < 10; i++)
1143
0
  {
1144
0
    if (i == 1 || i == 9) {
1145
0
      nodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip, i));
1146
0
    } else {
1147
0
      nodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue, i));
1148
0
    }
1149
0
  }
1150
0
1151
0
  RefPtr<ForEachTestNodeForward> root = nodeList[0];
1152
0
  nodeList[0]->AddChild(nodeList[1]);
1153
0
  nodeList[0]->AddChild(nodeList[2]);
1154
0
  nodeList[2]->AddChild(nodeList[3]);
1155
0
  nodeList[2]->AddChild(nodeList[4]);
1156
0
  nodeList[4]->AddChild(nodeList[5]);
1157
0
  nodeList[4]->AddChild(nodeList[6]);
1158
0
  nodeList[6]->AddChild(nodeList[7]);
1159
0
  nodeList[7]->AddChild(nodeList[8]);
1160
0
  nodeList[7]->AddChild(nodeList[9]);
1161
0
1162
0
  ForEachNode<layers::ForwardIterator>(root.get(),
1163
0
      [&visitCount](ForEachTestNodeForward* aNode)
1164
0
      {
1165
0
        aNode->SetActualTraversalRank(visitCount);
1166
0
        visitCount++;
1167
0
        return aNode->GetType() == ForEachNodeType::Continue
1168
0
            ? TraversalFlag::Continue : TraversalFlag::Skip;
1169
0
      });
1170
0
1171
0
  for (size_t i = 0; i < nodeList.size(); i++)
1172
0
  {
1173
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
1174
0
        nodeList[i]->GetActualTraversalRank())
1175
0
        << "Node at index " << i << " was hit out of order.";
1176
0
  }
1177
0
}
1178
1179
TEST(TreeTraversal, ForEachNodeLeavesIneligibleReverse)
1180
0
{
1181
0
1182
0
  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
1183
0
  nodeList.reserve(10);
1184
0
  int visitCount = 0;
1185
0
  for (int i = 0; i < 10; i++)
1186
0
  {
1187
0
    if (i == 1 || i == 9) {
1188
0
      nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip, i));
1189
0
    } else {
1190
0
      nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue, i));
1191
0
    }
1192
0
  }
1193
0
1194
0
  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
1195
0
  nodeList[0]->AddChild(nodeList[2]);
1196
0
  nodeList[0]->AddChild(nodeList[1]);
1197
0
  nodeList[2]->AddChild(nodeList[4]);
1198
0
  nodeList[2]->AddChild(nodeList[3]);
1199
0
  nodeList[4]->AddChild(nodeList[6]);
1200
0
  nodeList[4]->AddChild(nodeList[5]);
1201
0
  nodeList[6]->AddChild(nodeList[7]);
1202
0
  nodeList[7]->AddChild(nodeList[9]);
1203
0
  nodeList[7]->AddChild(nodeList[8]);
1204
0
1205
0
  ForEachNode<layers::ReverseIterator>(root.get(),
1206
0
      [&visitCount](ForEachTestNodeReverse* aNode)
1207
0
      {
1208
0
        aNode->SetActualTraversalRank(visitCount);
1209
0
        visitCount++;
1210
0
        return aNode->GetType() == ForEachNodeType::Continue
1211
0
            ? TraversalFlag::Continue : TraversalFlag::Skip;
1212
0
      });
1213
0
1214
0
  for (size_t i = 0; i < nodeList.size(); i++)
1215
0
  {
1216
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
1217
0
        nodeList[i]->GetActualTraversalRank())
1218
0
        << "Node at index " << i << " was hit out of order.";
1219
0
  }
1220
0
}
1221
1222
TEST(TreeTraversal, ForEachNodeLambdaReturnsVoid)
1223
0
{
1224
0
  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
1225
0
  nodeList.reserve(10);
1226
0
  int visitCount = 0;
1227
0
  for (int i = 0; i < 10; i++)
1228
0
  {
1229
0
    nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue,i));
1230
0
  }
1231
0
1232
0
  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
1233
0
  nodeList[0]->AddChild(nodeList[4]);
1234
0
  nodeList[0]->AddChild(nodeList[1]);
1235
0
  nodeList[1]->AddChild(nodeList[3]);
1236
0
  nodeList[1]->AddChild(nodeList[2]);
1237
0
  nodeList[4]->AddChild(nodeList[6]);
1238
0
  nodeList[4]->AddChild(nodeList[5]);
1239
0
  nodeList[6]->AddChild(nodeList[7]);
1240
0
  nodeList[7]->AddChild(nodeList[9]);
1241
0
  nodeList[7]->AddChild(nodeList[8]);
1242
0
1243
0
1244
0
  ForEachNode<layers::ReverseIterator>(root.get(),
1245
0
      [&visitCount](ForEachTestNodeReverse* aNode)
1246
0
      {
1247
0
        aNode->SetActualTraversalRank(visitCount);
1248
0
        visitCount++;
1249
0
      });
1250
0
1251
0
  for (size_t i = 0; i < nodeList.size(); i++)
1252
0
  {
1253
0
    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
1254
0
        nodeList[i]->GetActualTraversalRank())
1255
0
        << "Node at index " << i << " was hit out of order.";
1256
0
  }
1257
0
}
1258
1259
struct AssignSearchNodeTypesWithLastLeafAsNeedle {
1260
  RefPtr<SearchTestNodeForward>& node;
1261
0
  void operator()(SearchTestNodeForward* aNode) {
1262
0
    aNode->SetType(SearchNodeType::Hay);
1263
0
    if (aNode->IsLeaf()) {
1264
0
      node = aNode;
1265
0
    }
1266
0
  }
1267
};
1268
1269
0
bool FindNeedle(SearchTestNode* aNode) {
1270
0
  return aNode->GetType() == SearchNodeType::Needle;
1271
0
}
1272
1273
struct AssignSearchNodeTypesAllHay
1274
{
1275
0
  void operator()(SearchTestNode* aNode){
1276
0
    aNode->SetType(SearchNodeType::Hay);
1277
0
  }
1278
};
1279
1280
struct AssignSearchNodeTypesWithFirstLeafAsNeedle
1281
{
1282
  RefPtr<SearchTestNodeReverse>& needleNode;
1283
0
  void operator()(SearchTestNodeReverse* aNode){
1284
0
    if (!needleNode && aNode->IsLeaf()) {
1285
0
      needleNode = aNode;
1286
0
    }
1287
0
    aNode->SetType(SearchNodeType::Hay);
1288
0
  }
1289
};
1290
1291
struct AssignSearchNodeValuesAllFalseValuesReverse
1292
{
1293
  int falseValue;
1294
  RefPtr<SearchTestNodeReverse>& needleNode;
1295
0
  void operator()(SearchTestNodeReverse* aNode){
1296
0
    aNode->SetValue(falseValue);
1297
0
    if (!needleNode && aNode->IsLeaf()) {
1298
0
      needleNode = aNode;
1299
0
    }
1300
0
  }
1301
};
1302
1303
struct AssignSearchNodeValuesAllFalseValuesForward
1304
{
1305
  int falseValue;
1306
  RefPtr<SearchTestNodeForward>& needleNode;
1307
0
  void operator()(SearchTestNodeForward* aNode){
1308
0
    aNode->SetValue(falseValue);
1309
0
    needleNode = aNode;
1310
0
  }
1311
};
1312
1313
struct AllocateUnitRegionsToLeavesOnly
1314
{
1315
  int& xWrap;
1316
  int& squareCount;
1317
0
  void operator()(ForEachTestNode* aNode) {
1318
0
    if (aNode->IsLeaf()) {
1319
0
      int x = squareCount % xWrap;
1320
0
      int y = squareCount / xWrap;
1321
0
      aNode->SetRegion(nsRegion(nsRect(x, y, 1, 1)));
1322
0
      squareCount++;
1323
0
    }
1324
0
  }
1325
};
1326
1327
0
void ForEachNodeDoNothing(ForEachTestNode* aNode) {}
1328
1329
template <typename Node>
1330
static RefPtr<Node> DepthFirstSearchForwardRecursive(RefPtr<Node> aNode)
1331
{
1332
  if (aNode->GetType() == SearchNodeType::Needle) {
1333
    return aNode;
1334
  }
1335
  for (RefPtr<Node> node = aNode->GetFirstChild();
1336
      node != nullptr;
1337
      node = node->GetNextSibling()) {
1338
    if (RefPtr<Node> foundNode = DepthFirstSearchForwardRecursive(node)) {
1339
      return foundNode;
1340
    }
1341
  }
1342
  return nullptr;
1343
}
1344
1345
template <typename Node>
1346
static RefPtr<Node> DepthFirstSearchCaptureVariablesForwardRecursive(RefPtr<Node> aNode,
1347
    int a, int b, int c, int d, int e, int f,
1348
    int g, int h, int i, int j, int k, int l,
1349
    int m, int& n, int& o, int& p, int& q, int& r,
1350
    int& s, int& t, int& u, int& v, int& w, int& x,
1351
    int& y, int& z)
1352
{
1353
  if (aNode->GetValue() == a + b + c + d + e + f + g + h + i + j + k + l + m +
1354
         n + o + p + q + r + s + t + u + v + w + x + y + z) {
1355
    return aNode;
1356
  }
1357
  for (RefPtr<Node> node = aNode->GetFirstChild();
1358
      node != nullptr;
1359
      node = node->GetNextSibling()) {
1360
    if (RefPtr<Node> foundNode = DepthFirstSearchCaptureVariablesForwardRecursive(node,
1361
          a, b, c, d, e, f, g, h, i, j, k, l, m,
1362
          n, o, p, q, r, s, t, u, v, w, x, y, z)) {
1363
      return foundNode;
1364
    }
1365
  }
1366
  return nullptr;
1367
}
1368
1369
template <typename Node>
1370
static RefPtr<Node> DepthFirstSearchPostOrderForwardRecursive(RefPtr<Node> aNode)
1371
{
1372
  for (RefPtr<Node> node = aNode->GetFirstChild();
1373
      node != nullptr;
1374
      node = node->GetNextSibling()) {
1375
    if (RefPtr<Node> foundNode = DepthFirstSearchPostOrderForwardRecursive(node)) {
1376
      return foundNode;
1377
    }
1378
  }
1379
  if (aNode->GetType() == SearchNodeType::Needle) {
1380
    return aNode;
1381
  }
1382
  return nullptr;
1383
}
1384
1385
template <typename Node>
1386
static RefPtr<Node> BreadthFirstSearchForwardQueue(RefPtr<Node> aNode)
1387
{
1388
  std::queue<RefPtr<Node>> nodes;
1389
  nodes.push(aNode);
1390
  while(!nodes.empty()) {
1391
    RefPtr<Node> node = nodes.front();
1392
    nodes.pop();
1393
    if (node->GetType() == SearchNodeType::Needle) {
1394
      return node;
1395
    }
1396
    for (RefPtr<Node> childNode = node->GetFirstChild();
1397
        childNode != nullptr;
1398
        childNode = childNode->GetNextSibling()) {
1399
      nodes.push(childNode);
1400
    }
1401
  }
1402
  return nullptr;
1403
}
1404
1405
template <typename Node>
1406
static RefPtr<Node> DepthFirstSearchReverseRecursive(RefPtr<Node> aNode)
1407
{
1408
  if (aNode->GetType() == SearchNodeType::Needle) {
1409
    return aNode;
1410
  }
1411
  for (RefPtr<Node> node = aNode->GetLastChild();
1412
      node != nullptr;
1413
      node = node->GetPrevSibling()) {
1414
    if (RefPtr<Node> foundNode = DepthFirstSearchReverseRecursive(node)) {
1415
      return foundNode;
1416
    }
1417
  }
1418
  return nullptr;
1419
}
1420
1421
1422
template <typename Node>
1423
static RefPtr<Node> DepthFirstSearchCaptureVariablesReverseRecursive(RefPtr<Node> aNode,
1424
    int a, int b, int c, int d, int e, int f,
1425
    int g, int h, int i, int j, int k, int l,
1426
    int m, int& n, int& o, int& p, int& q, int& r,
1427
    int& s, int& t, int& u, int& v, int& w, int& x,
1428
    int& y, int& z)
1429
{
1430
  if (aNode->GetValue() == a + b + c + d + e + f + g + h + i + j + k + l +
1431
         m + n + o + p + q + r + s + t + u + v + w + x + y + z) {
1432
    return aNode;
1433
  }
1434
  for (RefPtr<Node> node = aNode->GetLastChild();
1435
      node != nullptr;
1436
      node = node->GetPrevSibling()) {
1437
    if (RefPtr<Node> foundNode = DepthFirstSearchCaptureVariablesReverseRecursive(node,
1438
            a, b, c, d, e, f, g, h, i, j, k, l, m,
1439
            n, o, p, q, r, s, t, u, v, w, x, y, z)) {
1440
      return foundNode;
1441
    }
1442
  }
1443
  return nullptr;
1444
}
1445
1446
1447
template <typename Node>
1448
static RefPtr<Node> DepthFirstSearchPostOrderReverseRecursive(RefPtr<Node> aNode)
1449
{
1450
  for (RefPtr<Node> node = aNode->GetLastChild();
1451
      node != nullptr;
1452
      node = node->GetPrevSibling()) {
1453
    if (RefPtr<Node> foundNode = DepthFirstSearchPostOrderReverseRecursive(node)) {
1454
      return foundNode;
1455
    }
1456
  }
1457
  if (aNode->GetType() == SearchNodeType::Needle) {
1458
    return aNode;
1459
  }
1460
  return nullptr;
1461
}
1462
1463
1464
template <typename Node>
1465
static RefPtr<Node> BreadthFirstSearchReverseQueue(RefPtr<Node> aNode)
1466
{
1467
  std::queue<RefPtr<Node>> nodes;
1468
  nodes.push(aNode);
1469
  while(!nodes.empty()) {
1470
    RefPtr<Node> node = nodes.front();
1471
    nodes.pop();
1472
    if (node->GetType() == SearchNodeType::Needle) {
1473
      return node;
1474
    }
1475
    for (RefPtr<Node> childNode = node->GetLastChild();
1476
        childNode != nullptr;
1477
        childNode = childNode->GetPrevSibling()) {
1478
      nodes.push(childNode);
1479
    }
1480
  }
1481
  return nullptr;
1482
}
1483