// filename: List.h
//   author: John Flores
//     date: May, 2003.
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

#ifndef LIST_H
#define LIST_H

#include <stdlib.h>
#include <assert.h>

template <class T>
class List {
    struct Node {
        T     data;
        Node *prev;
        Node *next;

        Node(const T &d, Node *p, Node *n): data(d), prev(p), next(n) {}
    };

    Node *head;
    Node *tail;

public:
    class iterator;
    friend class iterator;

    class iterator {
        friend class List;

        List *list;
        Node *node;

    public:
        iterator(List *l = NULL, Node *n = NULL): list(l), node(n) {}
        iterator operator++(int) {
            if (list != NULL) {
                if (node != NULL)
                    node = node->next;
                else
                    node = list->head;
            }
            return *this;
        }
        iterator operator--(int) {
            if (list != NULL) {
                if (node != NULL)
                    node = node->prev;
                else
                    node = list->tail;
            }
            return *this;
        }
        T *operator->() {
            assert(list != NULL && node != NULL);
            return &(node->data); 
        }
        T &operator*() {
            assert(list != NULL && node != NULL);
            return node->data;
        }
        bool operator!=(iterator rhs) {
            return list != rhs.list || node != rhs.node;
        }
        bool operator==(iterator rhs) {
            return list == rhs.list && node == rhs.node;
        }
    };

    List(): head(NULL), tail(NULL) {}
    ~List() {
        Node *next;
        while (head != NULL) {
            next = head->next;
            delete head;
            head = next;
        }
    }
    iterator insert(iterator itr, const T &data) {
        if (itr.list == this) { 
            Node *node = new Node(data, 
                                  itr.node!=NULL?itr.node->prev:tail, 
                                  itr.node);

            if (node->prev != NULL)
                node->prev->next = node;
            else
                head = node;
     
            if (node->next != NULL)
                node->next->prev = node;
            else
                tail = node;

            return iterator(this, node);
        }       
        return itr;
    }
    // insert a node AFTER itr
    iterator rinsert(iterator itr, const T &data) {
        if (itr.list == this) { 
            Node *node = new Node(data, 
                                  itr.node,
                                  itr.node!=NULL?itr.node->next:head);

            if (node->prev != NULL)
                node->prev->next = node;
            else
                head = node;
     
            if (node->next != NULL)
                node->next->prev = node;
            else
                tail = node;

            return iterator(this, node);
        }       
        return itr;
    }
    iterator remove(iterator itr) {
        if (itr.list == this) { 
            if (itr.node != NULL) { 
                if (itr.node->next != NULL)
                    itr.node->next->prev = itr.node->prev;

                if (itr.node->prev != NULL)
                    itr.node->prev->next = itr.node->next;

                if (itr.node == head)
                    head = head->next;

                if (itr.node == tail)
                    tail = tail->prev;

                Node *node = itr.node->next;
                delete itr.node;

                return iterator(this, node);
            } else {    
                return iterator(this, NULL);
            }       
        }       
        return itr;
    }
    iterator rremove(iterator itr) {
        if (itr.list == this) { 
            if (itr.node != NULL) { 
                if (itr.node->next != NULL)
                    itr.node->next->prev = itr.node->prev;

                if (itr.node->prev != NULL)
                    itr.node->prev->next = itr.node->next;

                if (itr.node == head)
                    head = head->next;

                if (itr.node == tail)
                    tail = tail->prev;

                Node *node = itr.node->prev;
                delete itr.node;

                return iterator(this, node);
            } else {    
                return iterator(this, NULL);
            }       
        }       
        return itr;
    }
    iterator begin() {
        return iterator(this, head);
    }
    iterator end() {
        return iterator(this, NULL);
    }
    iterator rbegin() {
        return iterator(this, tail);
    }
    iterator rend() {
        return iterator(this, NULL);
    }
    bool isempty() {
        return head == NULL;
    }
};

#endif