// Copyright (C) 2015 ChaosForge Ltd
// http://chaosforge.org/
//
// This file is part of Nova libraries. 
// For conditions of distribution and use, see copying.txt file in root folder.

/**
 * @file unordered_map.hh
 * @author Kornel Kisielewicz epyon@chaosforge.org
 * @brief unordered_map
 */

#ifndef NV_STL_UNORDERED_MAP_HH
#define NV_STL_UNORDERED_MAP_HH

#include <nv/common.hh>
#include <nv/stl/container/hash_table.hh>
#include <nv/stl/utility/pair.hh>
#include <nv/stl/functional/hash.hh>
#include <nv/stl/functional/comparisons.hh>
#include <nv/stl/memory.hh>

namespace nv
{

	template <
		typename T,
		typename IsEqual = equal_to<T>,
		bool IsEmpty = is_empty< IsEqual >::value
	>
	struct compare_policy;


	template < typename T >
	struct compare_policy< T, equal_to<T>, true >
	{
		constexpr bool compare( const T& t1, const T& t2 ) const
		{
			return t1 == t2;
		}
		equal_to<T> key_eq() const { return equal_to<T>(); }
	};

	template < typename T, typename IsEqual >
	struct compare_policy< T, IsEqual, true > : private IsEqual
	{
		constexpr bool compare( const T& t1, const T& t2 ) const
	{
		return ( *this )( t1 == t2 );
	}
	IsEqual key_eq() const { return ( *this ); }
	};

	template < typename T, typename IsEqual >
	struct compare_policy< T, IsEqual, false >
	{
		constexpr bool compare( const T& t1, const T& t2 ) const
		{
			return m_key_eq( t1 == t2 );
		}
		IsEqual key_eq() const { return m_key_eq; }
	private:
		IsEqual m_key_eq;
	};

	template <
		typename T,
		typename H,
		typename Hasher = hash< T, H >,
		bool IsEmpty = is_empty< Hasher >::value
	>
	struct hash_policy;


	template < typename T, typename H >
	struct hash_policy< T, H, hash< T, H >, true >
	{
		constexpr H get_hash( const T& t ) const
		{
			return hash< T, H >::get( t );
		}
		hash< T, H > hash_function() const { return hash< T, H >(); }
	};

	template < typename T, typename H, typename Hasher >
	struct hash_policy< T, H, Hasher, true > : private Hasher
	{
		constexpr H get_hash( const T& t ) const
	{
		return ( *this )( t );
	}
	hash< T, H > hash_function() const { return ( *this ); }
	};

	template < typename T, typename H, typename Hasher >
	struct hash_policy< T, H, Hasher, false >
	{
		constexpr H get_hash( const T& t ) const
		{
			return m_hasher( t );
		}
		hash< T, H > hash_function() const { return m_hasher; }
	private:
		Hasher m_hasher;
	};

	// Due to MSVC not being able to handle multiple empty bases, if both
	// hash and compare are empty, we will still get a 4-size structure.
	// We will optimize here, to assure that if either is empty, we will still
	// get an empty class
	template <
		typename T,
		typename H,
		typename IsEqual = equal_to< T >,
		typename Hasher = hash< T, H >,
		bool IsEqualIsEmpty = is_empty< IsEqual >::value,
		bool HasherIsEmpty = is_empty< Hasher >::value
	>
	struct hash_compare_policy;

	template <
		typename T,
		typename H,
		typename IsEqual,
		typename Hasher,
		bool HasherIsEmpty
	>
	struct hash_compare_policy< T, H, IsEqual, Hasher, false, HasherIsEmpty >
		: hash_policy< T, H, Hasher, HasherIsEmpty >
	{
		constexpr bool compare( const T& t1, const T& t2 ) const
	{
		return m_key_eq( t1 == t2 );
	}
	IsEqual key_eq() const { return m_key_eq; }
	private:
		IsEqual m_key_eq;
	};

	template <
		typename T,
		typename H,
		typename IsEqual,
		typename Hasher
	>
	struct hash_compare_policy< T, H, IsEqual, Hasher, true, false >
		: compare_policy< T, IsEqual, true >
	{
		constexpr H get_hash( const T& t ) const
	{
		return m_hasher( t );
	}
	hash< T, H > hash_function() const { return m_hasher; }
	private:
		Hasher m_hasher;
	};

	template <
		typename T,
		typename H,
		typename Hasher,
		typename IsEqual
	>
	struct hash_compare_policy< T, H, IsEqual, Hasher, true, true >
		: hash_policy< T, H, Hasher, true >
	{
		constexpr bool compare( const T& t1, const T& t2 ) const
	{
		static_assert( is_trivial< IsEqual >::value, "There is something really wrong with your equality functor." );
		return IsEqual()( t1, t2 );
	}
	IsEqual key_eq() const { return IsEqual(); }
	};

	template <
		typename Key,
		typename Value,
		typename Hash,
		typename IsEqual = equal_to< Key >,
		typename Hasher = hash< Key, Hash >
	>
	struct hash_table_stl_map_policy : hash_compare_policy< Key, Hash, IsEqual, Hasher >
	{
		typedef hash_compare_policy< Key, Hash, IsEqual, Hasher >    base_type;

		typedef hash_table_standard_entry< Key, Value, Hash, false > entry_type;
		typedef typename entry_type::key_type    key_type;
		typedef typename entry_type::mapped_type mapped_type;
		typedef typename entry_type::hash_type   hash_type;
		typedef typename entry_type::value_type  value_type;
		typedef Key                              query_type;

		constexpr bool entry_compare( const entry_type* entry, hash_type, const query_type& key ) const
		{
			return base_type::compare( entry_type::get_key( entry ), key );
		}

		constexpr bool entry_compare( const entry_type* entry, hash_type, const value_type& value ) const
		{
			return base_type::compare( entry_type::get_key( entry ), entry_type::get_key( value ) );
		}

		template < typename... Args >
		static void entry_construct( entry_type* entry, hash_type, Args&&... params )
		{
			construct_object( entry_type::get_value( entry ), ::nv::forward<Args>( params )... );
		}

		static void entry_destroy( entry_type* entry )
		{
			destroy_object( entry_type::get_value( entry ) );
		}

		constexpr hash_type get_entry_hash( const entry_type* entry ) const
		{
			return base_type::get_hash( entry_type::get_key( entry ) );
		}
		constexpr hash_type get_value_hash( const value_type& value ) const
		{
			return base_type::get_hash( entry_type::get_key( value ) );
		}
	};

	template <
		typename Key, 
		typename T,
		typename Hash = hash< Key >,
		typename KeyEqual = equal_to< Key >,
		typename HashEntryPolicy = hash_table_stl_map_policy< Key, T, typename Hash::result_type, KeyEqual, Hash >
	>
	class unordered_map
		: public hash_table< 
			HashEntryPolicy,
			hash_table_no_extra_types_policy,
			hash_table_prime_rehash_policy,
			HashEntryPolicy
		>
	{
	public:
		typedef hash_table< 
			HashEntryPolicy,
			hash_table_no_extra_types_policy,
			hash_table_prime_rehash_policy,
			HashEntryPolicy
		> base_type;
		typedef typename base_type::value_type                                           value_type;
		typedef typename base_type::pointer                                              pointer;
		typedef typename base_type::const_pointer                                        const_pointer;
		typedef typename base_type::reference                                            reference;
		typedef typename base_type::const_reference                                      const_reference;
		typedef typename base_type::iterator                                             iterator;
		typedef typename base_type::const_iterator                                       const_iterator;
		typedef typename base_type::size_type                                            size_type;
		typedef typename base_type::difference_type                                      difference_type;
		typedef typename base_type::key_type                                             key_type;
		typedef typename base_type::mapped_type                                          mapped_type;
		typedef typename base_type::node_type                                            node_type;
		typedef typename base_type::insert_return_type                                   insert_return_type;
		typedef Hash                                                                     hasher;
		typedef KeyEqual                                                                 key_equal;

		using base_type::base_type;

		mapped_type& operator[]( const key_type& key )
		{
			return ( *base_type::insert_key( key ).first ).second;
		}

		mapped_type& at( const key_type& key )
		{
			iterator it = base_type::find( key );
			NV_ASSERT_ALWAYS( it != base_type::end(), "Key not found in map!" );
			return *it;
		}

		const mapped_type& at( const key_type& key ) const
		{
			const_iterator it = base_type::find( key );
			NV_ASSERT_ALWAYS( it != base_type::cend(), "Key not found in map!" );
			return *it;
		}

		size_type count( const key_type& key ) const
		{
			return base_type::find( key ) == base_type::cend() ? 0 : 1;
		}

		pair<iterator, iterator> equal_range( const key_type& key ) 
		{
			iterator it = base_type::find( key );
			return pair<iterator, iterator>( it, it == base_type::end() ? it : ++it );
		}

		pair<const_iterator, const_iterator> equal_range( const key_type& key ) const
		{
			const_iterator it = base_type::find( key );
			return pair<const_iterator, const_iterator>( it, it == base_type::cend() ? it : ++it );
		}

		using base_type::insert;

		template < typename M >
		insert_return_type insert_or_assign( const key_type& k, M&& obj )
		{
			insert_return_type result = base_type::try_insert( k, nv::forward<M>( obj ) );
			if ( !result.second ) result.first->second = obj;
			return result;
		}

		template < typename M >
		insert_return_type insert_or_assign( key_type&& k, M&& obj )
		{
			insert_return_type result = base_type::try_insert( nv::forward<key_type>( k ), nv::forward<M>( obj ) );
			if ( !result.second ) result.first->second = obj;
			return result;
		}

		// STL compatibility only, hint unused
		iterator insert( const_iterator, const value_type& value )
		{
			return base_type::insert( value ).first;
		}

	};

	// TODO: remove and make a proper hashed map
	template <
		typename Key,
		typename T,
		typename Hasher = hash< Key, typename Key::value_type >,
		typename KeyEqual = equal_to< Key >,
		typename HashEntryPolicy = hash_table_stl_map_policy< Key, T, typename Key::value_type, KeyEqual, Hasher >
	>
	class hashed_table
		: public hash_table<
		HashEntryPolicy,
		hash_table_no_extra_types_policy,
		hash_table_prime_rehash_policy,
		HashEntryPolicy
		>
	{
	public:
		typedef hash_table<
			HashEntryPolicy,
			hash_table_no_extra_types_policy,
			hash_table_prime_rehash_policy,
			HashEntryPolicy
		> base_type;
		typedef typename base_type::value_type                                           value_type;
		typedef typename base_type::pointer                                              pointer;
		typedef typename base_type::const_pointer                                        const_pointer;
		typedef typename base_type::reference                                            reference;
		typedef typename base_type::const_reference                                      const_reference;
		typedef typename base_type::iterator                                             iterator;
		typedef typename base_type::const_iterator                                       const_iterator;
		typedef typename base_type::size_type                                            size_type;
		typedef typename base_type::difference_type                                      difference_type;
		typedef typename base_type::key_type                                             key_type;
		typedef typename base_type::mapped_type                                          mapped_type;
		typedef typename base_type::node_type                                            node_type;
		typedef typename base_type::insert_return_type                                   insert_return_type;
		typedef Hasher                                                                   hasher;
		typedef KeyEqual                                                                 key_equal;

		using base_type::base_type;

		mapped_type& operator[]( const key_type& key )
		{
			return ( *base_type::insert_key( key ).first ).second;
		}
	};


}

#endif // NV_STL_UNORDERED_MAP_HH