Panda3D
 All Classes Functions Variables Enumerations
findApproxLevelEntry.cxx
00001 // Filename: findApproxLevelEntry.cxx
00002 // Created by:  drose (13Mar02)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 #include "findApproxLevelEntry.h"
00016 #include "nodePathCollection.h"
00017 #include "pandaNode.h"
00018 #include "indent.h"
00019 
00020 TypeHandle FindApproxLevelEntry::_type_handle;
00021 
00022 ////////////////////////////////////////////////////////////////////
00023 //     Function: FindApproxLevelEntry::output
00024 //       Access: Public
00025 //  Description: Formats the entry for meaningful output.  For
00026 //               debugging only.
00027 ////////////////////////////////////////////////////////////////////
00028 void FindApproxLevelEntry::
00029 output(ostream &out) const {
00030   out << "(" << _node_path << "):";
00031   if (is_solution(0)) {
00032     out << " solution!";
00033   } else {
00034     out << "(";
00035     _approx_path.output_component(out, _i);
00036     out << ")," << _i;
00037   }
00038 }
00039 
00040 ////////////////////////////////////////////////////////////////////
00041 //     Function: FindApproxLevelEntry::write_level
00042 //       Access: Public
00043 //  Description: Writes the entire level (a linked list of entries
00044 //               beginning at this entry).  For debugging only.
00045 ////////////////////////////////////////////////////////////////////
00046 void FindApproxLevelEntry::
00047 write_level(ostream &out, int indent_level) const {
00048   for (const FindApproxLevelEntry *entry = this;
00049        entry != (const FindApproxLevelEntry *)NULL;
00050        entry = entry->_next) {
00051     indent(out, indent_level);
00052     out << *entry << "\n";
00053   }
00054 }
00055 
00056 ////////////////////////////////////////////////////////////////////
00057 //     Function: FindApproxLevelEntry::consider_node
00058 //       Access: Public
00059 //  Description: Considers the node represented by the entry for
00060 //               matching the find path.  If a solution is found, it
00061 //               is added to result; if the children of this node
00062 //               should be considered, the appropriate entries are
00063 //               added to next_level.
00064 //
00065 //               The return value is true if result now contains
00066 //               max_matches solutions, or false if we should keep
00067 //               looking.
00068 ////////////////////////////////////////////////////////////////////
00069 bool FindApproxLevelEntry::
00070 consider_node(NodePathCollection &result, FindApproxLevelEntry *&next_level,
00071               int max_matches, int increment) const {
00072   if (is_solution(increment)) {
00073     // If the entry represents a solution, save it and we're done with
00074     // the entry.
00075     result.add_path(_node_path.get_node_path());
00076     if (max_matches > 0 && result.get_num_paths() >= max_matches) { 
00077       return true;
00078     }
00079 
00080     return false;
00081   }
00082 
00083   // If the entry is not itself a solution, consider its children.
00084 
00085   if (_approx_path.is_component_match_many(_i + increment)) {
00086     // Match any number, zero or more, levels of nodes.  This is the
00087     // tricky case that requires this whole nutty breadth-first thing.
00088 
00089     // This means we must reconsider our own entry with the next path
00090     // entry, before we consider the next entry--this supports
00091     // matching zero levels of nodes.
00092 
00093     // We used to make a temporary copy of our own record, and then
00094     // increment _i on that copy, but we can't do that nowadays
00095     // because the WorkingNodePath object stores a pointer to each
00096     // previous generation, which means we can't use any temporary
00097     // FindApproxLevelEntry objects.  Instead, we pass around the
00098     // increment parameter, which increments _i on the fly.
00099 
00100     if (consider_node(result, next_level, max_matches, increment + 1)) {
00101       return true;
00102     }
00103   }
00104 
00105   PandaNode *this_node = _node_path.node();
00106   nassertr(this_node != (PandaNode *)NULL, false);
00107 
00108   bool stashed_only = next_is_stashed(increment);
00109 
00110   if (!stashed_only) {
00111     // Check the normal list of children.
00112     PandaNode::Children children = this_node->get_children();
00113     int num_children = children.get_num_children();
00114     for (int i = 0; i < num_children; i++) {
00115       PandaNode *child_node = children.get_child(i);
00116       
00117       consider_next_step(child_node, next_level, increment);
00118     }
00119   }
00120 
00121   if (_approx_path.return_stashed() || stashed_only) {
00122     // Also check the stashed list.
00123     int num_stashed = this_node->get_num_stashed();
00124     for (int i = 0; i < num_stashed; i++) {
00125       PandaNode *stashed_node = this_node->get_stashed(i);
00126       
00127       consider_next_step(stashed_node, next_level, increment);
00128     }
00129   }
00130 
00131   return false;
00132 }
00133 
00134 ////////////////////////////////////////////////////////////////////
00135 //     Function: FindApproxLevelEntry::consider_next_step
00136 //       Access: Public
00137 //  Description: Compares the indicated child node (which is assumed
00138 //               to be a child of _node_path) with the next component
00139 //               of the path.  If it matches, generates whatever
00140 //               additional entries are appropriate and stores them in
00141 //               next_level.
00142 ////////////////////////////////////////////////////////////////////
00143 void FindApproxLevelEntry::
00144 consider_next_step(PandaNode *child_node, FindApproxLevelEntry *&next_level, 
00145                    int increment) const {
00146   nassertv(child_node != _node_path.node());
00147 
00148   if (!_approx_path.return_hidden() && child_node->is_overall_hidden()) {
00149     // If the approx path does not allow us to return hidden nodes,
00150     // and this node has indeed been completely hidden, then stop
00151     // here.
00152     return;
00153   }
00154 
00155   nassertv(_i + increment < _approx_path.get_num_components());
00156 
00157   if (_approx_path.is_component_match_many(_i + increment)) {
00158     // Match any number, zero or more, levels of nodes.  This is the
00159     // tricky case that requires this whole nutty breadth-first thing.
00160 
00161     // And now we just add the next entry without incrementing its
00162     // path entry.
00163 
00164     next_level = new FindApproxLevelEntry
00165       (*this, child_node, _i + increment, next_level);
00166 
00167   } else {
00168     if (_approx_path.matches_component(_i + increment, child_node)) {
00169       // That matched, and it consumes one path entry.
00170       next_level = new FindApproxLevelEntry
00171         (*this, child_node, _i + increment + 1, next_level);
00172     }
00173   }
00174 }
 All Classes Functions Variables Enumerations