/**
*    Sean Vogel
*	11 -28 -2012
*	Just a linked list
*/
#ifndef SV_LINK_LIST
#define SV_LINK_LIST
#ifndef NULL
	#define NULL 0
#endif
#include <limits>

namespace sv
{
	template <class T>
	class list
	{
		class node
		{	
		public:
			node *prev,
				*next;

			T data;

			node() : prev(NULL), next(NULL), data(NULL){}
			node(const T& t) : prev(NULL), next(NULL), data(t){}
		};

		node *_front,
			*_back;
		unsigned int _size;

	public:
		class iterator
		{
			node* _node;
		public:
			iterator() : _node(NULL){}
			iterator(node* n) : _node(n){}
			iterator(const iterator& it) : _node(it._node){}
			T& operator*(){ if(_node)return _node->data; }
			T* operator->(){ if(_node)return &_node->data; }
			iterator& operator++()
			{
				if(_node)
				{
					_node = _node->next;
				}
				return *this;
			}
			iterator operator++(int)
			{
				iterator it(*this);
				++(*this);
				return it;
			}
			iterator& operator--()
			{
				if(_node)
				{
					_node = _node->prev;
				}
				return *this;
			}
			iterator& operator--(int)
			{
				iterator it(*this);
				--(*this);
				return it;
			}
			bool operator!=(const iterator& it) const { return (this->_node != it._node); }

			iterator& operator=(const iterator& it)
			{
				_node = it._node;
				return *this;
			}
			node* nodeptr(){return _node;}
		};

		template <class U = iterator>
		class _reverse_iterator 
		{
			node* _node;
		public:
			_reverse_iterator() : _node(NULL){}
			_reverse_iterator(node* n) : _node(n){}
			_reverse_iterator(const _reverse_iterator& it) : _node(it._node){}
			T& operator*(){ if(_node)return _node->data; }
			T* operator->(){ if(_node)return &_node->data; }
			_reverse_iterator& operator++()
			{
				if(_node)
				{
					_node = _node->prev;
				}
				return *this;
			}
			_reverse_iterator operator++(int)
			{
				iterator it(*this);
				--(*this);
				return it;
			}
			_reverse_iterator& operator--()
			{
				if(_node)
				{
					_node = _node->next;
				}
				return *this;
			}
			_reverse_iterator& operator--(int)
			{
				_reverse_iterator it(*this);
				--(*this);
				return it;
			}
			bool operator!=(const _reverse_iterator& it) const { return (this->_node != it._node); }

			_reverse_iterator& operator=(const _reverse_iterator& it)
			{
				_node = it._node;
				return *this;
			}
		}; typedef _reverse_iterator<> reverse_iterator;

		//constructors
		list() : _front(NULL), _back(NULL), _size(NULL){}
		list(unsigned int , const T& t = T());
		list(const list<T>&);
		template < class InputIterator >
        list(InputIterator first, InputIterator last);
		~list();

		//iterators
		iterator begin();
		iterator end();
		reverse_iterator rbegin();
		reverse_iterator rend();

		//operators
		list<T>& operator=(const list<T>&);

		//element access
		T& front();
		T& back();

		//capacity
		bool empty() const;
		unsigned int size() const;
		unsigned int max_size() const;
		void resize(unsigned int, const T& t = T());

		//modifiers
		void push_front(const T&);
		void pop_front();
		void push_back(const T&);
		void pop_back();
		iterator insert(iterator pos, const T&);
		void insert(iterator pos, unsigned int size, const T&);
		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last);
		iterator erase(iterator pos);
		iterator erase(iterator first, iterator last);
		//void swap(list<T>& lst);
		void clear();
		//void assign(size_type n, const T& u);
		//void assign(InputIterator first, InputIterator last);

		//operations
		//void remove(const T& value);
		//template <class Predicate>
		//void remove_if(Predicate pred);
		//void sort(list<T>& lst);
		//void merge(list<T>& lst):
		//void splice(iterator position, list<T,Allocator>& x);
		//void splice(iterator position, list<T,Allocator>& x, iterator i);
		//void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
		//void unique();
		//template <class BinaryPredicate>
		//void unique(BinaryPredicate binary_pred);
		//void reverse();
	};

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

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

	template <class T>
	typename list<T>::reverse_iterator list<T>::rbegin()
	{
		return reverse_iterator(_back);
	}

	template <class T>
	typename list<T>::reverse_iterator list<T>::rend()
	{
		return reverse_iterator(_front->prev);
	}

	template <class T>
	list<T>::list(unsigned int sz, const T& t) : _front(NULL), _back(NULL), _size(NULL)
	{
		while(_size < sz)
			push_back(t);
	}

	template <class T>
	list<T>::list(const list<T>& lst) : _front(NULL), _back(NULL), _size(NULL)
	{
		if(!lst.empty())
		{
			node* n = lst._front;			
			while(n)
			{
				push_back(n->data);
				n = n->next;						
			}
		}
	}

	template <class T>
	template <class InputIterator>
    list<T>::list(InputIterator first, InputIterator last) : _front(NULL), _back(NULL), _size(NULL)
	{
		while(first != last)
		{
			push_back(*first);
			++first;
		}
	}

	template <class T>
	list<T>& list<T>::operator=(const list<T>& lst)
	{
		if(this != &lst && !lst.empty())
		{
			clear();

			node* n = lst._front;			
			while(n)
			{
				push_back(n->data);
				n = n->next;						
			}
		}
		return this;
	}

	template <class T>
	list<T>::~list()
	{
		clear();
	}

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

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

	template <class T>
	unsigned int list<T>::max_size()const {return std::numeric_limits<T>::max();}

	template <class T>
	void list<T>::resize(unsigned int sz, const T& t)
	{
		while(sz > _size)
		{
			push_back(t);
		}
	}

	template <class T>
	T& list<T>::front()
	{
		if(_front)
			return _front->data;
	}

	template <class T>
	T& list<T>::back()
	{
		if(_back)
			return _back->data;
	}

	template <class T>
	void list<T>::push_front(const T& t)
	{			
		node* n = new node(t);

		if(_front)
		{
			n->next = _front;
			_front->prev = n;
			_front = n;
		}
		else
		{
			_back = _front = n;
		}
		++_size;
	}

	template <class T>
	void list<T>::pop_front()
	{
		if(front)
		{
			node* n = _front->next;
			delete _front;
			_front = n;
			--_size;
		}		
	}

	template <class T>
	void list<T>::push_back(const T& t)
	{
		node* n = new node(t);

		if(_back)
		{
			n->prev = _back;
			_back->next = n;
			_back = n;
		}
		else
		{
			_front = _back = n;			
		}
		++_size;
	}

	template <class T>
	void list<T>::pop_back()
	{
		if(back)
		{
			node* n = _back->prev;
			delete _back;
			_back = n;
			--_size;
		}		
	}

	template <class T>
	typename list<T>::iterator list<T>::insert(typename list<T>::iterator pos, const T& t)
	{
		node* n = new node(t);
		node* c = pos.nodeptr();
		n->prev = c->prev;
		n->next = c;
		c->prev->next = n;
		c->prev = n;
		return typename list<T>::iterator(c);
	}

	template <class T>
	void list<T>::insert(typename list<T>::iterator pos, unsigned int size, const T& t)
	{
		unsigned int i = 0;
		while(i < size)
		{
			pos = insert(pos,t);
			++i;
		}
	}

	template <class T>
	template <class InputIterator>
	void list<T>::insert(typename list<T>::iterator pos, InputIterator first, InputIterator last)
	{
		while(first != last)
		{
			T& t = *first;
			pos = insert(pos,t);
			++first;
		}
	}

	template <class T>
	typename list<T>::iterator list<T>::erase(typename list<T>::iterator pos)
	{
		node* c = pos.nodeptr();
		if(c->prev)
			c->prev->next = c->next;
		if(c->next)
			c->next->prev = c->prev;
		pos = c->next;
		delete c;
		return pos;
	}

	template <class T>
	typename list<T>::iterator list<T>::erase(typename list<T>::iterator first, typename list<T>::iterator last)
	{
		while(first != last)
		{
			first = erase(first);
		}
		return first;
	}

	template <class T>
	void list<T>::clear()
	{
		node* n;
		while(_front)
		{
			n = _front->next;
			delete _front;
			_front = n;
			--_size;
		}
		_front = _back = NULL;
	}
}
#endif
#include <iostream>
#include<list>
struct obj
{
    obj():a(0),b(0){}
	int a;
	int b;
};
int main()
{	
	typedef sv::list<int> L;

	L lst;

	for(int i = 0; i < 10; ++i)
		lst.push_front(i + 1);
        
	lst.resize(20, 9333);
    
	if(!lst.empty())
		std::cout<<"front= " << lst.front()<<" back= "<<lst.back()<<" size= "<<lst.size()<<std::endl;
	
		L lst2(lst.begin(), lst.end());
		L lst3 = lst;
        
	if(!lst2.empty())
		std::cout<<"front= " << lst2.front()<<" back= "<<lst2.back()<<" size= "<<lst2.size()<<std::endl;
	
	L::iterator it = lst.begin();
	++it;
	std::cout<<"\nlist1"<<std::endl;
    
	it = lst.erase(it);
	for(it=lst.begin(); it != lst.end(); ++it)
		std::cout<<*it<<" ";
	std::cout<<std::endl;

	std::cout<<"\nlist2"<<std::endl;
	it=lst2.begin();	
	++it;
    
	lst2.insert(it, 7577);
	lst2.insert(it,5u, 999);
	lst2.insert(it,lst.begin(),lst.end());
    
	for(it=lst2.begin(); it != lst2.end(); ++it)
		std::cout<<*it<<" ";
	std::cout<<std::endl;
    
	std::cout<<"\nlist3"<<std::endl;
	it=lst3.begin();	
	++it;
	++it;
	
	L::iterator it2 = lst3.begin();
	// std::advance (it2,6);
    for(int i =0; i<6;++i)
		++it2;
    lst3.erase(it,it2);

	for(it2=lst3.begin(); it2 != lst3.end(); ++it2)
		std::cout<<*it2<<" ";
	std::cout<<std::endl;
	//reverse iterator
	L::reverse_iterator rit;
	
	std::cout<<"\nreverse list1"<<std::endl;
	for(rit=lst.rbegin(); rit != lst.rend(); ++rit)
		std::cout<<*rit<<" ";
    std::cout<<std::endl;
    
	//std::cout<<l.max_size()<<std::endl;
	//std::cout<<lst.max_size()<<std::endl;
}