/***************************************************************************
*                                                                          *
*  Copyright (C) Golaem S.A.  All Rights Reserved.                         *
*                                                                          *
***************************************************************************/

#pragma once

#include "glmAssert.h"
#include "glmTypes.h"
#include "glmMemory.h"
#include "glmPODArray.h" // -> for managing list of arrays pointers

#include "glmContainersUtils.h"

// deque is usually, and here, implemented as an array of arrays. 
// ref : http://stackoverflow.com/questions/5728359/stl-internals-deque-implementation
// idea is to have an array of array pointers, growing on both sides by adding elements up to each array fixed container size
// thus first element is best placed at center of array pointers : first element of N/2 indexed array.
// at start array of arrays is constructed with a static size and grown geometrically when array of array size is not sufficient anymore.
// deque is completely ineffective on "insert" method (shifting up to N/2 elements if inserting in middle), this method have been banned from this interface.

//static int getLesserPowOf2(int aNumber)
//{
//	int result = 1;
//	while (result <= aNumber) 
//		result *= 2;
//
//	result /= 2;
//	return result;
//}

#define RETURN_REF_ON(dequeElementIndex) \
	GLM_DEBUG_ASSERT(dequeElementIndex < _size); \
	size_type nWithShift = dequeElementIndex + _headBlockFirstElementIndex; \
	size_type indexInBlock = nWithShift % _blockSize;  \
	size_type blockIndex = nWithShift / _blockSize + _headBlockIndex;  \
	return _blockAdresses[blockIndex][indexInBlock];

#define GET_DEQUE_VALUE_LOCATION(n, blockIndex, valueIndexInBlock) \
    GLM_DEBUG_ASSERT(n <= _size);                                  \
    size_type nWithShift = n + _headBlockFirstElementIndex;        \
    valueIndexInBlock = nWithShift % _blockSize;                   \
    blockIndex = nWithShift / _blockSize + _headBlockIndex;

#define GET_DEQUE_BLOCK_INDEX_FOR_ELEMENT(n, blockIndex) \
    GLM_DEBUG_ASSERT(n <= _size);                        \
    blockIndex = (n + _headBlockFirstElementIndex) / _blockSize + _headBlockIndex;

// was using size_type indexInBlock = nWithShift & (_blockSize - 1); , but can't work with non pow of 2 block size then.

#if GLM_IS_COMPILER_MSVC
#pragma warning(push)
#pragma warning(disable:4127)
#endif

namespace glm
{
	template<typename _Ty>
	class GlmDequeIter;

	template<typename _Ty>
	class GlmDequeConstIter;

	template <typename _Ty>
	class GlmDeque
	{
		friend class GlmDequeIter < _Ty >;
		friend class GlmDequeConstIter < _Ty >;

	public:

		// alloc stuff are not typedef 
		typedef _Ty value_type;
		typedef size_t size_type;
		typedef _Ty& reference;
		typedef const _Ty& const_reference;
		typedef _Ty* pointer;
		typedef const _Ty* const_pointer;
		typedef GlmDequeIter<_Ty> iterator;
		typedef GlmDequeConstIter<_Ty> const_iterator;

		typedef glm::GlmDeque < _Ty > ThisGlmDeque;
		GLM_CLASS_STAT_ID( getDefaultArrayMemoryStatId())

		static const size_type _minimumMapSize = 8;
		static const size_type _blockSize = sizeof(value_type) > 256 ? 1 : 512 / sizeof(value_type); // reserve arrays to fit a pow of 2 number of elements, up to 512 bytes, or one if element greater than 256

	public:

		GlmDeque(const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId()) :
			_memAllocStatId(memAllocStatId),
			_blockAdresses(memAllocStatId),
			_recycledBlocks(memAllocStatId),
			_size(0),
			_headBlockIndex(_minimumMapSize / 2), // place head array index on middle of head array
			_headBlockFirstElementIndex(0)
		{
			GLM_DEBUG_ASSERT_MSG(_blockSize > 2, "Using Deque with elements this big is completely uneffective (handling array of arrays of 1 or 2 element(s)) :  use GlmList or Array instead.");
			_blockAdresses.resize(_minimumMapSize, NULL);
			//_blockAdresses[_headBlockIndex] = allocateBlock();

			// deque now has _minimumMapSize block array entries, index _headBlockIndex point on head array, first available element is _headBlockFirstElementIndex (if any)
		}

		GlmDeque(const GlmDeque& other) :
			_memAllocStatId(other._memAllocStatId),
			_blockAdresses(other.getClassMemoryStatId()),
			_recycledBlocks(other.getClassMemoryStatId()),
			_size(0),
			_headBlockIndex(_minimumMapSize / 2), // place head array index on middle of head array
			_headBlockFirstElementIndex(0)
		{
			_blockAdresses.resize(_minimumMapSize, NULL);
			//_blockAdresses[_headBlockIndex] = allocateBlock();

			*this = other;
		}

		~GlmDeque()
		{
			clear();

			GLM_DEBUG_ASSERT(_size == 0);
		}

		reference front() { GLM_DEBUG_ASSERT(_size > 0); return _blockAdresses[_headBlockIndex][_headBlockFirstElementIndex]; }
		const_reference front() const { GLM_DEBUG_ASSERT(_size > 0); return _blockAdresses[_headBlockIndex][_headBlockFirstElementIndex]; }

		reference back() { GLM_DEBUG_ASSERT(_size > 0); 
			size_type nWithShift = _size - 1 + _headBlockFirstElementIndex; 
			size_type indexInBlock = nWithShift % _blockSize;  
			size_type blockIndex = nWithShift / _blockSize + _headBlockIndex;  
			return _blockAdresses[blockIndex][indexInBlock];	
			//RETURN_REF_ON(_size-1); 
		}
		const_reference back() const { GLM_DEBUG_ASSERT(_size > 0); RETURN_REF_ON(_size - 1); }

		iterator begin() { return iterator(this, 0); }
		const_iterator begin() const { return const_iterator(this, 0); }

		iterator end() { return iterator(this, _size); }
		const_iterator end() const { return const_iterator(this, _size); }

		bool empty() const { return _size == 0; }

		size_type size() const { return _size; }

		// ----------------------------------------------------------------------------------
		GlmDeque& operator=(const GlmDeque& other)
		{
			// for ease of reading, just clear and copy other values here. This is a suboptimal version, but unless it become critical,
			// way better to support/read (else handling used or unused elements in both deque is a hell)
			GLM_DEBUG_ASSERT(&other != this);
			
			clear();

			if (other._size > 0)
			{
				size_type blockCount = other._blockAdresses.size();
				_blockAdresses.resize(blockCount, NULL);
				_headBlockIndex = other._headBlockIndex;
				_headBlockFirstElementIndex = other._headBlockFirstElementIndex;
				_size = other._size;

				size_type lastBlockIndex(0);
				size_type lastIndexInLastBlock(0);
				GET_DEQUE_VALUE_LOCATION(_size - 1, lastBlockIndex, lastIndexInLastBlock);

				// copy elements
				for (size_type i = 0; i < blockCount; ++i)
				{
					if (other._blockAdresses[i] != NULL)
					{
						_blockAdresses[i] = allocateBlock(); // create a matching block

						// get indices of valid blocks to copy

						size_type firstIndexInBlock = i == other._headBlockIndex ? _headBlockFirstElementIndex : 0;
						size_type lastIndexInBlock = i == lastBlockIndex ? lastIndexInLastBlock : _blockSize - 1;

						copyBlock(other._blockAdresses[i], _blockAdresses[i], firstIndexInBlock, lastIndexInBlock); // call placement new with copy constructor on all valid items
					}
				}

			}

			return *this;
		}

		// ----------------------------------------------------------------------------------
		void clear()
		{
			size_t cleanedItems = 0; // should catch up with _size 

			// before _headBlockFirstElementIndex, no element to destroy, start at _headBlockFirstElementIndex
			value_type* headBlock = _blockAdresses[_headBlockIndex];
			if (headBlock != NULL)
			{
				for (size_t iElement = _headBlockFirstElementIndex; iElement < _blockSize && cleanedItems<_size; iElement++)
				{
					(headBlock + iElement)->~value_type();
					cleanedItems++;
				}
			}

			for (size_t iBlock = _headBlockIndex + 1; iBlock < _blockAdresses.size() && cleanedItems<_size; ++iBlock)
			{
				value_type* currentBlock = _blockAdresses[iBlock];
				GLM_UNREFERENCED(currentBlock); // for pod types such as float (not calling destructor on this, compiler optimized)
				for (size_t iElement = 0; iElement < _blockSize && cleanedItems<_size; iElement++)
				{
					(currentBlock + iElement)->~value_type();
					cleanedItems++;
				}				
			}

			GLM_DEBUG_ASSERT(cleanedItems == _size);

			// deallocate reserved memory of all blocks
			size_t blockCount = _blockAdresses.size();
			for (size_t i = 0; i < blockCount; ++i)
			{
				if (_blockAdresses[i] != NULL)
					deallocateBlock(_blockAdresses[i]);
			}
			_blockAdresses.clear();
			_blockAdresses.resize(_minimumMapSize, NULL);
			_headBlockFirstElementIndex = 0;
			_headBlockIndex = _minimumMapSize / 2; // place head array index on middle of head array

			// clear recycled blocks
			for (size_t i = 0; i < _recycledBlocks.size(); i++)
			{
				deallocateBlock(_recycledBlocks[i]);
			}
			_recycledBlocks.clear();

			_size = 0;
		}

		// resizing a queue is very odd, for the moment comment it and check when used what is expected (must cut or grow the back of queue).
		//void resize(size_type n, value_type val = value_type())
		//{
		//}

		// ----------------------------------------------------------------------------------
		reference operator[] (size_type n)
		{
			RETURN_REF_ON(n);
		}
		
		// ----------------------------------------------------------------------------------
		const_reference operator[] (size_type n) const
		{
			RETURN_REF_ON(n);
		}

		// ----------------------------------------------------------------------------------
		reference at(size_type n)
		{
			RETURN_REF_ON(n);
		}

		// ----------------------------------------------------------------------------------
		const_reference at(size_type n) const
		{
			RETURN_REF_ON(n);
		}

		// not implemented, this is not a good idea to use deque if we need this (requires many shift of elements)
		//iterator erase(iterator position);
		//iterator erase(iterator first, iterator last);
		//iterator insert(iterator pos, const value_type& value);
		//void insert(iterator pos, size_type count, const _Ty& value);
		//template< class InputIt >
		//void insert(iterator pos, InputIt first, InputIt last);

		// ----------------------------------------------------------------------------------
		void push_back(const value_type& value)
		{
			// if current array has space on it, add to end
			addValueAfter(value);
		}

		void pop_back()
		{
			removeValueAfter();
		}

		// ----------------------------------------------------------------------------------
		void push_front(const value_type& value)
		{
			addValueBefore(value);
		}

		// ----------------------------------------------------------------------------------
		void pop_front()
		{
			removeValueBefore();
		}

		// ----------------------------------------------------------------------------------
		void resize(size_type n, value_type val = value_type())
		{
			while (_size > n)
			{
				pop_back();
			}

			while (_size < n)
			{
				push_back(val);
			}
		}

		//void swap(list& other);

	protected:
		MemAllocStatId _memAllocStatId;

		// ----------------------------------------------------------------------------------
		static GLM_FORCE_INLINE MemAllocStatId getDefaultArrayMemoryStatId()
		{
			return glm::MemoryStatIds::GolaemShared;
		}

	protected:

		PODArray< value_type* > _blockAdresses;  // all arrays will have a static size. One block is a T[_blockSize] array, thus a T* (constructor/destructor is called by placement, per element)
		PODArray< value_type* > _recycledBlocks; // keep blocks allocated to avoid deallocations/reallocations, until clear is called

		size_t	_size;
		size_t  _headBlockIndex;
		size_t	_headBlockFirstElementIndex; // index of first entry in the head (1st) block.
		// element 0 is accessed via _blockAdresses[_headBlockIndex] + _headBlockFirstElementIndex; 
		// use GET_DEQUE_VALUE_LOCATION to get block index and index in block, from an element index.

	private:

		inline value_type* allocateBlock()
		{
			void* newValue = GLM_ALLOC(sizeof(value_type) * _blockSize, newValue, _memAllocStatId);
			return static_cast<value_type*>(newValue);
		}

		inline void deallocateBlock(value_type*& arrayToDelete)
		{
			GLM_FREE( arrayToDelete,  _memAllocStatId);
			arrayToDelete = NULL;
		}

		inline value_type* getRecycledOrAllocateBlock()
		{
			if (_recycledBlocks.empty())
			{
				return allocateBlock();
			}
			else
			{
				value_type* recycledBlock = _recycledBlocks.back();
				_recycledBlocks.pop_back();
				return recycledBlock;
			}			
		}

		inline void recycleBlock(value_type*& arrayToRecycle)
		{		
			_recycledBlocks.push_back(arrayToRecycle);
			arrayToRecycle = NULL;
		}

		inline void copyBlock(value_type* from, value_type* to, size_type firstValidBlockIndex, size_type lastValidBlockIndex)
		{
			for (size_type i = firstValidBlockIndex; i <= lastValidBlockIndex; ++i)
			{
				new (&(to[i])) value_type(from[i]);
			}
		}

		void addValueAfter(const value_type& value)
		{
			// determine blockIndex in _blockAdresses, and indexInBlock of next element :
			size_type indexInBlock(0);
			size_type blockIndex(0);

			GET_DEQUE_VALUE_LOCATION(_size, blockIndex, indexInBlock); // will return the virtual index for value before first

			// check if we must add a block :
			if (blockIndex >= _blockAdresses.size())
			{
				// if we have available entries in _blockAdresses, just shift pointers to fit in blockAdresses array (integer index -> round to lower position)
				if (_headBlockIndex > 0)
				{
					// shift all pointers backward from half the remaining space
					size_type shiftBackWardAmount = _headBlockIndex - (_headBlockIndex >> 1); // If only one slot available at front, (1 - 1>>1) = 1.
					
					_blockAdresses.shiftBackward(_headBlockIndex, _blockAdresses.size() - _headBlockIndex, shiftBackWardAmount, NULL);

					blockIndex -= shiftBackWardAmount;					
					_headBlockIndex -= shiftBackWardAmount;
				}
				else
				{
					// extend the main adress map at end, double the size (these are pointer arrays, inexpensive)
					_blockAdresses.resize(_blockAdresses.size() * 2, NULL);
				}
			}

			if (_blockAdresses[blockIndex] == NULL)
			{
				_blockAdresses[blockIndex] = getRecycledOrAllocateBlock();
			}

			new (_blockAdresses[blockIndex] + indexInBlock) value_type(value);

			++_size;
		}

		void addValueBefore(const value_type& value)
		{
			// determine blockIndex in _blockAdresses, and indexInBlock of next element :
			size_type blockIndex = _headBlockIndex;
			size_type indexInBlock = _headBlockFirstElementIndex;			

			// if data is on a previous block :			
			if (indexInBlock == 0)
			{
				indexInBlock = _blockSize - 1;

				// if current block is first, reallocate block adresses to get a block before
				if (blockIndex == 0)
				{
					// if we have available entries in _blockAdresses, just shift array pointers to make them fit in blockAdresses array (set them back in middle)
					size_type lastElementBlockIndex = 0;
					GET_DEQUE_BLOCK_INDEX_FOR_ELEMENT(_size - 1, lastElementBlockIndex); // will return the virtual index for value before first

					// if we have space at end, shift the array forward of half remaining space  
					if (lastElementBlockIndex < (_blockAdresses.size()-1))
					{
						// last < size -> (size - last) > 0 -> (size - last + 1 ) > 1 (or >= 2) -> /2 -> shift always >= 1
						size_type shiftForwardAmount = (_blockAdresses.size() - lastElementBlockIndex + 1) >> 1; // If remaining size is 1 only one slot available at back : shift of 1 (for odd values, rounding is done to displace one more than middle)

						_blockAdresses.shiftForward(_headBlockIndex, lastElementBlockIndex - _headBlockIndex + 1, shiftForwardAmount, NULL);
					
						// new blockIndex is first shifted block - 1, first was blockIndex 0, so shifted - 1
						blockIndex = shiftForwardAmount - 1;
					}
					else
					{
						// need to reallocate a block before first one 
						// extend the main adress map at begin, double the size (these are pointer arrays, inexpensive)
						size_type extensionSize = _blockAdresses.size();
						_blockAdresses.insert(_blockAdresses.begin(), _blockAdresses.size(), NULL);
						blockIndex = extensionSize - 1; // this will be assigned to _headBlockIndex later in this method
					}
				}
				else
					--blockIndex;

				if (_blockAdresses[blockIndex] == NULL)
				{
					_blockAdresses[blockIndex] = getRecycledOrAllocateBlock();
				}
			}
			else
			{
				--indexInBlock;
			}

			// if we modify first element, update head block index
			// back one position
			_headBlockIndex = blockIndex;
			_headBlockFirstElementIndex = indexInBlock;
			
			new (_blockAdresses[_headBlockIndex] + _headBlockFirstElementIndex) value_type(value);

			++_size;
		}

		inline void removeValueBefore()
		{
			GLM_DEBUG_ASSERT(_size > 0);

			(_blockAdresses[_headBlockIndex] + _headBlockFirstElementIndex)->~value_type();

			// increment index of first element :
			++_headBlockFirstElementIndex;
			if (_headBlockFirstElementIndex == _blockSize)
			{
				// can delete block :
				recycleBlock(_blockAdresses[_headBlockIndex]);

				_headBlockFirstElementIndex = 0;
				++_headBlockIndex;
				if (_size == 1) // removing last element
				{
					_headBlockIndex = _minimumMapSize / 2; // place head array index on middle of head array
				}
			}

			--_size;
		}

		inline void removeValueAfter()
		{
			GLM_DEBUG_ASSERT(_size > 0);

			size_type indexInBlock(0);
			size_type blockIndex(0);

			GET_DEQUE_VALUE_LOCATION(_size-1, blockIndex, indexInBlock); 

			(_blockAdresses[blockIndex] + indexInBlock)->~value_type();

			// decrement index of last element :
			if (indexInBlock == 0)
			{
				// can delete block :
				recycleBlock(_blockAdresses[blockIndex]);
			}

			--_size;
		}
	};

	// -----------------------------------------------------------------------------------
	// -----------------------------------------------------------------------------------
	// -----------------------------------------------------------------------------------
	template<typename _Ty>
	class GlmDequeIter {

		friend class GlmDeque < _Ty >;
		friend class GlmDequeConstIter < _Ty >; // for constIter constructor based on iteer

	public:

		typedef _Ty value_type;
		typedef size_t size_type;
		typedef class GlmDeque<_Ty> class_type;

		// ----------------------------------------------------------------------------------
		GlmDequeIter(class_type* myDeque = NULL, size_type index = 0) : 
			_owner(myDeque),
			_index(index)
		{}

		// ----------------------------------------------------------------------------------
		GlmDequeIter(const GlmDequeIter& other) :
			_owner(other._owner),
			_index(other._index)
		{}

		// ----------------------------------------------------------------------------------
		GlmDequeIter& operator=(const GlmDequeIter& other)
		{
			_owner = other._owner;
			_index = other._index;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		value_type& getValue() // can modify value on non const iterator
		{
			GLM_DEBUG_ASSERT(_owner != NULL);
			return (*_owner)[_index];
		}

		// ----------------------------------------------------------------------------------
		value_type& operator*() const
		{
			GLM_DEBUG_ASSERT(_owner != NULL);
			return (*_owner)[_index];
		}

		// ----------------------------------------------------------------------------------
		value_type* operator->() const
		{
			GLM_DEBUG_ASSERT(_owner != NULL);
			return &((*_owner)[_index]);
		}

		// ----------------------------------------------------------------------------------
		GlmDequeIter& operator++()
		{
			++_index;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		GlmDequeIter operator++(int)
		{
			GlmDequeIter tmp = *this;
			++*this;
			return (tmp);
		}

		// ----------------------------------------------------------------------------------
		GlmDequeIter& operator--()
		{
			--_index;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		GlmDequeIter operator--(int)
		{
			GlmDequeIter tmp = *this;
			--*this;
			return (tmp);
		}


		// ----------------------------------------------------------------------------------
		GlmDequeIter& operator+=(const size_type offset) 
		{
			_index += offset;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		//friend const GlmDequeIter operator+(const size_type offset, GlmDequeIter out) // friend makes it an external function
		//{
		//	out += offset;
		//	return out;
		//}

		// ----------------------------------------------------------------------------------
		friend const GlmDequeIter operator+(GlmDequeIter out, const size_type offset) // friend makes it an external function
		{
			out += offset;
			return out;
		}

		// ----------------------------------------------------------------------------------
		GlmDequeIter& operator-=(const size_type offset) 
		{
			_index -= offset;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		//friend const GlmDequeIter operator-(const size_type offset, GlmDequeIter out) // friend makes it an external function
		//{
		//	out -= offset;
		//	return out;
		//}

		// ----------------------------------------------------------------------------------
		friend const GlmDequeIter operator-(GlmDequeIter out, const size_type offset) // friend makes it an external function
		{
			out -= offset;
			return out;
		}

		// ----------------------------------------------------------------------------------
		bool operator==(const GlmDequeIter& other) const { return _owner == other._owner && _index == other._index; }
		bool operator!=(const GlmDequeIter& other) const { return _owner != other._owner || _index != other._index; }

	protected:

		class_type* _owner;
		size_type	_index;
	};

	// -----------------------------------------------------------------------------------
	// -----------------------------------------------------------------------------------
	// -----------------------------------------------------------------------------------
	template<typename _Ty>
	class GlmDequeConstIter {

		friend class GlmDeque < _Ty >;
		friend class GlmDequeIter < _Ty >; // for constIter constructor based on iteer

	public:

		typedef _Ty value_type;
		typedef size_t size_type;
		typedef class GlmDeque<_Ty> class_type;

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter(const class_type* myDeque = NULL, size_type index = 0) :
			_owner(myDeque),
			_index(index)
		{}

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter(const GlmDequeConstIter& other) :
			_owner(other._owner),
			_index(other._index)
		{}

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter(const GlmDequeIter<_Ty>& other) :
			_owner(other._owner),
			_index(other._index)
		{}

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter& operator=(const GlmDequeConstIter<_Ty>& other)
		{
			_owner = other._owner;
			_index = other._index;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		const value_type& getValue() // cannot modify value on non const iterator
		{
			GLM_DEBUG_ASSERT(_owner != NULL);
			return (*_owner)[_index];
		}

		// ----------------------------------------------------------------------------------
		const value_type& operator*() const
		{
			GLM_DEBUG_ASSERT(_owner != NULL);
			return (*_owner)[_index];
		}

		// ----------------------------------------------------------------------------------
		const value_type* operator->() const
		{
			GLM_DEBUG_ASSERT(_owner != NULL);
			return &((*_owner)[_index]);
		}


		// ----------------------------------------------------------------------------------
		GlmDequeConstIter& operator++()
		{
			++_index;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter operator++(int)
		{
			GlmDequeConstIter tmp = *this;
			++*this;
			return (tmp);
		}

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter& operator--()
		{
			--_index;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter operator--(int)
		{
			GlmDequeConstIter tmp = *this;
			--*this;
			return (tmp);
		}

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter& operator+=(const size_type offset) {
			_index += offset;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		//friend const GlmDequeConstIter operator+(const size_type offset, GlmDequeConstIter out) // friend makes it an external function
		//{
		//	out += offset;
		//	return out;
		//}

		// ----------------------------------------------------------------------------------
		friend const GlmDequeConstIter operator+(GlmDequeConstIter out, const size_type offset) // friend makes it an external function
		{
			out += offset;
			return out;
		}

		// ----------------------------------------------------------------------------------
		GlmDequeConstIter& operator-=(const size_type offset) {
			_index -= offset;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		//friend const GlmDequeConstIter operator-(const size_type offset, GlmDequeConstIter out) // friend makes it an external function
		//{
		//	out -= offset;
		//	return out;
		//}

		// ----------------------------------------------------------------------------------
		friend const GlmDequeConstIter operator-(GlmDequeConstIter out, const size_type offset) // friend makes it an external function
		{
			out -= offset;
			return out;
		}

		// ----------------------------------------------------------------------------------
		bool operator==(const GlmDequeConstIter& other) const { return _owner == other._owner && _index == other._index; }
		bool operator!=(const GlmDequeConstIter& other) const { return _owner != other._owner || _index != other._index; }

	protected:

		const class_type* _owner;
		size_type	_index;
	};

	//no operator overloading yet (unused)
	//template<class _Ty> bool operator==(GlmDeque<_Ty>& lhs, GlmDeque<_Ty>& rhs);
	//template<class _Ty> bool operator!=(GlmDeque<_Ty>& lhs, GlmDeque<_Ty>& rhs);
	//template<class _Ty> bool operator<(GlmDeque<_Ty>& lhs, GlmDeque<_Ty>& rhs);
	//template<class _Ty> bool operator>(GlmDeque<_Ty>& lhs, GlmDeque<_Ty>& rhs);
	//template<class _Ty> bool operator<=(GlmDeque<_Ty>& lhs, GlmDeque<_Ty>& rhs);
	//template<class _Ty> bool operator>=(GlmDeque<_Ty>& lhs, GlmDeque<_Ty>& rhs);
}

#if GLM_IS_COMPILER_MSVC
#pragma warning(pop)
#endif

