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

   1 //----------------------------------------------------------------------------
   2 /// @file sort_basic.hpp
   3 /// @brief Spin Sort algorithm
   4 ///
   5 /// @author Copyright (c) 2016 Francisco José 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_SORT_BASIC_HPP
  14 #define __BOOST_SORT_COMMON_SORT_BASIC_HPP
  15
  16 //#include <boost/sort/spinsort/util/indirect.hpp>
  17 #include <boost/sort/insert_sort/insert_sort.hpp>
  18 #include <boost/sort/common/util/traits.hpp>
  19 #include <boost/sort/common/range.hpp>
  20 #include <cstdlib>
  21 #include <functional>
  22 #include <iterator>
  23 #include <memory>
  24 #include <type_traits>
  25 #include <vector>
  26 #include <cstddef>
  27
  28 namespace boost
  29 {
  30 namespace sort
  31 {
  32 namespace common
  33 {
  34
  35 //----------------------------------------------------------------------------
  36 //                USING SENTENCES
  37 //----------------------------------------------------------------------------
  38 using boost::sort::insert_sort;
  39
  40 //-----------------------------------------------------------------------------
  41 //  function : is_stable_sorted_forward
  42 /// @brief examine the elements in the range first, last if they are stable
  43 ///        sorted, and return an iterator to the first element not sorted
  44 /// @param first : iterator to the first element in the range
  45 /// @param last : ierator after the last element of the range
  46 /// @param comp : object for to compare two elements
  47 /// @return iterator to the first element not stable sorted. The number of
  48 ///         elements sorted is the iterator returned minus first
  49 //-----------------------------------------------------------------------------
  50 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
  51 inline Iter_t is_stable_sorted_forward (Iter_t first, Iter_t last,
  52                                         Compare comp = Compare())
  53 {
  54 #ifdef __BS_DEBUG
  55     assert ( (last- first) >= 0);
  56 #endif
  57     if ((last - first) < 2) return first;
  58     Iter_t it2 = first + 1;
  59     for (Iter_t it1 = first; it2 != last and not comp(*it2, *it1); it1 = it2++);
  60     return it2;
  61 }
  62 //-----------------------------------------------------------------------------
  63 //  function : is_reverse_stable_sorted_forward
  64 /// @brief examine the elements in the range first, last if they are reverse
  65 ///        stable sorted, and return an iterator to the first element not
  66 ///        reverse stable sorted
  67 /// @param first : iterator to the first element in the range
  68 /// @param last : ierator after the last element of the range
  69 /// @param comp : object for to compare two elements
  70 /// @return iterator to the first element not  reverse stable sorted. The number
  71 ///         of elements sorted is the iterator returned minus first
  72 //-----------------------------------------------------------------------------
  73 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
  74 inline Iter_t is_reverse_stable_sorted_forward(Iter_t first, Iter_t last,
  75                                                Compare comp = Compare())
  76 {
  77 #ifdef __BS_DEBUG
  78     assert ( (last- first) >= 0);
  79 #endif
  80     if ((last - first) < 2) return first;
  81     Iter_t it2 = first + 1;
  82     for (Iter_t it1 = first; it2 != last and comp(*it2, *it1); it1 = it2++);
  83     return it2;
  84 };
  85 //-----------------------------------------------------------------------------
  86 //  function : number_stable_sorted_forward
  87 /// @brief examine the elements in the range first, last if they are stable
  88 ///        sorted, and return the number of elements sorted
  89 /// @param first : iterator to the first element in the range
  90 /// @param last : ierator after the last element of the range
  91 /// @param comp : object for to compare two elements
  92 /// @param min_process : minimal number of elements to be consideer
  93 /// @return number of element sorted. I f the number is lower than min_process
  94 ///         return 0
  95 //-----------------------------------------------------------------------------
  96 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
  97 size_t number_stable_sorted_forward (Iter_t first, Iter_t last,
  98                                              size_t min_process,
  99                                      Compare comp = Compare())
 100 {
 101 #ifdef __BS_DEBUG
 102     assert ( (last- first) >= 0);
 103 #endif
 104     if ((last - first) < 2) return 0;
 105
 106     // sorted elements
 107     Iter_t it2 = first + 1;
 108     for (Iter_t it1 = first; it2 != last and not comp(*it2, *it1); it1 = it2++);
 109     size_t nsorted = size_t ( it2 - first);
 110     if ( nsorted != 1)
 111         return (nsorted >= min_process) ? nsorted: 0;
 112
 113     // reverse sorted elements
 114     it2 = first + 1;
 115     for (Iter_t it1 = first; it2 != last and comp(*it2, *it1); it1 = it2++);
 116     nsorted = size_t ( it2 - first);
 117
 118     if ( nsorted < min_process) return 0 ;
 119     util::reverse ( first , it2);
 120     return nsorted;
 121 };
 122
 123 //-----------------------------------------------------------------------------
 124 //  function : is_stable_sorted_backward
 125 /// @brief examine the elements in the range first, last beginning at end, and
 126 ///        if they are stablesorted, and return an iterator to the last element
 127 ///        sorted
 128 /// @param first : iterator to the first element in the range
 129 /// @param last : ierator after the last element of the range
 130 /// @param comp : object for to compare two elements
 131 /// @return iterator to the last element stable sorted. The number of
 132 ///         elements sorted is the last minus the iterator returned
 133 //-----------------------------------------------------------------------------
 134 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
 135 inline Iter_t is_stable_sorted_backward(Iter_t first, Iter_t last,
 136                                         Compare comp = Compare())
 137 {
 138 #ifdef __BS_DEBUG
 139     assert ( (last- first) >= 0);
 140 #endif
 141     if ((last - first) < 2) return first;
 142     Iter_t itaux = last - 1;
 143     while (itaux != first and not comp(*itaux, *(itaux - 1))) {--itaux; };
 144     return itaux;
 145 }
 146 //-----------------------------------------------------------------------------
 147 //  function : is_reverse_stable_sorted_backward
 148 /// @brief examine the elements in the range first, last beginning at end, and
 149 ///        if they are stablesorted, and return an iterator to the last element
 150 ///        sorted
 151 /// @param first : iterator to the first element in the range
 152 /// @param last : ierator after the last element of the range
 153 /// @param comp : object for to compare two elements
 154 /// @return iterator to the last element stable sorted. The number of
 155 ///         elements sorted is the last minus the iterator returned
 156 //-----------------------------------------------------------------------------
 157 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
 158 inline Iter_t is_reverse_stable_sorted_backward (Iter_t first, Iter_t last,
 159                                                  Compare comp = Compare())
 160 {
 161 #ifdef __BS_DEBUG
 162     assert ( (last- first) >= 0);
 163 #endif
 164     if ((last - first) < 2) return first;
 165     Iter_t itaux = last - 1;
 166     for (; itaux != first and comp(*itaux, *(itaux - 1)); --itaux);
 167     return itaux;
 168 }
 169
 170 //-----------------------------------------------------------------------------
 171 //  function : number_stable_sorted_backward
 172 /// @brief examine the elements in the range first, last if they are stable
 173 ///        sorted, and return the number of elements sorted
 174 /// @param first : iterator to the first element in the range
 175 /// @param last : ierator after the last element of the range
 176 /// @param comp : object for to compare two elements
 177 /// @param min_process : minimal number of elements to be consideer
 178 /// @return number of element sorted. I f the number is lower than min_process
 179 ///         return 0
 180 //-----------------------------------------------------------------------------
 181 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
 182 size_t number_stable_sorted_backward (Iter_t first, Iter_t last,
 183                                              size_t min_process,
 184                                      Compare comp = Compare())
 185 {
 186 #ifdef __BS_DEBUG
 187     assert ( (last- first) >= 0);
 188 #endif
 189     if ((last - first) < 2) return 0;
 190     Iter_t itaux = last - 1;
 191     while (itaux != first and not comp(*itaux, *(itaux - 1))) {--itaux; };
 192     size_t nsorted = size_t ( last - itaux);
 193     if ( nsorted != 1)
 194         return ( nsorted >= min_process)?nsorted: 0 ;
 195
 196     itaux = last - 1;
 197     for (; itaux != first and comp(*itaux, *(itaux - 1)); --itaux);
 198     nsorted = size_t ( last - itaux);
 199     if ( nsorted < min_process) return 0 ;
 200     util::reverse ( itaux, last );
 201     return nsorted;
 202 }
 203 //-----------------------------------------------------------------------------
 204 //  function : internal_sort
 205 /// @brief this function divide r_input in two parts, sort it,and merge moving
 206 ///        the elements to range_buf
 207 /// @param range_input : range with the elements to sort
 208 /// @param range_buffer : range with the elements sorted
 209 /// @param comp : object for to compare two elements
 210 /// @param level : when is 1, sort with the insertionsort algorithm
 211 ///                if not make a recursive call splitting the ranges
 212 //
 213 //-----------------------------------------------------------------------------
 214 template <class Iter1_t, class Iter2_t, class Compare>
 215 inline void internal_sort (const range<Iter1_t> &rng1,
 216                                    const range<Iter2_t> &rng2,
 217                            Compare comp, uint32_t level, bool even = true)
 218 {
 219     //-----------------------------------------------------------------------
 220     //                  metaprogram
 221     //-----------------------------------------------------------------------
 222     typedef value_iter<Iter1_t> value_t;
 223     typedef value_iter<Iter2_t> value2_t;
 224     static_assert (std::is_same< value_t, value2_t>::value,
 225                     "Incompatible iterators\n");
 226
 227     //-----------------------------------------------------------------------
 228     //                  program
 229     //-----------------------------------------------------------------------
 230 #ifdef __BS_DEBUG
 231     assert (rng1.size ( ) == rng2.size ( ) );
 232 #endif
 233     size_t nelem = (rng1.size() + 1) >> 1;
 234
 235     range<Iter1_t> rng1_left(rng1.first, rng1.first + nelem),
 236                    rng1_right(rng1.first + nelem, rng1.last);
 237
 238     range<Iter2_t> rng2_left(rng2.first, rng2.first + nelem),
 239                    rng2_right(rng2.first + nelem, rng2.last);
 240
 241     if (nelem <= 32 and (level & 1) == even)
 242     {
 243         insert_sort(rng1_left.first, rng1_left.last, comp);
 244         insert_sort(rng1_right.first, rng1_right.last, comp);
 245     }
 246     else
 247     {
 248         internal_sort(rng2_left, rng1_left, comp, level + 1, even);
 249         internal_sort(rng2_right, rng1_right, comp, level + 1, even);
 250     };
 251     merge(rng2, rng1_left, rng1_right, comp);
 252 };
 253 //-----------------------------------------------------------------------------
 254 //  function : range_sort_data
 255 /// @brief this sort elements using the range_sort function and receiving a
 256 ///        buffer of initialized memory
 257 /// @param rng_data : range with the elements to sort
 258 /// @param rng_aux : range of at least the same memory than rng_data used as
 259 ///                  auxiliary memory in the sorting
 260 /// @param comp : object for to compare two elements
 261 //-----------------------------------------------------------------------------
 262 template<class Iter1_t, class Iter2_t, class Compare>
 263 static void range_sort_data (const range<Iter1_t> & rng_data,
 264                              const range<Iter2_t> & rng_aux, Compare comp)
 265 {
 266     //-----------------------------------------------------------------------
 267     //                  metaprogram
 268     //-----------------------------------------------------------------------
 269     typedef value_iter<Iter1_t> value_t;
 270     typedef value_iter<Iter2_t> value2_t;
 271     static_assert (std::is_same< value_t, value2_t>::value,
 272                     "Incompatible iterators\n");
 273
 274     //------------------------------------------------------------------------
 275     //                    program
 276     //------------------------------------------------------------------------
 277 #ifdef __BS_DEBUG
 278     assert ( rng_data.size() == rng_aux.size());
 279 #endif
 280     // minimal number of element before to jump to insertionsort
 281     const uint32_t sort_min = 32;
 282     if (rng_data.size() <= sort_min)
 283     {
 284         insert_sort(rng_data.first, rng_data.last, comp);
 285         return;
 286     };
 287
 288     internal_sort(rng_aux, rng_data, comp, 0, true);
 289 };
 290 //-----------------------------------------------------------------------------
 291 //  function : range_sort_buffer
 292 /// @brief this sort elements using the range_sort function and receiving a
 293 ///        buffer of initialized memory
 294 /// @param rng_data : range with the elements to sort
 295 /// @param rng_aux : range of at least the same memory than rng_data used as
 296 ///                  auxiliary memory in the sorting
 297 /// @param comp : object for to compare two elements
 298 //-----------------------------------------------------------------------------
 299 template<class Iter1_t, class Iter2_t, class Compare>
 300 static void range_sort_buffer(const range<Iter1_t> & rng_data,
 301                               const range<Iter2_t> & rng_aux, Compare comp)
 302 {
 303     //-----------------------------------------------------------------------
 304     //                  metaprogram
 305     //-----------------------------------------------------------------------
 306     typedef value_iter<Iter1_t> value_t;
 307     typedef value_iter<Iter2_t> value2_t;
 308     static_assert (std::is_same< value_t, value2_t>::value,
 309                     "Incompatible iterators\n");
 310
 311     //------------------------------------------------------------------------
 312     //                    program
 313     //------------------------------------------------------------------------
 314 #ifdef __BS_DEBUG
 315     assert ( rng_data.size() == rng_aux.size());
 316 #endif
 317     // minimal number of element before to jump to insertionsort
 318     const uint32_t sort_min = 32;
 319     if (rng_data.size() <= sort_min)
 320     {
 321         insert_sort(rng_data.first, rng_data.last, comp);
 322         move_forward(rng_aux, rng_data);
 323         return;
 324     };
 325
 326     internal_sort(rng_data, rng_aux, comp, 0, false);
 327 };
 328 //****************************************************************************
 329 };//    End namespace common
 330 };//    End namespace sort
 331 };//    End namepspace boost
 332 //****************************************************************************
 333 //
 334 #endif