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> 13 // requires ShuffleIterator<Iter> 14 // && LessThanComparable<Iter::value_type> 15 // void 16 // inplace_merge(Iter first, Iter middle, Iter last); 17 18 #include <algorithm> 19 #include <random> 20 #include <cassert> 21 22 #include "test_iterators.h" 23 24 #if TEST_STD_VER >= 11 25 struct S { 26 S() : i_(0) {} 27 S(int i) : i_(i) {} 28 29 S(const S& rhs) : i_(rhs.i_) {} 30 S( S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; } 31 32 S& operator =(const S& rhs) { i_ = rhs.i_; return *this; } 33 S& operator =( S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; assert(this != &rhs); return *this; } 34 S& operator =(int i) { i_ = i; return *this; } 35 36 bool operator <(const S& rhs) const { return i_ < rhs.i_; } 37 bool operator ==(const S& rhs) const { return i_ == rhs.i_; } 38 bool operator ==(int i) const { return i_ == i; } 39 40 void set(int i) { i_ = i; } 41 42 int i_; 43 }; 44 #endif 45 46 std::mt19937 randomness; 47 48 template <class Iter> 49 void 50 test_one(unsigned N, unsigned M) 51 { 52 typedef typename std::iterator_traits<Iter>::value_type value_type; 53 assert(M <= N); 54 value_type* ia = new value_type[N]; 55 for (unsigned i = 0; i < N; ++i) 56 ia[i] = i; 57 std::shuffle(ia, ia+N, randomness); 58 std::sort(ia, ia+M); 59 std::sort(ia+M, ia+N); 60 std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N)); 61 if(N > 0) 62 { 63 assert(ia[0] == 0); 64 assert(ia[N-1] == static_cast<value_type>(N-1)); 65 assert(std::is_sorted(ia, ia+N)); 66 } 67 delete [] ia; 68 } 69 70 template <class Iter> 71 void 72 test(unsigned N) 73 { 74 test_one<Iter>(N, 0); 75 test_one<Iter>(N, N/4); 76 test_one<Iter>(N, N/2); 77 test_one<Iter>(N, 3*N/4); 78 test_one<Iter>(N, N); 79 } 80 81 template <class Iter> 82 void 83 test() 84 { 85 test_one<Iter>(0, 0); 86 test_one<Iter>(1, 0); 87 test_one<Iter>(1, 1); 88 test_one<Iter>(2, 0); 89 test_one<Iter>(2, 1); 90 test_one<Iter>(2, 2); 91 test_one<Iter>(3, 0); 92 test_one<Iter>(3, 1); 93 test_one<Iter>(3, 2); 94 test_one<Iter>(3, 3); 95 test<Iter>(4); 96 test<Iter>(100); 97 test<Iter>(1000); 98 } 99 100 int main() 101 { 102 test<bidirectional_iterator<int*> >(); 103 test<random_access_iterator<int*> >(); 104 test<int*>(); 105 106 #if TEST_STD_VER >= 11 107 test<bidirectional_iterator<S*> >(); 108 test<random_access_iterator<S*> >(); 109 test<S*>(); 110 #endif // TEST_STD_VER >= 11 111 } 112