#ifndef ARRAYMAP_H__
#define ARRAYMAP_H__

#include "maxon/basearray.h"
#include "maxon/sortedarray.h"
#include "maxon/bitmanipulation.h"
#include "maxon/optional.h"

namespace maxon
{

/// @addtogroup STRUCTURES
/// @{

// helper class for ArrayMap for the unsorted case
template <typename K, typename V, Bool SORTED, typename COMPARE, typename ARRAY> class ArrayMapHelper
{
public:
	using Entry = Pair<K, V>;
	using Array = typename ARRAY::template Type<Entry>;

	static ResultRef<Entry> Insert(Array& array, const K& key, Bool& created, Int& index)
	{
		created = false;
		Int i = 0;
		for (Entry& e : array)
		{
			if (COMPARE::IsEqual(e.GetKey(), key))
			{
				index = i;
				return &e;
			}
			++i;
		}
		ResultRef<Entry> v = array.Append();
		if (v == OK)
		{
			created = true;
			index = i;
		}
		return v;
	}

	template <typename KEY> static const Entry* Find(const Array& array, const KEY& key)
	{
		for (const Entry& v : array)
		{
			if (COMPARE::IsEqual(key, v.GetKey()))
			{
				return &v;
			}
		}
		return nullptr;
	}

	template <typename KEY> static Int FindIndex(const Array& array, const KEY& key)
	{
		const Int n = array.GetCount();
		for (Int i = 0; i < n; ++i)
		{
			if (COMPARE::IsEqual(array[i].GetKey(), key))
				return i;
		}
		return ~n;
	}

	static Bool Erase(Array& array, const K& key)
	{
		for (auto it = Iterable::EraseIterator(array); it; ++it)
		{
			if (COMPARE::IsEqual(it->GetKey(), key))
			{
				it.Erase();
				return true;
			}
		}
		return false;
	}
};


// helper class for ArrayMap for the sorted case (where a SortedArray is used internally)
template <typename K, typename V, typename COMPARE, typename ARRAY> class ArrayMapHelper<K, V, true, COMPARE, ARRAY>
{
public:
	using Entry = Pair<K, V>;
	using Array = typename ARRAY::template Type<Entry>;
	using IsSorted = std::true_type;

	using Sort = SimpleSort<ArrayMapHelper>;

	static Bool LessThan(const Entry& a, const Entry& b) { return COMPARE::LessThan(a.first, b.first); }
	static Bool IsEqual(const Entry& a, const Entry& b) { return COMPARE::IsEqual(a.first, b.first); }

	template <typename KEY> static Bool LessThan(const KEY& a, const Entry& b) { return COMPARE::LessThan(a, b.first); }
	template <typename KEY> static Bool IsEqual(const KEY& a, const Entry& b) { return COMPARE::IsEqual(a, b.first); }

	template <typename KEY> static Bool LessThan(const Entry& a, const KEY& b) { return COMPARE::LessThan(a.first, b); }

	static ResultRef<Entry> Insert(Array& array, const K& key, Bool& created, Int& index)
	{
		index = NOTOK;
		Entry* e = Sort().FindInsertionIndex(key, array, index);
		if (!e)
		{
			e = array.Insert(index).GetPointer();
			created = true;
		}
		else
		{
			created = false;
		}
		return e;
	}

	template <typename KEY> static const Entry* Find(const Array& array, const KEY& key)
	{
		return Sort().Find(key, array);
	}

	template <typename KEY> static Int FindIndex(const Array& array, const KEY& key)
	{
		return Sort().FindIndex(key, array.Begin(), array.GetCount());
	}

	static Bool Erase(Array& array, const K& key)
	{
		Int i = FindIndex(array, key);
		if (i < 0)
			return false;
		array.Erase(i) iferr_cannot_fail("Erase cannot fail because the index is valid.");
		return true;
	}
};

//----------------------------------------------------------------------------------------
/// An ArrayMap maps keys to values using an underlying array whose elements are key-value-pairs.
/// It may be either sorted or unsorted. For very small maps, unsorted array maps are generally faster.
/// For large maps (exceeding about 100 entries), you should consider using another implementation
/// such as HashMap or BurstTrieMap because especially insertion and erasure become slow with array maps:
/// For a sorted ArrayMap, those operations have a time cost of O(N), while searching has a time cost of O(log N).
///
/// Of all maps, the ArrayMap is the most efficient with respect to memory usage as it really only stores the key-value-pairs.
///
/// See HashMap for more examples on how to use maps in general.
///
/// @tparam K											Type of keys.
/// @tparam V											Type of values.
/// @tparam SORTED								Use true for a sorted array.
/// @tparam COMPARE								Class to be used to compare the keys.
/// @tparam ARRAY									An array selector template to choose the array implementation to use.
/// @see @$ref maps
//----------------------------------------------------------------------------------------
template <typename K, typename V, Bool SORTED = true, typename COMPARE = DefaultCompare, typename ARRAY = BaseArraySelector<>> class ArrayMap : public MapBase<ArrayMap<K, V, SORTED, COMPARE, ARRAY>, K, V, typename ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Array, COMPARE>
{
public:
	using IsArrayMap = std::true_type;
	using Helper = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>;
	using ArrayType = typename Helper::Array;
	using Super = MapBase<ArrayMap<K, V, SORTED, COMPARE, ARRAY>, K, V, ArrayType, COMPARE>;
	using Entry = Pair<K, V>;

	//----------------------------------------------------------------------------------------
	/// Returns the pointer to the entry to which #value belongs. You must not use this function
	/// if you cannot guarantee that value is a part of an entry.
	/// @param[in] value							A pointer to a value which is known to belong to an entry.
	/// @return												The entry of which #value is a part.
	//----------------------------------------------------------------------------------------
	static const Entry* GetEntry(const V* value)
	{
		return reinterpret_cast<const Entry*>(reinterpret_cast<const Char*>(value) - MAXON_OFFSETOF_NON_STANDARD_LAYOUT(Entry, second));
	}

	//----------------------------------------------------------------------------------------
	/// Returns the pointer to the entry to which #value belongs. You must not use this function
	/// if you cannot guarantee that value is a part of an entry.
	/// @param[in] value							A pointer to a value which is known to belong to an entry.
	/// @return												The entry of which #value is a part.
	//----------------------------------------------------------------------------------------
	static Entry* GetEntry(typename std::remove_const<V>::type* value)
	{
		return reinterpret_cast<Entry*>(reinterpret_cast<Char*>(value) - MAXON_OFFSETOF_NON_STANDARD_LAYOUT(Entry, second));
	}

	//----------------------------------------------------------------------------------------
	/// Iterator implementation for ArrayMap. Besides the usual iterator operations,
	/// ArrayMap iterators support the foreach protocol and Erase and ChangeKey functions.
	/// For a sorted ArrayMap, the iterator will point to the map entries in ascending order of the keys
	/// if you use ++ on the iterator.
	//----------------------------------------------------------------------------------------
	template <Bool CONSTITERATOR, template <Bool> class SUPER> class IteratorTemplate : public ForEachIterator<IteratorTemplate<CONSTITERATOR, SUPER>, SUPER<CONSTITERATOR>>
	{
	public:
		using Super = ForEachIterator<IteratorTemplate<CONSTITERATOR, SUPER>, SUPER<CONSTITERATOR>>;

		IteratorTemplate() { }
		explicit IteratorTemplate(typename Super::CollectionType& m, Int s = 0) : Super(m, s) { }
		IteratorTemplate(const IteratorTemplate& src) : Super(src) { }

		MAXON_OPERATOR_COPY_ASSIGNMENT(IteratorTemplate);

		template <Bool C, template <Bool> class S, typename = typename std::enable_if<!CONSTITERATOR || C>::type> operator IteratorTemplate<C, S>&()
		{
			MAXON_ASSERT_STANDARD_LAYOUT(IteratorTemplate);
			using ICS = IteratorTemplate<C, S>;
			MAXON_ASSERT_STANDARD_LAYOUT(ICS);
			static_assert(SIZEOF(IteratorTemplate) == SIZEOF(ICS), "Iterators have different size.");
			return *reinterpret_cast<ICS*>(this);
		}

		using Super::operator Bool;

		IteratorTemplate& operator ++()
		{
			Super::operator ++();
			return *this;
		}

		IteratorTemplate& operator --()
		{
			--Super::GetIterator();
			return *this;
		}

		void operator ++(int)
		{
			Super::operator ++();
		}

		void operator --(int)
		{
			--Super::GetIterator();
		}
	};

	using IteratorBase = AutoIterator<const ArrayType>;

	class NonConstIteratorBase : public AutoIterator<ArrayType>
	{
	public:
		using Super = AutoIterator<ArrayType>;
		NonConstIteratorBase() { }
		NonConstIteratorBase(ArrayMap& m, Int s) : Super(m, s) { }
		NonConstIteratorBase(const NonConstIteratorBase& src) : Super(src) { }

		//----------------------------------------------------------------------------------------
		/// Removes @p eraseCnt elements from the map starting at the position given by this iterator.
		/// Afterwards, this iterator will point to the element behind the last removed element.
		/// @param[in] map								Map of this iterator.
		/// @param[in] eraseCnt						Number of elements to remove.
		/// @return												False if some allocation failed (for an ArrayMap, this is impossible, so this function will always return true).
		//----------------------------------------------------------------------------------------
		ResultOk<void> Erase(ArrayMap& map, Int eraseCnt = 1)
		{
			if (eraseCnt > 0)
			{
				this->_it = map.ArrayType::Erase(this->_it, eraseCnt);
				this->_end = map.ArrayType::End();
			}
			return OK;
		}

		//----------------------------------------------------------------------------------------
		/// Modifies the key of the map entry pointed to by this iterator.
		/// This operation is only supported by sorted array maps. The new key must be in a range
		/// such that this operation doesn't change the order, i.e., it must be above the
		/// key of the previous entry and below the key of the next entry.
		/// @param[in] map								Map of this iterator.
		/// @param[in] newKey							New value for the key of the current map entry.
		/// @return												False if some allocation failed (for an ArrayMap, this is impossible, so this function will always return true).
		//----------------------------------------------------------------------------------------
		ResultOk<void> ChangeKey(ArrayMap& map, const K& newKey)
		{
			static_assert(SORTED, "ChangeKey requires a sorted array map.");
			DebugAssert((this->GetIterator() == map.ArrayType::Begin()) || Helper::LessThan(*(this->GetIterator() - 1), newKey));
			DebugAssert((this->GetIterator() + 1 == map.ArrayType::End()) || Helper::LessThan(newKey, *(this->GetIterator() + 1)));
			K& k = (this->operator ->())->GetFirst();
			if (k != newKey)
			{
				k = newKey;
			}
			return OK;
		}
	};

	template <Bool CONSTITERATOR> class EntryIteratorBase : public std::conditional<CONSTITERATOR, IteratorBase, NonConstIteratorBase>::type
	{
	public:
		using Super = typename std::conditional<CONSTITERATOR, IteratorBase, NonConstIteratorBase>::type;
		using CollectionType = typename ConstIf<ArrayMap, CONSTITERATOR>::type;
		using KeyType = K;
		using MappedType = typename ConstIf<V, CONSTITERATOR>::type;

		EntryIteratorBase() { }
		EntryIteratorBase(CollectionType& m, Int s) : Super(m, (s < 0) ? m.GetCount() : s) { }
		EntryIteratorBase(const EntryIteratorBase& src) : Super(src) { }

		//----------------------------------------------------------------------------------------
		/// Returns the key of the current key-value-pair of this iterator.
		/// @return												Current key of this iterator.
		//----------------------------------------------------------------------------------------
		const K& GetKey() const
		{
			return (this->operator ->())->GetKey();
		}

		//----------------------------------------------------------------------------------------
		/// Returns the value of the current key-value-pair of this iterator.
		/// @return												Current value of this iterator.
		//----------------------------------------------------------------------------------------
		MappedType& GetValue() const
		{
			return (this->operator ->())->GetValue();
		}
	};

	template <Bool CONSTITERATOR> class KeyIteratorBase : public EntryIteratorBase<CONSTITERATOR>
	{
	public:
		using Super = EntryIteratorBase<CONSTITERATOR>;

		KeyIteratorBase() { }
		KeyIteratorBase(typename Super::CollectionType& m, Int s) : Super(m, s) { }
		KeyIteratorBase(const KeyIteratorBase& src) : Super(src) { }

		const K* operator ->() const
		{
			return &this->GetKey();
		}

		const K& operator *() const
		{
			return this->GetKey();
		}
	};

	template <Bool CONSTITERATOR> class ValueIteratorBase : public EntryIteratorBase<CONSTITERATOR>
	{
	public:
		using Type = typename ConstIf<V, CONSTITERATOR>::type;
		using Super = EntryIteratorBase<CONSTITERATOR>;

		ValueIteratorBase() { }
		ValueIteratorBase(typename Super::CollectionType& m, Int s) : Super(m, s) { }
		ValueIteratorBase(const ValueIteratorBase& src) : Super(src) { }

		Type* operator ->() const
		{
			return &this->GetValue();
		}

		Type& operator *() const
		{
			return this->GetValue();
		}
	};

	using Iterator = IteratorTemplate<false, EntryIteratorBase>;
	using ConstIterator = IteratorTemplate<true, EntryIteratorBase>;

	using KeyIterator = IteratorTemplate<false, KeyIteratorBase>;
	using ConstKeyIterator = IteratorTemplate<true, KeyIteratorBase>;

	using ValueIterator = IteratorTemplate<false, ValueIteratorBase>;
	using ConstValueIterator = IteratorTemplate<true, ValueIteratorBase>;

	//----------------------------------------------------------------------------------------
	/// Returns an iterator pointing to the first entry of this map.
	/// For a sorted map, the iteration order corresponds to the order of the keys.
	/// @return												Iterator for this map pointing to the first element.
	//----------------------------------------------------------------------------------------
	Iterator Begin()
	{
		return Iterator(*this);
	}

	//----------------------------------------------------------------------------------------
	/// Returns an iterator pointing just behind the last entry of this map.
	/// For a sorted map, the iteration order corresponds to the order of the keys.
	/// @return												Iterator for this map pointing behind the last element.
	//----------------------------------------------------------------------------------------
	Iterator End()
	{
		return Iterator(*this, ArrayType::GetCount());
	}

	//----------------------------------------------------------------------------------------
	/// Returns an iterator pointing to the first entry of this map.
	/// For a sorted map, the iteration order corresponds to the order of the keys.
	/// @return												Iterator for this map pointing to the first element.
	//----------------------------------------------------------------------------------------
	ConstIterator Begin() const
	{
		return ConstIterator(*this);
	}

	//----------------------------------------------------------------------------------------
	/// Returns an iterator pointing just behind the last entry of this map.
	/// For a sorted map, the iteration order corresponds to the order of the keys.
	/// @return												Iterator for this map pointing behind the last element.
	//----------------------------------------------------------------------------------------
	ConstIterator End() const
	{
		return ConstIterator(*this, ArrayType::GetCount());
	}

	//----------------------------------------------------------------------------------------
	/// Returns a foreach iterator to iterate over all keys of this map.
	/// For a sorted map, this will yield all keys in ascending order.
	/// @return												Foreach iterator over all keys.
	//----------------------------------------------------------------------------------------
	KeyIterator GetKeys()
	{
		return KeyIterator(*this);
	}

	//----------------------------------------------------------------------------------------
	/// Returns a foreach iterator to iterate over all keys of this map.
	/// For a sorted map, this will yield all keys in ascending order.
	/// @return												Foreach iterator over all keys.
	//----------------------------------------------------------------------------------------
	ConstKeyIterator GetKeys() const
	{
		return ConstKeyIterator(*this);
	}

	//----------------------------------------------------------------------------------------
	/// Returns a foreach iterator to iterate over all values of this map.
	/// For a sorted map, this will yield all values in ascending order of the corresponding keys.
	/// @return												Foreach iterator over all values.
	//----------------------------------------------------------------------------------------
	ValueIterator GetValues()
	{
		return ValueIterator(*this);
	}

	//----------------------------------------------------------------------------------------
	/// Returns a foreach iterator to iterate over all values of this map.
	/// For a sorted map, this will yield all values in ascending order of the corresponding keys.
	/// @return												Foreach iterator over all values.
	//----------------------------------------------------------------------------------------
	ConstValueIterator GetValues() const
	{
		return ConstValueIterator(*this);
	}

	ArrayMap() : Super() { }
	ArrayMap(ArrayMap&& src) : Super(std::move(src)) { }
	MAXON_OPERATOR_MOVE_ASSIGNMENT(ArrayMap);

	using Super::IsEqualImpl;

	template <typename MAP, typename CMP> typename SFINAEHelper<Bool, typename MAP::IsArrayMap, typename MAP::IsSorted, typename std::enable_if<STD_IS_REPLACEMENT(same, typename std::decay<CMP>::type, DefaultCompare)>::type>::type IsEqualImpl(const MAP& b, CMP&& cmp, OverloadRank1) const
	{
		Int n = this->GetCount();
		if (n != b.GetCount())
		{
			return false;
		}
		for (Int i = 0; i < n; ++i)
		{
			if (this->operator [](i) != b.operator [](i))
				return false;
		}
		return true;
	}

	//----------------------------------------------------------------------------------------
	/// Returns an estimate of the number of operations needed to locate a given key in this map.
	/// This is used when two collections are compared: The iteration goes over the collection which would require
	/// more operations for search, and each entry is searched in the other collection.
	/// @return												Estimate for the number of operations.
	//----------------------------------------------------------------------------------------
	Int GetOperationCountForSearch() const
	{
		// O(log N) in the sorted case, otherwise O(N).
		Int cnt = this->GetCount();
		return SORTED ? (SIZEOF(Int) * 8 - Clz<Int>(cnt)) : cnt;
	}

	//----------------------------------------------------------------------------------------
	/// Finds the value associated with the given key, or creates a corresponding entry if it doesn't exist yet.
	/// The value of a new entry has to be initialized afterwards (but its default constructor has already been invoked).
	/// @param[in] key								Key of the value to find or create.
	/// @param[out] created						This will be set to true if a new entry has been created successfully, otherwise it will be set to false.
	/// @return												Pointer to value for the given key, or nullptr if an entry didn't exist and allocation of a new entry failed.
	//----------------------------------------------------------------------------------------
	ResultRef<V> InsertKey(const K& key, Bool& created = BoolLValue())
	{
		Int index;
		ResultRef<Entry> v = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Insert(*this, key, created, index);
		if (v == FAILED)
			return nullptr;
		if (created)
		{
			if (AssignCopy(v.GetValue().first, key) == FAILED)
				return nullptr;
		}
		return &std::move(v.GetValue()).GetValue();
	}

	//----------------------------------------------------------------------------------------
	/// Finds the value associated with the given key, or creates a corresponding entry if it doesn't exist yet.
	/// The value of a new entry has to be initialized afterwards (but its default constructor has already been invoked).
	/// @param[in] key								Key of the value to find or create.
	/// @param[out] created						This will be set to true if a new entry has been created successfully, otherwise it will be set to false.
	/// @return												Pointer to value for the given key, or nullptr if an entry didn't exist and allocation of a new entry failed.
	//----------------------------------------------------------------------------------------
	ResultRef<V> InsertKey(K&& key, Bool& created = BoolLValue())
	{
		Int index;
		ResultRef<Entry> v = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Insert(*this, key, created, index);
		if (v == FAILED)
			return nullptr;
		if (created)
		{
			v.GetValue().first = std::move(key);
		}
		return &std::move(v.GetValue()).GetValue();
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the given key, or creates such an entry if it doesn't exist yet,
	/// and returns an iterator pointing to the entry.
	/// The value of a new entry has to be initialized afterwards (but its default constructor has already been invoked).
	/// @param[in] key								Key of the entry to find or create.
	/// @param[out] created						This will be set to true if a new entry has been created successfully, otherwise it will be set to false.
	/// @return												Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultMemT<Iterator> InsertEntry(const K& key, Bool& created = BoolLValue())
	{
		Int index;
		ResultRef<Entry> v = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Insert(*this, key, created, index);
		if (v == FAILED)
			return FAILED;
		if (created)
		{
			if (AssignCopy(v.GetValue().first, key) == FAILED)
				return FAILED;
		}
		return Iterator(*this, index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the given key, or creates such an entry if it doesn't exist yet,
	/// and returns an iterator pointing to the entry.
	/// The value of a new entry has to be initialized afterwards (but its default constructor has already been invoked).
	/// @param[in] key								Key of the entry to find or create. If a new entry is created, its key will be constructed by move-semantics if possible.
	/// @param[out] created						This will be set to true if a new entry has been created successfully, otherwise it will be set to false.
	/// @return												Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultMemT<Iterator> InsertEntry(K&& key, Bool& created = BoolLValue())
	{
		Int index;
		ResultRef<Entry> v = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Insert(*this, key, created, index);
		if (v == FAILED)
			return FAILED;
		if (created)
		{
			v.GetValue().first = std::move(key);
		}
		return Iterator(*this, index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the given key, or creates such an entry if it doesn't exist yet,
	/// and returns an iterator pointing to the entry.
	/// The value of the entry will be set to @p value in any case.
	/// @param[in] key								Key of the entry to find or create.
	/// @param[in] value							This will be copied to the value of the entry.
	/// @param[out] created						This will be set to true if a new entry has been created successfully, otherwise it will be set to false.
	/// @return												Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultMemT<Iterator> Insert(const K& key, const V& value, Bool& created = BoolLValue())
	{
		Int index;
		ResultRef<Entry> v = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Insert(*this, key, created, index);
		if (v == FAILED)
			return FAILED;
		if (created)
		{
			if (AssignCopy(v.GetValue().first, key) == FAILED)
				return FAILED;
		}
		if (AssignCopy(v.GetValue().second, value) == FAILED)
			return FAILED;
		return Iterator(*this, index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the given key, or creates such an entry if it doesn't exist yet,
	/// and returns an iterator pointing to the entry.
	/// The value of the entry will be set to @p value in any case.
	/// @param[in] key								Key of the entry to find or create. If a new entry is created, its key will be constructed by move-semantics if possible.
	/// @param[in] value							This will be copied to the value of the entry.
	/// @param[out] created						This will be set to true if a new entry has been created successfully, otherwise it will be set to false.
	/// @return												Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultMemT<Iterator> Insert(K&& key, const V& value, Bool& created = BoolLValue())
	{
		Int index;
		ResultRef<Entry> v = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Insert(*this, key, created, index);
		if (v == FAILED)
			return FAILED;
		if (created)
			v.GetValue().first = std::move(key);
		if (AssignCopy(v.GetValue().second, value) == FAILED)
			return FAILED;
		return Iterator(*this, index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the given key, or creates such an entry if it doesn't exist yet,
	/// and returns an iterator pointing to the entry.
	/// The value of the entry will be set to @p value in any case.
	/// @param[in] key								Key of the entry to find or create.
	/// @param[in] value							This will be moved to the value of the entry.
	/// @param[out] created						This will be set to true if a new entry has been created successfully, otherwise it will be set to false.
	/// @return												Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultMemT<Iterator> Insert(const K& key, V&& value, Bool& created = BoolLValue())
	{
		Int index;
		ResultRef<Entry> v = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Insert(*this, key, created, index);
		if (v == FAILED)
			return FAILED;
		if (created)
		{
			if (AssignCopy(v.GetValue().first, key) == FAILED)
				return FAILED;
		}
		v.GetValue().second = std::move(value);
		return Iterator(*this, index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the given key, or creates such an entry if it doesn't exist yet,
	/// and returns an iterator pointing to the entry.
	/// The value of the entry will be set to @p value in any case.
	/// @param[in] key								Key of the entry to find or create. If a new entry is created, its key will be constructed by move-semantics if possible.
	/// @param[in] value							This will be moved to the value of the entry.
	/// @param[out] created						This will be set to true if a new entry has been created successfully, otherwise it will be set to false.
	/// @return												Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultMemT<Iterator> Insert(K&& key, V&& value, Bool& created = BoolLValue())
	{
		Int index;
		ResultRef<Entry> v = ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Insert(*this, key, created, index);
		if (v == FAILED)
			return FAILED;
		if (created)
			v.GetValue().first = std::move(key);
		v.GetValue().second = std::move(value);
		return Iterator(*this, index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the index of the entry with the given key.
	/// @param[in] key								The key that the array is searched for.
	/// @return												If an element is found its index will be returned, otherwise the result is the bitwise inverse of the index where key would be inserted (which is always negative). If multiple elements have the same key the index of the first of those elements will be returned.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> Int FindIndex(const KEY& key) const
	{
		return ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::FindIndex(*this, key);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the value associated with the given key in this map.
	/// @param[in] key								Key to search for.
	/// @return												Pointer to value for the given key, or nullptr if no entry exists for the key.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> Opt<const V&> FindValue(const KEY& key) const
	{
		const Entry* v = ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::Find(*this, key);
		return v ? &v->GetValue() : nullptr;
	}

	//----------------------------------------------------------------------------------------
	/// Finds the value associated with the given key in this map.
	/// @param[in] key								Key to search for.
	/// @return												Pointer to value for the given key, or nullptr if no entry exists for the key.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> Opt<V&> FindValue(const KEY& key)
	{
		const Entry* v = ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::Find(*this, key);
		return v ? const_cast<V*>(&v->GetValue()) : nullptr;
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry for the given key in this map.
	/// @param[in] key								Key to search for.
	/// @return												Iterator pointing to the entry with the given @p key,
	/// 															or an invalid iterator if this doesn't exist.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> Iterator Find(const KEY& key)
	{
		Int index = ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::FindIndex(*this, key);
		return (index < 0) ? Iterator() : Iterator(*this, index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry for the given key in this map.
	/// @param[in] key								Key to search for.
	/// @return												Iterator pointing to the entry with the given @p key,
	/// 															or an invalid iterator if this doesn't exist.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> ConstIterator Find(const KEY& key) const
	{
		Int index = ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::FindIndex(*this, key);
		return (index < 0) ? ConstIterator() : ConstIterator(*this, index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the greatest key less than or equal to the given @p key.
	/// If no such entry exists, the returned iterator will be invalid (its <tt>operator Bool</tt> will return false).
	/// This function is only supported by sorted array maps.
	/// @param[in] key								Key to search for.
	/// @return												Iterator pointing to the entry with greatest key less than or equal to the given @p key,
	/// 															or an invalid iterator if this doesn't exist.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> Iterator FindFloor(const KEY& key)
	{
		static_assert(SORTED, "FindFloor requires a sorted array map.");
		Int index = ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::FindIndex(*this, key);
		return (index == -1) ? Iterator() : Iterator(*this, (index < 0) ? -2 - index : index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the greatest key less than or equal to the given @p key.
	/// If no such entry exists, the returned iterator will be invalid (its <tt>operator Bool</tt> will return false).
	/// This function is only supported by sorted array maps.
	/// @param[in] key								Key to search for.
	/// @return												Iterator pointing to the entry with greatest key less than or equal to the given @p key,
	/// 															or an invalid iterator if this doesn't exist.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> ConstIterator FindFloor(const KEY& key) const
	{
		static_assert(SORTED, "FindFloor requires a sorted array map.");
		Int index = ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::FindIndex(*this, key);
		return (index == -1) ? ConstIterator() : ConstIterator(*this, (index < 0) ? -2 - index : index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the smallest key greater than or equal to the given @p key.
	/// If no such entry exists, the returned iterator will be invalid (its <tt>operator Bool</tt> will return false).
	/// This function is only supported by sorted array maps.
	/// @param[in] key								Key to search for.
	/// @return												Iterator pointing to the entry with smallest key greater than or equal to the given @p key,
	/// 															or an invalid iterator if this doesn't exist.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> Iterator FindCeiling(const KEY& key)
	{
		static_assert(SORTED, "FindCeiling requires a sorted array map.");
		Int index = ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::FindIndex(*this, key);
		return (index == this->GetCount()) ? Iterator() : Iterator(*this, (index < 0) ? ~index : index);
	}

	//----------------------------------------------------------------------------------------
	/// Finds the entry with the smallest key greater than or equal to the given @p key.
	/// If no such entry exists, the returned iterator will be invalid (its <tt>operator Bool</tt> will return false).
	/// This function is only supported by sorted array maps.
	/// @param[in] key								Key to search for.
	/// @return												Iterator pointing to the entry with smallest key greater than or equal to the given @p key,
	/// 															or an invalid iterator if this doesn't exist.
	//----------------------------------------------------------------------------------------
	template <typename KEYCOMPARE = COMPARE, typename KEY = K> ConstIterator FindCeiling(const KEY& key) const
	{
		static_assert(SORTED, "FindCeiling requires a sorted array map.");
		Int index = ArrayMapHelper<K, V, SORTED, KEYCOMPARE, ARRAY>::FindIndex(*this, key);
		return (index == this->GetCount()) ? ConstIterator() : ConstIterator(*this, (index < 0) ? ~index : index);
	}

	//----------------------------------------------------------------------------------------
	/// Removes an entry with the given key from this map (if possible).
	/// @param[in] key								Key of the map entry to be be removed.
	/// @return												True if an entry was found and removed for #key, otherwise false.
	//----------------------------------------------------------------------------------------
	ResultOk<Bool> Erase(const K& key)
	{
		return ArrayMapHelper<K, V, SORTED, COMPARE, ARRAY>::Erase(*this, key);
	}

	//----------------------------------------------------------------------------------------
	/// Removes @p eraseCnt elements from this map starting at the position given by @p position.
	/// The returned iterator will point to the element behind the last removed element.
	/// @param[in] position						Iterator pointing to the first element to be removed.
	/// @param[in] eraseCnt						Number of elements to remove.
	/// @return												Iterator pointing to the element behind the last removed element.
	//----------------------------------------------------------------------------------------
	template <template <Bool> class SUPER> IteratorTemplate<false, SUPER> Erase(const IteratorTemplate<false, SUPER>& position, Int eraseCnt = 1)
	{
		IteratorTemplate<false, SUPER> it = position;
		it.Erase(*this, eraseCnt);
		return it;
	}

	//----------------------------------------------------------------------------------------
	/// Appends a map entry with the given key and value at the end, without checking if it
	/// already exists and without respecting the sort order. For a sorted ArrayMap you have to call Sort()
	/// afterwards. This function can be used if you want to append several entries at once,
	/// then it can be faster to do a single sorting step at the end.
	/// @param[in] key								Key of the entry to add.
	/// @param[in] value							Value of the entry to add.
	/// @return												Added entry.
	//----------------------------------------------------------------------------------------
	template <typename KEY, typename VALUE> Result<typename Helper::Entry&> AppendUnsorted(KEY&& key, VALUE&& value)
	{
		return GetUnderlyingArray().Append(typename Helper::Entry(std::forward<KEY>(key), std::forward<VALUE>(value)));
	}

	//----------------------------------------------------------------------------------------
	/// Sorts a map when it's in unsorted state. You have to call this function after
	/// a sequence of calls to AppendUnsorted to ensure sorted state of the ArrayMap.
	//----------------------------------------------------------------------------------------
	void Sort()
	{
		if (SORTED)
		{
			typename Helper::Sort().Sort(GetUnderlyingArray());
		}
	}

	const ArrayType& GetUnderlyingArray() const
	{
		return *this;
	}

	ArrayType& GetUnderlyingArray()
	{
		return *this;
	}

	using Super::CopyFromImpl;

	template <typename COLLECTION, typename = typename std::enable_if<STD_IS_REPLACEMENT(same, typename std::decay<COLLECTION>::type, ArrayMap)>::type>
	Result<void> CopyFromImpl(COLLECTION&& src, COLLECTION_RESIZE_FLAGS resizeFlags, OverloadRank4)
	{
		return GetUnderlyingArray().CopyFrom(src.GetUnderlyingArray(), resizeFlags);
	}
};


//----------------------------------------------------------------------------------------
/// This selector class is used for template parameters which select the map implementation
/// to use. It will then instruct the template to use the ArrayMap implementation.
/// For example, RangeSet uses an underlying BurstTrieMap by default. If you want to use
/// an ArrayMap instead, you'd write
/// @code
/// RangeSet<Int, ArrayMapSelector<>> set;
/// @endcode
///
/// @tparam SORTED								Shall a sorted array map be selected?
/// @tparam COMPARE								Class to be used to compare the keys.
/// @tparam ARRAY									Selector for the array implementation that this map shall use.
//----------------------------------------------------------------------------------------
template <Bool SORTED = true, typename COMPARE = DefaultCompare, typename ARRAY = BaseArraySelector<>> class ArrayMapSelector
{
public:
	template <typename K, typename V> using Type = ArrayMap<K, V, SORTED, COMPARE, ARRAY>;
};


//----------------------------------------------------------------------------------------
/// An ArraySet is an implementation of a set using an underlying array. An element is in
/// the set if it is in the array. ArraySet is based on ArrayMap and takes care of not inserting an element twice
/// in the array. Like ArrayMap, ArraySet may be either sorted or unsorted. For very small sets, unsorted array sets are generally faster.
/// For large sets (exceeding about 100 entries), you should consider using another implementation
/// such as HashSet or BurstTrieSet because especially insertion and erasure become slow with array sets:
/// For a sorted ArraySet, those operations have a time cost of O(N), while searching has a time cost of O(log N).
///
/// Of all sets, the ArraySet is the most efficient with respect to memory usage as it really only stores the contained values.
///
/// See HashSet for more examples on how to use sets in general.
///
/// @tparam T											Type of elements of the set.
/// @tparam SORTED								Use true for a sorted array.
/// @tparam COMPARE								Class to be used to compare the values.
/// @tparam ARRAY									An array selector template to choose the array implementation to use.
/// @see ArrayMap
/// @see @$ref sets
//----------------------------------------------------------------------------------------
template <typename T, Bool SORTED = true, typename COMPARE = DefaultCompare, typename ARRAY = BaseArraySelector<>> class ArraySet
	: public SetBase<ArraySet<T, SORTED, COMPARE, ARRAY>, T, Protected<ArrayMap<T, UnitType, SORTED, COMPARE, ARRAY>>, COMPARE>
{
public:
	using MapType = ArrayMap<T, UnitType, SORTED, COMPARE, ARRAY>;
private:
	using Super = SetBase<ArraySet<T, SORTED, COMPARE, ARRAY>, T, Protected<MapType>, COMPARE>;

	MAXON_DISALLOW_COPY_AND_ASSIGN(ArraySet);

public:
	using MapType::Find;
	using MapType::FindFloor;
	using MapType::FindCeiling;
	using MapType::GetCount;
	using MapType::GetOperationCountForSearch;
	using MapType::SetCapacityHint;
	using MapType::Reset;
	using MapType::Flush;
	using MapType::GetMemorySize;

	using IsArrayMap = std::true_type;
	using IsArraySet = std::true_type;


	ArraySet() : Super()
	{
	}

	ArraySet(ArraySet&& src) : Super(std::move(src))
	{
	}

	MAXON_OPERATOR_MOVE_ASSIGNMENT(ArraySet);

	MapType& GetMap() { return *this; }
	const MapType& GetMap() const { return *this; }

	using Iterator = typename Super::KeyIterator;
	using ConstIterator = typename Super::ConstKeyIterator;

	//----------------------------------------------------------------------------------------
	/// Checks if this set contains @p value.
	/// @param[in] value							The value to check.
	/// @return												True if this set contains @p value.
	//----------------------------------------------------------------------------------------
	Bool Contains(typename ByValueParam<T>::type value) const
	{
		return Super::FindValue(value) != nullptr;
	}

	//----------------------------------------------------------------------------------------
	/// Adds @p value to this set. If @p value is already contained in this set, nothing happens,
	/// and @p added is set to @c false.
	/// @param[in] value							Value to add to this set.
	/// @param[out] added							This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.
	/// @return												Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultMemT<Iterator> Insert(const T& value, Bool& added = BoolLValue())
	{
		return std::move(static_cast<Iterator&>(std::move(Super::InsertEntry(value, added).GetValue())));
	}

	//----------------------------------------------------------------------------------------
	/// Adds @p value to this set. If @p value is already contained in this set, nothing happens,
	/// and @p added is set to @c false.
	/// @param[in] value							Value to add to this set. When a new element has to be added, @p value will be moved into the new element.
	/// @param[out] added							This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.
	/// @return												Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultMemT<Iterator> Insert(T&& value, Bool& added = BoolLValue())
	{
		return std::move(static_cast<Iterator&>(std::move(Super::InsertEntry(std::move(value), added).GetValue())));
	}

	//----------------------------------------------------------------------------------------
	/// Adds @p value to this set. If @p value is already contained in this set, nothing happens,
	/// and @p added is set to @c false.
	/// @param[in] value							Value to add to this set.
	/// @param[out] added							This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.
	/// @return												Pointer to the value in the set, or nullptr if the element had to be added, but the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultRef<const T> InsertKey(const T& value, Bool& added = BoolLValue())
	{
		typename Super::Iterator it = std::move(Super::InsertEntry(value, added).GetValue());
		return it ? &it.GetKey() : nullptr;
	}

	//----------------------------------------------------------------------------------------
	/// Adds @p value to this set. If @p value is already contained in this set, nothing happens,
	/// and @p added is set to @c false.
	/// @param[in] value							Value to add to this set. When a new element has to be added, @p value will be moved into the new element.
	/// @param[out] added							This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.
	/// @return												Pointer to the value in the set, or nullptr if the element had to be added, but the allocation failed.
	//----------------------------------------------------------------------------------------
	ResultRef<const T> InsertKey(T&& value, Bool& added = BoolLValue())
	{
		typename Super::Iterator it = std::move(Super::InsertEntry(std::move(value), added).GetValue());
		return it ? &it.GetKey() : nullptr;
	}

	//----------------------------------------------------------------------------------------
	/// Remove @p value from this set. If @p value isn't contained in this set, nothing happens.
	/// @param[in] value							Value to remove from this set.
	/// @return												True if an entry was found and removed for #value, otherwise false.
	//----------------------------------------------------------------------------------------
	ResultOk<Bool> Erase(const T& value)
	{
		return Super::Erase(value);
	}

	ConstIterator Begin() const
	{
		return ConstIterator(*this);
	}

	ConstIterator End() const
	{
		return ConstIterator(*this, this->GetCount());
	}

	Iterator Begin()
	{
		return Iterator(*this);
	}

	Iterator End()
	{
		return Iterator(*this, this->GetCount());
	}

	Iterator Erase(const Iterator& it)
	{
		return Super::Erase(it);
	}

	const typename ARRAY::template Type<T>& GetUnderlyingArray() const
	{
		return reinterpret_cast<const typename ARRAY::template Type<T>&>(MapType::GetUnderlyingArray());
	}

	typename ARRAY::template Type<T>& GetUnderlyingArray()
	{
		return reinterpret_cast<typename ARRAY::template Type<T>&>(MapType::GetUnderlyingArray());
	}
};

/// @}

} // namespace maxon

#endif // ARRAYMAP_H__
