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// <set>
11
12// class set
13
14//       iterator lower_bound(const key_type& k);
15// const_iterator lower_bound(const key_type& k) const;
16
17#include <set>
18#include <cassert>
19
20#include "test_macros.h"
21#include "min_allocator.h"
22#include "private_constructor.hpp"
23
24int main()
25{
26    {
27    typedef int V;
28    typedef std::set<int> M;
29    {
30        typedef M::iterator R;
31        V ar[] =
32        {
33            5,
34            7,
35            9,
36            11,
37            13,
38            15,
39            17,
40            19
41        };
42        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
43        R r = m.lower_bound(5);
44        assert(r == m.begin());
45        r = m.lower_bound(7);
46        assert(r == next(m.begin()));
47        r = m.lower_bound(9);
48        assert(r == next(m.begin(), 2));
49        r = m.lower_bound(11);
50        assert(r == next(m.begin(), 3));
51        r = m.lower_bound(13);
52        assert(r == next(m.begin(), 4));
53        r = m.lower_bound(15);
54        assert(r == next(m.begin(), 5));
55        r = m.lower_bound(17);
56        assert(r == next(m.begin(), 6));
57        r = m.lower_bound(19);
58        assert(r == next(m.begin(), 7));
59        r = m.lower_bound(4);
60        assert(r == next(m.begin(), 0));
61        r = m.lower_bound(6);
62        assert(r == next(m.begin(), 1));
63        r = m.lower_bound(8);
64        assert(r == next(m.begin(), 2));
65        r = m.lower_bound(10);
66        assert(r == next(m.begin(), 3));
67        r = m.lower_bound(12);
68        assert(r == next(m.begin(), 4));
69        r = m.lower_bound(14);
70        assert(r == next(m.begin(), 5));
71        r = m.lower_bound(16);
72        assert(r == next(m.begin(), 6));
73        r = m.lower_bound(18);
74        assert(r == next(m.begin(), 7));
75        r = m.lower_bound(20);
76        assert(r == next(m.begin(), 8));
77    }
78    {
79        typedef M::const_iterator R;
80        V ar[] =
81        {
82            5,
83            7,
84            9,
85            11,
86            13,
87            15,
88            17,
89            19
90        };
91        const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
92        R r = m.lower_bound(5);
93        assert(r == m.begin());
94        r = m.lower_bound(7);
95        assert(r == next(m.begin()));
96        r = m.lower_bound(9);
97        assert(r == next(m.begin(), 2));
98        r = m.lower_bound(11);
99        assert(r == next(m.begin(), 3));
100        r = m.lower_bound(13);
101        assert(r == next(m.begin(), 4));
102        r = m.lower_bound(15);
103        assert(r == next(m.begin(), 5));
104        r = m.lower_bound(17);
105        assert(r == next(m.begin(), 6));
106        r = m.lower_bound(19);
107        assert(r == next(m.begin(), 7));
108        r = m.lower_bound(4);
109        assert(r == next(m.begin(), 0));
110        r = m.lower_bound(6);
111        assert(r == next(m.begin(), 1));
112        r = m.lower_bound(8);
113        assert(r == next(m.begin(), 2));
114        r = m.lower_bound(10);
115        assert(r == next(m.begin(), 3));
116        r = m.lower_bound(12);
117        assert(r == next(m.begin(), 4));
118        r = m.lower_bound(14);
119        assert(r == next(m.begin(), 5));
120        r = m.lower_bound(16);
121        assert(r == next(m.begin(), 6));
122        r = m.lower_bound(18);
123        assert(r == next(m.begin(), 7));
124        r = m.lower_bound(20);
125        assert(r == next(m.begin(), 8));
126    }
127    }
128#if TEST_STD_VER >= 11
129    {
130    typedef int V;
131    typedef std::set<int, std::less<int>, min_allocator<int>> M;
132    {
133        typedef M::iterator R;
134        V ar[] =
135        {
136            5,
137            7,
138            9,
139            11,
140            13,
141            15,
142            17,
143            19
144        };
145        M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
146        R r = m.lower_bound(5);
147        assert(r == m.begin());
148        r = m.lower_bound(7);
149        assert(r == next(m.begin()));
150        r = m.lower_bound(9);
151        assert(r == next(m.begin(), 2));
152        r = m.lower_bound(11);
153        assert(r == next(m.begin(), 3));
154        r = m.lower_bound(13);
155        assert(r == next(m.begin(), 4));
156        r = m.lower_bound(15);
157        assert(r == next(m.begin(), 5));
158        r = m.lower_bound(17);
159        assert(r == next(m.begin(), 6));
160        r = m.lower_bound(19);
161        assert(r == next(m.begin(), 7));
162        r = m.lower_bound(4);
163        assert(r == next(m.begin(), 0));
164        r = m.lower_bound(6);
165        assert(r == next(m.begin(), 1));
166        r = m.lower_bound(8);
167        assert(r == next(m.begin(), 2));
168        r = m.lower_bound(10);
169        assert(r == next(m.begin(), 3));
170        r = m.lower_bound(12);
171        assert(r == next(m.begin(), 4));
172        r = m.lower_bound(14);
173        assert(r == next(m.begin(), 5));
174        r = m.lower_bound(16);
175        assert(r == next(m.begin(), 6));
176        r = m.lower_bound(18);
177        assert(r == next(m.begin(), 7));
178        r = m.lower_bound(20);
179        assert(r == next(m.begin(), 8));
180    }
181    {
182        typedef M::const_iterator R;
183        V ar[] =
184        {
185            5,
186            7,
187            9,
188            11,
189            13,
190            15,
191            17,
192            19
193        };
194        const M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
195        R r = m.lower_bound(5);
196        assert(r == m.begin());
197        r = m.lower_bound(7);
198        assert(r == next(m.begin()));
199        r = m.lower_bound(9);
200        assert(r == next(m.begin(), 2));
201        r = m.lower_bound(11);
202        assert(r == next(m.begin(), 3));
203        r = m.lower_bound(13);
204        assert(r == next(m.begin(), 4));
205        r = m.lower_bound(15);
206        assert(r == next(m.begin(), 5));
207        r = m.lower_bound(17);
208        assert(r == next(m.begin(), 6));
209        r = m.lower_bound(19);
210        assert(r == next(m.begin(), 7));
211        r = m.lower_bound(4);
212        assert(r == next(m.begin(), 0));
213        r = m.lower_bound(6);
214        assert(r == next(m.begin(), 1));
215        r = m.lower_bound(8);
216        assert(r == next(m.begin(), 2));
217        r = m.lower_bound(10);
218        assert(r == next(m.begin(), 3));
219        r = m.lower_bound(12);
220        assert(r == next(m.begin(), 4));
221        r = m.lower_bound(14);
222        assert(r == next(m.begin(), 5));
223        r = m.lower_bound(16);
224        assert(r == next(m.begin(), 6));
225        r = m.lower_bound(18);
226        assert(r == next(m.begin(), 7));
227        r = m.lower_bound(20);
228        assert(r == next(m.begin(), 8));
229    }
230    }
231#endif
232#if TEST_STD_VER > 11
233    {
234    typedef int V;
235    typedef std::set<V, std::less<>> M;
236    typedef M::iterator R;
237
238    V ar[] =
239    {
240        5,
241        7,
242        9,
243        11,
244        13,
245        15,
246        17,
247        19
248    };
249    M m(ar, ar+sizeof(ar)/sizeof(ar[0]));
250    R r = m.lower_bound(5);
251    assert(r == m.begin());
252    r = m.lower_bound(7);
253    assert(r == next(m.begin()));
254    r = m.lower_bound(9);
255    assert(r == next(m.begin(), 2));
256    r = m.lower_bound(11);
257    assert(r == next(m.begin(), 3));
258    r = m.lower_bound(13);
259    assert(r == next(m.begin(), 4));
260    r = m.lower_bound(15);
261    assert(r == next(m.begin(), 5));
262    r = m.lower_bound(17);
263    assert(r == next(m.begin(), 6));
264    r = m.lower_bound(19);
265    assert(r == next(m.begin(), 7));
266    r = m.lower_bound(4);
267    assert(r == next(m.begin(), 0));
268    r = m.lower_bound(6);
269    assert(r == next(m.begin(), 1));
270    r = m.lower_bound(8);
271    assert(r == next(m.begin(), 2));
272    r = m.lower_bound(10);
273    assert(r == next(m.begin(), 3));
274    r = m.lower_bound(12);
275    assert(r == next(m.begin(), 4));
276    r = m.lower_bound(14);
277    assert(r == next(m.begin(), 5));
278    r = m.lower_bound(16);
279    assert(r == next(m.begin(), 6));
280    r = m.lower_bound(18);
281    assert(r == next(m.begin(), 7));
282    r = m.lower_bound(20);
283    assert(r == next(m.begin(), 8));
284    }
285
286    {
287    typedef PrivateConstructor V;
288    typedef std::set<V, std::less<>> M;
289    typedef M::iterator R;
290
291    M m;
292    m.insert ( V::make ( 5 ));
293    m.insert ( V::make ( 7 ));
294    m.insert ( V::make ( 9 ));
295    m.insert ( V::make ( 11 ));
296    m.insert ( V::make ( 13 ));
297    m.insert ( V::make ( 15 ));
298    m.insert ( V::make ( 17 ));
299    m.insert ( V::make ( 19 ));
300
301    R r = m.lower_bound(5);
302    assert(r == m.begin());
303    r = m.lower_bound(7);
304    assert(r == next(m.begin()));
305    r = m.lower_bound(9);
306    assert(r == next(m.begin(), 2));
307    r = m.lower_bound(11);
308    assert(r == next(m.begin(), 3));
309    r = m.lower_bound(13);
310    assert(r == next(m.begin(), 4));
311    r = m.lower_bound(15);
312    assert(r == next(m.begin(), 5));
313    r = m.lower_bound(17);
314    assert(r == next(m.begin(), 6));
315    r = m.lower_bound(19);
316    assert(r == next(m.begin(), 7));
317    r = m.lower_bound(4);
318    assert(r == next(m.begin(), 0));
319    r = m.lower_bound(6);
320    assert(r == next(m.begin(), 1));
321    r = m.lower_bound(8);
322    assert(r == next(m.begin(), 2));
323    r = m.lower_bound(10);
324    assert(r == next(m.begin(), 3));
325    r = m.lower_bound(12);
326    assert(r == next(m.begin(), 4));
327    r = m.lower_bound(14);
328    assert(r == next(m.begin(), 5));
329    r = m.lower_bound(16);
330    assert(r == next(m.begin(), 6));
331    r = m.lower_bound(18);
332    assert(r == next(m.begin(), 7));
333    r = m.lower_bound(20);
334    assert(r == next(m.begin(), 8));
335    }
336#endif
337
338}
339