#ifndef __DLLIST_H__
#define __DLLIST_H__
#define NULL 0



template <typename T>
class CDList {

public:
template <typename T>
struct Node {
Node *next;
Node *prev;
T data;
};

public:
CDList ()
: pHead(NULL), pTail(NULL) {};

CDList (const CDList &dl)
: pHead(NULL), pTail(NULL) {
*this = dl;
}

~CDList () {
clear();
}

typedef const T& const_reference;
typedef const Node<T>* const_pointer;
typedef T& reference;
typedef Node<T>* pointer;

class iterator;
class const_iterator;
friend class const_iterator;
class const_iterator {
public:
const_iterator() : nodePtr(NULL) {}
const_iterator( const iterator &iter )
: nodePtr(iter.nodePtr)
{}
const_iterator( Node<T> *pNode )
: nodePtr(pNode)
{}

const_reference operator *() const {
return nodePtr->data;
}

pointer operator ->() const {
return nodePtr;
}

const_iterator &operator ++() {
if(nodePtr != NULL) {
nodePtr = nodePtr->next;
}
return *this;
}

const_iterator &operator --() {
if(nodePtr != NULL) {
nodePtr = nodePtr->prev;
}
return *this;
}

const_iterator operator ++(int) {
const_iterator temp(*this);
++(*this);
return temp;
}

const_iterator operator --(int) {
const_iterator temp(*this);
--(*this);
return temp;
}

const_iterator &operator =(const_iterator iter) {
nodePtr = iter.nodePtr;
return *this;
}

bool operator ==(const const_iterator iter) const {
return nodePtr == iter.nodePtr;
}

bool operator !=(const const_iterator iter) const {
return nodePtr != iter.nodePtr;
}

Node<T> *getNodePtr() {
return nodePtr;
}

protected:
Node<T> *nodePtr;

};


friend class iterator;
class iterator : public const_iterator {
public:
iterator (): const_iterator(NULL) {}
iterator( Node<T> *pNode )
: const_iterator(pNode)
{}
iterator (const_iterator &iter)
: const_iterator(iter) {}

reference operator *() {
return nodePtr->data;
}

pointer &operator ->() {
return nodePtr;
}

iterator &operator ++() {
if(nodePtr != NULL) {
nodePtr = nodePtr->next;
}
return *this;
}

iterator &operator --() {
if(nodePtr != NULL) {
nodePtr = nodePtr->prev;
}
return *this;
}

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

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

iterator &operator =(iterator iter) {
nodePtr = iter.nodePtr;
return *this;
}

bool operator ==(const iterator iter) const {
return nodePtr == iter.nodePtr;
}

bool operator !=(const iterator iter) const {
return nodePtr != iter.nodePtr;
}
};

const_iterator begin() const {
return const_iterator(pHead);
}

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

iterator begin() {
return iterator(pHead);
}

iterator end() {
return iterator();
}

const_reference front() const {
return pHead->data;
}

const_reference back() const {
return pTail->data;
}

reference front() {
return pHead->data;
}

reference back() {
return pTail->data;
}

void clear() {
erase(begin(), end());
}

// erases all element in the range of "first" and "last"
iterator erase(iterator first, iterator last) {
while(first != last) {
erase(first++);
}
return first;
}

// erase an element pointed by the current iterator
iterator erase(iterator iter) {
if(iter.getNodePtr() != NULL) {
iterator iter2 = iter++;
remove_node(iter2.getNodePtr());
}
return iter;
}

// search for a given element inside a list in the range
// spefied by "first" and "last"
iterator find(iterator first, iterator last, const T value) const {
iterator iter = first;
iterator end_pos = last;
if(end_pos != end()) {
end_pos = ++last;
}
for(; iter != end_pos; ++iter) {
if(*iter == value) {
return iter;
}
}
return iterator();
}

// search for a given element inside a list
iterator find(const T value) const {
return find(begin(), end(), value);
}

// inserts an element at the position
// specified by the variable "iter"
void insert(iterator iter, T data) {
if(iter == begin()) {
insert_before(pHead, data);
} else if(iter == end()) {
insert_after(pTail, data);
} else {
insert_after(iter.getNodePtr()->prev, data);
}
}

// inserts an element after a given node
void insert_after(Node<T> *pBefore, T data) {
Node<T> *pNode = new Node<T>;
if(pNode == NULL) {
throw "memory allocation failure (pNode - after)";
}
pNode->data = data;
insert_after(pBefore, pNode);
}

// inserts an element before a given node
void insert_before(Node<T> *pAfter, T data) {
Node<T> *pNode = new Node<T>;
if(pNode == NULL) {
throw "memory allocation failure (pNode - before)";
}
pNode->data = data;
insert_before(pAfter, pNode);
}

// inserts a new node after a given node
void insert_after(Node<T> *pBefore, Node<T> *pNode) {
pNode->prev = pBefore;
pNode->next = pBefore->next;
if(pBefore->next == NULL) {
pTail = pNode;
} else {
pBefore->next->prev = pNode;
}
pBefore->next = pNode;
}

// inserts a new node before another one
void insert_before(Node<T> *pAfter, Node<T> *pNode) {
pNode->prev = pAfter->prev;
pNode->next = pAfter;
if(pAfter->prev == NULL) {
pHead = pNode;
} else {
pAfter->prev->next = pNode;
}
pAfter->prev = pNode;
}

// add a node at the tail of the list
void push_back(T data) {
if(pTail == NULL) {
create_list();
pHead->data = data;
pTail->data = data;
} else {
insert_after(pTail, data);
}
}

// add a node in front of the list
void push_front(T data) {
if(pHead == NULL) {
create_list();
pHead->data = data;
pTail->data = data;
} else {
insert_before(pHead, data);
}
}

// removes the last node of the list
void pop_back() {
remove_node(pTail);
}

// removes the first node of the list
void pop_front() {
remove_node(pHead);
}

// removes the current node from the list
void remove_node( Node<T> *pNode ) {
if(pNode == pHead) {
pHead = pHead->next;
} else {
pNode->prev->next = pNode->next;
}
if(pNode->next == NULL) {
pTail = pNode->prev;
} else {
pNode->next->prev = pNode->prev;
}
delete pNode;
}

// removes a given element from a list
void remove(const T data) {
iterator iter = find(data);
if(iter != end()) {
erase(iter);
}
}

// check to see if a list is empty
bool empty() const {
return (size() == 0);
}

// computes the size of the list
size_t size() const {
const_iterator iter(pHead);
size_t counter = 0;
for(; iter != end(); ++iter, ++counter)
;
return counter;
}

// assign one list to another one
CDList &operator =( const CDList &rhs ) {
if(this->size() > 0) {
this->clear();
}
iterator iter(rhs.pHead);
for( ; iter != end(); ++iter ) {
this->push_back(*iter);
}
return *this;
}

// checks to see if two list are equal
bool operator ==( const CDList &rhs ) const {
bool bRet = 1;
if(this->size() != rhs.size()) {
bRet = 0;
} else {
const_iterator it1(this->pHead);
const_iterator it2(rhs.pHead);
for(; it1 != end(); ++it1, ++it2) {
if(*it1 != *it2) {
bRet = 0;
break;
}
}
}
return bRet;
}

private:
// allocates memory for the head and tail of the list
// which at these specific moment is the same node
void create_list() {
pHead = new Node<T>;
if(pHead == NULL) {
throw "memory allocation failure (pHead)";
}
pTail = pHead;
pHead->prev = NULL;
pTail->next = NULL;
}

private:
Node<T> *pHead;
Node<T> *pTail;

};


#endif

******************************************************************
.h file and main program
******************************************************************