UT_CycleDetect< T > Class Template Reference

#include <UT_Algorithm.h>

Classes
class	AutoScope

Public Member Functions
	UT_CycleDetect ()
void	reset ()
bool	detect (const T &tail)
exint	length () const

Detailed Description

template<typename T>
class UT_CycleDetect< T >

A generic cycle detector that takes constant space and will detect cycles using at most O(N) extra calls to detect() for a cycle of length N (if it exists) using O(1) space.

NOTE: In general, this won't detect cycles immediately and so your loop must be able to support extra iterations.

You might have as many as 3 times the number of iterations as your total path length.

Example:

T walk; UT_CycleDetect<T> cycle; for (walk = first; walk && !cycle.detect(walk); walk = walk->next) { .... do stuff with walk .... }

Definition at line 55 of file UT_Algorithm.h.

Constructor & Destructor Documentation

template<typename T>

UT_CycleDetect< T >::UT_CycleDetect ( )

inline

Definition at line 120 of file UT_Algorithm.h.

Member Function Documentation

template<typename T>

bool UT_CycleDetect< T >::detect ( const T &  tail )

inline

Definition at line 131 of file UT_Algorithm.h.

template<typename T>

exint UT_CycleDetect< T >::length ( void  ) const

inline

Definition at line 155 of file UT_Algorithm.h.

template<typename T>

void UT_CycleDetect< T >::reset ( void  )

inline

Definition at line 125 of file UT_Algorithm.h.

---

The documentation for this class was generated from the following file:

• UT/UT_Algorithm.h