Home | History | Annotate | Download | only in alg.partitions
      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<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>
     13 //   requires ShuffleIterator<Iter>
     14 //         && CopyConstructible<Pred>
     15 //   Iter
     16 //   stable_partition(Iter first, Iter last, Pred pred);
     17 
     18 #include <algorithm>
     19 #include <cassert>
     20 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
     21 #include <memory>
     22 #endif
     23 
     24 #include "test_iterators.h"
     25 
     26 struct is_odd
     27 {
     28     bool operator()(const int& i) const {return i & 1;}
     29 };
     30 
     31 struct odd_first
     32 {
     33     bool operator()(const std::pair<int,int>& p) const
     34         {return p.first & 1;}
     35 };
     36 
     37 template <class Iter>
     38 void
     39 test()
     40 {
     41     {  // check mixed
     42     typedef std::pair<int,int> P;
     43     P array[] =
     44     {
     45         P(0, 1),
     46         P(0, 2),
     47         P(1, 1),
     48         P(1, 2),
     49         P(2, 1),
     50         P(2, 2),
     51         P(3, 1),
     52         P(3, 2),
     53         P(4, 1),
     54         P(4, 2)
     55     };
     56     const unsigned size = sizeof(array)/sizeof(array[0]);
     57     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
     58     assert(base(r) == array + 4);
     59     assert(array[0] == P(1, 1));
     60     assert(array[1] == P(1, 2));
     61     assert(array[2] == P(3, 1));
     62     assert(array[3] == P(3, 2));
     63     assert(array[4] == P(0, 1));
     64     assert(array[5] == P(0, 2));
     65     assert(array[6] == P(2, 1));
     66     assert(array[7] == P(2, 2));
     67     assert(array[8] == P(4, 1));
     68     assert(array[9] == P(4, 2));
     69     }
     70     {
     71     typedef std::pair<int,int> P;
     72     P array[] =
     73     {
     74         P(0, 1),
     75         P(0, 2),
     76         P(1, 1),
     77         P(1, 2),
     78         P(2, 1),
     79         P(2, 2),
     80         P(3, 1),
     81         P(3, 2),
     82         P(4, 1),
     83         P(4, 2)
     84     };
     85     const unsigned size = sizeof(array)/sizeof(array[0]);
     86     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
     87     assert(base(r) == array + 4);
     88     assert(array[0] == P(1, 1));
     89     assert(array[1] == P(1, 2));
     90     assert(array[2] == P(3, 1));
     91     assert(array[3] == P(3, 2));
     92     assert(array[4] == P(0, 1));
     93     assert(array[5] == P(0, 2));
     94     assert(array[6] == P(2, 1));
     95     assert(array[7] == P(2, 2));
     96     assert(array[8] == P(4, 1));
     97     assert(array[9] == P(4, 2));
     98     // check empty
     99     r = std::stable_partition(Iter(array), Iter(array), odd_first());
    100     assert(base(r) == array);
    101     // check one true
    102     r = std::stable_partition(Iter(array), Iter(array+1), odd_first());
    103     assert(base(r) == array+1);
    104     assert(array[0] == P(1, 1));
    105     // check one false
    106     r = std::stable_partition(Iter(array+4), Iter(array+5), odd_first());
    107     assert(base(r) == array+4);
    108     assert(array[4] == P(0, 1));
    109     }
    110     {  // check all false
    111     typedef std::pair<int,int> P;
    112     P array[] =
    113     {
    114         P(0, 1),
    115         P(0, 2),
    116         P(2, 1),
    117         P(2, 2),
    118         P(4, 1),
    119         P(4, 2),
    120         P(6, 1),
    121         P(6, 2),
    122         P(8, 1),
    123         P(8, 2)
    124     };
    125     const unsigned size = sizeof(array)/sizeof(array[0]);
    126     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
    127     assert(base(r) == array);
    128     assert(array[0] == P(0, 1));
    129     assert(array[1] == P(0, 2));
    130     assert(array[2] == P(2, 1));
    131     assert(array[3] == P(2, 2));
    132     assert(array[4] == P(4, 1));
    133     assert(array[5] == P(4, 2));
    134     assert(array[6] == P(6, 1));
    135     assert(array[7] == P(6, 2));
    136     assert(array[8] == P(8, 1));
    137     assert(array[9] == P(8, 2));
    138     }
    139     {  // check all true
    140     typedef std::pair<int,int> P;
    141     P array[] =
    142     {
    143         P(1, 1),
    144         P(1, 2),
    145         P(3, 1),
    146         P(3, 2),
    147         P(5, 1),
    148         P(5, 2),
    149         P(7, 1),
    150         P(7, 2),
    151         P(9, 1),
    152         P(9, 2)
    153     };
    154     const unsigned size = sizeof(array)/sizeof(array[0]);
    155     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
    156     assert(base(r) == array + size);
    157     assert(array[0] == P(1, 1));
    158     assert(array[1] == P(1, 2));
    159     assert(array[2] == P(3, 1));
    160     assert(array[3] == P(3, 2));
    161     assert(array[4] == P(5, 1));
    162     assert(array[5] == P(5, 2));
    163     assert(array[6] == P(7, 1));
    164     assert(array[7] == P(7, 2));
    165     assert(array[8] == P(9, 1));
    166     assert(array[9] == P(9, 2));
    167     }
    168     {  // check all false but first true
    169     typedef std::pair<int,int> P;
    170     P array[] =
    171     {
    172         P(1, 1),
    173         P(0, 2),
    174         P(2, 1),
    175         P(2, 2),
    176         P(4, 1),
    177         P(4, 2),
    178         P(6, 1),
    179         P(6, 2),
    180         P(8, 1),
    181         P(8, 2)
    182     };
    183     const unsigned size = sizeof(array)/sizeof(array[0]);
    184     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
    185     assert(base(r) == array + 1);
    186     assert(array[0] == P(1, 1));
    187     assert(array[1] == P(0, 2));
    188     assert(array[2] == P(2, 1));
    189     assert(array[3] == P(2, 2));
    190     assert(array[4] == P(4, 1));
    191     assert(array[5] == P(4, 2));
    192     assert(array[6] == P(6, 1));
    193     assert(array[7] == P(6, 2));
    194     assert(array[8] == P(8, 1));
    195     assert(array[9] == P(8, 2));
    196     }
    197     {  // check all false but last true
    198     typedef std::pair<int,int> P;
    199     P array[] =
    200     {
    201         P(0, 1),
    202         P(0, 2),
    203         P(2, 1),
    204         P(2, 2),
    205         P(4, 1),
    206         P(4, 2),
    207         P(6, 1),
    208         P(6, 2),
    209         P(8, 1),
    210         P(1, 2)
    211     };
    212     const unsigned size = sizeof(array)/sizeof(array[0]);
    213     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
    214     assert(base(r) == array + 1);
    215     assert(array[0] == P(1, 2));
    216     assert(array[1] == P(0, 1));
    217     assert(array[2] == P(0, 2));
    218     assert(array[3] == P(2, 1));
    219     assert(array[4] == P(2, 2));
    220     assert(array[5] == P(4, 1));
    221     assert(array[6] == P(4, 2));
    222     assert(array[7] == P(6, 1));
    223     assert(array[8] == P(6, 2));
    224     assert(array[9] == P(8, 1));
    225     }
    226     {  // check all true but first false
    227     typedef std::pair<int,int> P;
    228     P array[] =
    229     {
    230         P(0, 1),
    231         P(1, 2),
    232         P(3, 1),
    233         P(3, 2),
    234         P(5, 1),
    235         P(5, 2),
    236         P(7, 1),
    237         P(7, 2),
    238         P(9, 1),
    239         P(9, 2)
    240     };
    241     const unsigned size = sizeof(array)/sizeof(array[0]);
    242     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
    243     assert(base(r) == array + size-1);
    244     assert(array[0] == P(1, 2));
    245     assert(array[1] == P(3, 1));
    246     assert(array[2] == P(3, 2));
    247     assert(array[3] == P(5, 1));
    248     assert(array[4] == P(5, 2));
    249     assert(array[5] == P(7, 1));
    250     assert(array[6] == P(7, 2));
    251     assert(array[7] == P(9, 1));
    252     assert(array[8] == P(9, 2));
    253     assert(array[9] == P(0, 1));
    254     }
    255     {  // check all true but last false
    256     typedef std::pair<int,int> P;
    257     P array[] =
    258     {
    259         P(1, 1),
    260         P(1, 2),
    261         P(3, 1),
    262         P(3, 2),
    263         P(5, 1),
    264         P(5, 2),
    265         P(7, 1),
    266         P(7, 2),
    267         P(9, 1),
    268         P(0, 2)
    269     };
    270     const unsigned size = sizeof(array)/sizeof(array[0]);
    271     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
    272     assert(base(r) == array + size-1);
    273     assert(array[0] == P(1, 1));
    274     assert(array[1] == P(1, 2));
    275     assert(array[2] == P(3, 1));
    276     assert(array[3] == P(3, 2));
    277     assert(array[4] == P(5, 1));
    278     assert(array[5] == P(5, 2));
    279     assert(array[6] == P(7, 1));
    280     assert(array[7] == P(7, 2));
    281     assert(array[8] == P(9, 1));
    282     assert(array[9] == P(0, 2));
    283     }
    284 }
    285 
    286 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    287 
    288 struct is_null
    289 {
    290     template <class P>
    291         bool operator()(const P& p) {return p == 0;}
    292 };
    293 
    294 template <class Iter>
    295 void
    296 test1()
    297 {
    298     const unsigned size = 5;
    299     std::unique_ptr<int> array[size];
    300     Iter r = std::stable_partition(Iter(array), Iter(array+size), is_null());
    301 }
    302 
    303 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
    304 
    305 int main()
    306 {
    307     test<bidirectional_iterator<std::pair<int,int>*> >();
    308     test<random_access_iterator<std::pair<int,int>*> >();
    309     test<std::pair<int,int>*>();
    310 
    311 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    312     test1<bidirectional_iterator<std::unique_ptr<int>*> >();
    313 #endif
    314 }
    315