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