intksort.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/algo/intksort.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2002 Peter Sanders <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_ALGO_INTKSORT_HEADER
#define STXXL_ALGO_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 TypeKey>
static void
count(TypeKey* a, TypeKey* aEnd, int_type* bucket, int_type K,
 typename TypeKey::key_type offset, unsigned shift)
{
 // reset buckets
 std::fill(bucket, bucket + K, 0);

 // count occupancies
 for (TypeKey* p = a; p < aEnd; p++)
 {
 int_type i = (int_type)((p->key - offset) >> shift);
 /*
 if (!(i < K && i >= 0))
 {
 STXXL_ERRMSG("i: " << i);
 abort();
 }
 */
 bucket[i]++;
 }
}

static inline 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;
 }
}

// distribute input a to output b using bucket for the starting indices
template <typename TypeKey>
static void
classify(TypeKey* a, TypeKey* aEnd, TypeKey* b, int_type* bucket,
 typename TypeKey::key_type offset, unsigned shift)
{
 for (TypeKey* p = a; p < aEnd; p++)
 {
 int_type i = (int_type)((p->key - offset) >> shift);
 int_type bi = bucket[i];
 b[bi] = *p;
 bucket[i] = bi + 1;
 }
}

template <class Type>
inline void
sort2(Type& a, Type& b)
{
 if (b < a)
 std::swap(a, b);
}

template <class Type>
inline void
sort3(Type& a, Type& b, Type& c)
{
 Type temp;
 if (b < a)
 {
 if (c < a)
 { // b , c < a
 if (b < c)
 { // b < c < a
 temp = a;
 a = b;
 b = c;
 c = temp;
 }
 else
 { // c <=b < a
 std::swap(c, a);
 }
 }
 else
 { // b < a <=c
 std::swap(a, b);
 }
 }
 else
 { // a <=b
 if (c < a)
 { // c < a <=b
 temp = a;
 a = c;
 c = b;
 b = temp;
 }
 else
 { // a <=b , c
 if (c < b)
 { // a <=c < b
 std::swap(b, c);
 }
 }
 }
 // Assert1 (!(b < a) && !(c < b));
}

template <class Type>
inline void
sort4(Type& a, Type& b, Type& c, Type& d)
{
 sort2(a, b);
 sort2(c, d); // a < b ; c < d
 if (c < a)
 { // c minimal, a < b
 if (d < a)
 { // c < d < a < b
 std::swap(a, c);
 std::swap(b, d);
 }
 else
 { // c < a < {db}
 if (d < b)
 { // c < a < d < b
 Type temp = a;
 a = c;
 c = d;
 d = b;
 b = temp;
 }
 else
 { // c < a < b < d
 Type temp = a;
 a = c;
 c = b;
 b = temp;
 }
 }
 }
 else
 { // a minimal ; c < d
 if (c < b)
 { // c < (bd)
 if (d < b)
 { // c < d < b
 Type temp = b;
 b = c;
 c = d;
 d = temp;
 }
 else
 { // a < c < b < d
 std::swap(b, c);
 }
 } // else sorted
 }
 //Assert1 (!(b < a) && !(c < b) & !(d < c));
}

template <class Type>
inline void
sort5(Type& a, Type& b, Type& c, Type& d, Type& e)
{
 sort2(a, b);
 sort2(d, e);
 if (d < a)
 {
 std::swap(a, d);
 std::swap(b, e);
 } // a < d < e, a < b
 if (d < c)
 {
 std::swap(c, d); // a minimal, c < {de}
 sort2(d, e);
 }
 else
 { // a<b, a<d<e, c<d<e
 sort2(a, c);
 } // a min, c < d < e
 // insert b int cde by binary search
 if (d < b)
 { // c < d < {be}
 if (e < b)
 { // c < d < e < b
 Type temp = b;
 b = c;
 c = d;
 d = e;
 e = temp;
 }
 else
 { // c < d < b < e
 Type temp = b;
 b = c;
 c = d;
 d = temp;
 }
 }
 else
 { // {cb} <=d < e
 sort2(b, c);
 }
 //Assert1 (!(b < a) && !(c < b) & !(d < c) & !(e < d));
}

template <class Type>
inline void
insertion_sort(Type* a, Type* aEnd)
{
 Type* pp;
 for (Type* p = a + 1; p < aEnd; p++)
 {
 // Invariant a..p-1 is sorted;
 Type t = *p;
 if (t < *a)
 { // new minimum
 // move stuff to the right
 for (pp = p; pp != a; pp--)
 {
 *pp = *(pp - 1);
 }
 *pp = t;
 }
 else
 {
 // now we can use *a as a sentinel
 for (pp = p; t < *(pp - 1); pp--)
 {
 *pp = *(pp - 1);
 }
 *pp = t;
 }
 }
}

// sort each bucket
// bucket[i] is an index one off to the right from
// the end of the i-th bucket
template <class Type>
static void
cleanup(Type* b, int_type* bucket, int_type K)
{
 Type* c = b;
 for (int_type i = 0; i < K; i++)
 {
 Type* 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;
 }
}

// do a single level MDS radix sort
// using bucket[0..K-1] as a counter array
// and using (key(x) - offset) >> shift to index buckets.
// and using (key(x) - offset) >> shift to index buckets.
// the input comes from a..aEnd-1
// the output goes to b
template <typename TypeKey>
void
l1sort(TypeKey* a,
 TypeKey* aEnd,
 TypeKey* b, int_type* bucket, int_type K,
 typename TypeKey::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 TypeKey, typename KeyExtractor>
void classify_block(Type* begin, Type* end, TypeKey*& out,
 int_type* bucket, typename KeyExtractor::key_type offset, unsigned shift, KeyExtractor keyobj)
{
 assert(shift < (sizeof(typename KeyExtractor::key_type) * 8 + 1));
 for (Type* p = begin; p < end; p++, out++) // count & create references
 {
 out->ptr = p;
 typename KeyExtractor::key_type key = keyobj(*p);
 int_type ibucket = (int_type)((key - offset) >> shift);
 out->key = key;
 bucket[ibucket]++;
 }
}
template <typename Type, typename TypeKey, typename KeyExtractor>
void classify_block(Type* begin, Type* end, TypeKey*& out, int_type* bucket, typename Type::key_type offset, unsigned shift,
 const int_type K, KeyExtractor keyobj)
{
 assert(shift < (sizeof(typename Type::key_type) * 8 + 1));
 for (Type* p = begin; p < end; p++, out++) // count & create references
 {
 out->ptr = p;
 typename Type::key_type key = keyobj(*p);
 int_type ibucket = (key - offset) >> shift;
 /*
 if (!(ibucket < K && ibucket >= 0))
 {
 STXXL_ERRMSG("ibucket: " << ibucket << " K:" << K);
 abort();
 }
 */
 out->key = key;
 bucket[ibucket]++;
 }
 STXXL_UNUSED(K);
}

STXXL_END_NAMESPACE

#endif // !STXXL_ALGO_INTKSORT_HEADER