nuclear@1: /************************************************************************************
nuclear@1: 
nuclear@1: PublicHeader:   OVR.h
nuclear@1: Filename    :   OVR_Alg.h
nuclear@1: Content     :   Simple general purpose algorithms: Sort, Binary Search, etc.
nuclear@1: Created     :   September 19, 2012
nuclear@1: Notes       : 
nuclear@1: 
nuclear@1: Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
nuclear@1: 
nuclear@1: Use of this software is subject to the terms of the Oculus license
nuclear@1: agreement provided at the time of installation or download, or which
nuclear@1: otherwise accompanies this software in either electronic or hard copy form.
nuclear@1: 
nuclear@1: ************************************************************************************/
nuclear@1: 
nuclear@1: #ifndef OVR_Alg_h
nuclear@1: #define OVR_Alg_h
nuclear@1: 
nuclear@1: #include "OVR_Types.h"
nuclear@1: #include <string.h>
nuclear@1: 
nuclear@1: namespace OVR { namespace Alg {
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** Operator extensions
nuclear@1: 
nuclear@1: template <typename T> OVR_FORCE_INLINE void Swap(T &a, T &b) 
nuclear@1: {  T temp(a); a = b; b = temp; }
nuclear@1: 
nuclear@1: 
nuclear@1: // ***** min/max are not implemented in Visual Studio 6 standard STL
nuclear@1: 
nuclear@1: template <typename T> OVR_FORCE_INLINE const T Min(const T a, const T b)
nuclear@1: { return (a < b) ? a : b; }
nuclear@1: 
nuclear@1: template <typename T> OVR_FORCE_INLINE const T Max(const T a, const T b)
nuclear@1: { return (b < a) ? a : b; }
nuclear@1: 
nuclear@1: template <typename T> OVR_FORCE_INLINE const T Clamp(const T v, const T minVal, const T maxVal)
nuclear@1: { return Max<T>(minVal, Min<T>(v, maxVal)); }
nuclear@1: 
nuclear@1: template <typename T> OVR_FORCE_INLINE int     Chop(T f)
nuclear@1: { return (int)f; }
nuclear@1: 
nuclear@1: template <typename T> OVR_FORCE_INLINE T       Lerp(T a, T b, T f) 
nuclear@1: { return (b - a) * f + a; }
nuclear@1: 
nuclear@1: 
nuclear@1: // These functions stand to fix a stupid VC++ warning (with /Wp64 on):
nuclear@1: // "warning C4267: 'argument' : conversion from 'size_t' to 'const unsigned', possible loss of data"
nuclear@1: // Use these functions instead of gmin/gmax if the argument has size
nuclear@1: // of the pointer to avoid the warning. Though, functionally they are
nuclear@1: // absolutelly the same as regular gmin/gmax.
nuclear@1: template <typename T>   OVR_FORCE_INLINE const T PMin(const T a, const T b)
nuclear@1: {
nuclear@1:     OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt));
nuclear@1:     return (a < b) ? a : b;
nuclear@1: }
nuclear@1: template <typename T>   OVR_FORCE_INLINE const T PMax(const T a, const T b)
nuclear@1: {
nuclear@1:     OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt));
nuclear@1:     return (b < a) ? a : b;
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: template <typename T>   OVR_FORCE_INLINE const T Abs(const T v)
nuclear@1: { return (v>=0) ? v : -v; }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** OperatorLess
nuclear@1: //
nuclear@1: template<class T> struct OperatorLess
nuclear@1: {
nuclear@1:     static bool Compare(const T& a, const T& b)
nuclear@1:     {
nuclear@1:         return a < b;
nuclear@1:     }
nuclear@1: };
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** QuickSortSliced
nuclear@1: //
nuclear@1: // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
nuclear@1: // The range is specified with start, end, where "end" is exclusive!
nuclear@1: // The comparison predicate must be specified.
nuclear@1: template<class Array, class Less> 
nuclear@1: void QuickSortSliced(Array& arr, UPInt start, UPInt end, Less less)
nuclear@1: {
nuclear@1:     enum 
nuclear@1:     {
nuclear@1:         Threshold = 9
nuclear@1:     };
nuclear@1: 
nuclear@1:     if(end - start <  2) return;
nuclear@1: 
nuclear@1:     SPInt  stack[80];
nuclear@1:     SPInt* top   = stack; 
nuclear@1:     SPInt  base  = (SPInt)start;
nuclear@1:     SPInt  limit = (SPInt)end;
nuclear@1: 
nuclear@1:     for(;;)
nuclear@1:     {
nuclear@1:         SPInt len = limit - base;
nuclear@1:         SPInt i, j, pivot;
nuclear@1: 
nuclear@1:         if(len > Threshold)
nuclear@1:         {
nuclear@1:             // we use base + len/2 as the pivot
nuclear@1:             pivot = base + len / 2;
nuclear@1:             Swap(arr[base], arr[pivot]);
nuclear@1: 
nuclear@1:             i = base + 1;
nuclear@1:             j = limit - 1;
nuclear@1: 
nuclear@1:             // now ensure that *i <= *base <= *j 
nuclear@1:             if(less(arr[j],    arr[i])) Swap(arr[j],    arr[i]);
nuclear@1:             if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
nuclear@1:             if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
nuclear@1: 
nuclear@1:             for(;;)
nuclear@1:             {
nuclear@1:                 do i++; while( less(arr[i], arr[base]) );
nuclear@1:                 do j--; while( less(arr[base], arr[j]) );
nuclear@1: 
nuclear@1:                 if( i > j )
nuclear@1:                 {
nuclear@1:                     break;
nuclear@1:                 }
nuclear@1: 
nuclear@1:                 Swap(arr[i], arr[j]);
nuclear@1:             }
nuclear@1: 
nuclear@1:             Swap(arr[base], arr[j]);
nuclear@1: 
nuclear@1:             // now, push the largest sub-array
nuclear@1:             if(j - base > limit - i)
nuclear@1:             {
nuclear@1:                 top[0] = base;
nuclear@1:                 top[1] = j;
nuclear@1:                 base   = i;
nuclear@1:             }
nuclear@1:             else
nuclear@1:             {
nuclear@1:                 top[0] = i;
nuclear@1:                 top[1] = limit;
nuclear@1:                 limit  = j;
nuclear@1:             }
nuclear@1:             top += 2;
nuclear@1:         }
nuclear@1:         else
nuclear@1:         {
nuclear@1:             // the sub-array is small, perform insertion sort
nuclear@1:             j = base;
nuclear@1:             i = j + 1;
nuclear@1: 
nuclear@1:             for(; i < limit; j = i, i++)
nuclear@1:             {
nuclear@1:                 for(; less(arr[j + 1], arr[j]); j--)
nuclear@1:                 {
nuclear@1:                     Swap(arr[j + 1], arr[j]);
nuclear@1:                     if(j == base)
nuclear@1:                     {
nuclear@1:                         break;
nuclear@1:                     }
nuclear@1:                 }
nuclear@1:             }
nuclear@1:             if(top > stack)
nuclear@1:             {
nuclear@1:                 top  -= 2;
nuclear@1:                 base  = top[0];
nuclear@1:                 limit = top[1];
nuclear@1:             }
nuclear@1:             else
nuclear@1:             {
nuclear@1:                 break;
nuclear@1:             }
nuclear@1:         }
nuclear@1:     }
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** QuickSortSliced
nuclear@1: //
nuclear@1: // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
nuclear@1: // The range is specified with start, end, where "end" is exclusive!
nuclear@1: // The data type must have a defined "<" operator.
nuclear@1: template<class Array> 
nuclear@1: void QuickSortSliced(Array& arr, UPInt start, UPInt end)
nuclear@1: {
nuclear@1:     typedef typename Array::ValueType ValueType;
nuclear@1:     QuickSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: // Same as corresponding G_QuickSortSliced but with checking array limits to avoid
nuclear@1: // crash in the case of wrong comparator functor.
nuclear@1: template<class Array, class Less> 
nuclear@1: bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end, Less less)
nuclear@1: {
nuclear@1:     enum 
nuclear@1:     {
nuclear@1:         Threshold = 9
nuclear@1:     };
nuclear@1: 
nuclear@1:     if(end - start <  2) return true;
nuclear@1: 
nuclear@1:     SPInt  stack[80];
nuclear@1:     SPInt* top   = stack; 
nuclear@1:     SPInt  base  = (SPInt)start;
nuclear@1:     SPInt  limit = (SPInt)end;
nuclear@1: 
nuclear@1:     for(;;)
nuclear@1:     {
nuclear@1:         SPInt len = limit - base;
nuclear@1:         SPInt i, j, pivot;
nuclear@1: 
nuclear@1:         if(len > Threshold)
nuclear@1:         {
nuclear@1:             // we use base + len/2 as the pivot
nuclear@1:             pivot = base + len / 2;
nuclear@1:             Swap(arr[base], arr[pivot]);
nuclear@1: 
nuclear@1:             i = base + 1;
nuclear@1:             j = limit - 1;
nuclear@1: 
nuclear@1:             // now ensure that *i <= *base <= *j 
nuclear@1:             if(less(arr[j],    arr[i])) Swap(arr[j],    arr[i]);
nuclear@1:             if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
nuclear@1:             if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
nuclear@1: 
nuclear@1:             for(;;)
nuclear@1:             {
nuclear@1:                 do 
nuclear@1:                 {   
nuclear@1:                     i++; 
nuclear@1:                     if (i >= limit)
nuclear@1:                         return false;
nuclear@1:                 } while( less(arr[i], arr[base]) );
nuclear@1:                 do 
nuclear@1:                 {
nuclear@1:                     j--; 
nuclear@1:                     if (j < 0)
nuclear@1:                         return false;
nuclear@1:                 } while( less(arr[base], arr[j]) );
nuclear@1: 
nuclear@1:                 if( i > j )
nuclear@1:                 {
nuclear@1:                     break;
nuclear@1:                 }
nuclear@1: 
nuclear@1:                 Swap(arr[i], arr[j]);
nuclear@1:             }
nuclear@1: 
nuclear@1:             Swap(arr[base], arr[j]);
nuclear@1: 
nuclear@1:             // now, push the largest sub-array
nuclear@1:             if(j - base > limit - i)
nuclear@1:             {
nuclear@1:                 top[0] = base;
nuclear@1:                 top[1] = j;
nuclear@1:                 base   = i;
nuclear@1:             }
nuclear@1:             else
nuclear@1:             {
nuclear@1:                 top[0] = i;
nuclear@1:                 top[1] = limit;
nuclear@1:                 limit  = j;
nuclear@1:             }
nuclear@1:             top += 2;
nuclear@1:         }
nuclear@1:         else
nuclear@1:         {
nuclear@1:             // the sub-array is small, perform insertion sort
nuclear@1:             j = base;
nuclear@1:             i = j + 1;
nuclear@1: 
nuclear@1:             for(; i < limit; j = i, i++)
nuclear@1:             {
nuclear@1:                 for(; less(arr[j + 1], arr[j]); j--)
nuclear@1:                 {
nuclear@1:                     Swap(arr[j + 1], arr[j]);
nuclear@1:                     if(j == base)
nuclear@1:                     {
nuclear@1:                         break;
nuclear@1:                     }
nuclear@1:                 }
nuclear@1:             }
nuclear@1:             if(top > stack)
nuclear@1:             {
nuclear@1:                 top  -= 2;
nuclear@1:                 base  = top[0];
nuclear@1:                 limit = top[1];
nuclear@1:             }
nuclear@1:             else
nuclear@1:             {
nuclear@1:                 break;
nuclear@1:             }
nuclear@1:         }
nuclear@1:     }
nuclear@1:     return true;
nuclear@1: }
nuclear@1: 
nuclear@1: template<class Array> 
nuclear@1: bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end)
nuclear@1: {
nuclear@1:     typedef typename Array::ValueType ValueType;
nuclear@1:     return QuickSortSlicedSafe(arr, start, end, OperatorLess<ValueType>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** QuickSort
nuclear@1: //
nuclear@1: // Sort an array Array, ArrayPaged, ArrayUnsafe.
nuclear@1: // The array must have GetSize() function.
nuclear@1: // The comparison predicate must be specified.
nuclear@1: template<class Array, class Less> 
nuclear@1: void QuickSort(Array& arr, Less less)
nuclear@1: {
nuclear@1:     QuickSortSliced(arr, 0, arr.GetSize(), less);
nuclear@1: }
nuclear@1: 
nuclear@1: // checks for boundaries
nuclear@1: template<class Array, class Less> 
nuclear@1: bool QuickSortSafe(Array& arr, Less less)
nuclear@1: {
nuclear@1:     return QuickSortSlicedSafe(arr, 0, arr.GetSize(), less);
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** QuickSort
nuclear@1: //
nuclear@1: // Sort an array Array, ArrayPaged, ArrayUnsafe.
nuclear@1: // The array must have GetSize() function.
nuclear@1: // The data type must have a defined "<" operator.
nuclear@1: template<class Array> 
nuclear@1: void QuickSort(Array& arr)
nuclear@1: {
nuclear@1:     typedef typename Array::ValueType ValueType;
nuclear@1:     QuickSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: template<class Array> 
nuclear@1: bool QuickSortSafe(Array& arr)
nuclear@1: {
nuclear@1:     typedef typename Array::ValueType ValueType;
nuclear@1:     return QuickSortSlicedSafe(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** InsertionSortSliced
nuclear@1: //
nuclear@1: // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
nuclear@1: // The range is specified with start, end, where "end" is exclusive!
nuclear@1: // The comparison predicate must be specified.
nuclear@1: // Unlike Quick Sort, the Insertion Sort works much slower in average, 
nuclear@1: // but may be much faster on almost sorted arrays. Besides, it guarantees
nuclear@1: // that the elements will not be swapped if not necessary. For example, 
nuclear@1: // an array with all equal elements will remain "untouched", while 
nuclear@1: // Quick Sort will considerably shuffle the elements in this case.
nuclear@1: template<class Array, class Less> 
nuclear@1: void InsertionSortSliced(Array& arr, UPInt start, UPInt end, Less less)
nuclear@1: {
nuclear@1:     UPInt j = start;
nuclear@1:     UPInt i = j + 1;
nuclear@1:     UPInt limit = end;
nuclear@1: 
nuclear@1:     for(; i < limit; j = i, i++)
nuclear@1:     {
nuclear@1:         for(; less(arr[j + 1], arr[j]); j--)
nuclear@1:         {
nuclear@1:             Swap(arr[j + 1], arr[j]);
nuclear@1:             if(j <= start)
nuclear@1:             {
nuclear@1:                 break;
nuclear@1:             }
nuclear@1:         }
nuclear@1:     }
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** InsertionSortSliced
nuclear@1: //
nuclear@1: // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
nuclear@1: // The range is specified with start, end, where "end" is exclusive!
nuclear@1: // The data type must have a defined "<" operator.
nuclear@1: template<class Array> 
nuclear@1: void InsertionSortSliced(Array& arr, UPInt start, UPInt end)
nuclear@1: {
nuclear@1:     typedef typename Array::ValueType ValueType;
nuclear@1:     InsertionSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** InsertionSort
nuclear@1: //
nuclear@1: // Sort an array Array, ArrayPaged, ArrayUnsafe.
nuclear@1: // The array must have GetSize() function.
nuclear@1: // The comparison predicate must be specified.
nuclear@1: 
nuclear@1: template<class Array, class Less> 
nuclear@1: void InsertionSort(Array& arr, Less less)
nuclear@1: {
nuclear@1:     InsertionSortSliced(arr, 0, arr.GetSize(), less);
nuclear@1: }
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** InsertionSort
nuclear@1: //
nuclear@1: // Sort an array Array, ArrayPaged, ArrayUnsafe.
nuclear@1: // The array must have GetSize() function.
nuclear@1: // The data type must have a defined "<" operator.
nuclear@1: template<class Array> 
nuclear@1: void InsertionSort(Array& arr)
nuclear@1: {
nuclear@1:     typedef typename Array::ValueType ValueType;
nuclear@1:     InsertionSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** LowerBoundSliced
nuclear@1: //
nuclear@1: template<class Array, class Value, class Less>
nuclear@1: UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less)
nuclear@1: {
nuclear@1:     SPInt first = (SPInt)start;
nuclear@1:     SPInt len   = (SPInt)(end - start);
nuclear@1:     SPInt half;
nuclear@1:     SPInt middle;
nuclear@1:     
nuclear@1:     while(len > 0) 
nuclear@1:     {
nuclear@1:         half = len >> 1;
nuclear@1:         middle = first + half;
nuclear@1:         if(less(arr[middle], val)) 
nuclear@1:         {
nuclear@1:             first = middle + 1;
nuclear@1:             len   = len - half - 1;
nuclear@1:         }
nuclear@1:         else
nuclear@1:         {
nuclear@1:             len = half;
nuclear@1:         }
nuclear@1:     }
nuclear@1:     return (UPInt)first;
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** LowerBoundSliced
nuclear@1: //
nuclear@1: template<class Array, class Value>
nuclear@1: UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val)
nuclear@1: {
nuclear@1:     return LowerBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** LowerBoundSized
nuclear@1: //
nuclear@1: template<class Array, class Value>
nuclear@1: UPInt LowerBoundSized(const Array& arr, UPInt size, const Value& val)
nuclear@1: {
nuclear@1:     return LowerBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** LowerBound
nuclear@1: //
nuclear@1: template<class Array, class Value, class Less>
nuclear@1: UPInt LowerBound(const Array& arr, const Value& val, Less less)
nuclear@1: {
nuclear@1:     return LowerBoundSliced(arr, 0, arr.GetSize(), val, less);
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** LowerBound
nuclear@1: //
nuclear@1: template<class Array, class Value>
nuclear@1: UPInt LowerBound(const Array& arr, const Value& val)
nuclear@1: {
nuclear@1:     return LowerBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** UpperBoundSliced
nuclear@1: //
nuclear@1: template<class Array, class Value, class Less>
nuclear@1: UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less)
nuclear@1: {
nuclear@1:     SPInt first = (SPInt)start;
nuclear@1:     SPInt len   = (SPInt)(end - start);
nuclear@1:     SPInt half;
nuclear@1:     SPInt middle;
nuclear@1:     
nuclear@1:     while(len > 0) 
nuclear@1:     {
nuclear@1:         half = len >> 1;
nuclear@1:         middle = first + half;
nuclear@1:         if(less(val, arr[middle]))
nuclear@1:         {
nuclear@1:             len = half;
nuclear@1:         }
nuclear@1:         else 
nuclear@1:         {
nuclear@1:             first = middle + 1;
nuclear@1:             len   = len - half - 1;
nuclear@1:         }
nuclear@1:     }
nuclear@1:     return (UPInt)first;
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** UpperBoundSliced
nuclear@1: //
nuclear@1: template<class Array, class Value>
nuclear@1: UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val)
nuclear@1: {
nuclear@1:     return UpperBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** UpperBoundSized
nuclear@1: //
nuclear@1: template<class Array, class Value>
nuclear@1: UPInt UpperBoundSized(const Array& arr, UPInt size, const Value& val)
nuclear@1: {
nuclear@1:     return UpperBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** UpperBound
nuclear@1: //
nuclear@1: template<class Array, class Value, class Less>
nuclear@1: UPInt UpperBound(const Array& arr, const Value& val, Less less)
nuclear@1: {
nuclear@1:     return UpperBoundSliced(arr, 0, arr.GetSize(), val, less);
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** UpperBound
nuclear@1: //
nuclear@1: template<class Array, class Value>
nuclear@1: UPInt UpperBound(const Array& arr, const Value& val)
nuclear@1: {
nuclear@1:     return UpperBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** ReverseArray
nuclear@1: //
nuclear@1: template<class Array> void ReverseArray(Array& arr)
nuclear@1: {
nuclear@1:     SPInt from = 0;
nuclear@1:     SPInt to   = arr.GetSize() - 1;
nuclear@1:     while(from < to)
nuclear@1:     {
nuclear@1:         Swap(arr[from], arr[to]);
nuclear@1:         ++from;
nuclear@1:         --to;
nuclear@1:     }
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: // ***** AppendArray
nuclear@1: //
nuclear@1: template<class CDst, class CSrc> 
nuclear@1: void AppendArray(CDst& dst, const CSrc& src)
nuclear@1: {
nuclear@1:     UPInt i;
nuclear@1:     for(i = 0; i < src.GetSize(); i++) 
nuclear@1:         dst.PushBack(src[i]);
nuclear@1: }
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** ArrayAdaptor
nuclear@1: //
nuclear@1: // A simple adapter that provides the GetSize() method and overloads 
nuclear@1: // operator []. Used to wrap plain arrays in QuickSort and such.
nuclear@1: template<class T> class ArrayAdaptor
nuclear@1: {
nuclear@1: public:
nuclear@1:     typedef T ValueType;
nuclear@1:     ArrayAdaptor() : Data(0), Size(0) {}
nuclear@1:     ArrayAdaptor(T* ptr, UPInt size) : Data(ptr), Size(size) {}
nuclear@1:     UPInt GetSize() const { return Size; }
nuclear@1:     const T& operator [] (UPInt i) const { return Data[i]; }
nuclear@1:           T& operator [] (UPInt i)       { return Data[i]; }
nuclear@1: private:
nuclear@1:     T*      Data;
nuclear@1:     UPInt   Size;
nuclear@1: };
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ***** GConstArrayAdaptor
nuclear@1: //
nuclear@1: // A simple const adapter that provides the GetSize() method and overloads 
nuclear@1: // operator []. Used to wrap plain arrays in LowerBound and such.
nuclear@1: template<class T> class ConstArrayAdaptor
nuclear@1: {
nuclear@1: public:
nuclear@1:     typedef T ValueType;
nuclear@1:     ConstArrayAdaptor() : Data(0), Size(0) {}
nuclear@1:     ConstArrayAdaptor(const T* ptr, UPInt size) : Data(ptr), Size(size) {}
nuclear@1:     UPInt GetSize() const { return Size; }
nuclear@1:     const T& operator [] (UPInt i) const { return Data[i]; }
nuclear@1: private:
nuclear@1:     const T* Data;
nuclear@1:     UPInt    Size;
nuclear@1: };
nuclear@1: 
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: extern const UByte UpperBitTable[256];
nuclear@1: extern const UByte LowerBitTable[256];
nuclear@1: 
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: inline UByte UpperBit(UPInt val)
nuclear@1: {
nuclear@1: #ifndef OVR_64BIT_POINTERS
nuclear@1: 
nuclear@1:     if (val & 0xFFFF0000)
nuclear@1:     {
nuclear@1:         return (val & 0xFF000000) ? 
nuclear@1:             UpperBitTable[(val >> 24)       ] + 24: 
nuclear@1:             UpperBitTable[(val >> 16) & 0xFF] + 16;
nuclear@1:     }
nuclear@1:     return (val & 0xFF00) ?
nuclear@1:         UpperBitTable[(val >> 8) & 0xFF] + 8:
nuclear@1:         UpperBitTable[(val     ) & 0xFF];
nuclear@1: 
nuclear@1: #else
nuclear@1: 
nuclear@1:     if (val & 0xFFFFFFFF00000000)
nuclear@1:     {
nuclear@1:         if (val & 0xFFFF000000000000)
nuclear@1:         {
nuclear@1:             return (val & 0xFF00000000000000) ?
nuclear@1:                 UpperBitTable[(val >> 56)       ] + 56: 
nuclear@1:                 UpperBitTable[(val >> 48) & 0xFF] + 48;
nuclear@1:         }
nuclear@1:         return (val & 0xFF0000000000) ?
nuclear@1:             UpperBitTable[(val >> 40) & 0xFF] + 40:
nuclear@1:             UpperBitTable[(val >> 32) & 0xFF] + 32;
nuclear@1:     }
nuclear@1:     else
nuclear@1:     {
nuclear@1:         if (val & 0xFFFF0000)
nuclear@1:         {
nuclear@1:             return (val & 0xFF000000) ? 
nuclear@1:                 UpperBitTable[(val >> 24)       ] + 24: 
nuclear@1:                 UpperBitTable[(val >> 16) & 0xFF] + 16;
nuclear@1:         }
nuclear@1:         return (val & 0xFF00) ?
nuclear@1:             UpperBitTable[(val >> 8) & 0xFF] + 8:
nuclear@1:             UpperBitTable[(val     ) & 0xFF];
nuclear@1:     }
nuclear@1: 
nuclear@1: #endif
nuclear@1: }
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: inline UByte LowerBit(UPInt val)
nuclear@1: {
nuclear@1: #ifndef OVR_64BIT_POINTERS
nuclear@1: 
nuclear@1:     if (val & 0xFFFF)
nuclear@1:     {
nuclear@1:         return (val & 0xFF) ?
nuclear@1:             LowerBitTable[ val & 0xFF]:
nuclear@1:             LowerBitTable[(val >> 8) & 0xFF] + 8;
nuclear@1:     }
nuclear@1:     return (val & 0xFF0000) ?
nuclear@1:             LowerBitTable[(val >> 16) & 0xFF] + 16:
nuclear@1:             LowerBitTable[(val >> 24) & 0xFF] + 24;
nuclear@1: 
nuclear@1: #else
nuclear@1: 
nuclear@1:     if (val & 0xFFFFFFFF)
nuclear@1:     {
nuclear@1:         if (val & 0xFFFF)
nuclear@1:         {
nuclear@1:             return (val & 0xFF) ?
nuclear@1:                 LowerBitTable[ val & 0xFF]:
nuclear@1:                 LowerBitTable[(val >> 8) & 0xFF] + 8;
nuclear@1:         }
nuclear@1:         return (val & 0xFF0000) ?
nuclear@1:                 LowerBitTable[(val >> 16) & 0xFF] + 16:
nuclear@1:                 LowerBitTable[(val >> 24) & 0xFF] + 24;
nuclear@1:     }
nuclear@1:     else
nuclear@1:     {
nuclear@1:         if (val & 0xFFFF00000000)
nuclear@1:         {
nuclear@1:              return (val & 0xFF00000000) ?
nuclear@1:                 LowerBitTable[(val >> 32) & 0xFF] + 32:
nuclear@1:                 LowerBitTable[(val >> 40) & 0xFF] + 40;
nuclear@1:         }
nuclear@1:         return (val & 0xFF000000000000) ?
nuclear@1:             LowerBitTable[(val >> 48) & 0xFF] + 48:
nuclear@1:             LowerBitTable[(val >> 56) & 0xFF] + 56;
nuclear@1:     }
nuclear@1: 
nuclear@1: #endif
nuclear@1: }
nuclear@1: 
nuclear@1: 
nuclear@1: 
nuclear@1: // ******* Special (optimized) memory routines
nuclear@1: // Note: null (bad) pointer is not tested
nuclear@1: class MemUtil
nuclear@1: {
nuclear@1: public:
nuclear@1:                                     
nuclear@1:     // Memory compare
nuclear@1:     static int      Cmp  (const void* p1, const void* p2, UPInt byteCount)      { return memcmp(p1, p2, byteCount); }
nuclear@1:     static int      Cmp16(const void* p1, const void* p2, UPInt int16Count);
nuclear@1:     static int      Cmp32(const void* p1, const void* p2, UPInt int32Count);
nuclear@1:     static int      Cmp64(const void* p1, const void* p2, UPInt int64Count); 
nuclear@1: };
nuclear@1: 
nuclear@1: // ** Inline Implementation
nuclear@1: 
nuclear@1: inline int MemUtil::Cmp16(const void* p1, const void* p2, UPInt int16Count)
nuclear@1: {
nuclear@1:     SInt16*  pa  = (SInt16*)p1; 
nuclear@1:     SInt16*  pb  = (SInt16*)p2;
nuclear@1:     unsigned ic  = 0;
nuclear@1:     if (int16Count == 0)
nuclear@1:         return 0;
nuclear@1:     while (pa[ic] == pb[ic])
nuclear@1:         if (++ic==int16Count)
nuclear@1:             return 0;
nuclear@1:     return pa[ic] > pb[ic] ? 1 : -1;
nuclear@1: }
nuclear@1: inline int MemUtil::Cmp32(const void* p1, const void* p2, UPInt int32Count)
nuclear@1: {
nuclear@1:     SInt32*  pa  = (SInt32*)p1;
nuclear@1:     SInt32*  pb  = (SInt32*)p2;
nuclear@1:     unsigned ic  = 0;
nuclear@1:     if (int32Count == 0)
nuclear@1:         return 0;
nuclear@1:     while (pa[ic] == pb[ic])
nuclear@1:         if (++ic==int32Count)
nuclear@1:             return 0;
nuclear@1:     return pa[ic] > pb[ic] ? 1 : -1;
nuclear@1: }
nuclear@1: inline int MemUtil::Cmp64(const void* p1, const void* p2, UPInt int64Count)
nuclear@1: {
nuclear@1:     SInt64*  pa  = (SInt64*)p1;
nuclear@1:     SInt64*  pb  = (SInt64*)p2;
nuclear@1:     unsigned ic  = 0;
nuclear@1:     if (int64Count == 0)
nuclear@1:         return 0;
nuclear@1:     while (pa[ic] == pb[ic])
nuclear@1:         if (++ic==int64Count)
nuclear@1:             return 0;
nuclear@1:     return pa[ic] > pb[ic] ? 1 : -1;
nuclear@1: }
nuclear@1: 
nuclear@1: // ** End Inline Implementation
nuclear@1: 
nuclear@1: 
nuclear@1: //-----------------------------------------------------------------------------------
nuclear@1: // ******* Byte Order Conversions
nuclear@1: namespace ByteUtil {
nuclear@1: 
nuclear@1:     // *** Swap Byte Order
nuclear@1: 
nuclear@1:     // Swap the byte order of a byte array
nuclear@1:     inline void     SwapOrder(void* pv, int size)
nuclear@1:     {
nuclear@1:         UByte*  pb = (UByte*)pv;
nuclear@1:         UByte   temp;
nuclear@1:         for (int i = 0; i < size>>1; i++)
nuclear@1:         { 
nuclear@1:             temp            = pb[size-1-i];
nuclear@1:             pb[size-1-i]    = pb[i];
nuclear@1:             pb[i]           = temp; 
nuclear@1:         }
nuclear@1:     }
nuclear@1: 
nuclear@1:     // Swap the byte order of primitive types
nuclear@1:     inline UByte    SwapOrder(UByte v)      { return v; }
nuclear@1:     inline SByte    SwapOrder(SByte v)      { return v; }
nuclear@1:     inline UInt16   SwapOrder(UInt16 v)     { return UInt16(v>>8)|UInt16(v<<8); }
nuclear@1:     inline SInt16   SwapOrder(SInt16 v)     { return SInt16((UInt16(v)>>8)|(v<<8)); }
nuclear@1:     inline UInt32   SwapOrder(UInt32 v)     { return (v>>24)|((v&0x00FF0000)>>8)|((v&0x0000FF00)<<8)|(v<<24); }
nuclear@1:     inline SInt32   SwapOrder(SInt32 p)     { return (SInt32)SwapOrder(UInt32(p)); }
nuclear@1:     inline UInt64   SwapOrder(UInt64 v)
nuclear@1:     { 
nuclear@1:         return   (v>>56) |
nuclear@1:                  ((v&UInt64(0x00FF000000000000))>>40) |
nuclear@1:                  ((v&UInt64(0x0000FF0000000000))>>24) |
nuclear@1:                  ((v&UInt64(0x000000FF00000000))>>8)  |
nuclear@1:                  ((v&UInt64(0x00000000FF000000))<<8)  |
nuclear@1:                  ((v&UInt64(0x0000000000FF0000))<<24) |
nuclear@1:                  ((v&UInt64(0x000000000000FF00))<<40) |
nuclear@1:                  (v<<56); 
nuclear@1:     }
nuclear@1:     inline SInt64   SwapOrder(SInt64 v)     { return (SInt64)SwapOrder(UInt64(v)); }
nuclear@1:     inline float    SwapOrder(float p)      
nuclear@1:     { 
nuclear@1:         union {
nuclear@1:             float p;
nuclear@1:             UInt32 v;
nuclear@1:         } u;
nuclear@1:         u.p = p;
nuclear@1:         u.v = SwapOrder(u.v);
nuclear@1:         return u.p;
nuclear@1:     }
nuclear@1: 
nuclear@1:     inline double   SwapOrder(double p)
nuclear@1:     { 
nuclear@1:         union {
nuclear@1:             double p;
nuclear@1:             UInt64 v;
nuclear@1:         } u;
nuclear@1:         u.p = p;
nuclear@1:         u.v = SwapOrder(u.v);
nuclear@1:         return u.p;
nuclear@1:     }
nuclear@1:     
nuclear@1:     // *** Byte-order conversion
nuclear@1: 
nuclear@1: #if (OVR_BYTE_ORDER == OVR_LITTLE_ENDIAN)
nuclear@1:     // Little Endian to System (LE)
nuclear@1:     inline UByte    LEToSystem(UByte  v)    { return v; }
nuclear@1:     inline SByte    LEToSystem(SByte  v)    { return v; }
nuclear@1:     inline UInt16   LEToSystem(UInt16 v)    { return v; }
nuclear@1:     inline SInt16   LEToSystem(SInt16 v)    { return v; }
nuclear@1:     inline UInt32   LEToSystem(UInt32 v)    { return v; }
nuclear@1:     inline SInt32   LEToSystem(SInt32 v)    { return v; }
nuclear@1:     inline UInt64   LEToSystem(UInt64 v)    { return v; }
nuclear@1:     inline SInt64   LEToSystem(SInt64 v)    { return v; }
nuclear@1:     inline float    LEToSystem(float  v)    { return v; }
nuclear@1:     inline double   LEToSystem(double v)    { return v; }
nuclear@1: 
nuclear@1:     // Big Endian to System (LE)
nuclear@1:     inline UByte    BEToSystem(UByte  v)    { return SwapOrder(v); }
nuclear@1:     inline SByte    BEToSystem(SByte  v)    { return SwapOrder(v); }
nuclear@1:     inline UInt16   BEToSystem(UInt16 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt16   BEToSystem(SInt16 v)    { return SwapOrder(v); }
nuclear@1:     inline UInt32   BEToSystem(UInt32 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt32   BEToSystem(SInt32 v)    { return SwapOrder(v); }
nuclear@1:     inline UInt64   BEToSystem(UInt64 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt64   BEToSystem(SInt64 v)    { return SwapOrder(v); }
nuclear@1:     inline float    BEToSystem(float  v)    { return SwapOrder(v); }
nuclear@1:     inline double   BEToSystem(double v)    { return SwapOrder(v); }
nuclear@1: 
nuclear@1:     // System (LE) to Little Endian
nuclear@1:     inline UByte    SystemToLE(UByte  v)    { return v; }
nuclear@1:     inline SByte    SystemToLE(SByte  v)    { return v; }
nuclear@1:     inline UInt16   SystemToLE(UInt16 v)    { return v; }
nuclear@1:     inline SInt16   SystemToLE(SInt16 v)    { return v; }
nuclear@1:     inline UInt32   SystemToLE(UInt32 v)    { return v; }
nuclear@1:     inline SInt32   SystemToLE(SInt32 v)    { return v; }
nuclear@1:     inline UInt64   SystemToLE(UInt64 v)    { return v; }
nuclear@1:     inline SInt64   SystemToLE(SInt64 v)    { return v; }
nuclear@1:     inline float    SystemToLE(float  v)    { return v; }
nuclear@1:     inline double   SystemToLE(double v)    { return v; }   
nuclear@1: 
nuclear@1:     // System (LE) to Big Endian
nuclear@1:     inline UByte    SystemToBE(UByte  v)    { return SwapOrder(v); }
nuclear@1:     inline SByte    SystemToBE(SByte  v)    { return SwapOrder(v); }
nuclear@1:     inline UInt16   SystemToBE(UInt16 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt16   SystemToBE(SInt16 v)    { return SwapOrder(v); }
nuclear@1:     inline UInt32   SystemToBE(UInt32 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt32   SystemToBE(SInt32 v)    { return SwapOrder(v); }
nuclear@1:     inline UInt64   SystemToBE(UInt64 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt64   SystemToBE(SInt64 v)    { return SwapOrder(v); }
nuclear@1:     inline float    SystemToBE(float  v)    { return SwapOrder(v); }
nuclear@1:     inline double   SystemToBE(double v)    { return SwapOrder(v); }
nuclear@1: 
nuclear@1: #elif (OVR_BYTE_ORDER == OVR_BIG_ENDIAN)
nuclear@1:     // Little Endian to System (BE)
nuclear@1:     inline UByte    LEToSystem(UByte  v)    { return SwapOrder(v); }
nuclear@1:     inline SByte    LEToSystem(SByte  v)    { return SwapOrder(v); }
nuclear@1:     inline UInt16   LEToSystem(UInt16 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt16   LEToSystem(SInt16 v)    { return SwapOrder(v); }
nuclear@1:     inline UInt32   LEToSystem(UInt32 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt32   LEToSystem(SInt32 v)    { return SwapOrder(v); }
nuclear@1:     inline UInt64   LEToSystem(UInt64 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt64   LEToSystem(SInt64 v)    { return SwapOrder(v); }
nuclear@1:     inline float    LEToSystem(float  v)    { return SwapOrder(v); }
nuclear@1:     inline double   LEToSystem(double v)    { return SwapOrder(v); }
nuclear@1: 
nuclear@1:     // Big Endian to System (BE)
nuclear@1:     inline UByte    BEToSystem(UByte  v)    { return v; }
nuclear@1:     inline SByte    BEToSystem(SByte  v)    { return v; }
nuclear@1:     inline UInt16   BEToSystem(UInt16 v)    { return v; }
nuclear@1:     inline SInt16   BEToSystem(SInt16 v)    { return v; }
nuclear@1:     inline UInt32   BEToSystem(UInt32 v)    { return v; }
nuclear@1:     inline SInt32   BEToSystem(SInt32 v)    { return v; }
nuclear@1:     inline UInt64   BEToSystem(UInt64 v)    { return v; }
nuclear@1:     inline SInt64   BEToSystem(SInt64 v)    { return v; }
nuclear@1:     inline float    BEToSystem(float  v)    { return v; }
nuclear@1:     inline double   BEToSystem(double v)    { return v; }
nuclear@1: 
nuclear@1:     // System (BE) to Little Endian
nuclear@1:     inline UByte    SystemToLE(UByte  v)    { return SwapOrder(v); }
nuclear@1:     inline SByte    SystemToLE(SByte  v)    { return SwapOrder(v); }
nuclear@1:     inline UInt16   SystemToLE(UInt16 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt16   SystemToLE(SInt16 v)    { return SwapOrder(v); }
nuclear@1:     inline UInt32   SystemToLE(UInt32 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt32   SystemToLE(SInt32 v)    { return SwapOrder(v); }
nuclear@1:     inline UInt64   SystemToLE(UInt64 v)    { return SwapOrder(v); }
nuclear@1:     inline SInt64   SystemToLE(SInt64 v)    { return SwapOrder(v); }
nuclear@1:     inline float    SystemToLE(float  v)    { return SwapOrder(v); }
nuclear@1:     inline double   SystemToLE(double v)    { return SwapOrder(v); }
nuclear@1: 
nuclear@1:     // System (BE) to Big Endian
nuclear@1:     inline UByte    SystemToBE(UByte  v)    { return v; }
nuclear@1:     inline SByte    SystemToBE(SByte  v)    { return v; }
nuclear@1:     inline UInt16   SystemToBE(UInt16 v)    { return v; }
nuclear@1:     inline SInt16   SystemToBE(SInt16 v)    { return v; }
nuclear@1:     inline UInt32   SystemToBE(UInt32 v)    { return v; }
nuclear@1:     inline SInt32   SystemToBE(SInt32 v)    { return v; }
nuclear@1:     inline UInt64   SystemToBE(UInt64 v)    { return v; }
nuclear@1:     inline SInt64   SystemToBE(SInt64 v)    { return v; }
nuclear@1:     inline float    SystemToBE(float  v)    { return v; }
nuclear@1:     inline double   SystemToBE(double v)    { return v; }
nuclear@1: 
nuclear@1: #else
nuclear@1:     #error "OVR_BYTE_ORDER must be defined to OVR_LITTLE_ENDIAN or OVR_BIG_ENDIAN"
nuclear@1: #endif
nuclear@1: 
nuclear@1: } // namespace ByteUtil
nuclear@1: 
nuclear@1: 
nuclear@1: 
nuclear@1: }} // OVR::Alg
nuclear@1: 
nuclear@1: #endif