#ifndef TCG_LIST_H

#define TCG_LIST_H

// tcg includes

#include "alignment.h"

#include "macros.h"

// STD includes

#include <cstddef> // size_t</cstddef>

#include <new>	 // placement new</new>

#include <vector></vector>

#include "assert.h"

// Discriminate rvalues support - either use Boost's config.hpp for automatic lookup,

// or deal with it manually

#ifndef TCG_RVALUES_SUPPORT

#include <boost config.hpp=""></boost>

#ifdef BOOST_NO_RVALUE_REFERENCES

#define TCG_RVALUES_SUPPORT 0

#else

#define TCG_RVALUES_SUPPORT 1

#endif

#endif

#if (TCG_RVALUES_SUPPORT > 0)

// Perfect forwarding macros

#define TCG_FORWARD_TYPE(TheType) TheType##__ &&

#define TCG_FORWARD_TEMPLATE(TheType) template <typename thetype##__=""></typename>

#define TCG_FORWARD(TheType, Val) std::forward<thetype##__>(Val)</thetype##__>

#else

// Common const reference forwarding macros

#define TCG_FORWARD_TYPE(TheType) const TheType &

#define TCG_FORWARD_TEMPLATE(TheType)

#define TCG_FORWARD(TheType, Val) Val

#endif

/*! \file     tcg_list.h

    \brief    This file contains the implementation of an indexed list,

              a list class based on a random access sequential container.

*/

//************************************************************************************

//    Preliminaries

//************************************************************************************

namespace tcg

{

static const size_t _neg = -1,

					_invalid = -2;

} // namespace tcg

//************************************************************************************

//    Indexed list node  definition

//************************************************************************************

namespace tcg

{

/*!

  \brief    Internal node class used in the implementation of a tcg::list_base.

*/

template <typename t=""></typename>

struct _list_node {

	TCG_STATIC_ASSERT(sizeof(T) == sizeof(aligned_buffer<t>));</t>

	aligned_buffer<t> m_val;</t>

	size_t m_prev, m_next;

	TCG_DEBUG(T &m_t;) // Provided for debuggers' convenience

public:

	_list_node() : m_prev(_neg), m_next(_invalid) TCG_DEBUG2(, m_t(value()))

	{

	}

	_list_node(const T &val) : m_prev(_neg), m_next(_neg) TCG_DEBUG2(, m_t(value()))

	{

		constructValue(val);

	}

	~_list_node()

	{

		if (isValid())

			destroyValue();

	}

	_list_node(const _list_node &other)

		: m_prev(other.m_prev), m_next(other.m_next) TCG_DEBUG2(, m_t(value()))

	{

		if (other.isValid())

			constructValue(other.value());

	}

	_list_node &operator=(const _list_node &other)

	{

		if (isValid())

			if (other.isValid())

				value() = other.value();

			else

				destroyValue();

		else

			constructValue(other.value());

		m_prev = other.m_prev, m_next = other.m_next;

		return *this;

	}

	const T &value() const { return reinterpret_cast<const &="" t="">(m_val.m_buf); }</const>

	T &value() { return reinterpret_cast<t &="">(m_val.m_buf); }</t>

	bool isValid() const { return (m_next != _invalid); }

	void invalidate()

	{

		assert(isValid());

		destroyValue();

		m_next = _invalid;

	}

#if (TCG_RVALUES_SUPPORT > 0)

	_list_node(T &&val) : m_prev(_neg), m_next(_neg) TCG_DEBUG2(, m_t(value()))

	{

		constructValue(std::move(val));

	}

	_list_node(_list_node &&other)

		: m_prev(other.m_prev), m_next(other.m_next) TCG_DEBUG2(, m_t(value()))

	{

		if (other.isValid())

			constructValue(std::move(other.value())), other.invalidate();

	}

	_list_node &operator=(_list_node &&other)

	{

		if (isValid())

			if (other.isValid())

				value() = other.value();

			else

				destroyValue();

		else

			constructValue(std::move(other.value()));

		value() = std::move(other.value());

		m_prev = other.m_prev, m_next = other.m_next;

		return *this;

	}

#endif

public:

	void constructValue(const T &val) { new (m_val.m_buf) T(val); }

	void destroyValue() { value().~T(); }

#if (TCG_RVALUES_SUPPORT > 0)

	void constructValue(T &&val)

	{

		new (m_val.m_buf) T(std::move(val));

	}

#endif

};

//************************************************************************************

//    Base indexed list  definition

//************************************************************************************

/*!

  \brief    Base class for list-like containers based on <tt>tcg::list</tt>'s

            indexed list implementation.

  \details  This class implements a barebone container class which manages

            a collection of nodes stored in an iternal random access container.

            Nodes management is limited to the \a acquisition and \a release

            of individual nodes (see the buyNode() and sellNode() functions).

            Links between list nodes must be managed externally.

  \sa       Template class \p tcg::list for an explanation of the indexed list

            container concept.

*/

template <typename t=""></typename>

class list_base

{

public:

	typedef T value_type;

	typedef ::size_t size_t;

	static const size_t _neg = -1;

protected:

	typedef _list_node<t> list_node;</t>

	std::vector<list_node> m_vector;</list_node>

	size_t m_size;

	size_t m_clearedHead;

public:

	struct const_iterator : public std::iterator<std::bidirectional_iterator_tag, const="" t=""> {</std::bidirectional_iterator_tag,>

		const list_base *m_list;

		size_t m_idx;

		TCG_DEBUG(const list_node *m_node;) // Provided for debuggers' convenience

	public:

		typedef const T value_type;

		typedef const T *pointer;

		typedef const T &reference;

	public:

		const_iterator() {}

		const_iterator(const list_base *list, size_t idx)

			: m_list(list), m_idx(idx) { TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]); }

		size_t index() const { return m_idx; }

		reference operator*() const { return (*m_list)[m_idx]; }

		pointer operator->() const { return &(*m_list)[m_idx]; }

		const_iterator operator++(int)

		{

			const_iterator temp(*this);

			operator++();

			return temp;

		}

		const_iterator &operator++()

		{

			m_idx = m_list->m_vector[m_idx].m_next;

			TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]);

			return *this;

		}

		const_iterator operator--(int)

		{

			const_iterator temp(*this);

			operator--();

			return temp;

		}

		const_iterator &operator--()

		{

			m_idx = m_list->m_vector[m_idx].m_prev;

			TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]);

			return *this;

		}

		bool operator==(const const_iterator &it) const { return (m_idx == it.m_idx); }

		bool operator!=(const const_iterator &it) const { return (m_idx != it.m_idx); }

	};

	struct iterator : public const_iterator {

	public:

		typedef T value_type;

		typedef T *pointer;

		typedef T &reference;

	public:

		iterator() {}

		iterator(list_base *list, size_t idx) : const_iterator(list, idx) {}

		reference operator*() const { return const_cast<reference>(const_iterator::operator*()); }</reference>

		pointer operator->() const { return const_cast<pointer>(const_iterator::operator->()); }</pointer>

		iterator operator++(int)

		{

			iterator temp(*this);

			operator++();

			return temp;

		}

		iterator &operator++()

		{

			const_iterator::operator++();

			return *this;

		}

		iterator operator--(int)

		{

			iterator temp(*this);

			operator--();

			return temp;

		}

		iterator &operator--()

		{

			const_iterator::operator--();

			return *this;

		}

	};

	friend struct iterator;

	friend struct const_iterator;

public:

	list_base() : m_size(0), m_clearedHead(_neg) {}

	list_base(size_t count, const T &val)

		: m_vector(count, list_node(val)), m_size(count), m_clearedHead(_neg)

	{

		assert(m_size >= 0);

		for (size_t i = 0; i < m_size; ++i)

			m_vector[i].m_prev = i - 1, m_vector[i].m_next = i + 1;

		if (m_size > 0)

			m_vector[m_size - 1].m_next = _neg;

	}

	template <typename init=""></typename>

	list_base(InIt begin, InIt end)

		: m_vector(begin, end), m_size(m_vector.size()), m_clearedHead(_neg)

	{

		assert(m_size >= 0);

		for (size_t i = 0; i < m_size; ++i)

			m_vector[i].m_prev = i - 1, m_vector[i].m_next = i + 1;

		if (m_size > 0)

			m_vector[m_size - 1].m_next = _neg;

	}

	//-----------------------------------------------------------------------------------------

	list_base(const list_base &other)

		: m_vector(other.m_vector), m_size(other.m_size), m_clearedHead(other.m_clearedHead) {}

	list_base &operator=(const list_base &other)

	{

		// Note: not using the copy-and-swap idiom. We want to attempt preservation

		// of m_vector's buffer in case its current capacity is sufficient.

		m_size = other.m_size;

		m_clearedHead = other.m_clearedHead;

		// A clear must be performed before the actual =. It's necessary to prevent copying to

		// objects that were already destroyed - but are still in the vector as zombies.

		// In this case, the value-to-value vector::operator= would assume that the

		// assigned-to object is NOT a zombie - and would attempt its release, which is UB!

		m_vector.clear();

		m_vector = other.m_vector;

		return *this;

	}

#if (TCG_RVALUES_SUPPORT > 0)

	list_base(list_base &&other)

		: m_vector(std::move(other.m_vector)), m_size(other.m_size), m_clearedHead(other.m_clearedHead)

	{

	}

	list_base &operator=(list_base &&other)

	{

		swap(*this, std::forward<list_base>(other));</list_base>

		return *this;

	}

#endif

	T &operator[](size_t idx)

	{

		assert(idx < m_vector.size() && isValid(idx));

		return m_vector[idx].value();

	}

	const T &operator[](size_t idx) const

	{

		assert(idx < m_vector.size() && isValid(idx));

		return m_vector[idx].value();

	}

	bool isValid(size_t idx) const { return m_vector[idx].isValid(); }

	size_t size() const { return m_size; }

	size_t nodesCount() const { return m_vector.size(); }

	void reserve(size_t size) { m_vector.reserve(size); }

	size_t capacity() const { return m_vector.capacity(); }

	void clear()

	{

		m_size = 0;

		m_clearedHead = _neg;

		m_vector.clear();

	}

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

	void _swap(list_base &a, list_base &b)

	{

		std::swap(a.m_size, b.m_size);

		std::swap(a.m_clearedHead, b.m_clearedHead);

		a.m_vector.swap(b.m_vector);

	}

#if (TCG_RVALUES_SUPPORT > 0)

	void _swap(list_base &a, list_base &&b)

	{

		a.m_size = b.m_size;

		a.m_clearedHead = b.m_clearedHead;

		a.m_vector.swap(b.m_vector);

	}

	void _swap(list_base &&a, list_base &b)

	{

		swap(b, std::move(a));

	}

#endif

	//-----------------------------------------------------------------------------------------

	//! Constructs from a range of (index, value) pairs

	template <typename forit=""></typename>

	list_base(ForIt begin, ForIt end, size_t nodesCount)

	{

		// Initialize the vector with invalid nodes up to the required nodes count

		m_vector.resize(nodesCount, list_node());

		// Iterate the range and add corresponding value pairs

		size_t lastIdx = _neg;

		for (; begin != end; ++begin) {

			size_t idx = (*begin).first;

			assert(idx >= 0);

			// Further resize the vector with holes if necessary

			if (idx >= m_vector.size()) {

				// The nodesCount hint was not sufficient. Thus, we have to readjust the correct minimal

				// allocation size. Let's do it now with a further single pass toward the end.

				size_t newSize = m_vector.size();

				for (ForIt it = begin; it != end; ++it)

					newSize = std::max(newSize, size_t((*it).first) + 1);

				m_vector.resize(newSize, list_node());

			}

			// Place current node in the vector

			list_node &node = m_vector[idx];

			new (&node) list_node((*begin).second);

			// Link the node

			node.m_prev = lastIdx;

			if (lastIdx != _neg)

				m_vector[lastIdx].m_next = idx;

			lastIdx = idx;

		}

		// Finally, make up a consistent links chain for holes

		lastIdx = _neg;

		size_t n, nCount = m_vector.size();

		for (n = 0; n != nCount; ++n) {

			list_node &node = m_vector[n];

			if (!node.isValid())

				node.m_prev = lastIdx, lastIdx = n;

		}

		m_clearedHead = lastIdx;

	}

	//-----------------------------------------------------------------------------------------

protected:

	TCG_FORWARD_TEMPLATE(T)

	size_t buyNode(TCG_FORWARD_TYPE(T) val)

	{

		size_t nodeIdx;

		list_node *node;

		++m_size;

		if (m_clearedHead != _neg) {

			assert(m_clearedHead < m_vector.size());

			// Take the last cleared element

			nodeIdx = m_clearedHead;

			node = &m_vector[nodeIdx];

			m_clearedHead = node->m_prev;

		} else {

			m_vector.push_back(list_node());

			nodeIdx = m_vector.size() - 1;

			node = &m_vector[nodeIdx];

		}

		// Construct the node's value

		node->constructValue(TCG_FORWARD(T, val));

		return nodeIdx;

	}

	//-----------------------------------------------------------------------------------------

	void sellNode(size_t idx)

	{

		assert(isValid(idx));

		list_node &node = m_vector[idx];

		// Relink neighbours

		if (node.m_prev != _neg)

			m_vector[node.m_prev].m_next = node.m_next;

		if (node.m_next != _neg)

			m_vector[node.m_next].m_prev = node.m_prev;

		// Explicitly invoke the node's destructor

		node.invalidate();

		// Now, the node is a zombie - still, use its indices data to remember the list

		// of unused nodes

		// Remember the last cleared element in element.m_prev

		node.m_prev = m_clearedHead;

		m_clearedHead = idx;

		--m_size;

	}

	//-----------------------------------------------------------------------------------------

	void sellNodes(size_t begin, size_t end)

	{

		for (size_t i = begin; i != end; i = m_vector[i].m_next)

			sellNode(i);

	}

	//-----------------------------------------------------------------------------------------

	void move(size_t afterDst, size_t &dstBegin, size_t &dstRBegin,

			  size_t srcBegin, size_t srcEnd, size_t srcRBegin)

	{

		if (srcBegin == _neg || srcBegin == afterDst)

			return;

		// afterDst-1 -> srcBegin

		{

			size_t beforeDst = (afterDst == _neg) ? dstRBegin : m_vector[afterDst].m_prev;

			m_vector[srcBegin].m_prev = beforeDst;

			if (beforeDst != _neg)

				m_vector[beforeDst].m_next = srcBegin;

			else

				dstBegin = srcBegin;

		}

		// srcEnd-1 -> afterDst

		{

			size_t srcLast = (srcEnd == _neg) ? srcRBegin : m_vector[srcEnd].m_prev;

			m_vector[srcLast].m_next = afterDst; // NOTE: srcLast cannot be _neg

			if (afterDst != _neg)

				m_vector[afterDst].m_prev = srcLast;

			else

				dstRBegin = srcLast;

		}

	}

};

//************************************************************************************

//    Indexed list  definition

//************************************************************************************

/*!

  \brief    Double linked list container class with indexed access to elements.

  \details  This class is the result of implementing a double linked list using a

            dynamic random access sequential container as the underlying pool for

            the list's nodes.

            This is somewhat different than supplying a custom allocator to an existing

            list implementation, like \p std::list, since:

              
  No memory model of the underlying container is actually

                    required.

              
  The underlying container provides explicit access to nodes

                    using their associated insertion indexes, so \p std::list

                    could not be used as-is.

\n

            The nodes pool (see \p list_base) is an internal \a lazy container that

            saves released nodes \a without actually deallocating them (of course,

            their content is properly destroyed). They are rather stored into an

            internal \a stack of released nodes, ready to be reacquired.

              \par Features

              \li  Insertion indexes are automatically generated keys with the same

                   access time of the undelying container (typically super-fast

                   \p O(1)).

              \li  Stable indexes and iterators with respect to every operation.

              \li  Copying an indexed list \a preserves the original indexes.

              \li  Indexes are process independent - they can be saved

                   on file and restored later (although you probably want to

                   \a squeeze the list before saving).

              \par Use cases

            This class is surprisingly useful for cross-referencing.

            A graph data structure, for example, can be implemented using a pair of

            indexed lists for vertexes and edges.

              \par Known issues

            The lazy nature of this container class may require \a squeezing the list's

            content at strategic places in your code, as noted before.

            Beware that composite cross-referencing may be hard to track \a precisely

            during this particular operation.

  \remark   Current implementation explicitly uses an \p std::vector class as the

            underlying random access container. Future improvements will make the

            container class a template parameter.

  \sa       Template class \p tcg::Mesh for a notable use case.

*/

template <typename t=""></typename>

class list : public list_base<t></t>

{

	size_t m_begin, m_rbegin;

protected:

	typedef typename list_base<t>::list_node list_node;</t>

	using list_base<t>::m_vector;</t>

public:

	struct iterator : public list_base<t>::iterator {</t>

		iterator() {}

		iterator(list *l, size_t idx) : list_base<t>::iterator(l, idx) {}</t>

		iterator &operator++()

		{

			list_base<t>::iterator::operator++();</t>

			return *this;

		}

		iterator &operator--()

		{

			if (this->m_idx == _neg)

				operator=(static_cast<list *="">(this->m_list)->last());</list>

			else

				list_base<t>::iterator::operator--();</t>

			return *this;

		}

		iterator operator++(int)

		{

			iterator temp(*this);

			operator++();

			return temp;

		}

		iterator operator--(int)

		{

			iterator temp(*this);

			operator--();

			return temp;

		}

	};

	struct const_iterator : public list_base<t>::const_iterator {</t>

		const_iterator() {}

		const_iterator(const list *l, size_t idx) : list_base<t>::const_iterator(l, idx) {}</t>

		const_iterator &operator++()

		{

			list_base<t>::const_iterator::operator++();</t>

			return *this;

		}

		const_iterator &operator--()

		{

			if (this->m_idx == _neg)

				operator=(static_cast<const *="" list="">(this->m_list)->last());</const>

			else

				list_base<t>::const_iterator::operator--();</t>

			return *this;

		}

		const_iterator operator++(int)

		{

			const_iterator temp(*this);

			operator++();

			return temp;

		}

		const_iterator operator--(int)

		{

			const_iterator temp(*this);

			operator--();

			return temp;

		}

	};

public:

	list() : m_begin(_neg), m_rbegin(_neg) {}

	list(size_t count, const T &val) : list_base<t>(count, val), m_begin(0), m_rbegin(count - 1) {}</t>

	template <typename init=""></typename>

	list(InIt begin, InIt end) : list_base<t>(begin, end), m_begin(list_base<t>::m_size ? 0 : _neg), m_rbegin(list_base<t>::m_size - 1) {}</t></t></t>

	//! Constructs from a range of (index, value) pairs

	template <typename bidit=""></typename>

	list(BidIt begin, BidIt end, size_t nodesCount) : list_base<t>(begin, end, nodesCount)</t>

	{

		if (begin != end)

			m_begin = (*begin).first, m_rbegin = (*--end).first;

	}

	//-----------------------------------------------------------------------------------------

	list(const list &other) : list_base<t>(other), m_begin(other.m_begin), m_rbegin(other.m_rbegin) {}</t>

	/*!

    \warning  \p tcg::list has a different copy behavior from other container classes, since

              it is intended to preserve the source's node indices in the process.

              This means that no value-to-value assignment can take place, and thus <tt>operator=</tt>'s

              behavior is equivalent to first clearing it, and then copy-constructing each value.

              This typically leads to performance penalties with respect to other container classes that

              implement value-to-value assignments, like \p std::vector in case its capacity is not exceeded.

  */

	list &operator=(const list &other)

	{

		m_begin = other.m_begin, m_rbegin = other.m_rbegin;

		list_base<t>::operator=(other);</t>

		return *this;

	}

#if (TCG_RVALUES_SUPPORT > 0)

	list(list &&other) : list_base<t>(std::forward<list_base<t>>(other)), m_begin(other.m_begin), m_rbegin(other.m_rbegin)</list_base<t></t>

	{

	}

	list &operator=(list &&other)

	{

		swap(*this, std::forward<list>(other));</list>

		return *this;

	}

#endif

	//-----------------------------------------------------------------------------------------

	TCG_FORWARD_TEMPLATE(T)

	size_t insert(size_t idx, TCG_FORWARD_TYPE(T) val)

	{

		assert(idx == _neg || list_base<t>::isValid(idx));</t>

		size_t nodeIdx = list_base<t>::buyNode(TCG_FORWARD(T, val));</t>

		list_node &node = m_vector[nodeIdx];

		//Update links

		if (idx != _neg) {

			//node has a valid next

			list_node &next = m_vector[idx];

			node.m_prev = next.m_prev;

			next.m_prev = nodeIdx;

			node.m_next = idx;

			if (node.m_prev != _neg)

				m_vector[node.m_prev].m_next = nodeIdx;

		} else {

			node.m_next = _neg;

			node.m_prev = m_rbegin;

			if (m_rbegin != _neg)

				m_vector[m_rbegin].m_next = nodeIdx;

			m_rbegin = nodeIdx;

		}

		if (idx == m_begin)

			m_begin = nodeIdx;

		return nodeIdx;

	}

	template <typename iter=""></typename>

	size_t insert(size_t idx, Iter begin, Iter end)

	{

		if (begin == end)

			return idx;

		assert(idx == _neg || list_base<t>::isValid(idx));</t>

		size_t res = insert(idx, *begin);

		for (++begin; begin != end; ++begin)

			insert(idx, *begin);

		return res;

	}

	size_t erase(size_t idx)

	{

		assert(list_base<t>::isValid(idx));</t>

		if (idx == m_begin)

			m_begin = m_vector[idx].m_next;

		if (idx == m_rbegin)

			m_rbegin = m_vector[idx].m_prev;

		size_t result = m_vector[idx].m_next;

		list_base<t>::sellNode(idx);</t>

		return result;

	}

	size_t erase(size_t begin, size_t end)

	{

		assert(list_base<t>::isValid(begin));</t>

		if (begin == m_begin)

			m_begin = end;

		if (end == m_rbegin)

			m_rbegin = m_vector[begin].m_prev;

		list_base<t>::sellNodes(begin, end);</t>

		return end;

	}

	void clear()

	{

		list_base<t>::clear();</t>

		m_begin = m_rbegin = _neg;

	}

	void swap(list &other)

	{

		_swap(*this, other);

		std::swap(m_begin, other.m_begin);

		std::swap(m_rbegin, other.m_rbegin);

	}

	void swap(list &a, list &b)

	{

		a.swap(b);

	}

#if (TCG_RVALUES_SUPPORT > 0)

	void swap(list &&other)

	{

		this->_swap(*this, std::move(other));

		m_begin = other.m_begin;

		m_rbegin = other.m_rbegin;

	}

	void swap(list &a, list &&b)

	{

		a.swap(std::move(b));

	}

	void swap(list &&a, list &b)

	{

		b.swap(std::move(a));

	}

#endif

	//-----------------------------------------------------------------------------------------

	/*!

    \details  This function is \p tcg::list's counterpart to \p std::list::splice().

              It moves the specified range to a different part of the list, \a without

              touching any element elements - just by altering node links.

    \note     Unlike \p std::list::splice(), the list must be the same.