libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp

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