// 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 array.hh
 * @author Kornel Kisielewicz epyon@chaosforge.org
 * @brief exception free array classes
 */

#ifndef NV_CORE_ARRAY_HH
#define NV_CORE_ARRAY_HH

#include <nv/core/common.hh>
#include <nv/stl/memory.hh>
#include <nv/stl/iterator.hh>
#include <nv/stl/utility.hh>
#include <vector>
#include <algorithm>
#include <array>

namespace nv
{

	struct default_init
	{

	};

	template< typename SizeType >
	struct default_next_capacity
	{
		static SizeType get( SizeType requested, SizeType capacity, SizeType max_size )
		{
			SizeType minimum = nv::min<SizeType>( capacity, 4 );
			SizeType remaining = max_size - capacity;
			if ( remaining < requested ) return 0;
			SizeType additional = nv::max( requested, capacity );
			return nv::max( minimum, remaining < additional ? max_size : capacity + additional );
		}
	};

	struct policy_initialize_always
	{
		template < typename ForwardIterator >
		inline static void initialize( ForwardIterator first, ForwardIterator last )
		{
			uninitialized_construct( first, last );
		}
		template < typename InputIterator, typename ForwardIterator >
		inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out )
		{
			return uninitialized_copy( first, last, out );
		}
		template < typename ForwardIterator >
		inline static void destroy( ForwardIterator first, ForwardIterator last )
		{
			uninitialized_destroy( first, last );
		}
		template < typename ForwardIterator >
		inline static void destroy( ForwardIterator first )
		{
			destroy_object( first );
		}
	};

	struct policy_initialize_never
	{
		template < typename ForwardIterator >
		inline static void initialize( ForwardIterator, ForwardIterator )
		{
		}
		template < typename InputIterator, typename ForwardIterator >
		inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out )
		{
			return detail::uninitialized_copy( first, last, out, true_type );
		}
		template < typename ForwardIterator >
		inline static void destroy( ForwardIterator, ForwardIterator )
		{
		}
		template < typename ForwardIterator >
		inline static void destroy( ForwardIterator )
		{
		}
	};

	struct policy_initialize_standard
	{
		template < typename ForwardIterator >
		inline static void initialize( ForwardIterator first, ForwardIterator last )
		{
			typedef typename iterator_traits< ForwardIterator >::value_type value_type;
			if ( !has_trivial_constructor<value_type>() )
				detail::uninitialized_construct_impl( first, last, false_type() );
		}
		template < typename InputIterator, typename ForwardIterator >
		inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out )
		{
			return uninitialized_copy( first, last, out );
		}
		template < typename ForwardIterator >
		inline static void destroy( ForwardIterator first, ForwardIterator last )
		{
			typedef typename iterator_traits< ForwardIterator >::value_type value_type;
			if ( !has_trivial_destructor<value_type>() )
				detail::uninitialized_destroy_impl( first, last, false_type() );
		}
		template < typename ForwardIterator >
		inline static void destroy( ForwardIterator first )
		{
			typedef typename iterator_traits< ForwardIterator >::value_type value_type;
			if ( !has_trivial_destructor<value_type>() )
				destroy_object( first );
		}
	};

	template< typename T >
	class dynamic_storage
	{
	public:
		typedef T      value_type;

		static constexpr bool is_static = false;
		static constexpr bool is_const = false;

		constexpr const value_type* data() const { return reinterpret_cast<const value_type*>( m_data ); }
		inline    value_type* data() { return reinterpret_cast<T*>( m_data ); }
		constexpr const char* raw_data() const { return reinterpret_cast<const char*>( m_data ); }
		inline    char* raw_data() { return reinterpret_cast<char*>( m_data ); }

	protected:
		constexpr dynamic_storage() : m_data( nullptr ) {}
		// prevent copying 
		dynamic_storage( const dynamic_storage& ) = delete;
		dynamic_storage& operator=( const dynamic_storage& ) = delete;
		// allow move
		inline dynamic_storage( dynamic_storage&& other )
			: m_data( other.m_data )
		{
			other.m_data = nullptr;
		}
		inline dynamic_storage& operator=( dynamic_storage&& other  )
		{
			if ( this != &other )
			{
				reallocate( 0, false );
				m_data = other.m_data;
			}
			return *this;
		}
		~dynamic_storage() = default;

		bool reallocate( size_t new_size, bool copy_needed )
		{
			if ( copy_needed )
				m_data = (uint8*)nvrealloc( m_data, new_size * sizeof( value_type ) );
			else
			{
				nvfree( m_data );
				m_data = ( new_size > 0 ? (uint8*)nvmalloc( new_size * sizeof( value_type ) ) : nullptr );
			}
			return true; // TODO : alloc check?
		}
	protected:
		uint8* m_data;
	};

	template< typename T, size_t N >
	class static_storage
	{
	public:
		typedef T      value_type;

		static constexpr bool is_static = true;
		static constexpr bool is_const = false;

		constexpr const value_type* data() const { return reinterpret_cast<const value_type*>( m_data ); }
		inline    value_type* data() { return reinterpret_cast<T*>( m_data ); }
		constexpr const char* raw_data() const { return reinterpret_cast<const char*>( m_data ); }
		inline    char* raw_data() { return reinterpret_cast<char*>( m_data ); }

	protected:
		static constexpr bool reallocate( size_t new_size, bool /*copy_needed*/ ) { return new_size <= N; }

		static_storage() = default;

		// prevent copying 
		static_storage( const static_storage& ) = delete;
		static_storage& operator=( const static_storage& ) = delete;
		// allow move
		static_storage( static_storage&& other ) = default;
		static_storage& operator=( static_storage&& other ) = default;

		~static_storage() = default;
	protected:
		typedef aligned_array_t<T, N, alignof( T ) > storage_type;
		storage_type m_data;
	};

	template< typename Storage, size_t N >
	class fixed_storage : public Storage
	{
	public:
		typedef size_t                       size_type;
		typedef typename Storage::value_type value_type;

		static constexpr bool is_fixed = true;

		fixed_storage()
		{
			Storage::reallocate( N, false );
		}
		~fixed_storage()
		{
			Storage::reallocate( 0, false );
		}
		static constexpr size_type max_size() { return N; }
		static constexpr size_type capacity() { return N; }
		static constexpr size_type size() { return N; }
		static constexpr bool empty() { return N == 0; }
		static constexpr size_type raw_size() { return sizeof( value_type ) * N; }

		operator array_ref< value_type >()             { return array_ref< value_type >( Storage::data(), size() ); }
		operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); }

		// allow move
		fixed_storage( fixed_storage&& ) = default;
		fixed_storage& operator=( fixed_storage&& ) = default;
	};

	template< typename Storage >
	class resizable_storage : public Storage
	{
	public:
		typedef size_t                       size_type;
		typedef typename Storage::value_type value_type;

		static constexpr bool is_fixed = false;

		~resizable_storage()
		{
			if ( m_size > 0 ) reallocate( 0, false );
		}
		static constexpr size_type max_size() { return size_type( 0x80000000 ); }
		constexpr size_t capacity() { return m_size; }
		constexpr size_t size() const { return m_size; }
		constexpr bool empty() const { return m_size == 0; }
		constexpr size_t raw_size() const { return sizeof( value_type ) * m_size; }

		operator array_ref< value_type >()             { return array_ref< value_type >( Storage::data(), size() ); }
		operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); }
	protected:
		constexpr resizable_storage() : m_size( 0 ) {}

		// allow move
		inline resizable_storage( resizable_storage&& other )
			: Storage( nv::move( other ) ), m_size( other.m_size )
		{
			other.m_size = 0;
		}
		inline resizable_storage& operator=( resizable_storage&& other )
		{
			m_size = other.m_size;
			Storage::operator=( nv::move( o ) );
			other.m_size = 0;
			return *this;
		}

		// TODO: return type error checking
		bool try_resize( size_t new_size, bool copy_needed )
		{
			if ( new_size != m_size )
			{
				if ( reallocate( new_size, copy_needed ) )
				{
					m_size = new_size;
					return true;
				}
				return false;
			}
			return true;
		}
	protected:
		size_type m_size;
	};

	template< typename Storage, typename NextCapacity = default_next_capacity< size_t > >
	class growable_storage : public Storage
	{
	public:
		typedef size_t                       size_type;
		typedef typename Storage::value_type value_type;

		static constexpr bool is_fixed = false;

		~growable_storage()
		{
			if ( m_capacity > 0 ) reallocate( 0, false );
		}
		static constexpr size_type max_size() { return size_type( 0x80000000 ); }
		constexpr size_t capacity() { return m_capacity; }
		constexpr size_t size() const { return m_size; }
		constexpr bool empty() const { return m_size == 0; }
		constexpr size_t raw_size() const { return sizeof( value_type ) * m_size; }

		operator array_ref< value_type >()             { return array_ref< value_type >( Storage::data(), size() ); }
		operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); }
	protected:
		constexpr growable_storage() : m_size( 0 ), m_capacity( 0 ) {}

		// allow move
		inline growable_storage( growable_storage&& other )
			: Storage( nv::move( other ) ), m_size( other.m_size ), m_capacity( other.m_capacity )
		{
			other.m_size     = 0;
			other.m_capacity = 0;
		}
		inline growable_storage& operator=( growable_storage&& other )
		{
			m_size     = other.m_size;
			m_capacity = other.m_capacity;
			Storage::operator=( nv::move( other ) );
			other.m_size     = 0;
			other.m_capacity = 0;
			return *this;
		}

		// TODO: return type error checking
		bool try_grow( size_t amount )
		{
			size_type new_size = amount + m_size;
			if ( new_size > m_capacity )
			{
				size_type new_capacity = NextCapacity::get( new_size - m_capacity, m_capacity, max_size() );
				if ( new_capacity > 0 && reallocate( new_capacity, true ) )
				{
					m_capacity = new_capacity;
					m_size = new_size;
				}
				else return false;
			}
			m_size = new_size;
			return true;
		}
		// TODO: return type error checking
		bool try_reserve( size_t new_capacity, bool copy_needed )
		{
			if ( new_capacity > m_capacity )
			{
				if ( reallocate( new_capacity, copy_needed ) )
				{
					m_capacity = new_capacity;
				}
				else return false;
			}
			return true;
		}
		// TODO: return type error checking
		bool try_resize( size_t new_size, bool copy_needed )
		{
			if ( new_size > m_size )
			{
				if ( try_reserve( new_size, copy_needed ) )
				{
					m_size = new_size;
					return true;
				}
				return false;
			}
			m_size = new_size;
			return true;
		}
	protected:
		size_type m_size;
		size_type m_capacity;
	};


	template< typename T, size_t N >
	using fixed_static_storage = fixed_storage< static_storage< T, N >, N >;

	template< typename T, size_t N >
	using fixed_dynamic_storage = fixed_storage< dynamic_storage< T >, N >;

	template< typename T >
	using resizable_dynamic_storage = resizable_storage< dynamic_storage< T > >;

	template< typename T, size_t N >
	using resizable_static_storage = resizable_storage< static_storage< T, N > >;

	template< typename T >
	using growable_dynamic_storage = growable_storage< dynamic_storage< T > >;

	template< typename T, size_t N >
	using growable_static_storage = growable_storage< static_storage< T, N > >;

	template <
		typename Storage,
		typename InitializePolicy = policy_initialize_standard
	>
	class fixed_container_allocator : public Storage
	{
	public:
		typedef typename Storage::value_type value_type;
		typedef typename Storage::size_type  size_type;

		fixed_container_allocator()
		{
			InitializePolicy::initialize( data(), data() + Storage::capacity() );
		}

		explicit fixed_container_allocator( default_init )
		{
			uninitialized_construct( data(), data() + Storage::capacity() );
		}

		explicit fixed_container_allocator( const value_type& v )
		{
			uninitialized_fill( data(), data() + Storage::capacity(), v );
		}

		~fixed_container_allocator()
		{
			InitializePolicy::destroy( data(), data() + Storage::capacity() );
		}

		// prevent copying 
		fixed_container_allocator( const fixed_container_allocator& ) = delete;
		fixed_container_allocator& operator=( const fixed_container_allocator& ) = delete;
		// allow move
		fixed_container_allocator( fixed_container_allocator&& ) = default;
		fixed_container_allocator& operator=( fixed_container_allocator&& ) = default;
	};

	template <
		typename Storage,
		typename InitializePolicy = policy_initialize_standard
	>
	class sized_container_allocator : public Storage
	{
	public:
		typedef typename Storage::value_type value_type;
		typedef typename Storage::size_type  size_type;

		inline sized_container_allocator() {}
		inline explicit sized_container_allocator( size_type new_size ) { resize( new_size ); }
		inline explicit sized_container_allocator( default_init ) { resize( default_init() ); }
		inline sized_container_allocator( size_type new_size, const value_type& v ) { resize( new_size, v ); }

		// prevent copying 
		sized_container_allocator( const sized_container_allocator& ) = delete;
		sized_container_allocator& operator=( const sized_container_allocator& ) = delete;
		// allow move
		sized_container_allocator( sized_container_allocator&& ) = default;
		sized_container_allocator& operator=( sized_container_allocator&& ) = default;


		inline void resize( size_type new_size )
		{
			size_type old_size = Storage::size();
			resize_impl( new_size );
			initialize_range( old_size, Storage::size() );
		}

		inline void resize( size_type new_size, default_init )
		{
			size_type old_size = Storage::size();
			resize_impl( new_size );
			initialize_range( old_size, Storage::size(), default_init() );
		}

		inline void resize( size_type new_size, const value_type& value )
		{
			size_type old_size = Storage::size();
			resize_impl( new_size );
			initialize_range( old_size, Storage::size(), value );
		}

		inline void assign( const value_type* ptr, size_type sz )
		{
			if ( Storage::size() > 0 ) InitializePolicy::destroy( Storage::data(), Storage::data() + Storage::size() );
			if ( ptr != nullptr && sz > 0 )
			{
				if ( sz != Storage::size() && Storage::try_resize( sz, false ) )
					InitializePolicy::copy( ptr, ptr + sz, Storage::data() );
			}
			else Storage::try_resize( 0, false );
		}

		template< typename InputIterator >
		inline void assign( InputIterator first, InputIterator last )
		{
			size_type d = distance( first, last );
			if ( d != Storage::size() && Storage::try_resize( sz, false ) )
				InitializePolicy::copy( first, last, Storage::data() );
		}

		// explicit copy
		inline void assign( const sized_container_allocator& other )
		{
			assign( other.data(), other.size() );
		}

		inline void clear()
		{
			if ( Storage::size() > 0 )
			{
				InitializePolicy::destroy( Storage::data(), Storage::data() + Storage::size() );
				Storage::try_resize( 0, false );
			}
		}

		~sized_container_allocator()
		{
			if ( Storage::size() > 0 ) clear();
		}

	protected:

		inline void initialize_range( size_type old_size, size_type new_size )
		{
			if ( new_size > old_size ) InitializePolicy::initialize( Storage::data() + old_size, Storage::data() + new_size );
		}
		inline void initialize_range( size_type old_size, size_type new_size, default_init )
		{
			if ( new_size > old_size ) uninitialized_construct( Storage::data() + old_size, Storage::data() + new_size );
		}
		inline void initialize_range( size_type old_size, size_type new_size, const value_type& value )
		{
			if ( new_size > old_size ) uninitialized_fill( Storage::data() + old_size, Storage::data() + new_size, value );
		}
		inline void resize_impl( size_type new_size )
		{
			size_type old_size = Storage::size();
			if ( new_size != old_size )
			{
				if ( new_size < old_size )
				{
					InitializePolicy::destroy( Storage::data() + new_size, Storage::data() + old_size );
				}
				if ( Storage::try_resize( new_size, true ) )
				{
					// TODO: error checking
				}
			}
		}

	};

	template <
		typename Storage,
		typename InitializePolicy = policy_initialize_standard
	>
	class growing_container_allocator : public sized_container_allocator< Storage, InitializePolicy >
	{
		typedef sized_container_allocator< Storage, InitializePolicy > inherited;
	public:
		typedef typename Storage::value_type value_type;
		typedef typename Storage::size_type  size_type;

		using sized_container_allocator< Storage, InitializePolicy >::sized_container_allocator;

		void reserve( size_type new_capacity )
		{
			Storage::try_reserve( new_capacity, true );
		}
		void push_back( const value_type& e )
		{
			if ( Storage::try_grow( 1 ) ) copy_construct_object( data() + size() - 1, e );
		}
		void push_back( value_type&& e )
		{
			if ( Storage::try_grow( 1 ) ) move_construct_object( data() + size() - 1, forward<value_type>( e ) );
		}
		template < typename... Args >
		void emplace_back( Args&&... args )
		{
			if ( Storage::try_grow( 1 ) ) construct_object( data() + size() - 1, forward<Args>( args )... );
		}
		void pop_back()
		{
			try_resize( size() - 1, true );
		}

	};


	template < typename ContainerAllocator >
	using array_base_t = detail::add_random_access< detail::add_iterators < ContainerAllocator > >;

	template< typename T, size_t N >
	using array = array_base_t < fixed_container_allocator < fixed_static_storage< T, N > > >;
	
	template< typename T >
	using dynamic_array = array_base_t < sized_container_allocator< resizable_dynamic_storage< T > > >;

	template< typename T >
	using vector = array_base_t < growing_container_allocator< growable_dynamic_storage< T > > >;

}

#endif // NV_CORE_ARRAY_HH