#ifndef DDCHAIN_H
#define DDCHAIN_H

#include "Exception.h"
#include 

template
class DDChain;

template
class DDChainNode{
    friend class DDChain;
private:
    T data;
    DDChainNode* left;
    DDChainNode* right;
};

template
class DDChain{
public:
    DDChain(){leftEnd = rightEnd = 0;}
    ~DDChain();
    int Length() const;
    bool isEmpty();
    bool Find(int k,T& x) const;
    int Search(const T&  x);
    DDChain& Delete(int k,T& x);
    DDChain& Insert(int k,const T& x);
    void print();
private:
    DDChainNode* leftEnd;
    DDChainNode* rightEnd;
};

template
DDChain::~DDChain()
{
   DDChainNode* current = leftEnd;

   while(current){
       leftEnd = leftEnd->right;
       delete current;
       current = leftEnd;
   }

  leftEnd = rightEnd = 0;
}

template
bool DDChain::isEmpty()
{
    return ((leftEnd == rightEnd) && (leftEnd == 0));
}

template
int DDChain::Length() const
{
    DDChainNode* current = leftEnd;

    int index = 0;
    while(current){
        index++;
        current = current->right;
    }

    return index;
}

template
bool DDChain::Find(int k, T &x) const
{
    if(k < 1)
        throw OutOfBounds();

    DDChainNode* current = leftEnd;

    for(int i = 1;i < k && current;i++){
        current = current->right;
    }

    if(!current)
        return false;

    x = current->data;
    return true;
}

template
int DDChain::Search(const T &x)
{
    DDChainNode* current = leftEnd;
    int index = 1;

    while(current && (current->data != x)){
        index++;
        current = current->right;
    }

    if(current)
        return index;
    else
        return -1;
}

template
DDChain& DDChain::Delete(int k, T &x)
{
    if(k < 1)
        throw OutOfBounds();

   DDChainNode* current = leftEnd;
   DDChainNode *p = current->left;
   DDChainNode  *q = current->right;

   for(int i = 1;i < k && current;i++){
        p = current;
        current = current->right;
        q = current->right;
   }

   if(!current)
       throw OutOfBounds();

   if(p == 0 && q == 0){
       x = current->data;
       delete current;
       leftEnd = rightEnd = 0;

       return *this;
   }

   if(p == 0 && q != 0){
       leftEnd = leftEnd->right;

       x = current->data;

       delete current;

       return *this;
   }

   if(q == 0 && p != 0){
       rightEnd = rightEnd->left;

       x = current->data;
       delete current;

       return *this;
   }

   p->right = current->right;
   q->left = current->left;

   x = current->data;
   delete current;

   return *this;
}

template
DDChain& DDChain::Insert(int k, const T &x)
{
    if(k < 0)
        throw OutOfBounds();

    DDChainNode* temp = new DDChainNode();
    temp->data = x;

    if((leftEnd == rightEnd) && (leftEnd == 0)){
        std::cout << "insert" << std::endl;

        leftEnd = rightEnd = temp;
        leftEnd->left = 0;
        leftEnd->right = 0;

        return *this;
    }

    if(k == 0){
        temp->left = 0;
        temp->right = leftEnd;

        leftEnd = temp;

        return *this;
    }

    DDChainNode* current = leftEnd;
    DDChainNode* p = current->right;

    for(int i = 1;i < k && current;i++){
        current = current->right;
        p = current->right;
    }

    if(!current)
        throw OutOfBounds();

    if(current && !p){
        rightEnd->right = temp;
        temp->left = rightEnd;
        temp->right = 0;

        rightEnd = temp;

        return *this;
    }

    current->right = temp;
    temp->right = p;
    temp->left = current;
    p->left = temp;

    return *this;

}

template
void DDChain::print()
{
    DDChainNode* current = leftEnd;

    while(current){
        std::cout << current->data << " ";
        current = current->right;
    }

    std::cout << std::endl;
}

#endif // DDCHAIN_H