2017-06-29 22:31:55 +02:00
|
|
|
// Remove duplicates from a linked list.
|
|
|
|
|
|
|
|
#define CATCH_CONFIG_MAIN
|
|
|
|
#include <catch.hpp>
|
|
|
|
|
|
|
|
#include <unordered_set>
|
|
|
|
|
2017-06-29 22:55:22 +02:00
|
|
|
#include "libcc2x.cc"
|
2017-06-29 22:31:55 +02:00
|
|
|
|
|
|
|
IntItem* remove_duplicates(IntItem* head) {
|
|
|
|
std::unordered_set<int> seen;
|
|
|
|
|
2017-06-29 22:55:22 +02:00
|
|
|
// TODO(michaelh): is [&] or [&seen] better style?
|
|
|
|
return filter(head, [&](int v) {
|
2017-06-29 22:31:55 +02:00
|
|
|
if (seen.find(v) != seen.end()) {
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
seen.emplace(v);
|
|
|
|
return false;
|
|
|
|
});
|
|
|
|
}
|
|
|
|
|
|
|
|
TEST_CASE("cc21", "remove_duplicates") {
|
2017-06-29 22:59:43 +02:00
|
|
|
auto first = make_list({2, 3, 4});
|
2017-06-29 22:31:55 +02:00
|
|
|
CHECK(to_string(first) == " 1 2 3 4");
|
|
|
|
first = filter(first, [](int v) { return v % 2 == 0; });
|
|
|
|
CHECK(to_string(first) == " 1 3");
|
|
|
|
|
|
|
|
first->tail()->emplace(7)->emplace(8);
|
|
|
|
CHECK(to_string(first) == " 1 3 7 8");
|
|
|
|
|
|
|
|
first->tail()->emplace(3)->emplace(7);
|
|
|
|
CHECK(to_string(first) == " 1 3 7 8 3 7");
|
|
|
|
first = remove_duplicates(first);
|
|
|
|
CHECK(to_string(first) == " 1 3 7 8");
|
|
|
|
}
|