//----------------------------------------------------------------------------
/// @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 <ciso646>
#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