PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // ObjectGraphIterator.cc 00004 // 00005 // Copyright (C) 2005 Nicolas Chapados 00006 // 00007 // Redistribution and use in source and binary forms, with or without 00008 // modification, are permitted provided that the following conditions are met: 00009 // 00010 // 1. Redistributions of source code must retain the above copyright 00011 // notice, this list of conditions and the following disclaimer. 00012 // 00013 // 2. Redistributions in binary form must reproduce the above copyright 00014 // notice, this list of conditions and the following disclaimer in the 00015 // documentation and/or other materials provided with the distribution. 00016 // 00017 // 3. The name of the authors may not be used to endorse or promote 00018 // products derived from this software without specific prior written 00019 // permission. 00020 // 00021 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR 00022 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00023 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN 00024 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00025 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 00026 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 00027 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 00028 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00029 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00030 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00031 // 00032 // This file is part of the PLearn library. For more information on the PLearn 00033 // library, go to the PLearn Web site at www.plearn.org 00034 00035 /* ******************************************************* 00036 * $Id: .pyskeleton_header 544 2003-09-01 00:05:31Z plearner $ 00037 ******************************************************* */ 00038 00039 // Authors: Nicolas Chapados 00040 00043 #include <plearn/base/Object.h> 00044 #include <algorithm> 00045 #include <assert.h> 00046 #include <deque> 00047 #include <set> 00048 00049 #include "ObjectGraphIterator.h" 00050 //#include <plearn/base/Object.h> 00051 #include <plearn/base/OptionBase.h> 00052 #include <plearn/base/TypeFactory.h> 00053 00054 namespace PLearn { 00055 using namespace std; 00056 00057 00058 //##### ObjectOptionsIterator ############################################### 00059 00060 ObjectOptionsIterator::ObjectOptionsIterator() 00061 : m_invalid(true), 00062 m_ignore_nontraversable(false), 00063 m_skip_nulls(true), 00064 m_object(0), 00065 m_options(0), 00066 m_cur_option(), 00067 m_cur_index(), 00068 m_max_index() 00069 { } 00070 00071 00072 ObjectOptionsIterator::ObjectOptionsIterator(const Object* root, 00073 bool ignore_nontraversable, 00074 bool skip_nulls) 00075 : m_invalid(true), 00076 m_ignore_nontraversable(ignore_nontraversable), 00077 m_skip_nulls(skip_nulls), 00078 m_object(root), 00079 m_options(0), 00080 m_cur_option(), 00081 m_cur_index(), 00082 m_max_index() 00083 { 00084 if (m_object) { 00085 m_options = &m_object->getOptionList(); 00086 PLASSERT( m_options ); 00087 00088 if (m_options->size() > 0) { 00089 m_invalid = false; 00090 m_cur_option = -1; 00091 ++(*this); // find first valid option 00092 } 00093 } 00094 } 00095 00096 00097 bool ObjectOptionsIterator::operator==(const ObjectOptionsIterator& rhs) const 00098 { 00099 return (m_invalid && rhs.m_invalid) || 00100 (! m_invalid && 00101 m_object == rhs.m_object && 00102 m_options == rhs.m_options && 00103 m_cur_option == rhs.m_cur_option && 00104 m_cur_index == rhs.m_cur_index && 00105 m_max_index == rhs.m_max_index); 00106 } 00107 00108 00109 const Object* ObjectOptionsIterator::operator*() const 00110 { 00111 PLASSERT( !m_invalid && m_object && m_options ); 00112 00113 if (m_max_index > 0) 00114 return (*m_options)[m_cur_option]->getIndexedObject(m_object, 00115 m_cur_index); 00116 else 00117 return (*m_options)[m_cur_option]->getAsObject(m_object); 00118 } 00119 00120 00121 string ObjectOptionsIterator::getCurrentOptionName() const 00122 { 00123 PLASSERT( !m_invalid && m_object && m_options ); 00124 string optionname = (*m_options)[m_cur_option]->optionname(); 00125 if (m_max_index > 0) 00126 optionname += '[' + tostring(m_cur_index) + ']'; 00127 return optionname; 00128 } 00129 00130 00131 OptionBase::flag_t ObjectOptionsIterator::getCurrentOptionFlags() const 00132 { 00133 PLASSERT( !m_invalid && m_object && m_options ); 00134 return (*m_options)[m_cur_option]->flags(); 00135 } 00136 00137 00138 const ObjectOptionsIterator& ObjectOptionsIterator::operator++() 00139 { 00140 PLASSERT( !m_invalid && m_object && m_options ); 00141 00142 do { 00143 // Start by considering current iteration within an indexable option 00144 if (m_max_index > 0) { 00145 ++m_cur_index; 00146 PLASSERT( m_cur_index <= m_max_index ); 00147 if (m_cur_index < m_max_index) 00148 return *this; 00149 } 00150 00151 // Otherwise find next option accessible as object, and that is not 00152 // marked with the 'nontraversable' flag (assuming 00153 // 'ignore_nontraversable' is not set). Go to invalid state if cannot 00154 // find any 00155 const int n = m_options->size(); 00156 for ( ++m_cur_option ; m_cur_option < n ; ++m_cur_option ) { 00157 if ( (*m_options)[m_cur_option]->isAccessibleAsObject() && 00158 ( m_ignore_nontraversable || 00159 ! ((*m_options)[m_cur_option]->flags() & OptionBase::nontraversable)) ) 00160 { 00161 m_cur_index = 0; 00162 m_max_index = (*m_options)[m_cur_option]->indexableSize(m_object); 00163 break; 00164 } 00165 } 00166 00167 m_invalid = (m_cur_option >= n); 00168 00169 // Condition below: keep incrementing as long as we are hitting a null 00170 // object (and skipping nulls is requested), or an empty array/vector 00171 } while (!m_invalid && 00172 ( (!m_max_index && m_skip_nulls && !**this) || 00173 ( m_max_index && m_cur_index >= m_max_index ) )); 00174 00175 return *this; 00176 } 00177 00178 00179 //##### ObjectGraphIterator ################################################# 00180 00181 ObjectGraphIterator::ObjectGraphIterator(): 00182 m_it(0), 00183 m_end(0), 00184 m_isa_tester() 00185 { } 00186 00187 00188 ObjectGraphIterator::ObjectGraphIterator( 00189 const Object* root, TraversalType tt, 00190 bool compute_optnames, const string& base_class_filter) 00191 : m_isa_tester() 00192 { 00193 // Build the traversal graph 00194 buildTraversalGraph(root, tt, compute_optnames); 00195 m_it = m_object_list.begin(); 00196 m_end = m_object_list.end(); 00197 00198 // Filter by base-class if required 00199 if (base_class_filter != "") { 00200 const TypeMapEntry& tme = 00201 TypeFactory::instance().getTypeMapEntry(base_class_filter); 00202 m_isa_tester = tme.isa_method; 00203 if (! m_isa_tester) 00204 PLERROR("ObjectGraphIterator: requested type filter \"%s\" does not " 00205 "have an ISA type predicate function", base_class_filter.c_str()); 00206 } 00207 00208 // If first object is not acceptable according to predicate, skip to next 00209 // valid object 00210 if (!invalid() && m_isa_tester && !m_isa_tester(**this)) 00211 ++(*this); 00212 } 00213 00214 00215 bool ObjectGraphIterator::operator==(const ObjectGraphIterator& rhs) const 00216 { 00217 return (invalid() && rhs.invalid()) || 00218 (! invalid() && 00219 m_it == rhs.m_it && 00220 m_end == rhs.m_end); 00221 } 00222 00223 00224 const ObjectGraphIterator& ObjectGraphIterator::operator++() 00225 { 00226 PLASSERT( !invalid() ); 00227 for ( ++m_it ; m_it != m_end && m_isa_tester && !m_isa_tester(**this) ; ++m_it ) 00228 continue; 00229 return *this; 00230 } 00231 00232 00233 //##### buildTraversalGraph ################################################# 00234 00235 void ObjectGraphIterator::buildTraversalGraph(const Object* root, 00236 TraversalType tt, 00237 bool compute_optnames) 00238 { 00239 // The deque is used to maintain either a FIFO or LIFO of nodes to visit. 00240 // Deletion is always carried out with a pop_back. 00241 typedef std::deque<ObjectAndName> Q; 00242 typedef std::set<const Object*> SeenSet; 00243 typedef void (Q::*QAppender)(Q::const_reference); 00244 00245 Q object_queue; 00246 SeenSet seen; 00247 const SeenSet::iterator not_seen = seen.end(); 00248 QAppender appender; 00249 00250 bool ignore_nontraversable = tt & IgnoreNonTraversable; 00251 tt = TraversalType(int(tt) & ~IgnoreNonTraversable); 00252 00253 switch (tt & ~Reversed) { 00254 case BreadthOrder : appender = &Q::push_front; break; 00255 case DepthPreOrder : appender = &Q::push_back; break; 00256 default: 00257 PLERROR("ObjectGraphIterator::buildTraversalGraph: unknown traversal type (%d)",tt); 00258 } 00259 00260 // Start out by appending the root 00261 m_object_list.resize(0); 00262 (object_queue.*appender)(make_pair(root, "")); 00263 seen.insert(root); 00264 00265 // Traverse the graph 00266 while (object_queue.size() > 0) { 00267 ObjectAndName cur_objname = object_queue.back(); 00268 object_queue.pop_back(); 00269 m_object_list.push_back(cur_objname); 00270 00271 ObjectOptionsIterator options(cur_objname.first, ignore_nontraversable), 00272 end_options; 00273 for ( ; options != end_options ; ++options) { 00274 const Object* candidate_object = *options; 00275 if (candidate_object && seen.find(candidate_object) == not_seen) { 00276 string new_optname; 00277 if (compute_optnames) { 00278 new_optname = cur_objname.second; 00279 if (new_optname != "") 00280 new_optname += "."; 00281 new_optname += options.getCurrentOptionName(); 00282 } 00283 (object_queue.*appender)(make_pair(candidate_object, 00284 new_optname)); 00285 seen.insert(candidate_object); 00286 } 00287 } 00288 } 00289 00290 // Finally reverse the elements if required 00291 if (tt & Reversed) 00292 std::reverse(m_object_list.begin(), m_object_list.end()); 00293 } 00294 00295 00296 //##### setoption_broadcast ################################################# 00297 00298 void setoption_broadcast(const Object* o, const string& class_name, 00299 const string& option_name, const string& option_value, 00300 ObjectGraphIterator::TraversalType tt) 00301 { 00302 ObjectGraphIterator grit(o, tt, false, class_name), grend; 00303 for ( ; grit != grend ; ++grit) 00304 const_cast<Object*>(*grit)->setOption(option_name, option_value); 00305 } 00306 00307 } // end of namespace PLearn 00308 00309 00310 /* 00311 Local Variables: 00312 mode:c++ 00313 c-basic-offset:4 00314 c-file-style:"stroustrup" 00315 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00316 indent-tabs-mode:nil 00317 fill-column:79 00318 End: 00319 */ 00320 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :