// basic setup for a useable doubly linked list.
//
// some of this may seem like a pain initially, but some of the decisions
// made here can make things easier down the road. e.g.:
//
// decoupling linked list data and user data.
// defining iterators, especially one capable of interacting with the STL.
// using an object rather than a pointer for the head node.
// using a circular list rather than terminating with NULL.
//
// this omits a lot, but should be a fairly decent base to build on.

#include <algorithm>
#include <iterator>

// ListNodeBase
// basic linked list data and operations.
struct ListNodeBase
{
	ListNodeBase* next;
	ListNodeBase* prev;
	
	// setup as circular by default.
	ListNodeBase()
		: next(this), prev(this) {}
	void reset()
	{ next = prev = this; }

	static void link(ListNodeBase* position, ListNodeBase* x);
	static ListNodeBase* unlink(ListNodeBase* position);
	static void swap(ListNodeBase* a, ListNodeBase* b);
};

void ListNodeBase::link(ListNodeBase* position, ListNodeBase* x)
{
	x->next = position;
	x->prev = position->prev;
	position->prev->next = x;
	position->prev = x;
}

ListNodeBase* ListNodeBase::unlink(ListNodeBase* position)
{
	position->next->prev = position->prev;
	position->prev->next = position->next;
	return position->next;
}

void ListNodeBase::swap(ListNodeBase* a, ListNodeBase* b)
{
	ListNodeBase* anext = a->next;
	ListNodeBase* aprev = a->prev;
	ListNodeBase* bnext = b->next;
	ListNodeBase* bprev = b->prev;
	
	anext->prev = aprev->next = b;
	bnext->prev = bprev->next = a;
	std::iter_swap(a, b);
}

// ListNode
// append user data to link list node.
template<typename Tp>
struct ListNode : public ListNodeBase
{
	Tp data;
	// @todo support parameter packs.
	ListNode(const Tp& x)
		: data(x) {}
};

// ListIterator
// user interface for linked list traversal and access.
template<typename Tp>
struct ListIterator
{
	// set standard typedefs (enable use of STL functions).
	typedef std::bidirectional_iterator_tag iterator_category;
	typedef std::ptrdiff_t	difference_type;
	typedef Tp				value_type;
	typedef Tp*				pointer;
	typedef Tp&				reference;
	
	ListIterator(ListNodeBase* initial = nullptr)
		: m_base(initial) {}
		
	reference operator*()
	{ return base()->data; }
	pointer operator->()
	{ return std::addressof(operator*()); }
	
	ListIterator& operator++()
	{ m_base = m_base->next; return *this; }
	ListIterator& operator--()
	{ m_base = m_base->prev; return *this; }
	
	ListIterator operator++(int)
	{ ListIterator temp = *this; ++*this; return temp; }
	ListIterator operator--(int)
	{ ListIterator temp = *this; --*this; return temp; }
	
	bool operator==(const ListIterator& other) const
	{ return m_base == other.m_base; }
	bool operator!=(const ListIterator& other) const
	{ return !(*this == other); }
	
	// downcast to user type.
	ListNode<Tp>* base()
	{ return static_cast<ListNode<Tp>*>(m_base); }
private:
	ListNodeBase* m_base;
};

// ListIterator (non-member)
// @note uncommon extension for bidirectional iterators.
template<typename Tp>
inline ListIterator<Tp> operator+(ListIterator<Tp> i,
		typename ListIterator<Tp>::difference_type c)
{
	std::advance(i, c);
	return i;
}

// List
// @todo add more methods.
template<typename Tp>
struct List
{
	// @todo fill in standard typedefs.
	typedef ListIterator<Tp> iterator;
	typedef Tp   value_type;
	
	~List()
	{ clear(); }
	
	List() = default;
	List(const List& other)
	{ std::copy(other.begin(), other.end(), std::back_inserter(*this)); }
	
	List(List&& other)
	{ swap(other); }
	List& operator=(List other)
	{ swap(other); return *this; }
	
	iterator begin()
	{ return iterator(m_head.next); }
	iterator end()
	{ return iterator(&m_head); }	
	
	// @todo movable and emplace variations.
	void insert(iterator position, const Tp& x)
	{ ListNodeBase::link(position.base(), new ListNode<Tp>(x)); }
	void push_front(const Tp& x)
	{ insert(begin(), x); }
	void push_back(const Tp& x)
	{ insert(end(), x); }

	// @todo build pop front/back from erase.	
	iterator erase(iterator position);
	iterator erase(iterator first, iterator last);
	
	void clear()
	{ erase(begin(), end()); }
	void swap(List& other)
	{ ListNodeBase::swap(&m_head, &other.m_head); }

	// size is O(n), but it's supposed to be O(1) since C++11.
	std::size_t size() const
	{ return static_cast<std::size_t>(std::distance(begin(), end())); }
	bool empty() const
	{ return begin() == end(); }
private:
	// we can get away with this as long as we don't violate the
	// logical-constness. better - implement const_iterator type.
	iterator begin() const
	{ return iterator(const_cast<ListNodeBase*>(m_head.next)); }
	iterator end() const
	{ return iterator(const_cast<ListNodeBase*>(&m_head)); }
	
	// this is POD type; list initialization cannot fail.
	ListNodeBase m_head;
};

template<typename Tp>
typename List<Tp>::iterator List<Tp>::erase(iterator position)
{
	ListNode<Tp>* current = position.base();
	ListNodeBase* next = ListNodeBase::unlink(current);
	delete current;
	return iterator(next);
}

template<typename Tp>
typename List<Tp>::iterator List<Tp>::erase(iterator first, iterator last)
{
	while ( first != last )
		first = erase(first);
	return first;
}

// Testing
#include <chrono>
#include <iostream>
#include <cassert>

int main(int argc, char* argv[])
{
	int size; std::cin >> size;
	List<int> list, temp;
	
	using clock = std::chrono::high_resolution_clock;
	clock::time_point start;
	std::chrono::duration<double> elapsed;
	
	// insert.
	std::cout << "Test insert .. " << std::flush;
	start = clock::now();
	for ( int i = 0; i < size; i++ )
		list.push_back(i);
	elapsed = clock::now() - start;
	assert(list.size() == size);
	{
		int value = 0;
		for ( auto i = list.begin(); i != list.end(); i++, value++ )
			assert(*i == value);
	}
	std::cout << "Okay. Elapsed: " << elapsed.count() << std::endl;
	
	// copy.
	std::cout << "Test copy .. " << std::flush;
	start = clock::now();
	temp = list;
	elapsed = clock::now() - start;
	assert(list.size() == size);
	assert(temp.size() == size);
	assert(std::equal(list.begin(), list.end(), temp.begin()));
	std::cout << "Okay. Elapsed: " << elapsed.count() << std::endl;
	
	// clear/erase.
	std::cout << "Test erase .. " << std::flush;
	start = clock::now();
	list.clear();
	elapsed = clock::now() - start;
	assert(list.empty());
	assert(temp.size() == size);
	std::cout << "Okay. Elapsed: " << elapsed.count() << std::endl;
	
	std::cout << "Test move .. " << std::flush;
	start = clock::now();
	list = std::move(temp);
	elapsed = clock::now() - start;
	assert(list.size() == size);
	assert(temp.empty());
	std::cout << "Okay. Elapsed: " << elapsed.count() << std::endl;
	list.clear();
	
	// generate some output (?).
	size = 10;
	for ( int i = 0; i < size; i++ )
		list.push_back(i);
	auto mid = list.begin() + size/2;
	std::cout << "\n1st: ";
	for ( auto i = list.begin(); i != mid; ++i )
		std::cout << *i << ' ';
	std::cout << "\n2nd: ";
	for ( auto i = mid; i != list.end(); ++i )
		std::cout << *i << ' ';
	std::cout << "\nall: ";
	for ( auto v : list )
		std::cout << v << ' ';
	std::cout << "\nall rotated(" << size/2 << "): ";
	std::rotate(list.begin(), mid, list.end());
	for ( auto v : list )
		std::cout << v << ' ';
	std::cout << std::endl;
	return 0;
}