path: root/Vector.hpp

/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   Vector.hpp                                         :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: charles <charles.cabergs@gmail.com>        +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/24 16:19:04 by charles           #+#    #+#             */
/*   Updated: 2020/04/27 12:54:08 by charles          ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#ifndef VECTOR_HPP
# define VECTOR_HPP

# include <climits>
# include <cstddef>
# include <stdexcept>
# include "ReverseIterator.hpp"

# define FT_VECTOR_GROWTH_FACTOR 1.5

namespace ft
{
	template < typename T, typename Alloc = std::allocator<T> >
	class Vector
	{
        typedef Vector<T, Alloc>                         m_type;

    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;

        class iterator
        {
            friend class Vector;
        public:
            typedef Vector::value_type      value_type;
            typedef Vector::difference_type difference_type;

            iterator() : m_ptr(NULL), m_pos(-1) {}
            iterator(const iterator& other) : m_ptr(other.m_ptr), m_pos(other.m_pos) {}
            ~iterator() {}

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

            value_type& operator*()  { return (*m_ptr)[m_pos];  }
            value_type* operator->() { return &(*m_ptr)[m_pos]; }

            bool operator==(const iterator& other) const { return m_pos == other.m_pos; }
            bool operator!=(const iterator& other) const { return !(operator==(other)); }

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

            iterator& operator++()    { m_pos++; return *this;                      }
            iterator& operator--()    { m_pos--; return *this;                      }
            iterator  operator++(int) { iterator copy(*this); m_pos++; return copy; }
            iterator  operator--(int) { iterator copy(*this); m_pos--; return copy; }

            iterator operator+(int n)        { iterator copy(*this); return copy += n;        }
            iterator operator-(int n)        { iterator copy(*this); return copy -= n;        }
            iterator operator+(iterator& it) { iterator copy(*this); return copy += it.m_pos; }
            iterator operator-(iterator& it) { iterator copy(*this); return copy -= it.m_pos; }

            iterator& operator+=(int n) { m_pos += n; return *this; }
            iterator& operator-=(int n) { m_pos -= n; return *this; }

            value_type& operator[](size_type n) { return (*m_ptr)[m_pos + n]; }

            // tmp
            iterator(Vector* ptr, size_type pos) : m_ptr(ptr), m_pos(pos) {}
        protected:

            Vector*   m_ptr;
            size_type m_pos;
        };

        class const_iterator : public iterator
        {
            // const value_type& operator*()  { return m_ptr[m_pos]; }
            // const value_type& operator->() { return m_ptr[m_pos]; }
        };

        typedef ReverseIterator<iterator>                reverse_iterator;
        typedef ReverseIterator<const_iterator>          const_reverse_iterator;

        explicit Vector(const allocator_type& alloc = allocator_type())
            : m_under(new value_type[0]), m_size(0), m_capacity(0), m_alloc(alloc)
        {}

        explicit Vector(size_type n,
                        const value_type& val = value_type(),
                        const allocator_type& alloc = allocator_type())
            : m_under(new value_type[n]), m_size(n), m_capacity(n), m_alloc(alloc)
        {
            for (size_type i = 0; i < n; i++)
                m_under[i] = val;
        }

        template <typename InputIterator>
        Vector (InputIterator first,
                InputIterator last,
                const allocator_type& alloc = allocator_type())
            : m_under(new value_type[0]), m_size(0), m_capacity(0), m_alloc(alloc)
        {
            for (; first != last; ++first)
                push_back(*first);
        }

        ~Vector() { delete [] m_under; }

        Vector& operator=(const Vector& x)
        {
            if (this == &x)
                return *this;
            delete [] m_under;
            m_capacity = x.m_capacity;
            m_size = x.m_size;
            m_under = new value_type[m_capacity];
            for (size_type i = 0; i < m_size; i++)
                m_under[i] = x.m_under[i];
            return *this;
        }

        Vector (const Vector& x)
            : m_under(new value_type[x.m_capacity]),
              m_size(x.m_size),
              m_capacity(x.m_capacity),
              m_alloc(x.m_alloc)
        {
            for (size_type i = 0; i < m_size; i++)
                m_under[i] = x.m_under[i];
        }

        iterator               begin()        { return iterator(this, 0);                 }
        iterator               end()          { return iterator(this, m_size);            }
        const_iterator         begin()  const { return const_iterator(this, 0);           }
        const_iterator         end()    const { return const_iterator(this, m_size);      }
        reverse_iterator       rbegin()       { return reverse_iterator(iterator(this, m_size - 1));       }
        reverse_iterator       rend()         { return reverse_iterator(iterator(this, -1));               }
        const_reverse_iterator rbegin() const { return reverse_iterator(const_iterator(this, m_size - 1)); }
        const_reverse_iterator rend()   const { return reverse_iterator(const_iterator(this, -1));         }

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

        void resize(size_type n, value_type val = value_type())
        {
            if (n == m_size)
                return ;
            if (n > m_size)
            {
                reserve(n);
                for (; m_size < n; m_size++)
                    m_under[m_size] = val;
            }
            else
            {
                value_type* newUnder = new value_type[n];
                m_capacity = n;
                m_size = n;
                for (size_type i = 0; i < m_size; i++)
                    newUnder[i] = m_under[i];
                delete [] m_under;
                m_under = newUnder;
            }
        }

        void reserve(size_type n)
        {
            if (n <= m_capacity)
                return ;
            if (m_capacity < 2)
                m_capacity = 2;
            while (m_capacity < n)
                m_capacity *= FT_VECTOR_GROWTH_FACTOR;
            value_type* newUnder = new value_type[m_capacity];
            for (size_type i = 0; i < m_size; i++)
                newUnder[i] = m_under[i];
            delete [] m_under;
            m_under = newUnder;
        }

        reference       operator[](size_type n)       { return m_under[n]; }
        const_reference operator[](size_type n) const { return m_under[n]; }

        reference at(size_type n)
        {
            if (n >= m_size)
                throw std::out_of_range("vector::_M_range_check");
            return m_under[n];
        }

        const_reference at(size_type n) const
        {
            if (n >= m_size)
                throw std::out_of_range("vector::_M_range_check");
            return m_under[n];
        }

        reference       front()       { return m_under[0];          }
        const_reference front() const { return m_under[0];          }
        reference       back()        { return m_under[m_size - 1]; }
        const_reference back()  const { return m_under[m_size - 1]; }

        template <typename InputIterator>
        void assign(InputIterator first, InputIterator last)
        {
            size_type     count;
            InputIterator copy(first);
            for (count = 0; copy != last; ++copy)
                count++;
            resize(count);
            for (size_type i = 0; first != last; ++first, i++)
                m_under[i] = *first;
        }

        void assign(size_type n, const value_type& val)
        {
            resize(n);
            for (size_type i = 0; i < n; i++)
                m_under[i] = val;
        }

        void push_back(const value_type& val)
        {
            reserve(m_size + 1);
            m_under[m_size] = val;
            m_size++;
        }

        void pop_back()  // call destructor with m_alloc ?
        {
            m_size--;
        }

        iterator insert(iterator position, const value_type& val)
        {
            reverse_iterator rev_position(position);

            if (position == end())
                push_back(val);
            else
            {
                m_size++;
                reserve(m_size);
                for (reverse_iterator it = rbegin(); it != rev_position; ++it)
                    it[0] = it[1];
                *position = val;
            }
            return position;
        }

        void insert(iterator position, size_type n, const value_type& val)
        {
            reserve(m_size + n);
            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);

            for (; position != end(); ++position)
                *position = *(position + 1);
            m_size--;
            return ret;
        }

        iterator erase(iterator first, iterator last)
        {
            size_type i;
            size_type count;
            iterator  copy(first);
            iterator  ret(first);

            for (count = 0; copy != last; ++copy)
                count++;
            for (i = 0; first != last && last + i != end(); ++first, i++)
                *first = *(last + i);
            m_size -= count;
            return ret;
        }

        void swap(Vector& x)
        {
            value_type* tmpUnder = m_under;
            size_type tmpSize = m_size;
            size_type tmpCapacity = m_capacity;

            m_under = x.m_under;
            m_size = x.m_size;
            m_capacity = x.m_capacity;

            x.m_under = tmpUnder;
            x.m_size = tmpSize;
            x.m_capacity = tmpCapacity;
        }

        void clear()
        {
            delete [] m_under;
            m_under = new value_type[0];
            m_size = 0;
            m_capacity = 0;
        }

        bool operator==(const Vector& rhs) const
        {
            if (size() != rhs.size())
                return false;
            for (size_type i = 0; i < size(); i++)
                if (!((*this)[i] == rhs[i]))
                    return false;
            return true;
        }

        bool operator!=(const Vector& rhs) const { return !(*this == rhs); }

        bool operator<(const m_type& rhs) const
        {
            size_type i = 0;
            while (i < size() && i < rhs.size() && (*this)[i] == rhs[i])
                i++;
            if (i == size() && i == rhs.size())
                return false;
            if (i == size() || i == rhs.size())
                return i == size();
            return (*this)[i] < rhs[i];
        }

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


    private:
        value_type* m_under;
        size_type   m_size;
        size_type   m_capacity;
        allocator_type m_alloc;
	};
}

// automatic ?
// template <typename T, typename Alloc>
// void swap(ft::Vector<T, Alloc>& x, ft::Vector<T, Alloc>& y)
// {
//     x.swap(y);
// }

#endif