#pragma once
/*
  dlist.hpp
  Doubly-linked lists of ints
 */
#include <vector>

/* dlist
   Doubly-linked list class. 
*/
class dlist {
  public:
    struct node
    {
        int value;
        node* next;
        node* prev;
    };
  
    /* head(), tail()
       Returns the head/tail nodes of the list. These functions are provided
       for you.
    */
    node* head() const { return hd; }
    node* tail() const { return tl; }

    /* constructor
       You do not need to add any code to the constructor, since lists start
       as empty.
    */
    dlist() { }

    // **************** Implement ALL the following functions ****************

    /* destructor
       Delete all nodes in the list.

       Must run in O(n) time.
    */
    ~dlist();

    /* copy constructor
       Construct a copy of the `original` list. The copy must not share any
       node pointers with the original list.

       Must run in O(n) time.
    */
    dlist(const dlist& original);

    /* a = b  (copy assignment)
       Copy all values in `b` into `a`. After the copy, `a` and `b` must not
       share any node pointers. 

       Must run in O(n) time.
    */
    dlist& operator= (const dlist& original);

    /* at(i)
       Returns a pointer to the i-th node (head = index 0, tail = size() - 1).
       If i < 0, return the head. If i >= size, return the tail.
       
       Must run in O(i) time.
    */
    node* at(int i) const;

    /* insert(a, value)
       Insert a new node after `a`, containing the `value`. If 
       `a == nullptr` then insert the new node *before* the head.

       Must run in O(1) time.
    */
    void insert(node *a, int value);

    /* erase(which)
       Delete the given node. If which == nullptr, then this function does 
       nothing.

       Must run in O(1) time.
    */
    void erase(node* which);

    /* erase(i)
       Erase the node at index i (indexes work as for at()). If i < 0, 
       erase the head, if i >= size(), erase the tail.

       Must run in O(i) time.
    */
    void erase(int i);

    /* remove(x)
       Remove the *first* node whose value is `x`. If `x` does not occur in the 
       list, then nothing should be removed. If multiple nodes have `x` as
       their values, only the first (closest to the head) should be removed.

       Must run in O(n) time.
    */
    void remove(int x);

    /* push_back(value)
       Add a new node containing value at the *end* of the list. 

       Must run in O(1) time.
    */
    void push_back(int value);

    /* push_front(value)
       Add a new node containing value before the head of the list. 

       Must run in O(1) time.
    */
    void push_front(int value);

    /* pop_front()
       Remove the first (head) element. If the list is empty, do nothing.

       Must run in O(1) time.
    */
    void pop_front();

    /* pop_back()
       Remove the last (tail) element. If the list is empty, do nothing.

       Must run in O(1) time.
    */
    void pop_back();

    /* size()
       Returns the size of the list. 

       Must run in O(n) time (an O(1) implementation is fine).
    */
    int size() const;

    /* empty()
       Returns true if the list is empty.

       Must run in O(1) time.
    */
    bool empty() const;

    /* to_vector()
       Converts the list to a vector containing the same values and returns it.

       Must run in O(n) time.
    */
    std::vector<int> to_vector() const;

  private:
    node* hd = nullptr; // Pointer to the first node
    node* tl = nullptr; // Pointer to the last node

    // Add any other private members you need
};