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

#pragma once

#include "glmAssert.h"
#include "glmTypes.h"
#include "glmMemory.h"
#include "glmRecyclerT.h"

#include "glmContainersUtils.h"

namespace glm
{
	template<typename _Ty>
	class GlmListIter;

	template<typename _Ty>
	class GlmListConstIter;

	template <typename _Ty>
	class GlmList
	{
		friend class GlmListIter < _Ty > ;
		friend class GlmListConstIter < _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 GlmListIter<_Ty> iterator;
		typedef GlmListConstIter<_Ty> const_iterator;
		
		typedef glm::GlmList < _Ty > ThisGlmList;
		GLM_CLASS_STAT_ID( getDefaultArrayMemoryStatId())

	protected:

		class GlmListNode
		{
		public:
			GLM_CLASS_STAT_ID( ThisGlmList::getDefaultArrayMemoryStatId())

			value_type _data;
			GlmListNode* _prev;
			GlmListNode* _next;

			GlmListNode(const value_type & d = value_type(), GlmListNode * p = NULL, GlmListNode * n = NULL)
				: _data(d), _prev(p), _next(n) { }
		};

	public:

		GlmList(const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId()) :
			_memAllocStatId(memAllocStatId),
			_head(NULL),
			_tail(NULL),
			_size(0),
			_nodeRecycler(8, memAllocStatId)
		{
			_head = _nodeRecycler.obtain();// GLM_NEW( GlmListNode, _head,  memAllocStatId);
			_tail = _nodeRecycler.obtain();//GLM_NEW( GlmListNode, _tail,  memAllocStatId);
			_head->_next = _tail;
			_tail->_prev = _head;
		}

		GlmList(size_t reservedSize, const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId()) :
			_memAllocStatId(memAllocStatId),
			_head(NULL),
			_tail(NULL),
			_size(0),
			_nodeRecycler(reservedSize, memAllocStatId)
		{
			_head = _nodeRecycler.obtain();// GLM_NEW( GlmListNode, _head,  memAllocStatId);
			_tail = _nodeRecycler.obtain();//GLM_NEW( GlmListNode, _tail,  memAllocStatId);
			_head->_next = _tail;
			_tail->_prev = _head;
		}


		GlmList(const GlmList& other) :
			_memAllocStatId(other._memAllocStatId),
			_head(NULL),
			_tail(NULL),
			_size(0),
			_nodeRecycler(other.size(), other._memAllocStatId)
		{
			_head = _nodeRecycler.obtain(); // GLM_NEW( GlmListNode, _head,  _memAllocStatId);
			_tail = _nodeRecycler.obtain(); // GLM_NEW( GlmListNode, _tail,  _memAllocStatId);
			_head->_next = _tail;
			_tail->_prev = _head;

			*this = other;
		}

		~GlmList()
		{
			clear(); // move everything in recycledItems, so that their destructor is called. (head and tail are untouched) -> not necessary to produce moves for nothing
			//-> fact is: it might produce a memory leak if clear is not called (the destructor is called from the recycle method, which is only called in pop functions, but not in recycler clear)
			//_nodeRecycler.recycle(_head);
			//_nodeRecycler.recycle(_tail);

			// this will free all allocated memory without useless data moves
			_nodeRecycler.clear(); // actually free memory (clear have put back everything in recycler first). head and tail are not used after that, they will be cleared here too

			//GLM_DEBUG_ASSERT(_size == 0);
						
			//GLM_DELETE(_head,  _memAllocStatId);
			//GLM_DELETE(_tail,  _memAllocStatId);
		}

		reference front() { GLM_DEBUG_ASSERT(_size > 0); return _head->_next->_data; }
		const_reference front() const { GLM_DEBUG_ASSERT(_size > 0); return _head->_next->_data; }

		reference back() { GLM_DEBUG_ASSERT(_size > 0); return _tail->_prev->_data; }
		const_reference back() const { GLM_DEBUG_ASSERT(_size > 0); return _tail->_prev->_data; }

		iterator begin() { return iterator(_head->_next); }
		const_iterator begin() const { return const_iterator(_head->_next); }

		iterator end() { return iterator(_tail); }
		const_iterator end() const { return const_iterator(_tail); }

		iterator rbegin() { return iterator(_tail->_prev); }
		const_iterator rbegin() const { return const_iterator(_tail->_prev); }

		iterator rend() { return iterator(_head); }
		const_iterator rend() const { return const_iterator(_head); }

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

		size_type size() const { return _size; }

		// ----------------------------------------------------------------------------------
		GlmList& operator=(const GlmList& other)
		{
			clear();
			const_iterator otherIte = other.begin();
			const_iterator otherEndIte = other.end();
			while (otherIte != otherEndIte)
			{ 
				this->push_back(otherIte.getValue());
				otherIte++;
			}
			return *this;
		}

		void clear() 
		{
			while (!empty())
				pop_front();
		}

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

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

		iterator erase(iterator position)
		{
			GLM_DEBUG_ASSERT(position != end());
			GlmListNode* prevNode = position._node->_prev;
			GlmListNode* nextNode = position._node->_next;
			nextNode->_prev = prevNode;
			prevNode->_next = nextNode;

			_nodeRecycler.recycle(position._node);
			//delete position._node;

			--_size;

			return iterator(nextNode);
		}

		//iterator erase(iterator first, iterator last);

		void remove(const value_type& val)
		{
			iterator removeIte = begin();
			iterator endIte = end();
			while (removeIte != endIte)
			{
				if (removeIte.getValue() == val)
				{
					removeIte = erase(removeIte);
				}
				else
				{
					++removeIte;
				}
			}
		}

		iterator insert(iterator pos, const value_type& value)
		{
			GlmListNode* newNode = _nodeRecycler.obtain();// GLM_NEW( GlmListNode, newNode,  _memAllocStatId,  value);
			newNode->_data = value;

			GlmListNode* posNode = pos._node;
		
			newNode->_next = posNode;
			newNode->_prev = posNode->_prev;
			posNode->_prev->_next = newNode;
			posNode->_prev = newNode;

			++_size;
			/*
			if (posNode != _head)
			{
				newNode->_prev = posNode->_prev;
				posNode->_prev = newNode;
			}
			else
			{
				_head->_prev = newNode;
				_head = newNode;
			}*/

			return iterator(newNode);
		}

		//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)
		{
			GlmListNode* newNode = _nodeRecycler.obtain();//GLM_NEW( GlmListNode, newNode,  _memAllocStatId,  value); 
			newNode->_data = value;
			newNode->_next = _tail;
			newNode->_prev = _tail->_prev;
			_tail->_prev->_next = newNode;
			_tail->_prev = newNode;

			_size++;
		}


		value_type& addOneFront()
		{
			GlmListNode* newNode = _nodeRecycler.obtain();//GLM_NEW( GlmListNode, newNode,  _memAllocStatId,  value); 
			//newNode->_data = value; // value is let as is
			newNode->_next = _head->_next;
			newNode->_prev = _head;
			_head->_next->_prev = newNode;
			_head->_next = newNode;

			_size++;

			return newNode->_data;
		}

		value_type& addOneBack()
		{
			GlmListNode* newNode = _nodeRecycler.obtain();//GLM_NEW( GlmListNode, newNode,  _memAllocStatId,  value); 
			//newNode->_data = value; // value is let as is
			newNode->_next = _tail;
			newNode->_prev = _tail->_prev;
			_tail->_prev->_next = newNode;
			_tail->_prev = newNode;

			_size++;

			return newNode->_data;
		}

		void pop_back()
		{
			GLM_DEBUG_ASSERT(_size > 0);

			GlmListNode* nodeToDelete = _tail->_prev;
			nodeToDelete->_prev->_next = _tail;
			_tail->_prev = nodeToDelete->_prev;
			_nodeRecycler.recycle(nodeToDelete); //GLM_DELETE(nodeToDelete,  _memAllocStatId);
			_size--;
		}

		void push_front(const value_type& value)
		{
			GlmListNode* newNode = _nodeRecycler.obtain();//GLM_NEW( GlmListNode, newNode,  _memAllocStatId,  value);
			newNode->_data = value;
			newNode->_prev = _head;
			newNode->_next = _head->_next;
			_head->_next->_prev = newNode;
			_head->_next = newNode;

			_size++;
		}

		void pop_front()
		{
			GLM_DEBUG_ASSERT(_size > 0);

			GlmListNode* nodeToDelete = _head->_next;
			nodeToDelete->_next->_prev = _head;
			_head->_next = nodeToDelete->_next;
			_nodeRecycler.recycle(nodeToDelete); //GLM_DELETE(nodeToDelete,  _memAllocStatId);			

			_size--;
		}

		//void resize(size_type count, _Ty value = _Ty());

		//void swap(list& other);

	protected:
		MemAllocStatId _memAllocStatId;

		// ----------------------------------------------------------------------------------
		static GLM_FORCE_INLINE MemAllocStatId getDefaultArrayMemoryStatId()
		{
			return glm::MemoryStatIds::GolaemShared;
		}
					
	private:
		GlmListNode* _head; // value before first valid element, used as a sentinel
		GlmListNode* _tail; // value after last valid element, used as a sentinel

		size_t		_size;

		RecyclerT<GlmListNode> _nodeRecycler;
	};

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

		friend class GlmList < _Ty >;
		friend class GlmListConstIter < _Ty >; // for constIter constructor based on iteer

	public:

		typedef _Ty value_type;
		typedef typename GlmList<_Ty>::GlmListNode	node_type;

		// ----------------------------------------------------------------------------------
		GlmListIter(node_type* aNode = NULL) : _node(aNode)
		{}

		// ----------------------------------------------------------------------------------
		GlmListIter(const GlmListIter& other) : _node(other._node)
		{}

		// ----------------------------------------------------------------------------------
		GlmListIter& operator=(const GlmListIter& other)
		{
			_node = other._node;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		_Ty& getValue() // can modify value on non const iterator
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			return _node->_data;
		}
		
		// ----------------------------------------------------------------------------------
		value_type& operator*() const
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			return _node->_data;
		}

		// ----------------------------------------------------------------------------------
		value_type* operator->() const
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			return &(_node->_data);
		}

		// ----------------------------------------------------------------------------------
		GlmListIter& operator++()
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			_node = _node->_next;
			return *this;
		}

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

		// ----------------------------------------------------------------------------------
		GlmListIter& operator--()
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			_node = _node->_prev;
			return *this;

		}

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

		// ----------------------------------------------------------------------------------
		bool operator==(const GlmListIter& other) const { return _node == other._node; }
		bool operator!=(const GlmListIter& other) const { return _node != other._node; }
		bool operator==(const GlmListConstIter<_Ty>& other) const { return _node == other._node; }
		bool operator!=(const GlmListConstIter<_Ty>& other) const { return _node != other._node; }


	protected:

		node_type*	_node;
	};

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

		friend class GlmList < _Ty >;
		friend class GlmListIter < _Ty >; // for constIter constructor based on iteer

	public:

		typedef _Ty value_type;
		typedef typename GlmList<_Ty>::GlmListNode	node_type;

		// ----------------------------------------------------------------------------------
		GlmListConstIter(node_type* aNode = NULL) : _node(aNode)
		{}

		// ----------------------------------------------------------------------------------
		GlmListConstIter(const GlmListConstIter<_Ty>& other) : _node(other._node)
		{}
		
		// ----------------------------------------------------------------------------------
		GlmListConstIter(const GlmListIter<_Ty>& other) : _node(other._node)
		{}

		// ----------------------------------------------------------------------------------
		GlmListConstIter& operator=(const GlmListConstIter<_Ty>& other)
		{
			_node = other._node;
			return *this;
		}

		// ----------------------------------------------------------------------------------
		const _Ty& getValue() // cannot modify value on non const iterator
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			return _node->_data;
		}

		// ----------------------------------------------------------------------------------
		const value_type& operator*() const
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			return _node->_data;
		}

		// ----------------------------------------------------------------------------------
		const value_type* operator->() const
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			return &(_node->_data);
		}


		// ----------------------------------------------------------------------------------
		GlmListConstIter& operator++()
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			_node = _node->_next;
			return *this;
		}

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

		// ----------------------------------------------------------------------------------
		GlmListConstIter& operator--()
		{
			GLM_DEBUG_ASSERT(_node != NULL);
			_node = _node->_prev;
			return *this;
		}

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

		// ----------------------------------------------------------------------------------
		bool operator==(const GlmListConstIter<_Ty>& other) const { return _node == other._node; }
		bool operator!=(const GlmListConstIter<_Ty>& other) const { return _node != other._node; }
		bool operator==(const GlmListIter<_Ty>& other) const { return _node == other._node; }
		bool operator!=(const GlmListIter<_Ty>& other) const { return _node != other._node; }

	protected:

		node_type*	_node;
	}; 

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