// 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;
		typedef TAG tag_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>()( 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 >
		friend class handle_operator;
	};

	template < typename HANDLE >
	class handle_operator
	{
	public:
		typedef typename HANDLE::value_type value_type;

		static HANDLE create( value_type index, value_type counter )
		{
			return HANDLE( index, counter );
		}
		static value_type get_counter( const HANDLE& h ) { return h.m_counter; }
		static value_type get_index( const HANDLE& h ) { return h.m_index; }
	};

	template < typename HANDLE >
	class handle_manager
	{
		static const sint32 NONE = -1;
		static const sint32 USED = -2;
	public:

		typedef HANDLE handle;
		typedef typename HANDLE::value_type value_type;

		handle_manager() : m_first_free( NONE ), m_last_free( NONE ) {}

		handle create_handle()
		{
			typedef handle_operator<HANDLE> hop;
			value_type i = get_free_entry();
			m_entries[i].counter++;
			m_entries[i].next_free = USED;
			return hop::create( i, m_entries[i].counter );
		}

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

		bool is_valid( handle h ) const
		{
			typedef handle_operator<HANDLE> hop;
			if ( h.is_nil() ) return false;
			if ( h.index() >= m_entries.size() ) return false;
			const index_entry& entry = m_entries[h.index()];
			return entry.next_free == USED && entry.counter == hop::get_counter( h );
		}

	private:
		struct index_entry
		{
			value_type counter;
			sint32     next_free;

			index_entry() : counter( 0 ), next_free( NONE ) {}
		};

		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 = USED;
				if ( m_first_free == -1 ) m_last_free = -1;
				return result;
			}
			m_entries.emplace_back();
			return value_type( m_entries.size() - 1 );
		}

		sint32 m_first_free;
		sint32 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( (index_type) h.index() );
			m_indexes[ h.index() ] = (index_type) 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[ (unsigned)i ]) : nullptr;
		}

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

		void remove( handle h )
		{
			if ( h.is_nil() || h.index() >= m_indexes.size() || m_indexes[h.index()] == -1 ) 
				return;
			handle swap_handle    = m_handles.back();
			sint32 dead_eindex    = m_indexes[ h.index() ];
			if ( dead_eindex != (sint32)m_data.size()-1 )
			{
				m_data[ (unsigned)dead_eindex ]    = m_data.back();
				m_handles[ (unsigned)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();
		}

		handle get_handle( index_type i ) const { return m_handles[(unsigned)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:
		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_t)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 handle_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;

		handle_store() {}

		explicit handle_store( uint32 reserve )
		{
			m_data.reserve( reserve );
		}

		handle create()
		{
			handle h = m_indexes.create_handle();
			m_data.insert( h );
			return h;
		}

		bool is_valid( handle h )
		{
			return m_indexes.is_valid( h );
		}

		const value_type* get( handle h ) const
		{
			return m_data.get( h );
		}

		value_type* get( handle h )
		{
			return m_data.get( h );
		}

		void destroy( handle e )
		{
			m_data.remove( e );
			m_indexes.free_handle( e );
		}

		handle get_handle( index_type i ) const { return m_data.get_handle(i); }
		const value_type& operator[] ( index_type i ) const { return m_data[(unsigned)i]; }
		value_type& operator[] ( index_type i ) { return m_data[(unsigned)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:
		packed_indexed_array< T, handle, TINDEX > m_data;
		handle_manager< handle >                  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