http://stxxl.sourceforge.net
<sanders@mpi-sb.mpg.de>
http://www.boost.org/LICENSE_1_0.txt
#ifndef STXXL_INTKSORT_HEADER
#define STXXL_INTKSORT_HEADER
#include <algorithm>
#include <cassert>
#include <stxxl/bits/common/types.h>
#include <stxxl/bits/unused.h>
#include <stxxl/bits/parallel.h>
__STXXL_BEGIN_NAMESPACE
template <typename type_key>
static void
count(type_key * a, type_key * aEnd, int_type * bucket, int_type K, typename type_key::key_type offset,
unsigned shift)
{
std::fill(bucket, bucket + K, 0);
for (type_key * p = a; p < aEnd; p++)
{
int_type i = (p->key - offset) >> shift;
bucket[i]++;
}
}
static void
exclusive_prefix_sum(int_type * bucket, int_type K)
{
int_type sum = 0;
for (int_type i = 0; i < K; i++)
{
int_type current = bucket[i];
bucket[i] = sum;
sum += current;
}
}
template <typename type_key>
static void
classify(type_key * a, type_key * aEnd, type_key * b, int_type * bucket, typename type_key::key_type offset, unsigned shift)
{
for (type_key * p = a; p < aEnd; p++)
{
int_type i = (p->key - offset) >> shift;
int_type bi = bucket[i];
b[bi] = *p;
bucket[i] = bi + 1;
}
}
template <class T>
inline void
sort2(T & a, T & b)
{
if (b < a)
std::swap(a, b);
}
template <class T>
inline void
sort3(T & a, T & b, T & c)
{
T temp;
if (b < a)
{
if (c < a)
{
if (b < c)
{
temp = a;
a = b;
b = c;
c = temp;
}
else
{
std::swap(c, a);
}
}
else
{
std::swap(a, b);
}
}
else
{
if (c < a)
{
temp = a;
a = c;
c = b;
b = temp;
}
else
{
if (c < b)
{
std::swap(b, c);
}
}
}
}
template <class T>
inline void
sort4(T & a, T & b, T & c, T & d)
{
sort2(a, b);
sort2(c, d);
if (c < a)
{
if (d < a)
{
std::swap(a, c);
std::swap(b, d);
}
else
{
if (d < b)
{
T temp = a;
a = c;
c = d;
d = b;
b = temp;
}
else
{
T temp = a;
a = c;
c = b;
b = temp;
}
}
}
else
{
if (c < b)
{
if (d < b)
{
T temp = b;
b = c;
c = d;
d = temp;
}
else
{
std::swap(b, c);
}
}
}
}
template <class T>
inline void
sort5(T & a, T & b, T & c, T & d, T & e)
{
sort2(a, b);
sort2(d, e);
if (d < a)
{
std::swap(a, d);
std::swap(b, e);
}
if (d < c)
{
std::swap(c, d);
sort2(d, e);
}
else
{
sort2(a, c);
}
if (d < b)
{
if (e < b)
{
T temp = b;
b = c;
c = d;
d = e;
e = temp;
}
else
{
T temp = b;
b = c;
c = d;
d = temp;
}
}
else
{
sort2(b, c);
}
}
template <class T>
inline void
insertion_sort(T * a, T * aEnd)
{
T * pp;
for (T * p = a + 1; p < aEnd; p++)
{
T t = *p;
if (t < *a)
{
for (pp = p; pp != a; pp--)
{
*pp = *(pp - 1);
}
*pp = t;
}
else
{
for (pp = p; t < *(pp - 1); pp--)
{
*pp = *(pp - 1);
}
*pp = t;
}
}
}
template <class T>
static void
cleanup(T * b, int_type * bucket, int_type K)
{
T * c = b;
for (int_type i = 0; i < K; i++)
{
T * cEnd = b + bucket[i];
switch (cEnd - c)
{
case 0:
break;
case 1:
break;
case 2:
sort2(c[0], c[1]);
break;
case 3:
sort3(c[0], c[1], c[2]);
break;
case 4:
sort4(c[0], c[1], c[2], c[3]);
break;
case 5:
#if 0
sort5(c[0], c[1], c[2], c[3], c[4]);
break;
#endif
case 6:
case 7:
case 8:
case 9:
case 10:
case 11:
case 12:
case 13:
case 14:
case 15:
case 16:
insertion_sort(c, cEnd);
break;
default:
check_sort_settings();
potentially_parallel::
sort(c, cEnd);
}
c = cEnd;
}
}
template <typename type_key>
void
l1sort(type_key * a,
type_key * aEnd,
type_key * b, int_type * bucket, int_type K, typename type_key::key_type offset, int shift)
{
count(a, aEnd, bucket, K, offset, shift);
exclusive_prefix_sum(bucket, K);
classify(a, aEnd, b, bucket, offset, shift);
cleanup(b, bucket, K);
}
template <typename type, typename type_key, typename key_extractor>
void classify_block(type * begin, type * end, type_key * & out,
int_type * bucket, typename key_extractor::key_type offset, unsigned shift, key_extractor keyobj)
{
assert(shift < (sizeof(typename key_extractor::key_type) * 8 + 1));
for (type * p = begin; p < end; p++, out++)
{
out->ptr = p;
typename key_extractor::key_type key = keyobj(*p);
int_type ibucket = (key - offset) >> shift;
out->key = key;
bucket[ibucket]++;
}
}
template <typename type, typename type_key, typename key_extractor>
void classify_block(type * begin, type * end, type_key * & out, int_type * bucket, typename type::key_type offset, unsigned shift,
const int_type K, key_extractor keyobj)
{
assert(shift < (sizeof(typename type::key_type) * 8 + 1));
for (type * p = begin; p < end; p++, out++)
{
out->ptr = p;
typename type::key_type key = keyobj(*p);
int_type ibucket = (key - offset) >> shift;
out->key = key;
bucket[ibucket]++;
}
STXXL_UNUSED(K);
}
__STXXL_END_NAMESPACE
#endif