// Copyright (C) 2005  Davis E. King (davis@dlib.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#ifndef DLIB_SORt_
#define DLIB_SORt_

#include "algs.h"
#include <functional>

namespace dlib
{

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        typename compare
        >
    inline void qsort_array (
        T& array,
        unsigned long left,
        unsigned long right,
        const compare& comp 
    );
    /*!
        requires
            - T implements operator[]                                 
            - the items in array must be comparable by comp where comp is a function
              object with the same syntax as std::less<>
            - the items in array must be swappable by a global swap()   
            - left and right are within the bounds of array
              i.e. array[left] and array[right] are valid elements
            - left <= right
        ensures
            - for all elements in #array between and including left and right the 
              ith element is < the i+1 element
            - sorts using a quick sort algorithm
    !*/ 

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        typename compare
        >
    void hsort_array (
        T& array,
        unsigned long left,
        unsigned long right,
        const compare& comp 
    );
    /*!
        requires
            - T implements operator[]                                 
            - the items in array must be comparable by comp where comp is a function
              object with the same syntax as std::less<>
            - the items in array must be swappable by a global swap()   
            - left and right are within the bounds of array
              i.e. array[left] and array[right] are valid elements
            - left <= right
        ensures
            - for all elements in #array between and including left and right the 
              ith element is < the i+1 element
            - sorts using a heapsort algorithm
    !*/ 

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        typename compare
        >
    void isort_array (
        T& array,
        unsigned long left,
        unsigned long right,
        const compare& comp 
    );
    /*!
        requires
            - T implements operator[]                                 
            - the items in array must be comparable by comp where comp is a function
              object with the same syntax as std::less<>
            - the items in array must be swappable by a global swap()   
            - left and right are within the bounds of array
              i.e. array[left] and array[right] are valid elements
            - left <= right
        ensures
            - for all elements in #array between and including left and right the 
              ith element is < the i+1 element
            - sorts using an insertion sort algorithm
    !*/

// ----------------------------------------------------------------------------------------

    template <
        typename T
        >
    inline void qsort_array (
        T& array,
        unsigned long left,
        unsigned long right
    ); 
    /*!
        requires
            - T implements operator[]                                 
            - the items in array must be comparable by std::less         
            - the items in array must be swappable by a global swap()   
            - left and right are within the bounds of array
              i.e. array[left] and array[right] are valid elements
            - left <= right
        ensures
            - for all elements in #array between and including left and right the 
              ith element is < the i+1 element
            - sorts using a quick sort algorithm
    !*/ 

// ----------------------------------------------------------------------------------------

    template <
        typename T
        >
    void hsort_array (
        T& array,
        unsigned long left,
        unsigned long right
    );
    /*!
        requires
            - T implements operator[]                                 
            - the items in array must be comparable by std::less         
            - the items in array must be swappable by a global swap()   
            - left and right are within the bounds of array
              i.e. array[left] and array[right] are valid elements
            - left <= right
        ensures
            - for all elements in #array between and including left and right the 
              ith element is < the i+1 element
            - sorts using a heapsort algorithm
    !*/ 

// ----------------------------------------------------------------------------------------

    template <
        typename T
        >
    void isort_array (
        T& array,
        unsigned long left,
        unsigned long right
    ); 
    /*!
        requires
            - T implements operator[]                                 
            - the items in array must be comparable by std::less      
            - the items in array must be swappable by a global swap()   
            - left and right are within the bounds of array
              i.e. array[left] and array[right] are valid elements
            - left <= right
        ensures
            - for all elements in #array between and including left and right the 
              ith element is < the i+1 element
            - sorts using an insertion sort algorithm
    !*/

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
//                            IMPLEMENTATION DETAILS
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    namespace sort_helpers
    {
        template <typename T>
        inline const std::less<T> comp (const T&)
        {
            return std::less<T>();
        }

        template <
            typename T,
            typename Y,
            typename compare
            >
        inline unsigned long qsort_partition (
            T& array,
            Y& pivot,
            const unsigned long left,
            const unsigned long right,
            const compare& comp
        )
        /*!
            requires
                - &pivot == &array[right]
                - T implements operator[]                             
                - the items in array must be comparable by comp     
                - left and right are within the bounts of the array
                - left < right
            ensures
                - returns a number called partition_element such that:
                    - left <= partition_element <= right                              
                    - all elements in #array < #array[partition_element] have 
                    indices >= left and < partition_element                         
                    - all elements in #array > #array[partition_element] have 
                    indices > partition_element and <= right
        !*/
        {
            DLIB_ASSERT (&pivot == &array[right] && left < right,
                    "\tunsigned long qsort_partition()"
                    << "\n\t&pivot:        " << &pivot
                    << "\n\t&array[right]: " << &array[right]
                    << "\n\tleft:          " << left
                    << "\n\tright:         " << right );

            exchange(array[(right-left)/2 +left],pivot);

            unsigned long i = left;
            for (unsigned long j = left; j < right; ++j)
            {
                if (comp(array[j] , pivot))
                {
                    swap(array[i],array[j]);
                    ++i;
                }
            }
            exchange(array[i],pivot);
            
            return i;
        }

// ----------------------------------------------------------------------------------------

        template <
            typename T,
            typename compare
            >
        void qsort_array_main (
            T& array,
            const unsigned long left,
            const unsigned long right,
            unsigned long depth_check,
            const compare& comp
        )
        /*!
            requires
                - T implements operator[]                                 
                - the items in array must be comparable by comp         
                - the items in array must be swappable by a global swap()   
                - left and right are within the bounds of array
                  i.e. array[left] and array[right] are valid elements
            ensures
                - for all elements in #array between and including left and right the 
                  ith element is < the i+1 element
                - will only recurse about as deep as log(depth_check) calls
                - sorts using a quick sort algorithm
        !*/ 
        {
            if ( left < right)
            {
                if (right-left < 30 || depth_check == 0)
                {
                    hsort_array(array,left,right,comp);
                }
                else
                {
                    // The idea here is to only let quick sort go about log(N)
                    // calls deep before it kicks into something else.
                    depth_check >>= 1;
                    depth_check += (depth_check>>4);

                    unsigned long partition_element = 
                        qsort_partition(array,array[right],left,right,comp);
                    
                    if (partition_element > 0)
                        qsort_array_main(array,left,partition_element-1,depth_check,comp);
                    qsort_array_main(array,partition_element+1,right,depth_check,comp);
                }
            }
        }

// ----------------------------------------------------------------------------------------

        template <
            typename T,
            typename compare
            >
        void heapify (
            T& array,
            const unsigned long start,
            const unsigned long end,
            unsigned long i,
            const compare& comp
        )
        /*!
            requires
                - T implements operator[]                                 
                - the items in array must be comparable by comp        
                - the items in array must be swappable by a global swap()   
                - start, end, and i are within the bounds of array
                  i.e. array[start], array[end], and array[i] are valid elements
                - start <= i <= end
                - array[i/2] is a max heap
                - array[i/2+1] is a max heap
                - start and end specify the range of the array we are working with.
            ensures
                - array[i] is now a max heap
        !*/
        {
            DLIB_ASSERT (start <= i && i <= end,
                    "\tvoid heapify()"
                    << "\n\tstart:   " << start 
                    << "\n\tend:     " << end 
                    << "\n\ti:       " << i );

            bool keep_going = true;            
            unsigned long left;
            unsigned long right;   
            unsigned long largest; 
            while (keep_going)
            {
                keep_going = false;
                left = (i<<1)+1-start;
                right = left+1;

                if (left <= end && comp(array[i] , array[left]))
                    largest = left;
                else
                    largest = i;

                if (right <= end && comp(array[largest] , array[right]))
                    largest = right;

                if (largest != i)
                {
                    exchange(array[i],array[largest]);
                    i = largest;
                    keep_going = true;
                }
            }
        }

// ----------------------------------------------------------------------------------------
    }
// ----------------------------------------------------------------------------------------


    template <
        typename T
        >
    inline void qsort_array (
        T& array,
        unsigned long left,
        unsigned long right
    ) 
    {
        using namespace sort_helpers;
        qsort_array(array,left,right,comp(array[left]));
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T
        >
    void hsort_array (
        T& array,
        unsigned long left,
        unsigned long right
    )
    {
        using namespace sort_helpers;
        hsort_array(array,left,right,comp(array[left]));
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T
        >
    void isort_array (
        T& array,
        unsigned long left,
        unsigned long right
    ) 
    {
        using namespace sort_helpers;
        isort_array(array,left,right,comp(array[left]));
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        typename compare
        >
    void isort_array (
        T& array,
        const unsigned long left,
        const unsigned long right,
        const compare& comp
    )
    {
        DLIB_ASSERT (left <= right,
                "\tvoid isort_array()"
                << "\n\tleft:          " << left
                << "\n\tright:         " << right );
        using namespace sort_helpers;

        unsigned long pos;
        for (unsigned long i = left+1; i <= right; ++i)
        {
            // everything from left to i-1 is sorted.
            pos = i;
            for (unsigned long j = i-1; comp(array[pos] , array[j]); --j)
            {
                exchange(array[pos],array[j]);
                pos = j;
                
                if (j == left)
                    break;
            }
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T,
        typename compare
        >
    void qsort_array (
        T& array,
        const unsigned long left,
        const unsigned long right,
        const compare& comp
    )
    {      
        DLIB_ASSERT (left <= right,
                "\tvoid qsort_array()"
                << "\n\tleft:          " << left
                << "\n\tright:         " << right );

        sort_helpers::qsort_array_main(array,left,right,right-left,comp);
    }

// ----------------------------------------------------------------------------------------
    
    template <
        typename T,
        typename compare
        >
    void hsort_array (
        T& array,
        const unsigned long left,
        const unsigned long right,
        const compare& comp
    )
    {
        DLIB_ASSERT (left <= right,
                "\tvoid hsort_array()"
                << "\n\tleft:          " << left
                << "\n\tright:         " << right );

        if (right-left < 30)
        {
            isort_array(array,left,right,comp);
            return;
        }

        // turn array into a max heap
        for (unsigned long i = left+((right-left)>>1);; --i)
        {
            sort_helpers::heapify(array,left,right,i,comp);
            if (i == left)
                break;
        }

        // now sort the array
        for (unsigned long i = right; i > left;)
        {
            exchange(array[i],array[left]);
            sort_helpers::heapify(array,left,--i,left,comp);
        }
    }

// ----------------------------------------------------------------------------------------

}

#endif // DLIB_SORt_