hakutaku/tdesktop
1
0
Fork 0
Code Issues Pull Requests Actions 5 Packages Projects Releases Wiki Activity
Files
master
tdesktop/Telegram/ThirdParty/range-v3/test/view/set_symmetric_difference.cpp
allhaileris afb81b8278
Some checks failed
Docker. / Ubuntu (push) Has been cancelled
Details
User-agent updater. / User-agent (push) Failing after 15s
Details
Lock Threads / lock (push) Failing after 10s
Details
Waiting for answer. / waiting-for-answer (push) Failing after 22s
Details
Needs user action. / needs-user-action (push) Failing after 8s
Details
Can't reproduce. / cant-reproduce (push) Failing after 8s
Details
Close stale issues and PRs / stale (push) Has been cancelled
Details
init
2026-02-16 15:50:16 +03:00

325 lines
13 KiB
C++
Raw Permalink Blame History

// Range v3 library
//
// Copyright Eric Niebler 2014-present
// Copyright Tomislav Ivek 2015-2016
//
// Use, modification and distribution is subject to 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)
//
// Project home: https://github.com/ericniebler/range-v3
#include <vector>
#include <sstream>
#include <range/v3/core.hpp>
#include <range/v3/range_for.hpp>
#include <range/v3/algorithm/set_algorithm.hpp>
#include <range/v3/algorithm/move.hpp>
#include <range/v3/utility/common_type.hpp>
#include <range/v3/iterator/operations.hpp>
#include <range/v3/iterator/insert_iterators.hpp>
#include <range/v3/iterator/move_iterators.hpp>
#include <range/v3/functional/identity.hpp>
#include <range/v3/view/all.hpp>
#include <range/v3/view/const.hpp>
#include <range/v3/view/drop_while.hpp>
#include <range/v3/view/empty.hpp>
#include <range/v3/view/iota.hpp>
#include <range/v3/view/reverse.hpp>
#include <range/v3/view/set_algorithm.hpp>
#include <range/v3/view/stride.hpp>
#include <range/v3/view/take.hpp>
#include <range/v3/view/transform.hpp>
#include <range/v3/view/zip.hpp>
#include <range/v3/utility/copy.hpp>
#include "../simple_test.hpp"
#include "../test_utils.hpp"
int main()
{
using namespace ranges;
int i1_finite[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
int i2_finite[] = { -3, 2, 4, 4, 6, 9};
auto i1_infinite = views::ints | views::stride(3);
auto i2_infinite = views::ints | views::transform([](int x)
{
return x * x;
});
// symmetric difference between two finite ranges/sets
{
auto res = views::set_symmetric_difference(i1_finite, i2_finite);
CPP_assert(view_<decltype(res)>);
CPP_assert(forward_range<decltype(res)>);
CPP_assert(!random_access_range<decltype(res)>);
CPP_assert(!common_range<decltype(res)>);
using R = decltype(res);
CPP_assert(same_as<range_value_t<R>, int>);
CPP_assert(same_as<range_reference_t<R>, int&>);
CPP_assert(same_as<decltype(iter_move(begin(res))), int&&>);
static_assert(range_cardinality<R>::value == ranges::finite, "Cardinality of symmetric difference of finite ranges should be finite!");
::check_equal(res, {-3, 1, 2, 3, 3, 3, 4, 4, 6, 9});
// check if the final result agrees with the greedy algorithm
std::vector<int> greedy_sd;
set_symmetric_difference(i1_finite, i2_finite, back_inserter(greedy_sd));
::check_equal(res, greedy_sd);
auto it = begin(res);
CHECK(&*it == &*(begin(i2_finite)));
++it;
CHECK(&*it == &*(begin(i1_finite)));
}
// symmetric difference between two infinite ranges
{
auto res = views::set_symmetric_difference(i1_infinite, i2_infinite);
CPP_assert(view_<decltype(res)>);
CPP_assert(forward_range<decltype(res)>);
CPP_assert(!random_access_range<decltype(res)>);
CPP_assert(!common_range<decltype(res)>);
using R = decltype(res);
CPP_assert(same_as<range_value_t<R>,
common_type_t<range_value_t<decltype(i1_infinite)>,
range_value_t<decltype(i2_infinite)>>>);
CPP_assert(same_as<range_reference_t<R>,
common_reference_t<range_reference_t<decltype(i1_infinite)>,
range_reference_t<decltype(i2_infinite)>>
>);
CPP_assert(same_as<range_rvalue_reference_t<R>,
common_reference_t<range_rvalue_reference_t<decltype(i1_infinite)>,
range_rvalue_reference_t<decltype(i2_infinite)>>
>);
static_assert(range_cardinality<R>::value == ranges::unknown, "Cardinality of symmetric difference between infinite ranges should be unknown!");
::check_equal(res | views::take(6), {1, 3, 4, 6, 12, 15});
// check if the final result agrees with the greedy algorithm
std::vector<int> greedy_sd;
set_symmetric_difference(i1_infinite | views::take(10), i2_infinite | views::take(10), back_inserter(greedy_sd));
::check_equal(res | views::take(6), greedy_sd | views::take(6));
}
// symmetric difference between a finite and an infinite range
{
auto res1 = views::set_symmetric_difference(i1_finite, i2_infinite);
CPP_assert(view_<decltype(res1)>);
CPP_assert(forward_range<decltype(res1)>);
CPP_assert(!random_access_range<decltype(res1)>);
CPP_assert(!common_range<decltype(res1)>);
using R1 = decltype(res1);
CPP_assert(same_as<range_value_t<R1>, int>);
CPP_assert(same_as<range_reference_t<R1>, int>); // our infinite range does not give out references
CPP_assert(same_as<range_rvalue_reference_t<R1>, int>);
static_assert(range_cardinality<R1>::value == ranges::infinite, "Cardinality of symmetric difference between a finite and an infinite range should be infinite!");
::check_equal(res1 | views::take(10), {0, 2, 2, 3, 3, 3, 4, 4, 4, 9});
// now swap the operands:
auto res2 = views::set_symmetric_difference(i2_infinite, i1_finite);
CPP_assert(view_<decltype(res2)>);
CPP_assert(forward_range<decltype(res2)>);
CPP_assert(!random_access_range<decltype(res2)>);
CPP_assert(!common_range<decltype(res2)>);
using R2 = decltype(res2);
CPP_assert(same_as<range_value_t<R2>, int>);
CPP_assert(same_as<range_reference_t<R2>, int>); // our infinite range does not give out references
CPP_assert(same_as<range_rvalue_reference_t<R2>, int>);
static_assert(range_cardinality<R2>::value == ranges::infinite, "Cardinality of symmetric difference between a finite and an infinite range should be infinite!");
::check_equal(res1 | views::take(10), res2 | views::take(10));
}
// symmetric differences involving unknown cardinalities
{
auto rng0 = views::iota(10) | views::drop_while([](int i)
{
return i < 25;
});
static_assert(range_cardinality<decltype(rng0)>::value == ranges::unknown, "");
auto res1 = views::set_symmetric_difference(i2_finite, rng0);
static_assert(range_cardinality<decltype(res1)>::value == ranges::unknown, "Symmetric difference between a finite and unknown cardinality set should have unknown cardinality!");
auto res2 = views::set_symmetric_difference(rng0, i2_finite);
static_assert(range_cardinality<decltype(res2)>::value == ranges::unknown, "Symmetric difference between an unknown and finite cardinality set should have unknown cardinality!");
auto res3 = views::set_symmetric_difference(i1_infinite, rng0);
static_assert(range_cardinality<decltype(res3)>::value == ranges::unknown, "Symmetric difference between an infinite and unknown cardinality set should have unknown cardinality!");
auto res4 = views::set_symmetric_difference(rng0, i1_infinite);
static_assert(range_cardinality<decltype(res4)>::value == ranges::unknown, "Symmetric difference between an unknown and infinite cardinality set should have infinite cardinality!");
auto res5 = views::set_symmetric_difference(rng0, rng0);
static_assert(range_cardinality<decltype(res5)>::value == ranges::unknown, "Symmetric difference between two unknown cardinality sets should have unknown cardinality!");
}
// test const ranges
{
auto res1 = views::set_symmetric_difference(views::const_(i1_finite), views::const_(i2_finite));
using R1 = decltype(res1);
CPP_assert(same_as<range_value_t<R1>, int>);
CPP_assert(same_as<range_reference_t<R1>, const int&>);
CPP_assert(same_as<range_rvalue_reference_t<R1>, const int&&>);
auto res2 = views::set_symmetric_difference(views::const_(i1_finite), i2_finite);
using R2 = decltype(res2);
CPP_assert(same_as<range_value_t<R2>, int>);
CPP_assert(same_as<range_reference_t<R2>, const int&>);
CPP_assert(same_as<range_rvalue_reference_t<R2>, const int&&>);
}
// test different orderings
{
auto res = views::set_symmetric_difference(views::reverse(i1_finite), views::reverse(i2_finite), [](int a, int b)
{
return a > b;
});
::check_equal(res, {9, 6, 4, 4, 3, 3, 3, 2, 1, -3});
CHECK(&*begin(res) == &*(begin(i2_finite) + 5));
}
struct B
{
int val;
B(int i): val{i} {}
bool operator==(const B& other) const
{
return val == other.val;
}
};
struct D: public B
{
D(int i): B{i} {}
D(B b): B{std::move(b)} {}
};
B b_finite[] = {B{-20}, B{-10}, B{1}, B{3}, B{3}, B{6}, B{8}, B{20}};
D d_finite[] = {D{0}, D{2}, D{4}, D{6}};
// sets with different element types, custom orderings
{
auto res = views::set_symmetric_difference(b_finite, d_finite, [](const B& a, const D& b){ return a.val < b.val; });
CPP_assert(same_as<range_value_t<decltype(res)>, B>);
CPP_assert(same_as<range_reference_t<decltype(res)>, B&>);
CPP_assert(same_as<range_rvalue_reference_t<decltype(res)>, B&&>);
::check_equal(res, {B{-20}, B{-10}, B{0}, B{1}, B{2}, B{3}, B{3}, B{4}, B{8}, B{20}});
auto it = begin(res);
CHECK(&*it == &*begin(b_finite));
advance(it, 2);
CHECK(&*it == &*begin(d_finite));
}
// projections
{
auto res1 = views::set_symmetric_difference(b_finite, d_finite,
less(),
&B::val,
&D::val
);
CPP_assert(same_as<range_value_t<decltype(res1)>, B>);
CPP_assert(same_as<range_reference_t<decltype(res1)>, B&>);
CPP_assert(same_as<range_rvalue_reference_t<decltype(res1)>, B&&>);
::check_equal(res1, {B{-20}, B{-10}, B{0}, B{1}, B{2}, B{3}, B{3}, B{4}, B{8}, B{20}});
auto res2 = views::set_symmetric_difference(views::ints(-2, 10), b_finite,
less(),
identity(),
[](const B& x){ return x.val; }
);
CPP_assert(same_as<range_value_t<decltype(res2)>, B>);
CPP_assert(same_as<range_reference_t<decltype(res2)>, B>);
CPP_assert(same_as<range_rvalue_reference_t<decltype(res2)>, B>);
::check_equal(res2, {B{-20}, B{-10}, B{-2}, B{-1}, B{0}, B{2}, B{3}, B{4}, B{5}, B{7}, B{9}, B{20}});
}
// move
{
auto v0 = to<std::vector<MoveOnlyString>>({"a","b","b","c","x","x"});
auto v1 = to<std::vector<MoveOnlyString>>({"b","x","y","z"});
auto res = views::set_symmetric_difference(v0, v1, [](const MoveOnlyString& a, const MoveOnlyString& b){return a<b;});
std::vector<MoveOnlyString> expected;
move(res, back_inserter(expected));
::check_equal(expected, {"a","b","c","x","y","z"});
::check_equal(v1, {"b","x","",""});
::check_equal(v0, {"","b","","","x",""});
auto v0_greedy = to<std::vector<MoveOnlyString>>({"a","b","b","c","x","x"});
auto v1_greedy = to<std::vector<MoveOnlyString>>({"b","x","y","z"});
std::vector<MoveOnlyString> expected_greedy;
set_symmetric_difference(v0_greedy, v1_greedy,
move_into(back_inserter(expected_greedy)),
[](const MoveOnlyString& a, const MoveOnlyString& b){return a<b;});
::check_equal(expected_greedy, expected);
::check_equal(v0_greedy, v0);
::check_equal(v1_greedy, v1);
using R = decltype(res);
CPP_assert(same_as<range_value_t<R>, MoveOnlyString>);
CPP_assert(same_as<range_reference_t<R>, MoveOnlyString &>);
CPP_assert(same_as<range_rvalue_reference_t<R>, MoveOnlyString &&>);
}
// WARNING: set_symmetric_difference between two infinite ranges can create infinite loops!
// {
// auto empty_range = views::set_symmetric_difference(views::ints, views::ints);
// begin(empty_range); // infinite loop!
// }
// iterator (in)equality
{
int r1[] = {1, 2, 3};
int r2[] = { 2, 3, 4, 5};
auto res = views::set_symmetric_difference(r1, r2); // 1, 4, 5
auto it1 = ranges::next(res.begin()); // *it1 == 4, member iterator into r1 points to r1.end()
auto it2 = ranges::next(it1); // *it2 == 5, member iterator into r1 also points to r1.end()
auto sentinel = res.end();
CHECK(*it1 == 4);
CHECK(*it2 == 5);
CHECK(it1 != it2); // should be different even though member iterators into r1 are the same
CHECK(it1 != sentinel);
CHECK(ranges::next(it1, 2) == sentinel);
CHECK(it2 != sentinel);
CHECK(ranges::next(it2, 1) == sentinel);
}
{
auto rng = views::set_symmetric_difference(
debug_input_view<int const>{i1_finite},
debug_input_view<int const>{i2_finite}
);
::check_equal(rng, {-3, 1, 2, 3, 3, 3, 4, 4, 6, 9});
}
return test_result();
}
Reference in New Issue View Git Blame Copy Permalink