ceph/src/boost/libs/algorithm/test/find_backward_test.cpp

   1 /*
   2    Copyright (c) T. Zachary Laine 2018.
   3
   4    Distributed under the Boost Software License, Version 1.0. (See accompanying
   5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7     For more information, see http://www.boost.org
   8 */
   9 #include <iostream>
  10
  11 #include <boost/algorithm/find_backward.hpp>
  12
  13 #define BOOST_TEST_MAIN
  14 #include <boost/test/unit_test.hpp>
  15
  16 #include <vector>
  17 #include <list>
  18
  19
  20 namespace ba = boost::algorithm;
  21
  22 template <typename Container>
  23 struct dist_t
  24 {
  25     dist_t(Container & cont) : cont_(cont) {}
  26     template<typename Iter>
  27     std::ptrdiff_t operator()(Iter it) const
  28     {
  29         return std::distance(cont_.begin(), it);
  30     }
  31
  32     Container & cont_;
  33 };
  34
  35 BOOST_CXX14_CONSTEXPR bool check_constexpr_backward()
  36 {
  37     int in_data[] = {1, 2, 3, 4, 5};
  38     bool res = true;
  39
  40     const int* from = in_data;
  41     const int* to = in_data + 5;
  42
  43     const int* start = ba::find_backward(from, to, 1); // stops on first
  44     res = (res && start == from);
  45
  46     start = ba::find_backward(in_data, 1); // stops on first
  47     res = (res && start == from);
  48
  49     const int* end = ba::find_backward(from, to, 6); // stops on the end
  50     res = (res && end == to);
  51
  52     end = ba::find_backward(in_data, 6); // stops on the end
  53     res = (res && end == to);
  54
  55     const int* three = ba::find_backward(from, to, 3); // stops on third element
  56     res = (res && three == in_data + 2);
  57
  58     three = ba::find_backward(in_data, 3); // stops on third element
  59     res = (res && three == in_data + 2);
  60
  61     return res;
  62 }
  63
  64 void test_find_backward()
  65 {
  66     {
  67         std::vector<int> v1;
  68         const dist_t<std::vector<int> > dist(v1);
  69
  70         for (int i = 5; i < 15; ++i)
  71             v1.push_back(i);
  72         BOOST_CHECK_EQUAL(
  73             dist(ba::find_backward(v1.begin(), v1.end(), 0)), v1.size());
  74         BOOST_CHECK_EQUAL(
  75             dist(ba::find_backward(v1.begin(), v1.end(), 100)), v1.size());
  76         BOOST_CHECK_EQUAL(
  77             dist(ba::find_backward(v1.begin(), v1.end(), v1.back())),
  78             v1.size() - 1);
  79         BOOST_CHECK_EQUAL(
  80             dist(ba::find_backward(v1.begin(), v1.end(), v1.front())), 0);
  81
  82         BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, 0)), v1.size());
  83         BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, 100)), v1.size());
  84         BOOST_CHECK_EQUAL(
  85             dist(ba::find_backward(v1, v1.back())), v1.size() - 1);
  86         BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, v1.front())), 0);
  87     }
  88
  89     //  With bidirectional iterators.
  90     {
  91         std::list<int> l1;
  92         const dist_t<std::list<int> > dist(l1);
  93
  94         for (int i = 5; i < 15; ++i)
  95             l1.push_back(i);
  96         BOOST_CHECK_EQUAL(
  97             dist(ba::find_backward(l1.begin(), l1.end(), 0)), l1.size());
  98         BOOST_CHECK_EQUAL(
  99             dist(ba::find_backward(l1.begin(), l1.end(), 100)), l1.size());
 100         BOOST_CHECK_EQUAL(
 101             dist(ba::find_backward(l1.begin(), l1.end(), l1.back())),
 102             l1.size() - 1);
 103         BOOST_CHECK_EQUAL(
 104             dist(ba::find_backward(l1.begin(), l1.end(), l1.front())), 0);
 105
 106         BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, 0)), l1.size());
 107         BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, 100)), l1.size());
 108         BOOST_CHECK_EQUAL(
 109             dist(ba::find_backward(l1, l1.back())), l1.size() - 1);
 110         BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, l1.front())), 0);
 111     }
 112
 113     BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_backward();
 114     BOOST_CHECK(ce_result);
 115 }
 116
 117 struct equals
 118 {
 119     BOOST_CXX14_CONSTEXPR equals(int n) : n_(n) {}
 120     BOOST_CXX14_CONSTEXPR bool operator()(int i) { return i == n_; }
 121     int n_;
 122 };
 123
 124 BOOST_CXX14_CONSTEXPR bool check_constexpr_if_backward()
 125 {
 126     int in_data[] = {1, 2, 3, 4, 5};
 127     bool res = true;
 128
 129     const int* from = in_data;
 130     const int* to = in_data + 5;
 131
 132     const int* start = ba::find_if_backward(from, to, equals(1)); // stops on first
 133     res = (res && start == from);
 134
 135     start = ba::find_if_backward(in_data, equals(1)); // stops on first
 136     res = (res && start == from);
 137
 138     const int* end = ba::find_if_backward(from, to, equals(6)); // stops on the end
 139     res = (res && end == to);
 140
 141     end = ba::find_if_backward(in_data, equals(6)); // stops on the end
 142     res = (res && end == to);
 143
 144     const int* three = ba::find_if_backward(from, to, equals(3)); // stops on third element
 145     res = (res && three == in_data + 2);
 146
 147     three = ba::find_if_backward(in_data, equals(3)); // stops on third element
 148     res = (res && three == in_data + 2);
 149
 150     return res;
 151 }
 152
 153 void test_find_if_backward()
 154 {
 155     {
 156         std::vector<int> v1;
 157         const dist_t<std::vector<int> > dist(v1);
 158
 159         for (int i = 5; i < 15; ++i)
 160             v1.push_back(i);
 161         BOOST_CHECK_EQUAL(
 162             dist(ba::find_if_backward(v1.begin(), v1.end(), equals(0))),
 163             v1.size());
 164         BOOST_CHECK_EQUAL(
 165             dist(ba::find_if_backward(v1.begin(), v1.end(), equals(100))),
 166             v1.size());
 167         BOOST_CHECK_EQUAL(
 168             dist(ba::find_if_backward(v1.begin(), v1.end(), equals(v1.back()))),
 169             v1.size() - 1);
 170         BOOST_CHECK_EQUAL(
 171             dist(
 172                 ba::find_if_backward(v1.begin(), v1.end(), equals(v1.front()))),
 173             0);
 174
 175         BOOST_CHECK_EQUAL(dist(ba::find_if_backward(v1, equals(0))), v1.size());
 176         BOOST_CHECK_EQUAL(
 177             dist(ba::find_if_backward(v1, equals(100))), v1.size());
 178         BOOST_CHECK_EQUAL(
 179             dist(ba::find_if_backward(v1, equals(v1.back()))), v1.size() - 1);
 180         BOOST_CHECK_EQUAL(
 181             dist(ba::find_if_backward(v1, equals(v1.front()))), 0);
 182     }
 183
 184     //  With bidirectional iterators.
 185     {
 186         std::list<int> l1;
 187         const dist_t<std::list<int> > dist(l1);
 188
 189         for (int i = 5; i < 15; ++i)
 190             l1.push_back(i);
 191         BOOST_CHECK_EQUAL(
 192             dist(ba::find_if_backward(l1.begin(), l1.end(), equals(0))),
 193             l1.size());
 194         BOOST_CHECK_EQUAL(
 195             dist(ba::find_if_backward(l1.begin(), l1.end(), equals(100))),
 196             l1.size());
 197         BOOST_CHECK_EQUAL(
 198             dist(ba::find_if_backward(l1.begin(), l1.end(), equals(l1.back()))),
 199             l1.size() - 1);
 200         BOOST_CHECK_EQUAL(
 201             dist(
 202                 ba::find_if_backward(l1.begin(), l1.end(), equals(l1.front()))),
 203             0);
 204
 205         BOOST_CHECK_EQUAL(dist(ba::find_if_backward(l1, equals(0))), l1.size());
 206         BOOST_CHECK_EQUAL(
 207             dist(ba::find_if_backward(l1, equals(100))), l1.size());
 208         BOOST_CHECK_EQUAL(
 209             dist(ba::find_if_backward(l1, equals(l1.back()))), l1.size() - 1);
 210         BOOST_CHECK_EQUAL(
 211             dist(ba::find_if_backward(l1, equals(l1.front()))), 0);
 212     }
 213
 214     BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_if_backward();
 215     BOOST_CHECK(ce_result);
 216 }
 217
 218 struct not_equals
 219 {
 220     BOOST_CXX14_CONSTEXPR not_equals(int n) : n_(n) {}
 221     BOOST_CXX14_CONSTEXPR bool operator()(int i) { return i != n_; }
 222     int n_;
 223 };
 224
 225 BOOST_CXX14_CONSTEXPR bool check_constexpr_if_not_backward()
 226 {
 227     int in_data[] = {1, 2, 3, 4, 5};
 228     bool res = true;
 229
 230     const int* from = in_data;
 231     const int* to = in_data + 5;
 232
 233     const int* start = ba::find_if_not_backward(from, to, not_equals(1)); // stops on first
 234     res = (res && start == from);
 235
 236     start = ba::find_if_not_backward(in_data, not_equals(1)); // stops on first
 237     res = (res && start == from);
 238
 239     const int* end = ba::find_if_not_backward(from, to, not_equals(6)); // stops on the end
 240     res = (res && end == to);
 241
 242     end = ba::find_if_not_backward(in_data, not_equals(6)); // stops on the end
 243     res = (res && end == to);
 244
 245     const int* three = ba::find_if_not_backward(from, to, not_equals(3)); // stops on third element
 246     res = (res && three == in_data + 2);
 247
 248     three = ba::find_if_not_backward(in_data, not_equals(3)); // stops on third element
 249     res = (res && three == in_data + 2);
 250
 251     return res;
 252 }
 253
 254 void test_find_if_not_backward()
 255 {
 256     {
 257         std::vector<int> v1;
 258         const dist_t<std::vector<int> > dist(v1);
 259
 260         for (int i = 5; i < 15; ++i)
 261             v1.push_back(i);
 262         BOOST_CHECK_EQUAL(
 263             dist(ba::find_if_not_backward(v1.begin(), v1.end(), not_equals(0))),
 264             v1.size());
 265         BOOST_CHECK_EQUAL(
 266             dist(ba::find_if_not_backward(
 267                 v1.begin(), v1.end(), not_equals(100))),
 268             v1.size());
 269         BOOST_CHECK_EQUAL(
 270             dist(ba::find_if_not_backward(
 271                 v1.begin(), v1.end(), not_equals(v1.back()))),
 272             v1.size() - 1);
 273         BOOST_CHECK_EQUAL(
 274             dist(ba::find_if_not_backward(
 275                 v1.begin(), v1.end(), not_equals(v1.front()))),
 276             0);
 277
 278         BOOST_CHECK_EQUAL(
 279             dist(ba::find_if_not_backward(v1, not_equals(0))), v1.size());
 280         BOOST_CHECK_EQUAL(
 281             dist(ba::find_if_not_backward(v1, not_equals(100))), v1.size());
 282         BOOST_CHECK_EQUAL(
 283             dist(ba::find_if_not_backward(v1, not_equals(v1.back()))),
 284             v1.size() - 1);
 285         BOOST_CHECK_EQUAL(
 286             dist(ba::find_if_not_backward(v1, not_equals(v1.front()))), 0);
 287     }
 288
 289     //  With bidirectional iterators.
 290     {
 291         std::list<int> l1;
 292         const dist_t<std::list<int> > dist(l1);
 293
 294         for (int i = 5; i < 15; ++i)
 295             l1.push_back(i);
 296         BOOST_CHECK_EQUAL(
 297             dist(ba::find_if_not_backward(l1.begin(), l1.end(), not_equals(0))),
 298             l1.size());
 299         BOOST_CHECK_EQUAL(
 300             dist(ba::find_if_not_backward(
 301                 l1.begin(), l1.end(), not_equals(100))),
 302             l1.size());
 303         BOOST_CHECK_EQUAL(
 304             dist(ba::find_if_not_backward(
 305                 l1.begin(), l1.end(), not_equals(l1.back()))),
 306             l1.size() - 1);
 307         BOOST_CHECK_EQUAL(
 308             dist(ba::find_if_not_backward(
 309                 l1.begin(), l1.end(), not_equals(l1.front()))),
 310             0);
 311
 312         BOOST_CHECK_EQUAL(
 313             dist(ba::find_if_not_backward(l1, not_equals(0))), l1.size());
 314         BOOST_CHECK_EQUAL(
 315             dist(ba::find_if_not_backward(l1, not_equals(100))), l1.size());
 316         BOOST_CHECK_EQUAL(
 317             dist(ba::find_if_not_backward(l1, not_equals(l1.back()))),
 318             l1.size() - 1);
 319         BOOST_CHECK_EQUAL(
 320             dist(ba::find_if_not_backward(l1, not_equals(l1.front()))), 0);
 321     }
 322
 323     BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_if_not_backward();
 324     BOOST_CHECK(ce_result);
 325 }
 326
 327 BOOST_CXX14_CONSTEXPR bool check_constexpr_not_backward()
 328 {
 329     int in_data[] = {1, 5, 5, 5, 5};
 330     bool res = true;
 331
 332     const int* from = in_data;
 333     const int* to = in_data + 5;
 334
 335     const int* start = ba::find_not_backward(from, to, 5); // stops on first
 336     res = (res && start == from);
 337
 338     start = ba::find_not_backward(in_data, 5); // stops on first
 339     res = (res && start == from);
 340
 341     const int in_data_2[] = {6, 6, 6, 6, 6};
 342     const int* end = ba::find_not_backward(in_data_2, in_data_2 + 5, 6); // stops on the end
 343     res = (res && end == in_data_2 + 5);
 344
 345     end = ba::find_not_backward(in_data_2, 6); // stops on the end
 346     res = (res && end == in_data_2 + 5);
 347
 348     return res;
 349 }
 350
 351 void test_find_not_backward()
 352 {
 353     {
 354         std::vector<int> v1;
 355         const dist_t<std::vector<int> > dist(v1);
 356
 357         for (int i = 0; i < 5; ++i)
 358             v1.push_back(0);
 359         for (int i = 0; i < 5; ++i)
 360             v1.push_back(1);
 361         BOOST_CHECK_EQUAL(
 362             dist(ba::find_not_backward(v1.begin(), v1.end(), 1)), 4);
 363         BOOST_CHECK_EQUAL(
 364             dist(ba::find_not_backward(v1.begin(), v1.end(), 0)),
 365             v1.size() - 1);
 366         BOOST_CHECK_EQUAL(
 367             dist(ba::find_not_backward(v1.begin(), v1.end(), 2)),
 368             v1.size() - 1);
 369
 370         BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 1)), 4);
 371         BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 0)), v1.size() - 1);
 372         BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 2)), v1.size() - 1);
 373
 374         v1.resize(5);
 375         BOOST_CHECK_EQUAL(
 376             dist(ba::find_not_backward(v1.begin(), v1.end(), 0)), v1.size());
 377
 378         BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 0)), v1.size());
 379     }
 380
 381     //  With bidirectional iterators.
 382     {
 383         std::list<int> l1;
 384         const dist_t<std::list<int> > dist(l1);
 385
 386         for (int i = 0; i < 5; ++i)
 387             l1.push_back(0);
 388         for (int i = 0; i < 5; ++i)
 389             l1.push_back(1);
 390         BOOST_CHECK_EQUAL(
 391             dist(ba::find_not_backward(l1.begin(), l1.end(), 1)), 4);
 392         BOOST_CHECK_EQUAL(
 393             dist(ba::find_not_backward(l1.begin(), l1.end(), 0)),
 394             l1.size() - 1);
 395         BOOST_CHECK_EQUAL(
 396             dist(ba::find_not_backward(l1.begin(), l1.end(), 2)),
 397             l1.size() - 1);
 398
 399         BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 1)), 4);
 400         BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 0)), l1.size() - 1);
 401         BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 2)), l1.size() - 1);
 402
 403         l1.resize(5);
 404         BOOST_CHECK_EQUAL(
 405             dist(ba::find_not_backward(l1.begin(), l1.end(), 0)), l1.size());
 406
 407         BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 0)), l1.size());
 408     }
 409
 410     BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_not_backward();
 411     BOOST_CHECK(ce_result);
 412 }
 413
 414 BOOST_AUTO_TEST_CASE(test_main)
 415 {
 416     test_find_backward();
 417     test_find_if_backward();
 418     test_find_if_not_backward();
 419     test_find_not_backward();
 420 }