http://stxxl.sourceforge.net
<dementiev@mpi-sb.mpg.de>
<beckmann@cs.uni-frankfurt.de>
http://www.boost.org/LICENSE_1_0.txt
#ifndef STXXL_SORT_HELPER_HEADER
#define STXXL_SORT_HELPER_HEADER
#include <algorithm>
#include <functional>
#include <stxxl/bits/algo/run_cursor.h>
#include <stxxl/bits/verbose.h>
__STXXL_BEGIN_NAMESPACE
namespace sort_helper
{
template <typename StrictWeakOrdering>
inline void verify_sentinel_strict_weak_ordering(StrictWeakOrdering cmp)
{
assert(!cmp(cmp.min_value(), cmp.min_value()));
assert(cmp(cmp.min_value(), cmp.max_value()));
assert(!cmp(cmp.max_value(), cmp.min_value()));
assert(!cmp(cmp.max_value(), cmp.max_value()));
STXXL_UNUSED(cmp);
}
template <typename BlockTp_, typename ValTp_ = typename BlockTp_::value_type>
struct trigger_entry
{
typedef BlockTp_ block_type;
typedef typename block_type::bid_type bid_type;
typedef ValTp_ value_type;
bid_type bid;
value_type value;
operator bid_type ()
{
return bid;
}
};
template <typename TriggerEntryTp_, typename ValueCmp_>
struct trigger_entry_cmp : public std::binary_function<TriggerEntryTp_, TriggerEntryTp_, bool>
{
typedef TriggerEntryTp_ trigger_entry_type;
ValueCmp_ cmp;
trigger_entry_cmp(ValueCmp_ c) : cmp(c) { }
trigger_entry_cmp(const trigger_entry_cmp & a) : cmp(a.cmp) { }
bool operator () (const trigger_entry_type & a, const trigger_entry_type & b) const
{
return cmp(a.value, b.value);
}
};
template <typename block_type,
typename prefetcher_type,
typename value_cmp>
struct run_cursor2_cmp : public std::binary_function<run_cursor2<block_type, prefetcher_type>, run_cursor2<block_type, prefetcher_type>, bool>
{
typedef run_cursor2<block_type, prefetcher_type> cursor_type;
value_cmp cmp;
run_cursor2_cmp(value_cmp c) : cmp(c) { }
run_cursor2_cmp(const run_cursor2_cmp & a) : cmp(a.cmp) { }
inline bool operator () (const cursor_type & a, const cursor_type & b) const
{
if (UNLIKELY(b.empty()))
return true;
if (UNLIKELY(a.empty()))
return false;
return (cmp(a.current(), b.current()));
}
};
template <typename SequenceVector, typename ValueType, typename Comparator>
inline
unsigned_type count_elements_less_equal(const SequenceVector & seqs, const ValueType & bound, Comparator cmp)
{
typedef typename SequenceVector::size_type seqs_size_type;
typedef typename SequenceVector::value_type::first_type iterator;
unsigned_type count = 0;
for (seqs_size_type i = 0; i < seqs.size(); ++i)
{
iterator position = std::upper_bound(seqs[i].first, seqs[i].second, bound, cmp);
STXXL_VERBOSE1("less equal than " << position - seqs[i].first);
count += position - seqs[i].first;
}
STXXL_VERBOSE1("finished loop");
return count;
}
template <typename SequenceVector, typename BufferPtrVector, typename Prefetcher>
inline
void refill_or_remove_empty_sequences(SequenceVector & seqs,
BufferPtrVector & buffers,
Prefetcher & prefetcher)
{
typedef typename SequenceVector::size_type seqs_size_type;
for (seqs_size_type i = 0; i < seqs.size(); ++i)
{
if (seqs[i].first == seqs[i].second)
{
if (prefetcher.block_consumed(buffers[i]))
{
seqs[i].first = buffers[i]->begin();
seqs[i].second = buffers[i]->end();
STXXL_VERBOSE1("block ran empty " << i);
}
else
{
seqs.erase(seqs.begin() + i);
buffers.erase(buffers.begin() + i);
STXXL_VERBOSE1("seq removed " << i);
--i;
}
}
}
}
}
__STXXL_END_NAMESPACE
#endif