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