#ifndef __list__

#define __list__

template class list

    {

     class node;

     friend class node;

    public:

     class iterator;

     friend class iterator;

     //Constructor

     list():pHead(0),pTail(0) {};

     //Destructor

     ~list() { PopAll(); };

     //This method allocated new nodes.

     //You have to clean out the list yourself before.

     //Example: iterator i = GetHead(); while(*i) delete PopHead();

     list &operator = (const list &m)

         {

         if(this == &m) return *this;

         iterator i = m.GetHead();

         while(*i) PushTail(*i++);

         return *this;

         };

         //The iteration class.

         class iterator

             {

             public:

             friend iterator;

             friend list;

             iterator(node *nNode = 0):pNode(nNode) {};

             explicit iterator(iterator &i):pNode(i.pNode) {};

             ~iterator() {};

             iterator &operator = (node *nNode) { pNode = nNode; return *this; };

             iterator &operator ++ (void) { pNode = pNode->pNext; return *this; };

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

             iterator &operator -- (void) { pNode = pNode->pPrev; return *this; };

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

             T *operator * (void) { return (pNode) ? (&**pNode):0; };

             T *operator -> () { return (**this); };

             bool  operator == (iterator &i) const { return (pNode == i.pNode); };

             bool  operator == (node *n)  const { return (pNode == n); };

             bool  operator != (iterator &i) const { return (pNode != i.pNode); };

             bool  operator != (node *n)  const { return (pNode != n); };

             protected:

             private:

             node *pNode;

             };

             //Returns pointer to pHead

             node *GetHead(void) const { return pHead; };

             //Returns pointer to pTail

             node *GetTail(void) const { return pTail; };

             //Adds an item at head-position

             node *PushHead(T *nData)

                 {

                 if(!nData) return 0;

                 node *n = new node(nData);

                 if (!pTail) pTail = n;

                 else pHead->pPrev = n;

                 n->pNext = pHead;

                 pHead = n;

                 return n;

                 };

                 //Adds an item at tail-position

                 node *PushTail(T *nData)

                     {

                     if(!nData) return 0;

                     node *n = new node(nData);

                     if (!pHead) pHead = n;

                     else pTail->pNext = n;

                     n->pPrev = pTail;

                     pTail = n;

                     return n;

                     };

                     //Detaches the first node and returns the item

                     T *PopHead(void) { return Detach(pHead); };

                     //Detaches the last node and returns the item

                     T *PopTail(void) { return Detach(pTail); };

                     //Detaches the node pointed on by i

                     T *Pop(iterator &i) { return Detach(i.pNode); };

                     //Detaches n and returns n's item

                     T *Pop(node *n)  { return Detach(n); };

                     //Removes and deletes node, deletes item.

                     void  Erase(iterator &i) { delete Detach(i.pNode); };

                     //Removes and deletes all nodes, deletes all items.

                     void  EraseAll(void) { iterator i(GetHead()); while(*i) Erase(i++); };

                     //Removes all nodes, does not free memory for items, use with caution

                     void  PopAll(void) { iterator i(GetHead()); while(*i) Pop(i++); };

                     //Returns pointer to the node pointing to nData, else returns 0

                     node *Find(T *nData)

                         {

                         iterator i = GetHead();

                         while(*i) { if(i.pNode->pData == nData) return i.pNode; ++i; }

                         return 0;

                         };

                         //Counts and returns number of items in list.

                         int GetCount(void) { int x = 0; for(iterator i = GetHead();*i;++i,++x); return x; };

                        protected:

                        private:

                         T *Detach(node *nNode)

                             {

                             if(!nNode) return 0;

                             if (!nNode->pPrev) pHead = nNode->pNext;

                             else nNode->pPrev->pNext = nNode->pNext;

                             if (!nNode->pNext) pTail = nNode->pPrev;

                             else nNode->pNext->pPrev = nNode->pPrev;

                             T *p = nNode->pData;

                             delete nNode;

                             return p;

                             };

                             class node

                                 {

                                 friend class list;

                                 friend class node;

                                 friend class iterator;

                                 public:

                                 node(T *nData = 0):pData(nData),pPrev(0),pNext(0) {};

                                 ~node() {};

                                 private:

                                 T &operator * (void) { return *pData; };

                                 node *pPrev;

                                 node *pNext;

                                 T *pData;

                                 };

                                 node *pHead;

                                 node *pTail;

                            };

                            #endif