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
make(int size,int start=0)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
test(int P,C & c1,const C & c2)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
testN(int start,int N,int M)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
testI(int P,C & c1,const C & c2)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
testNI(int start,int N,int M)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
test_move()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
main()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