#if !defined(__QSORT__)
#define __QSORT__

// stealed from qsort.c

#if !defined(FASTAPICALLCONVENTION)
  #if defined(_WINDOWS)
    #ifdef WIN32
      #define FASTAPICALLCONVENTION __fastcall
    #else // !WIN32
      #define FASTAPICALLCONVENTION PASCAL
    #endif // WIN32
  #else // !defined(_WINDOWS)
    #define FASTAPICALLCONVENTION
  #endif // defined(_WINDOWS)
#endif // !defined(TSORTCALL)

#define TQSORT_VALUE(TYPE,ptr,count) TQSORT<TYPE, TCompDiff<TYPE>, TSwapAssign<TYPE> >::qsort(ptr,count)
#define TQSORT_VALUEUNSIGNED(TYPE,ptr,count) TQSORT<TYPE, TCompDiffUnsigned<TYPE>, TSwapAssign<TYPE> >::qsort(ptr,count)
#define TQSORT_MEM(TYPE,ptr,count) TQSORT<TYPE, TCompMEM<TYPE>, TSwapMEM<TYPE> >::qsort(ptr,count)
#define TQSORT_PTR(TYPE,ptr,count) TQSORT<TYPE, TCompPtr<TYPE>, TSwapAssign<TYPE> >::qsort(ptr,count)

/* this parameter defines the cutoff between using quick sort and
   insertion sort for arrays; arrays with lengths shorter or equal to the
   below value use insertion sort */

#define TQSORT_CUTOFF 8            /* testing shows that this is good value */

template <class TYPE>
struct TCompDiff
{
    static int FASTAPICALLCONVENTION Compare(const TYPE* pa, const TYPE* pb)
    {
        return *pa - *pb;
    }
};

template <class TYPE>
struct TCompDiffUnsigned
{
    static int FASTAPICALLCONVENTION Compare(const TYPE* pa, const TYPE* pb)
    {
        TYPE tmpA = *pa;
        TYPE tmpB = *pb;

        if (tmpA != tmpB) {
            if (tmpA > tmpB) {
                return +1;
            }
            return -1;
        }

        return 0;
    }
};

template <class TYPE>
struct TCompMEM
{
    static int FASTAPICALLCONVENTION Compare(const TYPE* pa, const TYPE* pb)
    {
        return memcmp(pa, pb, sizeof(TYPE));
    }
};

template <class TYPE>
struct TCompPtr
{
    static int FASTAPICALLCONVENTION Compare(const TYPE* pa, const TYPE* pb)
    {
        BYTE* p1 = (BYTE**)pa;
        BYTE* p2 = (BYTE**)pb;

        if (p1 != p2) {
            if (p1 > p2) {
                return +1;
            }
            return -1;
        }

        return 0;
    }
};

template <class TYPE>
struct TSwapAssign
{
    static void FASTAPICALLCONVENTION Swap(TYPE* pa, TYPE* pb)
    {
        if (pa != pb) {
            TYPE tmp;

            tmp = *pa;
            *pa = *pb;
            *pb = tmp;
        }
    }
};

template <class TYPE>
struct TSwapMEM
{
    static void FASTAPICALLCONVENTION Swap(BYTE* pa, BYTE* pb)
    {
        if (pa != pb) {
            int nWidth = sizeof(TYPE);
            /* Do the swap one character at a time to avoid potential alignment problems. */
            while(nWidth-- > 0) {
                BYTE tmp;

                tmp = *(BYTE*)pa;
                *pa++ = *pb;
                *pb++ = tmp;
            }
        }
    }
};

template <class TYPE, class COMP, class SWAP>
class TQSORT
{
public:
public:
private:
    static void FASTAPICALLCONVENTION shortsort(BYTE *lo, BYTE *hi)
    {
    /***
    *shortsort(hi, lo) - insertion sort for sorting short arrays
    *
    *Purpose:
    *       sorts the sub-array of elements between lo and hi (inclusive)
    *       side effects:  sorts in place
    *       assumes that lo < hi
    *
    *Entry:
    *       BYTE *lo = pointer to low element to sort
    *       BYTE *hi = pointer to high element to sort
    *Exit:
    *       returns void
    *
    *Exceptions:
    *
    *******************************************************************************/
        BYTE *p, *max;

        /* Note: in assertions below, i and j are alway inside original bound of
           array to sort. */

        while (hi > lo) {
            /* A[i] <= A[j] for i <= j, j > hi */
            max = lo;
            for (p = lo+sizeof(TYPE); p <= hi; p += sizeof(TYPE)) {
                /* A[i] <= A[max] for lo <= i < p */
                if (COMP::Compare((TYPE*)p, (TYPE*)max) > 0) {
                    max = p;
                }
                /* A[i] <= A[max] for lo <= i <= p */
            }

            /* A[i] <= A[max] for lo <= i <= hi */

            SWAP::Swap((TYPE*)max, (TYPE*)hi);

            /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */

            hi -= sizeof(TYPE);

            /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
        }
        /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
           so array is sorted */
    }
public:
    static void FASTAPICALLCONVENTION qsort(TYPE* base, size_t num)
    {
    /* sort the array between lo and hi (inclusive) */
    /***
    *qsort(base, num, wid) - quicksort function for sorting arrays
    *
    *Purpose:
    *       quicksort the array of elements
    *       side effects:  sorts in place
    *
    *Entry:
    *       TYPE *base = pointer to base of array
    *       size_t num  = number of elements in the array
    *Exit:
    *       returns void
    *
    *Exceptions:
    *
    *******************************************************************************/

        BYTE *lo, *hi;              /* ends of sub-array currently sorting */
        BYTE *mid;                  /* points to middle of subarray */
        BYTE *loguy, *higuy;        /* traveling pointers for partition step */
        unsigned size;              /* size of the sub-array */
        BYTE *lostk[30], *histk[30];
        int stkptr;                 /* stack for saving sub-array to be processed */

        /* Note: the number of stack entries required is no more than
           1 + log2(size), so 30 is sufficient for any array */

        if (num < 2 || sizeof(TYPE) == 0)
            return;                 /* nothing to do */

        stkptr = 0;                 /* initialize stack */

        lo = (BYTE*)&base[0];
        hi = (BYTE*)&base[num - 1];        /* initialize limits */

        /* this entry point is for pseudo-recursion calling: setting
           lo and hi and jumping to here is like recursion, but stkptr is
           prserved, locals aren't, so we preserve stuff on the stack */
    recurse:

        size = (hi - lo) / sizeof(TYPE) + 1;        /* number of el's to sort */

        /* below a certain size, it is faster to use a O(n^2) sorting method */
        if (size <= TQSORT_CUTOFF) {
             shortsort(lo, hi);
        } else {
            /* First we pick a partititioning element.  The efficiency of the
               algorithm demands that we find one that is approximately the
               median of the values, but also that we select one fast.  Using
               the first one produces bad performace if the array is already
               sorted, so we use the middle one, which would require a very
               wierdly arranged array for worst case performance.  Testing shows
               that a median-of-three algorithm does not, in general, increase
               performance. */

            mid = lo + (size / 2) * sizeof(TYPE);      /* find middle element */
            SWAP::Swap((TYPE*)mid, (TYPE*)lo);               /* swap it to beginning of array */

            /* We now wish to partition the array into three pieces, one
               consisiting of elements <= partition element, one of elements
               equal to the parition element, and one of element >= to it.  This
               is done below; comments indicate conditions established at every
               step. */

            loguy = lo;
            higuy = hi + sizeof(TYPE);

            /* Note that higuy decreases and loguy increases on every iteration,
               so loop must terminate. */
            for (;;) {
                /* lo <= loguy < hi, lo < higuy <= hi + 1,
                   A[i] <= A[lo] for lo <= i <= loguy,
                   A[i] >= A[lo] for higuy <= i <= hi */

                do  {
                    loguy += sizeof(TYPE);
                } while (loguy <= hi && COMP::Compare((const TYPE*)loguy, (const TYPE*)lo) <= 0);

                /* lo < loguy <= hi+1, A[i] <= A[lo] for lo <= i < loguy,
                   either loguy > hi or A[loguy] > A[lo] */

                do  {
                    higuy -= sizeof(TYPE);
                } while (higuy > lo && COMP::Compare((const TYPE*)higuy, (const TYPE*)lo) >= 0);

                /* lo-1 <= higuy <= hi, A[i] >= A[lo] for higuy < i <= hi,
                   either higuy <= lo or A[higuy] < A[lo] */

                if (higuy < loguy)
                    break;

                /* if loguy > hi or higuy <= lo, then we would have exited, so
                   A[loguy] > A[lo], A[higuy] < A[lo],
                   loguy < hi, highy > lo */

                SWAP::Swap((TYPE*)loguy, (TYPE*)higuy);

                /* A[loguy] < A[lo], A[higuy] > A[lo]; so condition at top
                   of loop is re-established */
            }

            /*     A[i] >= A[lo] for higuy < i <= hi,
                   A[i] <= A[lo] for lo <= i < loguy,
                   higuy < loguy, lo <= higuy <= hi
               implying:
                   A[i] >= A[lo] for loguy <= i <= hi,
                   A[i] <= A[lo] for lo <= i <= higuy,
                   A[i] = A[lo] for higuy < i < loguy */

            SWAP::Swap((TYPE*)lo, (TYPE*)higuy); /* put partition element in place */

            /* OK, now we have the following:
                  A[i] >= A[higuy] for loguy <= i <= hi,
                  A[i] <= A[higuy] for lo <= i < higuy
                  A[i] = A[lo] for higuy <= i < loguy    */

            /* We've finished the partition, now we want to sort the subarrays
               [lo, higuy-1] and [loguy, hi].
               We do the smaller one first to minimize stack usage.
               We only sort arrays of length 2 or more.*/

            if ( higuy - 1 - lo >= hi - loguy ) {
                if (lo + sizeof(TYPE) < higuy) {
                    lostk[stkptr] = lo;
                    histk[stkptr] = higuy - sizeof(TYPE);
                    ++stkptr;
                }                           /* save big recursion for later */

                if (loguy < hi) {
                    lo = loguy;
                    goto recurse;           /* do small recursion */
                }
            } else {
                if (loguy < hi) {
                    lostk[stkptr] = loguy;
                    histk[stkptr] = hi;
                    ++stkptr;               /* save big recursion for later */
                }

                if (lo + sizeof(TYPE) < higuy) {
                    hi = higuy - sizeof(TYPE);
                    goto recurse;           /* do small recursion */
                }
            }
        }

        /* We have sorted the array, except for any pending sorts on the stack.
           Check if there are any, and do them. */

        --stkptr;
        if (stkptr >= 0) {
            lo = lostk[stkptr];
            hi = histk[stkptr];
            goto recurse;           /* pop subarray from stack */
        }
        //return; /* all subarrays done */
    }
};

#endif // !defined(__QSORT__)