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 // <deque> 11 12 // template <class InputIterator> 13 // iterator insert (const_iterator p, InputIterator f, InputIterator l); 14 15 #include <deque> 16 #include <cassert> 17 18 #include "test_iterators.h" 19 #include "../../../MoveOnly.h" 20 #include "../../../stack_allocator.h" 21 #include "min_allocator.h" 22 23 template <class C> 24 C 25 make(int size, int start = 0 ) 26 { 27 const int b = 4096 / sizeof(int); 28 int init = 0; 29 if (start > 0) 30 { 31 init = (start+1) / b + ((start+1) % b != 0); 32 init *= b; 33 --init; 34 } 35 C c(init, 0); 36 for (int i = 0; i < init-start; ++i) 37 c.pop_back(); 38 for (int i = 0; i < size; ++i) 39 c.push_back(i); 40 for (int i = 0; i < start; ++i) 41 c.pop_front(); 42 return c; 43 }; 44 45 template <class C> 46 void 47 test(int P, C& c1, const C& c2) 48 { 49 typedef typename C::iterator I; 50 typedef typename C::const_iterator CI; 51 typedef bidirectional_iterator<CI> BCI; 52 std::size_t c1_osize = c1.size(); 53 CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end())); 54 assert(i == c1.begin() + P); 55 assert(c1.size() == c1_osize + c2.size()); 56 assert(distance(c1.begin(), c1.end()) == c1.size()); 57 i = c1.begin(); 58 for (int j = 0; j < P; ++j, ++i) 59 assert(*i == j); 60 for (int j = 0; j < c2.size(); ++j, ++i) 61 assert(*i == j); 62 for (int j = P; j < c1_osize; ++j, ++i) 63 assert(*i == j); 64 } 65 66 template <class C> 67 void 68 testN(int start, int N, int M) 69 { 70 typedef typename C::iterator I; 71 typedef typename C::const_iterator CI; 72 for (int i = 0; i <= 3; ++i) 73 { 74 if (0 <= i && i <= N) 75 { 76 C c1 = make<C>(N, start); 77 C c2 = make<C>(M); 78 test(i, c1, c2); 79 } 80 } 81 for (int i = M-1; i <= M+1; ++i) 82 { 83 if (0 <= i && i <= N) 84 { 85 C c1 = make<C>(N, start); 86 C c2 = make<C>(M); 87 test(i, c1, c2); 88 } 89 } 90 for (int i = N/2-1; i <= N/2+1; ++i) 91 { 92 if (0 <= i && i <= N) 93 { 94 C c1 = make<C>(N, start); 95 C c2 = make<C>(M); 96 test(i, c1, c2); 97 } 98 } 99 for (int i = N - M - 1; i <= N - M + 1; ++i) 100 { 101 if (0 <= i && i <= N) 102 { 103 C c1 = make<C>(N, start); 104 C c2 = make<C>(M); 105 test(i, c1, c2); 106 } 107 } 108 for (int i = N - M - 1; i <= N - M + 1; ++i) 109 { 110 if (0 <= i && i <= N) 111 { 112 C c1 = make<C>(N, start); 113 C c2 = make<C>(M); 114 test(i, c1, c2); 115 } 116 } 117 for (int i = N - 3; i <= N; ++i) 118 { 119 if (0 <= i && i <= N) 120 { 121 C c1 = make<C>(N, start); 122 C c2 = make<C>(M); 123 test(i, c1, c2); 124 } 125 } 126 } 127 128 template <class C> 129 void 130 testI(int P, C& c1, const C& c2) 131 { 132 typedef typename C::iterator I; 133 typedef typename C::const_iterator CI; 134 typedef input_iterator<CI> ICI; 135 std::size_t c1_osize = c1.size(); 136 CI i = c1.insert(c1.begin() + P, ICI(c2.begin()), ICI(c2.end())); 137 assert(i == c1.begin() + P); 138 assert(c1.size() == c1_osize + c2.size()); 139 assert(distance(c1.begin(), c1.end()) == c1.size()); 140 i = c1.begin(); 141 for (int j = 0; j < P; ++j, ++i) 142 assert(*i == j); 143 for (int j = 0; j < c2.size(); ++j, ++i) 144 assert(*i == j); 145 for (int j = P; j < c1_osize; ++j, ++i) 146 assert(*i == j); 147 } 148 149 template <class C> 150 void 151 testNI(int start, int N, int M) 152 { 153 typedef typename C::iterator I; 154 typedef typename C::const_iterator CI; 155 for (int i = 0; i <= 3; ++i) 156 { 157 if (0 <= i && i <= N) 158 { 159 C c1 = make<C>(N, start); 160 C c2 = make<C>(M); 161 testI(i, c1, c2); 162 } 163 } 164 for (int i = M-1; i <= M+1; ++i) 165 { 166 if (0 <= i && i <= N) 167 { 168 C c1 = make<C>(N, start); 169 C c2 = make<C>(M); 170 testI(i, c1, c2); 171 } 172 } 173 for (int i = N/2-1; i <= N/2+1; ++i) 174 { 175 if (0 <= i && i <= N) 176 { 177 C c1 = make<C>(N, start); 178 C c2 = make<C>(M); 179 testI(i, c1, c2); 180 } 181 } 182 for (int i = N - M - 1; i <= N - M + 1; ++i) 183 { 184 if (0 <= i && i <= N) 185 { 186 C c1 = make<C>(N, start); 187 C c2 = make<C>(M); 188 testI(i, c1, c2); 189 } 190 } 191 for (int i = N - 3; i <= N; ++i) 192 { 193 if (0 <= i && i <= N) 194 { 195 C c1 = make<C>(N, start); 196 C c2 = make<C>(M); 197 testI(i, c1, c2); 198 } 199 } 200 } 201 202 template <class C> 203 void 204 test_move() 205 { 206 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 207 C c; 208 typedef typename C::const_iterator CI; 209 { 210 MoveOnly mo(0); 211 typedef MoveOnly* I; 212 c.insert(c.end(), std::move_iterator<I>(&mo), std::move_iterator<I>(&mo+1)); 213 } 214 int j = 0; 215 for (CI i = c.begin(); i != c.end(); ++i, ++j) 216 assert(*i == MoveOnly(j)); 217 { 218 MoveOnly mo(1); 219 typedef input_iterator<MoveOnly*> I; 220 c.insert(c.end(), std::move_iterator<I>(I(&mo)), std::move_iterator<I>(I(&mo+1))); 221 } 222 j = 0; 223 for (CI i = c.begin(); i != c.end(); ++i, ++j) 224 assert(*i == MoveOnly(j)); 225 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 226 } 227 228 int main() 229 { 230 { 231 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049}; 232 const int N = sizeof(rng)/sizeof(rng[0]); 233 for (int i = 0; i < N; ++i) 234 for (int j = 0; j < N; ++j) 235 for (int k = 0; k < N; ++k) 236 testN<std::deque<int> >(rng[i], rng[j], rng[k]); 237 testNI<std::deque<int> >(1500, 2000, 1000); 238 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 239 test_move<std::deque<MoveOnly, stack_allocator<MoveOnly, 2000> > >(); 240 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 241 } 242 #if __cplusplus >= 201103L 243 { 244 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049}; 245 const int N = sizeof(rng)/sizeof(rng[0]); 246 for (int i = 0; i < N; ++i) 247 for (int j = 0; j < N; ++j) 248 for (int k = 0; k < N; ++k) 249 testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j], rng[k]); 250 testNI<std::deque<int> >(1500, 2000, 1000); 251 test_move<std::deque<MoveOnly, min_allocator<MoveOnly> > >(); 252 } 253 #endif 254 } 255
