\hypertarget{sort_8h}{}\doxysection{kblib/sort.h File Reference}
\label{sort_8h}\index{kblib/sort.h@{kblib/sort.h}}


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


{\ttfamily \#include \char`\"{}algorithm.\+h\char`\"{}}\newline
{\ttfamily \#include \char`\"{}bits.\+h\char`\"{}}\newline
{\ttfamily \#include \char`\"{}fakestd.\+h\char`\"{}}\newline
{\ttfamily \#include \char`\"{}simple.\+h\char`\"{}}\newline
{\ttfamily \#include $<$bitset$>$}\newline
{\ttfamily \#include $<$numeric$>$}\newline
Include dependency graph for sort.\+h\+:\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=350pt]{sort_8h__incl}
\end{center}
\end{figure}
This graph shows which files directly or indirectly include this file\+:\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=350pt]{sort_8h__dep__incl}
\end{center}
\end{figure}
\doxysubsection*{Classes}
\begin{DoxyCompactItemize}
\item 
struct \mbox{\hyperlink{structkblib_1_1is__radix__sortable}{kblib\+::is\+\_\+radix\+\_\+sortable$<$ T, typename $>$}}
\item 
struct \mbox{\hyperlink{structkblib_1_1is__radix__sortable_3_01_t_00_01void__if__t_3_01std_1_1is__integral_3_01_t_01_4_1_1value_01_4_01_4}{kblib\+::is\+\_\+radix\+\_\+sortable$<$ T, void\+\_\+if\+\_\+t$<$ std\+::is\+\_\+integral$<$ T $>$\+::value $>$ $>$}}
\item 
struct \mbox{\hyperlink{structkblib_1_1is__radix__sortable_3_01_t_00_01void__if__t_3_01std_1_1is__enum_3_01_t_01_4_1_1value_01_4_01_4}{kblib\+::is\+\_\+radix\+\_\+sortable$<$ T, void\+\_\+if\+\_\+t$<$ std\+::is\+\_\+enum$<$ T $>$\+::value $>$ $>$}}
\item 
struct \mbox{\hyperlink{structkblib_1_1is__radix__sortable_3_01std_1_1bitset_3_01_b_01_4_00_01void_01_4}{kblib\+::is\+\_\+radix\+\_\+sortable$<$ std\+::bitset$<$ B $>$, void $>$}}
\item 
struct \mbox{\hyperlink{structkblib_1_1is__radix__sortable_3_01_t_00_01void__if__t_3_01is__linear__container__v_3_01_t_0e0a5e14e1e0c00645c6c7783f7f45255}{kblib\+::is\+\_\+radix\+\_\+sortable$<$ T, void\+\_\+if\+\_\+t$<$ is\+\_\+linear\+\_\+container\+\_\+v$<$ T $>$ and std\+::is\+\_\+integral$<$ typename T\+::value\+\_\+type $>$\+::value $>$ $>$}}
\item 
struct \mbox{\hyperlink{structkblib_1_1is__trivial__transformation}{kblib\+::is\+\_\+trivial\+\_\+transformation$<$ T $>$}}
\item 
struct \mbox{\hyperlink{structkblib_1_1is__trivial__transformation_3_01identity_01_4}{kblib\+::is\+\_\+trivial\+\_\+transformation$<$ identity $>$}}
\item 
struct \mbox{\hyperlink{structkblib_1_1detail__sort_1_1sort__transform__impl}{kblib\+::detail\+\_\+sort\+::sort\+\_\+transform\+\_\+impl$<$ Random\+Access\+It, Unary\+Operation, Binary\+Predicate, Sort\+Key, small\+\_\+size, bool, bool, bool, bool $>$}}
\begin{DoxyCompactList}\small\item\em Sort data after applying an arbitrary transformation to it. The primary template handles the general case of arbitrary transformation and arbitrary compare predicate. \end{DoxyCompactList}\item 
struct \mbox{\hyperlink{structkblib_1_1detail__sort_1_1sort__transform__impl_3_01_random_access_it_00_01_unary_operation935542bc395b86fd33cf9be63ad3de74}{kblib\+::detail\+\_\+sort\+::sort\+\_\+transform\+\_\+impl$<$ Random\+Access\+It, Unary\+Operation, Binary\+Predicate, Sort\+Key, small\+\_\+size, true, false, false, false $>$}}
\begin{DoxyCompactList}\small\item\em 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 \mbox{\hyperlink{namespacekblib_1_1detail__sort_a3b873e1b1c2c3a4865638d2c904c4c1d}{sort()}}) \end{DoxyCompactList}\item 
struct \mbox{\hyperlink{structkblib_1_1detail__sort_1_1sort__transform__impl_3_01_random_access_it_00_01_unary_operationf1e9e425aa5b0d07fb4c879cfd659585}{kblib\+::detail\+\_\+sort\+::sort\+\_\+transform\+\_\+impl$<$ Random\+Access\+It, Unary\+Operation, std\+::less$<$ Less\+T $>$, Sort\+Key, small\+\_\+size, true, true, false, false $>$}}
\begin{DoxyCompactList}\small\item\em 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. \end{DoxyCompactList}\item 
struct \mbox{\hyperlink{structkblib_1_1detail__sort_1_1sort__transform__impl_3_01_random_access_it_00_01_unary_operation3c2c850b5ad1e4acd66097d89e51c4f1}{kblib\+::detail\+\_\+sort\+::sort\+\_\+transform\+\_\+impl$<$ Random\+Access\+It, Unary\+Operation, std\+::greater$<$ Less\+T $>$, Sort\+Key, small\+\_\+size, true, true, false, false $>$}}
\begin{DoxyCompactList}\small\item\em 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. \end{DoxyCompactList}\item 
struct \mbox{\hyperlink{structkblib_1_1detail__sort_1_1sort__transform__impl_3_01_random_access_it_00_01_unary_operation03a4b8b2612786c18e671d7b72685405}{kblib\+::detail\+\_\+sort\+::sort\+\_\+transform\+\_\+impl$<$ Random\+Access\+It, Unary\+Operation, std\+::less$<$ Less\+T $>$, Sort\+Key, small\+\_\+size, true, true, true, true $>$}}
\begin{DoxyCompactList}\small\item\em Sort implementation for pointer to member object of integral type with default sorting, so we can do radix sort. \end{DoxyCompactList}\item 
struct \mbox{\hyperlink{structkblib_1_1detail__sort_1_1sort__transform__impl_3_01_random_access_it_00_01_unary_operationbcac2feda0fade87a36510b7d31d2576}{kblib\+::detail\+\_\+sort\+::sort\+\_\+transform\+\_\+impl$<$ Random\+Access\+It, Unary\+Operation, std\+::greater$<$ Less\+T $>$, Sort\+Key, small\+\_\+size, true, true, true, true $>$}}
\begin{DoxyCompactList}\small\item\em Sort implementation for pointer to member object of integral type with reverse sorting, so we can do radix sort. \end{DoxyCompactList}\item 
struct \mbox{\hyperlink{structkblib_1_1detail__sort_1_1sort__transform__impl_3_01_random_access_it_00_01_unary_operationfec06b35b16d095881d1da3ea9777678}{kblib\+::detail\+\_\+sort\+::sort\+\_\+transform\+\_\+impl$<$ Random\+Access\+It, Unary\+Operation, std\+::less$<$ Less\+T $>$, Sort\+Key, small\+\_\+size, M, false, true, false $>$}}
\begin{DoxyCompactList}\small\item\em Sort implementation for key of radix sortable type type with default sorting. \end{DoxyCompactList}\item 
struct \mbox{\hyperlink{structkblib_1_1detail__sort_1_1sort__transform__impl_3_01_random_access_it_00_01_unary_operation51fbb4ca17e940976b57d3794660a6d8}{kblib\+::detail\+\_\+sort\+::sort\+\_\+transform\+\_\+impl$<$ Random\+Access\+It, Unary\+Operation, std\+::greater$<$ Less\+T $>$, Sort\+Key, small\+\_\+size, M, false, true, false $>$}}
\begin{DoxyCompactList}\small\item\em Sort implementation for key of radix sortable type type with reverse sorting. \end{DoxyCompactList}\end{DoxyCompactItemize}
\doxysubsection*{Namespaces}
\begin{DoxyCompactItemize}
\item 
namespace \mbox{\hyperlink{namespacekblib}{kblib}}
\begin{DoxyCompactList}\small\item\em The main namespace in which all entities from kblib are defined. \end{DoxyCompactList}\item 
namespace \mbox{\hyperlink{namespacekblib_1_1detail__sort}{kblib\+::detail\+\_\+sort}}
\end{DoxyCompactItemize}
\doxysubsection*{Enumerations}
\begin{DoxyCompactItemize}
\item 
enum class \mbox{\hyperlink{namespacekblib_1_1detail__sort_ae4569ffb1f5bfbe2b7792cba89647a07}{kblib\+::detail\+\_\+sort\+::sort\+\_\+direction}} \{ \mbox{\hyperlink{namespacekblib_1_1detail__sort_ae4569ffb1f5bfbe2b7792cba89647a07a9c9ab624360885fcf93b7643c93b6748}{kblib\+::detail\+\_\+sort\+::ascending}}
, \mbox{\hyperlink{namespacekblib_1_1detail__sort_ae4569ffb1f5bfbe2b7792cba89647a07ab19e9805fd7727c52ca04dfa3d24a2e5}{kblib\+::detail\+\_\+sort\+::descending}}
 \}
\end{DoxyCompactItemize}
\doxysubsection*{Functions}
\begin{DoxyCompactItemize}
\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Compare  = std\+::less$<$$>$$>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a43cda388d529e7f9553850b366ef3380}{kblib\+::insertion\+\_\+sort}} (const Random\+Access\+It begin, const Random\+Access\+It end, Compare \&\&compare=\{\}) noexcept(noexcept(swap($\ast$begin, $\ast$begin)) and noexcept(compare($\ast$begin, $\ast$begin))) -\/$>$ void
\begin{DoxyCompactList}\small\item\em In-\/place insertion sort. As is usual, it is stable. Provides as a guarantee that it will perform no moves on sorted input. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Random\+Access\+It2 , typename Compare  = std\+::less$<$$>$$>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a654de993e7d26592cdc4e05443150296}{kblib\+::insertion\+\_\+sort\+\_\+copy}} (const Random\+Access\+It begin, const Random\+Access\+It end, const Random\+Access\+It2 d\+\_\+begin, const Random\+Access\+It2 d\+\_\+end, Compare \&\&compare=\{\}) noexcept(noexcept(detail\+\_\+algorithm\+::shift\+\_\+backward(d\+\_\+begin, d\+\_\+begin, d\+\_\+end)) and noexcept($\ast$d\+\_\+begin= $\ast$begin)) -\/$>$ void
\begin{DoxyCompactList}\small\item\em Out-\/of-\/place insertion sort, which does not modify the input. Provides as a guarantee that it will perform no moves on sorted input. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Random\+Access\+It2 , typename Compare  = std\+::less$<$$>$$>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a707446076d1cc9e803e1041117924a73}{kblib\+::adaptive\+\_\+insertion\+\_\+sort\+\_\+copy}} (const Random\+Access\+It begin, const Random\+Access\+It end, const Random\+Access\+It2 d\+\_\+begin, const Random\+Access\+It2 d\+\_\+end, Compare \&\&compare=\{\}) noexcept(noexcept(detail\+\_\+algorithm\+::shift\+\_\+backward(d\+\_\+begin, d\+\_\+begin, d\+\_\+end)) and noexcept($\ast$d\+\_\+begin= $\ast$begin)) -\/$>$ void
\begin{DoxyCompactList}\small\item\em 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\textquotesingle{}s still possible to fool it, but it requires a staggered input, which is a highly unlikely shape for random data. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename T $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a407763ccb393b23e4d9616cd76f03fe5}{kblib\+::byte\+\_\+count}} (T) noexcept -\/$>$ enable\+\_\+if\+\_\+t$<$ std\+::is\+\_\+integral$<$ T $>$\+::value, std\+::size\+\_\+t $>$
\item 
{\footnotesize template$<$typename T $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_aafdfcc252a37b2ca60ce1807d188d658}{kblib\+::byte\+\_\+count}} (T $\ast$) noexcept -\/$>$ std\+::size\+\_\+t
\item 
{\footnotesize template$<$typename T $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_afca31fdc704e55f5ffabeea66e533794}{kblib\+::byte\+\_\+count}} (const std\+::unique\+\_\+ptr$<$ T $>$ \&) noexcept -\/$>$ std\+::size\+\_\+t
\item 
{\footnotesize template$<$typename T $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a913269f668b6359d0ebc552f8fdb9bc6}{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 $>$
\item 
constexpr auto \mbox{\hyperlink{namespacekblib_a84bbf075be5e924b9ff6efd6fb9ea0de}{kblib\+::byte\+\_\+count}} (...) -\/$>$ void=delete
\item 
{\footnotesize template$<$typename T $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_ae8bc9b87eff6f20b23a0da335c9501b9}{kblib\+::get\+\_\+byte\+\_\+index}} (T x, std\+::size\+\_\+t idx) noexcept -\/$>$ enable\+\_\+if\+\_\+t$<$ std\+::is\+\_\+integral$<$ T $>$\+::value, unsigned char $>$
\item 
{\footnotesize template$<$typename T $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a9eb65dc24cfed091382a277d77ac00a0}{kblib\+::get\+\_\+byte\+\_\+index}} (const T \&x, std\+::size\+\_\+t idx) noexcept -\/$>$ enable\+\_\+if\+\_\+t$<$ std\+::is\+\_\+enum$<$ T $>$\+::value, unsigned char $>$
\item 
{\footnotesize template$<$typename T $>$ }\\auto \mbox{\hyperlink{namespacekblib_aa0ce497444d4994f7a2c9832e415f607}{kblib\+::get\+\_\+byte\+\_\+index}} (T $\ast$x, std\+::size\+\_\+t idx) noexcept -\/$>$ unsigned char
\item 
{\footnotesize template$<$typename T $>$ }\\auto \mbox{\hyperlink{namespacekblib_adaffd058800d74e8a1573f1f15b8ec11}{kblib\+::get\+\_\+byte\+\_\+index}} (const std\+::unique\+\_\+ptr$<$ T $>$ \&x, std\+::size\+\_\+t idx) noexcept -\/$>$ unsigned char
\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Compare $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_a3b873e1b1c2c3a4865638d2c904c4c1d}{kblib\+::detail\+\_\+sort\+::sort}} (Random\+Access\+It, const Random\+Access\+It, Compare) -\/$>$ void
\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Compare $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_af5a02e7ee5bdc9865f19946e829dff5e}{kblib\+::detail\+\_\+sort\+::stable\+\_\+sort}} (Random\+Access\+It, const Random\+Access\+It, Compare) -\/$>$ void
\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Compare , std\+::size\+\_\+t small\+\_\+size$>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_a00851154e70e649ffb1972b0cb461199}{kblib\+::detail\+\_\+sort\+::merge\+\_\+sort}} (Random\+Access\+It begin, const Random\+Access\+It end, Compare cmp) -\/$>$ void
\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Compare , std\+::size\+\_\+t small\+\_\+size$>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_a280b17f79cf4bcc871b9eb23de612dba}{kblib\+::detail\+\_\+sort\+::heap\+\_\+sort}} (Random\+Access\+It begin, const Random\+Access\+It end, Compare cmp) -\/$>$ void
\item 
{\footnotesize template$<$sort\+\_\+direction dir, typename Random\+Access\+It , typename Projection $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_a0f3e1fc1f2ed59538aa52f01165b5c81}{kblib\+::detail\+\_\+sort\+::radix\+\_\+sort\+\_\+i}} (Random\+Access\+It begin, const Random\+Access\+It end, Projection proj) -\/$>$ void
\item 
{\footnotesize template$<$sort\+\_\+direction dir, typename Random\+Access\+It , typename Projection $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_a9c74bbb469dc7a2355b5d62913e9dfd9}{kblib\+::detail\+\_\+sort\+::radix\+\_\+sort\+\_\+s}} (Random\+Access\+It begin, const Random\+Access\+It end, Projection proj) -\/$>$ void
\item 
{\footnotesize template$<$std\+::size\+\_\+t size$>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_a2ff494c126d5f8be25c0602e00b5ff2d}{kblib\+::detail\+\_\+sort\+::make\+\_\+array\+\_\+for}} (std\+::false\+\_\+type) -\/$>$ \mbox{\hyperlink{structkblib_1_1containing__ptr}{kblib\+::containing\+\_\+ptr}}$<$ std\+::array$<$ std\+::size\+\_\+t, size $>$ $>$
\item 
{\footnotesize template$<$std\+::size\+\_\+t size$>$ }\\auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_ad77575019d9733392aebfdbb371d7323}{kblib\+::detail\+\_\+sort\+::make\+\_\+array\+\_\+for}} (std\+::true\+\_\+type) -\/$>$ \mbox{\hyperlink{classkblib_1_1heap__value}{kblib\+::heap\+\_\+value}}$<$ std\+::array$<$ std\+::size\+\_\+t, size+1 $>$ $>$
\item 
{\footnotesize template$<$sort\+\_\+direction dir, typename Random\+Access\+It1 , typename Random\+Access\+It2 , typename Projection $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_1_1detail__sort_a0ae455fa600a4399c16b1159b04ec5c9}{kblib\+::detail\+\_\+sort\+::counting\+\_\+sort}} (Random\+Access\+It1 begin, const Random\+Access\+It1 end, Random\+Access\+It2 d\+\_\+begin, Projection proj) -\/$>$ void
\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Unary\+Operation , typename Binary\+Predicate $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a7b871050bf43912f54b38ba4ecf027fe}{kblib\+::sort\+\_\+transform}} (Random\+Access\+It begin, Random\+Access\+It end, Unary\+Operation \&\&transform, Binary\+Predicate \&\&compare) -\/$>$ void
\begin{DoxyCompactList}\small\item\em Sorts a range after applying a transformation. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Unary\+Operation $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a49c4ab0021b9025dcc1ab803f35130a7}{kblib\+::sort\+\_\+transform}} (Random\+Access\+It begin, Random\+Access\+It end, Unary\+Operation \&\&transform) -\/$>$ void
\item 
{\footnotesize template$<$typename Random\+Access\+It , typename Binary\+Predicate $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_ae0cd00a865682926e1053ece9dc8ccdb}{kblib\+::sort}} (Random\+Access\+It begin, Random\+Access\+It end, Binary\+Predicate \&\&compare) -\/$>$ void
\begin{DoxyCompactList}\small\item\em Sorts a range. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Random\+Access\+It $>$ }\\constexpr auto \mbox{\hyperlink{namespacekblib_a3b409f97a9a14760031484b8285f7534}{kblib\+::sort}} (Random\+Access\+It begin, Random\+Access\+It end) -\/$>$ void
\end{DoxyCompactItemize}
\doxysubsection*{Variables}
\begin{DoxyCompactItemize}
\item 
{\footnotesize template$<$typename T $>$ }\\constexpr bool \mbox{\hyperlink{namespacekblib_ab58211612f119bcfedd22ca4ef9999de}{kblib\+::is\+\_\+radix\+\_\+sortable\+\_\+v}} = is\+\_\+radix\+\_\+sortable$<$T$>$\+::value
\item 
{\footnotesize template$<$typename T $>$ }\\constexpr bool \mbox{\hyperlink{namespacekblib_ad80f4ade2acc180c9caf217300f2ffa5}{kblib\+::is\+\_\+byte\+\_\+v}} = false
\end{DoxyCompactItemize}


\doxysubsection{Detailed Description}
\{WIP\} Provides a fast and generic sorting interface. 

\begin{DoxyAuthor}{Author}
killerbee 
\end{DoxyAuthor}
\begin{DoxyDate}{Date}
2019-\/2021 
\end{DoxyDate}
\begin{DoxyCopyright}{Copyright}
GNU General Public Licence v3.\+0 
\end{DoxyCopyright}


Definition in file \mbox{\hyperlink{sort_8h_source}{sort.\+h}}.