#include <iostream>
#include <stdexcept>
#include <cstdlib>
#include <ctime>
#include <chrono>

namespace vp {
   template<class T>
   class list {
      private:
         struct node {
            node();
            node(T Value, node *pnode);
            node(T Value, node *Prev, node *Next);
            ~node();
            void insert_after(node *pnode);
            void insert_before(node *pnode);
            void remove();
            T value;
            node *prev;
            node *next;
         };
         node *firstNode;
         node *lastNode;
         unsigned int mSize;
         typedef T& reference;
         typedef const T& const_reference;
      public:
         class iterator {
            private:
               node *current;
            public:
               friend class list<T>;
               iterator();
               iterator(node* node);
               reference operator ->();
               reference operator *();
               bool operator ==(const iterator it) const;
               bool operator !=(const iterator it) const;
               iterator& operator ++();
               iterator operator ++(int);
               iterator& operator --();
               iterator operator --(int);
         };
      private:
         typedef const typename vp::list<T>::iterator const_iterator;
      public:
         list();
         list(unsigned n, const_reference value = T());
         list(list<T>& x);
         ~list();
         bool operator == (const list<T>& l);
         bool operator < (const list<T>& l);
         bool operator > (const list<T>& l);
         bool operator != (const list<T>& l);
         bool operator >= (const list<T>& l);
         bool operator <= (const list<T>& l);
         list<T>& operator =(const list<T>& l);
         void assign(iterator first, iterator last);
         void assign(unsigned n, const_reference value);
         reference back();
         const_reference back() const;
         iterator begin();
         const_iterator begin() const;
         void clear();
         bool empty() const;
         iterator end();
         const_iterator end() const;
         iterator erase(iterator it);
         iterator erase(iterator first, iterator last);
         reference front();
         const_reference front() const;
         iterator insert(iterator it, const_reference value);
         void insert(iterator it, unsigned n, const_reference value);
         void insert(iterator it, iterator first, iterator last);
         unsigned max_size() const;
         void merge(list<T> l);
         // void merge (list<T>& l, Compare comp);
         void pop_back();
         void pop_front();
         void push_back(T x);
         void push_front(T x);
         iterator rbegin();
         // reverse_iterator rbegin();
         // const_reverse_iterator rbegin() const;
         void remove(const_reference value);
         // void remove_if(Predicate pred);
         iterator rend();
         // reverse_iterator rend();
         // const_reverse_iterator rend() const;
         void resize(unsigned n, T value = T());
         void reverse();
         unsigned int size() const;
         void sort();
         // void sort(Compare comp);
         // void splice(iterator it, list<T>& l);
         // void splice(iterator it, list<T>& l, iterator i);
         // void splice(iterator it, list<T>& l, iterator first, iterator last);
         void swap(list<T> l);
         void unique();
         void unique(BinaryPredicate binary_pred);
   };
}

/** Node definitions **/
template<class T>
vp::list<T>::node::node() : value(T()), prev(NULL), next(NULL) {}

template<class T>
vp::list<T>::node::node(T Value, node *pnode) :
   value(Value), prev(pnode->prev), next(pnode) {
   pnode->prev = this;

   if (prev)
      prev->next = this;
}

template<class T>
vp::list<T>::node::node(T Value, node *Prev, node *Next) :
   value(Value), prev(Prev), next(Next) {
   if (prev)
      prev->next = this;

   if (next)
      next->prev = this;
}

template<class T>
vp::list<T>::node::~node() {
   remove();
}

template<class T>
void vp::list<T>::node::insert_after(node *pnode) {
   if (!pnode || pnode == this)
      return;

   remove();
   prev = pnode;
   next = pnode->next;

   if (pnode->next)
      pnode->next->prev = this;

   pnode->next = this;
}

template<class T>
void vp::list<T>::node::insert_before(node *pnode) {
   if (!pnode || pnode == this)
      return;

   remove();
   next = pnode;
   prev = pnode->prev;

   if (pnode->prev)
      pnode->prev->next = this;

   pnode->prev = this;
}

template<class T>
void vp::list<T>::node::remove() {
   if (prev)
      prev->next = next;

   if (next)
      next->prev = prev;

   next = prev = NULL;
}

/** Iterator definitions **/
template<class T>
vp::list<T>::iterator::iterator() :
   current(NULL) {}

template<class T>
vp::list<T>::iterator::iterator(node *n) :
   current(n) {}

template<class T>
typename vp::list<T>::reference vp::list<T>::iterator::operator ->() {
   return current->value;
}

template<class T>
typename vp::list<T>::reference vp::list<T>::iterator::operator *() {
   return current->value;
}

template<class T>
bool vp::list<T>::iterator::operator ==(const iterator it) const {
   return (current == it.current);
}

template<class T>
bool vp::list<T>::iterator::operator !=(const iterator it) const {
   return !operator == (it);
}

template<class T>
typename vp::list<T>::iterator& vp::list<T>::iterator::operator ++() {
   if (current)
      current = current->next;

   return *this;
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::iterator::operator ++(int) {
   iterator result = *this;

   if (current)
      current = current->next;

   return result;
}

template<class T>
typename vp::list<T>::iterator& vp::list<T>::iterator::operator --() {
   if (current)
      current = current->prev;

   return *this;
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::iterator::operator --(int) {
   iterator result = *this;

   if (current)
      current = current->prev;

   return result;
}

/** List definitions **/
template<class T>
vp::list<T>::list() :
   firstNode(NULL), lastNode(NULL), mSize(0) {}

template<class T>
vp::list<T>::list(unsigned n, const_reference value) :
   firstNode(NULL), lastNode(NULL), mSize(0) {
   for (unsigned i = 0; i < n; i ++)
      push_back(value);
}

template<class T>
vp::list<T>::list(list<T>& x) :
   firstNode(NULL), lastNode(NULL), mSize(0) {
   for (auto it : x)
      push_back(it);
}

template<class T>
vp::list<T>::~list() {
   while (firstNode != NULL) {
      node *n = firstNode->next;
      delete firstNode;
      firstNode = n;
   }
}

template<class T>
bool vp::list<T>::operator == (const list<T>& l) {
   if (mSize != l.mSize)
      return false;
   for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
      if (*lhsIt != *rhsIt)
         return false;
   return true;
}

template<class T>
bool vp::list<T>::operator < (const list<T>& l) {
   if (mSize < l.mSize)
      return true;
   else if (mSize > l.mSize)
      return false;
   for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
      if (*lhsIt < *rhsIt)
         return true;
      else if (*lhsIt > *rhsIt)
         return false;
   return false;
}

template<class T>
bool vp::list<T>::operator > (const list<T>& l) {
   if (mSize > l.mSize)
      return true;
   else if (mSize < l.mSize)
      return false;
   for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
      if (*lhsIt > *rhsIt)
         return true;
      else if (*lhsIt < *rhsIt)
         return false;
   return false;
}

template<class T>
bool vp::list<T>::operator != (const list<T>& l) {
   return !(*this == l);
}

template<class T>
bool vp::list<T>::operator >= (const list<T>& l) {
   return !(*this < l);
}

template<class T>
bool vp::list<T>::operator <= (const list<T>& l) {
   return !(*this > l);
}

template<class T>
vp::list<T>& vp::list<T>::operator = (const list<T>& l) {
   clear();

   for (T val : l)
      push_back(val);

   return *this;
}

template<class T>
void vp::list<T>::assign(iterator first, iterator last) {
   clear();

   for (; first != last; first ++)
      push_back(*first);
}

template<class T>
void vp::list<T>::assign(unsigned n, const_reference value) {
   clear();

   for (unsigned i = 0; i < n; i ++)
      push_back(value);
}

template<class T>
typename vp::list<T>::reference vp::list<T>::back() {
   if (empty())
      throw std::logic_error("list: Invoked back() on empty list") ;

   return lastNode->value;
}

template<class T>
typename vp::list<T>::const_reference vp::list<T>::back() const {
   if (empty())
      throw std::logic_error("list: Invoked back() on empty list") ;

   return lastNode->value;
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::begin() {
   return iterator(firstNode);
}

template<class T>
typename vp::list<T>::const_iterator vp::list<T>::begin() const {
   return iterator(firstNode);
}

template<class T>
void vp::list<T>::clear() {
   while (firstNode != NULL) {
      node *n = firstNode->next;
      delete firstNode;
      firstNode = n;
   }

   lastNode = firstNode;
   mSize = 0;
}

template<class T>
bool vp::list<T>::empty() const {
   return !mSize;
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::erase(iterator it) {
   if (it != end()) {
      if (firstNode == it.current)
         firstNode = it.current->next;

      if (lastNode == it.current)
         lastNode = it.current->prev;

      mSize --;
      delete(it++).current;
   }

   return it;
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::erase(iterator first, iterator last) {
   for (; first != last; first ++)
      erase(first);

   return (++ last);
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::end() {
   return iterator();
}

template<class T>
typename vp::list<T>::const_iterator vp::list<T>::end() const {
   return iterator();
}

template<class T>
typename vp::list<T>::reference vp::list<T>::front() {
   if (empty())
      throw std::logic_error("list: Invoked front() on empty list") ;

   return firstNode->value;
}

template<class T>
typename vp::list<T>::const_reference vp::list<T>::front() const {
   if (empty())
      throw std::logic_error("list: Invoked front() on empty list") ;

   return firstNode->value;
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::insert(iterator it, const_reference value) {
   iterator result(new node(value, it.current->prev, it.current->next));
   mSize ++;
   return result;
}

template<class T>
void vp::list<T>::insert(iterator it, unsigned n, const_reference value) {
   for (unsigned i = 0; i < n; i ++)
      it = insert(it, value);
}

template<class T>
void vp::list<T>::insert(iterator it, iterator first, iterator last) {
   for (; first != last; first ++)
      it = insert(it, *first);
}

template<class T>
unsigned vp::list<T>::max_size() const {
   return mSize;
}

template<class T>
void vp::list<T>::merge(list<T> l) {
   node *p = firstNode;

   while (l.size()) {
      node *q = l.firstNode;

      if (q->value < p->value) {
         l.firstNode = l.firstNode->next;
         q->insert_before(p);

         if (p == firstNode)
            firstNode = q;

         mSize ++;
         l.mSize --;
      }
      else if (p == lastNode) {
         l.firstNode = l.firstNode->next;
         q->insert_after(p);
         p = lastNode = q;
         mSize ++;
         l.mSize --;
      }
      else
         p = p->next;
   }
}

template<class T>
void vp::list<T>::pop_back() {
   if (empty())
      return;

   node *n = lastNode->prev;
   n->next = NULL;
   delete lastNode;
   lastNode = n;
   mSize --;

   if (empty())
      firstNode = lastNode;
}

template<class T>
void vp::list<T>::pop_front() {
   if (empty())
      return;

   node *n = firstNode->next;
   n->prev = NULL;
   delete firstNode;
   firstNode = n;
   mSize --;

   if (empty())
      lastNode = firstNode;
}

template<class T>
void vp::list<T>::push_back(T x) {
   lastNode = new node(x, lastNode, NULL);

   if (firstNode == NULL)
      firstNode = lastNode;

   mSize ++;
}

template<class T>
void vp::list<T>::push_front(T x) {
   firstNode = new node(x, NULL, firstNode);

   if (lastNode == NULL)
      lastNode = firstNode;

   mSize ++;
}

/** Need to add and change to reverse_iterator **/
template<class T>
typename vp::list<T>::iterator vp::list<T>::rbegin() {
   return iterator(lastNode);
}

template<class T>
void vp::list<T>::remove(const_reference value) {
   for (iterator it(firstNode); it != end(); it ++)
      if (*it == value)
         erase(it);
}

template<class T>
typename vp::list<T>::iterator vp::list<T>::rend() {
   return iterator();
}

template<class T>
void vp::list<T>::resize(unsigned n, T value) {
   if (n < mSize)
      while (mSize > n)
         pop_back();
   else
      for (unsigned i = 0; i < n; i ++)
         push_back(value);
}

template<class T>
void vp::list<T>::reverse() {
   node* temp = lastNode;
   lastNode = firstNode;
   firstNode = temp;

   for (node* tempNode = temp; temp;  temp = temp->next) {
      tempNode = temp->prev;
      temp->prev = temp->next;
      temp->next = tempNode;
   }
}

template<class T>
unsigned int vp::list<T>::size() const {
   return mSize;
}

template<class T>
void vp::list<T>::sort() {
   if (size() <= 1)
      return;

   for (int merges = 0, k = 1; merges != 1; k *= 2) {
      node *p = firstNode, *q = p;

      for (int qsize = merges = 0; p; merges ++, p = q) {
         for (qsize = 0; qsize < k && q; qsize ++, q = q->next);

         while (qsize && q) {
            if (q->value <= p->value) {
               if (q->next) {
                  q = q->next;
                  q->prev->insert_before(p);
               }
               else {
                  q->insert_before(p);
                  q = NULL;
                  lastNode = lastNode->prev;
               }

               if (p == firstNode)
                  firstNode = firstNode->prev;

               qsize --;
            }
            else
               p = p->next;
         }
      }
   }
}

//void splice(iterator it, list<T>& l);
//void splice(iterator it, list<T>& l, iterator i);
//void splice(iterator it, list<T>& l, iterator first, iterator last);

template<class T>
void vp::list<T>::swap(list<T> l) {
   list<T> temp = l;
   l = *this;
   this = temp;
}

template<class T>
void vp::list<T>::unique() {
   for (iterator it = begin(); it != end(); it ++)
      if ((it != begin()) && (*it == it.current->prev->value))
         erase(it --);
}

template<class T>
void vp::list<T>::unique(BinaryPredicate binary_pred) {
   for (iterator it = begin(); it != end(); it ++)
      if ((it != begin()) && (binary_pred(*it, it.current->prev->value)))
         erase(it --);
}

bool isSame(int a, int b) {
   return a == b;
}

int main() {
   vp::list<int> list1, list2;
   for (int i = 0; i < 10; i ++) {
      list1.push_back(i);
      list2.push_back(i);
   }

   list1.pop_back();
   list1.push_back(7);

   list1.sort();
   list1.unique(isSame);

   for (auto it : list1)
      std::cout << *it << "\n";

   return 0;
}