sort/common/merge_block.hpp

0001 //----------------------------------------------------------------------------
0002 /// @file merge_block.hpp
0003 /// @brief This file constains the class merge_block, which is part of the
0004 ///        block_indirect_sort algorithm
0005 ///
0006 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
0007 ///         Distributed under the Boost Software License, Version 1.0.\n
0008 ///         ( See accompanying file LICENSE_1_0.txt or copy at
0009 ///           http://www.boost.org/LICENSE_1_0.txt  )
0010 /// @version 0.1
0011 ///
0012 /// @remarks
0013 //-----------------------------------------------------------------------------
0014 #ifndef __BOOST_SORT_COMMON_MERGE_BLOCK_HPP
0015 #define __BOOST_SORT_COMMON_MERGE_BLOCK_HPP
0016
0017 #include <boost/sort/common/range.hpp>
0018 #include <boost/sort/common/rearrange.hpp>
0019 #include <boost/sort/common/util/merge.hpp>
0020 #include <boost/sort/common/util/traits.hpp>
0021
0022 namespace boost
0023 {
0024 namespace sort
0025 {
0026 namespace common
0027 {
0028 ///---------------------------------------------------------------------------
0029 /// @struct merge_block
0030 /// @brief This contains all the information shared betwen the classes of the
0031 ///        block indirect sort algorithm
0032
0033 //----------------------------------------------------------------------------
0034 template<class Iter_t, class Compare, uint32_t Power2 = 10>
0035 struct merge_block
0036 {
0037     //-------------------------------------------------------------------------
0038     //                  D E F I N I T I O N S
0039     //-------------------------------------------------------------------------
0040     typedef util::value_iter<Iter_t>                    value_t;
0041     typedef range<size_t>                               range_pos;
0042     typedef range<Iter_t>                               range_it;
0043     typedef range<value_t *>                            range_buf;
0044     typedef typename std::vector<size_t>::iterator      it_index;
0045     typedef util::circular_buffer<value_t, Power2 + 1>  circular_t;
0046
0047     //------------------------------------------------------------------------
0048     //                          CONSTANTS
0049     //------------------------------------------------------------------------
0050     const size_t BLOCK_SIZE = (size_t) 1 << Power2;
0051     const size_t LOG_BLOCK = Power2;
0052
0053     //------------------------------------------------------------------------
0054     //                V A R I A B L E S
0055     //------------------------------------------------------------------------
0056     // range with all the element to sort
0057     range<Iter_t> global_range;
0058
0059     // index vector of block_pos elements
0060     std::vector<size_t> index;
0061
0062     // Number of elements to sort
0063     size_t nelem;
0064
0065     // Number of blocks to sort
0066     size_t nblock;
0067
0068     // Number of elements in the last block (tail)
0069     size_t ntail;
0070
0071     // object for to compare two elements
0072     Compare cmp;
0073
0074     // range  of elements of the last block (tail)
0075     range_it range_tail;
0076
0077     // circular buffer
0078     circular_t * ptr_circ;
0079
0080     // indicate  if the circulr buffer is owned  by the data structure
0081     // or is received as parameter
0082     bool owned;
0083
0084     //
0085     //------------------------------------------------------------------------
0086     //                F U N C T I O N S
0087     //------------------------------------------------------------------------
0088     //
0089     //------------------------------------------------------------------------
0090     //  function : merge_block
0091     /// @brief constructor of the class
0092     //
0093     /// @param first : iterator to the first element of the range to sort
0094     /// @param last : iterator after the last element to the range to sort
0095     /// @param comp : object for to compare two elements pointed by Iter_t
0096     ///               iterators
0097     //------------------------------------------------------------------------
0098     merge_block (Iter_t first, Iter_t last, Compare comp,
0099                  circular_t *pcirc_buffer)
0100     : global_range(first, last), cmp(comp), ptr_circ(pcirc_buffer),
0101       owned(pcirc_buffer == nullptr)
0102     {
0103         assert((last - first) >= 0);
0104         if (first == last) return; // nothing to do
0105
0106         nelem = size_t(last - first);
0107         nblock = (nelem + BLOCK_SIZE - 1) / BLOCK_SIZE;
0108         ntail = (nelem % BLOCK_SIZE);
0109         index.reserve(nblock + 1);
0110
0111         for (size_t i = 0; i < nblock; ++i)
0112             index.emplace_back(i);
0113
0114         range_tail.first = first + ((nblock - 1) << LOG_BLOCK);
0115         range_tail.last = last;
0116         if (owned)
0117         {
0118             ptr_circ = new circular_t;
0119             ptr_circ->initialize(*first);
0120         };
0121     }
0122
0123     merge_block(Iter_t first, Iter_t last, Compare comp)
0124                     : merge_block(first, last, comp, nullptr) { };
0125
0126     ~ merge_block()
0127     {
0128         if (ptr_circ != nullptr && owned)
0129         {
0130             delete ptr_circ;
0131             ptr_circ = nullptr;
0132         };
0133     };
0134     //-------------------------------------------------------------------------
0135     //  function : get_range
0136     /// @brief obtain the range in the position pos
0137     /// @param pos : position of the range
0138     /// @return range required
0139     //-------------------------------------------------------------------------
0140     range_it get_range(size_t pos) const
0141     {
0142         Iter_t it1 = global_range.first + (pos << LOG_BLOCK);
0143         Iter_t it2 = (pos == (nblock - 1)) ?
0144                         global_range.last : it1 + BLOCK_SIZE;
0145         return range_it(it1, it2);
0146     };
0147     //-------------------------------------------------------------------------
0148     //  function : get_group_range
0149     /// @brief obtain the range of the contiguous blocks beginning in the
0150     //         position pos
0151     /// @param pos : position of the first range
0152     /// @param nrange : number of ranges of the group
0153     /// @return range required
0154     //-------------------------------------------------------------------------
0155     range_it get_group_range(size_t pos, size_t nrange) const
0156     {
0157         Iter_t it1 = global_range.first + (pos << LOG_BLOCK);
0158
0159         Iter_t it2 = ((pos + nrange) == nblock)?global_range.last: global_range.first + ((pos + nrange) << LOG_BLOCK);
0160         //Iter_t it2 = global_range.first + ((pos + nrange) << LOG_BLOCK);
0161         //if ((pos + nrange) == nblock) it2 = global_range.last;
0162
0163         return range_it(it1, it2);
0164     };
0165     //-------------------------------------------------------------------------
0166     //  function : is_tail
0167     /// @brief indicate if a block is the tail
0168     /// @param pos : position of the block
0169     /// @return true : taiol  false : not tail
0170     //-------------------------------------------------------------------------
0171     bool is_tail(size_t pos) const
0172     {
0173         return (pos == (nblock - 1) && ntail != 0);
0174     };
0175     //-------------------------------------------------------------------------
0176     //  function :
0177     /// @brief
0178     /// @param
0179     /// @return
0180     //-------------------------------------------------------------------------
0181     void merge_range_pos(it_index itx_first, it_index itx_mid,
0182                          it_index itx_last);
0183
0184     //-------------------------------------------------------------------------
0185     //  function : move_range_pos_backward
0186     /// @brief Move backward the elements of a range of blocks in a index
0187     /// @param itx_first : iterator to the position of the first block
0188     /// @param  itx_last : itertor to the position of the last block
0189     /// @param  npos : number of positions to move. Must be less than BLOCK_SIZE
0190     /// @return
0191     //-------------------------------------------------------------------------
0192     void move_range_pos_backward(it_index itx_first, it_index itx_last,
0193                                  size_t npos);
0194
0195     //-------------------------------------------------------------------------
0196     //  function : rearrange_with_index
0197     /// @brief rearrange the blocks with the relative positions of the index
0198     /// @param
0199     /// @param
0200     /// @param
0201     /// @return
0202     //-------------------------------------------------------------------------
0203     void rearrange_with_index(void);
0204
0205 //---------------------------------------------------------------------------
0206 };// end struct merge_block
0207 //---------------------------------------------------------------------------
0208 //
0209 //############################################################################
0210 //                                                                          ##
0211 //           N O N     I N L I N E     F U N C T IO N S                     ##
0212 //                                                                          ##
0213 //############################################################################
0214 //
0215 //-------------------------------------------------------------------------
0216 //  function :
0217 /// @brief
0218 /// @param
0219 /// @return
0220 //-------------------------------------------------------------------------
0221 template<class Iter_t, class Compare, uint32_t Power2>
0222 void merge_block<Iter_t, Compare, Power2>
0223 ::merge_range_pos(it_index itx_first, it_index itx_mid,it_index itx_last)
0224 {
0225     assert((itx_last - itx_mid) >= 0 && (itx_mid - itx_first) >= 0);
0226
0227     size_t nelemA = (itx_mid - itx_first), nelemB = (itx_last - itx_mid);
0228     if (nelemA == 0 || nelemB == 0) return;
0229
0230     //-------------------------------------------------------------------
0231     // Create two index with the position of the blocks to merge
0232     //-------------------------------------------------------------------
0233     std::vector<size_t> indexA, indexB;
0234     indexA.reserve(nelemA + 1);
0235     indexB.reserve(nelemB);
0236
0237     indexA.insert(indexA.begin(), itx_first, itx_mid);
0238     indexB.insert(indexB.begin(), itx_mid, itx_last);
0239
0240     it_index itx_out = itx_first;
0241     it_index itxA = indexA.begin(), itxB = indexB.begin();
0242     range_it rngA, rngB;
0243     Iter_t itA = global_range.first, itB = global_range.first;
0244     bool validA = false, validB = false;
0245
0246     while (itxA != indexA.end() && itxB != indexB.end())
0247     {   //----------------------------------------------------------------
0248         // Load valid ranges from the itxA and ItxB positions
0249         //----------------------------------------------------------------
0250         if (! validA)
0251         {
0252             rngA = get_range(*itxA);
0253             itA = rngA.first;
0254             validA = true;
0255         };
0256         if (! validB)
0257         {
0258             rngB = get_range(*itxB);
0259             itB = rngB.first;
0260             validB = true;
0261         };
0262         //----------------------------------------------------------------
0263         // If don't have merge betweeen the  blocks, pass directly the
0264         // position of the block to itx_out
0265         //----------------------------------------------------------------
0266         if (ptr_circ->size() == 0)
0267         {
0268             if (! cmp(*rngB.front(), *rngA.back()))
0269             {
0270                 *(itx_out++) = *(itxA++);
0271                 validA = false;
0272                 continue;
0273             };
0274             if (cmp(*rngB.back(), *rngA.front()))
0275             {
0276                 if (! is_tail(*itxB))
0277                     *(itx_out++) = *itxB;
0278                 else ptr_circ->push_move_back(rngB.first, rngB.size());
0279                 ++itxB;
0280                 validB = false;
0281                 continue;
0282             };
0283         };
0284         //----------------------------------------------------------------
0285         // Normal merge
0286         //----------------------------------------------------------------
0287         bool side = util::merge_circular(itA, rngA.last, itB, rngB.last,
0288                         *ptr_circ, cmp, itA, itB);
0289         if (side)
0290         {   // rngA is finished
0291             ptr_circ->pop_move_front(rngA.first, rngA.size());
0292             *(itx_out++) = *(itxA++);
0293             validA = false;
0294         }
0295         else
0296         {   // rngB is finished
0297             if (! is_tail(*itxB))
0298             {
0299                 ptr_circ->pop_move_front(rngB.first, rngB.size());
0300                 *(itx_out++) = *itxB;
0301             };
0302             ++itxB;
0303             validB = false;
0304         };
0305     }; // end while
0306
0307     if (itxA == indexA.end())
0308     {   // the index A is finished
0309         rngB = get_range(*itxB);
0310         ptr_circ->pop_move_front(rngB.first, ptr_circ->size());
0311         while (itxB != indexB.end())
0312             *(itx_out++) = *(itxB++);
0313     }
0314     else
0315     {   // The list B is finished
0316         rngA = get_range(*itxA);
0317         if (ntail != 0 && indexB.back() == (nblock - 1)) // exist tail
0318         {   // add the tail block to indexA, and shift the element
0319             indexA.push_back(indexB.back());
0320             size_t numA = size_t(itA - rngA.first);
0321             ptr_circ->pop_move_back(rngA.first, numA);
0322             move_range_pos_backward(itxA, indexA.end(), ntail);
0323         };
0324
0325         ptr_circ->pop_move_front(rngA.first, ptr_circ->size());
0326         while (itxA != indexA.end())
0327             *(itx_out++) = *(itxA++);
0328     };
0329 }
0330
0331 //-------------------------------------------------------------------------
0332 //  function : move_range_pos_backward
0333 /// @brief Move backward the elements of a range of blocks in a index
0334 /// @param itx_first : iterator to the position of the first block
0335 /// @param  itx_last : itertor to the position of the last block
0336 /// @param  npos : number of positions to move. Must be less than BLOCK_SIZE
0337 /// @return
0338 //-------------------------------------------------------------------------
0339 template<class Iter_t, class Compare, uint32_t Power2>
0340 void merge_block<Iter_t, Compare, Power2>
0341 ::move_range_pos_backward(it_index itx_first, it_index itx_last, size_t npos)
0342 {
0343     assert((itx_last - itx_first) >= 0 && npos <= BLOCK_SIZE);
0344
0345     //--------------------------------------------------------------------
0346     // Processing the last block. Must be ready fore to accept npos
0347     // elements from the upper block
0348     //--------------------------------------------------------------------
0349     range_it rng1 = get_range(*(itx_last - 1));
0350     assert(rng1.size() >= npos);
0351     if (rng1.size() > npos)
0352     {
0353         size_t nmove = rng1.size() - npos;
0354         util::move_backward(rng1.last, rng1.first, rng1.first + nmove);
0355     };
0356     //--------------------------------------------------------------------
0357     // Movement of elements between blocks
0358     //--------------------------------------------------------------------
0359     for (it_index itx = itx_last - 1; itx != itx_first;)
0360     {
0361         --itx;
0362         range_it rng2 = rng1;
0363         rng1 = get_range(*itx);
0364         Iter_t it_mid1 = rng1.last - npos, it_mid2 = rng2.first + npos;
0365         util::move_backward(it_mid2, it_mid1, rng1.last);
0366         util::move_backward(rng1.last, rng1.first, it_mid1);
0367     };
0368 }
0369 //-------------------------------------------------------------------------
0370 //  function : rearrange_with_index
0371 /// @brief rearrange the blocks with the relative positions of the index
0372 /// @param
0373 /// @param
0374 /// @param
0375 /// @return
0376 //-------------------------------------------------------------------------
0377 template<class Iter_t, class Compare, uint32_t Power2>
0378 void merge_block<Iter_t, Compare, Power2>
0379 ::rearrange_with_index(void)
0380 {   //--------------------------------------------------------------------
0381     //                     Code
0382     //--------------------------------------------------------------------
0383     size_t pos_dest, pos_src, pos_ini;
0384     size_t nelem = index.size();
0385
0386     ptr_circ->clear();
0387     value_t * aux = ptr_circ->get_buffer();
0388     range_buf rng_buf(aux, aux + ptr_circ->NMAX);
0389
0390     pos_ini = 0;
0391     while (pos_ini < nelem)
0392     {
0393         while (pos_ini < nelem && index[pos_ini] == pos_ini)
0394             ++pos_ini;
0395         if (pos_ini == nelem) return;
0396         pos_dest = pos_src = pos_ini;
0397         rng_buf = move_forward(rng_buf, get_range(pos_ini));
0398         pos_src = index[pos_ini];
0399
0400         while (pos_src != pos_ini)
0401         {
0402             move_forward(get_range(pos_dest), get_range(pos_src));
0403             index[pos_dest] = pos_dest;
0404             pos_dest = pos_src;
0405             pos_src = index[pos_src];
0406         };
0407         move_forward(get_range(pos_dest), rng_buf);
0408         index[pos_dest] = pos_dest;
0409         ++pos_ini;
0410     };
0411 }
0412
0413 //****************************************************************************
0414 }//    End namespace common
0415 }//    End namespace sort
0416 }//    End namespace boost
0417 //****************************************************************************
0418 #endif