#ifndef LIST_H
#define LIST_H

using namespace std;

template <typename T>
class List
{
private:   
   class Node
   {
   public:
      /** 
          Konstruuje węzeł z podaną wartością danych.
          @param element dane, które mają być zapisane w węźle
      */
      Node(const T& element);
      T data;
      Node* previous;
      Node* next;
   };
public:      
   class Iterator
   {
   public:
      /**
         Konstruuje iterator niewskazujący elementu żadnej listy.
      */
      Iterator();
      /**  
         Wyszukuje wartość na danej pozycji.
         @return wartość węzła wskazywanego przez iterator
      */
      const T& operator*() const;
      /**
         Przesuwa iterator na następny węzeł.
      */
      void operator++(); 
      void operator++(int dummy);
      /**
         Przesuwa iterator na poprzedni węzeł.
      */
      void operator--(); 
      void operator--(int dummy);

      bool operator==(const Iterator& other) const;
      bool operator!=(const Iterator& other) const;
   private:
      Node* position;
      List* container;
   friend class List;
   };
 
   /**
      Konstruuje pustą listę.
   */
   List();

   List(const List& other);
   ~List();
   List& operator=(const List& other);
   
   /**
      Dołącza do listy element.
      @param element dołączana wartość
   */
   void push_back(const T& element);
   /**
      Wstawia element do listy.
      @param iter pozycja, przed którą element ma być wstawiony
      @param element wstawiana wartość
   */
   void insert(const Iterator& iter, const T& element);
   /**
      Usuwa element z listy.
      @param iter pozycja do usunięcia
      @return iterator wskazujący element następny
      po usuwanym
   */
   Iterator erase(const Iterator& iter);
   /**
      Pobiera początkową pozycję listy.
      @return iterator wskazujący na początek listy
   */
   Iterator begin();
   /**
      Pobiera pozycję poza końcem listy.
      @return iterator wskazujący poza koniec listy
   */
   Iterator end();
private:
   void copy(const List& other);
   void free();
   
   Node* first;
   Node* last;
};

template <typename T>
List<T>::Node::Node(const T& element)
{  
   data = element;
   previous = nullptr;
   next = nullptr;
}

template <typename T>
List<T>::List()
{  
   first = nullptr;
   last = nullptr;
}

template <typename T>
void List<T>::push_back(const T& element)
{  
   Node* new_node = new Node(element);
   if (last == nullptr) // Lista jest pusta.
   {  
      first = new_node;
      last = new_node;
   }
   else
   {  
      new_node->previous = last;
      last->next = new_node;
      last = new_node;
   }
}

template <typename T>
void List<T>::insert(const Iterator& iter, const T& element)
{  
   if (iter.position == nullptr)
   {  
      push_back(element);
      return;
   }

   Node* after = iter.position;
   Node* before = after->previous;
   Node* new_node = new Node(element);
   new_node->previous = before;
   new_node->next = after;
   after->previous = new_node;
   if (before == nullptr) // Wstaw na początku.
   {
      first = new_node;
   }
   else
   {
      before->next = new_node;
   }
}

template <typename T>
typename List<T>::Iterator List<T>::erase(const Iterator& iter)
{  
   Node* remove = iter.position;
   Node* before = remove->previous;
   Node* after = remove->next;
   if (remove == first)
   {
      first = after;
   }
   else
   {
      before->next = after;
   }
   if (remove == last)
   {
      last = before;
   }
   else
   {
      after->previous = before;
   }
   delete remove;
   Iterator r;
   r.position = after;
   r.container = this;
   return r;
}

template <typename T>
typename List<T>::Iterator List<T>::begin()
{  
   Iterator iter;
   iter.position = first;
   iter.container = this;
   return iter;
}

template <typename T>
typename List<T>::Iterator List<T>::end()
{  
   Iterator iter;
   iter.position = nullptr;
   iter.container = this;
   return iter;
}

template <typename T>
List<T>::Iterator::Iterator()
{  
   position = nullptr;
   container = nullptr;
}

template <typename T>
const T& List<T>::Iterator::operator*() const
{  
   return position->data;
}

template <typename T>
void List<T>::Iterator::operator++()
{  
   position = position->next;
}

template <typename T>
void List<T>::Iterator::operator++(int dummy)
{  
   operator++();
}

template <typename T>
void List<T>::Iterator::operator--()
{  
   if (position == nullptr)
   {
      position = container->last;
   }
   else 
   {
      position = position->previous;
   }
}

template <typename T>
void List<T>::Iterator::operator--(int dummy)
{
   operator--();
}

template <typename T>
bool List<T>::Iterator::operator==(const Iterator& other) const
{  
   return position == other.position;
}

template <typename T>
bool List<T>::Iterator::operator!=(const Iterator& other) const
{  
   return position != other.position;
}

template <typename T>
void List<T>::free()
{
   Node* to_delete = first;
   while (to_delete != nullptr)
   {
      Node* next_to_delete = to_delete->next;
      delete to_delete;
      to_delete = next_to_delete;
   }
}

template <typename T>
void List<T>::copy(const List& other)
{
   Node* just_copied = nullptr;
   Node* next_to_copy = other.first;
   first = nullptr;
   last = nullptr;
   while (next_to_copy != nullptr)
   {
      Node* copy = new Node(next_to_copy->data);
      copy->previous = just_copied;
      if (just_copied == nullptr)
      {
         first = copy;
      }
      else
      {
         just_copied->next = copy;
      }
      if (next_to_copy == other.last)
      {
         last = copy;
      }
      next_to_copy = next_to_copy->next;
      just_copied = copy;
   }
}

template <typename T>
List<T>::List(const List& other)
{
   copy(other);
}

template <typename T>
List<T>::~List()
{
   free();
}

template <typename T>
List<T>& List<T>::operator=(const List& other)
{
   if (this != &other)
   {
      free();
      copy(other);
   }      
}

#endif

