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
117
118
119
120
121
122
123
124
125
126
127
128
129
|
/*
Copyright (C) 2005-2007 Feeling Software Inc.
Portions of the code are:
Copyright (C) 2005-2007 Sony Computer Entertainment America
MIT License: http://www.opensource.org/licenses/mit-license.php
*/
#ifndef _FCD_SCENE_NODE_H_
#include "FCDocument/FCDSceneNode.h"
#endif // _FCD_SCENE_NODE_H_
//
// FCDSceneNodeIterator
//
template <class NODE_T>
FCDSceneNodeIteratorT<NODE_T>::FCDSceneNodeIteratorT(NODE_T* root, SearchType searchType, bool pureChildOnly)
{
queue.reserve(8);
if (searchType == BREADTH_FIRST)
{
queue.push_back(root);
// Fill in the queue completely,
// in case the user using this iterator wants to modify stuff.
for (size_t index = 0; index < queue.size(); ++index)
{
NODE_T* it = queue[index];
size_t childCount = it->GetChildrenCount();
for (size_t c = 0; c < childCount; ++c)
{
NODE_T* node = it->GetChild(c);
if (!pureChildOnly || node->GetParent(0) == it) queue.push_back(node);
}
if (!pureChildOnly)
{
size_t instanceCount = it->GetInstanceCount();
for (size_t i = 0; i < instanceCount; ++i)
{
const FCDEntity* entity = it->GetInstance(i)->GetEntity();
if (entity != NULL && entity->HasType(FCDSceneNode::GetClassType())) queue.push_back((NODE_T*) entity);
}
}
}
}
else // depth first
{
// In depth-first mode, we need a breadth-first processing queue and a depth-first iteration queue.
typedef fm::pair<NODE_T*,size_t> Child;
fm::vector<Child> processQueue;
processQueue.reserve(8);
processQueue.push_back(Child(root, 0));
if (searchType == DEPTH_FIRST_PREORDER) queue.push_back(root);
while (!processQueue.empty())
{
Child& it = processQueue.back();
size_t nodeChildCount = it.first->GetChildrenCount();
size_t nodeInstanceCount = it.first->GetInstanceCount();
if (it.second < nodeChildCount)
{
NODE_T* add = it.first->GetChild(it.second++);
if (pureChildOnly && add->GetParent(0) != it.first) continue;
if (searchType == DEPTH_FIRST_PREORDER) queue.push_back(add);
if (add->GetChildrenCount() == 0 && add->GetInstanceCount() == 0)
{
// Don't bother processing this node.
if (searchType == DEPTH_FIRST_POSTORDER) queue.push_back(add);
}
else
{
processQueue.push_back(Child(add, 0));
}
}
else if (it.second < nodeChildCount + nodeInstanceCount && !pureChildOnly)
{
for (; it.second < nodeChildCount + nodeInstanceCount; ++it.second)
{
size_t instanceIndex = it.second - nodeChildCount;
const FCDEntity* entity = it.first->GetInstance(instanceIndex)->GetEntity();
if (entity != NULL && entity->HasType(FCDSceneNode::GetClassType()))
{
NODE_T* add = (NODE_T*) entity;
if (add->GetChildrenCount() == 0 && add->GetInstanceCount() == 0)
{
// Don't bother processing this node.
queue.push_back(add);
}
else
{
processQueue.push_back(Child(add, 0));
++(it.second);
break;
}
}
}
}
else
{
if (searchType == DEPTH_FIRST_POSTORDER) queue.push_back(it.first);
processQueue.pop_back();
}
}
}
iterator = 0;
}
template <class NODE_T>
FCDSceneNodeIteratorT<NODE_T>::~FCDSceneNodeIteratorT()
{
queue.clear();
}
template <class NODE_T>
NODE_T* FCDSceneNodeIteratorT<NODE_T>::GetNode()
{
return iterator < queue.size() ? queue[iterator] : NULL;
}
template <class NODE_T>
NODE_T* FCDSceneNodeIteratorT<NODE_T>::Next()
{
++iterator;
return iterator < queue.size() ? queue[iterator] : NULL;
}
|
