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// REQUIRES: long_tests
11
12// <deque>
13
14// iterator insert (const_iterator p, size_type n, const value_type& v);
15
16#include <deque>
17#include <cassert>
18#include <cstddef>
19
20#include "test_macros.h"
21#include "min_allocator.h"
22
23template <class C>
24C
25make(int size, int start = 0 )
26{
27    const int b = 4096 / sizeof(int);
28    int init = 0;
29    if (start > 0)
30    {
31        init = (start+1) / b + ((start+1) % b != 0);
32        init *= b;
33        --init;
34    }
35    C c(init, 0);
36    for (int i = 0; i < init-start; ++i)
37        c.pop_back();
38    for (int i = 0; i < size; ++i)
39        c.push_back(i);
40    for (int i = 0; i < start; ++i)
41        c.pop_front();
42    return c;
43}
44
45template <class C>
46void
47test(int P, C& c1, int size, int x)
48{
49    typedef typename C::const_iterator CI;
50    std::size_t c1_osize = c1.size();
51    CI i = c1.insert(c1.begin() + P, size, x);
52    assert(i == c1.begin() + P);
53    assert(c1.size() == c1_osize + size);
54    assert(static_cast<std::size_t>(distance(c1.begin(), c1.end())) == c1.size());
55    i = c1.begin();
56    for (int j = 0; j < P; ++j, ++i)
57        assert(*i == j);
58    for (int j = 0; j < size; ++j, ++i)
59        assert(*i == x);
60    for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
61        assert(*i == j);
62}
63
64template <class C>
65void
66testN(int start, int N, int M)
67{
68    for (int i = 0; i <= 3; ++i)
69    {
70        if (0 <= i && i <= N)
71        {
72            C c1 = make<C>(N, start);
73            test(i, c1, M, -10);
74        }
75    }
76    for (int i = M-1; i <= M+1; ++i)
77    {
78        if (0 <= i && i <= N)
79        {
80            C c1 = make<C>(N, start);
81            test(i, c1, M, -10);
82        }
83    }
84    for (int i = N/2-1; i <= N/2+1; ++i)
85    {
86        if (0 <= i && i <= N)
87        {
88            C c1 = make<C>(N, start);
89            test(i, c1, M, -10);
90        }
91    }
92    for (int i = N - M - 1; i <= N - M + 1; ++i)
93    {
94        if (0 <= i && i <= N)
95        {
96            C c1 = make<C>(N, start);
97            test(i, c1, M, -10);
98        }
99    }
100    for (int i = N - 3; i <= N; ++i)
101    {
102        if (0 <= i && i <= N)
103        {
104            C c1 = make<C>(N, start);
105            test(i, c1, M, -10);
106        }
107    }
108}
109
110template <class C>
111void
112self_reference_test()
113{
114    typedef typename C::const_iterator CI;
115    for (int i = 0; i < 20; ++i)
116    {
117        for (int j = 0; j < 20; ++j)
118        {
119            C c = make<C>(20);
120            CI it = c.cbegin() + i;
121            CI jt = c.cbegin() + j;
122            c.insert(it, 5, *jt);
123            assert(c.size() == 25);
124            assert(static_cast<std::size_t>(distance(c.begin(), c.end())) == c.size());
125            it = c.cbegin();
126            for (int k = 0; k < i; ++k, ++it)
127                assert(*it == k);
128            for (int k = 0; k < 5; ++k, ++it)
129                assert(*it == j);
130            for (int k = i; k < 20; ++k, ++it)
131                assert(*it == k);
132        }
133    }
134}
135
136int main()
137{
138    {
139    int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
140    const int N = sizeof(rng)/sizeof(rng[0]);
141    for (int i = 0; i < N; ++i)
142        for (int j = 0; j < N; ++j)
143            for (int k = 0; k < N; ++k)
144                testN<std::deque<int> >(rng[i], rng[j], rng[k]);
145    self_reference_test<std::deque<int> >();
146    }
147#if TEST_STD_VER >= 11
148    {
149    int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
150    const int N = sizeof(rng)/sizeof(rng[0]);
151    for (int i = 0; i < N; ++i)
152        for (int j = 0; j < N; ++j)
153            for (int k = 0; k < N; ++k)
154                testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j], rng[k]);
155    self_reference_test<std::deque<int, min_allocator<int>> >();
156    }
157#endif
158}
159