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
14 #include "findApproxLevelEntry.h"
15 #include "nodePathCollection.h"
16 #include "pandaNode.h"
17 #include "indent.h"
18
19 TypeHandle FindApproxLevelEntry::_type_handle;
20
21 /**
22 * Formats the entry for meaningful output. For debugging only.
23 */
24 void FindApproxLevelEntry::
25 output(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 */
40 void FindApproxLevelEntry::
41 write_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 */
58 bool FindApproxLevelEntry::
59 consider_node(NodePathCollection &result, FindApproxLevelEntry *&next_level,
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 */
128 void FindApproxLevelEntry::
129 consider_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 }
FindApproxLevelEntry
This class is local to this package only; it doesn't get exported.
Definition: findApproxLevelEntry.h:29
FindApproxLevelEntry::next_is_stashed
bool next_is_stashed(int increment) const
Returns true if the next node matched by this entry must be a stashed node, false otherwise.
Definition: findApproxLevelEntry.I:74
FindApproxLevelEntry::is_solution
bool is_solution(int increment) const
Returns true if this entry represents a solution to the search; i.e.
Definition: findApproxLevelEntry.I:83
FindApproxLevelEntry::write_level
void write_level(std::ostream &out, int indent_level) const
Writes the entire level (a linked list of entries beginning at this entry).
Definition: findApproxLevelEntry.cxx:41
FindApproxLevelEntry::consider_node
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.
Definition: findApproxLevelEntry.cxx:59
FindApproxLevelEntry::consider_next_step
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...
Definition: findApproxLevelEntry.cxx:129
FindApproxLevelEntry::output
void output(std::ostream &out) const
Formats the entry for meaningful output.
Definition: findApproxLevelEntry.cxx:25
FindApproxPath::matches_component
bool matches_component(int index, PandaNode *node) const
Returns true if the nth component of the path matches the indicated node, false otherwise.
Definition: findApproxPath.I:47
FindApproxPath::output_component
void output_component(std::ostream &out, int index) const
Formats the nth component of the path to the indicated output stream.
Definition: findApproxPath.I:96
FindApproxPath::return_hidden
bool return_hidden() const
Returns true if this path allows returning of hidden nodes, false otherwise.
Definition: findApproxPath.I:70
FindApproxPath::return_stashed
bool return_stashed() const
Returns true if this path allows returning of stashed nodes, false otherwise.
Definition: findApproxPath.I:79
FindApproxPath::is_component_match_many
bool is_component_match_many(int index) const
Returns true if the nth component is of type match_many, which will require special handling.
Definition: findApproxPath.I:37
FindApproxPath::get_num_components
int get_num_components() const
Returns the number of components in the path.
Definition: findApproxPath.I:28
NodePathCollection
This is a set of zero or more NodePaths.
Definition: nodePathCollection.h:26
NodePathCollection::add_path
void add_path(const NodePath &node_path)
Adds a new NodePath to the collection.
Definition: nodePathCollection.cxx:29
NodePathCollection::get_num_paths
get_num_paths
Returns the number of NodePaths in the collection.
Definition: nodePathCollection.h:47
PandaNode::Children
Definition: pandaNode.h:706
PandaNode::Children::get_child
PandaNode * get_child(size_t n) const
Returns the nth child of the node.
Definition: pandaNode.I:962
PandaNode::Children::get_num_children
size_t get_num_children() const
Returns the number of children of the node.
Definition: pandaNode.I:953
PandaNode
A basic node of the scene graph or data graph.
Definition: pandaNode.h:65
PandaNode::is_overall_hidden
is_overall_hidden
Returns true if the node has been hidden to all cameras by clearing its overall bit.
Definition: pandaNode.h:248
PandaNode::get_num_stashed
get_num_stashed
Returns the number of stashed nodes this node has.
Definition: pandaNode.h:148
PandaNode::get_stashed
get_stashed
Returns the nth stashed child of this node.
Definition: pandaNode.h:148
PandaNode::get_children
get_children
Returns an object that can be used to walk through the list of children of the node.
Definition: pandaNode.h:782
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
WorkingNodePath::node
PandaNode * node() const
Returns the node traversed to so far.
Definition: workingNodePath.I:89
WorkingNodePath::get_node_path
get_node_path
Constructs and returns an actual NodePath that represents the same path we have just traversed.
Definition: workingNodePath.h:60
findApproxLevelEntry.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
indent
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition: indent.cxx:20
indent.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
nodePathCollection.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
pandaNode.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.