UT_CycleDetect< T > Class Template Reference

#include <UT_Algorithm.h>

List of all members.

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

---

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.

For a more efficient cycle detector, we could use Floyd's cycle detection algorithm but then it would need to be given 2 iterators.

Example:

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

Definition at line 82 of file UT_Algorithm.h.

---

Constructor & Destructor Documentation

template<typename T>

UT_CycleDetect< T >::UT_CycleDetect

(

)

[inline]

Definition at line 85 of file UT_Algorithm.h.

---

Member Function Documentation

template<typename T>

bool UT_CycleDetect< T >::detect

(

const T &

tail

)

[inline]

Definition at line 96 of file UT_Algorithm.h.

template<typename T>

void UT_CycleDetect< T >::reset

(

void

)

[inline]

Definition at line 90 of file UT_Algorithm.h.

---

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

• UT/UT_Algorithm.h