path: root/List.hpp

/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   List.hpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/02/01 09:31:07 by cacharle          #+#    #+#             */
/*   Updated: 2020/04/26 12:50:59 by charles          ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#ifndef LIST_HPP
# define LIST_HPP

# include <cstddef>
# include <memory>

namespace ft
{
	template < typename T, typename Alloc = std::allocator<T> >
	class List
	{
    public:
		typedef T                                        value_type;
		typedef Alloc                                    allocator_type;
		typedef typename allocator_type::reference       reference;
		typedef typename allocator_type::const_reference const_reference;
		typedef typename allocator_type::pointer         pointer;
		typedef typename allocator_type::const_pointer   const_pointer;
		typedef ptrdiff_t                                difference_type;
		typedef size_t                                   size_type;

        explicit List(const allocator_type& alloc = allocator_type())
            : m_front(NULL), m_back(NULL), m_size(0), m_alloc(alloc) {}

        List(const List& other) : m_front(NULL), m_back(NULL) { *this = other; }

        List& operator=(const List& other)
        {
            if (this == &other)
                return *this;
            clear();
            for (iterator it = other.begin(); it != other.end(); ++it)
                push_back(*it);
            m_alloc = other.m_alloc;
            return *this;
        }

        ~List() { delete m_front; }

        explicit List(size_type n,
                      const value_type& val = value_type(),
                      const allocator_type& alloc = allocator_type())
            : m_front(NULL), m_back(NULL), m_size(0), m_alloc(alloc)
        {
            while (n-- > 0)
                push_back(val);
        }

        template<typename InputIterator>
        List(InputIterator first,
             InputIterator last,
             const allocator_type& alloc = allocator_type())
            : m_front(NULL), m_back(NULL), m_size(0), m_alloc(alloc)
        {
            for (; first != last; ++first)
                push_back(*first);
        }

    private:
        class ListNode
        {
        public:
            ListNode() : m_next(NULL), m_prev(NULL), m_data(value_type()) {}

            ListNode(const ListNode& other) { *this = other; }

            ListNode& operator=(const ListNode& other)
            {
                if (this == &other)
                    return *this;
                m_next = other.m_next;
                m_prev = other.m_prev;
                m_data = other.m_data;
                return *this;
            }

            ~ListNode()
            {
                if (m_next != NULL) {
                    m_next->m_prev = NULL;
                    delete m_next;
                }
                if (m_prev != NULL) {
                    m_prev->m_next = NULL;
                    delete m_prev;
                }
            }

            ListNode(const value_type& data) : m_next(NULL), m_prev(NULL), m_data(data) {}

            ListNode*   getNext() const { return m_next; }
            ListNode*   getPrev() const { return m_prev; }
            value_type& getData()       { return m_data; }

            void        setNext(ListNode* val)   { m_next = val; }
            void        setPrev(ListNode* val)   { m_prev = val; }
            void        setData(const value_type& val) { m_data = val; }

        private:
            ListNode*  m_next;
            ListNode*  m_prev;
            value_type m_data;
        };

    public:
        class iterator
        {
            friend class List<T, Alloc>;
        public:
            iterator() : m_current(NULL) {}
            iterator(const iterator& other) { *this = other; }
            ~iterator() {}

            iterator& operator=(const iterator& other)
            {
                if (this == &other)
                    return *this;
                m_current = other.m_current;
                return *this;
            }

            value_type& operator*()  { return m_current->getData();  }
            value_type* operator->() { return &m_current->getData(); }

            bool operator==(const iterator& other) const { return m_current == other.m_current; }
            bool operator!=(const iterator& other) const { return !(*this == other);            }

            iterator& operator++()    { m_current = m_current->getNext(); return *this;  }
            iterator& operator--()    { m_current = m_current->getPrev(); return *this;  }
            iterator  operator++(int) { iterator copy(*this); operator++(); return copy; }
            iterator  operator--(int) { iterator copy(*this); operator--(); return copy; }

        private:
            iterator(ListNode* current) : m_current(current) {}

            List::ListNode* m_current;
        };

        class const_iterator : public iterator
        {
        public:
            const_iterator() : iterator() {}
            const_iterator(const iterator& other) : iterator(other) {}
            ~const_iterator() {}
            const value_type& operator*()  const { return iterator::m_current->getData();  }
            const value_type* operator->() const { return &iterator::m_current->getData(); }
        };

        iterator        begin()          { return iterator(m_front);       }
        iterator        end()            { return iterator(NULL);          }
        const_iterator  begin()    const { return const_iterator(m_front); }
        const_iterator  end()      const { return const_iterator(NULL);    }

        bool            empty()    const { return m_size == 0;             }
        size_type       size()     const { return m_size;                  }
        size_type       max_size() const { return UINT_MAX;                }

        reference       front()          { return m_front->getData();      }
        reference       back()           { return m_back->getData();       }
        const_reference front()    const { return m_front->getData();      }
        const_reference back()     const { return m_back->getData();       }

        template <typename InputIterator>
        void assign(InputIterator first, InputIterator last)
        {
            clear();
            for (; first != last; ++first)
                push_back(*first);
        }

        void assign(size_type n, const value_type& val)
        {
            clear();
            while (n-- > 0)
                push_back(val);
        }

        void push_front(const value_type& val)
        {
            ListNode* new_front = new ListNode(val);
            new_front->setNext(m_front);
            if (m_front != NULL)
                m_front->setPrev(new_front);
            else
                m_back = new_front;
            m_front = new_front;
            m_size++;
        }

        void push_back(const value_type& val)
        {
            ListNode* new_back = new ListNode(val);
            new_back->setPrev(m_back);
            if (m_back != NULL)
                m_back->setNext(new_back);
            else
                m_front = new_back;
            m_back = new_back;
            m_size++;
        }

        void pop_front()
        {
            ListNode* tmp = m_front->getNext();
            tmp->setPrev(NULL);
            m_front->setNext(NULL);
            delete m_front;
            m_front = tmp;
            m_size--;
        }

        void pop_back()
        {
            ListNode* tmp = m_back->getPrev();
            tmp->setNext(NULL);
            m_back->setPrev(NULL);
            delete m_back;
            m_back = tmp;
            m_size--;
        }

        iterator insert(iterator position, const value_type& val)
        {
            ListNode* inserted = new ListNode(val);

            if (position.m_current->m_prev != NULL)
                position.m_current->m_prev->m_next = inserted;
            else
                m_front = inserted;
            if (position.m_current->m_next != NULL)
                position.m_current->m_next->m_prev = inserted;
            else
                m_back = inserted;
            m_size++;
            return iterator(inserted);
        }

        void insert(iterator position, size_type n, const value_type& val)
        {
            while (n-- > 0)
                insert(position, val);
        }

        template <typename InputIterator>
        void insert(iterator position, InputIterator first, InputIterator last)
        {
            if (first == last)
                return;
            --last;
            for (; last != first; --last)
                insert(position, *last);
            insert(position, *last);
        }

        iterator erase(iterator position)
        {
            iterator ret(position.m_current->m_next);

            if (position.m_current->m_prev != NULL)
                position.m_current->m_prev->m_next = position.m_current->m_next;
            if (position.m_current->m_next != NULL)
                position.m_current->m_next->m_prev = position.m_current->m_prev;
            delete position.m_current;
            m_size--;
            return ret;
        }

        iterator erase(iterator first, iterator last)
        {
            iterator tmp(first);

            while (first != last)
            {
                ++tmp;
                erase(first);
                first = tmp;
            }
            return last;
        }

        void swap(List& x)
        {
            ListNode*      tmp_front = x.m_front;
            ListNode*      tmp_back  = x.m_back;
            size_type      tmp_size  = x.m_size;
            allocator_type tmp_alloc = x.m_alloc;

            x.m_front = m_front;
            x.m_back = m_back;
            x.m_size = m_size;
            x.m_alloc = m_alloc;

            m_front = tmp_front;
            m_back = tmp_back;
            m_size = tmp_size;
            m_alloc = tmp_alloc;
        }

        void resize(size_type n, value_type val = value_type())
        {
            if (n == m_size)
                return;
            if (n < m_size)
                while (n-- > 0)
                    pop_back();
            else
                while (n-- > 0)
                    push_back(val);
        }

        void clear()
        {
            delete m_front;
            m_front = NULL;
            m_back = NULL;
            m_size = 0;
        }

        void remove(const value_type& val) { remove_if(EqualPredicate(val)); }

        template <typename Predicate>
        void remove_if(Predicate pred)
        {
            for (iterator it = begin(); it != end(); ++it)
                if (pred(*it))
                    erase(it);
        }

        void merge(List& x) { merge(x, &compar); }

        template <typename Compare>
        void merge(List& x, Compare comp)
        {
            iterator it = begin();
            while (!x.empty())
            {
                while (it != end() && comp(*it, x.front()))
                    ++it;
                insert(it, x.front());
                x.pop_front();
            }
        }

        void sort() { sort(&compar); }

        template <typename Compare>
        void sort(Compare comp)
        {
            (void)comp;
            // for (iterator it = begin(); it != end(); ++it)
            // {
            //     for (iterator it2(it); it2 != end(); ++it)
            // }
        }

        void reverse()
        {

        }

        bool operator==(const List& other) const
        {
            if (m_size != other.m_size)
                return false;
            iterator it1 = begin();
            iterator it2 = begin();
            for (; it1 != end(); ++it1, ++it2)
                if (*it1 != *it2)
                    return false;
            return true;
        }

        bool operator!=(const List& other) const { return !(*this == other); }

        bool operator<(const List& other) const
        {
            iterator it1 = begin();
            iterator it2 = begin();
            for (; it1 != end() && it2 != end() && *it1 == *it2; ++it1, ++it2);

            if (it1 == end() && it2 == other.end())
                return false;
            if (it1 == end() || it2 == other.end())
                return it1 == end();
            return *it1 < *it2;
        }

        bool operator>(const List& other)  const { return other < *this;    }
        bool operator<=(const List& other) const { return !(*this > other); }
        bool operator>=(const List& other) const { return !(*this < other); }

    private:
        ListNode* m_front;
        ListNode* m_back;
        size_type m_size;
        allocator_type m_alloc;

        static bool compar(const value_type& a, const value_type& b) { return a < b;  }

        struct EqualPred
        {
            bool operator()(const value_type& other) const { return val == other; }
            const value_type& val;
        };
    };
}

#endif