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//   copy(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    typedef input_iterator<CI> ICI;
54    C c1 = make<C>(N, start);
55    C c2 = make<C>(N);
56    assert(std::copy(c1.cbegin(), c1.cend(), c2.begin()) == c2.end());
57    assert(c1 == c2);
58    assert(std::copy(c2.cbegin(), c2.cend(), c1.begin()) == c1.end());
59    assert(c1 == c2);
60    assert(std::copy(c1.cbegin(), c1.cend(), RAI(c2.begin())) == RAI(c2.end()));
61    assert(c1 == c2);
62    assert(std::copy(c2.cbegin(), c2.cend(), RAI(c1.begin())) == RAI(c1.end()));
63    assert(c1 == c2);
64    assert(std::copy(RACI(c1.cbegin()), RACI(c1.cend()), c2.begin()) == c2.end());
65    assert(c1 == c2);
66    assert(std::copy(ICI(c2.cbegin()), ICI(c2.cend()), c1.begin()) == c1.end());
67    assert(c1 == c2);
68}
69
70int main()
71{
72    {
73    int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
74    const int N = sizeof(rng)/sizeof(rng[0]);
75    for (int i = 0; i < N; ++i)
76        for (int j = 0; j < N; ++j)
77            testN<std::deque<int> >(rng[i], rng[j]);
78    }
79#if __cplusplus >= 201103L
80    {
81    int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
82    const int N = sizeof(rng)/sizeof(rng[0]);
83    for (int i = 0; i < N; ++i)
84        for (int j = 0; j < N; ++j)
85            testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j]);
86    }
87#endif
88}
89