/**
*       Sean Vogel
*       11 -28 -2012
*       Just a linked list
*/
#ifndef SV_LINK_LIST
#define SV_LINK_LIST
 #define NULL 0
#include <limits>
 
namespace sv
{
        template <class T>
        class list
        {
                class node
                {      
                public:
                        node *prev,
                                *next;
 
                        T data;
 
                        node() : prev(NULL), next(NULL), data(NULL){}
                        node(const T& t) : prev(NULL), next(NULL), data(t){}
                };
 
                node *_front,
                        *_back;
                unsigned int _size;
 
        public:
                class iterator
                {
                        node* _node;
                public:
                        iterator() : _node(NULL){}
                        iterator(node* n) : _node(n){}
                        iterator(const iterator& it) : _node(it._node){}
                        T& operator*(){ if(_node)return _node->data; }
                        T& operator->(){ if(_node)return _node->data; }
                        iterator& operator++()
                        {
                                if(_node)
                                {
                                        _node = _node->next;
                                }
                                return *this;
                        }
                        iterator operator++(int)
                        {
                                iterator it(*this);
                                ++(*this);
                                return it;
                        }
                        iterator& operator--()
                        {
                                if(_node)
                                {
                                        _node = _node->prev;
                                }
                                return *this;
                        }
                        iterator& operator--(int)
                        {
                                iterator it(*this);
                                --(*this);
                                return it;
                        }
                        bool operator!=(const iterator& it) const { return (this->_node != it._node); }
 
                        iterator& operator=(const iterator& it)
                        {
                                _node = it._node;
                                return *this;
                        }
                };             
 
                //constructors
                list() : _front(NULL), _back(NULL), _size(NULL){}
                list(unsigned int , const T& t = T()){}
                list(const list<T>&);
                template < class InputIterator >
        list(InputIterator first, InputIterator last);
                ~list();
 
                //iterators
                iterator begin();
                iterator end();
                //iterator rbegin();
                //iterator rend();
 
                //operators
                list<T>& operator=(const list<T>&);
 
                //element access
                T& front();
                T& back();
 
                //capacity
                bool empty() const;
                unsigned int size() const;
                unsigned int max_size() const;
                void resize(unsigned int, const T& t);
 
                //modifiers
                void push_front(const T&);
                void pop_front();
                void push_back(const T&);
                void pop_back();
                //iterator insert(iterator pos, const T&);
                //void insert(iterator pos, unsigned int size, const T&);
                //void insert(iterator position, InputIterator first, InputIterator last);
                //iterator erase(iterator position);
                //iterator erase(iterator first, iterator last);
                //void swap(list<T>& lst);
                void clear();
                //void assign(size_type n, const T& u);
                //void assign(InputIterator first, InputIterator last);
 
                //operations
                //void remove(const T& value);
                //template <class Predicate>
                //void remove_if(Predicate pred);
                //void sort(list<T>& lst);
                //void merge(list<T>& lst):
                //void splice(iterator position, list<T,Allocator>& x);
                //void splice(iterator position, list<T,Allocator>& x, iterator i);
                //void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
                //void unique();
                //template <class BinaryPredicate>
                //void unique(BinaryPredicate binary_pred);
                //void reverse();
        };
 
        template <class T>
        typename list<T>::iterator list<T>::begin()
        {
                return iterator(_front);
        }
 
        template <class T>
        typename list<T>::iterator list<T>::end()
        {
                return iterator(_back->next);
        }
 
        /*template <class T>
        typename list<T>::iterator list<T>::rbegin()
        {
                return iterator(_back);
        }
 
        template <class T>
        typename list<T>::iterator list<T>::rend()
        {
                return iterator(_front->prev);
        }*/
 
        template <class T>
        list<T>::list(const list<T>& lst) : _front(NULL), _back(NULL), _size(NULL)
        {
                if(!lst.empty())
                {
                        node* n = lst._front;                  
                        while(n)
                        {
                                push_back(n->data);
                                n = n->next;                                           
                        }
                }
        }
 
        template <class T>
        list<T>& list<T>::operator=(const list<T>& lst)
        {
                if(this != &lst && !lst.empty())
                {
                        clear();
 
                        node* n = lst._front;                  
                        while(n)
                        {
                                push_back(n->data);
                                n = n->next;                                           
                        }
                }
                return this;
        }
 
        template <class T>
        list<T>::~list()
        {
                clear();
        }
 
        template <class T>
        bool list<T>::empty()const {return !_front;}
 
        template <class T>
        unsigned int list<T>::size()const{return _size;}
 
        template <class T>
        unsigned int list<T>::max_size()const {return std::numeric_limits<T>::max();}
 
        template <class T>
        void list<T>::resize(unsigned int sz, const T& t = T())
        {
                while(sz > _size)
                {
                        push_back(t);
                }
        }
 
        template <class T>
        T& list<T>::front()
        {
                if(_front)
                        return _front->data;
        }
 
        template <class T>
        T& list<T>::back()
        {
                if(_back)
                        return _back->data;
        }
 
        template <class T>
        void list<T>::push_front(const T& t)
        {                      
                node* n = new node(t);
 
                if(_front)
                {
                        n->next = _front;
                        _front->prev = n;
                        _front = n;
                }
                else
                {
                        _back = _front = n;
                }
                ++_size;
        }
 
        template <class T>
        void list<T>::pop_front()
        {
                if(front)
                {
                        node* n = _front->next;
                        delete _front;
                        _front = n;
                        --_size;
                }              
        }
 
        template <class T>
        void list<T>::push_back(const T& t)
        {
                node* n = new node(t);
 
                if(_back)
                {
                        n->prev = _back;
                        _back->next = n;
                        _back = n;
                }
                else
                {
                        _front = _back = n;                    
                }
                ++_size;
        }
 
        template <class T>
        void list<T>::pop_back()
        {
                if(back)
                {
                        node* n = _back->prev;
                        delete _back;
                        _back = n;
                        --_size;
                }              
        }
 
        template <class T>
        void list<T>::clear()
        {
                node* n;
                while(_front)
                {
                        n = _front->next;
                        delete _front;
                        _front = n;
                        --_size;
                }
                _front = _back = NULL;
        }
}
#endif
#include <iostream>
int main()
{
        sv::list<int> lst;
        for(int i = 0; i < 10; ++i)
                lst.push_front(i + 1);
        lst.resize(20, 9333);
        if(!lst.empty())
                std::cout<<"front= " << lst.front()<<" back= "<<lst.back()<<" size= "<<lst.size()<<std::endl;
        {
        sv::list<int> lst2 = lst;
        if(!lst2.empty())
                std::cout<<"front= " << lst2.front()<<" back= "<<lst2.back()<<" size= "<<lst2.size()<<std::endl;
        }
 
        sv::list<int>::iterator it;
        sv::list<int>::iterator end = lst.end();
        for(it=lst.begin(); it != lst.end(); it++)
                std::cout<<*it<<std::endl;
 
        //std::cout<<l.max_size()<<std::endl;
        //std::cout<<lst.max_size()<<std::endl;
}