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