ceph/src/boost/boost/sort/common/util/search.hpp

   1 //----------------------------------------------------------------------------
   2 /// @file search.hpp
   3 /// @brief
   4 /// @author Copyright (c) 2017 Francisco José Tapia (fjtapia@gmail.com )\n
   5 ///         Distributed under the Boost Software License, Version 1.0.\n
   6 ///         ( See copy at http://www.boost.org/LICENSE_1_0.txt  )
   7 /// @remarks
   8 //-----------------------------------------------------------------------------
   9 #ifndef __BOOST_SORT_COMMON_SEARCH_HPP
  10 #define __BOOST_SORT_COMMON_SEARCH_HPP
  11
  12 #include <boost/sort/common/util/traits.hpp>
  13 #include <cassert>
  14
  15 namespace boost
  16 {
  17 namespace sort
  18 {
  19 namespace common
  20 {
  21 namespace util
  22 {
  23
  24 template<class T>
  25 struct filter_pass
  26 {
  27     typedef T key;
  28     const key & operator()(const T & val) const
  29     {
  30         return val;
  31     };
  32 };
  33
  34 //
  35 //###########################################################################
  36 //                                                                         ##
  37 //    ################################################################     ##
  38 //    #                                                              #     ##
  39 //    #           I N T E R N A L      F U N C T I O N S             #     ##
  40 //    #                                                              #     ##
  41 //    ################################################################     ##
  42 //                                                                         ##
  43 //                       I M P O R T A N T                                 ##
  44 //                                                                         ##
  45 // These functions are not directly callable by the user, are for internal ##
  46 // use only.                                                               ##
  47 // These functions don't check the parameters                              ##
  48 //                                                                         ##
  49 //###########################################################################
  50 //
  51 //-----------------------------------------------------------------------------
  52 //  function : internal_find_first
  53 /// @brief find if a value exist in the range [first, last).
  54 ///        Always return as valid iterator in the range [first, last-1]
  55 ///        If exist return the iterator to the first occurrence. If don't exist
  56 ///        return the first greater than val.
  57 ///        If val is greater than the *(last-1), return (last-1)
  58 ///        If val is lower than  (*first), return  first
  59 //
  60 /// @param [in] first : iterator to the first element of the range
  61 /// @param [in] last : iterator to the last element of the range
  62 /// @param [in] val : value to find
  63 /// @param [in] comp : object for to compare two value_t objects
  64 /// @return iterator to the element found,
  65 //-----------------------------------------------------------------------------
  66 template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
  67           class Compare = std::less<typename Filter::key> >
  68 inline Iter_t internal_find_first(Iter_t first, Iter_t last,
  69                                   const typename Filter::key &val,
  70                                   const Compare & comp = Compare(),
  71                                   Filter flt = Filter())
  72 {
  73     Iter_t LI = first, LS = last - 1, it_out = first;
  74     while (LI != LS)
  75     {
  76         it_out = LI + ((LS - LI) >> 1);
  77         if (comp(flt(*it_out), val))
  78             LI = it_out + 1;
  79         else LS = it_out;
  80     };
  81     return LS;
  82 };
  83 //
  84 //-----------------------------------------------------------------------------
  85 //  function : internal_find_last
  86 /// @brief find if a value exist in the range [first, last).
  87 ///        Always return as valid iterator in the range [first, last-1]
  88 ///        If exist return the iterator to the last occurrence.
  89 ///        If don't exist return the first lower than val.
  90 ///        If val is greater than *(last-1) return (last-1).
  91 ///        If is lower than the first, return first
  92 //
  93 /// @param [in] first : iterator to the first element of the range
  94 /// @param [in] last : iterator to the last element of the range
  95 /// @param [in] val : value to find
  96 /// @param [in] comp : object for to compare two value_t objects
  97 /// @return iterator to the element found, if not found return last
  98
  99 //-----------------------------------------------------------------------------
 100 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
 101                 class Compare = std::less<typename Filter::key> >
 102 inline Iter_t internal_find_last(Iter_t first, Iter_t last,
 103                                  const typename Filter::key &val,
 104                                  const Compare & comp = Compare(), Filter flt =
 105                                                  Filter())
 106 {
 107     Iter_t LI = first, LS = last - 1, it_out = first;
 108     while (LI != LS)
 109     {
 110         it_out = LI + ((LS - LI + 1) >> 1);
 111         if (comp(val, flt(*it_out))) LS = it_out - 1;
 112         else                         LI = it_out;
 113     };
 114     return LS;
 115 };
 116
 117 //
 118 //###########################################################################
 119 //                                                                         ##
 120 //    ################################################################     ##
 121 //    #                                                              #     ##
 122 //    #              P U B L I C       F U N C T I O N S             #     ##
 123 //    #                                                              #     ##
 124 //    ################################################################     ##
 125 //                                                                         ##
 126 //###########################################################################
 127 //
 128 //-----------------------------------------------------------------------------
 129 //  function : find_first
 130 /// @brief find if a value exist in the range [first, last). If exist return the
 131 ///        iterator to the first occurrence. If don't exist return last
 132 //
 133 /// @param [in] first : iterator to the first element of the range
 134 /// @param [in] last : iterator to the last element of the range
 135 /// @param [in] val : value to find
 136 /// @param [in] comp : object for to compare two value_t objects
 137 /// @return iterator to the element found, and if not last
 138 //-----------------------------------------------------------------------------
 139 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
 140                 class Compare = std::less<typename Filter::key> >
 141 inline Iter_t find_first(Iter_t first, Iter_t last,
 142                          const typename Filter::key &val,
 143                          const Compare & comp = Compare(),
 144                          Filter flt = Filter())
 145 {
 146     assert((last - first) >= 0);
 147     if (first == last) return last;
 148     Iter_t LS = internal_find_first(first, last, val, comp, flt);
 149     return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS;
 150 };
 151 //
 152 //-----------------------------------------------------------------------------
 153 //  function : find_last
 154 /// @brief find if a value exist in the range [first, last). If exist return the
 155 ///        iterator to the last occurrence. If don't exist return last
 156 //
 157 /// @param [in] first : iterator to the first element of the range
 158 /// @param [in] last : iterator to the last element of the range
 159 /// @param [in] val : value to find
 160 /// @param [in] comp : object for to compare two value_t objects
 161 /// @return iterator to the element found, if not found return last
 162
 163 //-----------------------------------------------------------------------------
 164 template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
 165           class Compare = std::less<typename Filter::key> >
 166 inline Iter_t find_last(Iter_t first, Iter_t last,
 167                         const typename Filter::key &val,
 168                         const Compare & comp = Compare(),
 169                         Filter flt = Filter())
 170 {
 171     assert((last - first) >= 0);
 172     if (last == first) return last;
 173     Iter_t LS = internal_find_last(first, last, val, comp, flt);
 174     return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS;
 175 };
 176
 177 //----------------------------------------------------------------------------
 178 //  function : lower_bound
 179 /// @brief Returns an iterator pointing to the first element in the range
 180 ///        [first, last) that is not less than (i.e. greater or equal to) val.
 181 /// @param [in] last : iterator to the last element of the range
 182 /// @param [in] val : value to find
 183 /// @param [in] comp : object for to compare two value_t objects
 184 /// @return iterator to the element found
 185 //-----------------------------------------------------------------------------
 186 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
 187                 class Compare = std::less<typename Filter::key> >
 188 inline Iter_t lower_bound(Iter_t first, Iter_t last,
 189                           const typename Filter::key &val,
 190                           const Compare & comp = Compare(),
 191                           Filter flt = Filter())
 192 {
 193     assert((last - first) >= 0);
 194     if (last == first) return last;
 195     Iter_t itaux = internal_find_first(first, last, val, comp, flt);
 196     return (itaux == (last - 1) and comp(flt(*itaux), val)) ? last : itaux;
 197 };
 198 //----------------------------------------------------------------------------
 199 //  function :upper_bound
 200 /// @brief return the first element greather than val.If don't exist
 201 ///        return last
 202 //
 203 /// @param [in] first : iterator to the first element of the range
 204 /// @param [in] last : iterator to the last element of the range
 205 /// @param [in] val : value to find
 206 /// @param [in] comp : object for to compare two value_t objects
 207 /// @return iterator to the element found
 208 /// @remarks
 209 //-----------------------------------------------------------------------------
 210 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
 211                 class Compare = std::less<typename Filter::key> >
 212 inline Iter_t upper_bound(Iter_t first, Iter_t last,
 213                           const typename Filter::key &val,
 214                           const Compare & comp = Compare(),
 215                           Filter flt = Filter())
 216 {
 217     assert((last - first) >= 0);
 218     if (last == first) return last;
 219     Iter_t itaux = internal_find_last(first, last, val, comp, flt);
 220     return (itaux == first and comp(val, flt(*itaux))) ? itaux : itaux + 1;
 221 }
 222 ;
 223 //----------------------------------------------------------------------------
 224 //  function :equal_range
 225 /// @brief return a pair of lower_bound and upper_bound with the value val.If
 226 ///        don't exist return last in the two elements of the pair
 227 //
 228 /// @param [in] first : iterator to the first element of the range
 229 /// @param [in] last : iterator to the last element of the range
 230 /// @param [in] val : value to find
 231 /// @param [in] comp : object for to compare two value_t objects
 232 /// @return pair of iterators
 233 //-----------------------------------------------------------------------------
 234 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
 235          class Compare = std::less<typename Filter::key> >
 236 inline std::pair<Iter_t, Iter_t> equal_range(Iter_t first, Iter_t last,
 237                                              const typename Filter::key &val,
 238                                              const Compare & comp = Compare(),
 239                                              Filter flt = Filter())
 240 {
 241     return std::make_pair(lower_bound(first, last, val, comp, flt),
 242                     upper_bound(first, last, val, comp, flt));
 243 };
 244 //
 245 //-----------------------------------------------------------------------------
 246 //  function : insert_first
 247 /// @brief find if a value exist in the range [first, last). If exist return the
 248 ///        iterator to the first occurrence. If don't exist return last
 249 //
 250 /// @param [in] first : iterator to the first element of the range
 251 /// @param [in] last : iterator to the last element of the range
 252 /// @param [in] val : value to find
 253 /// @param [in] comp : object for to compare two value_t objects
 254 /// @return iterator to the element found, and if not last
 255 //-----------------------------------------------------------------------------
 256 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
 257                 class Compare = std::less<typename Filter::key> >
 258 inline Iter_t insert_first(Iter_t first, Iter_t last,
 259                            const typename Filter::key &val,
 260                            const Compare & comp = Compare(), Filter flt =
 261                                            Filter())
 262 {
 263     return lower_bound(first, last, val, comp, flt);
 264 };
 265 //
 266 //-----------------------------------------------------------------------------
 267 //  function : insert_last
 268 /// @brief find if a value exist in the range [first, last). If exist return the
 269 ///        iterator to the last occurrence. If don't exist return last
 270 //
 271 /// @param [in] first : iterator to the first element of the range
 272 /// @param [in] last : iterator to the last element of the range
 273 /// @param [in] val : value to find
 274 /// @param [in] comp : object for to compare two value_t objects
 275 /// @return iterator to the element found, if not found return last
 276
 277 //-----------------------------------------------------------------------------
 278 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
 279                 class Compare = std::less<typename Filter::key> >
 280 inline Iter_t insert_last(Iter_t first, Iter_t last,
 281                           const typename Filter::key &val,
 282                           const Compare & comp = Compare(), Filter flt =
 283                                           Filter())
 284 {
 285     return upper_bound(first, last, val, comp, flt);
 286 };
 287
 288 /*
 289
 290  //
 291  //###########################################################################
 292  //                                                                         ##
 293  //    ################################################################     ##
 294  //    #                                                              #     ##
 295  //    #           I N T E R N A L      F U N C T I O N S             #     ##
 296  //    #                                                              #     ##
 297  //    ################################################################     ##
 298  //                                                                         ##
 299  //                       I M P O R T A N T                                 ##
 300  //                                                                         ##
 301  // These functions are not directly callable by the user, are for internal ##
 302  // use only.                                                               ##
 303  // These functions don't check the parameters                              ##
 304  //                                                                         ##
 305  //###########################################################################
 306  //
 307  //-----------------------------------------------------------------------------
 308  //  function : internal_find_first
 309  /// @brief find if a value exist in the range [first, last).
 310  ///        Always return as valid iterator in the range [first, last-1]
 311  ///        If exist return the iterator to the first occurrence. If don't exist
 312  ///        return the first greater than val.
 313  ///        If val is greater than the *(last-1), return (last-1)
 314  ///        If val is lower than  (*first), return  first
 315  //
 316  /// @param [in] first : iterator to the first element of the range
 317  /// @param [in] last : iterator to the last element of the range
 318  /// @param [in] val : value to find
 319  /// @param [in] comp : object for to compare two value_t objects
 320  /// @return iterator to the element found,
 321  //-----------------------------------------------------------------------------
 322  template < class Iter_t, class Compare = compare_iter<Iter_t>  >
 323  inline Iter_t internal_find_first ( Iter_t first, Iter_t last,
 324  const value_iter<Iter_t> &val,
 325  const Compare & comp= Compare()  )
 326  {
 327  Iter_t LI = first , LS = last - 1, it_out = first;
 328  while ( LI != LS)
 329  {   it_out = LI + ( (LS - LI) >> 1);
 330  if ( comp ( *it_out, val)) LI = it_out + 1 ; else LS = it_out ;
 331  };
 332  return LS ;
 333  };
 334  //
 335  //-----------------------------------------------------------------------------
 336  //  function : internal_find_last
 337  /// @brief find if a value exist in the range [first, last).
 338  ///        Always return as valid iterator in the range [first, last-1]
 339  ///        If exist return the iterator to the last occurrence.
 340  ///        If don't exist return the first lower than val.
 341  ///        If val is greater than *(last-1) return (last-1).
 342  ///        If is lower than the first, return first
 343  //
 344  /// @param [in] first : iterator to the first element of the range
 345  /// @param [in] last : iterator to the last element of the range
 346  /// @param [in] val : value to find
 347  /// @param [in] comp : object for to compare two value_t objects
 348  /// @return iterator to the element found, if not found return last
 349
 350  //-----------------------------------------------------------------------------
 351  template < class Iter_t, class Compare = compare_iter<Iter_t> >
 352  inline Iter_t internal_find_last ( Iter_t first, Iter_t last ,
 353  const value_iter<Iter_t> &val,
 354  const Compare &comp= Compare() )
 355  {
 356  Iter_t LI = first , LS = last - 1, it_out = first ;
 357  while ( LI != LS)
 358  {   it_out = LI + ( (LS - LI + 1) >> 1);
 359  if ( comp (val, *it_out)) LS = it_out - 1 ; else LI = it_out ;
 360  };
 361  return LS ;
 362  };
 363
 364  //
 365  //###########################################################################
 366  //                                                                         ##
 367  //    ################################################################     ##
 368  //    #                                                              #     ##
 369  //    #              P U B L I C       F U N C T I O N S             #     ##
 370  //    #                                                              #     ##
 371  //    ################################################################     ##
 372  //                                                                         ##
 373  //###########################################################################
 374  //
 375  //-----------------------------------------------------------------------------
 376  //  function : find_first
 377  /// @brief find if a value exist in the range [first, last). If exist return the
 378  ///        iterator to the first occurrence. If don't exist return last
 379  //
 380  /// @param [in] first : iterator to the first element of the range
 381  /// @param [in] last : iterator to the last element of the range
 382  /// @param [in] val : value to find
 383  /// @param [in] comp : object for to compare two value_t objects
 384  /// @return iterator to the element found, and if not last
 385  //-----------------------------------------------------------------------------
 386  template < class Iter_t, class Compare = compare_iter<Iter_t> >
 387  inline Iter_t find_first ( Iter_t first, Iter_t last,
 388  const value_iter<Iter_t> &val,
 389  Compare comp = Compare() )
 390  {
 391  assert ( (last - first) >= 0 );
 392  if ( first == last) return last ;
 393  Iter_t LS = internal_find_first ( first, last, val, comp);
 394  return (comp (*LS, val) or comp (val, *LS))?last:LS;
 395  };
 396  //
 397  //-----------------------------------------------------------------------------
 398  //  function : find_last
 399  /// @brief find if a value exist in the range [first, last). If exist return the
 400  ///        iterator to the last occurrence. If don't exist return last
 401  //
 402  /// @param [in] first : iterator to the first element of the range
 403  /// @param [in] last : iterator to the last element of the range
 404  /// @param [in] val : value to find
 405  /// @param [in] comp : object for to compare two value_t objects
 406  /// @return iterator to the element found, if not found return last
 407
 408  //-----------------------------------------------------------------------------
 409  template < class Iter_t, class Compare = compare_iter<Iter_t> >
 410  inline Iter_t find_last ( Iter_t first, Iter_t last ,
 411  const value_iter<Iter_t> &val,
 412  Compare comp = Compare())
 413  {
 414  assert ( (last - first ) >= 0 );
 415  if ( last == first ) return last ;
 416  Iter_t LS = internal_find_last (first, last, val, comp);
 417  return (comp (*LS, val) or comp (val, *LS))?last:LS ;
 418  };
 419
 420  //----------------------------------------------------------------------------
 421  //  function : lower_bound
 422  /// @brief Returns an iterator pointing to the first element in the range
 423  ///        [first, last) that is not less than (i.e. greater or equal to) val.
 424  /// @param [in] last : iterator to the last element of the range
 425  /// @param [in] val : value to find
 426  /// @param [in] comp : object for to compare two value_t objects
 427  /// @return iterator to the element found
 428  //-----------------------------------------------------------------------------
 429  template < class Iter_t, class Compare = compare_iter<Iter_t> >
 430  inline Iter_t lower_bound ( Iter_t first, Iter_t last ,
 431  const value_iter<Iter_t> &val,
 432  Compare &comp = Compare() )
 433  {
 434  assert ( (last - first ) >= 0 );
 435  if ( last == first ) return last ;
 436  Iter_t  itaux = internal_find_first( first, last, val,comp);
 437  return (itaux == (last - 1) and comp (*itaux, val))?last: itaux;
 438  };
 439  //----------------------------------------------------------------------------
 440  //  function :upper_bound
 441  /// @brief return the first element greather than val.If don't exist
 442  ///        return last
 443  //
 444  /// @param [in] first : iterator to the first element of the range
 445  /// @param [in] last : iterator to the last element of the range
 446  /// @param [in] val : value to find
 447  /// @param [in] comp : object for to compare two value_t objects
 448  /// @return iterator to the element found
 449  /// @remarks
 450  //-----------------------------------------------------------------------------
 451  template < class Iter_t, class Compare = compare_iter<Iter_t> >
 452  inline Iter_t upper_bound ( Iter_t first, Iter_t last ,
 453  const value_iter<Iter_t> &val,
 454  Compare &comp = Compare() )
 455  {
 456  assert ( (last - first ) >= 0 );
 457  if ( last == first ) return last ;
 458  Iter_t itaux = internal_find_last( first, last, val,comp);
 459  return ( itaux == first and comp (val,*itaux))? itaux: itaux + 1;
 460  };
 461  //----------------------------------------------------------------------------
 462  //  function :equal_range
 463  /// @brief return a pair of lower_bound and upper_bound with the value val.If
 464  ///        don't exist return last in the two elements of the pair
 465  //
 466  /// @param [in] first : iterator to the first element of the range
 467  /// @param [in] last : iterator to the last element of the range
 468  /// @param [in] val : value to find
 469  /// @param [in] comp : object for to compare two value_t objects
 470  /// @return pair of iterators
 471  //-----------------------------------------------------------------------------
 472  template < class Iter_t, class Compare = compare_iter<Iter_t> >
 473  inline std::pair<Iter_t, Iter_t> equal_range ( Iter_t first, Iter_t last ,
 474  const value_iter<Iter_t> &val,
 475  Compare &comp = Compare() )
 476  {
 477  return std::make_pair(lower_bound(first, last, val,comp),
 478  upper_bound(first, last, val,comp));
 479  };
 480  //
 481  //-----------------------------------------------------------------------------
 482  //  function : insert_first
 483  /// @brief find if a value exist in the range [first, last). If exist return the
 484  ///        iterator to the first occurrence. If don't exist return last
 485  //
 486  /// @param [in] first : iterator to the first element of the range
 487  /// @param [in] last : iterator to the last element of the range
 488  /// @param [in] val : value to find
 489  /// @param [in] comp : object for to compare two value_t objects
 490  /// @return iterator to the element found, and if not last
 491  //-----------------------------------------------------------------------------
 492  template < class Iter_t, class Compare = compare_iter<Iter_t> >
 493  inline Iter_t insert_first ( Iter_t first, Iter_t last,
 494  const value_iter<Iter_t> &val,
 495  Compare comp = Compare() )
 496  {
 497  return lower_bound (first, last, val, comp);
 498  };
 499  //
 500  //-----------------------------------------------------------------------------
 501  //  function : insert_last
 502  /// @brief find if a value exist in the range [first, last). If exist return the
 503  ///        iterator to the last occurrence. If don't exist return last
 504  //
 505  /// @param [in] first : iterator to the first element of the range
 506  /// @param [in] last : iterator to the last element of the range
 507  /// @param [in] val : value to find
 508  /// @param [in] comp : object for to compare two value_t objects
 509  /// @return iterator to the element found, if not found return last
 510
 511  //-----------------------------------------------------------------------------
 512  template < class Iter_t, class Compare = compare_iter<Iter_t> >
 513  inline Iter_t insert_last ( Iter_t first, Iter_t last ,
 514  const value_iter<Iter_t> &val,
 515  Compare comp = Compare())
 516  {
 517  return upper_bound (first, last, val, comp);
 518  };
 519
 520  */
 521 //
 522 //****************************************************************************
 523 };//    End namespace util
 524 };//    End namespace common
 525 };//    End namespace sort
 526 };//    End namespace boost
 527 //****************************************************************************
 528 //
 529 #endif