/* -*- c++ -*-
Template Radix sort implementation
This file is part of the dpp library of C++ template classes
doc: http://diaxen.ssji.net/dpp/index.html
repo: https://www.ssji.net/svn/projets/trunk/libdpp
This program is free software: you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public License
as published by the Free Software Foundation, either version 3 of
the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this program. If not, see
.
(c) 2012 Alexandre Becoulet
*/
#ifndef DPP_RADIX_SORT_HH_
#define DPP_RADIX_SORT_HH_
#include
#include
#include
/** @file @module{Radix sort} */
namespace dpp {
/** @This class may be specialized to describe how radix are
extracted from values for a given type. Specializations are
provided for integer and floating-point types. */
template
struct radix_sort_type
{
static unsigned int extract(const X x, size_t pos)
{
X::_requires_8bits_radix_width_for_custom_types();
}
};
/** @This provides a generic byte-slicing radix extraction function. */
template
struct radix_sort_type
{
static unsigned int extract(const X x, size_t pos)
{
const uint8_t *d = (const uint8_t *)&x;
return d[pos];
}
};
/** @internal */
#define _DPP_RADIX_SORT_INT(type) \
/** @This class provides a radix extaction function for @tt{type} integers */ \
template \
struct radix_sort_type \
{ \
static const size_t _bsize = 1 << bits; \
static const size_t _passes = sizeof(type) * 8 / bits + (bits % 8 != 0); \
\
static unsigned int extract(type x, size_t pos) \
{ \
return (x >> (bits * pos)) & ((1 << bits) - 1); \
} \
}
_DPP_RADIX_SORT_INT(signed char);
_DPP_RADIX_SORT_INT(unsigned char);
_DPP_RADIX_SORT_INT(signed short);
_DPP_RADIX_SORT_INT(unsigned short);
_DPP_RADIX_SORT_INT(signed int);
_DPP_RADIX_SORT_INT(unsigned int);
_DPP_RADIX_SORT_INT(signed long);
_DPP_RADIX_SORT_INT(unsigned long);
_DPP_RADIX_SORT_INT(signed long long);
_DPP_RADIX_SORT_INT(unsigned long long);
/** @internal */
#define _DPP_RADIX_SORT_FLOAT(type) \
/** @This class provides a radix extaction function for @tt{type} floating-point values */ \
template \
struct radix_sort_type \
{ \
static const size_t _bsize = 1 << bits; \
static const size_t _passes = sizeof(type) * 8 / bits + (bits % 8 != 0); \
\
static unsigned int extract(type x, size_t pos) \
{ \
switch (sizeof(type)) \
{ \
case 4: { \
int32_t v = *(int32_t*)&x; \
return ((((v >> 31) | (1 << 31)) ^ v) >> (bits * pos)) & ((1 << bits) - 1); \
} \
case 8: { \
int64_t v = *(int64_t*)&x; \
return ((((v >> 63) | (1ULL << 63)) ^ v) >> (bits * pos)) & ((1 << bits) - 1); \
} \
default: \
std::abort(); \
} \
} \
}
_DPP_RADIX_SORT_FLOAT(float);
_DPP_RADIX_SORT_FLOAT(double);
/** @internal */
template
struct _radix_sort
{
static const size_t _bsize = 1 << bits;
static const size_t _passes = sizeof(X) * 8 / bits + (bits % 8 != 0); \
/** @This performs actual sorting */
static void sort(X *in, X *next_in, X *out, size_t len)
{
size_t hist[_passes][_bsize];
// zero histograms
for (size_t j = 0; j < _passes; j++)
for (size_t i = 0; i < _bsize; i++)
hist[j][i] = 0;
// compute histograms
for (size_t i = 0; i < len; i++)
for (size_t j = 0; j < _passes; j++)
hist[j][radix_sort_type::extract(in[i], j)]++;
// multiple passes stable radix-sort
for (size_t j = 0; j < _passes; j++)
{
uintptr_t offset[_bsize], o;
// compute offsets
o = offset[0] = 0;
for (size_t i = 1; i < _bsize; i++)
o = offset[i] = o + hist[j][i - 1];
// reorder array
for (size_t i = 0; i < len; i++)
{
size_t x = radix_sort_type::extract(in[i], j);
out[offset[x]++] = in[i];
}
// swap input/output arrays for next pass
in = next_in;
std::swap(in, out);
next_in = in;
}
}
/** @This performs sorting and final array copy when number of passes are odd
and sorting result must be stored back in original array. */
static void sort_in(X *in, size_t len)
{
X tmp[len];
sort(in, in, tmp, len);
if (_passes % 2)
for (size_t i = 0; i < len; i++)
in[i] = tmp[i];
}
/** @This performs input array copy to temporary storage when
number of passes are odd and sorting. */
static void sort_out(const X *in, X *out, size_t len)
{
if (_passes % 2)
{
X tmp[len];
for (size_t i = 0; i < len; i++)
tmp[i] = in[i];
sort(tmp, tmp, out, len);
}
else if (_passes > 1)
{
X tmp[len];
sort((X*)in, out, tmp, len);
}
else
{
sort((X*)in, 0, out, len);
}
}
};
/** @This function performs radix-sort on container iterators. Radix
width is 8 bits. */
template
void radix_sort(const iterator &begin, const iterator &end)
{
typedef typename iterator::value_type type;
size_t len = end - begin;
_radix_sort::sort_in(&*begin, len);
}
/** @This function performs radix-sort on container
iterators. Specified radix bit width is used. */
template
void radix_sort(const iterator &begin, const iterator &end)
{
typedef typename iterator::value_type type;
size_t len = end - begin;
_radix_sort::sort_in(&*begin, len);
}
/** @This function performs radix-sort on array. Radix
width is 8 bits. */
template
void radix_sort(X *begin, X *end)
{
typedef X type;
size_t len = end - begin;
_radix_sort::sort_in(begin, len);
}
/** @This function performs radix-sort on array.
Specified radix bit width is used. */
template
void radix_sort(X *begin, X *end)
{
typedef X type;
size_t len = end - begin;
_radix_sort::sort_in(begin, len);
}
/** @This function performs radix-sort on array. Radix
width is 8 bits. */
template
void radix_sort(const X *begin, const X *end, X *out)
{
typedef X type;
size_t len = end - begin;
_radix_sort::sort_out(begin, out, len);
}
/** @This function performs radix-sort on array.
Specified radix bit width is used. */
template
void radix_sort(const X *begin, const X *end, X *out)
{
typedef X type;
size_t len = end - begin;
_radix_sort::sort_out(begin, out, len);
}
}
#endif