#include <CMathDependencyNodeIterator.h>

Collaboration diagram for CMathDependencyNodeIterator:

Classes
class	CStackElement

Public Types
typedef CMathFlags< State >	Flag

enum	State { Start = 0x00, Before = 0x01, After = 0x02, Intermediate = 0x04, End = 0x08, Recursive = 0x10 }

enum	Type { Dependents, Prerequisites }

Public Member Functions
	CMathDependencyNodeIterator ()

	CMathDependencyNodeIterator (const CMathDependencyNodeIterator &src)

	CMathDependencyNodeIterator (CMathDependencyNode *pNode, const Type &type=Dependents)

Flag	getProcessingModes () const

size_t	level () const

bool	next ()

CMathDependencyNode *	operator* ()

CMathDependencyNode *	operator-> ()

const CMathDependencyNode *	parent ()

void	setProcessingModes (const Flag &processingModes)

const State &	skipChildren ()

const State &	state () const

	~CMathDependencyNodeIterator ()

Private Member Functions
void	increment ()

Private Attributes
State	mCurrentState

Flag	mProcessingModes

std::stack< CStackElement >	mStack

Type	mType

std::set< const CMathDependencyNode * >	mVisited

Detailed Description

This class allows to iterator over the nodes of a dependency graph in both directions (Dependents and Prerequisites) which is indicated by the type.

Definition at line 27 of file CMathDependencyNodeIterator.h.

Member Typedef Documentation

typedef CMathFlags< State > CMathDependencyNodeIterator::Flag

A flag indicating to which state the iterator should advance. These may be any combination of the enumeration value State. Please note the iterator will always return and End and Recursive

Definition at line 58 of file CMathDependencyNodeIterator.h.

Member Enumeration Documentation

enum CMathDependencyNodeIterator::State

The state of the iterator. Please note that the graph might be recursive which will cause the iterator to stop.

Enumerator
Start
Before
After
Intermediate
End
Recursive

Definition at line 43 of file CMathDependencyNodeIterator.h.

   {
     Start = 0x00,
     Before = 0x01,
     After = 0x02,
     Intermediate = 0x04,
     End = 0x08,
     Recursive = 0x10
   };

enum CMathDependencyNodeIterator::Type

Type defining whether we iterate over the dependents or prerequisites

Enumerator
Dependents
Prerequisites

Definition at line 33 of file CMathDependencyNodeIterator.h.

   {
     Dependents,
     Prerequisites
   };

Constructor & Destructor Documentation

CMathDependencyNodeIterator::CMathDependencyNodeIterator ( )

Default constructor

Definition at line 57 of file CMathDependencyNodeIterator.cpp.

                                                         :
   mStack(),
   mVisited(),
   mType(Dependents),
   mCurrentState(End),
   mProcessingModes(After | End | Recursive)
 {}

CMathDependencyNodeIterator::CMathDependencyNodeIterator ( const CMathDependencyNodeIterator & src )

Copy constructor

Parameters

const CMathDependencyNodeIterator & src

Definition at line 65 of file CMathDependencyNodeIterator.cpp.

                                                                                                :
   mStack(src.mStack),
   mVisited(src.mVisited),
   mType(src.mType),
   mCurrentState(src.mCurrentState),
   mProcessingModes(src.mProcessingModes)
 {}

CMathDependencyNodeIterator::CMathDependencyNodeIterator	(	CMathDependencyNode *	pNode,
		const Type &	type = `Dependents`
	)

Specific constructor

Parameters

CMathDependencyNode	* pNode
const	Type & type (default: Dependents)

Definition at line 73 of file CMathDependencyNodeIterator.cpp.

References mStack, mType, and mVisited.

                                                  :
   mStack(),
   mVisited(),
   mType(type),
   mCurrentState(Start),
   mProcessingModes(After | End | Recursive)
 {
   mStack.push(CStackElement(pNode, mType, NULL));
   mVisited.insert(pNode);
 }

CMathDependencyNodeIterator::~CMathDependencyNodeIterator ( )

Destructor

Definition at line 85 of file CMathDependencyNodeIterator.cpp.

86 {}

Member Function Documentation

CMathDependencyNodeIterator::Flag CMathDependencyNodeIterator::getProcessingModes ( ) const

Retrieve the valid states for which the method next() should return

Returns: Flag processingModes

Definition at line 223 of file CMathDependencyNodeIterator.cpp.

References End, mProcessingModes, and Recursive.

 {
   return (mProcessingModes & ~(End | Recursive));
 }

void CMathDependencyNodeIterator::increment ( )

private

This method advances the iterator to the next internal state. The tree is traversed depth first.

Please note that the iterator points to the same node multiple times, once before every child, and once after the last child to allow pre and post processing. This behavior is also true for childless nodes. To determine whether the iterator is in the pre, intermediate or post processing phase one may check the processing mode with: const State & state()

Definition at line 88 of file CMathDependencyNodeIterator.cpp.

References After, Before, End, Intermediate, mCurrentState, CMathDependencyNodeIterator::CStackElement::mEndChild, CMathDependencyNodeIterator::CStackElement::mItChild, CMathDependencyNodeIterator::CStackElement::mpNode, mStack, CMathDependencyNodeIterator::CStackElement::mType, mVisited, and Recursive.

Referenced by next().

 {
   // We must not further process any recursive
   if (mCurrentState == Recursive)
     {
       mStack.pop();
     }
 
   if (mStack.empty())
     {
       mCurrentState = End;
 
       return;
     }
 
   CStackElement & Current = mStack.top();
 
   if (mCurrentState != After)
     {
       if (Current.mItChild != Current.mEndChild)
         {
           CMathDependencyNode * pNode = *Current.mItChild;
 
           mStack.push(CStackElement(*Current.mItChild, Current.mType, Current.mpNode));
 
           // This will process any children since the iterator is context unaware.
           // It is therefore expected that we encounter recursive dependencies for
           // intensive/extensive value pairs.
           Current.mItChild++;
 
           if (mVisited.find(pNode) != mVisited.end())
             {
               // Indicate that this node is already in the stack and processing would lead to an
               // infinite recursion.
               mCurrentState = Recursive;
             }
           else
             {
               mVisited.insert(pNode);
               mCurrentState = Before;
             }
 
           return;
         }
 
       if (Current.mItChild == Current.mEndChild)
         {
           mCurrentState = After;
 
           return;
         }
     }
 
   mVisited.erase(Current.mpNode);
   mStack.pop();
 
   if (mStack.empty())
     {
       mCurrentState = End;
 
       return;
     }
 
   CStackElement & Parent = mStack.top();
 
   if (Parent.mItChild != Parent.mEndChild)
     {
       mCurrentState = Intermediate;
     }
   else
     {
       mCurrentState = After;
     }
 
   return;
 }

size_t CMathDependencyNodeIterator::level ( ) const

Retrieve the current nesting level of the iterator

Returns: size_t level

Definition at line 213 of file CMathDependencyNodeIterator.cpp.

References mStack.

 {
   return mStack.size();
 }

bool CMathDependencyNodeIterator::next ( )

This method advances the iterator to the next node and state combination for which the state is in the Flag of processing modes. A return value of true indicates that such a node has been found whereas false indicates the iteration has been completed or failed. To determine the current state of the iterator use: const State & state()

Returns: bool success

Definition at line 165 of file CMathDependencyNodeIterator.cpp.

References Before, End, increment(), mCurrentState, mProcessingModes, and Start.

Referenced by CMathDependencyNode::buildUpdateSequence(), CMathDependencyNode::updateDependentState(), and CMathDependencyNode::updatePrerequisiteState().

 {
   if (mCurrentState != Start)
     {
       increment();
     }
   else
     {
       mCurrentState = Before;
     }
 
   while (!(mProcessingModes & mCurrentState))
     {
       increment();
     }
 
   return mCurrentState & ~End;
 }

CMathDependencyNode * CMathDependencyNodeIterator::operator* ( )

This operator dereferences the iterator and returns a pointer the node of the graph

Returns: CMathDependencyNode * pNode

Definition at line 193 of file CMathDependencyNodeIterator.cpp.

References mStack.

 {
   return mStack.top().mpNode;
 }

CMathDependencyNode * CMathDependencyNodeIterator::operator-> ( )

This operator dereferences the iterator and returns a pointer the node of the graph

Returns: CMathDependencyNode * pNode

Definition at line 198 of file CMathDependencyNodeIterator.cpp.

References mStack.

 {
   return mStack.top().mpNode;
 }

const CMathDependencyNode * CMathDependencyNodeIterator::parent ( )

Retrieve the pointer to the parent node of the current node if known otherwise NULL

Returns: const CMathDependencyNode * pParent

Definition at line 203 of file CMathDependencyNodeIterator.cpp.

References mStack.

Referenced by CMathDependencyNode::updateDependentState(), and CMathDependencyNode::updatePrerequisiteState().

 {
   return mStack.top().mpParent;
 }

void CMathDependencyNodeIterator::setProcessingModes ( const Flag & processingModes )

Set the valid states for which the method next() should return

Parameters

const Flag & processingModes

Definition at line 218 of file CMathDependencyNodeIterator.cpp.

References End, mProcessingModes, and Recursive.

Referenced by CMathDependencyNode::buildUpdateSequence(), CMathDependencyNode::updateDependentState(), and CMathDependencyNode::updatePrerequisiteState().

 {
   mProcessingModes = (processingModes | End | Recursive);
 }

const CMathDependencyNodeIterator::State & CMathDependencyNodeIterator::skipChildren ( )

Calling this method causes the iterator to skip processing the children of the current node and advance to the State to next state allowed by the processing mode

Returns: const State & state

Definition at line 184 of file CMathDependencyNodeIterator.cpp.

References After, mCurrentState, CMathDependencyNodeIterator::CStackElement::mEndChild, CMathDependencyNodeIterator::CStackElement::mItChild, and mStack.

Referenced by CMathDependencyNode::buildUpdateSequence(), CMathDependencyNode::updateDependentState(), and CMathDependencyNode::updatePrerequisiteState().

 {
   CStackElement & Current = mStack.top();
   Current.mItChild = Current.mEndChild;
   mCurrentState = After;
 
   return mCurrentState;
 }

const CMathDependencyNodeIterator::State & CMathDependencyNodeIterator::state ( ) const

Retrieve the current state of the iterator

Returns: const State & state

Definition at line 208 of file CMathDependencyNodeIterator.cpp.

References mCurrentState.

Referenced by CMathDependencyNode::buildUpdateSequence(), CMathDependencyNode::updateDependentState(), and CMathDependencyNode::updatePrerequisiteState().

 {
   return mCurrentState;
 }

Member Data Documentation

State CMathDependencyNodeIterator::mCurrentState

private

The current state of the iterator

Definition at line 241 of file CMathDependencyNodeIterator.h.

Referenced by increment(), next(), skipChildren(), and state().

Flag CMathDependencyNodeIterator::mProcessingModes

private

The flag indicating to which state the iterator should advance. These may be any combination of the enumeration value State. Please note that this flag will always include return and End and Recursive

Definition at line 248 of file CMathDependencyNodeIterator.h.

Referenced by getProcessingModes(), next(), and setProcessingModes().

std::stack< CStackElement > CMathDependencyNodeIterator::mStack

private

A stack of context for each nesting level of the iterator

Definition at line 225 of file CMathDependencyNodeIterator.h.

Referenced by CMathDependencyNodeIterator(), increment(), level(), operator*(), operator->(), parent(), and skipChildren().