/*
  ==============================================================================

   This file is part of the JUCE library - "Jules' Utility Class Extensions"
   Copyright 2004-6 by Raw Material Software ltd.

  ------------------------------------------------------------------------------

   JUCE can be redistributed and/or modified under the terms of the
   GNU General Public License, as published by the Free Software Foundation;
   either version 2 of the License, or (at your option) any later version.

   JUCE is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with JUCE; if not, visit www.gnu.org/licenses or write to the
   Free Software Foundation, Inc., 59 Temple Place, Suite 330, 
   Boston, MA 02111-1307 USA

  ------------------------------------------------------------------------------

   If you'd like to release a closed-source product which uses JUCE, commercial
   licenses are also available: visit www.rawmaterialsoftware.com/juce for
   more information.

  ==============================================================================
*/

#ifndef __JUCE_ELEMENTCOMPARATOR_JUCEHEADER__
#define __JUCE_ELEMENTCOMPARATOR_JUCEHEADER__


//==============================================================================
/** Compares pairs of objects to find out which one should come first.

    This is used by arrays for sorting. To use it, you'll need to create a
    subclass of this that will compare pairs of objects in an appropriate way,
    and then pass this object to the array.

    The sortArray method can also be used directly on raw arrays if necessary.

    @see FloatElementComparator, IntegerElementComparator,
         Array::sort, OwnedArray::sort, ReferenceCountedArray::sort
*/
template <class ElementType>
class ElementComparator
{
public:
    //==============================================================================
    /** Destructor. */
    virtual ~ElementComparator()  {}

    //==============================================================================
    /** Compares the order of two objects.

        This must be implemented to compare the two objects passed in, and should
        return:

            - result < 0 means that the first comes before the second
            - result = 0 means that they're equivalent
            - result > 0 means that the second comes before the first
    */
    virtual int compareElements (ElementType first,
                                 ElementType second) = 0;


    //==============================================================================
    /** Uses this comparator to sort a range of elements in an array.

        @param array            the array to sort
        @param firstElement     the index of the first element of the range to be sorted
        @param lastElement      the index of the last element in the range that needs
                                sorting (this is inclusive)
    */
    void sortArray (ElementType* const array,
                    int firstElement,
                    int lastElement)
    {
        if (lastElement > firstElement)
        {
            int fromStack[30], toStack[30];
            int stackIndex = 0;

            for (;;)
            {
                const int size = (lastElement - firstElement) + 1;

                if (size <= 8)
                {
                    int j = lastElement;
                    int maxIndex;

                    while (j > firstElement)
                    {
                        maxIndex = firstElement;
                        for (int k = firstElement + 1; k <= j; ++k)
                            if (compareElements (array[k], array [maxIndex]) > 0)
                                maxIndex = k;

                        const ElementType temp = array [maxIndex];
                        array [maxIndex] = array[j];
                        array [j] = temp;

                        --j;
                    }
                }
                else
                {
                    const int mid = firstElement + (size >> 1);
                    ElementType temp = array [mid];
                    array [mid] = array [firstElement];
                    array [firstElement] = temp;

                    int i = firstElement;
                    int j = lastElement + 1;

                    for (;;)
                    {
                        while (++i <= lastElement
                                && compareElements (array[i], array [firstElement]) <= 0)
                        {}

                        while (--j > firstElement
                                && compareElements (array[j], array [firstElement]) >= 0)
                        {}

                        if (j < i)
                            break;

                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }

                    temp = array [firstElement];
                    array [firstElement] = array[j];
                    array [j] = temp;

                    if (j - 1 - firstElement >= lastElement - i)
                    {
                        if (firstElement + 1 < j)
                        {
                            fromStack [stackIndex] = firstElement;
                            toStack [stackIndex] = j - 1;
                            ++stackIndex;
                        }

                        if (i < lastElement)
                        {
                            firstElement = i;
                            continue;
                        }
                    }
                    else
                    {
                        if (i < lastElement)
                        {
                            fromStack [stackIndex] = i;
                            toStack [stackIndex] = lastElement;
                            ++stackIndex;
                        }

                        if (firstElement + 1 < j)
                        {
                            lastElement = j - 1;
                            continue;
                        }
                    }
                }

                if (--stackIndex < 0)
                    break;

                firstElement = fromStack [stackIndex];
                lastElement = toStack [stackIndex];
            }
        }
    }
};


//==============================================================================
/**
    A simple ElementComparator class that can be used to sort an array of
    integer primitive objects.

    Example: @code
    Array <int> myArray;

    IntegerElementComparator<int> sorter;
    myArray.sort (sorter);
    @endcode

    For floating point values, see the FloatElementComparator class instead.

    @see FloatElementComparator, ElementComparator
*/
template <class ElementType>
class IntegerElementComparator  : public ElementComparator <ElementType>
{
    int compareElements (ElementType first,
                         ElementType second)
    {
        return first - second;
    }
};


//==============================================================================
/**
    A simple ElementComparator class that can be used to sort an array of numeric
    double or floating point primitive objects.

    Example: @code
    Array <double> myArray;

    FloatElementComparator<double> sorter;
    myArray.sort (sorter);
    @endcode

    For integer values, see the IntegerElementComparator class instead.

    @see IntegerElementComparator, ElementComparator
*/
template <class ElementType>
class FloatElementComparator  : public ElementComparator <ElementType>
{
    int compareElements (ElementType first,
                         ElementType second)
    {
        return (first < second) ? -1
                                : ((first == second) ? 0
                                                     : 1);
    }
};



#endif   // __JUCE_ELEMENTCOMPARATOR_JUCEHEADER__
