#pragma once

#include <functional>
#include <memory>
#include <utility>
#include <type_traits>
#include <vector>

namespace fefu
{

    template<typename T>
    class allocator {
    public:
        using size_type = std::size_t;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using const_pointer = const T*;
        using reference = typename std::add_lvalue_reference<T>::type;
        using const_reference = typename std::add_lvalue_reference<const T>::type;
        using value_type = T;

        allocator() noexcept = default;

        allocator(const allocator&) noexcept = default;

        template <class U>
        allocator(const allocator<U>&) noexcept {};

        ~allocator() = default;

        pointer allocate(size_type size) {
            auto p = ::operator new(size * sizeof(value_type));

            return static_cast<pointer>(p);
        };

        void deallocate(pointer p, size_type n) noexcept {
            ::operator delete (p, n);
        };
    private:
    };
    template<typename ValueType>
    class Node {
    public:
        using value_type = ValueType*;
        enum  State
        {
            Empty = 0,
            Full = 1,
            END = 2
        };
        value_type val;
        State state;
    };
    template<typename ValueType>
    class hash_map_iterator {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = ValueType;
        using difference_type = std::ptrdiff_t;
        using reference = ValueType&;
        using pointer = ValueType*;

        template<typename K, typename T,
            typename Hash = std::hash<K>,
            typename Pred = std::equal_to<K>,
            typename Alloc = allocator<std::pair<const K, T>>>
            friend class hash_map;

        //friend class hash_map;
        hash_map_iterator() noexcept = default;
        hash_map_iterator(const hash_map_iterator& other) noexcept : ptr(other.ptr) {};

        reference operator*() const {
            return (*ptr);
        };
        pointer operator->() const {
            return (ptr);
        };

        // prefix ++
        hash_map_iterator& operator++() {
            //hash_map_iterator new_ptr = hash_map_iterator();
            //new_ptr.size = size;
            //new_ptr.set = set;
            //difference_type index = 0;

            //if (size == 0)
            //    throw (std::exception("Hash_mapIsEmpty"));
            //while (set[index] == 0) {
            //    index++;
            //    if (index > size - 1)
            //        throw (std::exception("Overload"));
            //}
            //ptr = ptr[index];
            ptr++;
            return *this;
        };
        // postfix ++
        hash_map_iterator operator++(int) {
            hash_map_iterator new_ptr = hash_map_iterator(*this);
            ptr++;
            return new_ptr;
        };

        friend bool operator==(const hash_map_iterator<ValueType>&, const hash_map_iterator<ValueType>&);
        friend bool operator!=(const hash_map_iterator<ValueType>&, const hash_map_iterator<ValueType>&);
    private:
        hash_map_iterator(Node* _new_ptr): ptr(_new_ptr) {};
        Node* ptr;
    };

    template<typename ValueType>
    class hash_map_const_iterator {
        // Shouldn't give non const references on value
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = ValueType;
        using difference_type = std::ptrdiff_t;
        using reference = const ValueType&;
        using pointer = const ValueType*;

        hash_map_const_iterator() noexcept;
        hash_map_const_iterator(const hash_map_const_iterator& other) noexcept;
        hash_map_const_iterator(const hash_map_iterator<ValueType>& other) noexcept;

        reference operator*() const;
        pointer operator->() const;

        // prefix ++
        hash_map_const_iterator& operator++();
        // postfix ++
        hash_map_const_iterator operator++(int);

        friend bool operator==(const hash_map_const_iterator<ValueType>&, const hash_map_const_iterator<ValueType>&);
        friend bool operator!=(const hash_map_const_iterator<ValueType>&, const hash_map_const_iterator<ValueType>&);
    private:
        hash_map_const_iterator(Node* _new_ptr) : ptr(_new_ptr) {}
        Node* ptr;

    };
    template<typename K, typename T,
        typename Hash = std::hash<K>,
        typename Pred = std::equal_to<K>,
        typename Alloc = allocator<std::pair<const K, T>>>
        class hash_map {
        public:
            using key_type = K;
            using mapped_type = T;
            using hasher = Hash;
            using key_equal = Pred;
            using allocator_type = Alloc;
            using value_type = std::pair<const key_type, mapped_type>;
            using reference = value_type&;
            using const_reference = const value_type&;
            using iterator = hash_map_iterator<value_type>;
            using const_iterator = hash_map_const_iterator<value_type>;
            using size_type = std::size_t;


            /// Default constructor.
            hash_map() = default;

            /**
             *  @brief  Default constructor creates no elements.
             *  @param n  Minimal initial number of buckets.
             */
            explicit hash_map(size_type n) :
                m_data(m_allocator.allocate(n)),
                m_size(n)
            {
                m_node.resize(n + 1);
                for (int i = 0; i < n; i++) {
                    m_node[i].val = m_data + i;
                    m_node[i].state = Empty;
                }
                m_node[n].state = END;
            }


            /**
             *  @brief  Builds an %hash_map from a range.
             *  @param  first  An input iterator.
             *  @param  last  An input iterator.
             *  @param  n  Minimal initial number of buckets.
             *
             *  Create an %hash_map consisting of copies of the elements from
             *  [first,last).  This is linear in N (where N is
             *  distance(first,last)).
             */
            template<typename InputIterator>
            hash_map(InputIterator first, InputIterator last,
                size_type n = 0);

            /// Copy constructor.
            hash_map(const hash_map&) {
                hash_map new_hash;
            };

            /// Move constructor.
            hash_map(hash_map&& x) {
                swap();
            };

            /**
             *  @brief Creates an %hash_map with no elements.
             *  @param a An allocator object.
             */
            explicit hash_map(const allocator_type& a);

            /*
            *  @brief Copy constructor with allocator argument.
            * @param  uset  Input %hash_map to copy.
            * @param  a  An allocator object.
            */
            hash_map(const hash_map& umap,
                const allocator_type& a);

            /*
            *  @brief  Move constructor with allocator argument.
            *  @param  uset Input %hash_map to move.
            *  @param  a    An allocator object.
            */
            hash_map(hash_map&& umap,
                const allocator_type& a);

            /**
             *  @brief  Builds an %hash_map from an initializer_list.
             *  @param  l  An initializer_list.
             *  @param n  Minimal initial number of buckets.
             *
             *  Create an %hash_map consisting of copies of the elements in the
             *  list. This is linear in N (where N is @a l.size()).
             */
            hash_map(std::initializer_list<value_type> l,
                size_type n = 0);

            /// Copy assignment operator.
            hash_map& operator=(const hash_map&);

            /// Move assignment operator.
            hash_map& operator=(hash_map&&);

            /**
             *  @brief  %hash_map list assignment operator.
             *  @param  l  An initializer_list.
             *
             *  This function fills an %hash_map with copies of the elements in
             *  the initializer list @a l.
             *
             *  Note that the assignment completely changes the %hash_map and
             *  that the resulting %hash_map's size is the same as the number
             *  of elements assigned.
             */
            hash_map& operator=(std::initializer_list<value_type> l);

            ///  Returns the allocator object used by the %hash_map.
            allocator_type get_allocator() const noexcept;

            // size and capacity:

            ///  Returns true if the %hash_map is empty.
            bool empty() const noexcept {
                if (m_size == 0)
                    return true;
                return false;
            };

            ///  Returns the size of the %hash_map.
            size_type size() const noexcept;

            ///  Returns the maximum size of the %hash_map.
            size_type max_size() const noexcept;

            // iterators.

            /**
             *  Returns a read/write iterator that points to the first element in the
             *  %hash_map.
             */
            iterator begin() noexcept {
                iterator ptr(&m_node[0]);
                return ptr;
            };

            //@{
            /**
             *  Returns a read-only (constant) iterator that points to the first
             *  element in the %hash_map.
             */
            const_iterator begin() const noexcept {
                const_iterator ptr(&m_node[0]);
                return ptr;
            };

            const_iterator cbegin() const noexcept;

            /**
             *  Returns a read/write iterator that points one past the last element in
             *  the %hash_map.
             */
            iterator end() noexcept;

            //@{
            /**
             *  Returns a read-only (constant) iterator that points one past the last
             *  element in the %hash_map.
             */
            const_iterator end() const noexcept;

            const_iterator cend() const noexcept;
            //@}

            // modifiers.

            /**
             *  @brief Attempts to build and insert a std::pair into the
             *  %hash_map.
             *
             *  @param args  Arguments used to generate a new pair instance (see
             *          std::piecewise_contruct for passing arguments to each
            *           part of the pair constructor).
            *
            *  @return  A pair, of which the first element is an iterator that points
            *           to the possibly inserted pair, and the second is a bool that
            *           is true if the pair was actually inserted.
            *
            *  This function attempts to build and insert a (key, value) %pair into
            *  the %hash_map.
            *  An %hash_map relies on unique keys and thus a %pair is only
            *  inserted if its first element (the key) is not already present in the
            *  %hash_map.
            *
            *  Insertion requires amortized constant time.
            */
            template<typename... _Args>
            std::pair<iterator, bool> emplace(_Args&&... args);

            /**
             *  @brief Attempts to build and insert a std::pair into the
             *  %hash_map.
             *
             *  @param  pos  An iterator that serves as a hint as to where the pair
             *                should be inserted.
             *  @param  args  Arguments used to generate a new pair instance (see
             *           std::piecewise_contruct for passing arguments to each
            *            part of the pair constructor).
            *  @return An iterator that points to the element with key of the
            *          std::pair built from @a args (may or may not be that
            *          std::pair).
            *
            *  This function is not concerned about whether the insertion took place,
            *  and thus does not return a boolean like the single-argument emplace()
            *  does.
            *  Note that the first parameter is only a hint and can potentially
            *  improve the performance of the insertion process. A bad hint would
            *  cause no gains in efficiency.
            *
            *  See
            *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
            *  for more on @a hinting.
            *
            *  Insertion requires amortized constant time.
            */
            template<typename... _Args>
            iterator emplace_hint(const_iterator pos, _Args&&... args);

            /**
             *  @brief Attempts to build and insert a std::pair into the
             *  %hash_map.
             *
             *  @param k    Key to use for finding a possibly existing pair in
             *                the hash_map.
             *  @param args  Arguments used to generate the .second for a
             *                new pair instance.
             *
             *  @return  A pair, of which the first element is an iterator that points
             *           to the possibly inserted pair, and the second is a bool that
             *           is true if the pair was actually inserted.
             *
             *  This function attempts to build and insert a (key, value) %pair into
             *  the %hash_map.
             *  An %hash_map relies on unique keys and thus a %pair is only
             *  inserted if its first element (the key) is not already present in the
             *  %hash_map.
             *  If a %pair is not inserted, this function has no effect.
             *
             *  Insertion requires amortized constant time.
             */
            template <typename... _Args>
            std::pair<iterator, bool> try_emplace(const key_type& k, _Args&&... args) {
                insert({ k, mapped_type(std::forward<_Args>(args)...) });
            }
            // move-capable overload
            template <typename... _Args>
            std::pair<iterator, bool> try_emplace(key_type&& k, _Args&&... args) {
                insert({ std::move(k), mapped_type(std::forward<_Args>(args)...) });
            }
            /**
             *  @brief Attempts to build and insert a std::pair into the
             *  %hash_map.
             *
             *  @param  hint  An iterator that serves as a hint as to where the pair
             *                should be inserted.
             *  @param k    Key to use for finding a possibly existing pair in
             *                the hash_map.
             *  @param args  Arguments used to generate the .second for a
             *                new pair instance.
             *  @return An iterator that points to the element with key of the
             *          std::pair built from @a args (may or may not be that
             *          std::pair).
             *
             *  This function is not concerned about whether the insertion took place,
             *  and thus does not return a boolean like the single-argument emplace()
             *  does. However, if insertion did not take place,
             *  this function has no effect.
             *  Note that the first parameter is only a hint and can potentially
             *  improve the performance of the insertion process. A bad hint would
             *  cause no gains in efficiency.
             *
             *  See
             *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
             *  for more on @a hinting.
             *
             *  Insertion requires amortized constant time.
             */
            template <typename... _Args>
            iterator try_emplace(const_iterator hint, const key_type& k,
                _Args&&... args);

            // move-capable overload
            template <typename... _Args>
            iterator try_emplace(const_iterator hint, key_type&& k, _Args&&... args);

            //@{
            /**
             *  @brief Attempts to insert a std::pair into the %hash_map.
             *  @param x Pair to be inserted (see std::make_pair for easy
             *       creation of pairs).
            *
            *  @return  A pair, of which the first element is an iterator that
            *           points to the possibly inserted pair, and the second is
            *           a bool that is true if the pair was actually inserted.
            *
            *  This function attempts to insert a (key, value) %pair into the
            *  %hash_map. An %hash_map relies on unique keys and thus a
            *  %pair is only inserted if its first element (the key) is not already
            *  present in the %hash_map.
            *
            *  Insertion requires amortized constant time.
            */
            std::pair<iterator, bool> insert(const value_type& x);

            std::pair<iterator, bool> insert(value_type&& x);

            //@}

            //@{
            /**
             *  @brief Attempts to insert a std::pair into the %hash_map.
             *  @param  hint  An iterator that serves as a hint as to where the
             *                 pair should be inserted.
             *  @param  x  Pair to be inserted (see std::make_pair for easy creation
             *               of pairs).
             *  @return An iterator that points to the element with key of
             *           @a x (may or may not be the %pair passed in).
             *
             *  This function is not concerned about whether the insertion took place,
             *  and thus does not return a boolean like the single-argument insert()
             *  does.  Note that the first parameter is only a hint and can
             *  potentially improve the performance of the insertion process.  A bad
             *  hint would cause no gains in efficiency.
             *
             *  See
             *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
             *  for more on @a hinting.
             *
             *  Insertion requires amortized constant time.
             */
            iterator insert(const_iterator hint, const value_type& x);

            iterator insert(const_iterator hint, value_type&& x);

            //@}

            /**
             *  @brief A template function that attempts to insert a range of
             *  elements.
             *  @param  first  Iterator pointing to the start of the range to be
             *                   inserted.
             *  @param  last  Iterator pointing to the end of the range.
             *
             *  Complexity similar to that of the range constructor.
             */
            template<typename _InputIterator>
            void insert(_InputIterator first, _InputIterator last);

            /**
             *  @brief Attempts to insert a list of elements into the %hash_map.
             *  @param  l  A std::initializer_list<value_type> of elements
             *               to be inserted.
             *
             *  Complexity similar to that of the range constructor.
             */
            void insert(std::initializer_list<value_type> l);


            /**
             *  @brief Attempts to insert a std::pair into the %hash_map.
             *  @param k    Key to use for finding a possibly existing pair in
             *                the map.
             *  @param obj  Argument used to generate the .second for a pair
             *                instance.
             *
             *  @return  A pair, of which the first element is an iterator that
             *           points to the possibly inserted pair, and the second is
             *           a bool that is true if the pair was actually inserted.
             *
             *  This function attempts to insert a (key, value) %pair into the
             *  %hash_map. An %hash_map relies on unique keys and thus a
             *  %pair is only inserted if its first element (the key) is not already
             *  present in the %hash_map.
             *  If the %pair was already in the %hash_map, the .second of
             *  the %pair is assigned from obj.
             *
             *  Insertion requires amortized constant time.
             */
            template <typename _Obj>
            std::pair<iterator, bool> insert_or_assign(const key_type& k, _Obj&& obj);

            // move-capable overload
            template <typename _Obj>
            std::pair<iterator, bool> insert_or_assign(key_type&& k, _Obj&& obj);

            /**
             *  @brief Attempts to insert a std::pair into the %hash_map.
             *  @param  hint  An iterator that serves as a hint as to where the
             *                  pair should be inserted.
             *  @param k    Key to use for finding a possibly existing pair in
             *                the hash_map.
             *  @param obj  Argument used to generate the .second for a pair
             *                instance.
             *  @return An iterator that points to the element with key of
             *           @a x (may or may not be the %pair passed in).
             *
             *  This function is not concerned about whether the insertion took place,
             *  and thus does not return a boolean like the single-argument insert()
             *  does.
             *  If the %pair was already in the %unordered map, the .second of
             *  the %pair is assigned from obj.
             *  Note that the first parameter is only a hint and can
             *  potentially improve the performance of the insertion process.  A bad
             *  hint would cause no gains in efficiency.
             *
             *  See
             *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
             *  for more on @a hinting.
             *
             *  Insertion requires amortized constant time.
             */
            template <typename _Obj>
            iterator insert_or_assign(const_iterator hint, const key_type& k,
                _Obj&& obj);

            // move-capable overload
            template <typename _Obj>
            iterator insert_or_assign(const_iterator hint, key_type&& k, _Obj&& obj);

            //@{
            /**
             *  @brief Erases an element from an %hash_map.
             *  @param  position  An iterator pointing to the element to be erased.
             *  @return An iterator pointing to the element immediately following
             *          @a position prior to the element being erased. If no such
             *          element exists, end() is returned.
             *
             *  This function erases an element, pointed to by the given iterator,
             *  from an %hash_map.
             *  Note that this function only erases the element, and that if the
             *  element is itself a pointer, the pointed-to memory is not touched in
             *  any way.  Managing the pointer is the user's responsibility.
             */
            iterator erase(const_iterator position);

            // LWG 2059.
            iterator erase(iterator position);
            //@}

            /**
             *  @brief Erases elements according to the provided key.
             *  @param  x  Key of element to be erased.
             *  @return  The number of elements erased.
             *
             *  This function erases all the elements located by the given key from
             *  an %hash_map. For an %hash_map the result of this function
             *  can only be 0 (not present) or 1 (present).
             *  Note that this function only erases the element, and that if the
             *  element is itself a pointer, the pointed-to memory is not touched in
             *  any way.  Managing the pointer is the user's responsibility.
             */
            size_type erase(const key_type& x);

            /**
             *  @brief Erases a [first,last) range of elements from an
             *  %hash_map.
             *  @param  first  Iterator pointing to the start of the range to be
             *                  erased.
             *  @param last  Iterator pointing to the end of the range to
             *                be erased.
             *  @return The iterator @a last.
             *
             *  This function erases a sequence of elements from an %hash_map.
             *  Note that this function only erases the elements, and that if
             *  the element is itself a pointer, the pointed-to memory is not touched
             *  in any way.  Managing the pointer is the user's responsibility.
             */
            iterator erase(const_iterator first, const_iterator last);

            /**
             *  Erases all elements in an %hash_map.
             *  Note that this function only erases the elements, and that if the
             *  elements themselves are pointers, the pointed-to memory is not touched
             *  in any way.  Managing the pointer is the user's responsibility.
             */
            void clear() noexcept;

            /**
             *  @brief  Swaps data with another %hash_map.
             *  @param  x  An %hash_map of the same element and allocator
             *  types.
             *
             *  This exchanges the elements between two %hash_map in constant
             *  time.
             *  Note that the global std::swap() function is specialized such that
             *  std::swap(m1,m2) will feed to this function.
             */
            void swap(hash_map& x);

            template<typename _H2, typename _P2>
            void merge(hash_map<K, T, _H2, _P2, Alloc>& source);

            template<typename _H2, typename _P2>
            void merge(hash_map<K, T, _H2, _P2, Alloc>&& source);

            // observers.

            ///  Returns the hash functor object with which the %hash_map was
            ///  constructed.
            Hash hash_function() const;

            ///  Returns the key comparison object with which the %hash_map was
            ///  constructed.
            Pred key_eq() const;

            // lookup.

            //@{
            /**
             *  @brief Tries to locate an element in an %hash_map.
             *  @param  x  Key to be located.
             *  @return  Iterator pointing to sought-after element, or end() if not
             *           found.
             *
             *  This function takes a key and tries to locate the element with which
             *  the key matches.  If successful the function returns an iterator
             *  pointing to the sought after element.  If unsuccessful it returns the
             *  past-the-end ( @c end() ) iterator.
             */
            iterator find(const key_type& x);

            const_iterator find(const key_type& x) const;
            //@}

            /**
             *  @brief  Finds the number of elements.
             *  @param  x  Key to count.
             *  @return  Number of elements with specified key.
             *
             *  This function only makes sense for %unordered_multimap; for
             *  %hash_map the result will either be 0 (not present) or 1
             *  (present).
             */
            size_type count(const key_type& x) const;

            /**
             *  @brief  Finds whether an element with the given key exists.
             *  @param  x  Key of elements to be located.
             *  @return  True if there is any element with the specified key.
             */
            bool contains(const key_type& x) const;

            //@{
            /**
             *  @brief  Subscript ( @c [] ) access to %hash_map data.
             *  @param  k  The key for which data should be retrieved.
             *  @return  A reference to the data of the (key,data) %pair.
             *
             *  Allows for easy lookup with the subscript ( @c [] )operator.  Returns
             *  data associated with the key specified in subscript.  If the key does
             *  not exist, a pair with that key is created using default values, which
             *  is then returned.
             *
             *  Lookup requires constant time.
             */
            mapped_type& operator[](const key_type& k) {
                const size_type n = m_hash(k);
                size_type index = n % m_size;
                size_type count = 0;
                while (m_node[index].state == Full && count != m_size && k != m_data[index].first) {
                    count++;
                    index = (index + 1) % m_size;
                }
                if (m_node[index].state == Full)
                    return m_data[index].second;
                if (m_node[index].state == Empty)
                {
                    new(m_data + index) value_type{ k, mapped_type{} };
                    m_node[index].state = Full;
                    return m_data[index].second;
                }


            };

            mapped_type& operator[](key_type&& k) {
                size_type n = m_hash(k);
                n = 0;
                size_type index = n % m_size;
                size_type count = 0;
                while (m_node[index].state == Full && count != m_size && k != m_data[index].first) {
                    count++;
                    index = (index + 1) % m_size;
                }
                if (m_node[index].state == Full)
                    return m_data[index].second;
                if (m_node[index].state == Empty)
                {
                    //insert(std:move(value_type(std:move(k),0)));
                    new(m_data + index) value_type{ k, mapped_type{} };
                    m_node[index].state = Full;
                    return m_data[index].second;
                }
            };
            //@}

            //@{
            /**
             *  @brief  Access to %hash_map data.
             *  @param  k  The key for which data should be retrieved.
             *  @return  A reference to the data whose key is equal to @a k, if
             *           such a data is present in the %hash_map.
             *  @throw  std::out_of_range  If no such data is present.
             */
            mapped_type& at(const key_type& k);

            const mapped_type& at(const key_type& k) const;
            //@}

            // bucket interface.

            /// Returns the number of buckets of the %hash_map.
            size_type bucket_count() const noexcept;

            /*
            * @brief  Returns the bucket index of a given element.
            * @param  _K  A key instance.
            * @return  The key bucket index.
            */
            size_type bucket(const key_type& _K) const;

            // hash policy.

            /// Returns the average number of elements per bucket.
            float load_factor() const noexcept;

            /// Returns a positive number that the %hash_map tries to keep the
            /// load factor less than or equal to.
            float max_load_factor() const noexcept;

            /**
             *  @brief  Change the %hash_map maximum load factor.
             *  @param  z The new maximum load factor.
             */
            void max_load_factor(float z);

            /**
             *  @brief  May rehash the %hash_map.
             *  @param  n The new number of buckets.
             *
             *  Rehash will occur only if the new number of buckets respect the
             *  %hash_map maximum load factor.
             */
            void rehash(size_type n);

            /**
             *  @brief  Prepare the %hash_map for a specified number of
             *          elements.
             *  @param  n Number of elements required.
             *
             *  Same as rehash(ceil(n / max_load_factor())).
             */
            void reserve(size_type n);

            bool operator==(const hash_map& other) const;
        private:
            allocator_type m_allocator;
            key_equal m_key_equal;
            hasher m_hash;
            std::vector<Node> m_node;
            value_type* m_data;
            std::vector<char> m_set;
            size_type m_size;

    };


} // namespace fefu