#include<iostream>
#include<functional>
#include<memory>
using namespace std;

template<typename T>
struct List {
private:
  struct node {
    T item;
    unique_ptr<node> next{nullptr};
    node(T i) { item = move(i); }
  };
  node& nth(unsigned int i, unique_ptr<node>& n) {  // tail-recursive
    if (i==0) return *n;
    else return nth(i-1,n->next);
  }
  void map(function<void(T&)> f, unique_ptr<node>& n) {
    if (n) {
      f(n->item);
      map(f,n->next);
    }
  }

  node& nth(unsigned int i) {
    if (i>=size) throw "invalid index";
    reference_wrapper<node> n = *first;
    while (i>0) {
      n = *n.get().next;
      i--;
    }
    return n.get();
  }
  
public:
  unique_ptr<node> first{nullptr};
  size_t size{0};

  size_t length() { return size; }

  void push(T x) {
    unique_ptr<node> newnode = make_unique<node>(x);
    newnode->next = move(first);
    first = move(newnode);
    size++;
  }

  T pop() {
    if (size<1) throw "nothing to pop";
    T answer = first->item;
    first = move(first->next);
    size--;
    return answer;
  }

  T& peek() {
    if (size<1) throw "nothing to peek";
    return first->item;
  }

  void map(function<void(T&)> f) { map(f,first); }

  friend ostream& operator <<(ostream& out, List& L) {
    L.map([&](T& x) { out << x << " "; });
    return out;
  }

  T& operator [](unsigned int i) { return nth(i,first).item; }

  void insert(unsigned int i, T x) {
    if (i>size) throw "invalid index";
    if (i==0) { push(x); return; }
    unique_ptr<node> newnode = make_unique<node>(x);
    node& previous = nth(i-1); //nth(i-1,first);
    unique_ptr<node> temp = move(previous.next);
    previous.next = move(newnode);
    previous.next->next = move(temp);
    size++;
  }

  T remove(unsigned int i) {
    if (i>=size) throw "invalid index";
    if (i==0) return pop();
    node& previous = nth(i-1,first);
    T answer = move(previous.next->item);
    previous.next = move(previous.next->next);
    size--;
    return answer;
  }

  void add(T x) {
    if (size==0) { push(x); return; }
    node& last = nth(size-1,first);
    last->next = make_unique<node>(x);
  }

  bool truncate(unsigned int i) {
    if (i>size) return false;
    node& previous = nth(i-1,first);
    previous.next = nullptr;
    return true;
  }

  List<T> reverse() {
    List<T> C;
    map([&](T& x) { C.push(x); });
    return C;
  }

  List<T> clone() {
    List<T> R = reverse();
    return R.reverse();
  }
  
};

int main() {
  List<int> L;
  L.push(1);L.push(2); L.push(4); L.push(6); L.push(8); L.push(10); L.push(12);
  L.pop();
  L.insert(3,5);
  L.remove(2);
  L.truncate(5);
  List<int> R = L.reverse();
  cout << L << endl;
  cout << R << endl;
  List<int> R2 = R.clone();
  cout << R2 << endl;
  return 0;
}