include/stxxl/bits/containers/sorter.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/containers/sorter.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2012 Timo Bingmann <bingmann@kit.edu>
 *
 *  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_SORTER_HEADER
#define STXXL_SORTER_HEADER

#include <stxxl/bits/deprecated.h>
#include <stxxl/bits/stream/sort_stream.h>

__STXXL_BEGIN_NAMESPACE

#ifndef STXXL_VERBOSE_SORTER
#define STXXL_VERBOSE_SORTER STXXL_VERBOSE2
#endif

//! \addtogroup stlcont
//! \{

/**
 * \brief External Sorter: use stream package objects to keep a sorted container.
 *
 * This sorter container combines the two functions of runs_creator and
 * runs_merger from the stream packages into a two-phase container.
 *
 * In the first phase the container is filled with unordered items via push(),
 * which are presorted internally into runs of size M. When the internal memory
 * overflows a runs is written to external memory in blocks of block_size.
 * 
 * When sort() is called the container enters the output phase and push() is
 * disallowed. After calling sort() the items can be read in sorted order using
 * operator*() to get the top item, operator++() to advance to the next one and
 * empty() to check for end of stream. This is exactly the stream interface.
 *
 * In the output phase the sorter can be returned to the beginning of the
 * stream using rewind() and everything is read again in sorted order.
 *
 * Using clear() the object can be reset into input state and all items are
 * destroyed.
 *
 * \tparam ValueType   type of the contained objects (POD with no references to internal memory)
 * \tparam CompareType type of comparison object used for sorting the runs
 * \tparam BlockSize   size of the external memory block in bytes, default is \c STXXL_DEFAULT_BLOCK_SIZE(ValTp)
 * \tparam AllocStr    parallel disk allocation strategy, default is \c STXXL_DEFAULT_ALLOC_STRATEGY
 */
template <typename ValueType,
          typename CompareType,
          unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
          class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
class sorter : private noncopyable
{
public:
    // *** Template Parameters

    typedef ValueType value_type;
    typedef CompareType cmp_type;
    enum {
        block_size = BlockSize
    };
    typedef AllocStrategy alloc_strategy_type;

    // *** Constructed Types

    /// runs creator type with push() method
    typedef stream::runs_creator< stream::use_push<ValueType>, cmp_type,
                                  block_size, alloc_strategy_type > runs_creator_type;

    /// corresponding runs merger type
    typedef stream::runs_merger< typename runs_creator_type::sorted_runs_type,
                                 cmp_type, alloc_strategy_type > runs_merger_type;

protected:

    // *** Object Attributes

    /// current state of sorter
    enum { STATE_INPUT, STATE_OUTPUT } m_state;

    // runs creator object holding all items
    runs_creator_type   m_runs_creator;

    // runs merger reading items when in STATE_OUTPUT
    runs_merger_type    m_runs_merger;

public:

    //! Constructor allocation memory_to_use bytes in ram for sorted runs.
    sorter(const cmp_type& cmp, unsigned_type memory_to_use)
        : m_state(STATE_INPUT), 
          m_runs_creator(cmp, memory_to_use),
          m_runs_merger(cmp, memory_to_use)
    {
    }

    // Constructor variant with differently sizes runs_creator and runs_merger
    sorter(const cmp_type& cmp, unsigned_type creator_memory_to_use, unsigned_type merger_memory_to_use)
        : m_state(STATE_INPUT), 
          m_runs_creator(cmp, creator_memory_to_use),
          m_runs_merger(cmp, merger_memory_to_use)
    {
    }

    //! Remove all items and return to input state.
    void clear()
    {
        if ( m_state == STATE_OUTPUT )
            m_runs_merger.deallocate();

        m_runs_creator.allocate();
        m_state = STATE_INPUT;
    }

    //! Push another item (only callable during input state).
    void push(const value_type & val)
    {
        assert( m_state == STATE_INPUT );
        m_runs_creator.push(val);
    }
    
    //! Finish push input state and deallocate input buffer.
    void finish()
    {
        if (m_state == STATE_OUTPUT)
        {
            m_runs_merger.deallocate();
        }

        m_runs_creator.deallocate();
    }

    //! Deallocate buffers and clear result.
    void finish_clear()
    {
        if (m_state == STATE_OUTPUT)
        {
            m_runs_merger.deallocate();
            m_runs_creator.result()->clear();
        }

        m_runs_creator.deallocate();
    }

    //! Number of items pushed or items remaining to be read.
    unsigned_type size() const
    {
        if ( m_state == STATE_INPUT )
            return m_runs_creator.size();
        else
            return m_runs_merger.size();
    }

    //! Switch to output state, rewind() in case the output was already sorted.
    void sort()
    {
        if (m_state == STATE_OUTPUT)
        {
            m_runs_merger.deallocate();
        }

        m_runs_creator.deallocate();
        m_runs_merger.initialize(m_runs_creator.result());
        m_state = STATE_OUTPUT;
    }

    //! Switch to output state, rewind() in case the output was already sorted.
    void sort(unsigned_type merger_memory_to_use)
    {
        m_runs_merger.set_memory_to_use(merger_memory_to_use);
        sort();
    }

    //! Switch to output state, rewind() in case the output was already sorted.
    void sort_reuse()
    {
        assert( m_state == STATE_INPUT );

        m_runs_merger.initialize(m_runs_creator.result());
        m_state = STATE_OUTPUT;
    }

    //! Rewind output stream to beginning.
    void rewind()
    {
        assert( m_state == STATE_OUTPUT );

        m_runs_merger.deallocate();

        m_state = STATE_INPUT;
        return sort();
    }

    //! Change runs_creator memory usage
    void set_creator_memory_to_use(unsigned_type creator_memory_to_use)
    {
        m_runs_creator.set_memory_to_use(creator_memory_to_use);
    }

    //! Change runs_merger memory usage
    void set_merger_memory_to_use(unsigned_type merger_memory_to_use)
    {
        m_runs_merger.set_memory_to_use(merger_memory_to_use);
    }

    //! \brief Standard stream method
    bool empty() const
    {
        assert( m_state == STATE_OUTPUT );
        return m_runs_merger.empty();
    }

    //! \brief Standard stream method
    const value_type& operator * () const
    {
        assert( m_state == STATE_OUTPUT );
        return *m_runs_merger;
    }

    //! \brief Standard stream method
    const value_type* operator -> () const
    {
        return &(operator * ());
    }

    //! \brief Standard stream method (preincrement operator)
    sorter& operator ++ ()
    {
        assert( m_state == STATE_OUTPUT );
        ++m_runs_merger;
        return *this;
    }
};

//! \}

__STXXL_END_NAMESPACE

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