#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) {
    std::stringstream w;
    head->visit([&w](const T& value) { w << " " << value; });
    return w.str();
}

template <typename T>
Item<T>* make_list(std::initializer_list<T> items) {
  // TODO(michaelh): change to take an initialiser list.
  auto first = new Item<T>{1};
  auto at = first;
  for (const auto& i : items) {
    at = at->emplace(i);
  }
  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;
}