pq_helpers.h

/***************************************************************************
 * include/stxxl/bits/containers/pq_helpers.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 1999 Peter Sanders <[email protected]>
 * Copyright (C) 2003, 2004, 2007 Roman Dementiev <[email protected]>
 * Copyright (C) 2007, 2009 Johannes Singler <[email protected]>
 * Copyright (C) 2007, 2008 Andreas Beckmann <[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_PQ_HELPERS_HEADER
#define STXXL_PQ_HELPERS_HEADER

#include <queue>

__STXXL_BEGIN_NAMESPACE


namespace priority_queue_local
{
 template <typename _Tp, typename _Sequence = std::vector<_Tp>,
 typename _Compare = std::less<typename _Sequence::value_type> >
 class internal_priority_queue
 {
 // concept requirements
 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:
 // See queue::heap for notes on these names.
 _Sequence heap;
 _Compare comp;
 size_type current_size;

 public:
 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();
 }

 void
 push(const value_type & __x)
 {
 heap[current_size] = __x;
 ++current_size;
 std::push_heap(heap.begin(), heap.begin() + current_size, comp);
 }

 void
 pop()
 {
 std::pop_heap(heap.begin(), heap.begin() + current_size, comp);
 --current_size;
 }

 void sort_to(value_type * target)
 {
 potentially_parallel::
 sort(heap.begin(), heap.begin() + current_size, comp);
 std::reverse_copy(heap.begin(), heap.begin() + current_size, target);
 }

 void clear()
 {
 current_size = 0;
 }
 };

 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;
 }
 };
} //priority_queue_local


__STXXL_END_NAMESPACE

#endif // !STXXL_PQ_HELPERS_HEADER
// vim: et:ts=4:sw=4