1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
/*=========================================================================
Program: Visualization Toolkit
Module: $RCSfile: vtkTreeBFSIterator.cxx,v $
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
All rights reserved.
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
#include "vtkTreeBFSIterator.h"
#include "vtkIntArray.h"
#include "vtkObjectFactory.h"
#include "vtkTree.h"
#include <queue>
using std::queue;
class vtkTreeBFSIteratorInternals
{
public:
queue<vtkIdType> Queue;
};
vtkStandardNewMacro(vtkTreeBFSIterator);
vtkTreeBFSIterator::vtkTreeBFSIterator()
{
this->Internals = new vtkTreeBFSIteratorInternals();
this->Color = vtkIntArray::New();
}
vtkTreeBFSIterator::~vtkTreeBFSIterator()
{
delete this->Internals;
this->Internals = NULL;
if (this->Color)
{
this->Color->Delete();
this->Color = NULL;
}
}
void vtkTreeBFSIterator::PrintSelf(ostream& os, vtkIndent indent)
{
this->Superclass::PrintSelf(os, indent);
}
void vtkTreeBFSIterator::Initialize()
{
if (this->Tree == NULL)
{
return;
}
// Set all colors to white
this->Color->Resize(this->Tree->GetNumberOfVertices());
for (vtkIdType i = 0; i < this->Tree->GetNumberOfVertices(); i++)
{
this->Color->SetValue(i, this->WHITE);
}
if (this->StartVertex < 0)
{
this->StartVertex = this->Tree->GetRoot();
}
while (this->Internals->Queue.size())
{
this->Internals->Queue.pop();
}
// Find the first item
if (this->Tree->GetNumberOfVertices() > 0)
{
this->NextId = this->NextInternal();
}
else
{
this->NextId = -1;
}
}
vtkIdType vtkTreeBFSIterator::NextInternal()
{
if(this->Color->GetValue(this->StartVertex) == this->WHITE)
{
this->Color->SetValue(this->StartVertex, this->GRAY);
this->Internals->Queue.push(this->StartVertex);
}
while (this->Internals->Queue.size() > 0)
{
vtkIdType currentId = this->Internals->Queue.front();
this->Internals->Queue.pop();
for(vtkIdType childNum = 0; childNum < this->Tree->GetNumberOfChildren(currentId); childNum++)
{
vtkIdType childId = this->Tree->GetChild(currentId, childNum);
if(this->Color->GetValue(childId) == this->WHITE)
{
// Found a white vertex; make it gray, add it to the queue
this->Color->SetValue(childId, this->GRAY);
this->Internals->Queue.push(childId);
}
}
this->Color->SetValue(currentId, this->BLACK);
return currentId;
}
return -1;
}
|
