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 #include <vector>
  21
  22 #include "count_new.h"
  23 #include "test_iterators.h"
  24 #include "test_macros.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 #if TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)
 285   // TODO: Re-enable this test once we're no longer using get_temporary_buffer().
 286   // For now it trips up GCC due to the use of always_inline.
 287 #if 0
 288   { // check that the algorithm still works when no memory is available
 289     std::vector<int> vec(150, 3);
 290     vec[5]                             = 6;
 291     getGlobalMemCounter()->throw_after = 0;
 292     std::stable_partition(vec.begin(), vec.end(), [](int i) { return i < 5; });
 293     assert(std::is_partitioned(vec.begin(), vec.end(), [](int i) { return i < 5; }));
 294     vec[5]                             = 6;
 295     getGlobalMemCounter()->throw_after = 0;
 296     std::stable_partition(
 297         forward_iterator<int*>(vec.data()), forward_iterator<int*>(vec.data() + vec.size()), [](int i) {
 298           return i < 5;
 299         });
 300     assert(std::is_partitioned(vec.begin(), vec.end(), [](int i) { return i < 5; }));
 301     getGlobalMemCounter()->reset();
 302   }
 303 #endif
 304 #endif // TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)
 305 }
 306
 307 #if TEST_STD_VER >= 11
 308
 309 struct is_null
 310 {
 311     template <class P>
 312         bool operator()(const P& p) {return p == 0;}
 313 };
 314
 315 template <class Iter>
 316 void
 317 test1()
 318 {
 319     const unsigned size = 5;
 320     std::unique_ptr<int> array[size];
 321     Iter r = std::stable_partition(Iter(array), Iter(array+size), is_null());
 322     assert(r == Iter(array+size));
 323 }
 324
 325 #endif // TEST_STD_VER >= 11
 326
 327 int main(int, char**)
 328 {
 329     test<bidirectional_iterator<std::pair<int,int>*> >();
 330     test<random_access_iterator<std::pair<int,int>*> >();
 331     test<std::pair<int,int>*>();
 332
 333 #if TEST_STD_VER >= 11
 334     test1<bidirectional_iterator<std::unique_ptr<int>*> >();
 335 #endif
 336
 337   return 0;
 338 }