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