#include <iostream>
using namespace std;

#include "MyException.h"

enum IterPosition {
   AtNode = 0,
   AtBeg = 0x1,
   AtEnd = 0x2
};



template <class T>
class DList
{
private:

   struct DListNode
   {
      T value;
      DListNode *next, *prev;
      DListNode() { next = prev = nullptr; }
      void LinkNext(DListNode *p) { next = p; if (p) p->prev = this; }
      void LinkPrev(DListNode *p) { prev = p; if (p) p->next = this; }
   };
   DListNode *first, *last;
   size_t size;

public:


   class Iterator
   {
       friend class DList<T>;
       DList<T> *pList;
       DListNode *currentNode;
       int itpos;   // 0 на узлах, 1 перед началом, 2 после конца
       Iterator (DList<T> *p, DListNode *pos, int b) { pList = p; currentNode = pos;  itpos = b; }
    public:
       Iterator () { currentNode = nullptr; itpos = AtBeg | AtEnd; }
       Iterator (const Iterator & i) { *this = i; }
       Iterator & operator=(const Iterator & i) 
       { 
          pList = i.pList; currentNode = i.currentNode;  itpos = i.itpos;
          return *this;  
       }
       bool operator!=(const Iterator &i);
       bool operator==(const Iterator &i);
       Iterator & operator++();
       Iterator & operator--();
       T & operator*() { return currentNode->value; }
   };

   Iterator begin() { return Iterator(this, first, (first) ? AtNode : AtEnd); }
   Iterator end() { return Iterator(this, nullptr, AtEnd); }
   Iterator rbegin() { return Iterator(this, last, (last) ? AtNode : AtBeg); }
   Iterator rend() { return Iterator(this, nullptr, AtBeg); }

   class ConstIterator
   {
       friend class DList<T>;
       const DList<T> *pList;
       const DListNode *currentNode;
       int itpos;   
       ConstIterator (const DList<T> *p, const DListNode *pos, int b) { pList = p; currentNode = pos;  itpos = b; }
    public:
       ConstIterator ();
       ConstIterator (const ConstIterator & i);
       ConstIterator & operator=(const ConstIterator & i); 
       bool operator!=(const ConstIterator &i) const;
       bool operator==(const ConstIterator &i) const;
       ConstIterator & operator++();
       ConstIterator & operator--();
       const T & operator*() const;
   };

   ConstIterator cbegin();
   ConstIterator cend();
   ConstIterator crbegin();
   ConstIterator crend();

   // создание, уничтожение
   DList() { size = 0; first = last = nullptr; }
   ~DList();

   // добавление  ...
   void PushLast(const T &x);                    //

   // удаление  ...
   bool RemoveAt (Iterator &i);

   // проверка состояния
   int Size() const { return size; } 
 
   template <class P>
   friend ostream & operator<<(ostream & os, const DList<P> & list);

};
                                                          
 template <class T>
 ostream & operator<<(ostream & os, const DList<T> & list)
 {
    typename DList<T>::DListNode *p;
    cout << "[" << list.Size() << "] ";
    for (p  = list.first; p; p = p->next) {
       cout << " " << p->value ;
    }
    cout << endl;
    return os;
}  


 template <class T>
 DList<T>::~DList()
 {
    DListNode *p = first;
    while (first) {
        p = first;
        first = first->next;
        delete p;
    }
 }


template <class T> 
void DList<T>::PushLast(const T &x)
{
try {
    DListNode *p = new DListNode;
    p->value = x;
    ++size;
    if (last == 0) {
       first = last = p;
    } else {
       last->LinkNext(p);
       last = p;
    }
} catch (std::bad_alloc) {
    throw new MyException ("DList<T>::PushLast: memory allocation error\n", EC_MEMORY);
}                                                            
}


template <class T> 
bool DList<T>::RemoveAt (Iterator &i)
{
    if (i == end() || i == rend())  return false;
    DListNode *p = i.currentNode;
    p->prev->LinkNext(p->next);
    i.currentNode = p->next;
    delete p;
    size--;
    return true;    
}


template <class T> 
bool DList<T>::Iterator::operator!=(const Iterator &i) 
{
    if (pList != i.pList) return true;
    if (currentNode != i.currentNode) return true;
    if (itpos != i.itpos) return true;
    return false;
} 

template <class T> 
bool DList<T>::Iterator::operator==(const Iterator &i) 
{
    if (pList != i.pList) return false;
    if (currentNode != i.currentNode) return false;
    if (itpos != i.itpos) return false;
    return true;
    // или return !(*this != i); 
} 

template <class T> 
typename DList<T>::Iterator &  DList<T>::Iterator::operator++()
{
    if (currentNode) {
        currentNode = currentNode->next;
        if (currentNode == nullptr) itpos = AtEnd;
    }
    return *this; 
}

template <class T> 
typename DList<T>::Iterator &  DList<T>::Iterator::operator--() 
{
    if (currentNode) {
        currentNode = currentNode->prev;
        if (currentNode == nullptr) itpos = AtBeg;
    }
    return *this; 
}