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 25struct 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 46std::mt19937 randomness; 47 48template <class Iter> 49void 50test_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 70template <class Iter> 71void 72test(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 81template <class Iter> 82void 83test() 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 100int 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