/*
  Simple unidirectional list class.
  Copyright (c) 2003, Jesper Öqvist

  [comments]
  You may use this code for any purpose, provided that you maintain
  this copyright notice.

  [created] 2003-02-28
  [updated] 2003-03-24
*/

#ifndef _jsh_list_h
#define _jsh_list_h

namespace jsh{

template <class _t>
class list
{
	struct _node
	{
		_t _value;
		_node* _next;

		_node() {}
		_node(const _node& _a) {*this = _a;}
		_node& operator=(const _node& _a) {_value = _a._value;_next = _a._next;}
		~_node() {}
	};
	_node* _front;
	_node* _back;
	unsigned int _size;

public:
	list<_t>(): _front(NULL), _back(NULL), _size(0) {}
	list<_t>(const list<_t>& _a): _front(NULL), _back(NULL), _size(0) {*this = _a;}
	list<_t>& operator=(const list<_t>& _a){
		clear();
		_node* _tmp = _a._front;
		while (true){
			if (_tmp == NULL) return *this;
			push_back(_tmp->_value);
			_tmp = _tmp->_next;}}
	~list<_t>() {clear();}

	class iterator
	{
		friend class list<_t>;
	protected:
		mutable _node* _pointer;

		const iterator& operator--() const {/*NOT a bidirectional iterator*/}
		const iterator operator--(int) const {/*NOT a bidirectional iterator*/}
		iterator& operator--() {/*NOT a bidirectional iterator*/}
		iterator operator--(int) {/*NOT a bidirectional iterator*/}

	public:
		iterator(): _pointer(NULL) {}
		iterator(const iterator& _a) {*this = _a;}
		iterator(_node*const& _a): _pointer(_a) {}
		~iterator() {}

		const iterator& operator=(const iterator& _a) const {_pointer = _a._pointer;return *this;}
		const iterator& operator=(const _node*const& _a) const {_pointer = _a;return *this;}
		const iterator& operator=(_node*& _a) {_pointer = _a;return *this;}

		const _t& operator*() const {return _pointer->_value;}
		const _t* operator->() const {return &_pointer->_value;}
		_t& operator*() {return _pointer->_value;}
		_t* operator->() {return &_pointer->_value;}
		const iterator& operator++() const {_pointer = _pointer->_next;return *this;}
		const iterator operator++(int) const {iterator _tmp(*this);++(*this);return _tmp;}
		iterator& operator++() {_pointer = _pointer->_next;return *this;}
		iterator operator++(int) {iterator _tmp(*this);++(*this);return _tmp;}
		bool operator==(const iterator& _a) const {return (_pointer == _a._pointer);}
		bool operator!=(const iterator& _a) const {return (_pointer != _a._pointer);}
		bool operator==(const _node*const& _a) const {return (_pointer == _a);}
		bool operator!=(const _node*const& _a) const {return (_pointer != _a);}
		friend bool operator==(const _node*const& _a, const iterator& _b) {return (_a == _b._pointer);}
		friend bool operator!=(const _node*const& _a, const iterator& _b) {return (_a != _b._pointer);}
	};

	void push_front(const _t& _a);//put value at front
	void push_back(const _t& _a);//put value at back
	void pop_front();//remove front element
	const iterator begin() const {return iterator(_front);}//constant iterator
	iterator begin() {return iterator(_front);}//non-constant iterator
	const _t& front() const {return _front->_value;}//consant reference
	_t& front() {return _front->_value;}//non-constant reference
	const iterator end() const {return iterator(_back);}//constant iterator
	iterator end() {return iterator(_back);}//non-constant iterator
	const _t& back() const {return _back->_value;}//constant reference
	_t& back() {return _back->_value;}//non-constant reference
	unsigned int size() const {return _size;}//size of list
	bool empty() const {return (!_size);}//is list empty?
	void clear() {while (!empty()) pop_front();}//erase all the contents of the list
	void remove(const _t& _a);//remove all elements with values equal to argument
	void erase(iterator& _a);//erases iterator from list
	void insert(iterator& _a, const _t& _b);//insert _b in front of _a
	void insert_after(iterator& _a, const _t& _b);//insert _b after _a
	void swap(list<_t>& _a){//swaps this list with argument
		_node* _tmp;_tmp = _front;_front = _a._front;_a._front = _tmp;
		_tmp = _back;_back = _a._back;_a._back = _tmp;
		unsigned int _tmp2 = _size;_size = _a._size;_a._size = _tmp2;}
	void reverse(){//reverses order of elements
		list<_t> _new;
		while (!empty()){
			_new.push_front(front());
			pop_front();}
		swap(_new);}
};

template <class _t>
void list<_t>::push_front(const _t& _a)
{
	if (!empty())
	{
		_node* _new = new _node;
		_new->_next = _front;
		_front = _new;
	}
	else
	{
		_front = new _node;
		_front->_next = NULL;
		_back = _front;
	}
	_front->_value = _a;
	_size++;
}

template <class _t>
void list<_t>::push_back(const _t& _a)
{
	if (!empty())
	{
		_back->_next = new _node;
		_back = _back->_next;
	}
	else
	{
		_front = new _node;
		_back = _front;
	}
	_back->_value = _a;
	_back->_next = NULL;
	_size++;
}

template <class _t>
void list<_t>::pop_front()
{
	if (empty()) return;
	if (_front == _back)
	{
		delete _front;
		_front = _back = NULL;
	}
	else
	{
		_node* _tmp = _front->_next;
		delete _front;
		_front = _tmp;
	}
	_size--;
}

template <class _t>
void list<_t>::remove(const _t& _a)
{
	_node* _tmp = _front;
	_node* _tmp2 = _tmp;
	while (true)
	{
		if (_tmp == NULL) return;
		if (_tmp->_value == _a)
		{
			if (_tmp == _front)
			{
				pop_front();
				if (empty()) return;
				_tmp = _tmp2 = _front;
				_tmp = _tmp->_next;
			}
			else
			{
				_tmp2->_next = _tmp->_next;
				if (_tmp == _back) _back = _tmp2;
				delete _tmp;
				_tmp = _tmp2->_next;
				_size--;
			}
			continue;
		}
		_tmp2 = _tmp;
		_tmp = _tmp->_next;
	}
}

template <class _t>
void list<_t>::erase(iterator& _a)
{
	_node* _tmp = _front;
	_node* _tmp2 = _tmp;
	while (true)
	{
		if (_tmp == NULL) return;
		if (_tmp == _a)
		{
			if (_tmp == _front)
			{
				pop_front();
				_a = _front;
			}
			else
			{
				_tmp2->_next = _tmp->_next;
				if (_tmp == _back) _back = _tmp2;
				delete _tmp;
				_a = _tmp2->_next;
				_size--;
			}
			return;
		}
		_tmp2 = _tmp;
		_tmp = _tmp->_next;
	}
}

template <class _t>
void list<_t>::insert(iterator& _a, const _t& _b)
{
	_node* _tmp = _front;
	_node* _tmp2 = _tmp;
	while (true)
	{
		if (_tmp == NULL) return;
		if (_tmp == _a)
		{
			if (_tmp == _front)
				push_front(_b);
			else
			{
				_tmp2->_next = new _node;
				_tmp2 = _tmp2->_next;
				_tmp2->_next = _tmp;
				_tmp2->_value = _b;
				_size++;
			}
			return;
		}
		_tmp2 = _tmp;
		_tmp = _tmp->_next;
	}
}

template <class _t>
void list<_t>::insert_after(iterator& _a, const _t& _b)
{
	_node* _tmp = _front;
	while (true)
	{
		if (_tmp == NULL) return;
		if (_tmp == _a)
		{
			if (_tmp == _back)
				push_back(_b);
			else
			{
				_node* _tmp2 = _tmp->_next;
				_tmp->_next = new _node;
				_tmp = _tmp->_next;
				_tmp->_next = _tmp2;
				_tmp->_value = _b;
				_size++;
			}
			return;
		}
		_tmp = _tmp->_next;
	}
}

};

#endif _jsh_list_h