/**
*    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;
			}
		};

		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&);
		//void insert(iterator position, InputIterator first, InputIterator last);
		//iterator erase(iterator position);
		//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(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>
	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>
	void list<T>::clear()
	{
		node* n;
		while(_front)
		{
			n = _front->next;
			delete _front;
			_front = n;
			--_size;
		}
		_front = _back = NULL;
	}
}
#endif
#include <iostream>
#include<list>
int main()
{
    std::list<int> l;
	sv::list<int> l2;
	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;
	if(!lst2.empty())
		std::cout<<"front= " << lst2.front()<<" back= "<<lst2.back()<<" size= "<<lst2.size()<<std::endl;
	}
	L::iterator it;
	for(it=lst.begin(); it != lst.end(); ++it)
		std::cout<<*it<<std::endl;
	//reverse iterator
	L::reverse_iterator rit;
	std::cout<<"reverse"<<std::endl;
	for(rit=lst.rbegin(); rit != lst.rend(); ++rit)
		std::cout<<*rit<<std::endl;
	//std::cout<<l.max_size()<<std::endl;
	//std::cout<<lst.max_size()<<std::endl;
}