pq_helpers.h

Go to the documentation of this file.

/***************************************************************************
 *  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_CONTAINERS_PQ_HELPERS_HEADER
#define STXXL_CONTAINERS_PQ_HELPERS_HEADER

#include <vector>
#include <algorithm>

#include <stxxl/bits/deprecated.h>
#include <stxxl/bits/mng/block_manager.h>
#include <stxxl/bits/mng/typed_block.h>
#include <stxxl/bits/mng/block_alloc.h>
#include <stxxl/bits/mng/read_write_pool.h>
#include <stxxl/bits/mng/prefetch_pool.h>
#include <stxxl/bits/mng/write_pool.h>
#include <stxxl/bits/common/tmeta.h>
#include <stxxl/bits/algo/sort_base.h>
#include <stxxl/bits/parallel.h>
#include <stxxl/bits/common/is_sorted.h>
#include <stxxl/bits/common/error_handling.h>

#if STXXL_PARALLEL

#if defined(STXXL_PARALLEL_MODE) && ((__GNUC__ * 10000 + __GNUC_MINOR__ * 100) < 40400)
#undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
#undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
#undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER
#define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 0
#define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 0
#define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER 0
#endif

// enable/disable parallel merging for certain cases, for performance tuning
#ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
#define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 1
#endif
#ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
#define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 1
#endif
#ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER
#define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER 1
#endif

#endif //STXXL_PARALLEL

#if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL
#define STXXL_PQ_EXTERNAL_LOSER_TREE 0 // no loser tree for the external sequences
#else
#define STXXL_PQ_EXTERNAL_LOSER_TREE 1
#endif

#if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL
#define STXXL_PQ_INTERNAL_LOSER_TREE 0 // no loser tree for the internal sequences
#else
#define STXXL_PQ_INTERNAL_LOSER_TREE 1
#endif

#define STXXL_VERBOSE_PQ(msg) STXXL_VERBOSE2_THIS("priority_queue::" << msg)

STXXL_BEGIN_NAMESPACE

//! \defgroup stlcontinternals internals
//! \ingroup stlcont
//! Supporting internal classes
//! \{

/*! \internal
 */
namespace priority_queue_local {

/*!
 * Similar to std::priority_queue, with the following differences:
 * - Maximum size is fixed at construction time, so an array can be used.
 * - Provides access to underlying heap, so (parallel) sorting in place is possible.
 * - Can be cleared "at once", without reallocation.
 */
template <typename ValueType, typename ContainerType = std::vector<ValueType>,
          typename CompareType = std::less<ValueType> >
class internal_priority_queue
{
public:
    typedef ValueType value_type;
    typedef ContainerType container_type;
    typedef CompareType compare_type;
    typedef typename container_type::reference reference;
    typedef typename container_type::const_reference const_reference;
    typedef typename container_type::size_type size_type;

protected:
    //  See queue::heap for notes on these names.
    container_type heap;
    CompareType comp;
    size_type current_size;

public:
    //! Default constructor creates no elements.
    explicit
    internal_priority_queue(size_type capacity)
        : heap(capacity), current_size(0)
    { }

    //! Returns true if the %queue is empty.
    bool
    empty() const
    { return current_size == 0; }

    //! Returns the number of elements in the %queue.
    size_type
    size() const
    { return current_size; }

    /*!
     * Returns a read-only (constant) reference to the data at the first
     * element of the %queue.
     */
    const_reference
    top() const
    {
        return heap.front();
    }

    /*!
     * Add data to the %queue.
     * \param  x  Data to be added.
     *
     * This is a typical %queue operation.
     * The time complexity of the operation depends on the underlying
     * container.
     */
    void
    push(const value_type& x)
    {
        heap[current_size] = x;
        ++current_size;
        std::push_heap(heap.begin(), heap.begin() + current_size, comp);
    }

    /*!
     * Removes first element.
     *
     * This is a typical %queue operation.  It shrinks the %queue
     * by one.  The time complexity of the operation depends on the
     * underlying container.
     *
     * Note that no data is returned, and if the first element's
     * data is needed, it should be retrieved before pop() is
     * called.
     */
    void
    pop()
    {
        std::pop_heap(heap.begin(), heap.begin() + current_size, comp);
        --current_size;
    }

    //! Sort all contained elements, write result to \c target.
    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);
    }

    //! Remove all contained elements.
    void clear()
    {
        current_size = 0;
    }
};

//! Inverts the order of a comparison functor by swapping its arguments.
template <class Predicate, typename FirstType, typename SecondType>
class invert_order
{
protected:
    Predicate pred;

public:
    explicit
    invert_order(const Predicate& _pred) : pred(_pred) { }

    bool operator () (const FirstType& x, const SecondType& y) const
    {
        return pred(y, x);
    }
};

/*!
 * Similar to std::stack, with the following differences:
 * - Maximum size is fixed at compilation time, so an array can be used.
 * - Can be cleared "at once", without reallocation.
 */
template <typename ValueType, unsigned_type MaxSize>
class internal_bounded_stack
{
    typedef ValueType value_type;
    typedef unsigned_type size_type;
    enum { max_size = MaxSize };

    size_type m_size;
    value_type m_array[max_size];

public:
    internal_bounded_stack() : m_size(0) { }

    void push(const value_type& x)
    {
        assert(m_size < max_size);
        m_array[m_size++] = x;
    }

    const value_type & top() const
    {
        assert(m_size > 0);
        return m_array[m_size - 1];
    }

    void pop()
    {
        assert(m_size > 0);
        --m_size;
    }

    void clear()
    {
        m_size = 0;
    }

    size_type size() const
    {
        return m_size;
    }

    bool empty() const
    {
        return m_size == 0;
    }
};

template <typename Iterator>
class short_sequence : public std::pair<Iterator, Iterator>
{
    typedef std::pair<Iterator, Iterator> pair;

public:
    typedef Iterator iterator;
    typedef const iterator const_iterator;
    typedef typename std::iterator_traits<iterator>::value_type value_type;
    typedef typename std::iterator_traits<iterator>::difference_type size_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef unsigned_type origin_type;

private:
    origin_type m_origin;

public:
    short_sequence(Iterator first, Iterator last, origin_type origin)
        : pair(first, last), m_origin(origin)
    { }

    iterator begin()
    {
        return this->first;
    }

    const_iterator begin() const
    {
        return this->first;
    }

    const_iterator cbegin() const
    {
        return begin();
    }

    iterator end()
    {
        return this->second;
    }

    const_iterator end() const
    {
        return this->second;
    }

    const_iterator cend() const
    {
        return end();
    }

    reference front()
    {
        return *begin();
    }

    const_reference front() const
    {
        return *begin();
    }

    reference back()
    {
        return *(end() - 1);
    }

    const_reference back() const
    {
        return *(end() - 1);
    }

    size_type size() const
    {
        return end() - begin();
    }

    bool empty() const
    {
        return size() == 0;
    }

    origin_type origin() const
    {
        return m_origin;
    }
};

} // namespace priority_queue_local

//! \}

STXXL_END_NAMESPACE

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