PLearn 0.1
ObjectGraphIterator.cc
Go to the documentation of this file.
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 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines