/*  Copyright (c) 2003-2006, Jesper Öqvist  [comments]  Simple unidirectional list class.  [license]  See license.txt  [created] 2003-02-28  [updated] 2004-07-10    added jsh::list::iterator::null_pointer  [updated] 2004-07-30    added jsh::list::find_first  [updated] 2005-12-02  	changed empty() to is_empty()  [updated] 2005-12-06  	added pop_back()*/#ifndef jshList_h#define jshList_h#include <jsh_base.h>#pragma warning(disable: 4284)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;	ulong _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);}		//is the iterator pointing at nothing?		bool null_pointer() const {return (_pointer == NULL) ? true : false;}	};	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	void pop_back();//remove last 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	ulong size() const {return _size;}//size of list	ulong length() const {return _size;}//size of list	bool is_empty() const {return (!_size);}//is list empty?	void clear() {while (!is_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;		ulong _tmp2 = _size;_size = _a._size;_a._size = _tmp2;}	void reverse(){//reverses order of elements		list<_t> _new;		while (!is_empty()){			_new.push_front(front());			pop_front();}		swap(_new);}	iterator find_first(const _t& _a){//finds first element matching argument		iterator _it = begin();		while (!_it.null_pointer()){			if (*_it == _a) return _it;			_it++;		}		return iterator(NULL);	}};template <class _t>void list<_t>::push_front(const _t& _a){	if (!is_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 (!is_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 (is_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>::pop_back(){	if (is_empty()) return;	if (size() == 1)	{		clear();		return;	}	_node* _tmp = _front;	while (_tmp->_next != _back)	{		_tmp = _tmp->_next;	}	delete _back;	_back = _tmp;	_back->_next = NULL;}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 (is_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;	}}};#pragma warning(default: 4284)#endif//jshList_h