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