Home | History | Annotate | Download | only in set.intersection 
      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<InputIterator InIter1, InputIterator InIter2, typename OutIter>
     13 //   requires OutputIterator<OutIter, InIter1::reference>
     14 //         && OutputIterator<OutIter, InIter2::reference>
     15 //         && HasLess<InIter2::value_type, InIter1::value_type>
     16 //         && HasLess<InIter1::value_type, InIter2::value_type>
     17 //   constpexr OutIter       // constexpr after C++17
     18 //   set_intersection(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2,
     19 //                    OutIter result);
     20 
     21 #include <algorithm>
     22 #include <cassert>
     23 
     24 #include "test_macros.h"
     25 #include "test_iterators.h"
     26 
     27 #if TEST_STD_VER > 17
     28 TEST_CONSTEXPR bool test_constexpr() {
     29     const int ia[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
     30     const int ib[] = {2, 4, 4, 6};
     31           int results[std::size(ia)] = {0};
     32 
     33     auto it = std::set_intersection(std::begin(ia), std::end(ia),
     34                                     std::begin(ib), std::end(ib), std::begin(results));
     35 
     36     return std::includes(std::begin(ia), std::end(ia), std::begin(results), it)
     37         && std::includes(std::begin(ib), std::end(ib), std::begin(results), it)
     38         && std::is_sorted(std::begin(results), it)
     39         && std::all_of(it, std::end(results), [](int a) {return a == 0; })
     40            ;
     41     }
     42 #endif
     43 
     44 
     45 template <class Iter1, class Iter2, class OutIter>
     46 void
     47 test()
     48 {
     49     int ia[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
     50     const int sa = sizeof(ia)/sizeof(ia[0]);
     51     int ib[] = {2, 4, 4, 6};
     52     const int sb = sizeof(ib)/sizeof(ib[0]);
     53     int ic[20];
     54     int ir[] = {2, 4, 4};
     55     const int sr = sizeof(ir)/sizeof(ir[0]);
     56     OutIter ce = std::set_intersection(Iter1(ia), Iter1(ia+sa),
     57                                        Iter2(ib), Iter2(ib+sb), OutIter(ic));
     58     assert(base(ce) - ic == sr);
     59     assert(std::lexicographical_compare(ic, base(ce), ir, ir+sr) == 0);
     60     ce = std::set_intersection(Iter1(ib), Iter1(ib+sb),
     61                                Iter2(ia), Iter2(ia+sa), OutIter(ic));
     62     assert(base(ce) - ic == sr);
     63     assert(std::lexicographical_compare(ic, base(ce), ir, ir+sr) == 0);
     64 }
     65 
     66 int main()
     67 {
     68     test<input_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
     69     test<input_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >();
     70     test<input_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
     71     test<input_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
     72     test<input_iterator<const int*>, input_iterator<const int*>, int*>();
     73 
     74     test<input_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
     75     test<input_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
     76     test<input_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
     77     test<input_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
     78     test<input_iterator<const int*>, forward_iterator<const int*>, int*>();
     79 
     80     test<input_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
     81     test<input_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
     82     test<input_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
     83     test<input_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
     84     test<input_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
     85 
     86     test<input_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
     87     test<input_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
     88     test<input_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
     89     test<input_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
     90     test<input_iterator<const int*>, random_access_iterator<const int*>, int*>();
     91 
     92     test<input_iterator<const int*>, const int*, output_iterator<int*> >();
     93     test<input_iterator<const int*>, const int*, forward_iterator<int*> >();
     94     test<input_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
     95     test<input_iterator<const int*>, const int*, random_access_iterator<int*> >();
     96     test<input_iterator<const int*>, const int*, int*>();
     97 
     98     test<forward_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
     99     test<forward_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >();
    100     test<forward_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    101     test<forward_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
    102     test<forward_iterator<const int*>, input_iterator<const int*>, int*>();
    103 
    104     test<forward_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
    105     test<forward_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
    106     test<forward_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
    107     test<forward_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
    108     test<forward_iterator<const int*>, forward_iterator<const int*>, int*>();
    109 
    110     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
    111     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
    112     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
    113     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
    114     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
    115 
    116     test<forward_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
    117     test<forward_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
    118     test<forward_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
    119     test<forward_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
    120     test<forward_iterator<const int*>, random_access_iterator<const int*>, int*>();
    121 
    122     test<forward_iterator<const int*>, const int*, output_iterator<int*> >();
    123     test<forward_iterator<const int*>, const int*, forward_iterator<int*> >();
    124     test<forward_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
    125     test<forward_iterator<const int*>, const int*, random_access_iterator<int*> >();
    126     test<forward_iterator<const int*>, const int*, int*>();
    127 
    128     test<bidirectional_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
    129     test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    130     test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    131     test<bidirectional_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
    132     test<bidirectional_iterator<const int*>, input_iterator<const int*>, int*>();
    133 
    134     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
    135     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
    136     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
    137     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
    138     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, int*>();
    139 
    140     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
    141     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
    142     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
    143     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
    144     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
    145 
    146     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
    147     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
    148     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
    149     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
    150     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, int*>();
    151 
    152     test<bidirectional_iterator<const int*>, const int*, output_iterator<int*> >();
    153     test<bidirectional_iterator<const int*>, const int*, forward_iterator<int*> >();
    154     test<bidirectional_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
    155     test<bidirectional_iterator<const int*>, const int*, random_access_iterator<int*> >();
    156     test<bidirectional_iterator<const int*>, const int*, int*>();
    157 
    158     test<random_access_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
    159     test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    160     test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    161     test<random_access_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
    162     test<random_access_iterator<const int*>, input_iterator<const int*>, int*>();
    163 
    164     test<random_access_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
    165     test<random_access_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
    166     test<random_access_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
    167     test<random_access_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
    168     test<random_access_iterator<const int*>, forward_iterator<const int*>, int*>();
    169 
    170     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
    171     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
    172     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
    173     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
    174     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
    175 
    176     test<random_access_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
    177     test<random_access_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
    178     test<random_access_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
    179     test<random_access_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
    180     test<random_access_iterator<const int*>, random_access_iterator<const int*>, int*>();
    181 
    182     test<random_access_iterator<const int*>, const int*, output_iterator<int*> >();
    183     test<random_access_iterator<const int*>, const int*, forward_iterator<int*> >();
    184     test<random_access_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
    185     test<random_access_iterator<const int*>, const int*, random_access_iterator<int*> >();
    186     test<random_access_iterator<const int*>, const int*, int*>();
    187 
    188     test<const int*, input_iterator<const int*>, output_iterator<int*> >();
    189     test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >();
    190     test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >();
    191     test<const int*, input_iterator<const int*>, random_access_iterator<int*> >();
    192     test<const int*, input_iterator<const int*>, int*>();
    193 
    194     test<const int*, forward_iterator<const int*>, output_iterator<int*> >();
    195     test<const int*, forward_iterator<const int*>, forward_iterator<int*> >();
    196     test<const int*, forward_iterator<const int*>, bidirectional_iterator<int*> >();
    197     test<const int*, forward_iterator<const int*>, random_access_iterator<int*> >();
    198     test<const int*, forward_iterator<const int*>, int*>();
    199 
    200     test<const int*, bidirectional_iterator<const int*>, output_iterator<int*> >();
    201     test<const int*, bidirectional_iterator<const int*>, forward_iterator<int*> >();
    202     test<const int*, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
    203     test<const int*, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
    204     test<const int*, bidirectional_iterator<const int*>, int*>();
    205 
    206     test<const int*, random_access_iterator<const int*>, output_iterator<int*> >();
    207     test<const int*, random_access_iterator<const int*>, forward_iterator<int*> >();
    208     test<const int*, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
    209     test<const int*, random_access_iterator<const int*>, random_access_iterator<int*> >();
    210     test<const int*, random_access_iterator<const int*>, int*>();
    211 
    212     test<const int*, const int*, output_iterator<int*> >();
    213     test<const int*, const int*, forward_iterator<int*> >();
    214     test<const int*, const int*, bidirectional_iterator<int*> >();
    215     test<const int*, const int*, random_access_iterator<int*> >();
    216     test<const int*, const int*, int*>();
    217 
    218 #if TEST_STD_VER > 17
    219     static_assert(test_constexpr());
    220 #endif
    221 }
    222