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// Optimization for deque::iterators
13
14// template <class InputIterator, class OutputIterator>
15//   OutputIterator
16//   move_backward(InputIterator first, InputIterator last, OutputIterator result);
17
18#include <deque>
19#include <cassert>
20
21#include "test_iterators.h"
22#include "min_allocator.h"
23
24template <class C>
25C
26make(int size, int start = 0 )
27{
28    const int b = 4096 / sizeof(int);
29    int init = 0;
30    if (start > 0)
31    {
32        init = (start+1) / b + ((start+1) % b != 0);
33        init *= b;
34        --init;
35    }
36    C c(init, 0);
37    for (int i = 0; i < init-start; ++i)
38        c.pop_back();
39    for (int i = 0; i < size; ++i)
40        c.push_back(i);
41    for (int i = 0; i < start; ++i)
42        c.pop_front();
43    return c;
44};
45
46template <class C>
47void testN(int start, int N)
48{
49    typedef typename C::iterator I;
50    typedef typename C::const_iterator CI;
51    typedef random_access_iterator<I> RAI;
52    typedef random_access_iterator<CI> RACI;
53    C c1 = make<C>(N, start);
54    C c2 = make<C>(N);
55    assert(std::move_backward(c1.cbegin(), c1.cend(), c2.end()) == c2.begin());
56    assert(c1 == c2);
57    assert(std::move_backward(c2.cbegin(), c2.cend(), c1.end()) == c1.begin());
58    assert(c1 == c2);
59    assert(std::move_backward(c1.cbegin(), c1.cend(), RAI(c2.end())) == RAI(c2.begin()));
60    assert(c1 == c2);
61    assert(std::move_backward(c2.cbegin(), c2.cend(), RAI(c1.end())) == RAI(c1.begin()));
62    assert(c1 == c2);
63    assert(std::move_backward(RACI(c1.cbegin()), RACI(c1.cend()), c2.end()) == c2.begin());
64    assert(c1 == c2);
65    assert(std::move_backward(RACI(c2.cbegin()), RACI(c2.cend()), c1.end()) == c1.begin());
66    assert(c1 == c2);
67}
68
69int main()
70{
71    {
72    int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
73    const int N = sizeof(rng)/sizeof(rng[0]);
74    for (int i = 0; i < N; ++i)
75        for (int j = 0; j < N; ++j)
76            testN<std::deque<int> >(rng[i], rng[j]);
77    }
78#if __cplusplus >= 201103L
79    {
80    int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
81    const int N = sizeof(rng)/sizeof(rng[0]);
82    for (int i = 0; i < N; ++i)
83        for (int j = 0; j < N; ++j)
84            testN<std::deque<int, min_allocator<int> > >(rng[i], rng[j]);
85    }
86#endif
87}
88