13 #ifndef STXXL_ALGO_INTKSORT_HEADER
14 #define STXXL_ALGO_INTKSORT_HEADER
25 template <
typename type_key>
31 std::fill(bucket, bucket + K, 0);
34 for (type_key* p = a; p < aEnd; p++)
36 int_type i = (p->key - offset) >> shift;
63 template <
typename type_key>
65 classify(type_key* a, type_key* aEnd, type_key* b,
int_type* bucket,
typename type_key::key_type offset,
unsigned shift)
67 for (type_key* p = a; p < aEnd; p++)
69 int_type i = (p->key - offset) >> shift;
237 for (T* p = a + 1; p < aEnd; p++)
244 for (pp = p; pp != a; pp--)
253 for (pp = p; t < *(pp - 1); pp--)
272 T* cEnd = b + bucket[i];
283 sort3(c[0], c[1], c[2]);
286 sort4(c[0], c[1], c[2], c[3]);
290 sort5(c[0], c[1], c[2], c[3], c[4]);
321 template <
typename type_key>
325 type_key* b,
int_type* bucket,
int_type K,
typename type_key::key_type offset,
int shift)
327 count(a, aEnd, bucket, K, offset, shift);
329 classify(a, aEnd, b, bucket, offset, shift);
333 template <
typename type,
typename type_key,
typename key_extractor>
335 int_type* bucket,
typename key_extractor::key_type offset,
unsigned shift, key_extractor keyobj)
337 assert(shift < (
sizeof(
typename key_extractor::key_type) * 8 + 1));
338 for (type* p = begin; p < end; p++, out++)
341 typename key_extractor::key_type key = keyobj(*p);
342 int_type ibucket = (key - offset) >> shift;
347 template <
typename type,
typename type_key,
typename key_extractor>
348 void classify_block(type* begin, type* end, type_key*& out,
int_type* bucket,
typename type::key_type offset,
unsigned shift,
349 const int_type K, key_extractor keyobj)
351 assert(shift < (
sizeof(
typename type::key_type) * 8 + 1));
352 for (type* p = begin; p < end; p++, out++)
355 typename type::key_type key = keyobj(*p);
356 int_type ibucket = (key - offset) >> shift;
372 #endif // !STXXL_ALGO_INTKSORT_HEADER
void sort(ExtIterator first, ExtIterator last, StrictWeakOrdering cmp, unsigned_type M)
Sort records comparison-based, see stxxl::sort -- Sorting Comparison-Based.
void sort3(T &a, T &b, T &c)
void insertion_sort(T *a, T *aEnd)
void check_sort_settings()
static void cleanup(T *b, int_type *bucket, int_type K)
choose_int_types< my_pointer_size >::int_type int_type
static void count(type_key *a, type_key *aEnd, int_type *bucket, int_type K, typename type_key::key_type offset, unsigned shift)
#define STXXL_BEGIN_NAMESPACE
void STXXL_UNUSED(const U &)
static void classify(type_key *a, type_key *aEnd, type_key *b, int_type *bucket, typename type_key::key_type offset, unsigned shift)
void sort4(T &a, T &b, T &c, T &d)
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)
static void exclusive_prefix_sum(int_type *bucket, int_type K)
void classify_block(type *begin, type *end, type_key *&out, int_type *bucket, typename key_extractor::key_type offset, unsigned shift, key_extractor keyobj)
void sort5(T &a, T &b, T &c, T &d, T &e)
#define STXXL_END_NAMESPACE