Home | History | Annotate | Download | only in deque.modifiers
      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 // template <class InputIterator>
     15 //   iterator insert (const_iterator p, InputIterator f, InputIterator l);
     16 
     17 #include <deque>
     18 #include <cassert>
     19 #include <cstddef>
     20 
     21 #include "test_macros.h"
     22 #include "test_iterators.h"
     23 #include "MoveOnly.h"
     24 #include "test_allocator.h"
     25 #include "min_allocator.h"
     26 
     27 template <class C>
     28 C
     29 make(int size, int start = 0 )
     30 {
     31     const int b = 4096 / sizeof(int);
     32     int init = 0;
     33     if (start > 0)
     34     {
     35         init = (start+1) / b + ((start+1) % b != 0);
     36         init *= b;
     37         --init;
     38     }
     39     C c(init, 0);
     40     for (int i = 0; i < init-start; ++i)
     41         c.pop_back();
     42     for (int i = 0; i < size; ++i)
     43         c.push_back(i);
     44     for (int i = 0; i < start; ++i)
     45         c.pop_front();
     46     return c;
     47 }
     48 
     49 template <class C>
     50 void
     51 test(int P, const C& c0, const C& c2)
     52 {
     53     {
     54     typedef typename C::const_iterator CI;
     55     typedef input_iterator<CI> BCI;
     56     C c1 = c0;
     57     std::size_t c1_osize = c1.size();
     58     CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
     59     assert(i == c1.begin() + P);
     60     assert(c1.size() == c1_osize + c2.size());
     61     assert(static_cast<std::size_t>(distance(c1.begin(), c1.end())) == c1.size());
     62     i = c1.begin();
     63     for (int j = 0; j < P; ++j, ++i)
     64         assert(*i == j);
     65     for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
     66         assert(*i == j);
     67     for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
     68         assert(*i == j);
     69     }
     70     {
     71     typedef typename C::const_iterator CI;
     72     typedef forward_iterator<CI> BCI;
     73     C c1 = c0;
     74     std::size_t c1_osize = c1.size();
     75     CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
     76     assert(i == c1.begin() + P);
     77     assert(c1.size() == c1_osize + c2.size());
     78     assert(static_cast<std::size_t>(distance(c1.begin(), c1.end())) == c1.size());
     79     i = c1.begin();
     80     for (int j = 0; j < P; ++j, ++i)
     81         assert(*i == j);
     82     for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
     83         assert(*i == j);
     84     for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
     85         assert(*i == j);
     86     }
     87     {
     88     typedef typename C::const_iterator CI;
     89     typedef bidirectional_iterator<CI> BCI;
     90     C c1 = c0;
     91     std::size_t c1_osize = c1.size();
     92     CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
     93     assert(i == c1.begin() + P);
     94     assert(c1.size() == c1_osize + c2.size());
     95     assert(static_cast<std::size_t>(distance(c1.begin(), c1.end())) == c1.size());
     96     i = c1.begin();
     97     for (int j = 0; j < P; ++j, ++i)
     98         assert(*i == j);
     99     for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
    100         assert(*i == j);
    101     for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
    102         assert(*i == j);
    103     }
    104 }
    105 
    106 template <class C>
    107 void
    108 testN(int start, int N, int M)
    109 {
    110     for (int i = 0; i <= 3; ++i)
    111     {
    112         if (0 <= i && i <= N)
    113         {
    114             C c1 = make<C>(N, start);
    115             C c2 = make<C>(M);
    116             test(i, c1, c2);
    117         }
    118     }
    119     for (int i = M-1; i <= M+1; ++i)
    120     {
    121         if (0 <= i && i <= N)
    122         {
    123             C c1 = make<C>(N, start);
    124             C c2 = make<C>(M);
    125             test(i, c1, c2);
    126         }
    127     }
    128     for (int i = N/2-1; i <= N/2+1; ++i)
    129     {
    130         if (0 <= i && i <= N)
    131         {
    132             C c1 = make<C>(N, start);
    133             C c2 = make<C>(M);
    134             test(i, c1, c2);
    135         }
    136     }
    137     for (int i = N - M - 1; i <= N - M + 1; ++i)
    138     {
    139         if (0 <= i && i <= N)
    140         {
    141             C c1 = make<C>(N, start);
    142             C c2 = make<C>(M);
    143             test(i, c1, c2);
    144         }
    145     }
    146     for (int i = N - M - 1; i <= N - M + 1; ++i)
    147     {
    148         if (0 <= i && i <= N)
    149         {
    150             C c1 = make<C>(N, start);
    151             C c2 = make<C>(M);
    152             test(i, c1, c2);
    153         }
    154     }
    155     for (int i = N - 3; i <= N; ++i)
    156     {
    157         if (0 <= i && i <= N)
    158         {
    159             C c1 = make<C>(N, start);
    160             C c2 = make<C>(M);
    161             test(i, c1, c2);
    162         }
    163     }
    164 }
    165 
    166 template <class C>
    167 void
    168 testI(int P, C& c1, const C& c2)
    169 {
    170     typedef typename C::const_iterator CI;
    171     typedef input_iterator<CI> ICI;
    172     std::size_t c1_osize = c1.size();
    173     CI i = c1.insert(c1.begin() + P, ICI(c2.begin()), ICI(c2.end()));
    174     assert(i == c1.begin() + P);
    175     assert(c1.size() == c1_osize + c2.size());
    176     assert(static_cast<std::size_t>(distance(c1.begin(), c1.end())) == c1.size());
    177     i = c1.begin();
    178     for (int j = 0; j < P; ++j, ++i)
    179         assert(*i == j);
    180     for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
    181         assert(*i == j);
    182     for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
    183         assert(*i == j);
    184 }
    185 
    186 template <class C>
    187 void
    188 testNI(int start, int N, int M)
    189 {
    190     for (int i = 0; i <= 3; ++i)
    191     {
    192         if (0 <= i && i <= N)
    193         {
    194             C c1 = make<C>(N, start);
    195             C c2 = make<C>(M);
    196             testI(i, c1, c2);
    197         }
    198     }
    199     for (int i = M-1; i <= M+1; ++i)
    200     {
    201         if (0 <= i && i <= N)
    202         {
    203             C c1 = make<C>(N, start);
    204             C c2 = make<C>(M);
    205             testI(i, c1, c2);
    206         }
    207     }
    208     for (int i = N/2-1; i <= N/2+1; ++i)
    209     {
    210         if (0 <= i && i <= N)
    211         {
    212             C c1 = make<C>(N, start);
    213             C c2 = make<C>(M);
    214             testI(i, c1, c2);
    215         }
    216     }
    217     for (int i = N - M - 1; i <= N - M + 1; ++i)
    218     {
    219         if (0 <= i && i <= N)
    220         {
    221             C c1 = make<C>(N, start);
    222             C c2 = make<C>(M);
    223             testI(i, c1, c2);
    224         }
    225     }
    226     for (int i = N - 3; i <= N; ++i)
    227     {
    228         if (0 <= i && i <= N)
    229         {
    230             C c1 = make<C>(N, start);
    231             C c2 = make<C>(M);
    232             testI(i, c1, c2);
    233         }
    234     }
    235 }
    236 
    237 template <class C>
    238 void
    239 test_move()
    240 {
    241 #if TEST_STD_VER >= 11
    242     C c;
    243     typedef typename C::const_iterator CI;
    244     {
    245         MoveOnly mo(0);
    246         typedef MoveOnly* I;
    247         c.insert(c.end(), std::move_iterator<I>(&mo), std::move_iterator<I>(&mo+1));
    248     }
    249     int j = 0;
    250     for (CI i = c.begin(); i != c.end(); ++i, ++j)
    251         assert(*i == MoveOnly(j));
    252     {
    253         MoveOnly mo(1);
    254         typedef input_iterator<MoveOnly*> I;
    255         c.insert(c.end(), std::move_iterator<I>(I(&mo)), std::move_iterator<I>(I(&mo+1)));
    256     }
    257     j = 0;
    258     for (CI i = c.begin(); i != c.end(); ++i, ++j)
    259         assert(*i == MoveOnly(j));
    260 #endif
    261 }
    262 
    263 int main()
    264 {
    265     {
    266     int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
    267     const int N = sizeof(rng)/sizeof(rng[0]);
    268     for (int i = 0; i < N; ++i)
    269         for (int j = 0; j < N; ++j)
    270             for (int k = 0; k < N; ++k)
    271                 testN<std::deque<int> >(rng[i], rng[j], rng[k]);
    272     testNI<std::deque<int> >(1500, 2000, 1000);
    273 #if TEST_STD_VER >= 11
    274     test_move<std::deque<MoveOnly, limited_allocator<MoveOnly, 2000> > >();
    275 #endif
    276     }
    277 #if TEST_STD_VER >= 11
    278     {
    279     int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
    280     const int N = sizeof(rng)/sizeof(rng[0]);
    281     for (int i = 0; i < N; ++i)
    282         for (int j = 0; j < N; ++j)
    283             for (int k = 0; k < N; ++k)
    284                 testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j], rng[k]);
    285     testNI<std::deque<int> >(1500, 2000, 1000);
    286     test_move<std::deque<MoveOnly, min_allocator<MoveOnly> > >();
    287     }
    288 #endif
    289 }
    290