//DCirList.h
#pragma once

#include "DLNode.h"

template <class T>
class DCirList
{
private:
	DLNode<T> * head;
	DLNode<T> * currPtr;
	int size;

public:
	DCirList(void);
	~DCirList(void)
	{ 
		ClearList();
	}

	int ListSize(void)const;
	int ListEmpty(void)const;
	DLNode<T> * Index(int pos);
	void Insert(const T&item,int pos);
	T Delete (int pos);
	T & GetData(int pos);
	void ClearList(void);

	DLNode<T> * NextRest(int pos=0);
	DLNode<T> * Next(void);
	int NextEndOfList(void)const;
};

template <class T>
DCirList<T>::DCirList()
{
	head = new DLNode<T>();
	head -> next = head;
	head -> prior = head;
	size = 0;
}

template <class T>
void DCirList<T>::Insert(const T & item,int pos)
{
	DLNode<T> * p = Index(pos);

	DLNode<T> * newNode = new DLNode<T>(item,NULL,NULL);

	newNode->prior = p->prior;
	newNode->next = p;
	p->prior->next = newNode;
	p->prior = newNode;
	size ++;
}

template <class T>
T DCirList<T>::Delete(int pos)
{
	if(pos<0 || pos>size)
	{
		cout<<"pos error!"<<endl;
		exit(0);
	}

	DLNode<T> * p = Index(pos);
	p->prior->next = p->next;
	p->next->prior = p->prior;

	T data = p->data;
	delete p;
	size --;
	return data;
}

template <class T>
int DCirList<T>::ListSize()const
{
	return size;
}

template <class T>
DLNode<T> * DCirList<T>::Index(int pos)
{
	if(pos < -1 || pos > size)
	{
		cout<<"pos error!"<<endl;
		exit(0);
	}

	if(pos == -1)
		return head;
	DLNode<T> * p = head->next;

	int i=0;
	while(p != head && i<pos)
	{
		p = p->next;
		i++;
	}
	return p;
}

template <class T>
int DCirList<T>::ListEmpty(void)const
{
	return (size==0);
}

template <class T>
T & DCirList<T>::GetData(int pos)
{
	if(pos<-1 || pos > size)
	{
		cout<<"pos error!"<<endl;
		exit(0);
	}
	DLNode<T> * p = Index(pos);
	return p->data;
}

template <class T>
void DCirList<T>::ClearList(void)
{
	DLNode<T> *p,*p1;

	p = head->next;
	while(p!=head)
	{
		p1 = p;
		p = p->next;
		delete p1;
	}
	size = 0;
}