diff options
Diffstat (limited to 'ml/dlib/dlib/sort.h')
| -rw-r--r-- | ml/dlib/dlib/sort.h | 490 |
1 files changed, 490 insertions, 0 deletions
diff --git a/ml/dlib/dlib/sort.h b/ml/dlib/dlib/sort.h new file mode 100644 index 000000000..c798372f3 --- /dev/null +++ b/ml/dlib/dlib/sort.h @@ -0,0 +1,490 @@ +// 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_ + |