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// <algorithm>
11
12// template<ForwardIterator Iter, class T>
13//   requires HasLess<T, Iter::value_type>
14//   Iter
15//   upper_bound(Iter first, Iter last, const T& value);
16
17#include <algorithm>
18#include <vector>
19#include <cassert>
20
21#include "test_iterators.h"
22
23template <class Iter, class T>
24void
25test(Iter first, Iter last, const T& value)
26{
27    Iter i = std::upper_bound(first, last, value);
28    for (Iter j = first; j != i; ++j)
29        assert(!(value < *j));
30    for (Iter j = i; j != last; ++j)
31        assert(value < *j);
32}
33
34template <class Iter>
35void
36test()
37{
38    const unsigned N = 1000;
39    const unsigned M = 10;
40    std::vector<int> v(N);
41    int x = 0;
42    for (int i = 0; i < v.size(); ++i)
43    {
44        v[i] = x;
45        if (++x == M)
46            x = 0;
47    }
48    std::sort(v.begin(), v.end());
49    for (x = 0; x <= M; ++x)
50        test(Iter(v.data()), Iter(v.data()+v.size()), x);
51}
52
53int main()
54{
55    int d[] = {0, 1, 2, 3};
56    for (int* e = d; e <= d+4; ++e)
57        for (int x = -1; x <= 4; ++x)
58            test(d, e, x);
59
60    test<forward_iterator<const int*> >();
61    test<bidirectional_iterator<const int*> >();
62    test<random_access_iterator<const int*> >();
63    test<const int*>();
64}
65