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)
        {
            std::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