#ifndef dlist_hxx_
#define dlist_hxx_

//===========================================================================

#include <algorithm>  // For std::swap
#include <limits>     // For std::numeric_limits
#include <cstddef>    // For std::size_t and std::ptrdiff_t
#include <iterator>   // For std::iterator
#include <initializer_list>

//===========================================================================

//
// dlist, dlist_iter, dlist_citer
// forward class declarations
//
template <typename T> class dlist;
template <typename T> class dlist_node;
template <typename T> class dlist_iter;
template <typename T> class dlist_citer;

//
// Forward declare some functions...
//
template <typename T>
void swap(dlist_node<T>& a, dlist_node<T>& b);

template <typename T>
void swap(dlist_iter<T>& a, dlist_iter<T>& b);

template <typename T>
void swap(dlist_citer<T>& a, dlist_citer<T>& b);

template <typename T>
void swap(dlist<T>& a, dlist<T>& b);

//===========================================================================

//
// dlist_node
// struct
//
// Represents a node in a doubly-linked list.
//
template <typename T>
class dlist_node
{
public:
  dlist_node()
  : prev_{nullptr}, next_{nullptr}// Set prev_ and next_ to nullptr here.
  {
  }

  dlist_node(dlist_node const& n) = delete;
  dlist_node& operator =(dlist_node& node) = delete;

  dlist_node(dlist_node&& n)
  : prev_{n.prev_},next_{n.next_},datum_{std::move(n.datum_)}// Set datum_, prev_, and next_.
  // Remember to move
  {
    // Remember to set n's pointers to nullptr.
    n.prev_= n.next_ = nullptr;
  }

  dlist_node& operator =(dlist_node&& n)
  {
    // Similar to move constructor code.
    swap(*this,std::move(n));
    return *this;
  }

  ~dlist_node() = default;

  dlist_node(T const& d, dlist_node* p=nullptr, dlist_node* n=nullptr)
    : prev_{p},next_{n},datum_{d}// Set datum_, prev_, and next_.
  {
  }

  dlist_node(T&& d, dlist_node* p=nullptr, dlist_node* n=nullptr)
    : prev_{p},next_{n},datum_{std:move(d)}// Set datum_, prev_, and next_.

    // Remember to move.
  {
  }

  T& datum()
  {
    // Return datum_
    return datum_;
  }

  T const& datum() const
  {
    // Return datum_
    return datum_;
  }

  T&& datum_as_rvalue()
  {
    // Return datum_. Ensure it is an rvalue.
    return std::move(datum_);
  }

  dlist_node* prev()
  {
    // Return prev_
    return prev_;
  }

  dlist_node const* prev() const
  {
    // Return prev_
    return prev_;
  }

  dlist_node* next()
  {
    // Return next_
    return next_;
  }

  dlist_node const* next() const
  {
    // Return next_
    return next_;
  }

  dlist_node* insert_before(T const& datum, dlist_node*& head)
  {
    // This function has been done for you.
    // Notice that a copy is made as it passes the arguments
    // to other insert_before() function...
    return insert_before(T(datum), head);
  }

  dlist_node* insert_before(T&& datum, dlist_node*& head)
  {
    // Dynamically allocate a new dlist_node. Call it node.
    // if prev_ is not null then
    //   prev_'s next_ pointer must be set to node
    // otherwise
    //   head must be set to node
    // And finally prev_ must be set to node.
    // return node;
    auto node = new dlist_node(datum, this->prev_, this);
    if (this->prev_ != nullptr)
       this->prev_->next_ = node;
    else
        head = node;
    this->prev_ = node;
    return node;
  }

  dlist_node* insert_after(T const& datum, dlist_node*& tail)
  {
    // This function has been done for you.
    // Notice that a copy is made as it passes the arguments
    // to other insert_after() function...
    return insert_after(T(datum), tail);
  }

  dlist_node* insert_after(T&& datum, dlist_node*& tail)
  {
    // Dynamically allocate a new dlist_node. Call it node.
    // if next_ is not null then
    //   next_'s prev_ pointer must be set to node
    // otherwise
    //   tail must be set to node
    // And finally next_ must be set to node.
    // return node;
    auto node = new dlist_node(std::forward<T>(datum), this, this->next_);
    if(this->next_!=nullptr)
        this->next_->prev_ = node;
    else
        tail = node;
    this->next_=node;
    return node;

  }

  // Remove this node from the list...
  static void remove(
    dlist_node* del, dlist_node*& head, dlist_node*& tail)
  {
    // if del's prev_ node is not null
    //   del's prev_'s next_ pointer must be set to del's next_
    // otherwise
    //   head must be set to del's next_
    if(del->prev_!=nullptr)
        del->prev_->next_ = del->next_;
    else
        head = del->next_;

    // if del's next_ node is not null
    //   del's next_'s prev_ pointer must be set to del's prev_
    // otherwise
    //   tail must be set to del's prev_
    if(del->next_!=nullptr)
        del->next_->prev_ = del->prev_;
    else
        tail = del->prev_;

    // deallocate del
    delete del;
  }

  friend void swap<>(dlist_node<T>& a, dlist_node<T>& b);

private:
  T datum_;           // Holds the datum
  dlist_node* prev_;  // Points to the previous node
  dlist_node* next_;  // Points to the next node
};

//===========================================================================

template <typename T>
inline void swap(dlist_node<T>& a, dlist_node<T>& b)
{
  using std::swap;            // Needed.

  // swap a and b's prev_
  // swap a and b's next_
  // swap a and b's datum_
  swap(a.datum_, b.datum_); // placed first just in case it throws an exception!
  swap(a.prev_, b.prev_); // copying pointers will never throw
  swap(a.next_, b.next_); // copying pointers will never throw
}

//===========================================================================

//
// dlist<T>
// class
//
template <typename T>
class dlist
{
  friend class dlist_iter<T>;       // Needed for head_/tail_ access
  friend class dlist_citer<T>;      // Needed for head_/tail_ access

public:
  typedef T value_type;

  typedef T& reference;
  typedef T const& const_reference;

  typedef T* pointer;
  typedef T const* const_pointer;

  typedef dlist_iter<T> iterator;
  typedef dlist_citer<T> const_iterator;

  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;


  dlist()
      : head_{nullptr},tail_{nullptr}
    // Set head_ and tail_ to null
  {
  }

  dlist(size_type n, T const& value = T())
     : dlist()
    // invoke default constructor
  {
    // call std::fill_n
    //   - use std::back_inserter to append elements
    //   - pass in n and value
    std::fill_n(std::back_inserter(this),n,value);
  }

  dlist(std::initializer_list<T> i)
     : dlist()
    // invoke default constructor
  {
    // call std::copy
    //   - use i.begin() and i.end()
    //   - use std::back_inserter to append elements
    std::copy(i.begin(),i.end(),std::back_inserter(this));
  }

  template <typename InIter>
  dlist(InIter first, InIter last)
     : dlist()
    // invoke default constructor
  {
    // call std::copy
    //   - use back_inserter to append elements
    std::copy(first,last,std::back_inserter(*this));
  }

  dlist(dlist<T> const& l)
     : dlist()
    // invoke default constructor
  {
    // call std::copy
    //   - use back_inserter to append elements
    std::copy(l.begin,l.end(),std::back_inserter(*this));
  }

  dlist(dlist<T>&& l) noexcept
  {
    // call swap()
    swap(l);
  }

  ~dlist()
  {
    // call clear()
    clear();
  }

  dlist<T>& operator =(dlist<T> const& l)
  {
    // make a copy of l
    // call swap() with the copy
    // return
    dlist<T> tmp = l;
    swap(tmp);
    return *this;
  }

  dlist<T>& operator =(dlist<T>&& l)
  {
    // call swap() on argument
    // return
    swap(l);
    return *this;
  }

  void assign(std::initializer_list<T> i)
  {
    // make a dlist using i
    // swap dlist with *this
    swap(dlist(i));
  }

  void assign(size_type n, value_type const& value)
  {
    // make a dlist using arguments
    // swap
    swap(dlist(n,value));
  }

  template <typename InIter>
  void assign(InIter first, InIter last)
  {
    // make a dlist using arguments
    // swap
    swap(dlist(first,last));
  }

  template <typename... Args>
  iterator emplace(iterator pos, Args&&... args)
  {
    // This function has been provided for you.
    if (empty())
    {
      head_ = tail_ = new dlist_node<T>(
        value_type(std::forward<Args>(args)...)
      );
      pos = dlist_iter<T>(this, tail_);
    }
    else
    {
      if (pos.curpos_ == nullptr)
      {
        auto loc = tail_->insert_after(
          value_type(std::forward<Args>(args)...),
          tail_
        );
        pos = dlist_iter<T>(this, loc);
      }
      else
      {
        auto loc = pos.curpos_->insert_before(
          value_type(std::forward<Args>(args)...),
          head_
        );
        pos = dlist_iter<T>(this, loc);
      }
    }

    return pos;
  }

  template <typename... Args>
  void emplace_front(Args&&... args)
  {
    // call emplace()
    //   - pass an iterator object that represents the
    //     start of the list
    //   - forward all args...
    emplace(begin(),std::forward<Args>(args)...);
  }

  template <typename... Args>
  void emplace_back(Args&&... args)
  {
    // call emplace()
    //   - pass an iterator object that represents the
    //     end of the list
    //   - forward all args...
    emplace(end(),std::forward<Args>(args)...);
  }

  iterator begin()
  {
    // return a begin dlist_iter<T>
    return dlist_iter<T>(this,head_);
  }

  const_iterator begin() const
  {
    // return a begin dlist_citer<T>
    return dlist_citer<T>(this,head_);
  }

  const_iterator cbegin() const
  {
    // return a begin dlist_citer<T>
    return dlist_citer<T>(this,head_);
  }

  reverse_iterator rbegin()
  {
    // return correct reverse_iterator
    return dlist_iter<T>(std::reverse(head_));
  }

  const_reverse_iterator rbegin() const
  {
    // return correct reverse_iterator
    return dlist_citer<T>(std::reverse(head_));
  }

  const_reverse_iterator crbegin() const
  {
    // return correct reverse_iterator
    return dlist_citer<T>(std::reverse(head_));
  }

  iterator end()
  {
    // return an end dlist_iter<T>
    return dlist_iter<T>(tail_);
  }

  const_iterator end() const
  {
    // return an end dlist_citer<T>
    return dlist_citer<T>(tail_);

  }

  const_iterator cend() const
  {
    // return an end dlist_citer<T>
    return dlist_citer<T>(tail_);
  }

  reverse_iterator rend()
  {
    // return the correct reverse_iterator
    return dlist_iter<T>(std::reverse(tail_));
  }

  const_reverse_iterator rend() const
  {
    // return the correct reverse_iterator
    return dlist_citer<T>(std::reverse(tail_));
  }

  const_reverse_iterator crend() const
  {
    // return the correct reverse_iterator
    return dlist_citer<T>(std::reverse(tail_));
  }

  bool empty() const
  {
    // This has been provided for you...
    return head_ == nullptr;
  }

  size_type size() const
  {
    // Write code to compute the size.
    dlist_iter<T> tmp = head_;
    int i = 0;
    while(tmp!=nullptr){
      tmp++;
      i++;
    }
    return i;
  }

  size_type max_size() const
  {
    // This has been provided for you...
    return std::numeric_limits<size_type>::max();
  }

  reference front()
  {
    // return the first element
    return &head_;
  }

  const_reference front() const
  {
    // return the first element
    return head_;
  }

  reference back()
  {
    // return the last element
    return tail_;
  }

  const_reference back() const
  {
    // return the last element
    return tail_;
  }

  void push_front(value_type const& i)
  {
    // if empty() then
    //   head_ = tail_ = new node
    // otherwise
    //   insert_before the first node in the list

   if(empty())
     head_= tail_= new dlist_node<T>(value_type(i));
    else
      head_->insert_before(T(i),head_);



  }

  void push_front(value_type&& i)
  {
    // Same as lvalue push_front() except
    //   - remember to std::forward all value_type arguments
     if(empty())
       head_=tail_= new dlist_node<T>(value_type(std::forward<value_type>(i)));
    else
     head_->insert_before(T(std::forward<value_type>(i)),head_);

  }

  void pop_front()
  {
    // call dlist_node<T>::remove() appropriately
    head_->remove(head_,head_,tail_);
  }

  void push_back(value_type const& i)
  {
    // if empty() then
    //   head_ = tail_ = new node
    // otherwise
    //   insert_after the last node in the list
    if(empty())
      head_=tail_=new dlist_node<T>(value_type(i));
    else
      tail_->insert_after(T(i),tail_);
  }

  void push_back(value_type&& i)
  {
    // Same as lvalue push_back() except
    //   - remember to std::forward all value_type arguments
    if(empty())
      head_= tail_=new dlist_node<T>(T(std::forward<value_type>(i)));
    else
      tail_->insert_after(T(std::forward<value_type>(i)),tail_);
  }

  void pop_back()
  {
    // call dlist_node<T>::remove() appropriately
    tail_->remove(tail_,head_,tail_);
  }

  iterator insert(iterator pos, value_type const& value)
  {
    // identical to emplace() except there are no moves or forwards
    if (empty()){
      head_=tail_=new dlist_node<T>(value);
      pos = dlist_iter<T>(this,tail_);
    }
    else{
      if(pos.curpos_ == nullptr){
    auto loc = tail_->insert_after(value,tail_);
    pos = dlist_iter<T>(this,loc);
      }
      else{
    auto loc = pos.curpos_->insert_before(value,head_);
    pos = dlist_iter<T>(this,loc);
      }
    }
    return pos;
  }

  template <typename InIter>
  void insert(iterator pos, InIter first, InIter last)
  {
    // loop through [first,last) calling insert(pos,value)
    while(first!=last){
      insert(pos,pos->value);
      first = first->next_;
    }
  }

  iterator erase(iterator pos)
  {
    // make a copy of pos
    // ++ the copy
    //   - NOTE: This is needed because when the node is destroyed the
    //     iterator is invalid. Thus, one needs to move to the next node
    //     BEFORE the current one is destroyed. Otherwise, the proper
    //     return value cannot be computed.
    // remove the node
    // return the copy
    dlist_iter<T> tmp = pos;
    ++tmp;
    remove(pos);
    return tmp;
  }

  iterator erase(iterator pos, iterator last)
  {
    // loop through [pos,last) calling erase()
    // return pos
    while(pos!=last){
      dlist_iter<T> tmp = pos;
      ++pos;
      erase(tmp);
    }
    return pos;
  }

  void swap(dlist& l) noexcept
  {
    using std::swap;        // Needed

    // swap the head_s
    // swap the tail_s
    swap(head_,l.head_);
    swap(tail_,l.tail_);

  }

  void clear()
  {
    // loop while the list is not empty
    //   remove the first node
    dlist_node<T>* tmp = head_;
    while(size() !=0){

      head_=head_->next();
      head_->remove(tmp,head_,tail_);
      tmp = head_;
    }

    // NOTE: There are multiple ways to do this. The above method is a
    //       straight-forward one.
  }

private:
  dlist_node<T>* head_;
  dlist_node<T>* tail_;
};

//===========================================================================

template <typename T>
bool operator ==(dlist<T> const& a, dlist<T> const& b)
{
  using std::begin;
  using std::end;
  dlist_iter<T> abegin = a.begin();
  dlist_iter<T> aend = a.end();
  dlist_iter<T> bbegin = b.begin();
  dlist_iter<T> bend = b.end();

  if(a.size()!=b.size())
    return false;

  // write a for loop to simultaneously iterator through a and b
  // to determine if they are the same
  while(abegin!= b.end() && bbegin!=bend){
    if(abegin != bbegin){
      return false;
      break;
    }
    else{
      abegin = abegin->next_;
      bbegin = bbegin->next_;
    }
  }
  return true;

  // abort the loop once different elements are found, or,
  // if the end of either list is arrived at

  // remember to ensure the return value returns false if the
  // lists are not identical in size

  // you are only allowed to iterators and a bool variable in this
  // function
}

template <typename T>
inline bool operator !=(dlist<T> const& a, dlist<T> const& b)
{
  // Provided for you...
  return !operator ==(a,b);
}

template <typename T>
inline bool operator <(dlist<T> const& a, dlist<T> const& b)
{
  // Provided for you...
  return std::lexicographical_compare(
    a.begin(), a.end(),
    b.begin(), b.end()
  );
}

template <typename T>
inline bool operator <=(dlist<T> const& a, dlist<T> const& b)
{
  // a <= b is the same as !(b < a)
  // Write the code in terms of <.
  if (!(b < a))
    return true;
  else
    return false;
}

template <typename T>
inline bool operator >(dlist<T> const& a, dlist<T> const& b)
{
  // a > b is the same as b < a
  // Write the code in terms of <.
  if(b<a)
    return true;
  else
    return false;
}

template <typename T>
inline bool operator >=(dlist<T> const& a, dlist<T> const& b)
{
  // a >= b is the same as !(a < b)
  // Write the code in terms of <.
  if(!(a<b))
    return true;
  else
    return false;
}

template <typename T>
inline void swap(dlist<T>& a, dlist<T>& b)
{
  // This function is trival: it simply calls dlist's swap().
  swap(a,b);
}

template <typename T>
inline auto begin(dlist<T>& a) -> decltype(a.begin())
{
  // Provided for you...
  return a.begin();
}

template <typename T>
inline auto begin(dlist<T> const& a) -> decltype(a.begin())
{
  // Provided for you...
  return a.begin();
}

template <typename T>
inline auto cbegin(dlist<T> const& a) -> decltype(a.cbegin())
{
  // Provided for you...
  return a.cbegin();
}

template <typename T>
inline auto rbegin(dlist<T>& a) -> decltype(a.rbegin())
{
  // Provided for you...
  return a.rbegin();
}

template <typename T>
inline auto rbegin(dlist<T> const& a) -> decltype(a.rbegin())
{
  // Provided for you...
  return a.rbegin();
}

template <typename T>
inline auto crbegin(dlist<T> const& a) -> decltype(a.crbegin())
{
  // Provided for you...
  return a.crbegin();
}

template <typename T>
inline auto end(dlist<T>& a) -> decltype(a.end())
{
  // Provided for you...
  return a.end();
}

template <typename T>
inline auto end(dlist<T> const& a) -> decltype(a.end())
{
  // Provided for you...
  return a.end();
}

template <typename T>
inline auto cend(dlist<T> const& a) -> decltype(a.cend())
{
  // Provided for you...
  return a.cend();
}

template <typename T>
inline auto rend(dlist<T>& a) -> decltype(a.rend())
{
  // Provided for you...
  return a.rend();
}

template <typename T>
inline auto rend(dlist<T> const& a) -> decltype(a.rend())
{
  // Provided for you...
  return a.rend();
}

template <typename T>
inline auto crend(dlist<T> const& a) -> decltype(a.crend())
{
  // Provided for you...
  return a.crend();
}

//===========================================================================

//
// dlist_iter
// class
//
// This class represents an iterator that operates on dlist.
//
template <typename T>
class dlist_iter :
  public std::iterator<
    std::bidirectional_iterator_tag, T
  >
{
  friend class dlist<T>;          // Permit access to private constructor
  friend class dlist_citer<T>;    // Permit access to member variables

  explicit dlist_iter(dlist<T>* l, dlist_node<T>* n)
    : list_(l), curpos_(n)// Set list_ and curpos_
  {
  }

public:
  dlist_iter(dlist_iter const& iter) = default;
  dlist_iter& operator =(dlist_iter const& iter) = default;

  bool operator ==(dlist_iter const& iter) const
  {
    // member variable equality test
    //check this
    return(curpos_ == iter.curpos_);
  }

  bool operator !=(dlist_iter const& iter) const
  {
    // member variable inequality test
    //check this
    return (curpos_!=iter.curpos_);
  }

  T& operator *() const
  {
    // Provided for you...
    return curpos_->datum();
  }

  T* operator ->() const
  {
    // return a pointer --not a reference!
    return &curpos_->datum_;
  }

  dlist_iter& operator ++()
  {
    // set curpos_ to the next pointer value
    // return this object
    curpos_ = curpos_->next();
    return *this;

  }

  dlist_iter operator ++(int)
  {
    // make a copy of the iterator
    // call the prefix ++ operator
    // return the copy
    dlist_iter tmp = *this;
    operator ++();
    return tmp;
  }

  dlist_iter& operator --()
  {
    // NOTE: Take care with this code. It is not as simple as
    //       the ++ operator since the end is one past the real
    //       end and so curpos_ can be null!

    // if curpos_ is not null, then
    //   set curpos_ to the prev position
    // otherwise
    //   set curpos_ to pointer to the last node in the list
    if(curpos_!=nullptr)
        curpos_=curpos_->prev_;
    else
        curpos_ = list_->tail_;
        return *this;

    // return this object
  }

  dlist_iter operator --(int)
  {
    // Very similar to the ++ postfix operator
    dlist_iter tmp = *this;
    operator --();
    return tmp;
  }

  friend void swap<>(dlist_iter<T>& a, dlist_iter<T>& b);

private:
  dlist<T>* list_;
  dlist_node<T>* curpos_;
};

//===========================================================================

template <typename T>
inline void swap(dlist_iter<T>& a, dlist_iter<T>& b)
{
  using std::swap;              // Needed

  // swap a and b's list_ and curpos_ variables
  swap(a.list_,b.list_);
  swap(a.curpos_,b.curpos_);
}

//===========================================================================

//
// dlist_citer
// class
//
// This class represents an constant iterator that operates on dlist.
//
template <typename T>
class dlist_citer :
  public std::iterator<
    std::bidirectional_iterator_tag,
    T const, std::ptrdiff_t, T const*, T const&
  >
{
  friend class dlist<T>;      // Permit access to private constructor

  explicit dlist_citer(dlist<T> const* l, dlist_node<T> const* n)
    : list_(l),curpos_(n)// Set list_ and curpos_
  {
  }

public:
  //check this
  dlist_citer(dlist_iter<T> const& iter)
    : list_(iter->list_),curpos_(iter->curpos_)// Set list_ and curpos_
  {
  }

  dlist_citer(dlist_citer const& iter) = default;

  dlist_citer& operator =(dlist_iter<T> const& iter)
  {
    // Set list_ and curpos_
    // return *this;
    list_=iter->list_;
    curpos_=iter->curpos_;
    return *this;

  }

  dlist_citer& operator =(dlist_citer const& iter) = default;

  bool operator ==(dlist_citer const& iter) const
  {
    // Return true if the iterators are the same
    //check this
    return (*this == iter);
  }

  bool operator !=(dlist_citer const& iter) const
  {
    // Return true if the iterators are not the same
    //check this
    return(*this != iter);
  }

  bool operator ==(dlist_iter<T> const& iter) const
  {
    // Return true if the iterators are the same
    //check this
    return (*this == iter);
  }

  bool operator !=(dlist_iter<T> const& iter) const
  {
    // Return true if the iterators are not the same
    //check this
    return (*this != iter);
  }

  T const& operator *() const
  {
    // Return the datum...
    // check this
    return curpos_->datum();
  }

  T const* operator ->() const
  {
    // Return the datum (as a pointer)
    return &curpos_->datum_;
  }

  dlist_citer& operator ++()
  {
    // Similar to dlist_iter's prefix ++
    curpos_ = curpos_->next_;
    return *this;

  }

  dlist_citer operator ++(int)
  {
    // Similar to dlist_iter's postfix ++
    dlist_citer tmp = curpos_;
    operator ++();
    return tmp;
  }

  dlist_citer& operator --()
  {
    // Similar to dlist_iter's prefix --
    if(*this != nullptr)
             curpos_ = curpos_->prev_;
    else
             curpos_ = list_->tail_;
    return *this;
  }

  dlist_citer operator --(int)
  {
    // Similar to dlist_iter's postfix --
    dlist_citer tmp = curpos_;
    operator --();
    return tmp;
  }

  friend void swap<>(dlist_citer<T>& a, dlist_citer<T>& b);

private:
  dlist<T> const* list_;
  dlist_node<T> const* curpos_;
};

//===========================================================================

template <typename T>
void swap(dlist_citer<T>& a, dlist_citer<T>& b)
{
  using std::swap;

  // swap a and b's list_ and curpos_
  swap(a.list_,b.list_);
  swap(a.curpos_,b.curpos_);
}

//===========================================================================

#endif // #ifndef dlist_hxx_