ceph/src/boost/boost/sort/common/rearrange.hpp

   1 //----------------------------------------------------------------------------
   2 /// @file rearrange.hpp
   3 /// @brief Indirect algorithm
   4 ///
   5 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
   6 ///         Distributed under the Boost Software License, Version 1.0.\n
   7 ///         ( See accompanying file LICENSE_1_0.txt or copy at
   8 ///           http://www.boost.org/LICENSE_1_0.txt  )
   9 /// @version 0.1
  10 ///
  11 /// @remarks
  12 //-----------------------------------------------------------------------------
  13 #ifndef __BOOST_SORT_COMMON_REARRANGE_HPP
  14 #define __BOOST_SORT_COMMON_REARRANGE_HPP
  15
  16 //#include <boost/sort/common/atomic.hpp>
  17 #include <boost/sort/common/util/traits.hpp>
  18 #include <functional>
  19 #include <iterator>
  20 #include <type_traits>
  21 #include <vector>
  22 #include <cassert>
  23
  24 namespace boost
  25 {
  26 namespace sort
  27 {
  28 namespace common
  29 {
  30
  31 template<class Iter_data>
  32 struct filter_iterator
  33 {
  34     //-----------------------------------------------------------------------
  35     //                   Variables
  36     //-----------------------------------------------------------------------
  37     Iter_data origin;
  38
  39     //-----------------------------------------------------------------------
  40     //                   Functions
  41     //-----------------------------------------------------------------------
  42     filter_iterator(Iter_data global_first): origin(global_first) { };
  43     size_t operator ()(Iter_data itx) const
  44     {
  45         return size_t(itx - origin);
  46     }
  47 };
  48
  49 struct filter_pos
  50 {
  51     size_t operator ()(size_t pos) const {  return pos; };
  52 };
  53
  54 //
  55 //-----------------------------------------------------------------------------
  56 //  function : rearrange
  57 /// @brief This function transform a logical sort of the elements in the index
  58 ///        of iterators in a physical sort.
  59 //
  60 /// @param global_first : iterator to the first element of the data
  61 /// @param [in] index : vector of the iterators
  62 //-----------------------------------------------------------------------------
  63 template<class Iter_data, class Iter_index, class Filter_pos>
  64 void rearrange(Iter_data global_first, Iter_index itx_first,
  65                Iter_index itx_last, Filter_pos pos)
  66 {
  67     //-----------------------------------------------------------------------
  68     //                    Metaprogramming
  69     //-----------------------------------------------------------------------
  70     typedef util::value_iter<Iter_data>     value_data;
  71     typedef util::value_iter<Iter_index>    value_index;
  72
  73     //-------------------------------------------------------------------------
  74     //                     Code
  75     //-------------------------------------------------------------------------
  76     assert((itx_last - itx_first) >= 0);
  77     size_t pos_dest, pos_src, pos_ini;
  78     size_t nelem = size_t(itx_last - itx_first);
  79     Iter_data data = global_first;
  80     Iter_index index = itx_first;
  81
  82     pos_ini = 0;
  83     while (pos_ini < nelem)
  84     {
  85         while (pos_ini < nelem and pos(index[pos_ini]) == pos_ini)
  86             ++pos_ini;
  87         if (pos_ini == nelem) return;
  88         pos_dest = pos_src = pos_ini;
  89         value_data aux = std::move(data[pos_ini]);
  90         value_index itx_src = std::move(index[pos_ini]);
  91
  92         while ((pos_src = pos(itx_src)) != pos_ini)
  93         {
  94             data[pos_dest] = std::move(data[pos_src]);
  95             std::swap(itx_src, index[pos_src]);
  96             pos_dest = pos_src;
  97         };
  98
  99         data[pos_dest] = std::move(aux);
 100         index[pos_ini] = std::move(itx_src);
 101         ++pos_ini;
 102     };
 103 };
 104
 105 /*
 106  //
 107  //-----------------------------------------------------------------------------
 108  //  function : rearrange_pos
 109  /// @brief This function transform a logical sort of the elements in the index
 110  ///        of iterators in a physical sort.
 111  //
 112  /// @param global_first : iterator to the first element of the data
 113  /// @param [in] index : vector of the iterators
 114  //-----------------------------------------------------------------------------
 115  template < class Iter_t, class Number >
 116  void rearrange_pos (Iter_t global_first, std::vector< Number> &index)
 117  {
 118  //-------------------------------------------------------------------------
 119  //          METAPROGRAMMING AND DEFINITIONS
 120  //-------------------------------------------------------------------------
 121  static_assert ( std::is_integral<Number>::value, "Incompatible Types");
 122  typedef iter_value< Iter_t > value_t;
 123
 124  //-------------------------------------------------------------------------
 125  //                     CODE
 126  //-------------------------------------------------------------------------
 127  size_t pos_dest = 0;
 128  size_t pos_src = 0;
 129  size_t pos_ini = 0;
 130  size_t nelem = index.size ( );
 131  Iter_t it_dest (global_first), it_src(global_first);
 132
 133  while (pos_ini < nelem)
 134  {
 135  while (pos_ini < nelem and
 136  index[pos_ini] == pos_ini)
 137  {
 138  ++pos_ini;
 139  };
 140
 141  if (pos_ini == nelem) return;
 142  pos_dest = pos_src = pos_ini;
 143  it_dest = global_first + pos_dest;
 144  value_t Aux = std::move (*it_dest);
 145
 146  while ((pos_src = index[pos_dest]) != pos_ini)
 147  {
 148  index[pos_dest] = it_dest - global_first;
 149  it_src = global_first + pos_src;
 150  *it_dest = std::move (*it_src);
 151  it_dest = it_src;
 152  pos_dest = pos_src;
 153  };
 154
 155  *it_dest = std::move (Aux);
 156  index[pos_dest] = it_dest - global_first;
 157  ++pos_ini;
 158  };
 159  };
 160  */
 161 //
 162 //****************************************************************************
 163 };//    End namespace common
 164 };//    End namespace sort
 165 };//    End namespace boost
 166 //****************************************************************************
 167 //
 168 #endif