#pragma once

#include <algorithm>
#include <vector>
#include <functional>
#include "NonCopyable.h"

namespace il2cpp
{

namespace utils
{

namespace collections
{

// Memory compact, map-like data structure that stores values and
// is a able to compute the key from the value with the provided converter
// This data structure is perfect to storing values that will not be changed
// for the duration of program (like type metadata) and need fast querying
//
// It is able to store multiple values associated with a single key, and query them through find()
// find_first() is a special case find() which improves performance for cases where we don't store multiple values for each key
template <typename TKey, typename TValue, typename TValueToKeyConverter, typename TKeyLess = std::less<TKey>, typename TKeyEquals = std::equal_to<TKey> >
class ArrayValueMap : NonCopyable
{
public:
	typedef ArrayValueMap<TKey, TValue, TValueToKeyConverter, TKeyLess, TKeyEquals> map_type;
	typedef const TValue* iterator;

private:
	const TValue* m_Values;
	const size_t m_ValueCount;
	bool m_OwnStorage;
	const TValueToKeyConverter m_ValueToKeyConverter;
	const TKeyLess m_KeyLessComparer;
	const TKeyEquals m_KeyEqualsComparer;

	struct SortComparer
	{
	private:
		const TValueToKeyConverter m_ValueToKeyConverter;
		const TKeyLess m_KeyComparer;

	public:
		SortComparer(TValueToKeyConverter valueToKeyConverter, TKeyLess keyComparer) :
			m_ValueToKeyConverter(valueToKeyConverter), m_KeyComparer(keyComparer)
		{
		}

		inline bool operator()(const TValue& left, const TValue& right) const
		{
			return m_KeyComparer(m_ValueToKeyConverter(left), m_ValueToKeyConverter(right));
		}
	};

	struct LowerBoundFindComparer
	{
	private:
		const TValueToKeyConverter m_ValueToKeyConverter;
		const TKeyLess m_KeyComparer;

	public:
		LowerBoundFindComparer(TValueToKeyConverter valueToKeyConverter, TKeyLess keyComparer) :
			m_ValueToKeyConverter(valueToKeyConverter), m_KeyComparer(keyComparer)
		{
		}

		inline bool operator()(const TValue& left, const TKey& right) const
		{
			return m_KeyComparer(m_ValueToKeyConverter(left), right);
		}
	};

	struct UpperBoundFindComparer
	{
	private:
		const TValueToKeyConverter m_ValueToKeyConverter;
		const TKeyLess m_KeyComparer;

	public:
		UpperBoundFindComparer(TValueToKeyConverter valueToKeyConverter, TKeyLess keyComparer) :
			m_ValueToKeyConverter(valueToKeyConverter), m_KeyComparer(keyComparer)
		{
		}

		inline bool operator()(const TKey& left, const TValue& right) const
		{
			return m_KeyComparer(left, m_ValueToKeyConverter(right));
		}
	};

	inline static TValue* InitializeInPlace(TValue* values, size_t valueCount, TValueToKeyConverter valueToKeyConverter, TKeyLess keyLessComparer)
	{
		std::sort(values, values + valueCount, SortComparer(valueToKeyConverter, keyLessComparer));
		return values;
	}

	inline static TValue* AllocateAndInitialize(const TValue* originalValues, size_t valueCount, TValueToKeyConverter valueToKeyConverter, TKeyLess keyLessComparer)
	{
		TValue* values = new TValue[valueCount];
		memcpy(values, originalValues, valueCount * sizeof(TValue));

		return InitializeInPlace(values, valueCount, valueToKeyConverter, keyLessComparer);
	}

public:
	inline ArrayValueMap() :
		m_Values(NULL),
		m_ValueCount(0),
		m_OwnStorage(false),
		m_ValueToKeyConverter(TValueToKeyConverter()),
		m_KeyLessComparer(TKeyLess()),
		m_KeyEqualsComparer(TKeyEquals())
	{
	}

	// Non-allocating constructor. It will take a pointer and will not allocate any storage
	// It WILL sort existing values
	inline ArrayValueMap(TValue* values, size_t valueCount, TValueToKeyConverter valueToKeyConverter = TValueToKeyConverter(),
		TKeyLess keyLessComparer = TKeyLess(), TKeyEquals keyEqualsComparer = TKeyEquals()) :
		m_Values(InitializeInPlace(values, valueCount, valueToKeyConverter, keyLessComparer)),
		m_ValueCount(valueCount),
		m_ValueToKeyConverter(valueToKeyConverter),
		m_KeyLessComparer(keyLessComparer),
		m_KeyEqualsComparer(keyEqualsComparer),
		m_OwnStorage(false)
	{
	}

	// Allocating constructor
	// Will copy values to newly allocated storage
	inline ArrayValueMap(const std::vector<TValue>& values, TValueToKeyConverter valueToKeyConverter = TValueToKeyConverter(),
		TKeyLess keyLessComparer = TKeyLess(), TKeyEquals keyEqualsComparer = TKeyEquals()) :
		m_Values(AllocateAndInitialize(values.data(), values.size(), valueToKeyConverter, keyLessComparer)),
		m_ValueCount(values.size()),
		m_ValueToKeyConverter(valueToKeyConverter),
		m_KeyLessComparer(keyLessComparer),
		m_KeyEqualsComparer(keyEqualsComparer),
		m_OwnStorage(true)
	{
	}

	~ArrayValueMap()
	{
		if (m_OwnStorage)
		{
			delete[] m_Values;
		}
	}

	inline void assign(TValue* values, size_t valueCount, TValueToKeyConverter valueToKeyConverter = TValueToKeyConverter(),
		TKeyLess keyLessComparer = TKeyLess(), TKeyEquals keyEqualsComparer = TKeyEquals())
	{
		this->~ArrayValueMap();
		new(this) map_type(values, valueCount, valueToKeyConverter, keyLessComparer, keyEqualsComparer);
	}

	// Constructs map that contains pointers to original array
	inline void assign_addresses(const TValue& valueArray, size_t valueCount, TValueToKeyConverter valueToKeyConverter = TValueToKeyConverter(),
		TKeyLess keyLessComparer = TKeyLess(), TKeyEquals keyEqualsComparer = TKeyEquals())
	{
		this->~ArrayValueMap();

		TValue* storage = NULL;

		if (valueCount > 0)
		{
			storage = new TValue[valueCount];

			for (size_t i = 0; i < valueCount; i++)
			{
				storage[i] = &valueArray[i];
			}
		}

		new(this) map_type(storage, valueCount, valueToKeyConverter, keyLessComparer, keyEqualsComparer);
		m_OwnStorage = true;
	}

	inline void assign(const std::vector<TValue>& values, TValueToKeyConverter valueToKeyConverter = TValueToKeyConverter(),
		TKeyLess keyLessComparer = TKeyLess(), TKeyEquals keyEqualsComparer = TKeyEquals())
	{
		this->~ArrayValueMap();
		new(this) map_type(values, valueToKeyConverter, keyLessComparer, keyEqualsComparer);
	}

	inline iterator begin() const
	{
		return m_Values;
	}

	inline iterator end() const
	{
		return m_Values + m_ValueCount;
	}

	template <typename EqualsPredicate>
	inline iterator find(const TKey& key, const EqualsPredicate& equalsPredicate) const
	{
		iterator dataStart = begin();
		iterator dataEnd = end();
		iterator ptr = std::lower_bound(dataStart, dataEnd, key, LowerBoundFindComparer(m_ValueToKeyConverter, m_KeyLessComparer));

		for (; ptr != dataEnd && m_KeyEqualsComparer(m_ValueToKeyConverter(*ptr), key); ptr++)
		{
			if (equalsPredicate(*ptr))
				return ptr;
		}

		return dataEnd;
	}

	inline iterator find_first(const TKey& key) const
	{
		iterator dataStart = begin();
		iterator dataEnd = end();
		iterator ptr = std::lower_bound(dataStart, dataEnd, key, LowerBoundFindComparer(m_ValueToKeyConverter, m_KeyLessComparer));

		if (ptr != dataEnd && m_KeyEqualsComparer(m_ValueToKeyConverter(*ptr), key))
			return ptr;

		return dataEnd;
	}

	inline iterator lower_bound(const TKey& key) const
	{
		return std::lower_bound(begin(), end(), key, LowerBoundFindComparer(m_ValueToKeyConverter, m_KeyLessComparer));
	}

	inline iterator upper_bound(const TKey& key) const
	{
		return std::upper_bound(begin(), end(), key, UpperBoundFindComparer(m_ValueToKeyConverter, m_KeyLessComparer));
	}

	inline size_t size() const
	{
		return m_ValueCount;
	}

	inline const TValue& operator[](size_t i) const
	{
		return m_Values[i];
	}
};

}

}	// namespace utils

}	// namespace il2cpp
