PLearn 0.1
Public Types | Public Member Functions | Static Public Attributes | Protected Types | Protected Member Functions | Protected Attributes
PLearn::ObjectGraphIterator Class Reference

An ObjectGraphIterator iterates through all objects through options. More...

#include <ObjectGraphIterator.h>

Collaboration diagram for PLearn::ObjectGraphIterator:
Collaboration graph
[legend]

List of all members.

Public Types

enum  TraversalType { BreadthOrder = 1, DepthPreOrder = 2, ReversedBreadthOrder = 64 | 1, ReversedDepthPreOrder = 64 | 2 }
 Specify the kinds of supported traversals. More...

Public Member Functions

 ObjectGraphIterator ()
 Default constructor makes an "invalid" iterator.
 ObjectGraphIterator (const Object *root, TraversalType tt=DepthPreOrder, bool compute_optnames=false, const std::string &base_class_filter="")
 Usual constructor to iterate over an object graph.
bool invalid () const
 Return true if the iterator is in an invalid state;.
bool operator== (const ObjectGraphIterator &rhs) const
 Equality testing; two invalid iterators always compare equal.
bool operator!= (const ObjectGraphIterator &rhs) const
 Inequality testing.
const Objectoperator* () const
 Dereference: access the current sub-object.
const string & getCurrentOptionName () const
 Return the option "pathname" to retrieve the option using getOption() on the root object.
const ObjectGraphIteratoroperator++ ()
 Go to next object or "invalid" state if end of iteration.
ObjectGraphIterator operator++ (int)
 Post-increment: implemented in terms of pre-increment.

Static Public Attributes

static const int Reversed = 64
 For convenience, you can bitwise-or this value with normal traversal types to get the reversed ones.
static const int IgnoreNonTraversable = 128
 If this option is true, traverse even non-traversable options.

Protected Types

typedef pair< const Object
*, string > 
ObjectAndName
typedef std::vector
< ObjectAndName
ObjectList
typedef bool(* ISA )(const Object *)

Protected Member Functions

void buildTraversalGraph (const Object *root, TraversalType tt, bool compute_optnames)
 Build a traversal graph from a root node; filters are not yet taken into account at this point.

Protected Attributes

ObjectList m_object_list
 from buildTraversalGraph()
ObjectList::iterator m_it
 Iterator within m_object_list.
ObjectList::iterator m_end
 End of m_object_list.
ISA m_isa_tester
 Predicate for sub-type filter.

Detailed Description

An ObjectGraphIterator iterates through all objects through options.

From a starting "root" object, the iterator returns pointers to each encountered object in the graph that is accessible through options. Since this is "real" graph traversal, the same object is not returned twice.

The following options are available:

The current implementation starts out by building a traversal list which records the set of all objects in the graph in the order in which they should be returned. Then the iteration per se is simply an STL-like forward iterator that performs the appropriate filterings.

The iterator skips ALL NULL POINTERS in unused options.

Definition at line 184 of file ObjectGraphIterator.h.


Member Typedef Documentation

typedef bool(* PLearn::ObjectGraphIterator::ISA)(const Object *) [protected]

Definition at line 289 of file ObjectGraphIterator.h.

typedef pair<const Object*, string> PLearn::ObjectGraphIterator::ObjectAndName [protected]

Definition at line 287 of file ObjectGraphIterator.h.

typedef std::vector<ObjectAndName> PLearn::ObjectGraphIterator::ObjectList [protected]

Definition at line 288 of file ObjectGraphIterator.h.


Member Enumeration Documentation

Specify the kinds of supported traversals.

If you use the "Reversed" versions, you obtain the elements in reverse order than what you would normally obtain.

Enumerator:
BreadthOrder 
DepthPreOrder 
ReversedBreadthOrder 
ReversedDepthPreOrder 

Definition at line 192 of file ObjectGraphIterator.h.


Constructor & Destructor Documentation

PLearn::ObjectGraphIterator::ObjectGraphIterator ( )

Default constructor makes an "invalid" iterator.

Definition at line 181 of file ObjectGraphIterator.cc.

                                        :
    m_it(0),
    m_end(0),
    m_isa_tester()
{ }
PLearn::ObjectGraphIterator::ObjectGraphIterator ( const Object root,
TraversalType  tt = DepthPreOrder,
bool  compute_optnames = false,
const std::string &  base_class_filter = "" 
)

Usual constructor to iterate over an object graph.

Parameters:
rootStarting object from which to start the iteration
ttType of traversal, e.g. BreadthOrder or DepthPreOrder
compute_optnamesWhether the function getCurrentOptionName() returns something meaningful; this slows down computations a bit
base_class_filterName of base class to filter results; it is guaranteed that the returned objects will be of a class derived from this one

Definition at line 188 of file ObjectGraphIterator.cc.

References buildTraversalGraph(), PLearn::TypeFactory::getTypeMapEntry(), PLearn::TypeFactory::instance(), invalid(), PLearn::TypeMapEntry::isa_method, m_end, m_isa_tester, m_it, m_object_list, and PLERROR.

    : m_isa_tester()
{
    // Build the traversal graph
    buildTraversalGraph(root, tt, compute_optnames);
    m_it  = m_object_list.begin();
    m_end = m_object_list.end();

    // Filter by base-class if required
    if (base_class_filter != "") {
        const TypeMapEntry& tme =
            TypeFactory::instance().getTypeMapEntry(base_class_filter);
        m_isa_tester = tme.isa_method;
        if (! m_isa_tester)
            PLERROR("ObjectGraphIterator: requested type filter \"%s\" does not "
                    "have an ISA type predicate function", base_class_filter.c_str());
    }

    // If first object is not acceptable according to predicate, skip to next
    // valid object
    if (!invalid() && m_isa_tester && !m_isa_tester(**this))
        ++(*this);
}

Here is the call graph for this function:


Member Function Documentation

void PLearn::ObjectGraphIterator::buildTraversalGraph ( const Object root,
TraversalType  tt,
bool  compute_optnames 
) [protected]

Build a traversal graph from a root node; filters are not yet taken into account at this point.

Definition at line 235 of file ObjectGraphIterator.cc.

References BreadthOrder, DepthPreOrder, IgnoreNonTraversable, m_object_list, PLERROR, and Reversed.

Referenced by ObjectGraphIterator().

{
    // The deque is used to maintain either a FIFO or LIFO of nodes to visit.
    // Deletion is always carried out with a pop_back.
    typedef std::deque<ObjectAndName> Q;
    typedef std::set<const Object*> SeenSet;
    typedef void (Q::*QAppender)(Q::const_reference);

    Q object_queue;
    SeenSet seen;
    const SeenSet::iterator not_seen = seen.end();
    QAppender appender;

    bool ignore_nontraversable = tt & IgnoreNonTraversable;
    tt = TraversalType(int(tt) & ~IgnoreNonTraversable);
    
    switch (tt & ~Reversed) {
    case BreadthOrder  : appender = &Q::push_front; break;
    case DepthPreOrder : appender = &Q::push_back;  break;
    default:
        PLERROR("ObjectGraphIterator::buildTraversalGraph: unknown traversal type (%d)",tt);
    }

    // Start out by appending the root
    m_object_list.resize(0);
    (object_queue.*appender)(make_pair(root, ""));
    seen.insert(root);

    // Traverse the graph
    while (object_queue.size() > 0) {
        ObjectAndName cur_objname = object_queue.back();
        object_queue.pop_back();
        m_object_list.push_back(cur_objname);

        ObjectOptionsIterator options(cur_objname.first, ignore_nontraversable),
                              end_options;
        for ( ; options != end_options ; ++options) {
            const Object* candidate_object = *options;
            if (candidate_object && seen.find(candidate_object) == not_seen) {
                string new_optname;
                if (compute_optnames) {
                    new_optname = cur_objname.second;
                    if (new_optname != "")
                        new_optname += ".";
                    new_optname += options.getCurrentOptionName();
                }
                (object_queue.*appender)(make_pair(candidate_object,
                                                   new_optname));
                seen.insert(candidate_object);
            }
        }
    }

    // Finally reverse the elements if required
    if (tt & Reversed)
        std::reverse(m_object_list.begin(), m_object_list.end());
}

Here is the caller graph for this function:

const string& PLearn::ObjectGraphIterator::getCurrentOptionName ( ) const [inline]

Return the option "pathname" to retrieve the option using getOption() on the root object.

This will be the empty string for the root object, or if the iterator was constructed with the option compute_optnames set to 'false'.

Definition at line 262 of file ObjectGraphIterator.h.

References invalid(), m_it, and PLASSERT.

Referenced by PLearn::iterate().

    {
        PLASSERT( !invalid() );
        return m_it->second;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

bool PLearn::ObjectGraphIterator::invalid ( ) const [inline]

Return true if the iterator is in an invalid state;.

Definition at line 236 of file ObjectGraphIterator.h.

References m_end, and m_it.

Referenced by getCurrentOptionName(), ObjectGraphIterator(), operator*(), operator++(), and operator==().

    {
        return m_it == m_end;
    }

Here is the caller graph for this function:

bool PLearn::ObjectGraphIterator::operator!= ( const ObjectGraphIterator rhs) const [inline]

Inequality testing.

Definition at line 245 of file ObjectGraphIterator.h.

    {
        return ! (*this == rhs);
    }
const Object* PLearn::ObjectGraphIterator::operator* ( ) const [inline]

Dereference: access the current sub-object.

Note that this never returns a null pointer.

Definition at line 252 of file ObjectGraphIterator.h.

References invalid(), m_it, and PLASSERT.

    {
        PLASSERT( !invalid() );
        return m_it->first;
    }

Here is the call graph for this function:

ObjectGraphIterator PLearn::ObjectGraphIterator::operator++ ( int  ) [inline]

Post-increment: implemented in terms of pre-increment.

Note that this is expensive; don't use if not necessary.

Definition at line 273 of file ObjectGraphIterator.h.

    {
        ObjectGraphIterator old(*this);
        ++(*this);
        return old;
    }
const ObjectGraphIterator & PLearn::ObjectGraphIterator::operator++ ( )

Go to next object or "invalid" state if end of iteration.

Definition at line 224 of file ObjectGraphIterator.cc.

References invalid(), m_end, m_isa_tester, m_it, and PLASSERT.

{
    PLASSERT( !invalid() );
    for ( ++m_it ; m_it != m_end && m_isa_tester && !m_isa_tester(**this) ; ++m_it )
        continue;
    return *this;
}

Here is the call graph for this function:

bool PLearn::ObjectGraphIterator::operator== ( const ObjectGraphIterator rhs) const

Equality testing; two invalid iterators always compare equal.

Definition at line 215 of file ObjectGraphIterator.cc.

References invalid(), m_end, and m_it.

{
    return (invalid() && rhs.invalid()) ||
        (! invalid()                    &&
         m_it   == rhs.m_it             &&
         m_end  == rhs.m_end);
}

Here is the call graph for this function:


Member Data Documentation

If this option is true, traverse even non-traversable options.

This sometimes makes sense for "deep-initialization" purposes. You can bitwise-or this option to TraversalType when creating the ObjectGraphIterator.

Definition at line 209 of file ObjectGraphIterator.h.

Referenced by buildTraversalGraph().

ObjectList::iterator PLearn::ObjectGraphIterator::m_end [protected]

End of m_object_list.

Definition at line 293 of file ObjectGraphIterator.h.

Referenced by invalid(), ObjectGraphIterator(), operator++(), and operator==().

Predicate for sub-type filter.

Definition at line 294 of file ObjectGraphIterator.h.

Referenced by ObjectGraphIterator(), and operator++().

ObjectList::iterator PLearn::ObjectGraphIterator::m_it [protected]

Iterator within m_object_list.

Definition at line 292 of file ObjectGraphIterator.h.

Referenced by getCurrentOptionName(), invalid(), ObjectGraphIterator(), operator*(), operator++(), and operator==().

from buildTraversalGraph()

Definition at line 291 of file ObjectGraphIterator.h.

Referenced by buildTraversalGraph(), and ObjectGraphIterator().

For convenience, you can bitwise-or this value with normal traversal types to get the reversed ones.

Definition at line 201 of file ObjectGraphIterator.h.

Referenced by buildTraversalGraph().


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines