123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180 |
- //----------------------------------------------------------------------------
- /// @file block.hpp
- /// @brief This file contains the internal data structures used in 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_PARALLEL_DETAIL_BLOCK_HPP
- #define __BOOST_SORT_PARALLEL_DETAIL_BLOCK_HPP
- #include <boost/sort/common/range.hpp>
- namespace boost
- {
- namespace sort
- {
- namespace blk_detail
- {
- //---------------------------------------------------------------------------
- // USING SENTENCES
- //---------------------------------------------------------------------------
- using namespace boost::sort::common;
- //
- //---------------------------------------------------------------------------
- /// @struct block_pos
- /// @brief represent a pair of values, a position represented as an unsigned
- /// variable ( position ), and a bool variable ( side ). They are packed
- /// in a size_t variable. The Least Significant Bit is the bool variable,
- /// and the others bits are the position
- //----------------------------------------------------------------------------
- class block_pos
- {
- //------------------------------------------------------------------------
- // VARIABLES
- //-----------------------------------------------------------------------
- size_t num; // number which store a position and a bool side
- public:
- //----------------------------- FUNCTIONS ------------------------------
- block_pos (void) : num (0){};
- //
- //-------------------------------------------------------------------------
- // function : block_pos
- /// @brief constructor from a position and a side
- /// @param position : position to sotre
- /// @param side : side to store
- //-------------------------------------------------------------------------
- block_pos (size_t position, bool side = false)
- {
- num = (position << 1) + ((side) ? 1 : 0);
- };
- //
- //-------------------------------------------------------------------------
- // function : pos
- /// @brief obtain the position stored inside the block_pos
- /// @return position
- //-------------------------------------------------------------------------
- size_t pos (void) const { return (num >> 1); };
- //
- //-------------------------------------------------------------------------
- // function : pos
- /// @brief store a position inside the block_pos
- /// @param position : value to store
- //-------------------------------------------------------------------------
- void set_pos (size_t position) { num = (position << 1) + (num & 1); };
- //
- //-------------------------------------------------------------------------
- // function : side
- /// @brief obtain the side stored inside the block_pos
- /// @return bool value
- //-------------------------------------------------------------------------
- bool side (void) const { return ((num & 1) != 0); };
- //
- //-------------------------------------------------------------------------
- // function : side
- /// @brief store a bool value the block_pos
- /// @param sd : bool value to store
- //-------------------------------------------------------------------------
- void set_side (bool sd) { num = (num & ~1) + ((sd) ? 1 : 0); };
- }; // end struct block_pos
- //
- //---------------------------------------------------------------------------
- /// @struct block
- /// @brief represent a group of Block_size contiguous elements, beginning
- /// with the pointed by first
- //----------------------------------------------------------------------------
- template < uint32_t Block_size, class Iter_t >
- struct block
- {
- //----------------------------------------------------------------------
- // VARIABLES
- //----------------------------------------------------------------------
- Iter_t first; // iterator to the first element of the block
- //-------------------------------------------------------------------------
- // function : block
- /// @brief constructor from an iterator to the first element of the block
- /// @param it : iterator to the first element of the block
- //-------------------------------------------------------------------------
- block (Iter_t it) : first (it){};
- //-------------------------------------------------------------------------
- // function : get_range
- /// @brief convert a block in a range
- /// @return range
- //-------------------------------------------------------------------------
- range< Iter_t > get_range (void)
- {
- return range_it (first, first + Block_size);
- };
- }; // end struct block
- //
- //-------------------------------------------------------------------------
- // function : compare_block
- /// @brief compare two blocks using the content of the pointed by first
- /// @param block1 : first block to compare
- /// @param block2 : second block to compare
- /// @param cmp : comparison operator
- //-------------------------------------------------------------------------
- template < uint32_t Block_size, class Iter_t, class Compare >
- bool compare_block (block< Block_size, Iter_t > block1,
- block< Block_size, Iter_t > block2,
- Compare cmp = Compare ( ))
- {
- return cmp (*block1.first, *block2.first);
- };
- //
- ///---------------------------------------------------------------------------
- /// @struct compare_block_pos
- /// @brief This is a object for to compare two block_pos objects
- //----------------------------------------------------------------------------
- template < uint32_t Block_size, class Iter_t, class Compare >
- struct compare_block_pos
- {
- //-----------------------------------------------------------------------
- // VARIABLES
- //-----------------------------------------------------------------------
- Iter_t global_first; // iterator to the first element to sort
- Compare comp; // comparison object for to compare two elements
- //-------------------------------------------------------------------------
- // function : compare_block_pos
- /// @brief constructor
- /// @param g_first : itertor to the first element to sort
- /// @param cmp : comparison operator
- //-------------------------------------------------------------------------
- compare_block_pos (Iter_t g_first, Compare cmp)
- : global_first (g_first), comp (cmp){};
- //
- //-------------------------------------------------------------------------
- // function : operator ()
- /// @brief compare two blocks using the content of the pointed by
- /// global_first
- /// @param block_pos1 : first block to compare
- /// @param block_pos2 : second block to compare
- //-------------------------------------------------------------------------
- bool operator( ) (block_pos block_pos1, block_pos block_pos2) const
- {
- return comp (*(global_first + (block_pos1.pos ( ) * Block_size)),
- *(global_first + (block_pos2.pos ( ) * Block_size)));
- };
- }; // end struct compare_block_pos
- //****************************************************************************
- }; // End namespace blk_detail
- }; // End namespace sort
- }; // End namespace boost
- //****************************************************************************
- //
- #endif
|