// $Id: list.h,v 1.4 2006-10-15 16:59:12 cactus Exp $ -*- c++ -*-

#ifndef EAF_LIST_H
#define EAF_LIST_H

template<typename T>
class List
{
public:
    typedef T value_t;
    
private:
    struct Node
    {
        value_t  value;
        Node    *next;
            
    public:
        Node (const value_t &value_, Node *next_ = 0):
            value (value_),  next (next_) {}
    };
    
    Node   *first;
    Node   *last;
    
public:
    class iterator
    {
        Node *prev;
        Node *curr;
        friend class List;
        
        iterator (Node *prev_, Node *curr_): prev (prev_), curr (curr_) {}
        
    public:
        typedef value_t                    value_type;
        typedef value_t&                   reference;
        typedef value_t*                   pointer;
        typedef ptrdiff_t                  difference_type;
        typedef std::forward_iterator_tag  iterator_category;
        
        iterator () : prev (0), curr (0) {}
        
        iterator&      operator++() { prev = curr; curr = curr->next; return *this;}
        const iterator operator++(int) { iterator ret = *this; ++*this; return ret; }
        
        reference operator* ()  { return curr->value; }
        pointer   operator-> () { return &curr->value; }
        
        bool operator== (const iterator &other) const { return other.curr == curr; }
        bool operator!= (const iterator &other) const { return !(other == *this); }
        
        operator bool () const { return curr != 0; }
    };
    
    class const_iterator
    {
        Node *prev;
        Node *curr;
        friend class List;
        
        const_iterator (Node *prev_, Node *curr_): prev (prev_), curr (curr_) {}
        
    public:
        typedef value_t                    value_type;
        typedef value_t&                   reference;
        typedef value_t*                   pointer;
        typedef ptrdiff_t                  difference_type;
        typedef std::forward_iterator_tag  iterator_category;
        
        const_iterator (): prev (0), curr (0) {}
        
        const_iterator (const iterator &src): prev (src.prev), curr (src.curr) {}
        
        const_iterator&      operator++() { prev = curr; curr = curr->next; return *this;}
        const const_iterator operator++(int) { iterator ret = *this; ++*this; return ret; }
        
        const reference operator* ()  { return curr->value; }
        const pointer   operator-> () { return &curr->value; }
        
        bool operator== (const const_iterator &other) const { return other.curr == curr; }
        bool operator!= (const const_iterator &other) const { return !(other == *this); }
        
        operator bool () const { return curr != 0; }
    };
    
    List () : first (0), last (first) {}
    
    ~List () {
        clear ();
    }

    // Copying, assignment
    List (const List &other): first (0), last (first) {
        for (const_iterator i = other.begin (); i != other.end (); ++i)
            insert (end (), *i);
    }

    List& operator= (const List &other) {
        if (this == &other) return *this;
        
        clear ();
        for (const_iterator i = other.begin (); i != other.end (); ++i)
            insert (end (), *i);

        return *this;
    }
    
    iterator       begin ()       { return iterator (0, first); }
    const_iterator begin () const { return const_iterator (0, first); }

    iterator       end ()       { return iterator (last, 0); }    
    const_iterator end () const { return const_iterator (last, 0); }

    size_t size () const { return std::distance (begin (), end ()); }
    
    void insert (const iterator &iter, const value_t &value) {
        if (!iter.prev)
        {
            first = new Node (value, first);
            if (!first->next)
                last = first;
        } else {
            Node *new_node = new Node (value, iter.curr);
            iter.prev->next = new_node;
            
            if (!iter.curr)
                last = new_node;
        }
    }
    
    void remove (const iterator &iter) {
        if (!iter.prev)
        {
            first = first->next;
        } else {
            if (!iter.curr)
                throw std::runtime_error ("Trying to remove extremal item from list");
            
            iter.prev->next = iter.curr->next;
        }

        if (iter.curr == last)
            last = iter.prev;
        delete iter.curr;
    }

    void clear () {
        Node *i = first;
        while (i)
        {
            Node *next = i->next;
            delete i;
            i = next;
        }

        first = 0;
        last = first;
    }
};

#endif