Permalink
Switch branches/tags
Nothing to show
Find file
1ba4e9b Feb 17, 2012
574 lines (503 sloc) 20.2 KB
#ifndef GALGORITHM_H
#define GALGORITHM_H
// Generalized algorithms based on Heap.
//
// Pass -DGHEAP_CPP11 to compiler for enabling C++11 optimization,
// otherwise C++03 optimization will be enabled.
//
// Don't forget passing -DNDEBUG option to the compiler when creating optimized
// builds. This significantly speeds up the code by removing debug assertions.
//
// Author: Aliaksandr Valialkin <valyala@gmail.com>.
#include "gheap.hpp"
#include <cassert> // for assert
#include <cstddef> // for size_t, ptrdiff_t
#include <iterator> // for std::iterator_traits, std::advance()
#include <memory> // for std::*_temporary_buffer()
#include <new> // for std::bad_alloc
#include <utility> // for std::move(), std::swap(), std::*pair
template <class Heap = gheap<> >
class galgorithm
{
private:
// Standard less comparer.
template <class InputIterator>
static bool _std_less_comparer(
const typename std::iterator_traits<InputIterator>::value_type &a,
const typename std::iterator_traits<InputIterator>::value_type &b)
{
return (a < b);
}
// Less comparer for nway_merge().
template <class LessComparer>
class _nway_merge_less_comparer
{
private:
const LessComparer &_less_comparer;
public:
_nway_merge_less_comparer(const LessComparer &less_comparer) :
_less_comparer(less_comparer) {}
template <class InputIterator>
bool operator() (
const std::pair<InputIterator, InputIterator> &input_range_a,
const std::pair<InputIterator, InputIterator> &input_range_b) const
{
assert(input_range_a.first != input_range_a.second);
assert(input_range_b.first != input_range_b.second);
return _less_comparer(*(input_range_b.first), *(input_range_a.first));
}
};
// RAII wrapper around temporary buffer.
// It is used by nway_mergesort() for allocation of temporary memory.
template <class T>
class _temporary_buffer
{
private:
T *_ptr;
public:
_temporary_buffer(const size_t size)
{
const std::pair<T *, ptrdiff_t> tmp_buf =
std::get_temporary_buffer<T>(size);
_ptr = tmp_buf.first;
assert(tmp_buf.second >= 0);
if (_ptr == 0 || (size_t)tmp_buf.second < size) {
// It is OK passing (_ptr == 0) to std::return_temporary_buffer().
std::return_temporary_buffer(_ptr);
throw std::bad_alloc();
}
}
~_temporary_buffer()
{
std::return_temporary_buffer(_ptr);
_ptr = 0;
}
T *get_ptr() const
{
return _ptr;
}
};
// Standard sorter for small ranges.
template <class T, class LessComparer>
static void _std_small_range_sorter(T *const first, T *const last,
const LessComparer &less_comparer)
{
assert(first <= last);
// Insertion sort implementation.
// See http://en.wikipedia.org/wiki/Insertion_sort .
for (T *it = first + 1; it != last; ++it) {
#ifdef GHEAP_CPP11
T tmp = std::move(*it);
T *hole = it;
while (hole != first && less_comparer(tmp, *(hole - 1))) {
*hole = std::move(*(hole - 1));
--hole;
}
*hole = std::move(tmp);
#else
T *hole = it;
while (hole != first && less_comparer(*hole, *(hole - 1))) {
std::swap(*hole, *(hole - 1));
--hole;
}
#endif
}
}
// Moves items from [first ... last) to uninitialized memory pointed
// by result.
template <class InputIterator, class ForwardIterator>
static ForwardIterator _uninitialized_move_items(const InputIterator &first,
const InputIterator &last, const ForwardIterator &result)
{
#ifdef GHEAP_CPP11
// libstdc++ is missing std::uninitialized_move(), so wrap
// the input iterator into std::make_move_iterator().
// See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51981 .
return std::uninitialized_copy(std::make_move_iterator(first),
std::make_move_iterator(last), result);
#else
return std::uninitialized_copy(first, last, result);
#endif
}
// Moves items from [first ... last) to result.
template <class InputIterator, class OutputIterator>
static OutputIterator _move_items(const InputIterator &first,
const InputIterator &last, const OutputIterator &result)
{
#ifdef GHEAP_CPP11
return std::move(first, last, result);
#else
return std::copy(first, last, result);
#endif
}
// Auxiliary function for nway_mergesort().
// Splits the range [first ... last) into subranges with small_range_size size
// each (except the last subrange, which may contain less
// than small_range_size items) and sort each of these subranges using
// small_range_sorter.
template <class RandomAccessIterator, class LessComparer,
class SmallRangeSorter>
static void _sort_subranges(const RandomAccessIterator &first,
const RandomAccessIterator &last, const LessComparer &less_comparer,
const SmallRangeSorter &small_range_sorter,
const size_t small_range_size)
{
assert(first <= last);
assert(small_range_size > 0);
const size_t range_size = last - first;
const RandomAccessIterator it_last = last - range_size % small_range_size;
RandomAccessIterator it = first;
while (it != it_last) {
const RandomAccessIterator it_first = it;
it += small_range_size;
small_range_sorter(it_first, it, less_comparer);
}
// Sort the last subrange, which contains less than small_range_size items.
if (it < last) {
small_range_sorter(it, last, less_comparer);
}
}
// Auxiliary function for nway_mergesort().
// Merges subranges inside each subrange tuple.
// Each subrange tuple contains subranges_count subranges, except the last
// tuple, which may contain less than subranges_count subranges.
// Each subrange contains subrange_size items, except the last subrange,
// which may contain less than subrange_size items.
template <class InputIterator, class OutputIterator, class LessComparer>
static void _merge_subrange_tuples(const InputIterator &first,
const InputIterator &last, const OutputIterator &result,
const LessComparer &less_comparer,
std::pair<InputIterator, InputIterator> *const subranges,
const size_t subranges_count, const size_t subrange_size)
{
assert(first <= last);
assert(subranges_count > 1);
assert(subrange_size > 0);
typedef std::pair<InputIterator, InputIterator> subrange_t;
const size_t range_size = last - first;
InputIterator it = first;
OutputIterator output = result;
// Merge full subrange tuples. Each full subrange tuple contains
// subranges_count full subranges. Each full subrange contains
// subrange_size items.
if (subrange_size <= range_size / subranges_count) {
const size_t tuple_size = subrange_size * subranges_count;
const InputIterator it_last = last - range_size % tuple_size;
while (it != it_last) {
for (size_t i = 0; i < subranges_count; ++i) {
const InputIterator it_first = it;
std::advance(it, subrange_size);
new (subranges + i) subrange_t(it_first, it);
}
output = nway_merge(subranges, subranges + subranges_count, output,
less_comparer);
for (size_t i = 0; i < subranges_count; ++i) {
subranges[i].~subrange_t();
}
}
}
// Merge tail subrange tuple. Tail subrange tuple contains less than
// subranges_count full subranges. It also may contain tail subrange
// with less than subrange_size items.
const size_t tail_tuple_size = last - it;
if (tail_tuple_size > 0) {
const size_t full_subranges_count = tail_tuple_size / subrange_size;
assert(full_subranges_count < subranges_count);
size_t tail_subranges_count = full_subranges_count;
for (size_t i = 0; i < full_subranges_count; ++i) {
const InputIterator it_first = it;
std::advance(it, subrange_size);
new (subranges + i) subrange_t(it_first, it);
}
if (it < last) {
new (subranges + full_subranges_count) subrange_t(it, last);
++tail_subranges_count;
}
nway_merge(subranges, subranges + tail_subranges_count, output,
less_comparer);
for (size_t i = 0; i < tail_subranges_count; ++i) {
subranges[i].~subrange_t();
}
}
}
public:
// Sorts items [first ... middle) in ascending order.
// Uses less_comparer for items' comparison.
//
// std::swap() specialization and/or move constructor/assignment
// may be provided for non-trivial items as a speed optimization.
template <class RandomAccessIterator, class LessComparer>
static void heapsort(const RandomAccessIterator &first,
const RandomAccessIterator &last, const LessComparer &less_comparer)
{
Heap::make_heap(first, last, less_comparer);
Heap::sort_heap(first, last, less_comparer);
}
// Sorts items [first ... middle) in ascending order.
// Uses operator< for items' comparison.
//
// std::swap() specialization and/or move constructor/assignment
// may be provided for non-trivial items as a speed optimization.
template <class RandomAccessIterator>
static void heapsort(const RandomAccessIterator &first,
const RandomAccessIterator &last)
{
heapsort(first, last, _std_less_comparer<RandomAccessIterator>);
}
// Performs partial sort, so [first ... middle) will contain items sorted
// in ascending order, which are smaller than the rest of items
// in the [middle ... last).
// Uses less_comparer for items' comparison.
//
// std::swap() specialization and/or move constructor/assignment
// may be provided for non-trivial items as a speed optimization.
template <class RandomAccessIterator, class LessComparer>
static void partial_sort(const RandomAccessIterator &first,
const RandomAccessIterator &middle, const RandomAccessIterator &last,
const LessComparer &less_comparer)
{
assert(first <= middle);
assert(middle <= last);
typedef typename std::iterator_traits<RandomAccessIterator>::value_type
value_type;
const size_t sorted_range_size = middle - first;
if (sorted_range_size > 0) {
Heap::make_heap(first, middle, less_comparer);
const size_t heap_size = last - first;
for (size_t i = sorted_range_size; i < heap_size; ++i) {
if (less_comparer(first[i], first[0])) {
Heap::swap_max_item(first, middle, first[i], less_comparer);
}
}
Heap::sort_heap(first, middle, less_comparer);
}
}
// Performs partial sort, so [first ... middle) will contain items sorted
// in ascending order, which are smaller than the rest of items
// in the [middle ... last).
// Uses operator< for items' comparison.
//
// std::swap() specialization and/or move constructor/assignment
// may be provided for non-trivial items as a speed optimization.
template <class RandomAccessIterator>
static void partial_sort(const RandomAccessIterator &first,
const RandomAccessIterator &middle, const RandomAccessIterator &last)
{
partial_sort(first, middle, last, _std_less_comparer<RandomAccessIterator>);
}
// Performs N-way merging of the given input ranges into the result sorted
// in ascending order, using less_comparer for items' comparison.
//
// Each input range must hold non-zero number of items sorted
// in ascending order. Each range is defined as a std::pair containing
// input iterators, where the first iterator points to the beginning
// of the range, while the second iterator points to the end of the range.
//
// Returns an iterator pointing to the next element in the result after
// the merge.
//
// std::swap() specialization and/or move constructor/assignment
// may be provided for non-trivial input ranges as a speed optimization.
//
// As a side effect the function shuffles input ranges between
// [input_ranges_first ... input_ranges_last) and sets the first iterator
// for each input range to the end of the corresponding range.
//
// Also values from input ranges may become obsolete after
// the funtion return, because they can be moved to the result via
// move construction or move assignment in C++11.
template <class RandomAccessIterator, class OutputIterator,
class LessComparer>
static OutputIterator nway_merge(
const RandomAccessIterator &input_ranges_first,
const RandomAccessIterator &input_ranges_last,
const OutputIterator &result, const LessComparer &less_comparer)
{
assert(input_ranges_first < input_ranges_last);
typedef typename std::iterator_traits<RandomAccessIterator>::value_type
input_range_iterator;
const RandomAccessIterator &first = input_ranges_first;
RandomAccessIterator last = input_ranges_last;
OutputIterator output = result;
const _nway_merge_less_comparer<LessComparer> less(less_comparer);
Heap::make_heap(first, last, less);
while (true) {
input_range_iterator &input_range = first[0];
assert(input_range.first != input_range.second);
#ifdef GHEAP_CPP11
*output = std::move(*(input_range.first));
#else
*output = *(input_range.first);
#endif
++output;
++(input_range.first);
if (input_range.first == input_range.second) {
--last;
if (first == last) {
break;
}
std::swap(input_range, *last);
}
Heap::restore_heap_after_item_decrease(first, first, last, less);
}
return output;
}
// Performs N-way merging of the given input ranges into the result sorted
// in ascending order, using operator< for items' comparison.
//
// Each input range must hold non-zero number of items sorted
// in ascending order. Each range is defined as a std::pair containing
// input iterators, where the first iterator points to the beginning
// of the range, while the second iterator points to the end of the range.
//
// Returns an iterator pointing to the next element in the result after
// the merge.
//
// std::swap() specialization and/or move constructor/assignment
// may be provided for non-trivial input ranges as a speed optimization.
//
// As a side effect the function shuffles input ranges between
// [input_ranges_first ... input_ranges_last) and sets the first iterator
// for each input range to the end of the corresponding range.
//
// Also values from input ranges may become obsolete after
// the function return, because they can be moved to the result via
// move construction or move assignment in C++11.
template <class RandomAccessIterator, class OutputIterator>
static OutputIterator nway_merge(
const RandomAccessIterator &input_ranges_first,
const RandomAccessIterator &input_ranges_last,
const OutputIterator &result)
{
typedef typename std::iterator_traits<RandomAccessIterator
>::value_type::first_type input_iterator;
return nway_merge(input_ranges_first, input_ranges_last, result,
_std_less_comparer<input_iterator>);
}
// Performs n-way mergesort.
//
// Uses:
// - less_comparer for items' comparison.
// - small_range_sorter for sorting ranges containing no more
// than small_range_size items.
//
// Splits the input range into subranges with small_range_size size,
// sorts them using small_range_sorter and then merges them back
// using n-way merge with n = subranges_count.
//
// items_tmp_buf must point to an uninitialized memory, which can hold
// up to (last - first) items.
//
// May raise std::bad_alloc on unsuccessful attempt to allocate temporary
// space for auxiliary structures required for n-way merging.
template <class ForwardIterator, class LessComparer, class SmallRangeSorter>
static void nway_mergesort(const ForwardIterator &first,
const ForwardIterator &last, const LessComparer &less_comparer,
const SmallRangeSorter &small_range_sorter,
const size_t small_range_size, const size_t subranges_count,
typename std::iterator_traits<ForwardIterator>::value_type
*const items_tmp_buf)
{
assert(first <= last);
assert(small_range_size > 0);
assert(subranges_count > 1);
typedef typename std::iterator_traits<ForwardIterator>::value_type
value_type;
typedef std::pair<ForwardIterator, ForwardIterator> subrange1_t;
typedef std::pair<value_type *, value_type *> subrange2_t;
const size_t range_size = last - first;
// Preparation: Move items to a temporary buffer.
_uninitialized_move_items(first, last, items_tmp_buf);
// Step 1: split the range into subranges with small_range_size size each
// (except the last subrange, which may contain less than small_range_size
// items) and sort each of these subranges using small_range_sorter.
_sort_subranges(items_tmp_buf, items_tmp_buf + range_size,
less_comparer, small_range_sorter, small_range_size);
// Step 2: Merge subranges sorted at the previous step using n-way merge.
const _temporary_buffer<subrange1_t> subranges_tmp_buf1(subranges_count);
const _temporary_buffer<subrange2_t> subranges_tmp_buf2(subranges_count);
size_t subrange_size = small_range_size;
for (;;) {
// First pass: merge items from the temporary buffer
// to the original location.
_merge_subrange_tuples(
items_tmp_buf, items_tmp_buf + range_size, first, less_comparer,
subranges_tmp_buf2.get_ptr(), subranges_count, subrange_size);
if (subrange_size > range_size / subranges_count) {
break;
}
subrange_size *= subranges_count;
// Second pass: merge items from the original location
// to the temporary buffer.
_merge_subrange_tuples(
first, last, items_tmp_buf, less_comparer,
subranges_tmp_buf1.get_ptr(), subranges_count, subrange_size);
if (subrange_size > range_size / subranges_count) {
// Move items from the temporary buffer to the original location.
_move_items(items_tmp_buf, items_tmp_buf + range_size, first);
break;
}
subrange_size *= subranges_count;
}
// Destroy dummy items in the temporary buffer.
for (size_t i = 0; i < range_size; ++i) {
items_tmp_buf[i].~value_type();
}
}
// Performs n-way mergesort.
//
// Uses:
// - less_comparer for items' comparison.
// - small_range_sorter for sorting ranges containing no more
// than small_range_size items.
//
// Splits the input range into subranges with small_range_size size,
// sorts them using small_range_sorter and then merges them back
// using n-way merge with n = subranges_count.
//
// May raise std::bad_alloc on unsuccessful attempt to allocate a temporary
// buffer for (last - first) items.
template <class ForwardIterator, class LessComparer, class SmallRangeSorter>
static void nway_mergesort(const ForwardIterator &first,
const ForwardIterator &last, const LessComparer &less_comparer,
const SmallRangeSorter &small_range_sorter,
const size_t small_range_size = 32, const size_t subranges_count = 15)
{
assert(first <= last);
typedef typename std::iterator_traits<ForwardIterator>::value_type
value_type;
const size_t range_size = last - first;
const _temporary_buffer<value_type> tmp_buf(range_size);
value_type *const items_tmp_buf = tmp_buf.get_ptr();
nway_mergesort(first, last, less_comparer, small_range_sorter,
small_range_size, subranges_count, items_tmp_buf);
}
// Performs n-way mergesort.
//
// Uses less_comparer for items' comparison.
//
// May raise std::bad_alloc on unsuccessful attempt to allocate a temporary
// buffer for (last - first) items.
template <class ForwardIterator, class LessComparer>
static void nway_mergesort(const ForwardIterator &first,
const ForwardIterator &last, const LessComparer &less_comparer)
{
typedef typename std::iterator_traits<ForwardIterator>::value_type
value_type;
nway_mergesort(first, last, less_comparer,
_std_small_range_sorter<value_type, LessComparer>);
}
// Performs n-way mergesort.
//
// Uses operator< for items' comparison.
//
// May raise std::bad_alloc on unsuccessful attempt to allocate a temporary
// buffer for (last - first) items.
template <class ForwardIterator>
static void nway_mergesort(const ForwardIterator &first,
const ForwardIterator &last)
{
nway_mergesort(first, last, _std_less_comparer<ForwardIterator>);
}
};
#endif