#ifndef LIST_H
#define LIST_H

#include <iostream>

namespace ecci
{

template <typename DataType>
class List
{
  private:
	class Node
	{
	  public:
		DataType data;
		Node* previous;
		Node* next;

	  public:
		Node(const DataType& data, Node* previous = nullptr, Node* next = nullptr)
			: data(data)
			, previous(previous)
			, next(next)
		{
		}
	};

  public:
	class Iterator
	{
	  friend class List;
	  private:
		Node* node;

	  public:
		Iterator(Node* node) : node(node) {}
		inline DataType& operator*() const { return node->data; }
		inline bool operator!=(const Iterator& other) const { return node != other.node; }
		const Iterator& operator++()
		{
			if (node)
				node = node->next;
			return *this;
		}
		const Iterator operator++(int) // post-increment
		{
			Iterator copyBefore(*this);
			if (node)
				node = node->next;
			return copyBefore;
		}
	};

	class ConstIterator
	{
	  friend class List;
	  private:
		Node* node;

	  public:
		ConstIterator(Node* node) : node(node) {}
		inline const DataType& operator*() const { return node->data; }
		inline bool operator!=(const ConstIterator& other) const { return node != other.node; }
		const ConstIterator& operator++()
		{
			if (node)
				node = node->next;
			return *this;
		}
		const ConstIterator operator++(int) // post-increment
		{
			ConstIterator copyBefore(*this);
			if (node)
				node = node->next;
			return copyBefore;
		}
	};

  protected:
	Node* head;
	Node* tail;
	size_t count;

  public:
	/// Default constructor
	List() : head(nullptr), tail(nullptr), count(0) { }
	/// Copy constructor
	List(const List<DataType>& other) : head(nullptr), tail(nullptr), count(other.count) { copy(other); }
	/// Copy assignment operator
	const List<DataType>& operator=(const List<DataType>& other)
	{
		if ( this == other ) return *this;
		if ( count == other.count )
		{
			for ( Node * c1 = head, * c2 = other.head; c2; c1 = c1->next, c2 = c2->next )
				c1->data = c2->data;
		}
		else
		{
			clear();
			copy(other);
		}
		return *this;
	}
	/// Move constructor
	List(List<DataType>&& temp) : head(temp.head), tail(temp.tail), count(temp.count)
	{
		temp.head = temp.tail = nullptr;
	}
	/// Move assignment operator
	const List<DataType>& operator=(const List<DataType>&& temp)
	{
		if ( this != temp )
		{
			clear();
			head = temp.head;
			tail = temp.tail;
			count = temp.count;

			temp.head = temp.tail = nullptr;
		}
	}
	/// Destructor
	~List() { clear(); }
	/// Empties the list
	void clear()
	{
		for (Node* current = head; current; current = head)
		{
			head = head->next;
			delete current;
		}
	}
	/// Adds an element to the list, returns true on success, false when no enough memory
	bool add(const DataType& data)
	{
		if ( head == nullptr )
			return head = tail = new Node(data);

		if ( ( tail->next = new Node(data, tail) ) != nullptr )
			return tail = tail->next;
		return false;
	}
	/// Prints all elements to the given output file
	/// @remarks Assumes DataType can be printed
	std::ostream& print(std::ostream& out, const char* const separator = ", ") const
	{
		for ( Node* current = head; current != nullptr; current = current->next )
			out << current->data << separator;
		return out;
	}
	/// Returns an iterator to the first element of the list
	Iterator begin() const { return Iterator(head); }
	/// Returns a no valid iterator, indicating the end of the list
	Iterator end() const { return Iterator(nullptr); }
	/// Returns an iterator to the first element of the list
	ConstIterator constBegin() const { return ConstIterator(head); }
	/// Returns a no valid iterator, indicating the end of the list
	ConstIterator constEnd() const { return ConstIterator(nullptr); }
	/// If @a elem is the list, returns a valid iterator to it, or an invalid iterator otherwise
	Iterator find(const DataType& elem, Iterator start) const
	{
		for ( Iterator enditr = end(); start != enditr; ++start )
			if ( *start == elem )
				return start;

		return end();
	}
	inline Iterator find(const DataType& elem) const { return find(elem, begin()); }
	/// If @a elem is the list, returns a valid iterator to it, or an invalid iterator otherwise
	ConstIterator find(const DataType& elem, ConstIterator start) const
	{
		for ( ConstIterator enditr = constEnd(); start != enditr; ++start )
			if ( *start == elem )
				return start;

		return constEnd();
	}
	inline ConstIterator constFind(const DataType& elem) const { return find(elem, constBegin()); }
	bool insertBefore(Iterator& itr, const DataType& elem)
	{
		if ( ! itr.node ) return false;
		Node* newNode = new Node(elem, itr.node->previous, itr.node);
		if ( ! newNode ) return false;
		if ( itr.node->previous )
			itr.node->previous->next = newNode;
		itr.node->previous = newNode;
		return true;
	}
	bool insertAfter(Iterator& itr, const DataType& elem)
	{
		if ( ! itr.node ) return false;
		Node* newNode = new Node(elem, itr.node, itr.node->next);
		if ( ! newNode ) return false;
		if ( itr.node->next )
			itr.node->next->previous = newNode;
		itr.node->next = newNode;
		return true;
	}
	bool operator==(const List<DataType>& other) const
	{
		if ( count != other.count ) return false;

		for ( Node * c1 = head, * c2 = other.head; c2; c1 = c1->next, c2 = c2->next )
			if ( ! ( c1->data == c2->data ) )
				return false;

		return true;
	}

  protected:
	/// Adds copies of all elements of the given the list
	void copy(const List<DataType>& other)
	{
		for ( Node* current = other.head; current; current = current->next )
			add(current->data);
	}
};

} // namespace ecci

template <typename DataType>
inline std::ostream& operator<<(std::ostream& out, const ecci::List<DataType>& list)
{
	return list.print(out);
}

#endif // LIST_H