sort/common/merge_block.hpp

//----------------------------------------------------------------------------
/// @file merge_block.hpp
/// @brief This file constains the class merge_block, which is part of the
///        block_indirect_sort algorithm
///
/// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
///         Distributed under the Boost Software License, Version 1.0.\n
///         ( See accompanying file LICENSE_1_0.txt or copy at
///           http://www.boost.org/LICENSE_1_0.txt  )
/// @version 0.1
///
/// @remarks
//-----------------------------------------------------------------------------
#ifndef __BOOST_SORT_COMMON_MERGE_BLOCK_HPP
#define __BOOST_SORT_COMMON_MERGE_BLOCK_HPP

#include <boost/sort/common/range.hpp>
#include <boost/sort/common/rearrange.hpp>
#include <boost/sort/common/util/merge.hpp>
#include <boost/sort/common/util/traits.hpp>

namespace boost
{
namespace sort
{
namespace common
{
///---------------------------------------------------------------------------
/// @struct merge_block
/// @brief This contains all the information shared betwen the classes of the
///        block indirect sort algorithm

//----------------------------------------------------------------------------
template<class Iter_t, class Compare, uint32_t Power2 = 10>
struct merge_block
{
    //-------------------------------------------------------------------------
    //                  D E F I N I T I O N S
    //-------------------------------------------------------------------------
    typedef util::value_iter<Iter_t>                    value_t;
    typedef range<size_t>                               range_pos;
    typedef range<Iter_t>                               range_it;
    typedef range<value_t *>                            range_buf;
    typedef typename std::vector<size_t>::iterator      it_index;
    typedef util::circular_buffer<value_t, Power2 + 1>  circular_t;

    //------------------------------------------------------------------------
    //                          CONSTANTS
    //------------------------------------------------------------------------
    const size_t BLOCK_SIZE = (size_t) 1 << Power2;
    const size_t LOG_BLOCK = Power2;

    //------------------------------------------------------------------------
    //                V A R I A B L E S
    //------------------------------------------------------------------------
    // range with all the element to sort
    range<Iter_t> global_range;

    // index vector of block_pos elements
    std::vector<size_t> index;

    // Number of elements to sort
    size_t nelem;

    // Number of blocks to sort
    size_t nblock;

    // Number of elements in the last block (tail)
    size_t ntail;

    // object for to compare two elements
    Compare cmp;

    // range  of elements of the last block (tail)
    range_it range_tail;

    // circular buffer
    circular_t * ptr_circ;

    // indicate  if the circulr buffer is owned  by the data structure
    // or is received as parameter
    bool owned;

    //
    //------------------------------------------------------------------------
    //                F U N C T I O N S
    //------------------------------------------------------------------------
    //
    //------------------------------------------------------------------------
    //  function : merge_block
    /// @brief constructor of the class
    //
    /// @param first : iterator to the first element of the range to sort
    /// @param last : iterator after the last element to the range to sort
    /// @param comp : object for to compare two elements pointed by Iter_t
    ///               iterators
    //------------------------------------------------------------------------
    merge_block (Iter_t first, Iter_t last, Compare comp,
                 circular_t *pcirc_buffer)
    : global_range(first, last), cmp(comp), ptr_circ(pcirc_buffer),
      owned(pcirc_buffer == nullptr)
    {
        assert((last - first) >= 0);
        if (first == last) return; // nothing to do

        nelem = size_t(last - first);
        nblock = (nelem + BLOCK_SIZE - 1) / BLOCK_SIZE;
        ntail = (nelem % BLOCK_SIZE);
        index.reserve(nblock + 1);

        for (size_t i = 0; i < nblock; ++i)
            index.emplace_back(i);

        range_tail.first = first + ((nblock - 1) << LOG_BLOCK);
        range_tail.last = last;
        if (owned)
        {
            ptr_circ = new circular_t;
            ptr_circ->initialize(*first);
        };
    }

    merge_block(Iter_t first, Iter_t last, Compare comp)
                    : merge_block(first, last, comp, nullptr) { };

    ~ merge_block()
    {
        if (ptr_circ != nullptr and owned)
        {
            delete ptr_circ;
            ptr_circ = nullptr;
        };
    };
    //-------------------------------------------------------------------------
    //  function : get_range
    /// @brief obtain the range in the position pos
    /// @param pos : position of the range
    /// @return range required
    //-------------------------------------------------------------------------
    range_it get_range(size_t pos) const
    {
        Iter_t it1 = global_range.first + (pos << LOG_BLOCK);
        Iter_t it2 = (pos == (nblock - 1)) ?
                        global_range.last : it1 + BLOCK_SIZE;
        return range_it(it1, it2);
    };
    //-------------------------------------------------------------------------
    //  function : get_group_range
    /// @brief obtain the range of the contiguous blocks beginning in the
    //         position pos
    /// @param pos : position of the first range
    /// @param nrange : number of ranges of the group
    /// @return range required
    //-------------------------------------------------------------------------
    range_it get_group_range(size_t pos, size_t nrange) const
    {
        Iter_t it1 = global_range.first + (pos << LOG_BLOCK);

        Iter_t it2 = ((pos + nrange) == nblock)?global_range.last: global_range.first + ((pos + nrange) << LOG_BLOCK);
        //Iter_t it2 = global_range.first + ((pos + nrange) << LOG_BLOCK);
        //if ((pos + nrange) == nblock) it2 = global_range.last;

        return range_it(it1, it2);
    };
    //-------------------------------------------------------------------------
    //  function : is_tail
    /// @brief indicate if a block is the tail
    /// @param pos : position of the block
    /// @return true : taiol  false : not tail
    //-------------------------------------------------------------------------
    bool is_tail(size_t pos) const
    {
        return (pos == (nblock - 1) and ntail != 0);
    };
    //-------------------------------------------------------------------------
    //  function :
    /// @brief
    /// @param
    /// @return
    //-------------------------------------------------------------------------
    void merge_range_pos(it_index itx_first, it_index itx_mid,
                         it_index itx_last);

    //-------------------------------------------------------------------------
    //  function : move_range_pos_backward
    /// @brief Move backward the elements of a range of blocks in a index
    /// @param itx_first : iterator to the position of the first block
    /// @param  itx_last : itertor to the position of the last block
    /// @param  npos : number of positions to move. Must be less than BLOCK_SIZE
    /// @return
    //-------------------------------------------------------------------------
    void move_range_pos_backward(it_index itx_first, it_index itx_last,
                                 size_t npos);

    //-------------------------------------------------------------------------
    //  function : rearrange_with_index
    /// @brief rearrange the blocks with the relative positions of the index
    /// @param
    /// @param
    /// @param
    /// @return
    //-------------------------------------------------------------------------
    void rearrange_with_index(void);

//---------------------------------------------------------------------------
};// end struct merge_block
//---------------------------------------------------------------------------
//
//############################################################################
//                                                                          ##
//           N O N     I N L I N E     F U N C T IO N S                     ##
//                                                                          ##
//############################################################################
//
//-------------------------------------------------------------------------
//  function :
/// @brief
/// @param
/// @return
//-------------------------------------------------------------------------
template<class Iter_t, class Compare, uint32_t Power2>
void merge_block<Iter_t, Compare, Power2>
::merge_range_pos(it_index itx_first, it_index itx_mid,it_index itx_last)
{
    assert((itx_last - itx_mid) >= 0 and (itx_mid - itx_first) >= 0);

    size_t nelemA = (itx_mid - itx_first), nelemB = (itx_last - itx_mid);
    if (nelemA == 0 or nelemB == 0) return;

    //-------------------------------------------------------------------
    // Create two index with the position of the blocks to merge
    //-------------------------------------------------------------------
    std::vector<size_t> indexA, indexB;
    indexA.reserve(nelemA + 1);
    indexB.reserve(nelemB);

    indexA.insert(indexA.begin(), itx_first, itx_mid);
    indexB.insert(indexB.begin(), itx_mid, itx_last);

    it_index itx_out = itx_first;
    it_index itxA = indexA.begin(), itxB = indexB.begin();
    range_it rngA, rngB;
    Iter_t itA = global_range.first, itB = global_range.first;
    bool validA = false, validB = false;

    while (itxA != indexA.end() and itxB != indexB.end())
    {   //----------------------------------------------------------------
        // Load valid ranges from the itxA and ItxB positions
        //----------------------------------------------------------------
        if (not validA)
        {
            rngA = get_range(*itxA);
            itA = rngA.first;
            validA = true;
        };
        if (not validB)
        {
            rngB = get_range(*itxB);
            itB = rngB.first;
            validB = true;
        };
        //----------------------------------------------------------------
        // If don't have merge betweeen the  blocks, pass directly the
        // position of the block to itx_out
        //----------------------------------------------------------------
        if (ptr_circ->size() == 0)
        {
            if (not cmp(*rngB.front(), *rngA.back()))
            {
                *(itx_out++) = *(itxA++);
                validA = false;
                continue;
            };
            if (cmp(*rngB.back(), *rngA.front()))
            {
                if (not is_tail(*itxB))
                    *(itx_out++) = *itxB;
                else ptr_circ->push_move_back(rngB.first, rngB.size());
                ++itxB;
                validB = false;
                continue;
            };
        };
        //----------------------------------------------------------------
        // Normal merge
        //----------------------------------------------------------------
        bool side = util::merge_circular(itA, rngA.last, itB, rngB.last,
                        *ptr_circ, cmp, itA, itB);
        if (side)
        {   // rngA is finished
            ptr_circ->pop_move_front(rngA.first, rngA.size());
            *(itx_out++) = *(itxA++);
            validA = false;
        }
        else
        {   // rngB is finished
            if (not is_tail(*itxB))
            {
                ptr_circ->pop_move_front(rngB.first, rngB.size());
                *(itx_out++) = *itxB;
            };
            ++itxB;
            validB = false;
        };
    }; // end while

    if (itxA == indexA.end())
    {   // the index A is finished
        rngB = get_range(*itxB);
        ptr_circ->pop_move_front(rngB.first, ptr_circ->size());
        while (itxB != indexB.end())
            *(itx_out++) = *(itxB++);
    }
    else
    {   // The list B is finished
        rngA = get_range(*itxA);
        if (ntail != 0 and indexB.back() == (nblock - 1)) // exist tail
        {   // add the tail block to indexA, and shift the element
            indexA.push_back(indexB.back());
            size_t numA = size_t(itA - rngA.first);
            ptr_circ->pop_move_back(rngA.first, numA);
            move_range_pos_backward(itxA, indexA.end(), ntail);
        };

        ptr_circ->pop_move_front(rngA.first, ptr_circ->size());
        while (itxA != indexA.end())
            *(itx_out++) = *(itxA++);
    };
};

//-------------------------------------------------------------------------
//  function : move_range_pos_backward
/// @brief Move backward the elements of a range of blocks in a index
/// @param itx_first : iterator to the position of the first block
/// @param  itx_last : itertor to the position of the last block
/// @param  npos : number of positions to move. Must be less than BLOCK_SIZE
/// @return
//-------------------------------------------------------------------------
template<class Iter_t, class Compare, uint32_t Power2>
void merge_block<Iter_t, Compare, Power2>
::move_range_pos_backward(it_index itx_first, it_index itx_last, size_t npos)
{
    assert((itx_last - itx_first) >= 0 and npos <= BLOCK_SIZE);

    //--------------------------------------------------------------------
    // Processing the last block. Must be ready fore to accept npos
    // elements from the upper block
    //--------------------------------------------------------------------
    range_it rng1 = get_range(*(itx_last - 1));
    assert(rng1.size() >= npos);
    if (rng1.size() > npos)
    {
        size_t nmove = rng1.size() - npos;
        util::move_backward(rng1.last, rng1.first, rng1.first + nmove);
    };
    //--------------------------------------------------------------------
    // Movement of elements between blocks
    //--------------------------------------------------------------------
    for (it_index itx = itx_last - 1; itx != itx_first;)
    {
        --itx;
        range_it rng2 = rng1;
        rng1 = get_range(*itx);
        Iter_t it_mid1 = rng1.last - npos, it_mid2 = rng2.first + npos;
        util::move_backward(it_mid2, it_mid1, rng1.last);
        util::move_backward(rng1.last, rng1.first, it_mid1);
    };
};
//-------------------------------------------------------------------------
//  function : rearrange_with_index
/// @brief rearrange the blocks with the relative positions of the index
/// @param
/// @param
/// @param
/// @return
//-------------------------------------------------------------------------
template<class Iter_t, class Compare, uint32_t Power2>
void merge_block<Iter_t, Compare, Power2>
::rearrange_with_index(void)
{   //--------------------------------------------------------------------
    //                     Code
    //--------------------------------------------------------------------
    size_t pos_dest, pos_src, pos_ini;
    size_t nelem = index.size();

    ptr_circ->clear();
    value_t * aux = ptr_circ->get_buffer();
    range_buf rng_buf(aux, aux + ptr_circ->NMAX);

    pos_ini = 0;
    while (pos_ini < nelem)
    {
        while (pos_ini < nelem and index[pos_ini] == pos_ini)
            ++pos_ini;
        if (pos_ini == nelem) return;
        pos_dest = pos_src = pos_ini;
        rng_buf = move_forward(rng_buf, get_range(pos_ini));
        pos_src = index[pos_ini];

        while (pos_src != pos_ini)
        {
            move_forward(get_range(pos_dest), get_range(pos_src));
            index[pos_dest] = pos_dest;
            pos_dest = pos_src;
            pos_src = index[pos_src];
        };
        move_forward(get_range(pos_dest), rng_buf);
        index[pos_dest] = pos_dest;
        ++pos_ini;
    };
};

//****************************************************************************
};//    End namespace common
};//    End namespace sort
};//    End namespace boost
//****************************************************************************
#endif