All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_CycleDetect< T > Class Template Reference

#include <UT_Algorithm.h>


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.


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 ( )

Definition at line 120 of file UT_Algorithm.h.

Member Function Documentation

template<typename T>
bool UT_CycleDetect< T >::detect ( const T tail)

Definition at line 131 of file UT_Algorithm.h.

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

Definition at line 155 of file UT_Algorithm.h.

template<typename T>
void UT_CycleDetect< T >::reset ( void  )

Definition at line 125 of file UT_Algorithm.h.

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