UT/UT_Algorithm.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Neil Girdhar
 *      Side Effects Software Inc
 *      477 Richmond Street West
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 *
 * NAME:        UT_Algorithm.h ( UT Library, C++)
 *
 * COMMENTS:
 *      this is supposed to be like STL's algorithm header -- put stuff in here
 *      that doesn't really belong in any other header.
 */

#ifndef __UT_Algorithm__
#define __UT_Algorithm__

#include <SYS/SYS_Types.h>

#define UT_SWAPPER_SIMPLE(T) \
        inline void UTswap(T &a, T &b) { T tmp = a; a = b; b = tmp; }
#define UT_SWAPPER_CLASS(T) \
        inline void UTswap(T &a, T &b) { a.swap(b); }
#define UT_SWAPPER_TEMPLATE(T) \
        template< typename TA > \
        inline void UTswap(T<TA> &a, T<TA> &b) { a.swap(b); }

template< typename T >
inline void
UTswap(T *&a, T *&b)
{
    T   *tmp = a;

    a = b;
    b = tmp;
}

UT_SWAPPER_SIMPLE(bool);
UT_SWAPPER_SIMPLE(unsigned char);
UT_SWAPPER_SIMPLE(char);
UT_SWAPPER_SIMPLE(uint16);
UT_SWAPPER_SIMPLE(int16);
UT_SWAPPER_SIMPLE(uint32);
UT_SWAPPER_SIMPLE(int32);
UT_SWAPPER_SIMPLE(uint64);
UT_SWAPPER_SIMPLE(int64);
UT_SWAPPER_SIMPLE(fpreal32);
UT_SWAPPER_SIMPLE(fpreal64);
#ifdef MBSD
    UT_SWAPPER_SIMPLE(size_t);
#endif

/// 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 ....
/// }
///
template <typename T>
class UT_CycleDetect
{
public:
    UT_CycleDetect()
    {
        reset();
    }

    void reset()
    {
        myCount = 2;        // must be a power of 2
        myCycleDetected = false;
    }

    bool detect(const T &tail)
    {
        if (myCycleDetected)
            return true;

        // Reset before detection so that for loop idiom works.
        // The if test is one iteration of the standard Brian Kernighan
        // bit count algorithm. We use this to check if myCount is a power
        // of 2 (ie. at most 1 bit set).
        if ((myCount & (myCount - 1)) == 0)
        {
            myHead = tail;
        }
        else if (myHead == tail)
        {
            myCycleDetected = true;
            return true;
        }

        myCount++;
        return false;
    }

private:
    T       myHead;
    int64   myCount;
    bool    myCycleDetected;
};

#endif

---