Calls the walker with each node starting with the top node and continues depth first The walker can signal to skip the children if false is returned.
Additionally this version allows for a priority measure that determines which child is traversed first.
140 {
141 static_assert(std::is_assignable<std::function<bool(Node*)>, AWalker>(), "");
142 static_assert(std::is_assignable<std::function<float(Node*)>, APriorityMeasure>(), "");
143
144 bool walkChildren = walker(this);
146 if (children and walkChildren) {
147 std::vector<std::pair<float, Node*> > prioritisedChildNodes;
148 size_t nChildren = children->size();
149
150 prioritisedChildNodes.reserve(nChildren);
151
152 for (Node& childNode : *children) {
153 float childPriority = priority(&childNode);
154 if (std::isnan(childPriority)) continue;
155 prioritisedChildNodes.push_back(std::make_pair(childPriority, &childNode));
156 }
157
158 std::make_heap(prioritisedChildNodes.begin(), prioritisedChildNodes.end());
159
160 while (not prioritisedChildNodes.empty()) {
161 std::pop_heap(prioritisedChildNodes.begin(), prioritisedChildNodes.end());
162 Node* priorityChildNode = prioritisedChildNodes.back().second;
163 prioritisedChildNodes.pop_back();
164
165 priorityChildNode->walk(walker, priority);
166
167
168 bool reheap = false;
169 erase_remove_if(prioritisedChildNodes,
170 [&reheap, &priority](std::pair<float, Node*>& prioritisedChildNode) {
171 float childPriority = priority(prioritisedChildNode.second);
172 if (std::isnan(childPriority)) return true;
173
174 reheap |= prioritisedChildNode.first != childPriority;
175 prioritisedChildNode.first = childPriority;
176 return false;
177 });
178
179 if (reheap) {
180 std::make_heap(prioritisedChildNodes.begin(), prioritisedChildNodes.end());
181 }
182 }
183 assert(prioritisedChildNodes.empty());
184 }
185 }
1.9.6