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