HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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: