// Copyright (C) 2014 ChaosForge Ltd
// http://chaosforge.org/
//
// This file is part of NV Libraries.
// For conditions of distribution and use, see copyright notice in nv.hh

/**
 * @file handle.hh
 * @author Kornel Kisielewicz
 */

#ifndef NV_CORE_HANDLE_HH
#define NV_CORE_HANDLE_HH

#include <nv/core/common.hh>
#include <nv/core/array.hh>

namespace nv
{

	template < 
		typename T = uint32, 
		unsigned IBITS = 16,
		unsigned CBITS = 16,
		typename TAG = void 
	>
	class handle
	{
	public:
		typedef T value_type;
		static const int INDEX_BITS   = IBITS;
		static const int COUNTER_BITS = IBITS;
		static const T MAX_INDEX   = (1 << IBITS) - 1;
		static const T MAX_COUNTER = (1 << CBITS) - 1;

		handle() : m_index(0), m_counter(0) {}

		inline bool operator==(const handle& rhs) const {return m_index == rhs.m_index && m_counter == rhs.m_counter; }
		inline bool operator!=(const handle& rhs) const {return !(*this == rhs);}

		bool is_nil() const { return m_index == 0 && m_counter == 0; }
		bool is_valid() const { return !is_nil(); }
		T index() const { return m_index; }
		size_t hash() const { return std::hash<T>()( m_counter << IBITS | m_index ); }
	protected:
		T m_index   : IBITS;
		T m_counter : CBITS;

		handle( T a_index, T a_counter ) : m_index( a_index ), m_counter( a_counter ) {}
		template < typename H, typename I >
		friend class index_store;
	};



	template < typename HANDLE, typename TINDEX = sint32 >
	class index_store
	{
	public:
		typedef HANDLE handle;
		typedef TINDEX index_type;
		typedef typename HANDLE::value_type value_type;

		index_store() : m_first_free(-1), m_last_free(-1) {}

		handle create_handle( index_type index )
		{
			value_type i       = get_free_entry();
			m_entries[i].index = index;
			m_entries[i].counter++;
			return handle( i, m_entries[i].counter );
		}

		void free_handle( handle h )
		{
			m_entries[ h.m_index ].index     = -1;
			m_entries[ h.m_index ].next_free = -1;
			if ( m_last_free == -1 )
			{
				m_first_free = m_last_free = h.m_index;
				return;
			}
			m_entries[ m_last_free ].next_free = h.m_index;
			m_last_free = h.m_index;
		}

		void swap_indices( handle h1, handle h2 )
		{
			std::swap( m_entries[ h1.m_index ].index, m_entries[ h2.m_index ].index );
		}

		sint32 get_index( handle h ) const
		{
			return m_entries[ h.m_index ].counter == h.m_counter ? m_entries[ h.m_index ].index : -1;
		}
	private:
		struct index_entry
		{
			index_type index;
			value_type counter;
			index_type next_free;

			index_entry() : index(0), counter(0), next_free(-1) {}
		};

		value_type get_free_entry()
		{
			if ( m_first_free != -1 )
			{
				value_type result = (value_type)m_first_free;
				m_first_free = m_entries[result].next_free;
				m_entries[result].next_free = -1;
				if ( m_first_free == -1 ) m_last_free = -1;
				return result;
			}
			m_entries.emplace_back();
			return value_type( m_entries.size() - 1 );
		}

		index_type m_first_free;
		index_type m_last_free;
		std::vector< index_entry > m_entries;
	};

	template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
	class packed_indexed_array
	{
	public:
		typedef HANDLE                   handle;
		typedef TINDEX                   index_type;
		typedef std::vector< T >         storage;
		typedef T                        value_type;
		typedef typename storage::iterator        iterator;
		typedef typename storage::const_iterator  const_iterator;
		typedef typename storage::reference       reference;
		typedef typename storage::const_reference const_reference;

		packed_indexed_array() {}
		packed_indexed_array( uint32 reserve )
		{
			m_data.reserve( reserve );
			m_indexes.reserve( reserve );
		}

		T* insert( handle h )
		{
			resize_indexes_to( h.index() );
			m_indexes[ h.index() ] = m_data.size();
			m_handles.push_back( h );
			m_data.emplace_back();
			return &(m_data.back());
		}

		bool exists( handle h )
		{
			if ( h.is_nil() || h.index() >= m_indexes.size() ) return false;
			return m_indexes[ h.index() ] >= 0;		
		}

		T* get( handle h )
		{
			if ( h.is_nil() || h.index() >= m_indexes.size() ) return nullptr;
			index_type i = m_indexes[ h.index() ];
			return i >= 0 ? &(m_data[ i ]) : nullptr;
		}

		void remove( handle h )
		{
			handle swap_handle    = m_handles.back();
			sint32 dead_eindex    = m_indexes[ h.index() ];
			if ( dead_eindex != (sint32)m_data.size()-1 )
			{
				m_data[ dead_eindex ]            = m_data.back();
				m_handles[ dead_eindex ]         = swap_handle;
				m_indexes[ swap_handle.index() ] = dead_eindex;
			}
			m_data.pop_back();
			m_handles.pop_back();
			m_indexes[ h.index() ] = -1;
		}

		void clear()
		{
			m_data.clear();
			m_handles.clear();
			m_indexes.clear();
		}

		const value_type& operator[] ( index_type i ) const { return m_data[i]; }
		value_type& operator[] ( index_type i ) { return m_data[i]; }
		size_t size() const { return m_data.size(); }

		iterator        begin()        { return m_data.begin(); }
		const_iterator  begin()  const { return m_data.cbegin(); }
		const_iterator  cbegin() const { return m_data.cbegin(); }

		iterator        end()        { return m_data.end(); }
		const_iterator  end()  const { return m_data.cend(); }
		const_iterator  cend() const { return m_data.cend(); }

	private:
		void resize_indexes_to( index_type i )
		{
			index_type size = (index_type)m_indexes.size();
			if ( i >= size )
			{
				if ( size == 0 ) size = 1;
				while ( i >= size ) size = size * 2;
				m_indexes.resize( size, -1 );
			}
		}

		std::vector< T >          m_data;
		std::vector< handle >     m_handles;
		std::vector< index_type > m_indexes;
	};


	template < typename T, typename HANDLE = handle<>, typename TINDEX = sint32 >
	class entity_store
	{
	public:
		typedef HANDLE                   handle;
		typedef TINDEX                   index_type;
		typedef std::vector< T >         storage;
		typedef T                        value_type;
		typedef typename storage::iterator        iterator;
		typedef typename storage::const_iterator  const_iterator;
		typedef typename storage::reference       reference;
		typedef typename storage::const_reference const_reference;

		entity_store() {}

		explicit entity_store( uint32 reserve )
		{
			m_handles.reserve( reserve );
			m_data.reserve( reserve );
		}

		handle create()
		{
			m_data.emplace_back();
			m_handles.push_back( m_indexes.create_handle( sint32( m_data.size() - 1 ) ) );
			return m_handles.back();
		}

		const value_type* get( handle h ) const
		{
			if ( h.is_nil() ) return nullptr;
			sint32 eindex = m_indexes.get_index( h );
			return eindex >= 0 ? &(m_data[ eindex ]) : nullptr;
		}

		value_type* get( handle h )
		{
			if ( h.is_nil() ) return nullptr;
			sint32 eindex = m_indexes.get_index( h );
			return eindex >= 0 ? &(m_data[ eindex ]) : nullptr;
		}

		void destroy( handle e )
		{
			handle swap_handle    = m_handles.back();
			sint32 dead_eindex    = m_indexes.get_index( e );
			if ( dead_eindex != (sint32)m_data.size()-1 )
			{
				m_data[ dead_eindex ]    = m_data.back();
				m_handles[ dead_eindex ] = m_handles.back();
			}
			m_data.pop_back();
			m_handles.pop_back();
			m_indexes.swap_indices( e, swap_handle );
			m_indexes.free_handle( e );
		}

		handle get_handle( index_type i ) const { return m_handles[i]; }
		const value_type& operator[] ( index_type i ) const { return m_data[i]; }
		value_type& operator[] ( index_type i ) { return m_data[i]; }
		size_t size() const { return m_data.size(); }

		iterator        begin()        { return m_data.begin(); }
		const_iterator  begin()  const { return m_data.cbegin(); }
		const_iterator  cbegin() const { return m_data.cbegin(); }

		iterator        end()        { return m_data.end(); }
		const_iterator  end()  const { return m_data.cend(); }
		const_iterator  cend() const { return m_data.cend(); }

	private:
		std::vector< handle >         m_handles;
		storage                       m_data;
		index_store< handle, TINDEX > m_indexes;
	};

}

namespace std
{
	template < 
		typename T, 
		unsigned IBITS,
		unsigned CBITS,
		typename TAG
	>
	struct hash<nv::handle<T,IBITS,CBITS,TAG>>
	{
		size_t operator()(const nv::handle<T,IBITS,CBITS,TAG>& h) const
		{
			return h.hash();
		}
	};
}

#endif // NV_CORE_HANDLE_HH