#pragma once

template<typename T, int items_per_bucket>
struct Bucket_Array
{
	struct Bucket
	{
		T items[items_per_bucket];
	};

	int user_length = 0; // Users may set this if they want to keep track of how many items are in this instance in total. It doesn't affect bucket allocation though.
	int _bucket_count = 0; // Number of currently allocated buckets in _all_buckets. Changes when capacity is set.
	Bucket **_all_buckets = nullptr;

	void clear()
	{
		if (this->_all_buckets == nullptr) { return; }
		for (int i = 0; i < this->_bucket_count; ++i)
		{
			delete this->_all_buckets[i];
		}
		delete this->_all_buckets;
		this->_all_buckets = nullptr;
		this->_bucket_count = 0;
	}

	// Gets a pointer to the item at the specified absolute index.
	// Use this to read or write item values. Returns null if the requested index is out of range.
	T *get_slot(int index)
	{
		int bucket_index = index / items_per_bucket;
		if (bucket_index >= this->_bucket_count) return nullptr;
		int index_in_bucket = index % items_per_bucket;
		Bucket *bucket = _all_buckets[bucket_index];
		T *slot = &bucket->items[index_in_bucket];
		return slot;
	}

	// Fancy C++ reference alternative for get_slot()
	T &operator[](int index) { return *this->get_slot(index); }

	static int get_required_bucket_count(int capacity)
	{
		return (capacity + (items_per_bucket - 1)) / items_per_bucket;
	}

	// If required, changes the number of buckets so that at least the specified number of array items can be stored.
	// Does not shrink the number of buckets.
	void ensure_capacity(int min_capacity)
	{
		int required_bucket_count = get_required_bucket_count(min_capacity);
		if (this->_bucket_count >= required_bucket_count) { return; }
		this->_change_bucket_count(required_bucket_count);
	}

	// If required, changes the number of buckets so that at least the specified number of array items can be stored with minimum overhead,
	// and frees any superfluous buckets that may currently be allocated. Pointers to items in the freed buckets become invalid.
	void set_capacity(int capacity)
	{
		int required_bucket_count = get_required_bucket_count(capacity);
		if (this->_bucket_count == required_bucket_count) { return; }
		this->_change_bucket_count(required_bucket_count);
	}

	void _change_bucket_count(int required_bucket_count)
	{
		int current_bucket_count = this->_bucket_count;
		Bucket **new_array = new Bucket *[required_bucket_count];
		int bucket_index = 0;
		if (_all_buckets != nullptr)
		{
			if (required_bucket_count >= current_bucket_count)
			{
				// Copy all existing buckets, no freeing, allocate new ones if necessary
				for (; bucket_index < current_bucket_count; ++bucket_index)
				{
					new_array[bucket_index] = this->_all_buckets[bucket_index];
				}
			}
			else
			{
				// Copy some buckets, free the rest
				for (; bucket_index < required_bucket_count; ++bucket_index)
				{
					new_array[bucket_index] = this->_all_buckets[bucket_index];
				}
				for (; bucket_index < current_bucket_count; ++bucket_index)
				{
					delete this->_all_buckets[bucket_index];
				}
			}
		}

		for (; bucket_index < required_bucket_count; ++bucket_index)
		{
			new_array[bucket_index] = new Bucket();
		}

		Bucket **old_array = this->_all_buckets;
		this->_all_buckets = new_array;
		this->_bucket_count = required_bucket_count;
		delete old_array;
	}

	~Bucket_Array()
	{
		this->clear();
	}
};