/*=========================================================================
liste rotative autoreferencielle a double pointeur
par Martin Robinson
but : avoir une liste rotative autoreferencielle a double pointeur
===========================================================================
preprocessor*/

#pragma once
#ifndef _LIST
#define _LIST

/*=========================================================================
classe
=========================================================================*/
template <typename T>
class list{
    list<T> * _next,
            * _back;
    T _data;
    bool _isSentinel;
    void _copy(const list<T>&);
public:
    list();
    list(const list<T>&);
    const list& operator=(const list<T>&);
    ~list();
    //
    void push_back(const T&);
    void push_front(const T&);
    //
    void pop_back();
    void pop_front();
    //
    T& data();
    bool empty()const;
    int size()const;
    //iterator
    typedef list<T>* iterator;
    iterator begin();
    iterator end();
    iterator next();
    iterator back();
    iterator remove();
};

/*=========================================================================
methode
=========================================================================*/
template <typename T>
void list<T>::_copy(const list<T>&l)
{
    if(l._isSentinel)
    {
        _isSentinel = true;
        _next = _back = this;
        _copy(l);
        iterator it = l.begin();
        while(!it.atEnd())
            push_back(it.data());
    }
    else
    {
        _isSentinel = l._isSentinel;
        _next = l._next;
        _back = l._back;
        _data = l._data;
    }
}

template <typename T>
list<T>::list()
{
    _isSentinel = true;
    _next = _back = this;
}

template <typename T>
list<T>::list(const list<T>& l)
{
    _copy(l);
}

template <typename T>
const list<T>& list<T>::operator=(const list<T>&l)
{
    _copy(l);
    return *this;
}

template <typename T>
list<T>::~list()
{
    if(_isSentinel)
        while(!empty())
            pop_front();
    else
    {
        _back->_next = _next;
        _next->_back = _back;
    }
}

template <typename T>
void list<T>::push_back(const T& data)
{
    list<T> * tmp = new list<T>;
    tmp->_data = data;
    tmp->_isSentinel = false;
    tmp->_back = _back;
    tmp->_next = this;
    tmp->_back->_next = tmp;
    tmp->_next->_back = tmp;
}

template <typename T>
void list<T>::push_front(const T& data)
{
    list<T> * tmp = new list<T>;
    tmp->_data = data;
    tmp->_isSentinel = false;
    tmp->_back = this;
    tmp->_next = _next;
    tmp->_back->_next = tmp;
    tmp->_next->_back = tmp;
}

//
template <typename T>
void list<T>::pop_back()
{
    if (_back->_isSentinel)
        return;

    list<T> * tmp = _back;
    tmp->_next->_back = tmp->_back;
    tmp->_back->_next = tmp->_next;
    delete tmp;
}

template <typename T>
void list<T>::pop_front()
{
    if (_next->_isSentinel)
        return;

    list<T> * tmp = _next;
    tmp->_next->_back = tmp->_back;
    tmp->_back->_next = tmp->_next;
    delete tmp;
}

//
template <typename T>
T& list<T>::data()
{
    assert(!_isSentinel);
    return _data;
}

template <typename T>
bool list<T>::empty()const
{
    return _next == this;
}

template <typename T>
int list<T>::size()const
{
    list<T> tmp = begin();
    int n=0;
    while(!tmp->atEnd())
    {
        tmp = tmp->next();
        n++;
    }
    return n;
}

//iterator
template <typename T>
list<T>* list<T>::begin()
{
    if(_isSentinel)
        return _next;
    else
        return _back->begin();
}

template <typename T>
list<T>* list<T>::end()
{
    if(_isSentinel)
        return this;
    else
        return _next->end();
}

template <typename T>
list<T>* list<T>::next()
{
    return _next;
}

template <typename T>
list<T>* list<T>::back()
{
    return _back;
}

template <typename T>
list<T>* list<T>::remove()
{
    iterator tmp = _back;
    delete this;
    return tmp;
}

#endif