MZ List Implementation in C/C++   Leave a comment

#ifndef __MZ_LIST_h__
#define __MZ_LIST_h__

#include <iterator>
#include <algorithm>
#include <memory>

#include <stdexcept> //out_of_range exception

using namespace std;

//Double-Linked List Implementation
namespace marzan
{
template
class dlinked_list
{

public:
	template
	class list_item
	{
		_Ty datum;
		list_item<_Ty>* prev;
		list_item<_Ty>* next;

		list_item(const _Ty& _datum, list_item<_Ty>* _prev, list_item<_Ty>* _next) 
			: datum(_datum),
				prev(_prev),
				next(_next){}
	public:
		list_item<_Ty>* prev_item() const { return prev;}
		list_item<_Ty>* next_item() const { return next;}
		_Ty& data(){
			return datum;
		}
		const _Ty& data() const {
			return datum;
		}

		friend class dlinked_list<_Ty>;
	};

	typedef _Ty value_type;
	typedef size_t size_type;
private:
	list_item<_Ty>* head;
	list_item<_Ty>* tail;
public:
	dlinked_list() : head(0), tail(0) {}

	~dlinked_list(){purge();}
	//cpy ctor
	dlinked_list(const dlinked_list<_Ty>& dl){
		_copy_from(dl);
	}
	//assignment op=
	dlinked_list& operator=(const dlinked_list<_Ty>& dl){
		if(&dl!=this){
			purge();
			_copy_from(dl);
		}
		return *this;
	}
	void purge(){		
		list_item<_Ty>* ptr = head;
		while(ptr!=0){ //O(n)
			head = head->next;
			delete ptr;
			ptr = head;
		}
		head = tail = 0;//important!
	}
	void _copy_from(const dlinked_list<_Ty>& dl){		
		list_item<_Ty>* ptr = const_cast<list_item<_Ty>*>(dl.head);
		for(;ptr!=0;ptr = ptr->next) //O(n)
			append(ptr->datum);
	}
	list_item<_Ty>* front() const{
		return head;
	}
	list_item<_Ty>* back() const{
		return tail;
	}

	const value_type& frontd() const{
		if(head==0)
			throw domain_error("the list is empty!");
		return head->datum;
	}
	value_type& frontd(){
		if(head==0)
			throw domain_error("the list is empty!");
		return head->datum;
	}

	const value_type& backd() const{
		if(tail==0)
			throw domain_error("the list is empty!");
		return tail->datum;
	}
	value_type& backd(){
		if(tail==0)
			throw domain_error("the list is empty!");
		return tail->datum;
	}

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

	void push_front(const value_type& datum){
		//add a new head...
		list_item<_Ty>* head_new = new list_item<_Ty>(datum, 0, head);
		if(empty())			
			tail = head_new;
		else
			head->prev = head_new;
		//set the new head
		head = head_new;		
	}
	void push_back(const value_type& datum){
		list_item<_Ty>* tail_new = new list_item<_Ty>(datum, tail, 0);
		if(empty())
			head = tail_new;			
		else
			tail->next = tail_new;			
		//set the new tail
		tail = tail_new;		
	}
	list_item<_Ty>* insert_before(list_item<_Ty>* ref, const value_type& datum)
	{
		if(empty() || ref==0)
			throw invalid_argument("invalid item reference for insertion.");

		list_item<_Ty>* item_new = new list_item<_Ty>(datum, ref->prev, ref);
		ref->prev = item_new;
		if(ref==head)
			head = item_new;
		return item_new;
	}

	list_item<_Ty>* insert_after(list_item<_Ty>* ref, const value_type& datum){
		if(empty() || ref==0)
			throw invalid_argument("invalid item reference for insertion.");

		list_item<_Ty>* item_new = new list_item<_Ty>(datum, ref, ref->next);
		if(ref==tail)
			tail = item_new;
		return item_new;
	}

	void erase(list_item<_Ty>* item)
	{
		list_item<_Ty>* prev = item->prev;
		list_item<_Ty>* next = item->next;

		if(item==tail){
			tail = prev;
			tail->next = 0;
		}
		else if(item==head){
			head = next;
			head->prev = 0;
		}else{
			if(prev)
				prev->next = next;
			if(next)
				next->prev = prev;
		}
		delete item;

	}
	void erase(const value_type& datum)
	{
		list_item<_Ty>* ptr = head;
		while(ptr!=0 && ptr->datum!=datum)
			ptr = ptr->next;

		if(ptr!=0)
			erase(ptr);
		else
			throw invalid_argument("item was not found in list.");
	}
};

template >
	class list
{
	dlinked_list<_Ty> _list;
	bool _sorted;
public:
	typedef _Ty value_type;
	typedef typename _Ay alloc_type;

	typedef typename _Ay::pointer pointer;
	typedef typename _Ay::const_pointer const_pointer;
	typedef typename _Ay::reference reference;
	typedef typename _Ay::const_reference const_reference;
public:
	list() : _list(), _sorted(false) {}
	list(bool sorted) : _list(), _sorted(sorted) {}
	~list(){}

	class iterator;
	friend class iterator;	
	class iterator : public std::iterator<bidirectional_iterator_tag, _Ty>
	{
		list<_Ty>* plist;
		typename dlinked_list<_Ty>::list_item<_Ty>* pitem;

		friend class list<_Ty>;
	public:
		iterator(list<_Ty>* list_ptr, typename dlinked_list<_Ty>::list_item<_Ty>* item_ptr) 		
			:	plist(list_ptr),
				pitem(item_ptr){}		
		iterator(const iterator& oi){
			plist = oi.plist;
			pitem = oi.pitem;
		}
		iterator& operator=(const iterator& oi){
			if(this!=&oi){
				plist = oi.plist;
				pitem = oi.pitem;
			}
			return *this;
		}
		//
		_Ty& operator*(){
			  if(pitem==0)
				  throw domain_error("invalid pointer!");
			  return pitem->data();
		}
		iterator& operator++(){
			  if(pitem==0)
				  throw logical_error("invalid pointer!");
			  pitem = pitem->next_item();
			  return *this;
		}
		iterator operator++(int){
			  if(pitem==0)
				  throw domain_error("invalid pointer!");			  
			  iterator tmp(plist, pitem);
			  pitem = pitem->next_item();
			  return tmp;
		}

		iterator& operator--(){
			  if(pitem==0)
				  throw domain_error("invalid pointer!");
			  pitem = pitem->prev_item();
			  return *this;
		}
		iterator operator--(int){
			  if(pitem==0)
				  throw logical_error("invalid pointer!");
			  iterator tmp(plist, pitem);			  
			  pitem = pitem->prev_item();
			  return tmp;
		}

		bool operator==(const iterator& oi){
			return (plist==oi.plist && pitem==oi.pitem);
		}
		bool operator!=(const iterator& oi){
			return !(*this==oi);
		}
	};

	iterator begin(){
		return iterator(this, _list.front());
	}
	iterator end(){
		return iterator(this, 0);
	}

	void push_front(const _Ty& _X){
		_list.push_front(_X);
	}
	void push_back(const _Ty& _X){
		_list.push_back(_X);
	}
	const_reference back() const{
		return _list.backd();
	}
	reference back(){
		return _list.backd();
	}
	const_reference front() const{
		return _list.frontd();
	}
	reference front(){
		return _list.frontd();
	}
	bool empty() const{
		return _list.empty();
	}

	void erase(const _Ty& _X)
	{
		_list.erase(_X);
	}

	void erase(const iterator& ref)
	{
		_list.erase(const_cast<dlinked_list<_Ty>::list_item<_Ty>*>(ref.pitem));
	}

	iterator insert(const iterator& ref, const _Ty& _X)
	{
		dlinked_list<_Ty>::list_item<_Ty>* item_new;
		item_new = _list.insert_before(const_cast<dlinked_list<_Ty>::list_item<_Ty>*>(ref.pitem), _X);
		return iterator(this, item_new);
	}
	iterator insert(const _Ty& _X)
	{
		if(_sorted)
		{
			if(_list.back()!=0 && _list.back()->data() < _X) //O(1)
			{
				_list.push_back(_X);
				return iterator(this, _list.back());
			}
			dlinked_list<_Ty>::list_item<_Ty>* ref = _list.front();
			//find the less thatn _X...
			while(ref!=0 && ref->data() < _X) //O(n) 				ref = ref->next_item();
			if(!ref){
				//insert before...
				push_front(_X);
				return iterator(this, _list.front());
			}
			else
				return insert(ref, _X); //O(1)
		}else{
			push_back(_X);	//O(1)
			return iterator(this, _list.back());
		}
	}
	iterator append(const iterator& ref, const _Ty& _X)
	{
		dlinked_list<_Ty>::list_item<_Ty>* item_new;
		item_new = _list.insert_after(const_cast<dlinked_list<_Ty>::list_item<_Ty>*>(ref.pitem), _X);
		return iterator(this, item_new);
	}
	void append(const _Ty& _X){
		_list.push_back(_X);
	}

	iterator find(const _Ty& _V)
	{
		iterator it = begin();
		while(it!=end()){
			if(*it==_V)
				return it;
			it++;
		}
		return end();
	}
};

}
#endif //__MZ_LIST_h__

Posted February 2, 2013 by hmarzan

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: