sort.h File Reference

{WIP} Provides a fast and generic sorting interface. More...

#include "algorithm.h"
#include "bits.h"
#include "fakestd.h"
#include "simple.h"
#include <bitset>
#include <numeric>

Include dependency graph for sort.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	kblib::is_radix_sortable< T, typename >
struct	kblib::is_radix_sortable< T, void_if_t< std::is_integral< T >::value > >
struct	kblib::is_radix_sortable< T, void_if_t< std::is_enum< T >::value > >
struct	kblib::is_radix_sortable< std::bitset< B >, void >
struct	kblib::is_radix_sortable< T, void_if_t< is_linear_container_v< T > and std::is_integral< typename T::value_type >::value > >
struct	kblib::is_trivial_transformation< T >
struct	kblib::is_trivial_transformation< identity >
struct	kblib::detail_sort::sort_transform_impl< RandomAccessIt, UnaryOperation, BinaryPredicate, SortKey, small_size, bool, bool, bool, bool >
	Sort data after applying an arbitrary transformation to it. The primary template handles the general case of arbitrary transformation and arbitrary compare predicate. More...
struct	kblib::detail_sort::sort_transform_impl< RandomAccessIt, UnaryOperation, BinaryPredicate, SortKey, small_size, true, false, false, false >
	Sort implementation for pointer to member object of non-fundamental type, so sort keys are constant time to extract (this is most similar to a general sort()) More...
struct	kblib::detail_sort::sort_transform_impl< RandomAccessIt, UnaryOperation, std::less< LessT >, SortKey, small_size, true, true, false, false >
	Sort implementation for pointer to member object of fundamental non-integral type with default sorting, so sort keys are constant time to extract and compare. More...
struct	kblib::detail_sort::sort_transform_impl< RandomAccessIt, UnaryOperation, std::greater< LessT >, SortKey, small_size, true, true, false, false >
	Sort implementation for pointer to member object of fundamental non-integral type with reverse sorting, so sort keys are constant time to extract and compare. More...
struct	kblib::detail_sort::sort_transform_impl< RandomAccessIt, UnaryOperation, std::less< LessT >, SortKey, small_size, true, true, true, true >
	Sort implementation for pointer to member object of integral type with default sorting, so we can do radix sort. More...
struct	kblib::detail_sort::sort_transform_impl< RandomAccessIt, UnaryOperation, std::greater< LessT >, SortKey, small_size, true, true, true, true >
	Sort implementation for pointer to member object of integral type with reverse sorting, so we can do radix sort. More...
struct	kblib::detail_sort::sort_transform_impl< RandomAccessIt, UnaryOperation, std::less< LessT >, SortKey, small_size, M, false, true, false >
	Sort implementation for key of radix sortable type type with default sorting. More...
struct	kblib::detail_sort::sort_transform_impl< RandomAccessIt, UnaryOperation, std::greater< LessT >, SortKey, small_size, M, false, true, false >
	Sort implementation for key of radix sortable type type with reverse sorting. More...

Namespaces
namespace	kblib
	The main namespace in which all entities from kblib are defined.
namespace	kblib::detail_sort

Enumerations
enum class	kblib::detail_sort::sort_direction { kblib::detail_sort::ascending , kblib::detail_sort::descending }

Functions
template<typename RandomAccessIt , typename Compare = std::less<>>
constexpr auto	kblib::insertion_sort (const RandomAccessIt begin, const RandomAccessIt end, Compare &&compare={}) noexcept(noexcept(swap(*begin, *begin)) and noexcept(compare(*begin, *begin))) -> void
	In-place insertion sort. As is usual, it is stable. Provides as a guarantee that it will perform no moves on sorted input. More...
template<typename RandomAccessIt , typename RandomAccessIt2 , typename Compare = std::less<>>
constexpr auto	kblib::insertion_sort_copy (const RandomAccessIt begin, const RandomAccessIt end, const RandomAccessIt2 d_begin, const RandomAccessIt2 d_end, Compare &&compare={}) noexcept(noexcept(detail_algorithm::shift_backward(d_begin, d_begin, d_end)) and noexcept(*d_begin= *begin)) -> void
	Out-of-place insertion sort, which does not modify the input. Provides as a guarantee that it will perform no moves on sorted input. More...
template<typename RandomAccessIt , typename RandomAccessIt2 , typename Compare = std::less<>>
constexpr auto	kblib::adaptive_insertion_sort_copy (const RandomAccessIt begin, const RandomAccessIt end, const RandomAccessIt2 d_begin, const RandomAccessIt2 d_end, Compare &&compare={}) noexcept(noexcept(detail_algorithm::shift_backward(d_begin, d_begin, d_end)) and noexcept(*d_begin= *begin)) -> void
	An adaptive sort which, at the cost of some additional work (time complexity Θ(sqrt(n))), avoids quadratic behavior for reverse-sorted inputs (and, in fact, handles them in optimal time). It's still possible to fool it, but it requires a staggered input, which is a highly unlikely shape for random data. More...
template<typename T >
constexpr auto	kblib::byte_count (T) noexcept -> enable_if_t< std::is_integral< T >::value, std::size_t >
template<typename T >
constexpr auto	kblib::byte_count (T *) noexcept -> std::size_t
template<typename T >
constexpr auto	kblib::byte_count (const std::unique_ptr< T > &) noexcept -> std::size_t
template<typename T >
constexpr auto	kblib::byte_count (const T &x) noexcept -> enable_if_t< is_linear_container_v< T > and(std::is_integral< typename T::value_type >::value or is_byte_v< T >) and sizeof(typename T::value_type)==1, std::size_t >
constexpr auto	kblib::byte_count (...) -> void=delete
template<typename T >
constexpr auto	kblib::get_byte_index (T x, std::size_t idx) noexcept -> enable_if_t< std::is_integral< T >::value, unsigned char >
template<typename T >
constexpr auto	kblib::get_byte_index (const T &x, std::size_t idx) noexcept -> enable_if_t< std::is_enum< T >::value, unsigned char >
template<typename T >
auto	kblib::get_byte_index (T *x, std::size_t idx) noexcept -> unsigned char
template<typename T >
auto	kblib::get_byte_index (const std::unique_ptr< T > &x, std::size_t idx) noexcept -> unsigned char
template<typename RandomAccessIt , typename Compare >
constexpr auto	kblib::detail_sort::sort (RandomAccessIt, const RandomAccessIt, Compare) -> void
template<typename RandomAccessIt , typename Compare >
constexpr auto	kblib::detail_sort::stable_sort (RandomAccessIt, const RandomAccessIt, Compare) -> void
template<typename RandomAccessIt , typename Compare , std::size_t small_size>
constexpr auto	kblib::detail_sort::merge_sort (RandomAccessIt begin, const RandomAccessIt end, Compare cmp) -> void
template<typename RandomAccessIt , typename Compare , std::size_t small_size>
constexpr auto	kblib::detail_sort::heap_sort (RandomAccessIt begin, const RandomAccessIt end, Compare cmp) -> void
template<sort_direction dir, typename RandomAccessIt , typename Projection >
constexpr auto	kblib::detail_sort::radix_sort_i (RandomAccessIt begin, const RandomAccessIt end, Projection proj) -> void
template<sort_direction dir, typename RandomAccessIt , typename Projection >
constexpr auto	kblib::detail_sort::radix_sort_s (RandomAccessIt begin, const RandomAccessIt end, Projection proj) -> void
template<std::size_t size>
constexpr auto	kblib::detail_sort::make_array_for (std::false_type) -> kblib::containing_ptr< std::array< std::size_t, size > >
template<std::size_t size>
auto	kblib::detail_sort::make_array_for (std::true_type) -> kblib::heap_value< std::array< std::size_t, size+1 > >
template<sort_direction dir, typename RandomAccessIt1 , typename RandomAccessIt2 , typename Projection >
constexpr auto	kblib::detail_sort::counting_sort (RandomAccessIt1 begin, const RandomAccessIt1 end, RandomAccessIt2 d_begin, Projection proj) -> void
template<typename RandomAccessIt , typename UnaryOperation , typename BinaryPredicate >
constexpr auto	kblib::sort_transform (RandomAccessIt begin, RandomAccessIt end, UnaryOperation &&transform, BinaryPredicate &&compare) -> void
	Sorts a range after applying a transformation. More...
template<typename RandomAccessIt , typename UnaryOperation >
constexpr auto	kblib::sort_transform (RandomAccessIt begin, RandomAccessIt end, UnaryOperation &&transform) -> void
template<typename RandomAccessIt , typename BinaryPredicate >
constexpr auto	kblib::sort (RandomAccessIt begin, RandomAccessIt end, BinaryPredicate &&compare) -> void
	Sorts a range. More...
template<typename RandomAccessIt >
constexpr auto	kblib::sort (RandomAccessIt begin, RandomAccessIt end) -> void

Variables
template<typename T >
constexpr bool	kblib::is_radix_sortable_v = is_radix_sortable<T>::value
template<typename T >
constexpr bool	kblib::is_byte_v = false

Detailed Description

{WIP} Provides a fast and generic sorting interface.

Author

killerbee

Date

2019-2021

Copyright

GNU General Public Licence v3.0

Definition in file sort.h.