Subversion Repositories spk

/****************************************

 *

 * List class - last modified 3.5. 2005

 *

 ****************************************/

#ifndef EXT_LIST_INCLUDED

#define EXT_LIST_INCLUDED

namespace ext

{

template <class T> class list

{

	public:

		typedef T value_type;

		typedef size_t size_type;

		typedef T& reference;

		typedef const T& const_reference;

	private:

		class node

		{

			public:

				node *prev, *next;

				value_type val;

		};

	public:

		class const_iterator

		{

			private:

				node *_mynode;

			public:

				node* mynode() const { return _mynode; }	

				const_iterator() { _mynode=0; }

				const_iterator(node* n) { _mynode=n; }

				const_reference operator *() const { return _mynode->val; }

				const_reference operator ->() const { return _mynode->val; }

				bool operator ==(const const_iterator &right) const { return _mynode==right.mynode(); }

				bool operator !=(const const_iterator &right) const { return _mynode!=right.mynode(); }

				const_iterator operator++(int) { _mynode=_mynode->next; return const_iterator(_mynode->prev); }

				const_iterator& operator++() { _mynode=_mynode->next; return *this; }

				const_iterator operator--(int) { _mynode=_mynode->prev; return const_iterator(_mynode->next); }

				const_iterator& operator--() { _mynode=_mynode->prev; return *this; }

				const_iterator operator+(int offset) 

				{ 

					const_iterator it(mynode());

					for(int i=0; i < offset; ++i, ++it)

						;

					return it;

				}

				const_iterator operator-(int offset) 

				{ 

					const_iterator it(mynode());

					for(int i=offset; i > 0; --i, --it)

						;

					return it;

				}

		};

		class iterator : public const_iterator 

		{

			public:				

				iterator() { }

				iterator(node* n) : const_iterator(n) { }

				reference operator *() { return mynode()->val; }

				reference operator ->() { return mynode()->val; }

				bool operator ==(const iterator &right) const { return mynode()==right.mynode(); }

				bool operator !=(const iterator &right) const { return mynode()!=right.mynode(); }

				iterator operator++(int) { iterator tmp=*this; ++*this; return tmp; }

				iterator& operator++() { ++(*(const_iterator*)this); return *this; }

				iterator operator--(int) { iterator tmp=*this; --*this; return tmp; }

				iterator& operator--() { --(*(const_iterator*)this); return *this; }

				iterator operator+(int offset) 

				{ 

					iterator it(mynode());

					for(int i=0; i < offset; ++i, ++it);

					return it;

				}

				iterator operator-(int offset) 

				{ 

					iterator it(mynode());

					for(int i=offset; i > 0; --i, --it)

						;

					return it;

				}

		};

		class const_reverse_iterator

		{

			private:

				node *_mynode;

			public:

				node* mynode() const { return _mynode; }	

				const_reverse_iterator() { _mynode=0; }

				const_reverse_iterator(node* n) { _mynode=n; }

				const_reference operator *() const { return _mynode->val; }

				const_reference operator ->() const { return _mynode->val; }

				bool operator ==(const const_reverse_iterator &right) const { return _mynode==right.mynode(); }

				bool operator !=(const const_reverse_iterator &right) const { return _mynode!=right.mynode(); }

				const_reverse_iterator operator++(int) { _mynode=_mynode->prev; return const_reverse_iterator(_mynode->next); }

				const_reverse_iterator& operator++() { _mynode=_mynode->prev; return *this; }

				const_reverse_iterator operator--(int) { _mynode=_mynode->next; return const_reverse_iterator(_mynode->prev); }

				const_reverse_iterator& operator--() { _mynode=_mynode->next; return *this; }

				const_reverse_iterator operator+(int offset) 

				{ 

					const_reverse_iterator it(mynode());

					for(int i=0; i < offset; ++i, ++it)

						;;

					return it;

				}

				const_reverse_iterator operator-(int offset) 

				{ 

					const_reverse_iterator it(mynode());

					for(int i=offset; i > 0; --i, --it)

						;;

					return it;

				}

		};

		class reverse_iterator : public const_reverse_iterator 

		{

			public:				

				reverse_iterator() { }

				reverse_iterator(node* n) : const_reverse_iterator(n) { }

				reference operator *() { return mynode()->val; }

				reference operator ->() { return mynode()->val; }

				bool operator ==(const reverse_iterator &right) const { return mynode()==right.mynode(); }

				bool operator !=(const reverse_iterator &right) const { return mynode()!=right.mynode(); }

				reverse_iterator operator++(int) { reverse_iterator tmp=*this; ++*this; return tmp; }

				reverse_iterator& operator++() { ++(*(const_reverse_iterator*)this); return *this; }

				reverse_iterator operator--(int) { reverse_iterator tmp=*this; --*this; return tmp; }

				reverse_iterator& operator--() { --(*(const_reverse_iterator*)this); return *this; }

				reverse_iterator operator+(int offset) 

				{ 

					reverse_iterator it(mynode());

					for(int i=0; i < offset; ++i, ++it)

						;;

					return it;

				}

				iterator operator-(int offset) 

				{ 

					reverse_iterator it(mynode());

					for(int i=offset; i > 0; --i, --it)

						;;

					return it;

				}

		};

	private:

		node *myhead;

		size_type count;

		static node* nextnode(node *n) { return n->next; }

		static node* prevnode(node *n) { return n->prev; }

		static reference nodeval(node *n) { return n->val; }

		void _insert(iterator& where, value_type val)

		{

			node *newnode=new node(), *nodeptr=where.mynode();

			newnode->prev=nodeptr->prev;

			newnode->next=nodeptr;

			newnode->prev->next=newnode;

			nodeptr->prev=newnode;

			newnode->val=val;

			count++;

		}

	public:

		list() 

		{ 

			myhead=new node();

			myhead->next=myhead;

			myhead->prev=myhead;

			count=0;

		}

		list(const list& other)

		{ 

			myhead=new node();

			myhead->next=myhead;

			myhead->prev=myhead;

			count=0;

			insert(end(), other.begin(), other.end());

		}

		~list()

		{

			clear();

			delete myhead;

		}

		void clear()

		{

			node *n, *d;

			n=d=nextnode(myhead);

			for( ; n!=myhead; d=n){

				n=nextnode(n);

				delete d;

			}

			myhead->next=myhead;

			myhead->prev=myhead;

			count=0;

		}

		size_type size() const { return count; }

		iterator begin() { return iterator(nextnode(myhead)); }

		iterator end() { return iterator(myhead); }

		const_iterator begin() const { return iterator(nextnode(myhead)); }

		const_iterator end() const { return iterator(myhead); }

		reverse_iterator rbegin() { return reverse_iterator(prevnode(myhead)); }

		reverse_iterator rend() { return reverse_iterator(myhead); }

		const_reverse_iterator rbegin() const { return reverse_iterator(prevnode(myhead)); }

		const_reverse_iterator rend() const { return reverse_iterator(myhead); }

		iterator insert(iterator where, const_reference val)

		{

			_insert(where, val);

			return --where;

		}

		void insert(iterator where, const_iterator first, const_iterator last)

		{

			for(; first!=last; ++first){

				_insert(where, *first);

			}

		}

		iterator erase(iterator& where)

		{

			node *delnode=(where++).mynode();

			if(delnode!=myhead){

				delnode->prev->next=delnode->next;

				delnode->next->prev=delnode->prev;

				delete delnode;

				count--;

			}

			return where;

		}

		iterator erase(iterator& first, iterator& last)

		{

			if(first==begin() && last==end())

				clear();

			else{

				while(first!=last)

					first=erase(first);

			}

			return last;

		}

		iterator push_front(const_reference val)

		{

			_insert(begin(), val);

			return begin();

		}

		iterator push_back(const_reference val)

		{

			_insert(end(), val);

			return --end();

		}

		bool empty() const { return size()==0; }

		void pop_front() { erase(begin()); }

		void pop_back() { erase(--end()); }

		const_reference front() const { return nodeval(myhead); }

		reference front() { return nodeval(myhead->next); }

		const_reference back() const { return nodeval(myhead->prev); }

		reference back() { return nodeval(myhead->prev); }

		iterator find(const_reference val)

		{

			for(iterator &it=begin(); it!=end(); ++it){

				if(*it==val)

					break;

			}

			return it;

		}

		void remove(const_reference val)

		{

			iterator old;

			for(iterator &it=begin(); it!=end(); ++it){

				if(*it==val){

					old=it - 1;

					_erase(it);

					it=old;

				}

			}

		}

};

}	// namespace ext

#endif // !defined(EXT_LIST_DEFINED)