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 <random> 21 #include <cassert> 22 23 #include "test_macros.h" 24 25 #if TEST_STD_VER >= 11 26 #include <memory> 27 28 struct indirect_less 29 { 30 template <class P> 31 bool operator()(const P& x, const P& y) 32 {return *x < *y;} 33 }; 34 35 struct S { 36 S() : i_(0) {} 37 S(int i) : i_(i) {} 38 39 S(const S& rhs) : i_(rhs.i_) {} 40 S( S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; } 41 42 S& operator =(const S& rhs) { i_ = rhs.i_; return *this; } 43 S& operator =( S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; assert(this != &rhs); return *this; } 44 S& operator =(int i) { i_ = i; return *this; } 45 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 ==(const S& rhs) const { return i_ == rhs.i_; } 49 bool operator ==(int i) const { return i_ == i; } 50 51 void set(int i) { i_ = i; } 52 53 int i_; 54 }; 55 56 57 #endif // TEST_STD_VER >= 11 58 59 #include "test_iterators.h" 60 #include "counting_predicates.hpp" 61 62 std::mt19937 randomness; 63 64 template <class Iter> 65 void 66 test_one(unsigned N, unsigned M) 67 { 68 assert(M <= N); 69 typedef typename std::iterator_traits<Iter>::value_type value_type; 70 value_type* ia = new value_type[N]; 71 for (unsigned i = 0; i < N; ++i) 72 ia[i] = i; 73 std::shuffle(ia, ia+N, randomness); 74 std::sort(ia, ia+M, std::greater<value_type>()); 75 std::sort(ia+M, ia+N, std::greater<value_type>()); 76 binary_counting_predicate<std::greater<value_type>, value_type, value_type> pred((std::greater<value_type>())); 77 std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::ref(pred)); 78 if(N > 0) 79 { 80 assert(ia[0] == static_cast<int>(N)-1); 81 assert(ia[N-1] == 0); 82 assert(std::is_sorted(ia, ia+N, std::greater<value_type>())); 83 assert(pred.count() <= (N-1)); 84 } 85 delete [] ia; 86 } 87 88 template <class Iter> 89 void 90 test(unsigned N) 91 { 92 test_one<Iter>(N, 0); 93 test_one<Iter>(N, N/4); 94 test_one<Iter>(N, N/2); 95 test_one<Iter>(N, 3*N/4); 96 test_one<Iter>(N, N); 97 } 98 99 template <class Iter> 100 void 101 test() 102 { 103 test_one<Iter>(0, 0); 104 test_one<Iter>(1, 0); 105 test_one<Iter>(1, 1); 106 test_one<Iter>(2, 0); 107 test_one<Iter>(2, 1); 108 test_one<Iter>(2, 2); 109 test_one<Iter>(3, 0); 110 test_one<Iter>(3, 1); 111 test_one<Iter>(3, 2); 112 test_one<Iter>(3, 3); 113 test<Iter>(4); 114 test<Iter>(20); 115 test<Iter>(100); 116 test<Iter>(1000); 117 } 118 119 int main() 120 { 121 test<bidirectional_iterator<int*> >(); 122 test<random_access_iterator<int*> >(); 123 test<int*>(); 124 125 #if TEST_STD_VER >= 11 126 test<bidirectional_iterator<S*> >(); 127 test<random_access_iterator<S*> >(); 128 test<S*>(); 129 130 { 131 int N = 100; 132 unsigned M = 50; 133 std::unique_ptr<int>* ia = new std::unique_ptr<int>[N]; 134 for (int i = 0; i < N; ++i) 135 ia[i].reset(new int(i)); 136 std::shuffle(ia, ia+N, randomness); 137 std::sort(ia, ia+M, indirect_less()); 138 std::sort(ia+M, ia+N, indirect_less()); 139 std::inplace_merge(ia, ia+M, ia+N, indirect_less()); 140 if(N > 0) 141 { 142 assert(*ia[0] == 0); 143 assert(*ia[N-1] == N-1); 144 assert(std::is_sorted(ia, ia+N, indirect_less())); 145 } 146 delete [] ia; 147 } 148 #endif // TEST_STD_VER >= 11 149 } 150
