#ifndef STRUCTS_DLLIST_H
#define STRUCTS_DLLIST_H

#include <stdint.h>

template<class data>
class dllist {
public:
  class node {
  public:
    node *next;
    node *prev;
    data d;
    node(node *next, node *prev, data d)
      : next(next), prev(prev), d(d) {}
  };
  node *first;
  node *last;

  dllist() : first(0), last(0) {}

  void add_front(data d) {
    node *const n = new node(first, 0, d);
    if (first)
      first->prev = n;
    first = n;
    if (!last)
      last = n;
  }

  void add_back(data d) {
    node *const n = new node(0, last, d);
    if (last)
      last->next = n;
    last = n;
    if (!first)
      first = n;
  }

  //return previous, or zero if this is the first
  node *remove_in_place(node *n) {
    if (n == first)
      first = n->next;
    if (n == last)
      last = n->prev;
    if (n->next)
      n->next->prev = n->prev;
    if (n->prev)
      n->prev->next = n->next;
    delete n;
    return n->prev;
  }

  bool try_remove_by_ref(data d) {
    for (node *n = first; n; n = n->next)
      if (&n->d == &d) {
        remove_in_place(n);
        return true;
      }
    return false;
  }

  //returns -1 if it isn't found
  uint32_t index_of(data d) {
    uint32_t i = 0;
    for (const node *n = first; n; n = n->next)
      if (d == n->d)
        return i;
      else
        ++i;
    return -1;
  }
};

#endif