list.h

///////////////////////////////////////////////////////////////////////////////
// Copyright (c) Electronic Arts Inc. All rights reserved.
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
// This file implements a doubly-linked list, much like the C++ std::list class.
// The primary distinctions between this list and std::list are:
//    - list doesn't implement some of the less-frequently used functions 
//      of std::list. Any required functions can be added at a later time.
//    - list has a couple extension functions that increase performance.
//    - list can contain objects with alignment requirements. std::list cannot
//      do so without a bit of tedious non-portable effort.
//    - list has optimizations that don't exist in the STL implementations 
//      supplied by library vendors for our targeted platforms.
//    - list supports debug memory naming natively.
//    - list::size() by default is not a constant time function, like the list::size 
//      in some std implementations such as STLPort and SGI STL but unlike the 
//      list in Dinkumware and Metrowerks. The EASTL_LIST_SIZE_CACHE option can change this.
//    - list provides a guaranteed portable node definition that allows users
//      to write custom fixed size node allocators that are portable.
//    - list is easier to read, debug, and visualize.
//    - list is savvy to an environment that doesn't have exception handling,
//      as is sometimes the case with console or embedded environments.
//    - list has less deeply nested function calls and allows the user to 
//      enable forced inlining in debug builds in order to reduce bloat.
//    - list doesn't keep a member size variable. This means that list is 
//      smaller than std::list (depends on std::list) and that for most operations
//      it is faster than std::list. However, the list::size function is slower.
//    - list::size_type is defined as eastl_size_t instead of size_t in order to 
//      save memory and run faster on 64 bit systems.
///////////////////////////////////////////////////////////////////////////////


#ifndef EASTL_LIST_H
#define EASTL_LIST_H


#include <eastl/internal/config.h>
#include <eastl/allocator.h>
#include <eastl/type_traits.h>
#include <eastl/iterator.h>
#include <eastl/algorithm.h>
#include <eastl/initializer_list.h>
#include <eastl/bonus/compressed_pair.h>

EA_DISABLE_ALL_VC_WARNINGS()
#include <new>
#include <stddef.h>
EA_RESTORE_ALL_VC_WARNINGS()


// 4530 - C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc
// 4345 - Behavior change: an object of POD type constructed with an initializer of the form () will be default-initialized
// 4571 - catch(...) semantics changed since Visual C++ 7.1; structured exceptions (SEH) are no longer caught.
// 4623 - default constructor was implicitly defined as deleted
EA_DISABLE_VC_WARNING(4530 4345 4571 4623);


#if defined(EASTL_PRAGMA_ONCE_SUPPORTED)
	#pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result.
#endif



namespace eastl
{

	/// EASTL_LIST_DEFAULT_NAME
	///
	/// Defines a default container name in the absence of a user-provided name.
	///
	#ifndef EASTL_LIST_DEFAULT_NAME
		#define EASTL_LIST_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " list" // Unless the user overrides something, this is "EASTL list".
	#endif


	/// EASTL_LIST_DEFAULT_ALLOCATOR
	///
	#ifndef EASTL_LIST_DEFAULT_ALLOCATOR
		#define EASTL_LIST_DEFAULT_ALLOCATOR allocator_type(EASTL_LIST_DEFAULT_NAME)
	#endif



	/// ListNodeBase
	///
	/// We define a ListNodeBase separately from ListNode (below), because it allows
	/// us to have non-templated operations such as insert, remove (below), and it 
	/// makes it so that the list anchor node doesn't carry a T with it, which would
	/// waste space and possibly lead to surprising the user due to extra Ts existing
	/// that the user didn't explicitly create. The downside to all of this is that 
	/// it makes debug viewing of a list harder, given that the node pointers are of 
	/// type ListNodeBase and not ListNode. However, see ListNodeBaseProxy below.
	///
	struct ListNodeBase
	{
		ListNodeBase* mpNext;
		ListNodeBase* mpPrev;

		void        insert(ListNodeBase* pNext) EASTL_NOEXCEPT;                                // Inserts this standalone node before the node pNext in pNext's list. 
		void        remove() EASTL_NOEXCEPT;                                                   // Removes this node from the list it's in. Leaves this node's mpNext/mpPrev invalid.
		void        splice(ListNodeBase* pFirst, ListNodeBase* pLast) EASTL_NOEXCEPT;          // Removes [pFirst,pLast) from the list it's in and inserts it before this in this node's list.
		void        reverse() EASTL_NOEXCEPT;                                                  // Reverses the order of nodes in the circular list this node is a part of.
		static void swap(ListNodeBase& a, ListNodeBase& b) EASTL_NOEXCEPT;                     // Swaps the nodes a and b in the lists to which they belong.

		void        insert_range(ListNodeBase* pFirst, ListNodeBase* pFinal) EASTL_NOEXCEPT;   // Differs from splice in that first/final aren't in another list.
		static void remove_range(ListNodeBase* pFirst, ListNodeBase* pFinal) EASTL_NOEXCEPT;   // 
	};

	EA_DISABLE_VC_WARNING(4625 4626)
	template <typename T>
	struct ListNode : public ListNodeBase
	{
			T mValue;
		};
	EA_RESTORE_VC_WARNING()

	/// ListIterator
	///
	template <typename T, typename Pointer, typename Reference>
	struct ListIterator
	{
		typedef ListIterator<T, Pointer, Reference>         this_type;
		typedef ListIterator<T, T*, T&>                     iterator;
		typedef ListIterator<T, const T*, const T&>         const_iterator;
		typedef eastl_size_t                                size_type;     // See config.h for the definition of eastl_size_t, which defaults to size_t.
		typedef ptrdiff_t                                   difference_type;
		typedef T                                           value_type;
		typedef ListNodeBase                                base_node_type;
		typedef ListNode<T>                                 node_type;
		typedef Pointer                                     pointer;
		typedef Reference                                   reference;
		typedef EASTL_ITC_NS::bidirectional_iterator_tag    iterator_category;

	public:
		base_node_type* mpNode;

	public:
		ListIterator() EASTL_NOEXCEPT;
		ListIterator(const ListNodeBase* pNode) EASTL_NOEXCEPT;
		ListIterator(const iterator& x) EASTL_NOEXCEPT;

		this_type next() const EASTL_NOEXCEPT;
		this_type prev() const EASTL_NOEXCEPT;

		reference operator*() const EASTL_NOEXCEPT;
		pointer   operator->() const EASTL_NOEXCEPT;

		this_type& operator++() EASTL_NOEXCEPT;
		this_type  operator++(int) EASTL_NOEXCEPT;

		this_type& operator--() EASTL_NOEXCEPT;
		this_type  operator--(int) EASTL_NOEXCEPT;

	}; // ListIterator




	/// ListBase
	///
	/// See VectorBase (class vector) for an explanation of why we 
	/// create this separate base class.
	///
	template <typename T, typename Allocator>
	class ListBase
	{
	public:
		typedef T                                    value_type;
		typedef Allocator                            allocator_type;
		typedef ListNode<T>                          node_type;
		typedef eastl_size_t                         size_type;     // See config.h for the definition of eastl_size_t, which defaults to size_t.
		typedef ptrdiff_t                            difference_type;
		typedef ListNodeBase                         base_node_type; // We use ListNodeBase instead of ListNode<T> because we don't want to create a T.

	protected:
		eastl::compressed_pair<base_node_type, allocator_type>  mNodeAllocator;
		#if EASTL_LIST_SIZE_CACHE
			size_type  mSize;
		#endif

		base_node_type& internalNode() EASTL_NOEXCEPT { return mNodeAllocator.first(); }
		base_node_type const& internalNode() const EASTL_NOEXCEPT { return mNodeAllocator.first(); }
		allocator_type& internalAllocator() EASTL_NOEXCEPT { return mNodeAllocator.second(); }
		const allocator_type& internalAllocator() const EASTL_NOEXCEPT { return mNodeAllocator.second(); }

	public:
		const allocator_type& getAllocator() const EASTL_NOEXCEPT;
		allocator_type&       getAllocator() EASTL_NOEXCEPT;
		void                  setAllocator(const allocator_type& allocator);

	protected:
		ListBase();
		ListBase(const allocator_type& a);
	   ~ListBase();

		node_type* DoAllocateNode();
		void       DoFreeNode(node_type* pNode);

		void DoInit() EASTL_NOEXCEPT;
		void DoClear();

	}; // ListBase




	/// list
	///
	/// -- size() is O(n) --
	/// Note that as of this writing, list::size() is an O(n) operation when EASTL_LIST_SIZE_CACHE is disabled. 
	/// That is, getting the size of the list is not a fast operation, as it requires traversing the list and 
	/// counting the nodes. We could make list::size() be fast by having a member mSize variable. There are reasons 
	/// for having such functionality and reasons for not having such functionality. We currently choose
	/// to not have a member mSize variable as it would add four bytes to the class, add a tiny amount
	/// of processing to functions such as insert and erase, and would only serve to improve the size
	/// function, but no others. The alternative argument is that the C++ standard states that std::list
	/// should be an O(1) operation (i.e. have a member size variable), most C++ standard library list
	/// implementations do so, the size is but an integer which is quick to update, and many users 
	/// expect to have a fast size function. The EASTL_LIST_SIZE_CACHE option changes this.
	/// To consider: Make size caching an optional template parameter.
	///
	/// Pool allocation
	/// If you want to make a custom memory pool for a list container, your pool 
	/// needs to contain items of type list::node_type. So if you have a memory
	/// pool that has a constructor that takes the size of pool items and the
	/// count of pool items, you would do this (assuming that MemoryPool implements
	/// the Allocator interface):
	///     typedef list<Widget, MemoryPool> WidgetList;           // Delare your WidgetList type.
	///     MemoryPool myPool(sizeof(WidgetList::node_type), 100); // Make a pool of 100 Widget nodes.
	///     WidgetList myList(&myPool);                            // Create a list that uses the pool.
	///
	template <typename T, typename Allocator = EASTLAllocatorType>
	class list : public ListBase<T, Allocator>
	{
		typedef ListBase<T, Allocator>                  base_type;
		typedef list<T, Allocator>                      this_type;

	protected:
		using base_type::mNodeAllocator;
		using base_type::DoAllocateNode;
		using base_type::DoFreeNode;
		using base_type::DoClear;
		using base_type::DoInit;
#if EASTL_LIST_SIZE_CACHE
		using base_type::mSize;
#endif
		using base_type::internalNode;
		using base_type::internalAllocator;

	public:
		typedef T                                       value_type;
		typedef T*                                      pointer;
		typedef const T*                                const_pointer;
		typedef T&                                      reference;
		typedef const T&                                const_reference;
		typedef ListIterator<T, T*, T&>                 iterator;
		typedef ListIterator<T, const T*, const T&>     const_iterator;
		typedef eastl::reverse_iterator<iterator>       reverse_iterator;
		typedef eastl::reverse_iterator<const_iterator> const_reverse_iterator;
		typedef typename base_type::size_type           size_type;
		typedef typename base_type::difference_type     difference_type;
		typedef typename base_type::allocator_type      allocator_type;
		typedef typename base_type::node_type           node_type;
		typedef typename base_type::base_node_type      base_node_type;

		using base_type::getAllocator;

	public:
		list();
		list(const allocator_type& allocator);
		explicit list(size_type n, const allocator_type& allocator = EASTL_LIST_DEFAULT_ALLOCATOR);
		list(size_type n, const value_type& value, const allocator_type& allocator = EASTL_LIST_DEFAULT_ALLOCATOR);
		list(const this_type& x);
		list(const this_type& x, const allocator_type& allocator);
		list(this_type&& x);
		list(this_type&&, const allocator_type&);
		list(std::initializer_list<value_type> ilist, const allocator_type& allocator = EASTL_LIST_DEFAULT_ALLOCATOR);

		template <typename InputIterator>
		list(InputIterator first, InputIterator last); // allocator arg removed because VC7.1 fails on the default arg. To do: Make a second version of this function without a default arg.

		this_type& operator=(const this_type& x);
		this_type& operator=(std::initializer_list<value_type> ilist);
		this_type& operator=(this_type&& x);

		// In the case that the two containers' allocators are unequal, swap copies elements instead
		// of replacing them in place. In this case swap is an O(n) operation instead of O(1).
		void swap(this_type& x);

		void assign(size_type n, const value_type& value);

		template <typename InputIterator>                       // It turns out that the C++ std::list specifies a two argument
		void assign(InputIterator first, InputIterator last);   // version of assign that takes (int size, int value). These are not 
																// iterators, so we need to do a template compiler trick to do the right thing.
		void assign(std::initializer_list<value_type> ilist);

		iterator       begin() EASTL_NOEXCEPT;
		const_iterator begin() const EASTL_NOEXCEPT;
		const_iterator cbegin() const EASTL_NOEXCEPT;

		iterator       end() EASTL_NOEXCEPT;
		const_iterator end() const EASTL_NOEXCEPT;
		const_iterator cend() const EASTL_NOEXCEPT;

		reverse_iterator       rbegin() EASTL_NOEXCEPT;
		const_reverse_iterator rbegin() const EASTL_NOEXCEPT;
		const_reverse_iterator crbegin() const EASTL_NOEXCEPT;

		reverse_iterator       rend() EASTL_NOEXCEPT;
		const_reverse_iterator rend() const EASTL_NOEXCEPT;
		const_reverse_iterator crend() const EASTL_NOEXCEPT;

		bool      empty() const EASTL_NOEXCEPT;
		size_type size() const EASTL_NOEXCEPT;

		void resize(size_type n, const value_type& value);
		void resize(size_type n);

		reference       front();
		const_reference front() const;

		reference       back();
		const_reference back() const;

		template <typename... Args>
		void emplace_front(Args&&... args);

		template <typename... Args>
		void emplace_back(Args&&... args);

		void      pushFront(const value_type& value);
		void      pushFront(value_type&& x);
		reference pushFront();
		void*     pushFrontUninitialized();

		void      pushBack(const value_type& value);
		void      pushBack(value_type&& x);
		reference pushBack();
		void*     pushBackUninitialized();

		void popFront();
		void popBack();

		template <typename... Args>
		iterator emplace(const_iterator position, Args&&... args);

		iterator insert(const_iterator position);
		iterator insert(const_iterator position, const value_type& value);
		iterator insert(const_iterator position, value_type&& x);
		iterator insert(const_iterator position, std::initializer_list<value_type> ilist);
		iterator insert(const_iterator position, size_type n, const value_type& value);

		template <typename InputIterator>
		iterator insert(const_iterator position, InputIterator first, InputIterator last);

		iterator erase(const_iterator position);
		iterator erase(const_iterator first, const_iterator last);

		reverse_iterator erase(const_reverse_iterator position);
		reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last);

		void clear() EASTL_NOEXCEPT;
		void reset_lose_memory() EASTL_NOEXCEPT;    // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs.

		size_type remove(const T& x);

		template <typename Predicate>
		size_type removeIf(Predicate);

		void reverse() EASTL_NOEXCEPT;

		// splice inserts elements in the range [first,last) before position and removes the elements from x.
		// In the case that the two containers' allocators are unequal, splice copies elements 
		// instead of splicing them. In this case elements are not removed from x, and iterators 
		// into the spliced elements from x continue to point to the original values in x.
		void splice(const_iterator position, this_type& x);
		void splice(const_iterator position, this_type& x, const_iterator i);
		void splice(const_iterator position, this_type& x, const_iterator first, const_iterator last);
		void splice(const_iterator position, this_type&& x);
		void splice(const_iterator position, this_type&& x, const_iterator i);
		void splice(const_iterator position, this_type&& x, const_iterator first, const_iterator last);

	public:
		// For merge, see notes for splice regarding the handling of unequal allocators.
		void merge(this_type& x);
		void merge(this_type&& x);

		template <typename Compare>
		void merge(this_type& x, Compare compare);

		template <typename Compare>
		void merge(this_type&& x, Compare compare);

		void unique();

		template <typename BinaryPredicate>
		void unique(BinaryPredicate);

		// Sorting functionality
		// This is independent of the global sort algorithms, as lists are 
		// linked nodes and can be sorted more efficiently by moving nodes
		// around in ways that global sort algorithms aren't privy to.
		void sort();

		template<typename Compare>
		void sort(Compare compare);

	public:
		bool validate() const;
		int  validateIterator(const_iterator i) const;

	protected:
		node_type* DoCreateNode();

		template<typename... Args>
		node_type* DoCreateNode(Args&&... args);

		template <typename Integer>
		void DoAssign(Integer n, Integer value, true_type);

		template <typename InputIterator>
		void DoAssign(InputIterator first, InputIterator last, false_type);

		void DoAssignValues(size_type n, const value_type& value);

		template <typename Integer>
		void DoInsert(ListNodeBase* pNode, Integer n, Integer value, true_type);

		template <typename InputIterator>
		void DoInsert(ListNodeBase* pNode, InputIterator first, InputIterator last, false_type);

		void DoInsertValues(ListNodeBase* pNode, size_type n, const value_type& value);
	   
		template<typename... Args>
		void DoInsertValue(ListNodeBase* pNode, Args&&... args);

		void DoErase(ListNodeBase* pNode);

		void DoSwap(this_type& x);

		template <typename Compare>
		iterator DoSort(iterator i1, iterator end2, size_type n, Compare& compare);

	}; // class list





	///////////////////////////////////////////////////////////////////////
	// ListNodeBase
	///////////////////////////////////////////////////////////////////////

	// Swaps the nodes a and b in the lists to which they belong. This is similar to 
	// splicing a into b's list and b into a's list at the same time.
	// Works by swapping the members of a and b, and fixes up the lists that a and b 
	// were part of to point to the new members.
	inline void ListNodeBase::swap(ListNodeBase& a, ListNodeBase& b) EASTL_NOEXCEPT
	{
		const ListNodeBase temp(a);
		a = b;
		b = temp;

		if(a.mpNext == &b)
			a.mpNext = a.mpPrev = &a;
		else
			a.mpNext->mpPrev = a.mpPrev->mpNext = &a;

		if(b.mpNext == &a)
			b.mpNext = b.mpPrev = &b;
		else
			b.mpNext->mpPrev = b.mpPrev->mpNext = &b;
	}


	// splices the [first,last) range from its current list into our list before this node.
	inline void ListNodeBase::splice(ListNodeBase* first, ListNodeBase* last) EASTL_NOEXCEPT
	{
		// We assume that [first, last] are not within our list.
		last->mpPrev->mpNext  = this;
		first->mpPrev->mpNext = last;
		this->mpPrev->mpNext  = first;

		ListNodeBase* const pTemp = this->mpPrev;
		this->mpPrev  = last->mpPrev;
		last->mpPrev  = first->mpPrev;
		first->mpPrev = pTemp;
	}


	inline void ListNodeBase::reverse() EASTL_NOEXCEPT
	{
		ListNodeBase* pNode = this;
		do
		{
			EA_ANALYSIS_ASSUME(pNode != NULL);
			ListNodeBase* const pTemp = pNode->mpNext;
			pNode->mpNext = pNode->mpPrev;
			pNode->mpPrev = pTemp;
			pNode         = pNode->mpPrev;
		} 
		while(pNode != this);
	}


	inline void ListNodeBase::insert(ListNodeBase* pNext) EASTL_NOEXCEPT
	{
		mpNext = pNext;
		mpPrev = pNext->mpPrev;
		pNext->mpPrev->mpNext = this;
		pNext->mpPrev = this;
	}


	// Removes this node from the list that it's in. Assumes that the 
	// node is within a list and thus that its prev/next pointers are valid.
	inline void ListNodeBase::remove() EASTL_NOEXCEPT
	{
		mpNext->mpPrev = mpPrev;
		mpPrev->mpNext = mpNext;
	}


	// Inserts the standalone range [pFirst, pFinal] before pPosition. Assumes that the
	// range is not within a list and thus that it's prev/next pointers are not valid.
	// Assumes that this node is within a list and thus that its prev/next pointers are valid.
	inline void ListNodeBase::insert_range(ListNodeBase* pFirst, ListNodeBase* pFinal) EASTL_NOEXCEPT
	{
		mpPrev->mpNext = pFirst;
		pFirst->mpPrev = mpPrev;
		mpPrev         = pFinal;
		pFinal->mpNext = this;
	}


	// Removes the range [pFirst, pFinal] from the list that it's in. Assumes that the 
	// range is within a list and thus that its prev/next pointers are valid.
	inline void ListNodeBase::remove_range(ListNodeBase* pFirst, ListNodeBase* pFinal) EASTL_NOEXCEPT
	{
		pFinal->mpNext->mpPrev = pFirst->mpPrev;
		pFirst->mpPrev->mpNext = pFinal->mpNext;
	}


	///////////////////////////////////////////////////////////////////////
	// ListIterator
	///////////////////////////////////////////////////////////////////////

	template <typename T, typename Pointer, typename Reference>
	inline ListIterator<T, Pointer, Reference>::ListIterator() EASTL_NOEXCEPT
		: mpNode() // To consider: Do we really need to intialize mpNode?
	{
		// Empty
	}


	template <typename T, typename Pointer, typename Reference>
	inline ListIterator<T, Pointer, Reference>::ListIterator(const ListNodeBase* pNode) EASTL_NOEXCEPT
		: mpNode(const_cast<base_node_type*>(pNode))
	{
		// Empty
	}


	template <typename T, typename Pointer, typename Reference>
	inline ListIterator<T, Pointer, Reference>::ListIterator(const iterator& x) EASTL_NOEXCEPT
		: mpNode(const_cast<base_node_type*>(x.mpNode))
	{
		// Empty
	} 


	template <typename T, typename Pointer, typename Reference>
	inline typename ListIterator<T, Pointer, Reference>::this_type
	ListIterator<T, Pointer, Reference>::next() const EASTL_NOEXCEPT
	{
		return ListIterator(mpNode->mpNext);
	}


	template <typename T, typename Pointer, typename Reference>
	inline typename ListIterator<T, Pointer, Reference>::this_type
	ListIterator<T, Pointer, Reference>::prev() const EASTL_NOEXCEPT
	{
		return ListIterator(mpNode->mpPrev);
	}


	template <typename T, typename Pointer, typename Reference>
	inline typename ListIterator<T, Pointer, Reference>::reference
	ListIterator<T, Pointer, Reference>::operator*() const EASTL_NOEXCEPT
	{
		return static_cast<node_type*>(mpNode)->mValue;
	}


	template <typename T, typename Pointer, typename Reference>
	inline typename ListIterator<T, Pointer, Reference>::pointer
	ListIterator<T, Pointer, Reference>::operator->() const EASTL_NOEXCEPT
	{
		return &static_cast<node_type*>(mpNode)->mValue;
	}


	template <typename T, typename Pointer, typename Reference>
	inline typename ListIterator<T, Pointer, Reference>::this_type&
	ListIterator<T, Pointer, Reference>::operator++() EASTL_NOEXCEPT
	{
		mpNode = mpNode->mpNext;
		return *this;
	}


	template <typename T, typename Pointer, typename Reference>
	inline typename ListIterator<T, Pointer, Reference>::this_type
	ListIterator<T, Pointer, Reference>::operator++(int) EASTL_NOEXCEPT
	{
		this_type temp(*this);
		mpNode = mpNode->mpNext;
		return temp;
	}


	template <typename T, typename Pointer, typename Reference>
	inline typename ListIterator<T, Pointer, Reference>::this_type&
	ListIterator<T, Pointer, Reference>::operator--() EASTL_NOEXCEPT
	{
		mpNode = mpNode->mpPrev;
		return *this;
	}


	template <typename T, typename Pointer, typename Reference>
	inline typename ListIterator<T, Pointer, Reference>::this_type 
	ListIterator<T, Pointer, Reference>::operator--(int) EASTL_NOEXCEPT
	{
		this_type temp(*this);
		mpNode = mpNode->mpPrev;
		return temp;
	}


	// The C++ defect report #179 requires that we support comparisons between const and non-const iterators.
	// Thus we provide additional template paremeters here to support this. The defect report does not
	// require us to support comparisons between reverse_iterators and const_reverse_iterators.
	template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB>
	inline bool operator==(const ListIterator<T, PointerA, ReferenceA>& a, 
						   const ListIterator<T, PointerB, ReferenceB>& b) EASTL_NOEXCEPT
	{
		return a.mpNode == b.mpNode;
	}


	template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB>
	inline bool operator!=(const ListIterator<T, PointerA, ReferenceA>& a, 
						   const ListIterator<T, PointerB, ReferenceB>& b) EASTL_NOEXCEPT
	{
		return a.mpNode != b.mpNode;
	}


	// We provide a version of operator!= for the case where the iterators are of the 
	// same type. This helps prevent ambiguity errors in the presence of rel_ops.
	template <typename T, typename Pointer, typename Reference>
	inline bool operator!=(const ListIterator<T, Pointer, Reference>& a, 
						   const ListIterator<T, Pointer, Reference>& b) EASTL_NOEXCEPT
	{
		return a.mpNode != b.mpNode;
	}



	///////////////////////////////////////////////////////////////////////
	// ListBase
	///////////////////////////////////////////////////////////////////////

	template <typename T, typename Allocator>
	inline ListBase<T, Allocator>::ListBase()
		: mNodeAllocator(base_node_type(), allocator_type(EASTL_LIST_DEFAULT_NAME))
		  #if EASTL_LIST_SIZE_CACHE
		  , mSize(0)
		  #endif
	{
		DoInit();
	}

	template <typename T, typename Allocator>
	inline ListBase<T, Allocator>::ListBase(const allocator_type& allocator)
		: mNodeAllocator(base_node_type(), allocator)
		  #if EASTL_LIST_SIZE_CACHE
		  , mSize(0)
		  #endif
	{
		DoInit();
	}


	template <typename T, typename Allocator>
	inline ListBase<T, Allocator>::~ListBase()
	{
		DoClear();
	}


	template <typename T, typename Allocator>
	const typename ListBase<T, Allocator>::allocator_type&
	ListBase<T, Allocator>::getAllocator() const EASTL_NOEXCEPT
	{
		return internalAllocator();
	}


	template <typename T, typename Allocator>
	typename ListBase<T, Allocator>::allocator_type&
	ListBase<T, Allocator>::getAllocator() EASTL_NOEXCEPT
	{
		return internalAllocator();
	}


	template <typename T, typename Allocator>
	inline void ListBase<T, Allocator>::setAllocator(const allocator_type& allocator)
	{
		EASTL_ASSERT((internalAllocator() == allocator) || (static_cast<node_type*>(internalNode().mpNext) == &internalNode())); // We can only assign a different allocator if we are empty of elements.
		internalAllocator() = allocator;
	}


	template <typename T, typename Allocator>
	inline typename ListBase<T, Allocator>::node_type*
	ListBase<T, Allocator>::DoAllocateNode()
	{
		node_type* pNode = (node_type*)allocate_memory(internalAllocator(), sizeof(node_type), EASTL_ALIGN_OF(node_type), 0);
		EASTL_ASSERT(pNode != nullptr);
		return pNode;
	}


	template <typename T, typename Allocator>
	inline void ListBase<T, Allocator>::DoFreeNode(node_type* p)
	{
		EASTLFree(internalAllocator(), p, sizeof(node_type));
	}


	template <typename T, typename Allocator>
	inline void ListBase<T, Allocator>::DoInit() EASTL_NOEXCEPT
	{
		internalNode().mpNext = &internalNode();
		internalNode().mpPrev = &internalNode();
	}


	template <typename T, typename Allocator>
	inline void ListBase<T, Allocator>::DoClear()
	{
		base_node_type* p = internalNode().mpNext;

		while(p != &internalNode())
		{
			node_type* const pTemp = static_cast<node_type*>(p);
			p = p->mpNext;
			pTemp->~node_type();
			EASTLFree(internalAllocator(), pTemp, sizeof(node_type));
		}
	}



	///////////////////////////////////////////////////////////////////////
	// list
	///////////////////////////////////////////////////////////////////////

	template <typename T, typename Allocator>
	inline list<T, Allocator>::list()
		: base_type()
	{
		// Empty
	}


	template <typename T, typename Allocator>
	inline list<T, Allocator>::list(const allocator_type& allocator)
		: base_type(allocator)
	{
		// Empty
	}


	template <typename T, typename Allocator>
	inline list<T, Allocator>::list(size_type n, const allocator_type& allocator)
		: base_type(allocator)
	{
		DoInsertValues(&internalNode(), n, value_type());
	}


	template <typename T, typename Allocator>
	inline list<T, Allocator>::list(size_type n, const value_type& value, const allocator_type& allocator)
		: base_type(allocator) 
	{
		DoInsertValues(&internalNode(), n, value);
	}


	template <typename T, typename Allocator>
	inline list<T, Allocator>::list(const this_type& x)
		: base_type(x.internalAllocator())
	{
		DoInsert(&internalNode(), const_iterator(x.internalNode().mpNext), const_iterator(&x.internalNode()), false_type());
	}


	template <typename T, typename Allocator>
	inline list<T, Allocator>::list(const this_type& x, const allocator_type& allocator)
		: base_type(allocator)
	{
		DoInsert(&internalNode(), const_iterator(x.internalNode().mpNext), const_iterator(&x.internalNode()), false_type());
	}


	template <typename T, typename Allocator>
	inline list<T, Allocator>::list(this_type&& x)
		: base_type(eastl::move(x.internalAllocator()))
	{
		swap(x);
	}


	template <typename T, typename Allocator>
	inline list<T, Allocator>::list(this_type&& x, const allocator_type& allocator)
		: base_type(allocator)
	{
		swap(x); // member swap handles the case that x has a different allocator than our allocator by doing a copy.
	}


	template <typename T, typename Allocator>
	inline list<T, Allocator>::list(std::initializer_list<value_type> ilist, const allocator_type& allocator)
		: base_type(allocator)
	{
		DoInsert(&internalNode(), ilist.begin(), ilist.end(), false_type());
	}


	template <typename T, typename Allocator>
	template <typename InputIterator>
	list<T, Allocator>::list(InputIterator first, InputIterator last)
		: base_type(EASTL_LIST_DEFAULT_ALLOCATOR)
	{
		//insert(const_iterator(&internalNode()), first, last);
		DoInsert(&internalNode(), first, last, is_integral<InputIterator>());
	}


	template <typename T, typename Allocator>
	typename list<T, Allocator>::iterator
	inline list<T, Allocator>::begin() EASTL_NOEXCEPT
	{
		return iterator(internalNode().mpNext);
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_iterator
	list<T, Allocator>::begin() const EASTL_NOEXCEPT
	{
		return const_iterator(internalNode().mpNext);
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_iterator
	list<T, Allocator>::cbegin() const EASTL_NOEXCEPT
	{
		return const_iterator(internalNode().mpNext);
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::iterator
	list<T, Allocator>::end() EASTL_NOEXCEPT
	{
		return iterator(&internalNode());
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_iterator
	list<T, Allocator>::end() const EASTL_NOEXCEPT
	{
		return const_iterator(&internalNode());
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_iterator
	list<T, Allocator>::cend() const EASTL_NOEXCEPT
	{
		return const_iterator(&internalNode());
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::reverse_iterator
	list<T, Allocator>::rbegin() EASTL_NOEXCEPT
	{
		return reverse_iterator(&internalNode());
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_reverse_iterator
	list<T, Allocator>::rbegin() const EASTL_NOEXCEPT
	{
		return const_reverse_iterator(&internalNode());
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_reverse_iterator
	list<T, Allocator>::crbegin() const EASTL_NOEXCEPT
	{
		return const_reverse_iterator(&internalNode());
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::reverse_iterator
	list<T, Allocator>::rend() EASTL_NOEXCEPT
	{
		return reverse_iterator(internalNode().mpNext);
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_reverse_iterator
	list<T, Allocator>::rend() const EASTL_NOEXCEPT
	{
		return const_reverse_iterator(internalNode().mpNext);
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_reverse_iterator
	list<T, Allocator>::crend() const EASTL_NOEXCEPT
	{
		return const_reverse_iterator(internalNode().mpNext);
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::reference
	list<T, Allocator>::front()
	{
		#if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
			if (EASTL_UNLIKELY(static_cast<node_type*>(internalNode().mpNext) == &internalNode()))
				EASTL_FAIL_MSG("list::front -- empty container");
		#else
			// We allow the user to reference an empty container.
		#endif

		return static_cast<node_type*>(internalNode().mpNext)->mValue;
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_reference
	list<T, Allocator>::front() const
	{
		#if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
			if (EASTL_UNLIKELY(static_cast<node_type*>(internalNode().mpNext) == &internalNode()))
				EASTL_FAIL_MSG("list::front -- empty container");
		#else
			// We allow the user to reference an empty container.
		#endif

		return static_cast<node_type*>(internalNode().mpNext)->mValue;
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::reference
	list<T, Allocator>::back()
	{
		#if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
			if (EASTL_UNLIKELY(static_cast<node_type*>(internalNode().mpNext) == &internalNode()))
				EASTL_FAIL_MSG("list::back -- empty container");
		#else
			// We allow the user to reference an empty container.
		#endif

		return static_cast<node_type*>(internalNode().mpPrev)->mValue;
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::const_reference
	list<T, Allocator>::back() const
	{
		#if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
			if (EASTL_UNLIKELY(static_cast<node_type*>(internalNode().mpNext) == &internalNode()))
				EASTL_FAIL_MSG("list::back -- empty container");
		#else
			// We allow the user to reference an empty container.
		#endif

		return static_cast<node_type*>(internalNode().mpPrev)->mValue;
	}


	template <typename T, typename Allocator>
	inline bool list<T, Allocator>::empty() const EASTL_NOEXCEPT
	{
		#if EASTL_LIST_SIZE_CACHE
			return (mSize == 0);
		#else
			return static_cast<node_type*>(internalNode().mpNext) == &internalNode();
		#endif
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::size_type
	list<T, Allocator>::size() const EASTL_NOEXCEPT
	{
		#if EASTL_LIST_SIZE_CACHE
			return mSize;
		#else
			#if EASTL_DEBUG
				const ListNodeBase* p = internalNode().mpNext;
				size_type n = 0;
				while(p != &internalNode())
				{
					++n;
					p = p->mpNext;
				}
				return n;
			#else
				// The following optimizes to slightly better code than the code above.
				return (size_type)eastl::distance(const_iterator(internalNode().mpNext), const_iterator(&internalNode()));
			#endif
		#endif
	}


	template <typename T, typename Allocator>
	typename list<T, Allocator>::this_type&
	list<T, Allocator>::operator=(const this_type& x)
	{
		if(this != &x) // If not assigning to self...
		{
			// If (EASTL_ALLOCATOR_COPY_ENABLED == 1) and the current contents are allocated by an 
			// allocator that's unequal to x's allocator, we need to reallocate our elements with 
			// our current allocator and reallocate it with x's allocator. If the allocators are 
			// equal then we can use a more optimal algorithm that doesn't reallocate our elements
			// but instead can copy them in place.

			#if EASTL_ALLOCATOR_COPY_ENABLED
				bool bSlowerPathwayRequired = (internalAllocator() != x.internalAllocator());
			#else
				bool bSlowerPathwayRequired = false;
			#endif

			if(bSlowerPathwayRequired)
			{
				clear();

				#if EASTL_ALLOCATOR_COPY_ENABLED
					internalAllocator() = x.internalAllocator();
				#endif
			}

			DoAssign(x.begin(), x.end(), eastl::false_type());
		}

		return *this;
	}


	template <typename T, typename Allocator>
	typename list<T, Allocator>::this_type&
	list<T, Allocator>::operator=(this_type&& x)
	{
		if(this != &x)
		{
			clear();        // To consider: Are we really required to clear here? x is going away soon and will clear itself in its dtor.
			swap(x);        // member swap handles the case that x has a different allocator than our allocator by doing a copy.
		}
		return *this;
	}


	template <typename T, typename Allocator>
	typename list<T, Allocator>::this_type&
	list<T, Allocator>::operator=(std::initializer_list<value_type> ilist)
	{
		DoAssign(ilist.begin(), ilist.end(), false_type());
		return *this;
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::assign(size_type n, const value_type& value)
	{
		DoAssignValues(n, value);
	}


	// It turns out that the C++ std::list specifies a two argument
	// version of assign that takes (int size, int value). These are not 
	// iterators, so we need to do a template compiler trick to do the right thing.
	template <typename T, typename Allocator>
	template <typename InputIterator>
	inline void list<T, Allocator>::assign(InputIterator first, InputIterator last)
	{
		DoAssign(first, last, is_integral<InputIterator>());
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::assign(std::initializer_list<value_type> ilist)
	{
		DoAssign(ilist.begin(), ilist.end(), false_type());
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::clear() EASTL_NOEXCEPT
	{
		DoClear();
		DoInit();
		#if EASTL_LIST_SIZE_CACHE
			mSize = 0;
		#endif
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::reset_lose_memory() EASTL_NOEXCEPT
	{
		// The reset_lose_memory function is a special extension function which unilaterally 
		// resets the container to an empty state without freeing the memory of 
		// the contained objects. This is useful for very quickly tearing down a 
		// container built into scratch memory.
		DoInit();
		#if EASTL_LIST_SIZE_CACHE
			mSize = 0;
		#endif
	}


	template <typename T, typename Allocator>
	void list<T, Allocator>::resize(size_type n, const value_type& value)
	{
		iterator current(internalNode().mpNext);
		size_type i = 0;

		while((current.mpNode != &internalNode()) && (i < n))
		{
			++current;  
			++i;
		}
		if(i == n)
			erase(current, &internalNode());
		else
			insert(&internalNode(), n - i, value);
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::resize(size_type n)
	{
		resize(n, value_type());
	}


	template <typename T, typename Allocator>
	template <typename... Args>
	void list<T, Allocator>::emplace_front(Args&&... args)
	{
		DoInsertValue(internalNode().mpNext, eastl::forward<Args>(args)...);
	}

	template <typename T, typename Allocator>
	template <typename... Args>
	void list<T, Allocator>::emplace_back(Args&&... args)
	{
		DoInsertValue(&internalNode(), eastl::forward<Args>(args)...);
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::pushFront(const value_type& value)
	{
		DoInsertValue(internalNode().mpNext, value);
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::pushFront(value_type&& value)
	{
		emplace(begin(), eastl::move(value));
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::reference
	list<T, Allocator>::pushFront()
	{
		node_type* const pNode = DoCreateNode();
		pNode->insert(internalNode().mpNext);
		#if EASTL_LIST_SIZE_CACHE
			++mSize;
		#endif
		return static_cast<node_type*>(internalNode().mpNext)->mValue; // Same as return front();
	}


	template <typename T, typename Allocator>
	inline void* list<T, Allocator>::pushFrontUninitialized()
	{
		node_type* const pNode = DoAllocateNode();
		pNode->insert(internalNode().mpNext);
		#if EASTL_LIST_SIZE_CACHE
			++mSize;
		#endif
		return &pNode->mValue;
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::popFront()
	{
		#if EASTL_ASSERT_ENABLED
			if(EASTL_UNLIKELY(static_cast<node_type*>(internalNode().mpNext) == &internalNode()))
				EASTL_FAIL_MSG("list::popFront -- empty container");
		#endif

		DoErase(internalNode().mpNext);
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::pushBack(const value_type& value)
	{
		DoInsertValue(&internalNode(), value);
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::pushBack(value_type&& value)
	{
		emplace(end(), eastl::move(value));
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::reference
	list<T, Allocator>::pushBack()
	{
		node_type* const pNode = DoCreateNode();
		pNode->insert(&internalNode());
		#if EASTL_LIST_SIZE_CACHE
			++mSize;
		#endif
		return static_cast<node_type*>(internalNode().mpPrev)->mValue;  // Same as return back();
	}


	template <typename T, typename Allocator>
	inline void* list<T, Allocator>::pushBackUninitialized()
	{
		node_type* const pNode = DoAllocateNode();
		pNode->insert(&internalNode());
		#if EASTL_LIST_SIZE_CACHE
			++mSize;
		#endif
		return &pNode->mValue;
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::popBack()
	{
		#if EASTL_ASSERT_ENABLED
			if(EASTL_UNLIKELY(static_cast<node_type*>(internalNode().mpNext) == &internalNode()))
				EASTL_FAIL_MSG("list::popBack -- empty container");
		#endif

		DoErase(internalNode().mpPrev);
	}


	template <typename T, typename Allocator>
	template <typename... Args>
	inline typename list<T, Allocator>::iterator
	list<T, Allocator>::emplace(const_iterator position, Args&&... args)
	{
		DoInsertValue(position.mpNode, eastl::forward<Args>(args)...);
		return iterator(position.mpNode->mpPrev);
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::iterator
	list<T, Allocator>::insert(const_iterator position)
	{
		ListNodeBase* const pNode = DoCreateNode(value_type());
		pNode->insert(position.mpNode);
		#if EASTL_LIST_SIZE_CACHE
			++mSize;
		#endif
		return pNode;
	}

	
	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::iterator
	list<T, Allocator>::insert(const_iterator position, const value_type& value)
	{
		ListNodeBase* const pNode = DoCreateNode(value);
		pNode->insert(position.mpNode);
		#if EASTL_LIST_SIZE_CACHE
			++mSize;
		#endif
		return pNode;
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::iterator
	list<T, Allocator>::insert(const_iterator position, value_type&& value)
	{
		return emplace(position, eastl::move(value));
	}

	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::iterator
	list<T, Allocator>::insert(const_iterator position, size_type n, const value_type& value)
	{
		iterator itPrev(position.mpNode);
		--itPrev;
		DoInsertValues(position.mpNode, n, value);
		return ++itPrev; // Inserts in front of position, returns iterator to new elements. 
	}


	template <typename T, typename Allocator>
	template <typename InputIterator>
	inline typename list<T, Allocator>::iterator
	list<T, Allocator>::insert(const_iterator position, InputIterator first, InputIterator last)
	{
		iterator itPrev(position.mpNode);
		--itPrev;
		DoInsert(position.mpNode, first, last, is_integral<InputIterator>());
		return ++itPrev; // Inserts in front of position, returns iterator to new elements. 
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::iterator 
	list<T, Allocator>::insert(const_iterator position, std::initializer_list<value_type> ilist)
	{
		iterator itPrev(position.mpNode);
		--itPrev;
		DoInsert(position.mpNode, ilist.begin(), ilist.end(), false_type());
		return ++itPrev; // Inserts in front of position, returns iterator to new elements. 
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::iterator
	list<T, Allocator>::erase(const_iterator position)
	{
		++position;
		DoErase(position.mpNode->mpPrev);
		return iterator(position.mpNode);
	}


	template <typename T, typename Allocator>
	typename list<T, Allocator>::iterator
	list<T, Allocator>::erase(const_iterator first, const_iterator last)
	{
		while(first != last)
			first = erase(first);
		return iterator(last.mpNode);
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::reverse_iterator
	list<T, Allocator>::erase(const_reverse_iterator position)
	{
		return reverse_iterator(erase((++position).base()));
	}


	template <typename T, typename Allocator>
	typename list<T, Allocator>::reverse_iterator
	list<T, Allocator>::erase(const_reverse_iterator first, const_reverse_iterator last)
	{
		// Version which erases in order from first to last.
		// difference_type i(first.base() - last.base());
		// while(i--)
		//     first = erase(first);
		// return first;

		// Version which erases in order from last to first, but is slightly more efficient:
		const_iterator itLastBase((++last).base());
		const_iterator itFirstBase((++first).base());

		return reverse_iterator(erase(itLastBase, itFirstBase));
	}


	template <typename T, typename Allocator>
	typename list<T, Allocator>::size_type list<T, Allocator>::remove(const value_type& value)
	{
		iterator current(internalNode().mpNext);
		size_type numRemoved = 0;

		while(current.mpNode != &internalNode())
		{
			if(EASTL_LIKELY(!(*current == value)))
				++current; // We have duplicate '++current' statements here and below, but the logic here forces this.
			else
			{
				++current;
				DoErase(current.mpNode->mpPrev);
				++numRemoved;
			}
		}
		return numRemoved;
	}


	template <typename T, typename Allocator>
	template <typename Predicate>
	inline typename list<T, Allocator>::size_type list<T, Allocator>::removeIf(Predicate predicate)
	{
		size_type numRemoved = 0;
		for(iterator first(internalNode().mpNext), last(&internalNode()); first != last; )
		{
			iterator temp(first);
			++temp;
			if(predicate(static_cast<node_type*>(first.mpNode)->mValue))
			{
				DoErase(first.mpNode);
				++numRemoved;
			}
			first = temp;
		}
		return numRemoved;
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::reverse() EASTL_NOEXCEPT
	{
		((ListNodeBase&)internalNode()).reverse();
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::splice(const_iterator position, this_type& x)
	{
		// Splicing operations cannot succeed if the two containers use unequal allocators.
		// This issue is not addressed in the C++ 1998 standard but is discussed in the 
		// LWG defect reports, such as #431. There is no simple solution to this problem.
		// One option is to throw an exception. Another option which probably captures the
		// user intent most of the time is to copy the range from the source to the dest and 
		// remove it from the source. 

		if(internalAllocator() == x.internalAllocator())
		{
			#if EASTL_LIST_SIZE_CACHE
				if(x.mSize)
				{
					(position.mpNode)->splice(x.internalNode().mpNext, &x.internalNode());
					mSize += x.mSize;
					x.mSize = 0;
				}
			#else
				if(!x.empty())
					(position.mpNode)->splice(x.internalNode().mpNext, &x.internalNode());
			#endif
		}
		else
		{
			insert(position, x.begin(), x.end());
			x.clear();
		}
	}

	template <typename T, typename Allocator>
	inline void list<T, Allocator>::splice(const_iterator position, this_type&& x)
	{
		return splice(position, x); // This will call splice(const_iterator, const this_type&);
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::splice(const_iterator position, list& x, const_iterator i)
	{
		if(internalAllocator() == x.internalAllocator())
		{
			iterator i2(i.mpNode);
			++i2;
			if((position != i) && (position != i2))
			{
				(position.mpNode)->splice(i.mpNode, i2.mpNode);

				#if EASTL_LIST_SIZE_CACHE
					++mSize;
					--x.mSize;
				#endif
			}
		}
		else
		{
			insert(position, *i);
			x.erase(i);
		}
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::splice(const_iterator position, list<T,Allocator>&& x, const_iterator i)
	{
		return splice(position, x, i); // This will call splice(const_iterator, const this_type&, const_iterator);
	}
		

	template <typename T, typename Allocator>
	inline void list<T, Allocator>::splice(const_iterator position, this_type& x, const_iterator first, const_iterator last)
	{
		if(internalAllocator() == x.internalAllocator())
		{
			#if EASTL_LIST_SIZE_CACHE
				const size_type n = (size_type)eastl::distance(first, last);

				if(n)
				{
					(position.mpNode)->splice(first.mpNode, last.mpNode);
					mSize += n;
					x.mSize -= n;
				}
			#else
				if(first != last)
					(position.mpNode)->splice(first.mpNode, last.mpNode);
			#endif
		}
		else
		{
			insert(position, first, last);
			x.erase(first, last);
		}
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::splice(const_iterator position, list<T,Allocator>&& x, const_iterator first, const_iterator last)
	{
		return splice(position, x, first, last); // This will call splice(const_iterator, const this_type&, const_iterator, const_iterator);
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::swap(this_type& x)
	{
		if(internalAllocator() == x.internalAllocator()) // If allocators are equivalent...
			DoSwap(x);
		else // else swap the contents.
		{
			const this_type temp(*this); // Can't call eastl::swap because that would
			*this = x;                   // itself call this member swap function.
			x     = temp;
		}
	}


	template <typename T, typename Allocator>
	void list<T, Allocator>::merge(this_type& x)
	{
		if(this != &x)
		{
			iterator       first(begin());
			iterator       firstX(x.begin());
			const iterator last(end());
			const iterator lastX(x.end());

			while((first != last) && (firstX != lastX))
			{
				if(*firstX < *first)
				{
					iterator next(firstX);

					splice(first, x, firstX, ++next);
					firstX = next;
				}
				else
					++first;
			}

			if(firstX != lastX)
				splice(last, x, firstX, lastX);
		}
	}


	template <typename T, typename Allocator>
	void list<T, Allocator>::merge(this_type&& x)
	{
		return merge(x); // This will call merge(this_type&)
	}


	template <typename T, typename Allocator>
	template <typename Compare>
	void list<T, Allocator>::merge(this_type& x, Compare compare)
	{
		if(this != &x)
		{
			iterator       first(begin());
			iterator       firstX(x.begin());
			const iterator last(end());
			const iterator lastX(x.end());

			while((first != last) && (firstX != lastX))
			{
				if(compare(*firstX, *first))
				{
					iterator next(firstX);

					splice(first, x, firstX, ++next);
					firstX = next;
				}
				else
					++first;
			}

			if(firstX != lastX)
				splice(last, x, firstX, lastX);
		}
	}


	template <typename T, typename Allocator>
	template <typename Compare>
	void list<T, Allocator>::merge(this_type&& x, Compare compare)
	{
		return merge(x, compare); // This will call merge(this_type&, Compare)
	}


	template <typename T, typename Allocator>
	void list<T, Allocator>::unique()
	{
		iterator       first(begin());
		const iterator last(end());

		if(first != last)
		{
			iterator next(first);

			while(++next != last)
			{
				if(*first == *next)
					DoErase(next.mpNode);
				else
					first = next;
				next = first;
			}
		}
	}


	template <typename T, typename Allocator>
	template <typename BinaryPredicate>
	void list<T, Allocator>::unique(BinaryPredicate predicate)
	{
		iterator       first(begin());
		const iterator last(end());

		if(first != last)
		{
			iterator next(first);

			while(++next != last)
			{
				if(predicate(*first, *next))
					DoErase(next.mpNode);
				else
					first = next;
				next = first;
			}
		}
	}


	template <typename T, typename Allocator>
	void list<T, Allocator>::sort()
	{
		eastl::less<value_type> compare;
		DoSort(begin(), end(), size(), compare);
	}


	template <typename T, typename Allocator>
	template <typename Compare>
	void list<T, Allocator>::sort(Compare compare)
	{
		DoSort(begin(), end(), size(), compare);
	}


	template <typename T, typename Allocator>
	template <typename Compare>
	typename list<T, Allocator>::iterator
	list<T, Allocator>::DoSort(iterator i1, iterator end2, size_type n, Compare& compare)
	{
		// A previous version of this function did this by creating temporary lists, 
		// but that was incompatible with fixedList because the sizes could be too big.
		// We sort subsegments by recursive descent. Then merge as we ascend.
		// Return an iterator to the beginning of the sorted subsegment.
		// Start with a special case for small node counts.
		switch (n)
		{
			case 0:
			case 1:
				return i1;

			case 2:
				// Potentialy swap these two nodes and return the resulting first of them.
				if(compare(*--end2, *i1))
				{
					end2.mpNode->remove();
					end2.mpNode->insert(i1.mpNode);
					return end2;
				}
				return i1;

			case 3:
			{
				// We do a list insertion sort. Measurements showed this improved performance 3-12%.
				iterator lowest = i1;

				for(iterator current = i1.next(); current != end2; ++current)
				{
					if(compare(*current, *lowest))
						lowest = current;
				}

				if(lowest == i1)
					++i1;
				else
				{
					lowest.mpNode->remove();
					lowest.mpNode->insert(i1.mpNode);
				}

				if(compare(*--end2, *i1)) // At this point, i1 refers to the second element in this three element segment.
				{
					end2.mpNode->remove();
					end2.mpNode->insert(i1.mpNode);
				}

				return lowest;
			}
		 }

		// Divide the range into two parts are recursively sort each part. Upon return we will have
		// two halves that are each sorted but we'll need to merge the two together before returning.
		iterator  result;
		size_type nMid = (n / 2);
		iterator  end1 = eastl::next(i1, (difference_type)nMid);
				  i1   = DoSort(i1, end1, nMid, compare);        // Return the new beginning of the first sorted sub-range.
		iterator  i2   = DoSort(end1, end2, n - nMid, compare);  // Return the new beginning of the second sorted sub-range.

		// If the start of the second list is before the start of the first list, insert the first list 
		// into the second at an appropriate starting place. 
		if(compare(*i2, *i1))
		{
			// Find the position to insert the first list into the second list. 
			iterator ix = i2.next();
			while((ix != end2) && compare(*ix, *i1))
				++ix;

			// Cut out the initial segment of the second list and move it to be in front of the first list. 
			ListNodeBase* i2Cut     = i2.mpNode;
			ListNodeBase* i2CutLast = ix.mpNode->mpPrev;
			result = i2;
			end1   = i2 = ix;
			ListNodeBase::remove_range(i2Cut, i2CutLast);
			i1.mpNode->insert_range(i2Cut, i2CutLast);
		}
		else
		{
			result = i1;
			end1   = i2;
		}

		// Merge the two segments. We do this by merging the second sub-segment into the first, by walking forward in each of the two sub-segments.
		for(++i1; (i1 != end1) && (i2 != end2); ++i1) // while still working on either segment...
		{
			if(compare(*i2, *i1)) // If i2 is less than i1 and it needs to be merged in front of i1...
			{
				// Find the position to insert the i2 list into the i1 list. 
				iterator ix = i2.next();
				while((ix != end2) && compare(*ix, *i1))
					++ix;

				// Cut this section of the i2 sub-segment out and merge into the appropriate place in the i1 list.
				ListNodeBase* i2Cut     = i2.mpNode;
				ListNodeBase* i2CutLast = ix.mpNode->mpPrev;
				if(end1 == i2)
					end1 = ix;
				i2 = ix;
				ListNodeBase::remove_range(i2Cut, i2CutLast);
				i1.mpNode->insert_range(i2Cut, i2CutLast);
			}
		}

		return result;
	}


	template <typename T, typename Allocator>
	template<typename... Args>
	inline typename list<T, Allocator>::node_type*
	list<T, Allocator>::DoCreateNode(Args&&... args)
	{
		node_type* const pNode = DoAllocateNode();  // pNode is of type node_type, but it's uninitialized memory.

		#if EASTL_EXCEPTIONS_ENABLED
			try
			{
				::new((void*)&pNode->mValue) value_type(eastl::forward<Args>(args)...);
			}
			catch(...)
			{
				DoFreeNode(pNode);
				throw;
			}
		#else
			::new((void*)&pNode->mValue) value_type(eastl::forward<Args>(args)...);
		#endif

		return pNode;
	}


	template <typename T, typename Allocator>
	inline typename list<T, Allocator>::node_type*
	list<T, Allocator>::DoCreateNode()
	{
		node_type* const pNode = DoAllocateNode();

		#if EASTL_EXCEPTIONS_ENABLED
			try
			{
				::new((void*)&pNode->mValue) value_type();
			}
			catch(...)
			{
				DoFreeNode(pNode);
				throw;
			}
		#else
			::new((void*)&pNode->mValue) value_type;
		#endif

		return pNode;
	}


	template <typename T, typename Allocator>
	template <typename Integer>
	inline void list<T, Allocator>::DoAssign(Integer n, Integer value, true_type)
	{
		DoAssignValues(static_cast<size_type>(n), static_cast<value_type>(value));
	}


	template <typename T, typename Allocator>
	template <typename InputIterator>
	void list<T, Allocator>::DoAssign(InputIterator first, InputIterator last, false_type)
	{
		node_type* pNode = static_cast<node_type*>(internalNode().mpNext);

		for(; (pNode != &internalNode()) && (first != last); ++first)
		{
			pNode->mValue = *first;
			pNode         = static_cast<node_type*>(pNode->mpNext);
		}

		if(first == last)
			erase(const_iterator(pNode), &internalNode());
		else
			DoInsert(&internalNode(), first, last, false_type());
	}


	template <typename T, typename Allocator>
	void list<T, Allocator>::DoAssignValues(size_type n, const value_type& value)
	{
		node_type* pNode  = static_cast<node_type*>(internalNode().mpNext);

		for(; (pNode != &internalNode()) && (n > 0); --n)
		{
			pNode->mValue = value;
			pNode         = static_cast<node_type*>(pNode->mpNext);
		}

		if(n)
			DoInsertValues(&internalNode(), n, value);
		else
			erase(const_iterator(pNode), &internalNode());
	}


	template <typename T, typename Allocator>
	template <typename Integer>
	inline void list<T, Allocator>::DoInsert(ListNodeBase* pNode, Integer n, Integer value, true_type)
	{
		DoInsertValues(pNode, static_cast<size_type>(n), static_cast<value_type>(value));
	}


	template <typename T, typename Allocator>
	template <typename InputIterator>
	inline void list<T, Allocator>::DoInsert(ListNodeBase* pNode, InputIterator first, InputIterator last, false_type)
	{
		for(; first != last; ++first)
			DoInsertValue(pNode, *first);
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::DoInsertValues(ListNodeBase* pNode, size_type n, const value_type& value)
	{
		for(; n > 0; --n)
			DoInsertValue(pNode, value);
	}


	template <typename T, typename Allocator>
	template<typename... Args>
	inline void list<T, Allocator>::DoInsertValue(ListNodeBase* pNode, Args&&... args)
	{
		node_type* const pNodeNew = DoCreateNode(eastl::forward<Args>(args)...);
		pNodeNew->insert(pNode);
		#if EASTL_LIST_SIZE_CACHE
			++mSize;
		#endif
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::DoErase(ListNodeBase* pNode)
	{
		pNode->remove();
		((node_type*)pNode)->~node_type();
		DoFreeNode(((node_type*)pNode));
		#if EASTL_LIST_SIZE_CACHE
			--mSize;
		#endif

		/* Test version that uses union intermediates
		union
		{
			ListNodeBase* mpBase;
			node_type*    mpNode;
		} node = { pNode };

		node.mpNode->~node_type();
		node.mpBase->remove();
		DoFreeNode(node.mpNode);
		#if EASTL_LIST_SIZE_CACHE
			--mSize;
		#endif
		*/
	}


	template <typename T, typename Allocator>
	inline void list<T, Allocator>::DoSwap(this_type& x)
	{
		ListNodeBase::swap((ListNodeBase&)internalNode(), (ListNodeBase&)x.internalNode()); // We need to implement a special swap because we can't do a shallow swap.
		eastl::swap(internalAllocator(), x.internalAllocator()); // We do this even if EASTL_ALLOCATOR_COPY_ENABLED is 0.
		#if EASTL_LIST_SIZE_CACHE
			eastl::swap(mSize, x.mSize);
		#endif
	}


	template <typename T, typename Allocator>
	inline bool list<T, Allocator>::validate() const
	{
		#if EASTL_LIST_SIZE_CACHE
			size_type n = 0;

			for(const_iterator i(begin()), iEnd(end()); i != iEnd; ++i)
				++n;

			if(n != mSize)
				return false;
		#endif

		// To do: More validation.
		return true;
	}


	template <typename T, typename Allocator>
	inline int list<T, Allocator>::validateIterator(const_iterator i) const
	{
		// To do: Come up with a more efficient mechanism of doing this.

		for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
		{
			if(temp == i)
				return (isf_valid | isf_current | isf_can_dereference);
		}

		if(i == end())
			return (isf_valid | isf_current); 

		return isf_none;
	}



	///////////////////////////////////////////////////////////////////////
	// global operators
	///////////////////////////////////////////////////////////////////////

	template <typename T, typename Allocator>
	bool operator==(const list<T, Allocator>& a, const list<T, Allocator>& b)
	{
		typename list<T, Allocator>::const_iterator ia   = a.begin();
		typename list<T, Allocator>::const_iterator ib   = b.begin();
		typename list<T, Allocator>::const_iterator enda = a.end();

		#if EASTL_LIST_SIZE_CACHE
			if(a.size() == b.size())
			{
				while((ia != enda) && (*ia == *ib))
				{
					++ia;
					++ib;
				}
				return (ia == enda);
			}
			return false;
		#else
			typename list<T, Allocator>::const_iterator endb = b.end();

			while((ia != enda) && (ib != endb) && (*ia == *ib))
			{
				++ia;
				++ib;
			}
			return (ia == enda) && (ib == endb);
		#endif
	}

#if defined(EA_COMPILER_HAS_THREE_WAY_COMPARISON)
	template <typename T, typename Allocator>
	inline synth_three_way_result<T> operator<=>(const list<T, Allocator>& a, const list<T, Allocator>& b)
	{
		return eastl::lexicographicalCompare_three_way(a.begin(), a.end(), b.begin(), b.end(), synth_three_way{});
	}
#else
	template <typename T, typename Allocator>
	bool operator<(const list<T, Allocator>& a, const list<T, Allocator>& b)
	{
		return eastl::lexicographicalCompare(a.begin(), a.end(), b.begin(), b.end());
	}

	template <typename T, typename Allocator>
	bool operator!=(const list<T, Allocator>& a, const list<T, Allocator>& b)
	{
		return !(a == b);
	}

	template <typename T, typename Allocator>
	bool operator>(const list<T, Allocator>& a, const list<T, Allocator>& b)
	{
		return b < a;
	}

	template <typename T, typename Allocator>
	bool operator<=(const list<T, Allocator>& a, const list<T, Allocator>& b)
	{
		return !(b < a);
	}

	template <typename T, typename Allocator>
	bool operator>=(const list<T, Allocator>& a, const list<T, Allocator>& b)
	{
		return !(a < b);
	}
#endif
	template <typename T, typename Allocator>
	void swap(list<T, Allocator>& a, list<T, Allocator>& b)
	{
		a.swap(b);
	}


	///////////////////////////////////////////////////////////////////////
	// erase / erase_if
	//
	// https://en.cppreference.com/w/cpp/container/list/erase2
	///////////////////////////////////////////////////////////////////////
	template <class T, class Allocator, class U>
	typename list<T, Allocator>::size_type erase(list<T, Allocator>& c, const U& value)
	{
		// Erases all elements that compare equal to value from the container.
		return c.remove(value);
	}

	template <class T, class Allocator, class Predicate>
	typename list<T, Allocator>::size_type erase_if(list<T, Allocator>& c, Predicate predicate)
	{
		// Erases all elements that satisfy the predicate pred from the container.
		return c.removeIf(predicate);
	}


} // namespace eastl


EA_RESTORE_SN_WARNING()

EA_RESTORE_VC_WARNING();


#endif // Header include guard