421 lines
13 KiB
C++
421 lines
13 KiB
C++
/*
|
|
Copyright (c) T. Zachary Laine 2018.
|
|
|
|
Distributed under the Boost Software License, Version 1.0. (See accompanying
|
|
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
|
|
|
|
For more information, see http://www.boost.org
|
|
*/
|
|
#include <iostream>
|
|
|
|
#include <boost/algorithm/find_backward.hpp>
|
|
|
|
#define BOOST_TEST_MAIN
|
|
#include <boost/test/unit_test.hpp>
|
|
|
|
#include <vector>
|
|
#include <list>
|
|
|
|
|
|
namespace ba = boost::algorithm;
|
|
|
|
template <typename Container>
|
|
struct dist_t
|
|
{
|
|
dist_t(Container & cont) : cont_(cont) {}
|
|
template<typename Iter>
|
|
std::ptrdiff_t operator()(Iter it) const
|
|
{
|
|
return std::distance(cont_.begin(), it);
|
|
}
|
|
|
|
Container & cont_;
|
|
};
|
|
|
|
BOOST_CXX14_CONSTEXPR bool check_constexpr_backward()
|
|
{
|
|
int in_data[] = {1, 2, 3, 4, 5};
|
|
bool res = true;
|
|
|
|
const int* from = in_data;
|
|
const int* to = in_data + 5;
|
|
|
|
const int* start = ba::find_backward(from, to, 1); // stops on first
|
|
res = (res && start == from);
|
|
|
|
start = ba::find_backward(in_data, 1); // stops on first
|
|
res = (res && start == from);
|
|
|
|
const int* end = ba::find_backward(from, to, 6); // stops on the end
|
|
res = (res && end == to);
|
|
|
|
end = ba::find_backward(in_data, 6); // stops on the end
|
|
res = (res && end == to);
|
|
|
|
const int* three = ba::find_backward(from, to, 3); // stops on third element
|
|
res = (res && three == in_data + 2);
|
|
|
|
three = ba::find_backward(in_data, 3); // stops on third element
|
|
res = (res && three == in_data + 2);
|
|
|
|
return res;
|
|
}
|
|
|
|
void test_find_backward()
|
|
{
|
|
{
|
|
std::vector<int> v1;
|
|
const dist_t<std::vector<int> > dist(v1);
|
|
|
|
for (int i = 5; i < 15; ++i)
|
|
v1.push_back(i);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(v1.begin(), v1.end(), 0)), v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(v1.begin(), v1.end(), 100)), v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(v1.begin(), v1.end(), v1.back())),
|
|
v1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(v1.begin(), v1.end(), v1.front())), 0);
|
|
|
|
BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, 0)), v1.size());
|
|
BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, 100)), v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(v1, v1.back())), v1.size() - 1);
|
|
BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, v1.front())), 0);
|
|
}
|
|
|
|
// With bidirectional iterators.
|
|
{
|
|
std::list<int> l1;
|
|
const dist_t<std::list<int> > dist(l1);
|
|
|
|
for (int i = 5; i < 15; ++i)
|
|
l1.push_back(i);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(l1.begin(), l1.end(), 0)), l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(l1.begin(), l1.end(), 100)), l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(l1.begin(), l1.end(), l1.back())),
|
|
l1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(l1.begin(), l1.end(), l1.front())), 0);
|
|
|
|
BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, 0)), l1.size());
|
|
BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, 100)), l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_backward(l1, l1.back())), l1.size() - 1);
|
|
BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, l1.front())), 0);
|
|
}
|
|
|
|
BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_backward();
|
|
BOOST_CHECK(ce_result);
|
|
}
|
|
|
|
struct equals
|
|
{
|
|
BOOST_CXX14_CONSTEXPR equals(int n) : n_(n) {}
|
|
BOOST_CXX14_CONSTEXPR bool operator()(int i) { return i == n_; }
|
|
int n_;
|
|
};
|
|
|
|
BOOST_CXX14_CONSTEXPR bool check_constexpr_if_backward()
|
|
{
|
|
int in_data[] = {1, 2, 3, 4, 5};
|
|
bool res = true;
|
|
|
|
const int* from = in_data;
|
|
const int* to = in_data + 5;
|
|
|
|
const int* start = ba::find_if_backward(from, to, equals(1)); // stops on first
|
|
res = (res && start == from);
|
|
|
|
start = ba::find_if_backward(in_data, equals(1)); // stops on first
|
|
res = (res && start == from);
|
|
|
|
const int* end = ba::find_if_backward(from, to, equals(6)); // stops on the end
|
|
res = (res && end == to);
|
|
|
|
end = ba::find_if_backward(in_data, equals(6)); // stops on the end
|
|
res = (res && end == to);
|
|
|
|
const int* three = ba::find_if_backward(from, to, equals(3)); // stops on third element
|
|
res = (res && three == in_data + 2);
|
|
|
|
three = ba::find_if_backward(in_data, equals(3)); // stops on third element
|
|
res = (res && three == in_data + 2);
|
|
|
|
return res;
|
|
}
|
|
|
|
void test_find_if_backward()
|
|
{
|
|
{
|
|
std::vector<int> v1;
|
|
const dist_t<std::vector<int> > dist(v1);
|
|
|
|
for (int i = 5; i < 15; ++i)
|
|
v1.push_back(i);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(v1.begin(), v1.end(), equals(0))),
|
|
v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(v1.begin(), v1.end(), equals(100))),
|
|
v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(v1.begin(), v1.end(), equals(v1.back()))),
|
|
v1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(
|
|
ba::find_if_backward(v1.begin(), v1.end(), equals(v1.front()))),
|
|
0);
|
|
|
|
BOOST_CHECK_EQUAL(dist(ba::find_if_backward(v1, equals(0))), v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(v1, equals(100))), v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(v1, equals(v1.back()))), v1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(v1, equals(v1.front()))), 0);
|
|
}
|
|
|
|
// With bidirectional iterators.
|
|
{
|
|
std::list<int> l1;
|
|
const dist_t<std::list<int> > dist(l1);
|
|
|
|
for (int i = 5; i < 15; ++i)
|
|
l1.push_back(i);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(l1.begin(), l1.end(), equals(0))),
|
|
l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(l1.begin(), l1.end(), equals(100))),
|
|
l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(l1.begin(), l1.end(), equals(l1.back()))),
|
|
l1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(
|
|
ba::find_if_backward(l1.begin(), l1.end(), equals(l1.front()))),
|
|
0);
|
|
|
|
BOOST_CHECK_EQUAL(dist(ba::find_if_backward(l1, equals(0))), l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(l1, equals(100))), l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(l1, equals(l1.back()))), l1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_backward(l1, equals(l1.front()))), 0);
|
|
}
|
|
|
|
BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_if_backward();
|
|
BOOST_CHECK(ce_result);
|
|
}
|
|
|
|
struct not_equals
|
|
{
|
|
BOOST_CXX14_CONSTEXPR not_equals(int n) : n_(n) {}
|
|
BOOST_CXX14_CONSTEXPR bool operator()(int i) { return i != n_; }
|
|
int n_;
|
|
};
|
|
|
|
BOOST_CXX14_CONSTEXPR bool check_constexpr_if_not_backward()
|
|
{
|
|
int in_data[] = {1, 2, 3, 4, 5};
|
|
bool res = true;
|
|
|
|
const int* from = in_data;
|
|
const int* to = in_data + 5;
|
|
|
|
const int* start = ba::find_if_not_backward(from, to, not_equals(1)); // stops on first
|
|
res = (res && start == from);
|
|
|
|
start = ba::find_if_not_backward(in_data, not_equals(1)); // stops on first
|
|
res = (res && start == from);
|
|
|
|
const int* end = ba::find_if_not_backward(from, to, not_equals(6)); // stops on the end
|
|
res = (res && end == to);
|
|
|
|
end = ba::find_if_not_backward(in_data, not_equals(6)); // stops on the end
|
|
res = (res && end == to);
|
|
|
|
const int* three = ba::find_if_not_backward(from, to, not_equals(3)); // stops on third element
|
|
res = (res && three == in_data + 2);
|
|
|
|
three = ba::find_if_not_backward(in_data, not_equals(3)); // stops on third element
|
|
res = (res && three == in_data + 2);
|
|
|
|
return res;
|
|
}
|
|
|
|
void test_find_if_not_backward()
|
|
{
|
|
{
|
|
std::vector<int> v1;
|
|
const dist_t<std::vector<int> > dist(v1);
|
|
|
|
for (int i = 5; i < 15; ++i)
|
|
v1.push_back(i);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(v1.begin(), v1.end(), not_equals(0))),
|
|
v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(
|
|
v1.begin(), v1.end(), not_equals(100))),
|
|
v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(
|
|
v1.begin(), v1.end(), not_equals(v1.back()))),
|
|
v1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(
|
|
v1.begin(), v1.end(), not_equals(v1.front()))),
|
|
0);
|
|
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(v1, not_equals(0))), v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(v1, not_equals(100))), v1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(v1, not_equals(v1.back()))),
|
|
v1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(v1, not_equals(v1.front()))), 0);
|
|
}
|
|
|
|
// With bidirectional iterators.
|
|
{
|
|
std::list<int> l1;
|
|
const dist_t<std::list<int> > dist(l1);
|
|
|
|
for (int i = 5; i < 15; ++i)
|
|
l1.push_back(i);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(l1.begin(), l1.end(), not_equals(0))),
|
|
l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(
|
|
l1.begin(), l1.end(), not_equals(100))),
|
|
l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(
|
|
l1.begin(), l1.end(), not_equals(l1.back()))),
|
|
l1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(
|
|
l1.begin(), l1.end(), not_equals(l1.front()))),
|
|
0);
|
|
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(l1, not_equals(0))), l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(l1, not_equals(100))), l1.size());
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(l1, not_equals(l1.back()))),
|
|
l1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_if_not_backward(l1, not_equals(l1.front()))), 0);
|
|
}
|
|
|
|
BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_if_not_backward();
|
|
BOOST_CHECK(ce_result);
|
|
}
|
|
|
|
BOOST_CXX14_CONSTEXPR bool check_constexpr_not_backward()
|
|
{
|
|
int in_data[] = {1, 5, 5, 5, 5};
|
|
bool res = true;
|
|
|
|
const int* from = in_data;
|
|
const int* to = in_data + 5;
|
|
|
|
const int* start = ba::find_not_backward(from, to, 5); // stops on first
|
|
res = (res && start == from);
|
|
|
|
start = ba::find_not_backward(in_data, 5); // stops on first
|
|
res = (res && start == from);
|
|
|
|
const int in_data_2[] = {6, 6, 6, 6, 6};
|
|
const int* end = ba::find_not_backward(in_data_2, in_data_2 + 5, 6); // stops on the end
|
|
res = (res && end == in_data_2 + 5);
|
|
|
|
end = ba::find_not_backward(in_data_2, 6); // stops on the end
|
|
res = (res && end == in_data_2 + 5);
|
|
|
|
return res;
|
|
}
|
|
|
|
void test_find_not_backward()
|
|
{
|
|
{
|
|
std::vector<int> v1;
|
|
const dist_t<std::vector<int> > dist(v1);
|
|
|
|
for (int i = 0; i < 5; ++i)
|
|
v1.push_back(0);
|
|
for (int i = 0; i < 5; ++i)
|
|
v1.push_back(1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_not_backward(v1.begin(), v1.end(), 1)), 4);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_not_backward(v1.begin(), v1.end(), 0)),
|
|
v1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_not_backward(v1.begin(), v1.end(), 2)),
|
|
v1.size() - 1);
|
|
|
|
BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 1)), 4);
|
|
BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 0)), v1.size() - 1);
|
|
BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 2)), v1.size() - 1);
|
|
|
|
v1.resize(5);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_not_backward(v1.begin(), v1.end(), 0)), v1.size());
|
|
|
|
BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 0)), v1.size());
|
|
}
|
|
|
|
// With bidirectional iterators.
|
|
{
|
|
std::list<int> l1;
|
|
const dist_t<std::list<int> > dist(l1);
|
|
|
|
for (int i = 0; i < 5; ++i)
|
|
l1.push_back(0);
|
|
for (int i = 0; i < 5; ++i)
|
|
l1.push_back(1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_not_backward(l1.begin(), l1.end(), 1)), 4);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_not_backward(l1.begin(), l1.end(), 0)),
|
|
l1.size() - 1);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_not_backward(l1.begin(), l1.end(), 2)),
|
|
l1.size() - 1);
|
|
|
|
BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 1)), 4);
|
|
BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 0)), l1.size() - 1);
|
|
BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 2)), l1.size() - 1);
|
|
|
|
l1.resize(5);
|
|
BOOST_CHECK_EQUAL(
|
|
dist(ba::find_not_backward(l1.begin(), l1.end(), 0)), l1.size());
|
|
|
|
BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 0)), l1.size());
|
|
}
|
|
|
|
BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_not_backward();
|
|
BOOST_CHECK(ce_result);
|
|
}
|
|
|
|
BOOST_AUTO_TEST_CASE(test_main)
|
|
{
|
|
test_find_backward();
|
|
test_find_if_backward();
|
|
test_find_if_not_backward();
|
|
test_find_not_backward();
|
|
}
|