- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# FMath/FMSort.h

Go to the documentation of this file.

    00001 /*
    00002     Copyright (C) 2005-2007 Feeling Software Inc.
    00003     Portions of the code are:
    00004     Copyright (C) 2005-2007 Sony Computer Entertainment America
    00005
    00006     MIT License: http://www.opensource.org/licenses/mit-license.php
    00007 */
    00008
    00014 #ifndef _FM_SORT_H_
    00015 #define _FM_SORT_H_
    00016
    00017 namespace fm
    00018 {
    00020     template <class T>
    00021     inline void swap(T& a, T& b)
    00022     {
    00023         T temp = a;
    00024         a = b;
    00025         b = temp;
    00026     }
    00027
    00029     template <class T>
    00030     class comparator
    00031     {
    00032     public:
    00034         virtual ~comparator() {}
    00035
    00041         virtual bool compare(const T& a, const T& b)
    00042         {
    00043             return (a < b);
    00044         }
    00045
    00049         void sort(T* data, size_t count)
    00050         {
    00051             if (data == NULL) return;
    00052             quicksort(data, 0, count);
    00053         }
    00054
    00055     private:
    00056         void quicksort(T* data, intptr_t beg, intptr_t end)
    00057         {
    00058             if (end > beg + 1)
    00059             {
    00060                 intptr_t l = beg + 1, r = end;
    00061                 T& pivot = data[beg];
    00062                 while (l < r)
    00063                 {
    00064                     if (compare(data[l], pivot))
    00065                         l++;
    00066                     else
    00067                         swap(data[l], data[--r]);
    00068                 }
    00069                 swap(data[--l], data[beg]);
    00070                 quicksort(data, beg, l);
    00071                 quicksort(data, r, end);
    00072             }
    00073         }
    00074     };
    00075
    00077     template <class T>
    00078     class icomparator : public comparator<T>
    00079     {
    00080     public:
    00082         virtual ~icomparator() {}
    00083
    00089         virtual bool compare(const T& a, const T& b)
    00090         {
    00091             return (b < a);
    00092         }
    00093     };
    00094
    00096     template <class T>
    00097     class pcomparator : public comparator<const void*>
    00098     {
    00099     public:
    00100         typedef const void* valueType;
    00101
    00103         virtual ~pcomparator() {}
    00104
    00110         virtual bool compare(const T* a, const T* b)
    00111         {
    00112             return (a < b);
    00113         }
    00114
    00120         virtual bool compare(const valueType& a, const valueType& b)
    00121         {
    00122             return compare((const T*)a, (const T*)b);
    00123         }
    00124     };
    00125 }
    00126
    00127 #endif // _FM_SORT_H_