Panda3D
findApproxLevelEntry.cxx
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file findApproxLevelEntry.cxx
10 * @author drose
11 * @date 2002-03-13
12 */
13
15#include "nodePathCollection.h"
16#include "pandaNode.h"
17#include "indent.h"
18
19TypeHandle FindApproxLevelEntry::_type_handle;
20
21/**
22 * Formats the entry for meaningful output. For debugging only.
23 */
25output(std::ostream &out) const {
26 out << "(" << _node_path << "):";
27 if (is_solution(0)) {
28 out << " solution!";
29 } else {
30 out << "(";
31 _approx_path.output_component(out, _i);
32 out << ")," << _i;
33 }
34}
35
36/**
37 * Writes the entire level (a linked list of entries beginning at this entry).
38 * For debugging only.
39 */
41write_level(std::ostream &out, int indent_level) const {
42 for (const FindApproxLevelEntry *entry = this;
43 entry != nullptr;
44 entry = entry->_next) {
45 indent(out, indent_level);
46 out << *entry << "\n";
47 }
48}
49
50/**
51 * Considers the node represented by the entry for matching the find path. If
52 * a solution is found, it is added to result; if the children of this node
53 * should be considered, the appropriate entries are added to next_level.
54 *
55 * The return value is true if result now contains max_matches solutions, or
56 * false if we should keep looking.
57 */
60 int max_matches, int increment) const {
61 if (is_solution(increment)) {
62 // If the entry represents a solution, save it and we're done with the
63 // entry.
64 result.add_path(_node_path.get_node_path());
65 if (max_matches > 0 && result.get_num_paths() >= max_matches) {
66 return true;
67 }
68
69 return false;
70 }
71
72 // If the entry is not itself a solution, consider its children.
73
74 if (_approx_path.is_component_match_many(_i + increment)) {
75 // Match any number, zero or more, levels of nodes. This is the tricky
76 // case that requires this whole nutty breadth-first thing.
77
78 // This means we must reconsider our own entry with the next path entry,
79 // before we consider the next entry--this supports matching zero levels
80 // of nodes.
81
82 // We used to make a temporary copy of our own record, and then increment
83 // _i on that copy, but we can't do that nowadays because the
84 // WorkingNodePath object stores a pointer to each previous generation,
85 // which means we can't use any temporary FindApproxLevelEntry objects.
86 // Instead, we pass around the increment parameter, which increments _i on
87 // the fly.
88
89 if (consider_node(result, next_level, max_matches, increment + 1)) {
90 return true;
91 }
92 }
93
94 PandaNode *this_node = _node_path.node();
95 nassertr(this_node != nullptr, false);
96
97 bool stashed_only = next_is_stashed(increment);
98
99 if (!stashed_only) {
100 // Check the normal list of children.
101 PandaNode::Children children = this_node->get_children();
102 int num_children = children.get_num_children();
103 for (int i = 0; i < num_children; i++) {
104 PandaNode *child_node = children.get_child(i);
105
106 consider_next_step(child_node, next_level, increment);
107 }
108 }
109
110 if (_approx_path.return_stashed() || stashed_only) {
111 // Also check the stashed list.
112 int num_stashed = this_node->get_num_stashed();
113 for (int i = 0; i < num_stashed; i++) {
114 PandaNode *stashed_node = this_node->get_stashed(i);
115
116 consider_next_step(stashed_node, next_level, increment);
117 }
118 }
119
120 return false;
121}
122
123/**
124 * Compares the indicated child node (which is assumed to be a child of
125 * _node_path) with the next component of the path. If it matches, generates
126 * whatever additional entries are appropriate and stores them in next_level.
127 */
129consider_next_step(PandaNode *child_node, FindApproxLevelEntry *&next_level,
130 int increment) const {
131 nassertv(child_node != _node_path.node());
132
133 if (!_approx_path.return_hidden() && child_node->is_overall_hidden()) {
134 // If the approx path does not allow us to return hidden nodes, and this
135 // node has indeed been completely hidden, then stop here.
136 return;
137 }
138
139 nassertv(_i + increment < _approx_path.get_num_components());
140
141 if (_approx_path.is_component_match_many(_i + increment)) {
142 // Match any number, zero or more, levels of nodes. This is the tricky
143 // case that requires this whole nutty breadth-first thing.
144
145 // And now we just add the next entry without incrementing its path entry.
146
147 next_level = new FindApproxLevelEntry
148 (*this, child_node, _i + increment, next_level);
149
150 } else {
151 if (_approx_path.matches_component(_i + increment, child_node)) {
152 // That matched, and it consumes one path entry.
153 next_level = new FindApproxLevelEntry
154 (*this, child_node, _i + increment + 1, next_level);
155 }
156 }
157}
This class is local to this package only; it doesn't get exported.
bool next_is_stashed(int increment) const
Returns true if the next node matched by this entry must be a stashed node, false otherwise.
bool is_solution(int increment) const
Returns true if this entry represents a solution to the search; i.e.
void write_level(std::ostream &out, int indent_level) const
Writes the entire level (a linked list of entries beginning at this entry).
bool consider_node(NodePathCollection &result, FindApproxLevelEntry *&next_level, int max_matches, int increment) const
Considers the node represented by the entry for matching the find path.
void consider_next_step(PandaNode *child_node, FindApproxLevelEntry *&next_level, int increment) const
Compares the indicated child node (which is assumed to be a child of _node_path) with the next compon...
void output(std::ostream &out) const
Formats the entry for meaningful output.
bool matches_component(int index, PandaNode *node) const
Returns true if the nth component of the path matches the indicated node, false otherwise.
void output_component(std::ostream &out, int index) const
Formats the nth component of the path to the indicated output stream.
bool return_hidden() const
Returns true if this path allows returning of hidden nodes, false otherwise.
bool return_stashed() const
Returns true if this path allows returning of stashed nodes, false otherwise.
bool is_component_match_many(int index) const
Returns true if the nth component is of type match_many, which will require special handling.
int get_num_components() const
Returns the number of components in the path.
This is a set of zero or more NodePaths.
void add_path(const NodePath &node_path)
Adds a new NodePath to the collection.
get_num_paths
Returns the number of NodePaths in the collection.
PandaNode * get_child(size_t n) const
Returns the nth child of the node.
Definition: pandaNode.I:962
size_t get_num_children() const
Returns the number of children of the node.
Definition: pandaNode.I:953
A basic node of the scene graph or data graph.
Definition: pandaNode.h:65
is_overall_hidden
Returns true if the node has been hidden to all cameras by clearing its overall bit.
Definition: pandaNode.h:248
get_num_stashed
Returns the number of stashed nodes this node has.
Definition: pandaNode.h:148
get_stashed
Returns the nth stashed child of this node.
Definition: pandaNode.h:148
get_children
Returns an object that can be used to walk through the list of children of the node.
Definition: pandaNode.h:782
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
PandaNode * node() const
Returns the node traversed to so far.
get_node_path
Constructs and returns an actual NodePath that represents the same path we have just traversed.
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition: dcindent.cxx:22
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.