test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp

   1 //===----------------------------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is dual licensed under the MIT and the University of Illinois Open
   6 // Source Licenses. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 // <algorithm>
  11
  12 // template<BidirectionalIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
  13 //   requires ShuffleIterator<Iter>
  14 //         && CopyConstructible<Compare>
  15 //   void
  16 //   inplace_merge(Iter first, Iter middle, Iter last, Compare comp);
  17
  18 #include <algorithm>
  19 #include <functional>
  20 #include <cassert>
  21
  22 #include "test_macros.h"
  23
  24 #if TEST_STD_VER >= 11
  25 #include <memory>
  26
  27 struct indirect_less
  28 {
  29     template <class P>
  30     bool operator()(const P& x, const P& y)
  31         {return *x < *y;}
  32 };
  33
  34 struct S {
  35         S() : i_(0) {}
  36         S(int i) : i_(i) {}
  37
  38         S(const S&  rhs) : i_(rhs.i_) {}
  39         S(      S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
  40
  41         S& operator =(const S&  rhs) { i_ = rhs.i_;              return *this; }
  42         S& operator =(      S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; assert(this != &rhs); return *this; }
  43         S& operator =(int i)         { i_ = i;                   return *this; }
  44
  45         bool operator  <(const S&  rhs) const { return i_ < rhs.i_; }
  46         bool operator  >(const S&  rhs) const { return i_ > rhs.i_; }
  47         bool operator ==(const S&  rhs) const { return i_ == rhs.i_; }
  48         bool operator ==(int i)         const { return i_ == i; }
  49
  50         void set(int i) { i_ = i; }
  51
  52         int i_;
  53         };
  54
  55
  56 #endif  // TEST_STD_VER >= 11
  57
  58 #include "test_iterators.h"
  59 #include "counting_predicates.hpp"
  60
  61 template <class Iter>
  62 void
  63 test_one(unsigned N, unsigned M)
  64 {
  65     assert(M <= N);
  66     typedef typename std::iterator_traits<Iter>::value_type value_type;
  67     value_type* ia = new value_type[N];
  68     for (unsigned i = 0; i < N; ++i)
  69         ia[i] = i;
  70     std::random_shuffle(ia, ia+N);
  71     std::sort(ia, ia+M, std::greater<value_type>());
  72     std::sort(ia+M, ia+N, std::greater<value_type>());
  73     binary_counting_predicate<std::greater<value_type>, value_type, value_type> pred((std::greater<value_type>()));
  74     std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::ref(pred));
  75     if(N > 0)
  76     {
  77         assert(ia[0] == static_cast<int>(N)-1);
  78         assert(ia[N-1] == 0);
  79         assert(std::is_sorted(ia, ia+N, std::greater<value_type>()));
  80         assert(pred.count() <= (N-1));
  81     }
  82     delete [] ia;
  83 }
  84
  85 template <class Iter>
  86 void
  87 test(unsigned N)
  88 {
  89     test_one<Iter>(N, 0);
  90     test_one<Iter>(N, N/4);
  91     test_one<Iter>(N, N/2);
  92     test_one<Iter>(N, 3*N/4);
  93     test_one<Iter>(N, N);
  94 }
  95
  96 template <class Iter>
  97 void
  98 test()
  99 {
 100     test_one<Iter>(0, 0);
 101     test_one<Iter>(1, 0);
 102     test_one<Iter>(1, 1);
 103     test_one<Iter>(2, 0);
 104     test_one<Iter>(2, 1);
 105     test_one<Iter>(2, 2);
 106     test_one<Iter>(3, 0);
 107     test_one<Iter>(3, 1);
 108     test_one<Iter>(3, 2);
 109     test_one<Iter>(3, 3);
 110     test<Iter>(4);
 111     test<Iter>(20);
 112     test<Iter>(100);
 113     test<Iter>(1000);
 114 }
 115
 116 int main()
 117 {
 118     test<bidirectional_iterator<int*> >();
 119     test<random_access_iterator<int*> >();
 120     test<int*>();
 121
 122 #if TEST_STD_VER >= 11
 123     test<bidirectional_iterator<S*> >();
 124     test<random_access_iterator<S*> >();
 125     test<S*>();
 126
 127     {
 128     int N = 100;
 129     unsigned M = 50;
 130     std::unique_ptr<int>* ia = new std::unique_ptr<int>[N];
 131     for (int i = 0; i < N; ++i)
 132         ia[i].reset(new int(i));
 133     std::random_shuffle(ia, ia+N);
 134     std::sort(ia, ia+M, indirect_less());
 135     std::sort(ia+M, ia+N, indirect_less());
 136     std::inplace_merge(ia, ia+M, ia+N, indirect_less());
 137     if(N > 0)
 138     {
 139         assert(*ia[0] == 0);
 140         assert(*ia[N-1] == N-1);
 141         assert(std::is_sorted(ia, ia+N, indirect_less()));
 142     }
 143     delete [] ia;
 144     }
 145 #endif  // TEST_STD_VER >= 11
 146 }