2017-06-29 22:55:22 +02:00
|
|
|
#include <fmt/format.h>
|
|
|
|
#include <functional>
|
|
|
|
#include <string>
|
|
|
|
|
|
|
|
template <typename T>
|
|
|
|
struct Item {
|
|
|
|
using value_type = T;
|
|
|
|
using const_reference = const T&;
|
|
|
|
|
|
|
|
T value;
|
|
|
|
Item<T>* next = nullptr;
|
|
|
|
|
|
|
|
Item<T>* emplace(const_reference value) {
|
|
|
|
auto item = new Item<T>{value, next};
|
|
|
|
next = item;
|
|
|
|
return item;
|
|
|
|
}
|
|
|
|
|
|
|
|
void visit(std::function<void(const_reference)> visitor) const {
|
|
|
|
visitor(value);
|
|
|
|
if (next != nullptr) {
|
|
|
|
next->visit(visitor);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
Item<T>* tail() {
|
|
|
|
for (auto at = this; at != nullptr; at = at->next) {
|
|
|
|
if (at->next == nullptr) {
|
|
|
|
return at;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return nullptr;
|
|
|
|
}
|
|
|
|
};
|
|
|
|
|
|
|
|
using IntItem = Item<int>;
|
|
|
|
|
|
|
|
template <typename T>
|
|
|
|
void dump(const Item<T>* head) {
|
|
|
|
head->visit([](const T& value) { fmt::print(" {}", value); });
|
|
|
|
fmt::print("\n");
|
|
|
|
}
|
|
|
|
|
|
|
|
template <typename T>
|
|
|
|
std::string to_string(const Item<T>* head) {
|
2018-10-22 12:15:50 +02:00
|
|
|
std::stringstream w;
|
|
|
|
head->visit([&w](const T& value) { w << " " << value; });
|
|
|
|
return w.str();
|
2017-06-29 22:55:22 +02:00
|
|
|
}
|
|
|
|
|
2017-06-29 22:59:43 +02:00
|
|
|
template <typename T>
|
|
|
|
Item<T>* make_list(std::initializer_list<T> items) {
|
2017-06-29 22:55:22 +02:00
|
|
|
// TODO(michaelh): change to take an initialiser list.
|
2017-06-29 22:59:43 +02:00
|
|
|
auto first = new Item<T>{1};
|
|
|
|
auto at = first;
|
|
|
|
for (const auto& i : items) {
|
|
|
|
at = at->emplace(i);
|
|
|
|
}
|
2017-06-29 22:55:22 +02:00
|
|
|
return first;
|
|
|
|
}
|
|
|
|
|
|
|
|
template <typename T>
|
|
|
|
Item<T>* filter(Item<T>* head, std::function<bool(int)> predicate) {
|
|
|
|
// TODO(michaelh): std::function<bool(T)> doesn't match.
|
|
|
|
// TODO(michaelh): how can you mark the return as not-null?
|
|
|
|
auto at = &head;
|
|
|
|
for (auto at = &head; *at != nullptr;) {
|
|
|
|
if (predicate((*at)->value)) {
|
|
|
|
*at = (*at)->next;
|
|
|
|
} else {
|
|
|
|
at = &(*at)->next;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
fmt::print("\n");
|
|
|
|
return head;
|
|
|
|
}
|