//
// Created by Eugeny Grishul
//
// See license at http://bamelg.com/license.txt
//

using System.Runtime;

namespace System.Collections {
	// Designed for huge amounts of small structs
	// O(1) allocation and removal
	// Object addresses not changed after resize
	public class PagedPool<T> {
		private int _version;

		private PageInfo* _firstPage;
		private int _pageCount;

		private const int _elementsPerPage1 = ( int )( ( Memory.DefaultPageReserveSize - typeof( PageInfo ).ContentStride ) / ( typeof( T ).ContentStride + sizeof( byte ) ) );
		private const int _elementsPerPage2 = ( int )( ( Memory.DefaultPageReserveSize - typeof( PageInfo ).ContentStride ) / ( typeof( T ).ContentStride + sizeof( ushort ) ) );
		private const bool _useIndices1 = _elementsPerPage1 < 256;
		public const int BlockSize = _useIndices1 ? _elementsPerPage1 : _elementsPerPage2;

		public int Count { get; private set; }
		public int Capacity { get { return _pageCount * BlockSize; } }

		public Functors.Action<T*> OnInitialize, OnFinalize = bitcast<Functors.Action<T*>>( typeof( T ).Destructor );

		public PagedPool() {
			Assert.IsTrue( typeof( T ).IsStruct | typeof( T ).IsFixedArray ); // PagedPool<T> designed to be used with structs
			Assert.IsTrue( BlockSize > 2 ); // Dont use big structures
		}

		~PagedPool() {
			if( OnFinalize != null )
				foreach( var value in this )
					OnFinalize( value );

			for( var page = _firstPage; page != null; ) {
				var next = page->Next;
				Memory.FreePages( page->Elements, Memory.DefaultPageReserveCount );
				page = next;
			}
		}

		private PageInfo* AllocatePage() {
			var memory = ( byte* ) Memory.AllocatePages( Memory.DefaultPageReserveCount );
			var page = ( PageInfo* )( memory + Memory.DefaultPageReserveSize - typeof( PageInfo ).ContentStride );

			// page->Parent = this; ReleaseReference();
			*( void** ) &page->Parent = bitcast<void*>( this ); // dont touch refcount
			page->Next = _firstPage;
			_firstPage = page;

			[DisableWarningUnreachable]
			if( _useIndices1 ) {
				var pageIndices = page->Indices1;
				page->FreeIndexPtr = pageIndices;
				for( var i = 0; i < BlockSize; ++i )
					pageIndices[i] = ( byte ) i;
			}
			else {
				var pageIndices = page->Indices2;
				page->FreeIndexPtr = pageIndices;
				for( var i = 0; i < BlockSize; ++i )
					pageIndices[i] = ( ushort ) i;
			}

			return page;
		}

		// unfortunately we must return ptrs to prevent possible usage errors
		public T* TryAllocate() {
			CommonCollectionOperations.UpdateVersion( &_version );

			for( var page = _firstPage; page != null; page = page->Next ) {
				if( page->FreeCount <= 0 ) continue;
				return Allocate( page );
			}

			// Allocate new page
			{
				var page = AllocatePage();
				return Allocate( page );
			}
		}

		public T* Allocate() {
			var result = TryAllocate();
			if( result == null ) Assert.Fail( "Not enought room for new elements!" );
			return result;
		}

		public void Free( T* value ) {
			if( value == null ) return;

			CommonCollectionOperations.UpdateVersion( &_version );

			var page = GetPageInfo( value );
			if( page != null ) {
				Free( page, value );
				return;
			}

			Assert.Fail( "'value' not owned!" );
		}

		public yield<T*> GetEnumerator() {
			var version = _version;

			var freeMap = new BitArray( BlockSize );

			for( var page = _firstPage; page != null; page = page->Next ) {
				freeMap.Clear();

				var count = page->Count;
				if( count <= 0 ) continue;

				var indices1 = page->Indices1;
				var indices2 = page->Indices2;
				var elements = page->Elements;

				for( var j = count; j < BlockSize; ++j ) {
					freeMap[_useIndices1 ? indices1[j] : indices2[j]] = true;
				}

				for( var j = 0; j < BlockSize; ++j ) {
					if( freeMap[j] ) continue;

					CommonCollectionOperations.VersionCheck( version == _version );

					yield return elements + j;
				}
			}
		}

		/// For debug-only purposes
		public int IndexOf( T* value ) {
			var page = GetPageInfo( value );
			if( page != null ) {
				var valueIndex = IndexOf( page, value );
				if( valueIndex == -1 ) return -1;

				var pageIndex = _pageCount - 1;
				for( var existingPage = _firstPage; existingPage != null; existingPage = existingPage->Next, --pageIndex ) {
					if( page == existingPage )
						return valueIndex + pageIndex * BlockSize;
				}

				return -1;
			}

			return -1;
		}

		/// @{ page operations
		private struct PageInfo {
			public declaringtype Parent;
			public void* FreeIndexPtr;
			public PageInfo* Next;

			public byte* Indices1 { get { return bitcast<byte*>( &this ) - BlockSize; } }
			public ushort* Indices2 { get { return bitcast<ushort*>( &this ) - BlockSize; } }

			public T* Elements { get { return bitcast<T*>( bitcast<uintptr>( &this ) & ~( Memory.DefaultPageReserveSize - 1 ) ); } }

			public int Count { get { return _useIndices1 ? ( int )( ( byte* ) FreeIndexPtr - Indices1 ) : ( int )( ( ushort* ) FreeIndexPtr - Indices2 ); } }
			public int FreeCount { get { return ( int )( BlockSize - Count ); } }
		}

		private static PageInfo* GetPageInfo( T* element ) { return ( bitcast<PageInfo*>( bitcast<byte*>( bitcast<uintptr>( element ) | ( Memory.DefaultPageReserveSize - 1 ) ) - typeof( PageInfo ).ContentStride + 1 ) ); }

		private int IndexOf( PageInfo* page, T* value ) {
			if( page->Parent != this ) return -1;

			var elements = page->Elements;

			return ( value >= elements && value < elements + BlockSize ) ? ( int )( value - elements ) : -1;
		}

		private T* Allocate( PageInfo* page ) {
			++Count;

			ushort index;

			[DisableWarningUnreachable]
			if( _useIndices1 ) {
				index = *( byte* ) page->FreeIndexPtr;
				page->FreeIndexPtr = ( byte* ) page->FreeIndexPtr + 1;
			}
			else {
				index = *( ushort* ) page->FreeIndexPtr;
				page->FreeIndexPtr = ( ushort* ) page->FreeIndexPtr + 1;
			}

			var result = page->Elements + index;
			Memory.Clear( result, sizeof( T ) );
			if( OnInitialize != null ) OnInitialize( result );
			return result;
		}

		[Conditional( ConditionString = "DEBUG" )]
		private void VerifyOwning( PageInfo* page, T* value ) {
			Assert.IsTrue( IsOwned( page, value ) );
		}

		[Conditional( ConditionString = "DEBUG" )]
		private void VerifyFree( PageInfo* page, intptr value ) {
			var freeCount = page->FreeCount;

			[DisableWarningUnreachable]
			if( _useIndices1 ) {
				var freePtr = ( byte* ) page->FreeIndexPtr;
				for( var i = 0; i < freeCount; ++i ) {
					if( freePtr[i] == value ) {
						Assert.Fail( "Object already freed!" );
						return;
					}
				}
			}
			else {
				var freePtr = ( ushort* ) page->FreeIndexPtr;
				for( var i = 0; i < freeCount; ++i ) {
					if( freePtr[i] == value ) {
						Assert.Fail( "Object already freed!" );
						return;
					}
				}
			}
		}

		private void Free( PageInfo* page, T* value ) {
			--Count;

			VerifyOwning( page, value );
			var index = value - page->Elements;
			VerifyFree( page, index );
			if( OnFinalize != null ) OnFinalize( value );

			[DisableWarningUnreachable]
			if( _useIndices1 ) {
				page->FreeIndexPtr = ( byte* ) page->FreeIndexPtr - 1;
				*( byte* ) page->FreeIndexPtr = ( byte ) index;
			}
			else {
				page->FreeIndexPtr = ( ushort* ) page->FreeIndexPtr - 1;
				*( ushort* ) page->FreeIndexPtr = ( ushort ) index;
			}
		}

		private bool IsOwned( PageInfo* page, T* value ) {
			var elements = page->Elements;

			return value >= elements && value < elements + BlockSize;
		}
		/// @}
	}
}