dlib C++ Library - sort.h

// 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_