//==============================================================================================================================
// Cric_Containers.cpp
// The Cric Framework © Chris Maiwald, 2004–2011
//		email	cricwood@lavabit.com
//		ICQ		342173470
// Codepage: Windows-1252; text width: 128 chars; tab size: 4 spaces
// File comments are in English language.
//==============================================================================================================================
#if !defined(CRIC_CONTAINERS_HPP)
#define CRIC_CONTAINERS_HPP

#if defined(CRICPP_NO_RVALUE_REFERENCES)
#	error Cric::TCPlainVector, Cric::TCVector and Cric::TCMap require rvalue reference support
#endif



// This file is a master include. It can be included without explicitly including <Cric.hpp> first.
#include "Cric.hpp"



namespace Cric {



	//==========================================================================================================================
	// A simple vector, similar to "::std::vector", but without random insertion or deletion — new elements must strictly be
	//	inserted at the end. However, this allows the vector to store elements which have no assignment operators (e.g. if they
	//	contain references or 'const' members).
	// Also, it has a little less overhad than an ordinary vector. You should choose this class whenever you plan to fill a
	//	vector continuously.
	// Works best if "CElement" defines a move constructor.
	//==========================================================================================================================
	template <
		typename itsElementType
	> class TCPlainVector
		: public INonAssignable	// currently no assignment operator required; suppress compiler-generated default
	{
	public:
		typedef itsElementType		CElement;
		typedef CElement *			CIterator;
		typedef CElement const *	CConstIterator;

		//----------------------------------------------------------------------------------------------------------------------
		// Default constructor. Does not allocate anything.
		//----------------------------------------------------------------------------------------------------------------------
		TCPlainVector()
			: myBegin(nullptr)
			, myLength(0)
			, myCapacity(0)
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Constructor. Reserves capacity for the given number of elements.
		//----------------------------------------------------------------------------------------------------------------------
		explicit // has only one parameter
		TCPlainVector(
			CSize const itsCapacity
		)
			: myBegin(reinterpret_cast<CElement *>(memory::allocate(itsCapacity * sizeof(CElement))))
			, myLength(0)
			, myCapacity(itsCapacity)
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Constructor. Allocates the given number of elements and initializes them with the given reference.
		// Requires "CElement" to have a copy-constructor.
		//----------------------------------------------------------------------------------------------------------------------
		TCPlainVector(
			CSize const			itsLength,
			CElement const &	initialValue
		)
			: myBegin(reinterpret_cast<CElement *>(memory::allocate(itsLength * sizeof(CElement))))
			, myLength(itsLength)
			, myCapacity(itsLength)
		{
			// Copy-construct each element using placement new.
			for(CSize currentElementsIndex = 0; currentElementsIndex < myLength; ++currentElementsIndex)
				// • Why not use "&myBegin[currentElementsIndex]"?
				//	— If "CElement" has its operator & overloaded, this would have unforeseen consequences.
				new (myBegin + currentElementsIndex) CElement(initialValue);

			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Copy constructor.
		// Requires "CElement" to have a copy-constructor.
		//----------------------------------------------------------------------------------------------------------------------
		TCPlainVector(
			TCPlainVector<CElement> const & reference
		)
			: myBegin(nullptr)
			, myLength(reference.myLength)
			, myCapacity(0)
		{
			reAllocateTo(reference.myCapacity);

			// !TODO! Make exception-safe

			// Copy-construct each element using placement new.
			for(CSize currentElementsIndex = 0; currentElementsIndex < reference.myLength; ++currentElementsIndex)
				// • Why not use "&myBegin[CurrentElementsIndex]"?
				//	— If "CElement" has its operator & overloaded, this would have unforeseen consequences.
				new (myBegin + currentElementsIndex) CElement(*(reference.myBegin + currentElementsIndex));

			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Move constructor.
		//----------------------------------------------------------------------------------------------------------------------
		TCPlainVector(
			TCPlainVector<CElement> && reference
		)
			: myBegin(reference.myBegin)
			, myLength(reference.myLength)
			, myCapacity(reference.myCapacity)
		{
			reference.myBegin		= nullptr;
			reference.myLength		= 0;
			reference.myCapacity	= 0;
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Move assignment operator.
		//----------------------------------------------------------------------------------------------------------------------
		TCPlainVector<CElement> & operator = (
			TCPlainVector<CElement> && reference
		) {
			this->~TCPlainVector();
			myBegin		= reference.myBegin;
			myLength	= reference.myLength;
			myCapacity	= reference.myCapacity;
			reference.myBegin		= nullptr;
			reference.myLength		= 0;
			reference.myCapacity	= 0;
			return *this;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns the number of elements in the vector.
		//----------------------------------------------------------------------------------------------------------------------
		CSize length() const {
			return myLength;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns whether there are no elements stored in the vector.
		//----------------------------------------------------------------------------------------------------------------------
		CBoolean isEmpty() const {
			return 0 >= myLength;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns the total size of all elements stored in the vector (not counting capacity), in bytes.
		//----------------------------------------------------------------------------------------------------------------------
		CByteSize size() const {
			return sizeof(CElement) * myLength;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns the number of elements that could technically be stored in the vector without a reallocation.
		//----------------------------------------------------------------------------------------------------------------------
		CSize capacity() const {
			return myCapacity;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Retuns an iterator to the array's begin.
		//----------------------------------------------------------------------------------------------------------------------
		CIterator begin() {
			return myBegin;
		}
		//......................................................................................................................
		CConstIterator begin() const {
			return myBegin;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns an iterator to the array's last element.
		//----------------------------------------------------------------------------------------------------------------------
		CIterator last() {
			// Consider that the vector may be empty.
			return isEmpty() ? nullptr : myBegin + myLength - 1;
		}
		//......................................................................................................................
		CConstIterator last() const {
			// Consider that the vector may be empty.
			return isEmpty() ? nullptr : myBegin + myLength - 1;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns an iterator to the array's end (the first element *beyond* the vector).
		//----------------------------------------------------------------------------------------------------------------------
		CIterator end() {
			return myBegin + myLength;
		}
		//......................................................................................................................
		CConstIterator end() const {
			return myBegin + myLength;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Index operator. Returns the element at the given index. Throws "CException" if the access is out-of-bounds.
		//----------------------------------------------------------------------------------------------------------------------
		CElement & operator [] (
			CSize const elementsIndex
		) {
			if_unlikely(elementsIndex >= myLength)
				CException::Throw("array index out of bounds");
			return myBegin[elementsIndex];
		}
		//......................................................................................................................
		CElement const & operator [] (
			CSize const elementsIndex
		) const {
			if_unlikely(elementsIndex >= myLength)
				CException::Throw("array index out of bounds");
			return myBegin[elementsIndex];
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Appends a new element at the end of the vector and returns a reference to it. This may cause a reallocation.
		//----------------------------------------------------------------------------------------------------------------------
		// • Why is there no const reference version?
		//	— It can be emulated clearly using "Copy()".
		//	— Accepting only rvalue references avoids the case where an element of the same vector is inserted. This would be
		//		complicated to handle, because the object would be invalid immediately after the reallocation.
		CElement & append(
			CElement &&	newElementsValue
		) {
			// Allocate sufficient memory. Consider: since move operations must not throw exceptions, this is the only thing
			//	that could go wrong.
			if(myCapacity <= myLength)
				reAllocateTo(proposeCapacityFor(myLength + 1));
			CRIC_ASSERT(nullptr != myBegin);

			// Move-construct the new element directly on the raw memory …
			// • Why not use "&myBegin[myLength]"?
			//	— If "CElement" has its operator & overloaded, this would have unforeseen consequences.
			new (myBegin + myLength) CElement(move(newElementsValue));
			// … and return a reference to it after having incremented the vector's length.
			return myBegin[myLength++];
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Deletes all elements at and after the given index.
		//----------------------------------------------------------------------------------------------------------------------
		void shortenTo(
			CSize const newSize
		) {
			// This is *not* an allocation function.
			CRIC_ASSERT(newSize <= myLength);

			// Delete all unneeded elements.
			for(CSize currentIndex = newSize; currentIndex < myLength; ++currentIndex)
				// Delete it manually since there is no placement delete in C++ (see
				//	http://www2.research.att.com/~bs/bs_faq2.html#placement-delete).
				myBegin[currentIndex].~CElement();

			myLength = newSize;
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Deletes all elements in the vector and deallocates it then.
		//----------------------------------------------------------------------------------------------------------------------
		void clear() {

			// Call each element's destructor. This must be done manually since there is no placement delete in C++ (see
			//	http://www2.research.att.com/~bs/bs_faq2.html#placement-delete).
			// If the vector is empty or has been moved, its begin and end are both 'nullptr'.
			for(CElement * toCurrentElement = myBegin; toCurrentElement < (myBegin + myLength); ++toCurrentElement)
				toCurrentElement->~CElement();

			// Release the memory associated with this vector.
			memory::release(myBegin); // checks for 'nullptr'

			myBegin = nullptr;
			myLength = myCapacity = 0;

			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Destructor. Releases all elements.
		//----------------------------------------------------------------------------------------------------------------------
		~TCPlainVector() {

			// Call each element's destructor. This must be done manually since there is no placement delete in C++ (see
			//	http://www2.research.att.com/~bs/bs_faq2.html#placement-delete).
			// If the vector is empty or has been moved, its begin and end are both 'nullptr'.
			for(CElement * ToCurrentElement = myBegin; ToCurrentElement < (myBegin + myLength); ++ToCurrentElement)
				ToCurrentElement->~CElement();

			// Release the memory associated with this vector.
			memory::release(myBegin); // checks for 'nullptr'

			return;
		}

	protected:

		//----------------------------------------------------------------------------------------------------------------------
		// Proposes a capacity for the given size, so reallocations are saved.
		//----------------------------------------------------------------------------------------------------------------------
		static // instance-independent
		CSize proposeCapacityFor(
			CSize const requestedLength
		) {
			// See http://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array.
			return requestedLength + (requestedLength / 2);
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Re-allocates the vector to the given capacity. This is very likely to cause a reallocation.
		// This is a low-level management function, it does not create or destroy any objects.
		//----------------------------------------------------------------------------------------------------------------------
		// Compilers tend to inline this function together with "append()" in loops. This, however, is completely wrong — if a
		//	vector is to be filled in loops with frequent reallocations, function call overhead is the least problem. Instead,
		//	the vector should have already been reserved to a sufficient size — then, not inlining this function will lower
		//	register pressure and improve cache locality.
		CRIC_DONT_INLINE
		void reAllocateTo(
			CSize const newCapacity
		) {
			if(0 < newCapacity)
				// Reallocation requested. Consider that "memory::reAllocate()" also handles first-time allocations.
				myBegin = reinterpret_cast<CElement *>(memory::reAllocate(myBegin, newCapacity * sizeof(CElement)));
			else
				// Deallocation requested.
				memory::release(myBegin), myBegin = nullptr;

			myCapacity = newCapacity;
			return;
		}

		// Points to the first element or is 'nullptr' (if the vector is empty or has been moved)
		CElement *	myBegin;
		// The number of elements in the array.
		CSize		myLength;
		// The maximal number of elements that could be stored without an reallocation.
		CSize		myCapacity;
	}; // class TCPlainVector



	//==========================================================================================================================
	// A dynamic array, similar to "::std::vector".
	// If you plan to fill a vector continuously, or if "CElement" does not define an assignment operator (e.g. contains 'const'
	//	members or references), use "TCPlainVector" instead.
	// Works best if "CElement" defines a move constructor and a move assignment operator.
	//==========================================================================================================================
	template <
		typename CElement
	> class TCVector
		: public TCPlainVector<CElement>
	{
	protected:
		using TCPlainVector<CElement>::myBegin;
		using TCPlainVector<CElement>::myLength;
		using TCPlainVector<CElement>::myCapacity;
	public:

		//----------------------------------------------------------------------------------------------------------------------
		// Default constructor. Does not allocate anything.
		//----------------------------------------------------------------------------------------------------------------------
		TCVector()
			: TCPlainVector<CElement>()
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Constructor. Reserves capacity for the given number of elements.
		//----------------------------------------------------------------------------------------------------------------------
		explicit // has only one parameter
		TCVector(
			CSize const itsCapacity
		)
			: TCPlainVector<CElement>(itsCapacity)
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Constructor. Default-constructs the given number of elements.
		//----------------------------------------------------------------------------------------------------------------------
		TCVector(
			CSize const			itsLength,
			CElement const &	initialValue
		)
			: TCPlainVector<CElement>(itsLength, initialValue)
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Copy constructor.
		//----------------------------------------------------------------------------------------------------------------------
		TCVector(
			TCVector<CElement> const & reference
		)
			: TCPlainVector<CElement>(reference)
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Move constructor.
		//----------------------------------------------------------------------------------------------------------------------
		TCVector(
			TCVector<CElement> && reference
		)
			: TCPlainVector<CElement>(move(reference))
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Move assignment operator.
		//----------------------------------------------------------------------------------------------------------------------
		TCVector<CElement> & operator = (
			TCVector<CElement> && reference
		) {
			TCPlainVector<CElement>::operator = (move(reference));
			return *this;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Inserts a new element at the given position and returns a reference to it. This may cause a reallocation.
		// It is optimal to insert elements at the end, so use "append()" instead, if you can.
		//----------------------------------------------------------------------------------------------------------------------
		CElement & insert(
			CSize const	newElementsIndex,
			CElement &&	newElementsValue
		) {
			// Allow insertion inside or at the end of the container. Do NOT allow insertion after the container's end, which
			//	would result in uninitialized elements being exposed to the user.
			CRIC_ASSERT(newElementsIndex <= myLength);

			// Allocate sufficient memory. Notice that this is the only thing that could go wrong, since move operations must
			//	not throw exceptions.
			if(myCapacity <= myLength)
				reAllocateTo(proposeCapacityFor(myLength + 1));
			CRIC_ASSERT(nullptr != myBegin);

			// If the new element is to be inserted at the vector's end (which is the optimal, therefore most likely option) …
			if(newElementsIndex == myLength) {
				// … move construct the new element directly on the raw memory.
				// • Why not use "&myBegin[NewElementsIndex]"?
				//	— If "CElement" has its operator & overloaded, this would have unforeseen consequences.
				new (myBegin + newElementsIndex) CElement(move(newElementsValue));
			} else {
				// If the new element is to be inserted inside the array, move all following elements one step backward.
				// This requires the new last element to be move constructed and all other elements to be move-assigned.
				// • Why not use "&myBegin[myLength]"?
				//	— If "CElement" has its operator & overloaded, this would have unforeseen consequences.
				new (myBegin + myLength) CElement(move(myBegin[myLength - 1]));
				for(CSize currentOldIndex = myLength - 1; currentOldIndex > newElementsIndex; --currentOldIndex)
					myBegin[currentOldIndex] = move(myBegin[currentOldIndex - 1]);
				// Insert the new element through move assignment.
				myBegin[newElementsIndex] = move(newElementsValue);
			}

			// Return a reference to the new element after having incremented the vector's length.
			++myLength;
			return myBegin[newElementsIndex];
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Removes the element at the given position (without causing a reallocation, thus keeping iterators intact). To delete
		//	elements at the end (which is optimal), use "shortenTo()".
		//----------------------------------------------------------------------------------------------------------------------
		void remove(
			CSize const elementsIndex
		) {
			// Allow deletion of elements *in*, but not *past* the vector.
			CRIC_ASSERT(elementsIndex < myLength);

			// If the element is to be removed from inside the array, …
			if((elementsIndex + 1) < myLength) {
				//	… then overwrite it by moving all following elements one step forward.
				for(CSize currentOldIndex = myLength - 1; currentOldIndex > elementsIndex; --currentOldIndex)
					myBegin[currentOldIndex - 1] = move(myBegin[currentOldIndex]);
			}

			// Now, the only element to be deleted is the one at the end. Delete it manually since there is no placement delete
			//	in C++ (see http://www2.research.att.com/~bs/bs_faq2.html#placement-delete).
			myBegin[--myLength].~CElement();

			return;
		}

	}; // class TCVector



	//==========================================================================================================================
	// Maps values to keys, similar to "::std::map".
	//==========================================================================================================================
	template <
		typename itsKeyType,
		typename itsValueType
	> class TCMap
		: public INonCopyAssignable	// currently no copy c'tor and operator = required; suppress compiler-generated default
	{
	public:
		typedef itsKeyType		CKey;
		typedef itsValueType	CValue;

		//======================================================================================================================
		// Entry of a map. Consists of a value and its key.
		//======================================================================================================================
		struct SEntry {
			CKey	key;
			CValue	value;

			//------------------------------------------------------------------------------------------------------------------
			// Move constructor.
			// This is the default constructor for inserting new elements.
			//------------------------------------------------------------------------------------------------------------------
			SEntry(
				CKey &&		itsKey,
				CValue &&	itsValue
			)
				: key(move(itsKey))
				, value(move(itsValue))
			{
				return;
			}

			//------------------------------------------------------------------------------------------------------------------
			// Move constructor. Actually used whenever the vector containing the map's entries is manipulated.
			//------------------------------------------------------------------------------------------------------------------
			explicit // has only one parameter
			SEntry(
				SEntry && ItsReference
			)
				: key(move(ItsReference.key))
				, value(move(ItsReference.value))
			{
				return;
			}

			//------------------------------------------------------------------------------------------------------------------
			// Move assignment operator. Actually used whenever the vector containing the map's entries is manipulated.
			//------------------------------------------------------------------------------------------------------------------
			SEntry & operator = (
				SEntry && Reference
			) {
				key = move(Reference.key);
				value = move(Reference.value);
				return *this;
			}

		}; // struct SEntry

		typedef typename TCVector<SEntry>::CIterator		CIterator;
		typedef typename TCVector<SEntry>::CConstIterator	CConstIterator;

		//----------------------------------------------------------------------------------------------------------------------
		// Default constructor. Does not allocate anything.
		//----------------------------------------------------------------------------------------------------------------------
		TCMap()
			: myEntries()
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Constructor. Reserves space for the given number of entries.
		//----------------------------------------------------------------------------------------------------------------------
		explicit // has only one parameter
		TCMap(
			CSize const itsCapacity
		)
			: myEntries(itsCapacity)
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Move constructor.
		//----------------------------------------------------------------------------------------------------------------------
		explicit // has only one parameter
		TCMap(
			TCMap<CKey, CValue> && reference
		)
			: myEntries(move(reference.myEntries))
		{
			return;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Move assignment operator.
		//----------------------------------------------------------------------------------------------------------------------
		TCMap<CKey, CValue> & operator = (
			TCMap<CKey, CValue> && reference
		) {
			myEntries = move(reference.myEntries);
			return *this;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns whether there are no elements stored in the map.
		//----------------------------------------------------------------------------------------------------------------------
		CBoolean isEmpty() const {
			return myEntries.isEmpty();
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns the map's entries, sorted in ascending order. You can use it to iterate over a map's entries.
		//----------------------------------------------------------------------------------------------------------------------
		// A non-'const' version of this function does not exist since it could be used to break the map's consistency.
		CIterator begin() {
			return myEntries.begin();
		}
		//......................................................................................................................
		CConstIterator begin() const {
			return myEntries.begin();
		}
		//......................................................................................................................
		CIterator end() {
			return myEntries.end();
		}
		//......................................................................................................................
		CConstIterator end() const {
			return myEntries.end();
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Returns the number of elements stored in the map.
		//----------------------------------------------------------------------------------------------------------------------
		CSize length() const {
			return myEntries.length();
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Removes the given entry from the map.
		//----------------------------------------------------------------------------------------------------------------------
		void remove(
			CIterator const toEntry
		) {
			CRIC_ASSERT(isWithin(begin(), toEntry, last()));
			myEntries.remove(CSize(toEntry - myEntries.begin())); // OK, as never negative
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Inserts a new entry of the given key and of the given value.
		// If the insertion succeeds, "true" is returned. If the insertion fails (for example, if an entry of the given key
		//	already exists), "false" is returned.
		//----------------------------------------------------------------------------------------------------------------------
		CBoolean tryToInsert(
			CKey &&		key,
			CValue &&	value
		) {
			CSize proposedIndex = 0;
			if(findEntry(key, proposedIndex))
				return false;
			else {
				myEntries.insert(proposedIndex, SEntry(move(key), move(value)));
				return true;
			}
		}
		//......................................................................................................................
		CBoolean tryToInsert(
			CKey const &key,
			CValue &&	value
		) {
			CSize proposedIndex = 0;
			if(findEntry(key, proposedIndex))
				return false;
			else {
				myEntries.insert(proposedIndex, SEntry(copy(key), move(value)));
				return true;
			}
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Tries to find a value of the given key. If it succeeds, a pointer to the value is returned. Otherwise, 'nullptr' is
		//	returned.
		//----------------------------------------------------------------------------------------------------------------------
		CValue * tryToFind(
			CKey const & Key
		) {
			CSize proposedIndex = 0;
			if(findEntry(Key, proposedIndex))
				return &(myEntries[proposedIndex].value);
			else
				return nullptr;
		}
		//......................................................................................................................
		CValue const * tryToFind(
			CKey const & key
		) const {
			CSize proposedIndex = 0;
			if(findEntry(key, proposedIndex))
				return &(myEntries[proposedIndex].value);
			else
				return nullptr;
		}

		//----------------------------------------------------------------------------------------------------------------------
		// Tries to find a value of the given key. If successful, a reference to it is returned. If not, a new entry is inserted
		//	and its value is default-initialized.
		//----------------------------------------------------------------------------------------------------------------------
		CValue & findOrInsertNew(
			CKey const & key
		) {
			CSize proposedIndex = 0;
			if(findEntry(key, proposedIndex))
				return myEntries[proposedIndex].value;
			else
				return myEntries.insert(proposedIndex, SEntry(key, CValue()));
		}

	protected:

		//----------------------------------------------------------------------------------------------------------------------
		// Finds an entry. If an entry of the given key already exists, its index is written and "true" is returned. Otherwise,
		//	"false" is returned and the index is set to the nearest index (it can be directly used as a parameter to "insert()"
		//	then). Consider that this index is out-of-bounds if the new entry is to be inserted at the end of the map.
		//----------------------------------------------------------------------------------------------------------------------
		// This function originally returned a pointer to the entry's proposed destination. However, since there are 'const'
		//	and non-'const' pointers, either inspectors or mutators could use this function, but not both. An index, on the
		//	other hand, can be used in 'const' and non-'const' member functions equally well.
		CBoolean findEntry(
			CKey const &	itsKey,
			CSize &			toBeItsProposedIndex
		) const {
			// Binary search: From a range of possible positions (at the beginning, this is the whole entry table), a central
			//	sample is taken and compared to the requested key. The result of the comparison then decides whether the upper
			//	or lower half of the range is re-used for the next iteration. A position is found if there remain one or zero
			//	indices in the range.
			// This could have been solved perfectly using recursion, but since recursion can be quite inefficient (recursive
			//	functions cannot be inlined, they consume much stack memory and prevent efficient register usage), it is
			//	implemented in an iterative approach.

			SEntry const * toMinimalPosition = myEntries.begin();
			SEntry const * toMaximalPosition = myEntries.end(); // exclusive!
			SEntry const * toSample			 = myEntries.begin();

			// The range's maximum is exclusive — even if there is just one element left, the minimal and maximal positions are
			//	still not equal. If they really are, this means that there are no possible entries left at all (the key does
			//	not exist).
			// This test also rejects empty maps — it must be performed here, not at the end of the loop.
			while(toMinimalPosition < toMaximalPosition) {

				// Take a sample from the middle and floor, if necessary. This guarantees that lower indices are preferred
				//	(which is necessary since an insertion will move all entries after the proposed index one up. If all entries
				//	*before* the proposed index would be moved one *down*, we would have to ceil).
				// The odd syntax is because it is impossible to add two pointers.
				toSample = toMinimalPosition + ((toMaximalPosition - toMinimalPosition) / 2);
				CRIC_ASSERT(toMinimalPosition <= toSample);
				CRIC_ASSERT(toMaximalPosition > toSample);

				// Compare the sample to the desired key. Consider that user types are only required to implement "operator <".
				if(itsKey < toSample->key) {
					// Choose the lower half. The current sample can be excluded since it is lower, not lower or equal — but
					//	then again, the maximal position is exclusive!
					toMaximalPosition = toSample;
				} else if(toSample->key < itsKey) {
					// Choose the upper half. The current sample can be excluded since it is above, not above or equal.
					toMinimalPosition = toSample + 1;
				} else {
					// Jackpot — the sample *is* the requested value.
					toBeItsProposedIndex = CSize(toSample - myEntries.begin());
					CRIC_ASSERT(toBeItsProposedIndex < myEntries.length());
					return true;
				}

				CRIC_ASSERT(toMaximalPosition >= toMinimalPosition);
			} // while possibilities left

			toBeItsProposedIndex = CSize(toMinimalPosition - myEntries.begin());
			CRIC_ASSERT(toBeItsProposedIndex <= myEntries.length());
			return false;
		}

		// Stores all entries of the map, sorted in ascending order.
		TCVector<SEntry> myEntries;
	}; // class TCMap



} // namespace Cric



#endif // CRIC_CONTAINERS_HPP