http://stxxl.sourceforge.net
<sanders@mpi-sb.mpg.de>
<dementiev@mpi-sb.mpg.de>
<singler@ira.uka.de>
<beckmann@cs.uni-frankfurt.de>
http://www.boost.org/LICENSE_1_0.txt
#ifndef STXXL_PQ_HELPERS_HEADER
#define STXXL_PQ_HELPERS_HEADER
#include <queue>
__STXXL_BEGIN_NAMESPACE
namespace priority_queue_local
{
@brief
template <typename _Tp, typename _Sequence = std::vector<_Tp>,
typename _Compare = std::less<typename _Sequence::value_type> >
class internal_priority_queue
{
typedef typename _Sequence::value_type _Sequence_value_type;
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
_Sequence heap;
_Compare comp;
size_type current_size;
public:
@brief
explicit
internal_priority_queue(size_type capacity)
: heap(capacity), current_size(0)
{ }
bool
empty() const
{ return current_size == 0; }
size_type
size() const
{ return current_size; }
const_reference
top() const
{
return heap.front();
}
@brief
@param
void
push(const value_type & __x)
{
heap[current_size] = __x;
++current_size;
std::push_heap(heap.begin(), heap.begin() + current_size, comp);
}
@brief
void
pop()
{
std::pop_heap(heap.begin(), heap.begin() + current_size, comp);
--current_size;
}
@brief@c
void sort_to(value_type * target)
{
check_sort_settings();
potentially_parallel::
sort(heap.begin(), heap.begin() + current_size, comp);
std::reverse_copy(heap.begin(), heap.begin() + current_size, target);
}
@brief
void clear()
{
current_size = 0;
}
};
@brief
template <class Predicate, typename first_argument_type, typename second_argument_type>
class invert_order
{
protected:
Predicate pred;
public:
explicit
invert_order(const Predicate & _pred) : pred(_pred) { }
bool operator () (const first_argument_type & x, const second_argument_type & y) const
{
return pred(y, x);
}
};
template <typename Tp_, unsigned_type max_size_>
class internal_bounded_stack
{
typedef Tp_ value_type;
typedef unsigned_type size_type;
enum { max_size = max_size_ };
size_type size_;
value_type array[max_size];
public:
internal_bounded_stack() : size_(0) { }
void push(const value_type & x)
{
assert(size_ < max_size);
array[size_++] = x;
}
const value_type & top() const
{
assert(size_ > 0);
return array[size_ - 1];
}
void pop()
{
assert(size_ > 0);
--size_;
}
void clear()
{
size_ = 0;
}
size_type size() const
{
return size_;
}
bool empty() const
{
return size_ == 0;
}
};
}
__STXXL_END_NAMESPACE
#endif