algorithm.h

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

///////////////////////////////////////////////////////////////////////////////
// This file implements some of the primary algorithms from the C++ STL 
// algorithm library. These versions are just like that STL versions and so 
// are redundant. They are provided solely for the purpose of projects that
// either cannot use standard C++ STL or want algorithms that have guaranteed
// identical behaviour across platforms.
///////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////
// Definitions
// 
// You will notice that we are very particular about the templated typenames
// we use here. You will notice that we follow the C++ standard closely in 
// these respects. Each of these typenames have a specific meaning; 
// this is why we don't just label templated arguments with just letters 
// such as T, U, V, A, B. Here we provide a quick reference for the typenames
// we use. See the C++ standard, section 25-8 for more details.
//    --------------------------------------------------------------
//    typename                     Meaning
//    --------------------------------------------------------------
//    T                            The value type.
//    Compare                      A function which takes two arguments and returns the lesser of the two.
//    Predicate                    A function which takes one argument returns true if the argument meets some criteria.
//    BinaryPredicate              A function which takes two arguments and returns true if some criteria is met (e.g. they are equal).
//    StrickWeakOrdering           A BinaryPredicate that compares two objects, returning true if the first precedes the second. Like Compare but has additional requirements. Used for sorting routines.
//    Function                     A function which takes one argument and applies some operation to the target.
//    Size                         A count or size.
//    Generator                    A function which takes no arguments and returns a value (which will usually be assigned to an object).
//    UnaryOperation               A function which takes one argument and returns a value (which will usually be assigned to second object).
//    BinaryOperation              A function which takes two arguments and returns a value (which will usually be assigned to a third object).
//    InputIterator                An input iterator (iterator you read from) which allows reading each element only once and only in a forward direction.
//    ForwardIterator              An input iterator which is like InputIterator except it can be reset back to the beginning.
//    BidirectionalIterator        An input iterator which is like ForwardIterator except it can be read in a backward direction as well.
//    RandomAccessIterator         An input iterator which can be addressed like an array. It is a superset of all other input iterators.
//    OutputIterator               An output iterator (iterator you write to) which allows writing each element only once in only in a forward direction.
//
// Note that with iterators that a function which takes an InputIterator will 
// also work with a ForwardIterator, BidirectionalIterator, or RandomAccessIterator.
// The given iterator type is merely the -minimum- supported functionality the 
// iterator must support.
///////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////
// Optimizations
//
// There are a number of opportunities for opptimizations that we take here
// in this library. The most obvious kinds are those that subsitute memcpy
// in the place of a conventional loop for data types with which this is 
// possible. The algorithms here are optimized to a higher level than currently
// available C++ STL algorithms from vendors such as Microsoft. This is especially
// so for game programming on console devices, as we do things such as reduce 
// branching relative to other STL algorithm implementations. However, the 
// proper implementation of these algorithm optimizations is a fairly tricky
// thing. 
//
// The various things we look to take advantage of in order to implement 
// optimizations include:
//    - Taking advantage of random access iterators.
//    - Taking advantage of POD (plain old data) data types.
//    - Taking advantage of type_traits in general.
//    - Reducing branching and taking advantage of likely branch predictions.
//    - Taking advantage of issues related to pointer and reference aliasing.
//    - Improving cache coherency during memory accesses.
//    - Making code more likely to be inlinable by the compiler.
//
///////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////
// Supported Algorithms
//
// Algorithms that we implement are listed here. Note that these items are not
// all within this header file, as we split up the header files in order to 
// improve compilation performance. Items marked with '+' are items that are
// extensions which don't exist in the C++ standard. 
//
//    -------------------------------------------------------------------------------
//      Algorithm                                   Notes
//    -------------------------------------------------------------------------------
//      adjacentFind
//      adjacentFind<Compare>
//      all_of                                      C++11
//      any_of                                      C++11
//      none_of                                     C++11
//      binarySearch
//      binarySearch<Compare>
//     +binarySearchI
//     +binarySearchI<Compare>
//     +changeHeap                                 Found in heap.h
//     +changeHeap<Compare>                        Found in heap.h
//      copy
//      copy_if                                     C++11
//      copy_n                                      C++11
//      copyBackward
//      count
//      countIf
//      equal
//      equal<Compare>
//      equalRange
//      equalRange<Compare>
//      fill
//      fillN
//      find
//      findEnd
//      findEnd<Compare>
//      findFirstOf
//      findFirstOf<Compare>
//     +findFirstNotOf
//     +findFirstNotOf<Compare>
//     +findLastOf
//     +findLastOf<Compare>
//     +findLastNotOf
//     +findLastNotOf<Compare>
//      findIf
//      findIf_not
//      forEach
//      generate
//      generateN
//     +identical
//     +identical<Compare>
//      iterSwap
//      lexicographicalCompare
//      lexicographicalCompare<Compare>
//      lowerBound
//      lowerBound<Compare>
//      makeHeap                                   Found in heap.h
//      makeHeap<Compare>                          Found in heap.h
//      min
//      min<Compare>
//      max
//      max<Compare>
//     +minAlt                                     Exists to work around the problem of conflicts with min/max #defines on some systems.
//     +minAlt<Compare>
//     +maxAlt
//     +maxAlt<Compare>
//     +median
//     +median<Compare>
//      merge                                       Found in sort.h
//      merge<Compare>                              Found in sort.h
//      minElement
//      minElement<Compare>
//      maxElement
//      maxElement<Compare>
//      mismatch
//      mismatch<Compare>
//      move
//      move_backward
//      nthElement                                 Found in sort.h
//      nthElement<Compare>                        Found in sort.h
//      partialSort                                Found in sort.h
//      partialSort<Compare>                       Found in sort.h
//      pushHeap                                   Found in heap.h
//      pushHeap<Compare>                          Found in heap.h
//      popHeap                                    Found in heap.h
//      popHeap<Compare>                           Found in heap.h
//      random_shuffle<Random>      
//      remove
//      removeIf
//      removeCopy
//      removeCopyIf
//     +removeHeap                                 Found in heap.h
//     +removeHeap<Compare>                        Found in heap.h
//      replace
//      replaceIf
//      replaceCopy
//      replaceCopyIf
//      reverseCopy
//      reverse
//      rotate
//      rotate_copy
//      search
//      search<Compare>
//      searchN
//      setDifference
//      setDifference<Compare>
//      set_intersection
//      set_intersection<Compare>
//      set_symmetric_difference
//      set_symmetric_difference<Compare>
//      sort                                        Found in sort.h
//      sort<Compare>                               Found in sort.h
//      sortHeap                                   Found in heap.h
//      sortHeap<Compare>                          Found in heap.h
//      stableSort                                 Found in sort.h
//      stableSort<Compare>                        Found in sort.h
//      swap
//      swapRanges
//      transform
//      transform<Operation>
//      unique
//      unique<Compare>
//      upperBound
//      upperBound<Compare>
//      is_permutation
//      is_permutation<Predicate>
//      next_permutation
//      next_permutation<Compare>
//
// Algorithms from the C++ standard that we don't implement are listed here.
// Most of these items are absent because they aren't used very often.
// They also happen to be the more complicated than other algorithms.
// However, we can implement any of these functions for users that might 
// need them. 
//      includes
//      includes<Compare>
//      inplace_merge
//      inplace_merge<Compare>
//      partialSort_copy
//      partialSort_copy<Compare>
//      paritition
//      prev_permutation
//      prev_permutation<Compare>
//      random_shuffle
//      searchN<Compare>
//      set_union
//      set_union<Compare>
//      stable_partition
//      unique_copy
//      unique_copy<Compare>
//
///////////////////////////////////////////////////////////////////////////////


#ifndef EASTL_ALGORITHM_H
#define EASTL_ALGORITHM_H


#include <eastl/internal/config.h>
#include <eastl/type_traits.h>
#include <eastl/internal/move_help.h>
#include <eastl/internal/copy_help.h>
#include <eastl/internal/fill_help.h>
#include <eastl/initializer_list.h>
#include <eastl/iterator.h>
#include <eastl/functional.h>
#include <eastl/utility.h>
#include <eastl/internal/generic_iterator.h>
#include <eastl/random.h>

#ifdef _MSC_VER
	#pragma warning(push, 0)
	#if defined(EA_COMPILER_MICROSOFT) && (defined(EA_PROCESSOR_X86) || defined(EA_PROCESSOR_X86_64))
		#include <intrin.h>
	#endif
#endif
	#include <stddef.h>
	#include <string.h> // memcpy, memcmp, memmove
#ifdef _MSC_VER
	#pragma warning(pop)
#endif

#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



///////////////////////////////////////////////////////////////////////////////
// min/max workaround
//
// MSVC++ has #defines for min/max which collide with the min/max algorithm
// declarations. The following may still not completely resolve some kinds of
// problems with MSVC++ #defines, though it deals with most cases in production
// game code.
//
#if EASTL_NOMINMAX
	#ifdef min
		#undef min
	#endif
	#ifdef max
		#undef max
	#endif
#endif




namespace eastl
{
	/// minElement
	///
	/// minElement finds the smallest element in the range [first, last). 
	/// It returns the first iterator i in [first, last) such that no other 
	/// iterator in [first, last) points to a value smaller than *i. 
	/// The return value is last if and only if [first, last) is an empty range.
	///
	/// Returns: The first iterator i in the range [first, last) such that 
	/// for any iterator j in the range [first, last) the following corresponding 
	/// condition holds: !(*j < *i).
	///
	/// Complexity: Exactly 'max((last - first) - 1, 0)' applications of the 
	/// corresponding comparisons.
	///
	template <typename ForwardIterator>
	ForwardIterator minElement(ForwardIterator first, ForwardIterator last)
	{
		if(first != last)
		{
			ForwardIterator currentMin = first;

			while(++first != last)
			{
				if(*first < *currentMin)
					currentMin = first;
			}
			return currentMin;
		}
		return first;
	}


	/// minElement
	///
	/// minElement finds the smallest element in the range [first, last). 
	/// It returns the first iterator i in [first, last) such that no other 
	/// iterator in [first, last) points to a value smaller than *i. 
	/// The return value is last if and only if [first, last) is an empty range.
	///
	/// Returns: The first iterator i in the range [first, last) such that 
	/// for any iterator j in the range [first, last) the following corresponding 
	/// conditions hold: compare(*j, *i) == false.
	///
	/// Complexity: Exactly 'max((last - first) - 1, 0)' applications of the 
	/// corresponding comparisons.
	///
	template <typename ForwardIterator, typename Compare>
	ForwardIterator minElement(ForwardIterator first, ForwardIterator last, Compare compare)
	{
		if(first != last)
		{
			ForwardIterator currentMin = first;

			while(++first != last)
			{
				if(compare(*first, *currentMin))
					currentMin = first;
			}
			return currentMin;
		}
		return first;
	}


	/// maxElement
	///
	/// maxElement finds the largest element in the range [first, last). 
	/// It returns the first iterator i in [first, last) such that no other 
	/// iterator in [first, last) points to a value greater than *i. 
	/// The return value is last if and only if [first, last) is an empty range.
	///
	/// Returns: The first iterator i in the range [first, last) such that 
	/// for any iterator j in the range [first, last) the following corresponding 
	/// condition holds: !(*i < *j).
	///
	/// Complexity: Exactly 'max((last - first) - 1, 0)' applications of the 
	/// corresponding comparisons.
	///
	template <typename ForwardIterator>
	ForwardIterator maxElement(ForwardIterator first, ForwardIterator last)
	{
		if(first != last)
		{
			ForwardIterator currentMax = first;

			while(++first != last)
			{
				if(*currentMax < *first)
					currentMax = first;
			}
			return currentMax;
		}
		return first;
	}


	/// maxElement
	///
	/// maxElement finds the largest element in the range [first, last). 
	/// It returns the first iterator i in [first, last) such that no other 
	/// iterator in [first, last) points to a value greater than *i. 
	/// The return value is last if and only if [first, last) is an empty range.
	///
	/// Returns: The first iterator i in the range [first, last) such that 
	/// for any iterator j in the range [first, last) the following corresponding 
	/// condition holds: compare(*i, *j) == false.
	///
	/// Complexity: Exactly 'max((last - first) - 1, 0)' applications of the 
	/// corresponding comparisons.
	///
	template <typename ForwardIterator, typename Compare>
	ForwardIterator maxElement(ForwardIterator first, ForwardIterator last, Compare compare)
	{
		if(first != last)
		{
			ForwardIterator currentMax = first;

			while(++first != last)
			{
				if(compare(*currentMax, *first))
					currentMax = first;
			}
			return currentMax;
		}
		return first;
	}


	#if EASTL_MINMAX_ENABLED

		/// min
		///
		/// Min returns the lesser of its two arguments; it returns the first 
		/// argument if neither is less than the other. The two arguments are
		/// compared with operator <.
		///
		/// This min and our other min implementations are defined as returning:
		///     b < a ? b : a
		/// which for example may in practice result in something different than:
		///     b <= a ? b : a
		/// in the case where b is different from a (though they compare as equal).
		/// We choose the specific ordering here because that's the ordering 
		/// done by other STL implementations.
		///
		/// Some compilers (e.g. VS20003 - VS2013) generate poor code for the case of  
		/// scalars returned by reference, so we provide a specialization for those cases.
		/// The specialization returns T by value instead of reference, which is 
		/// not that the Standard specifies. The Standard allows you to use
		/// an expression like &max(x, y), which would be impossible in this case.
		/// However, we have found no actual code that uses min or max like this and 
		/// this specialization causes no problems in practice. Microsoft has acknowledged
		/// the problem and may fix it for a future VS version.
		///
		template <typename T>
		inline EA_CONSTEXPR typename eastl::enable_if<eastl::is_scalar<T>::value, T>::type
		min(T a, T b)
		{
			return b < a ? b : a;
		}
	
		template <typename T>
		inline typename eastl::enable_if<!eastl::is_scalar<T>::value, const T&>::type
		min(const T& a, const T& b)
		{
			return b < a ? b : a;
		}

		#if defined(_MSC_VER) && defined(EA_PROCESSOR_POWERPC)
			inline float
			min(float a, float b)  
			{
				return (float)__fsel(a - b, b, a);
			}

			inline double
			min(double a, double b)  
			{
				return (double)__fsel(a - b, b, a);
			}

		#elif defined(_MSC_VER) && defined(EA_PROCESSOR_X86)

			// We used to have x86 asm here, but it didn't improve performance.

		#elif defined(__GNUC__) && defined(EA_PROCESSOR_POWERPC)
			inline float
			min(float a, float b)  
			{
				float result, test(a - b);
				__asm__ ("fsel %0, %1, %2, %3" : "=f" (result) : "f" (test), "f" (b), "f" (a));
				return result;
			}

			inline double
			min(double a, double b)  
			{
				double result, test(a - b);
				__asm__ ("fsel %0, %1, %2, %3" : "=f" (result) : "f" (test), "f" (b), "f" (a));
				return result;
			}
		#else
			inline EA_CONSTEXPR float       min(float  a, float   b)           { return b < a ? b : a; }
			inline EA_CONSTEXPR double      min(double a, double  b)           { return b < a ? b : a; }
			inline EA_CONSTEXPR long double min(long double a, long double  b) { return b < a ? b : a; }
		#endif

	#endif // EASTL_MINMAX_ENABLED


	/// minAlt
	///
	/// This is an alternative version of min that avoids any possible 
	/// collisions with Microsoft #defines of min and max.
	///
	/// See min(a, b) for detailed specifications.
	///
	template <typename T>
	inline EA_CONSTEXPR typename eastl::enable_if<eastl::is_scalar<T>::value, T>::type
	minAlt(T a, T b)
	{
		return b < a ? b : a;
	}

	template <typename T>
	inline typename eastl::enable_if<!eastl::is_scalar<T>::value, const T&>::type
	minAlt(const T& a, const T& b)
	{
		return b < a ? b : a;
	}


	#if defined(_MSC_VER) && defined(EA_PROCESSOR_POWERPC)
		inline float
		minAlt(float a, float b)  
		{
			return (float)__fsel(a - b, b, a);
		}

		inline double
		minAlt(double a, double b)  
		{
			return (double)__fsel(a - b, b, a);
		}

	#elif defined(_MSC_VER) && defined(EA_PROCESSOR_X86)

		// We used to have x86 asm here, but it didn't improve performance.

	#elif defined(__GNUC__) && defined(EA_PROCESSOR_POWERPC)
		inline float
		minAlt(float a, float b)  
		{
			float result, test(a - b);
			__asm__ ("fsel %0, %1, %2, %3" : "=f" (result) : "f" (test), "f" (b), "f" (a));
			return result;
		}

		inline double
		minAlt(double a, double b)  
		{
			double result, test(a - b);
			__asm__ ("fsel %0, %1, %2, %3" : "=f" (result) : "f" (test), "f" (b), "f" (a));
			return result;
		}
	#else
		inline EA_CONSTEXPR float       minAlt(float  a, float   b)           { return b < a ? b : a; }
		inline EA_CONSTEXPR double      minAlt(double a, double  b)           { return b < a ? b : a; }
		inline EA_CONSTEXPR long double minAlt(long double a, long double  b) { return b < a ? b : a; }
	#endif


	#if EASTL_MINMAX_ENABLED
		/// min
		///
		/// Min returns the lesser of its two arguments; it returns the first 
		/// argument if neither is less than the other. The two arguments are
		/// compared with the Compare function (or function object), which 
		/// takes two arguments and returns true if the first is less than 
		/// the second.
		///
		/// See min(a, b) for detailed specifications.
		///
		/// Example usage:
		///    struct A{ int a; };
		///    struct Struct{ bool operator()(const A& a1, const A& a2){ return a1.a < a2.a; } };
		///
		///    A a1, a2, a3;
		///    a3 = min(a1, a2, Struct());
		///
		/// Example usage:
		///    struct B{ int b; };
		///    inline bool Function(const B& b1, const B& b2){ return b1.b < b2.b; }
		///
		///    B b1, b2, b3;
		///    b3 = min(b1, b2, Function);
		///
		template <typename T, typename Compare>
		inline const T&
		min(const T& a, const T& b, Compare compare)
		{
			return compare(b, a) ? b : a;
		}

	#endif // EASTL_MINMAX_ENABLED


	/// minAlt
	///
	/// This is an alternative version of min that avoids any possible 
	/// collisions with Microsoft #defines of min and max.
	///
	/// See min(a, b) for detailed specifications.
	///
	template <typename T, typename Compare>
	inline const T&
	minAlt(const T& a, const T& b, Compare compare)
	{
		return compare(b, a) ? b : a;
	}


	#if EASTL_MINMAX_ENABLED
		/// max
		///
		/// Max returns the greater of its two arguments; it returns the first 
		/// argument if neither is greater than the other. The two arguments are
		/// compared with operator < (and not operator >).
		///
		/// This min and our other min implementations are defined as returning:
		///     a < b ? b : a
		/// which for example may in practice result in something different than:
		///     a <= b ? b : a
		/// in the case where b is different from a (though they compare as equal).
		/// We choose the specific ordering here because that's the ordering 
		/// done by other STL implementations.
		///
		template <typename T>
		inline EA_CONSTEXPR typename eastl::enable_if<eastl::is_scalar<T>::value, T>::type
		max(T a, T b)
		{
			return a < b ? b : a;
		}

		template <typename T>
		inline typename eastl::enable_if<!eastl::is_scalar<T>::value, const T&>::type
		max(const T& a, const T& b)
		{
			return a < b ? b : a;
		}


		#if defined(_MSC_VER) && defined(EA_PROCESSOR_POWERPC)
			inline float
			max(float a, float b)  
			{
				return (float)__fsel(a - b, a, b);
			}

			inline double
			max(double a, double b)  
			{
				return (double)__fsel(a - b, a, b);
			}

		#elif defined(_MSC_VER) && defined(EA_PROCESSOR_X86)

			// We used to have x86 asm here, but it didn't improve performance.

		#elif defined(__GNUC__) && defined(EA_PROCESSOR_POWERPC)
			inline float
			max(float a, float b)  
			{
				float result, test(a - b);
				__asm__ ("fsel %0, %1, %2, %3" : "=f" (result) : "f" (test), "f" (a), "f" (b));
				return result;
			}

			inline double
			max(double a, double b)  
			{
				double result, test(a - b);
				__asm__ ("fsel %0, %1, %2, %3" : "=f" (result) : "f" (test), "f" (a), "f" (b));
				return result;
			}
		#else
			inline EA_CONSTEXPR float       max(float       a, float       b) { return a < b ? b : a; }
			inline EA_CONSTEXPR double      max(double      a, double      b) { return a < b ? b : a; }
			inline EA_CONSTEXPR long double max(long double a, long double b) { return a < b ? b : a; }
		#endif

	#endif // EASTL_MINMAX_ENABLED


	/// maxAlt
	///
	/// This is an alternative version of max that avoids any possible 
	/// collisions with Microsoft #defines of min and max.
	///
	template <typename T>
	inline EA_CONSTEXPR typename eastl::enable_if<eastl::is_scalar<T>::value, T>::type
	maxAlt(T a, T b)
	{
		return a < b ? b : a;
	}

	template <typename T>
	inline typename eastl::enable_if<!eastl::is_scalar<T>::value, const T&>::type
	maxAlt(const T& a, const T& b)
	{
		return a < b ? b : a;
	}

	#if defined(_MSC_VER) && defined(EA_PROCESSOR_POWERPC)
		inline float
		maxAlt(float a, float b)  
		{
			return (float)__fsel(a - b, a, b);
		}

		inline double
		maxAlt(double a, double b)  
		{
			return (double)__fsel(a - b, a, b);
		}

	#elif defined(_MSC_VER) && defined(EA_PROCESSOR_X86)

		// We used to have x86 asm here, but it didn't improve performance.

	#elif defined(__GNUC__) && defined(EA_PROCESSOR_POWERPC)
		inline float
		maxAlt(float a, float b)  
		{
			float result, test(a - b);
			__asm__ ("fsel %0, %1, %2, %3" : "=f" (result) : "f" (test), "f" (a), "f" (b));
			return result;
		}

		inline double
		maxAlt(double a, double b)  
		{
			double result, test(a - b);
			__asm__ ("fsel %0, %1, %2, %3" : "=f" (result) : "f" (test), "f" (a), "f" (b));
			return result;
		}
		#else
			inline EA_CONSTEXPR float       maxAlt(float       a, float       b) { return a < b ? b : a; }
			inline EA_CONSTEXPR double      maxAlt(double      a, double      b) { return a < b ? b : a; }
			inline EA_CONSTEXPR long double maxAlt(long double a, long double b) { return a < b ? b : a; }
	#endif


	#if EASTL_MINMAX_ENABLED
		/// max
		///
		/// Min returns the lesser of its two arguments; it returns the first 
		/// argument if neither is less than the other. The two arguments are
		/// compared with the Compare function (or function object), which 
		/// takes two arguments and returns true if the first is less than 
		/// the second.
		///
		template <typename T, typename Compare>
		inline const T&
		max(const T& a, const T& b, Compare compare)
		{
			return compare(a, b) ? b : a;
		}
	#endif
 

	/// maxAlt
	///
	/// This is an alternative version of max that avoids any possible 
	/// collisions with Microsoft #defines of min and max.
	///
	template <typename T, typename Compare>
	inline const T&
	maxAlt(const T& a, const T& b, Compare compare)
	{
		return compare(a, b) ? b : a;
	}


	/// min(std::initializer_list)
	///
	template <typename T >
	T min(std::initializer_list<T> ilist)
	{
		return *eastl::minElement(ilist.begin(), ilist.end());
	}

	/// min(std::initializer_list, Compare)
	///
	template <typename T, typename Compare>
	T min(std::initializer_list<T> ilist, Compare compare)
	{
		return *eastl::minElement(ilist.begin(), ilist.end(), compare);
	}


	/// max(std::initializer_list)
	///
	template <typename T >
	T max(std::initializer_list<T> ilist)
	{
		return *eastl::maxElement(ilist.begin(), ilist.end());
	}

	/// max(std::initializer_list, Compare)
	///
	template <typename T, typename Compare>
	T max(std::initializer_list<T> ilist, Compare compare)
	{
		return *eastl::maxElement(ilist.begin(), ilist.end(), compare);
	}


	/// minmaxElement
	///
	/// Returns: makePair(first, first) if [first, last) is empty, otherwise makePair(m, M), 
	/// where m is the first iterator in [first,last) such that no iterator in the range 
	/// refers to a smaller element, and where M is the last iterator in [first,last) such 
	/// that no iterator in the range refers to a larger element.
	///
	/// Complexity: At most max([(3/2)*(N - 1)], 0) applications of the corresponding predicate, 
	/// where N is distance(first, last).
	///
	template <typename ForwardIterator, typename Compare>
	eastl::pair<ForwardIterator, ForwardIterator> 
	minmaxElement(ForwardIterator first, ForwardIterator last, Compare compare)
	{
		eastl::pair<ForwardIterator, ForwardIterator> result(first, first);
 
		if(!(first == last) && !(++first == last))
		{ 
			if(compare(*first, *result.first))
			{
				result.second = result.first;
				result.first = first;
			}
			else
				result.second = first;

			while(++first != last)
			{
				ForwardIterator i = first;

				if(++first == last)
				{
					if(compare(*i, *result.first)) 
						result.first = i;
					else if(!compare(*i, *result.second)) 
						result.second = i;
					break;
				} 
				else
				{
					if(compare(*first, *i))
					{
						if(compare(*first, *result.first)) 
							result.first = first;

						if(!compare(*i, *result.second)) 
							result.second = i;
					} 
					else
					{
						if(compare(*i, *result.first))
							result.first = i;

						if(!compare(*first, *result.second))
							result.second = first;
					}
				}
			}
		}

		return result;
	}


	template <typename ForwardIterator>
	eastl::pair<ForwardIterator, ForwardIterator> 
	minmaxElement(ForwardIterator first, ForwardIterator last)
	{
		typedef typename eastl::iterator_traits<ForwardIterator>::value_type value_type;

		return eastl::minmaxElement(first, last, eastl::less<value_type>());
	}



	/// minmax
	///
	/// Requires: Type T shall be LessThanComparable.
	/// Returns: pair<const T&, const T&>(b, a) if b is smaller than a, and pair<const T&, const T&>(a, b) otherwise.
	/// Remarks: Returns pair<const T&, const T&>(a, b) when the arguments are equivalent.
	/// Complexity: Exactly one comparison.
	///

	// The following optimization is a problem because it changes the return value in a way that would break
	// users unless they used auto (e.g. auto result = minmax(17, 33); )
	//
	// template <typename T> 
	// inline EA_CONSTEXPR typename eastl::enable_if<eastl::is_scalar<T>::value, eastl::pair<T, T> >::type
	// minmax(T a, T b)
	// {
	//     return (b < a) ? eastl::makePair(b, a) : eastl::makePair(a, b);
	// }
	//
	// template <typename T> 
	// inline typename eastl::enable_if<!eastl::is_scalar<T>::value, eastl::pair<const T&, const T&> >::type
	// minmax(const T& a, const T& b)
	// {
	//     return (b < a) ? eastl::makePair(b, a) : eastl::makePair(a, b);
	// }

	// It turns out that the following conforming definition of minmax generates a warning when used with VC++ up
	// to at least VS2012. The VS2012 version of minmax is a broken and non-conforming definition, and we don't
	// want to do that. We could do it for scalars alone, though we'd have to decide if we are going to do that 
	// for all compilers, because it changes the return value from a pair of references to a pair of values.
	template <typename T> 
	inline eastl::pair<const T&, const T&>
	minmax(const T& a, const T& b)
	{
		return (b < a) ? eastl::makePair(b, a) : eastl::makePair(a, b);
	}


	template <typename T, typename Compare> 
	eastl::pair<const T&, const T&>
	minmax(const T& a, const T& b, Compare compare)
	{
		return compare(b, a) ? eastl::makePair(b, a) : eastl::makePair(a, b);
	}



	template <typename T>
	eastl::pair<T, T>
	minmax(std::initializer_list<T> ilist)
	{
		typedef typename std::initializer_list<T>::iterator iterator_type;
		eastl::pair<iterator_type, iterator_type> iteratorPair = eastl::minmaxElement(ilist.begin(), ilist.end());
		return eastl::makePair(*iteratorPair.first, *iteratorPair.second);
	}

	template <typename T, class Compare>
	eastl::pair<T, T>
	minmax(std::initializer_list<T> ilist, Compare compare)
	{
		typedef typename std::initializer_list<T>::iterator iterator_type;
		eastl::pair<iterator_type, iterator_type> iteratorPair = eastl::minmaxElement(ilist.begin(), ilist.end(), compare);
		return eastl::makePair(*iteratorPair.first, *iteratorPair.second);
	}


	/// median
	///
	/// median finds which element of three (a, b, d) is in-between the other two.
	/// If two or more elements are equal, the first (e.g. a before b) is chosen.
	///
	/// Complexity: Either two or three comparisons will be required, depending 
	/// on the values.
	///
	template <typename T>
	inline const T& median(const T& a, const T& b, const T& c)
	{
		if(a < b)
		{
			if(b < c)
				return b;
			else if(a < c)
				return c;
			else
				return a;
		}
		else if(a < c)
			return a;
		else if(b < c)
			return c;
		return b;
	}


	/// median
	///
	/// median finds which element of three (a, b, d) is in-between the other two.
	/// If two or more elements are equal, the first (e.g. a before b) is chosen.
	///
	/// Complexity: Either two or three comparisons will be required, depending 
	/// on the values.
	///
	template <typename T, typename Compare>
	inline const T& median(const T& a, const T& b, const T& c, Compare compare)
	{
		if(compare(a, b))
		{
			if(compare(b, c))
				return b;
			else if(compare(a, c))
				return c;
			else
				return a;
		}
		else if(compare(a, c))
			return a;
		else if(compare(b, c))
			return c;
		return b;
	}




	/// all_of
	///
	/// Returns: true if the unary predicate p returns true for all elements in the range [first, last)
	///
	template <typename InputIterator, typename Predicate>
	inline bool all_of(InputIterator first, InputIterator last, Predicate p)
	{
		for(; first != last; ++first)
		{
			if(!p(*first))
				return false;
		}
		return true;
	}


	/// any_of
	///
	/// Returns: true if the unary predicate p returns true for any of the elements in the range [first, last)
	///
	template <typename InputIterator, typename Predicate>
	inline bool any_of(InputIterator first, InputIterator last, Predicate p)
	{
		for(; first != last; ++first)
		{
			if(p(*first))
				return true;
		}
		return false;
	}


	/// none_of
	///
	/// Returns: true if the unary predicate p returns true for none of the elements in the range [first, last)
	///
	template <typename InputIterator, typename Predicate>
	inline bool none_of(InputIterator first, InputIterator last, Predicate p)
	{
		for(; first != last; ++first)
		{
			if(p(*first)) 
				return false;
		}
		return true;
	}


	/// adjacentFind
	///
	/// Returns: The first iterator i such that both i and i + 1 are in the range 
	/// [first, last) for which the following corresponding conditions hold: *i == *(i + 1). 
	/// Returns last if no such iterator is found.
	///
	/// Complexity: Exactly 'find(first, last, value) - first' applications of the corresponding predicate.
	///
	template <typename ForwardIterator>
	inline ForwardIterator 
	adjacentFind(ForwardIterator first, ForwardIterator last)
	{
		if(first != last)
		{
			ForwardIterator i = first;

			for(++i; i != last; ++i)
			{
				if(*first == *i)
					return first;
				first = i;
			}
		}
		return last;
	}



	/// adjacentFind
	///
	/// Returns: The first iterator i such that both i and i + 1 are in the range 
	/// [first, last) for which the following corresponding conditions hold: predicate(*i, *(i + 1)) != false. 
	/// Returns last if no such iterator is found.
	///
	/// Complexity: Exactly 'find(first, last, value) - first' applications of the corresponding predicate.
	///
	template <typename ForwardIterator, typename BinaryPredicate>
	inline ForwardIterator 
	adjacentFind(ForwardIterator first, ForwardIterator last, BinaryPredicate predicate)
	{
		if(first != last)
		{
			ForwardIterator i = first;

			for(++i; i != last; ++i)
			{
				if(predicate(*first, *i))
					return first;
				first = i;
			}
		}
		return last;
	}


	/// shuffle
	///
	/// New for C++11
	/// Randomizes a sequence of values via a user-supplied UniformRandomNumberGenerator.
	/// The difference between this and the original random_shuffle function is that this uses the more
	/// advanced and flexible UniformRandomNumberGenerator interface as opposed to the more 
	/// limited RandomNumberGenerator interface of random_shuffle.
	///
	/// Effects: Shuffles the elements in the range [first, last) with uniform distribution.
	///
	/// Complexity: Exactly '(last - first) - 1' swaps.
	///
	/// Example usage:
	///     struct Rand{ eastl_size_t operator()(eastl_size_t n) { return (eastl_size_t)(rand() % n); } }; // Note: The C rand function is poor and slow.
	///     Rand randInstance;
	///     shuffle(pArrayBegin, pArrayEnd, randInstance);
	///
	#if EASTL_MOVE_SEMANTICS_ENABLED
		// See the C++11 Standard, 26.5.1.3, Uniform random number generator requirements.
		// Also http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution

		template <typename RandomAccessIterator, typename UniformRandomNumberGenerator>
		void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& urng)
		{
			if(first != last)
			{
				typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
				typedef typename eastl::make_unsigned<difference_type>::type                   unsigned_difference_type;
				typedef typename eastl::uniform_int_distribution<unsigned_difference_type>     uniform_int_distribution;
				typedef typename uniform_int_distribution::param_type                          uniform_int_distribution_param_type;

				uniform_int_distribution uid;

				for(RandomAccessIterator i = first + 1; i != last; ++i)
					iterSwap(i, first + uid(urng, uniform_int_distribution_param_type(0, i - first)));
			}
		}
	#endif


	/// random_shuffle
	///
	/// Randomizes a sequence of values.
	///
	/// Effects: Shuffles the elements in the range [first, last) with uniform distribution.
	///
	/// Complexity: Exactly '(last - first) - 1' swaps.
	///
	/// Example usage:
	///     eastl_size_t Rand(eastl_size_t n) { return (eastl_size_t)(rand() % n); } // Note: The C rand function is poor and slow.
	///     pointer_to_unary_function<eastl_size_t, eastl_size_t> randInstance(Rand);
	///     random_shuffle(pArrayBegin, pArrayEnd, randInstance);
	///
	/// Example usage:
	///     struct Rand{ eastl_size_t operator()(eastl_size_t n) { return (eastl_size_t)(rand() % n); } }; // Note: The C rand function is poor and slow.
	///     Rand randInstance;
	///     random_shuffle(pArrayBegin, pArrayEnd, randInstance);
	///
	#if EASTL_MOVE_SEMANTICS_ENABLED
		template <typename RandomAccessIterator, typename RandomNumberGenerator>
		inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator&& rng)
	#else
		template <typename RandomAccessIterator, typename RandomNumberGenerator>
		inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rng)
	#endif
		{
			typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;

			// We must do 'rand((i - first) + 1)' here and cannot do 'rand(last - first)',
			// as it turns out that the latter results in unequal distribution probabilities.
			// http://www.cigital.com/papers/download/developer_gambling.php

			for(RandomAccessIterator i = first + 1; i < last; ++i)               
				iterSwap(i, first + (difference_type)rng((eastl_size_t)((i - first) + 1)));
		}


	/// random_shuffle
	///
	/// Randomizes a sequence of values.
	///
	/// Effects: Shuffles the elements in the range [first, last) with uniform distribution.
	///
	/// Complexity: Exactly '(last - first) - 1' swaps.
	///
	/// Example usage:
	///     random_shuffle(pArrayBegin, pArrayEnd);
	///
	/// *** Disabled until we decide if we want to get into the business of writing random number generators. ***
	///
	/// template <typename RandomAccessIterator>
	/// inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last)
	/// {
	///     for(RandomAccessIterator i = first + 1; i < last; ++i)
	///         iterSwap(i, first + SomeRangedRandomNumberGenerator((i - first) + 1)); 
	/// }






	/// move_n
	///
	/// Same as move(InputIterator, InputIterator, OutputIterator) except based on count instead of iterator range.
	///
	template <typename InputIterator, typename Size, typename OutputIterator>
	inline OutputIterator
	move_n_impl(InputIterator first, Size n, OutputIterator result, EASTL_ITC_NS::input_iterator_tag)
	{
		for(; n > 0; --n)
			*result++ = eastl::move(*first++);
		return result;
	}

	template <typename RandomAccessIterator, typename Size, typename OutputIterator>
	inline OutputIterator
	move_n_impl(RandomAccessIterator first, Size n, OutputIterator result, EASTL_ITC_NS::random_access_iterator_tag)
	{ 
		return eastl::move(first, first + n, result); // Take advantage of the optimizations present in the move algorithm.
	}


	template <typename InputIterator, typename Size, typename OutputIterator>
	inline OutputIterator 
	move_n(InputIterator first, Size n, OutputIterator result)
	{
		typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
		return eastl::move_n_impl(first, n, result, IC());
	}



	/// copy_n
	///
	/// Same as copy(InputIterator, InputIterator, OutputIterator) except based on count instead of iterator range.
	/// Effects: Copies exactly count values from the range beginning at first to the range beginning at result, if count > 0. Does nothing otherwise. 
	/// Returns: Iterator in the destination range, pointing past the last element copied if count>0 or first otherwise. 
	/// Complexity: Exactly count assignments, if count > 0. 
	///
	template <typename InputIterator, typename Size, typename OutputIterator>
	inline OutputIterator
	copy_n_impl(InputIterator first, Size n, OutputIterator result, EASTL_ITC_NS::input_iterator_tag)
	{
		for(; n > 0; --n)
			*result++ = *first++;
		return result;
	}

	template <typename RandomAccessIterator, typename Size, typename OutputIterator>
	inline OutputIterator
	copy_n_impl(RandomAccessIterator first, Size n, OutputIterator result, EASTL_ITC_NS::random_access_iterator_tag)
	{ 
		return eastl::copy(first, first + n, result); // Take advantage of the optimizations present in the copy algorithm.
	}


	template <typename InputIterator, typename Size, typename OutputIterator>
	inline OutputIterator 
	copy_n(InputIterator first, Size n, OutputIterator result)
	{
		typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
		return eastl::copy_n_impl(first, n, result, IC());
	}


	/// copy_if
	///
	/// Effects: Assigns to the result iterator only if the predicate is true.
	/// 
	template <typename InputIterator, typename OutputIterator, typename Predicate>
	inline OutputIterator
	copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate)
	{
		// This implementation's performance could be improved by taking a more complicated approach like with the copy algorithm.
		for(; first != last; ++first)
		{
			if(predicate(*first))
				*result++ = *first;
		}

		return result;
	}




	// Implementation moving copying both trivial and non-trivial data via a lesser iterator than random-access.
	template <typename /*BidirectionalIterator1Category*/, bool /*isMove*/, bool /*canMemmove*/>
	struct move_and_copyBackward_helper
	{
		template <typename BidirectionalIterator1, typename BidirectionalIterator2>
		static BidirectionalIterator2 move_or_copyBackward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
		{
			while(first != last)
				*--resultEnd = *--last;
			return resultEnd; // resultEnd now points to the beginning of the destination sequence instead of the end.
		}
	};

	// Specialization for moving non-trivial data via a lesser iterator than random-access.
	template <typename BidirectionalIterator1Category>
	struct move_and_copyBackward_helper<BidirectionalIterator1Category, true, false>
	{
		template <typename BidirectionalIterator1, typename BidirectionalIterator2>
		static BidirectionalIterator2 move_or_copyBackward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
		{
			while(first != last)
				*--resultEnd = eastl::move(*--last);
			return resultEnd; // resultEnd now points to the beginning of the destination sequence instead of the end.
		}
	};

	// Specialization for moving non-trivial data via a random-access iterator. It's theoretically faster because the compiler can see the count when its a compile-time const.
	template<>
	struct move_and_copyBackward_helper<EASTL_ITC_NS::random_access_iterator_tag, true, false>
	{
		template<typename BidirectionalIterator1, typename BidirectionalIterator2>
		static BidirectionalIterator2 move_or_copyBackward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
		{
			typedef typename eastl::iterator_traits<BidirectionalIterator1>::difference_type difference_type;

			for(difference_type n = (last - first); n > 0; --n)
				*--resultEnd = eastl::move(*--last);
			return resultEnd; // resultEnd now points to the beginning of the destination sequence instead of the end.
		}
	};

	// Specialization for copying non-trivial data via a random-access iterator. It's theoretically faster because the compiler can see the count when its a compile-time const.
	// This specialization converts the random access BidirectionalIterator1 last-first to an integral type. There's simple way for us to take advantage of a random access output iterator,
	// as the range is specified by the input instead of the output, and distance(first, last) for a non-random-access iterator is potentially slow.
	template <> 
	struct move_and_copyBackward_helper<EASTL_ITC_NS::random_access_iterator_tag, false, false>
	{
		template <typename BidirectionalIterator1, typename BidirectionalIterator2>
		static BidirectionalIterator2 move_or_copyBackward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
		{
			typedef typename eastl::iterator_traits<BidirectionalIterator1>::difference_type difference_type;

			for(difference_type n = (last - first); n > 0; --n)
				*--resultEnd = *--last;
			return resultEnd; // resultEnd now points to the beginning of the destination sequence instead of the end.
		}
	};

	// Specialization for when we can use memmove/memcpy. See the notes above for what conditions allow this.
	template <bool isMove>
	struct move_and_copyBackward_helper<EASTL_ITC_NS::random_access_iterator_tag, isMove, true>
	{
		template <typename T>
		static T* move_or_copyBackward(const T* first, const T* last, T* resultEnd)
		{
			return (T*)memmove(resultEnd - (last - first), first, (size_t)((uintptr_t)last - (uintptr_t)first));
			// We could use memcpy here if there's no range overlap, but memcpy is rarely much faster than memmove.
		}
	};

	template <bool isMove, typename BidirectionalIterator1, typename BidirectionalIterator2>
	inline BidirectionalIterator2 move_and_copyBackward_chooser(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
	{
		typedef typename eastl::iterator_traits<BidirectionalIterator1>::iterator_category IIC;
		typedef typename eastl::iterator_traits<BidirectionalIterator2>::iterator_category OIC;
		typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type        value_type_input;
		typedef typename eastl::iterator_traits<BidirectionalIterator2>::value_type        value_type_output;

		const bool canBeMemmoved = eastl::is_trivially_copyable<value_type_output>::value && 
								   eastl::is_same<value_type_input, value_type_output>::value && 
								  (eastl::is_pointer<BidirectionalIterator1>::value || eastl::is_same<IIC, eastl::contiguous_iterator_tag>::value) && 
								  (eastl::is_pointer<BidirectionalIterator2>::value || eastl::is_same<OIC, eastl::contiguous_iterator_tag>::value);

		return eastl::move_and_copyBackward_helper<IIC, isMove, canBeMemmoved>::move_or_copyBackward(first, last, resultEnd); // Need to chose based on the input iterator tag and not the output iterator tag, because containers accept input ranges of iterator types different than self.
	}


	// We have a second layer of unwrap_iterator calls because the original iterator might be something like move_iterator<generic_iterator<int*> > (i.e. doubly-wrapped).
	template <bool isMove, typename BidirectionalIterator1, typename BidirectionalIterator2>
	inline BidirectionalIterator2 move_and_copyBackward_unwrapper(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
	{
		return BidirectionalIterator2(eastl::move_and_copyBackward_chooser<isMove>(eastl::unwrap_iterator(first), eastl::unwrap_iterator(last), eastl::unwrap_iterator(resultEnd))); // Have to convert to BidirectionalIterator2 because result.base() could be a T*
	}


	/// move_backward
	///
	/// The elements are moved in reverse order (the last element is moved first), but their relative order is preserved. 
	/// After this operation the elements in the moved-from range will still contain valid values of the 
	/// appropriate type, but not necessarily the same values as before the move. 
	/// Returns the beginning of the result range.
	/// Note: When moving between containers, the dest range must be valid; this function doesn't resize containers.
	/// Note: If result is within [first, last), move must be used instead of move_backward. 
	///
	/// Example usage:
	///     eastl::move_backward(myArray.begin(), myArray.end(), myDestArray.end()); 
	/// 
	/// Reference implementation:
	///     template <typename BidirectionalIterator1, typename BidirectionalIterator2>
	///     BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
	///     {
	///         while(last != first)
	///             *--resultEnd = eastl::move(*--last);
	///         return resultEnd;
	///     }
	/// 
	template <typename BidirectionalIterator1, typename BidirectionalIterator2>
	inline BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
	{
		return eastl::move_and_copyBackward_unwrapper<true>(eastl::unwrap_iterator(first), eastl::unwrap_iterator(last), resultEnd);
	}


	/// copyBackward
	///
	/// copies memory in the range of [first, last) to the range *ending* with result.
	/// 
	/// Effects: Copies elements in the range [first, last) into the range 
	/// [result - (last - first), result) starting from last 1 and proceeding to first. 
	/// For each positive integer n <= (last - first), performs *(result n) = *(last - n).
	///
	/// Requires: result shall not be in the range [first, last).
	///
	/// Returns: result - (last - first). That is, returns the beginning of the result range.
	///
	/// Complexity: Exactly 'last - first' assignments.
	/// 
	template <typename BidirectionalIterator1, typename BidirectionalIterator2>
	inline BidirectionalIterator2 copyBackward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
	{
		const bool isMove = eastl::is_move_iterator<BidirectionalIterator1>::value; EA_UNUSED(isMove);

		return eastl::move_and_copyBackward_unwrapper<isMove>(eastl::unwrap_iterator(first), eastl::unwrap_iterator(last), resultEnd);
	}


	/// count
	///
	/// Counts the number of items in the range of [first, last) which equal the input value.
	///
	/// Effects: Returns the number of iterators i in the range [first, last) for which the 
	/// following corresponding conditions hold: *i == value.
	///
	/// Complexity: At most 'last - first' applications of the corresponding predicate.
	///
	/// Note: The predicate version of count is countIf and not another variation of count.
	/// This is because both versions would have three parameters and there could be ambiguity.
	///
	template <typename InputIterator, typename T>
	inline typename eastl::iterator_traits<InputIterator>::difference_type
	count(InputIterator first, InputIterator last, const T& value)
	{
		typename eastl::iterator_traits<InputIterator>::difference_type result = 0;

		for(; first != last; ++first)
		{
			if(*first == value)
				++result;
		}
		return result;
	}


	// C++ doesn't define a count with predicate, as it can effectively be synthesized via countIf
	// with an appropriate predicate. However, it's often simpler to just have count with a predicate.
	template <typename InputIterator, typename T, typename Predicate>
	inline typename eastl::iterator_traits<InputIterator>::difference_type
	count(InputIterator first, InputIterator last, const T& value, Predicate predicate)
	{
		typename eastl::iterator_traits<InputIterator>::difference_type result = 0;

		for(; first != last; ++first)
		{
			if(predicate(*first, value))
				++result;
		}
		return result;
	}


	/// countIf
	///
	/// Counts the number of items in the range of [first, last) which match 
	/// the input value as defined by the input predicate function.
	///
	/// Effects: Returns the number of iterators i in the range [first, last) for which the 
	/// following corresponding conditions hold: predicate(*i) != false.
	///
	/// Complexity: At most 'last - first' applications of the corresponding predicate.
	///
	/// Note: The non-predicate version of countIf is count and not another variation of countIf.
	/// This is because both versions would have three parameters and there could be ambiguity.
	///
	template <typename InputIterator, typename Predicate>
	inline typename eastl::iterator_traits<InputIterator>::difference_type
	countIf(InputIterator first, InputIterator last, Predicate predicate)
	{
		typename eastl::iterator_traits<InputIterator>::difference_type result = 0;

		for(; first != last; ++first)
		{
			if(predicate(*first))
				++result;
		}
		return result;
	}


	/// find
	///
	/// finds the value within the unsorted range of [first, last). 
	///
	/// Returns: The first iterator i in the range [first, last) for which 
	/// the following corresponding conditions hold: *i == value. 
	/// Returns last if no such iterator is found.
	///
	/// Complexity: At most 'last - first' applications of the corresponding predicate.
	/// This is a linear search and not a binary one. 
	///
	/// Note: The predicate version of find is findIf and not another variation of find.
	/// This is because both versions would have three parameters and there could be ambiguity.
	///
	template <typename InputIterator, typename T>
	inline InputIterator
	find(InputIterator first, InputIterator last, const T& value)
	{
		while((first != last) && !(*first == value)) // Note that we always express value comparisons in terms of < or ==.
			++first;
		return first;
	}


	// C++ doesn't define a find with predicate, as it can effectively be synthesized via findIf
	// with an appropriate predicate. However, it's often simpler to just have find with a predicate.
	template <typename InputIterator, typename T, typename Predicate>
	inline InputIterator
	find(InputIterator first, InputIterator last, const T& value, Predicate predicate)
	{
		while((first != last) && !predicate(*first, value))
			++first;
		return first;
	}



	/// findIf
	///
	/// finds the value within the unsorted range of [first, last). 
	///
	/// Returns: The first iterator i in the range [first, last) for which 
	/// the following corresponding conditions hold: pred(*i) != false. 
	/// Returns last if no such iterator is found.
	/// If the sequence of elements to search for (i.e. first2 - last2) is empty,
	/// the find always fails and last1 will be returned.
	///
	/// Complexity: At most 'last - first' applications of the corresponding predicate.
	///
	/// Note: The non-predicate version of findIf is find and not another variation of findIf.
	/// This is because both versions would have three parameters and there could be ambiguity.
	///
	template <typename InputIterator, typename Predicate>
	inline InputIterator
	findIf(InputIterator first, InputIterator last, Predicate predicate)
	{
		while((first != last) && !predicate(*first))
			++first;
		return first;
	}



	/// findIf_not
	///
	/// findIf_not works the same as findIf except it tests for if the predicate
	/// returns false for the elements instead of true.
	///
	template <typename InputIterator, typename Predicate>
	inline InputIterator 
	findIf_not(InputIterator first, InputIterator last, Predicate predicate)
	{
		for(; first != last; ++first)
		{
			if(!predicate(*first))
				return first;
		}
		return last;
	}




	/// findFirstOf
	///
	/// findFirstOf is similar to find in that it performs linear search through 
	/// a range of ForwardIterators. The difference is that while find searches 
	/// for one particular value, findFirstOf searches for any of several values. 
	/// Specifically, findFirstOf searches for the first occurrance in the 
	/// range [first1, last1) of any of the elements in [first2, last2). 
	/// This function is thus similar to the strpbrk standard C string function.
	/// If the sequence of elements to search for (i.e. first2-last2) is empty,
	/// the find always fails and last1 will be returned.
	///
	/// Effects: Finds an element that matches one of a set of values.
	///
	/// Returns: The first iterator i in the range [first1, last1) such that for some 
	/// integer j in the range [first2, last2) the following conditions hold: *i == *j.
	/// Returns last1 if no such iterator is found.
	///
	/// Complexity: At most '(last1 - first1) * (last2 - first2)' applications of the 
	/// corresponding predicate.
	///
	template <typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1
	findFirstOf(ForwardIterator1 first1, ForwardIterator1 last1, 
				  ForwardIterator2 first2, ForwardIterator2 last2)
	{
		for(; first1 != last1; ++first1)
		{
			for(ForwardIterator2 i = first2; i != last2; ++i)
			{
				if(*first1 == *i)
					return first1;
			}
		}
		return last1;
	}


	/// findFirstOf
	///
	/// findFirstOf is similar to find in that it performs linear search through 
	/// a range of ForwardIterators. The difference is that while find searches 
	/// for one particular value, findFirstOf searches for any of several values. 
	/// Specifically, findFirstOf searches for the first occurrance in the 
	/// range [first1, last1) of any of the elements in [first2, last2). 
	/// This function is thus similar to the strpbrk standard C string function.
	///
	/// Effects: Finds an element that matches one of a set of values.
	///
	/// Returns: The first iterator i in the range [first1, last1) such that for some 
	/// integer j in the range [first2, last2) the following conditions hold: pred(*i, *j) != false.
	/// Returns last1 if no such iterator is found.
	///
	/// Complexity: At most '(last1 - first1) * (last2 - first2)' applications of the 
	/// corresponding predicate.
	///
	template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1
	findFirstOf(ForwardIterator1 first1, ForwardIterator1 last1, 
				  ForwardIterator2 first2, ForwardIterator2 last2,
				  BinaryPredicate predicate)
	{
		for(; first1 != last1; ++first1)
		{
			for(ForwardIterator2 i = first2; i != last2; ++i)
			{
				if(predicate(*first1, *i))
					return first1;
			}
		}
		return last1;
	}


	/// findFirstNotOf
	///
	/// Searches through first range for the first element that does not belong the second input range.
	/// This is very much like the C++ string findFirstNotOf function.
	///
	/// Returns: The first iterator i in the range [first1, last1) such that for some 
	/// integer j in the range [first2, last2) the following conditions hold: !(*i == *j).
	/// Returns last1 if no such iterator is found.
	///
	/// Complexity: At most '(last1 - first1) * (last2 - first2)' applications of the 
	/// corresponding predicate.
	///
	template <class ForwardIterator1, class ForwardIterator2>
	ForwardIterator1
	findFirstNotOf(ForwardIterator1 first1, ForwardIterator1 last1, 
					  ForwardIterator2 first2, ForwardIterator2 last2)
	{
		for(; first1 != last1; ++first1)
		{
			if(eastl::find(first2, last2, *first1) == last2)
				break;
		}

		return first1;
	}



	/// findFirstNotOf
	///
	/// Searches through first range for the first element that does not belong the second input range.
	/// This is very much like the C++ string findFirstNotOf function.
	///
	/// Returns: The first iterator i in the range [first1, last1) such that for some 
	/// integer j in the range [first2, last2) the following conditions hold: pred(*i, *j) == false.
	/// Returns last1 if no such iterator is found.
	///
	/// Complexity: At most '(last1 - first1) * (last2 - first2)' applications of the 
	/// corresponding predicate.
	///
	template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
	inline ForwardIterator1
	findFirstNotOf(ForwardIterator1 first1, ForwardIterator1 last1, 
					  ForwardIterator2 first2, ForwardIterator2 last2, 
					  BinaryPredicate predicate)
	{
		typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type;

		for(; first1 != last1; ++first1)
		{
			if(eastl::findIf(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *first1)) == last2)
				break;
		}

		return first1;
	}


	template <class BidirectionalIterator1, class ForwardIterator2>
	inline BidirectionalIterator1
	findLastOf(BidirectionalIterator1 first1, BidirectionalIterator1 last1, 
				 ForwardIterator2 first2, ForwardIterator2 last2)
	{
		if((first1 != last1) && (first2 != last2))
		{
			BidirectionalIterator1 it1(last1);

			while((--it1 != first1) && (eastl::find(first2, last2, *it1) == last2))
				; // Do nothing

			if((it1 != first1) || (eastl::find(first2, last2, *it1) != last2))
				return it1;
		}

		return last1;
	}


	template <class BidirectionalIterator1, class ForwardIterator2, class BinaryPredicate>
	BidirectionalIterator1
	findLastOf(BidirectionalIterator1 first1, BidirectionalIterator1 last1, 
				 ForwardIterator2 first2, ForwardIterator2 last2, 
				 BinaryPredicate predicate)
	{
		typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type value_type;

		if((first1 != last1) && (first2 != last2))
		{
			BidirectionalIterator1 it1(last1);

			while((--it1 != first1) && (eastl::findIf(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) == last2))
				; // Do nothing

			if((it1 != first1) || (eastl::findIf(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) != last2))
				return it1;
		}

		return last1;
	}


	template <class BidirectionalIterator1, class ForwardIterator2>
	inline BidirectionalIterator1
	findLastNotOf(BidirectionalIterator1 first1, BidirectionalIterator1 last1, 
					 ForwardIterator2 first2, ForwardIterator2 last2)
	{
		if((first1 != last1) && (first2 != last2))
		{
			BidirectionalIterator1 it1(last1);

			while((--it1 != first1) && (eastl::find(first2, last2, *it1) != last2))
				; // Do nothing

			if((it1 != first1) || (eastl::find( first2, last2, *it1) == last2))
				return it1;
		}

		return last1;
	}


	template <class BidirectionalIterator1, class ForwardIterator2, class BinaryPredicate>
	inline BidirectionalIterator1
	findLastNotOf(BidirectionalIterator1 first1, BidirectionalIterator1 last1, 
					 ForwardIterator2 first2, ForwardIterator2 last2, 
					 BinaryPredicate predicate)
	{
		typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type value_type;

		if((first1 != last1) && (first2 != last2))
		{
			BidirectionalIterator1 it1(last1);

			while((--it1 != first1) && (eastl::findIf(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) != last2))
				; // Do nothing

			if((it1 != first1) || (eastl::findIf(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1))) != last2)
				return it1;
		}

		return last1;
	}




	/// forEach
	///
	/// Calls the Function function for each value in the range [first, last).
	/// Function takes a single parameter: the current value.
	/// 
	/// Effects: Applies function to the result of dereferencing every iterator in 
	/// the range [first, last), starting from first and proceeding to last 1.
	///
	/// Returns: function.
	///
	/// Complexity: Applies function exactly 'last - first' times.
	///
	/// Note: If function returns a result, the result is ignored.
	/// 
	template <typename InputIterator, typename Function>
	inline Function
	forEach(InputIterator first, InputIterator last, Function function)
	{
		for(; first != last; ++first)
			function(*first);
		return function;
	}


	/// generate
	///
	/// Iterates the range of [first, last) and assigns to each element the
	/// result of the function generator. Generator is a function which takes
	/// no arguments.
	/// 
	/// Complexity: Exactly 'last - first' invocations of generator and assignments.
	///
	template <typename ForwardIterator, typename Generator>
	inline void
	generate(ForwardIterator first, ForwardIterator last, Generator generator)
	{
		for(; first != last; ++first) // We cannot call generateN(first, last-first, generator) 
			*first = generator();     // because the 'last-first' might not be supported by the 
	}                                 // given iterator.


	/// generateN
	///
	/// Iterates an interator n times and assigns the result of generator
	/// to each succeeding element. Generator is a function which takes
	/// no arguments.
	/// 
	/// Complexity: Exactly n invocations of generator and assignments.
	///
	template <typename OutputIterator, typename Size, typename Generator>
	inline OutputIterator
	generateN(OutputIterator first, Size n, Generator generator)
	{
		for(; n > 0; --n, ++first)
			*first = generator();
		return first;
	}


	/// transform
	///
	/// Iterates the input range of [first, last) and the output iterator result
	/// and assigns the result of unaryOperation(input) to result.
	/// 
	/// Effects: Assigns through every iterator i in the range [result, result + (last1 - first1))
	/// a new corresponding value equal to unaryOperation(*(first1 + (i - result)).
	///
	/// Requires: op shall not have any side effects.
	///
	/// Returns: result + (last1 - first1). That is, returns the end of the output range.
	///
	/// Complexity: Exactly 'last1 - first1' applications of unaryOperation.
	///
	/// Note: result may be equal to first.
	///
	template <typename InputIterator, typename OutputIterator, typename UnaryOperation>
	inline OutputIterator
	transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unaryOperation)
	{
		for(; first != last; ++first, ++result)
			*result = unaryOperation(*first);
		return result;
	}


	/// transform
	///
	/// Iterates the input range of [first, last) and the output iterator result
	/// and assigns the result of binaryOperation(input1, input2) to result.
	/// 
	/// Effects: Assigns through every iterator i in the range [result, result + (last1 - first1))
	/// a new corresponding value equal to binaryOperation(*(first1 + (i - result), *(first2 + (i - result))).
	///
	/// Requires: binaryOperation shall not have any side effects.
	///
	/// Returns: result + (last1 - first1). That is, returns the end of the output range.
	///
	/// Complexity: Exactly 'last1 - first1' applications of binaryOperation.
	///
	/// Note: result may be equal to first1 or first2.
	///
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
	inline OutputIterator
	transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binaryOperation)
	{
		for(; first1 != last1; ++first1, ++first2, ++result)
			*result = binaryOperation(*first1, *first2);
		return result;
	}


	/// equal
	///
	/// Returns: true if for every iterator i in the range [first1, last1) the 
	/// following corresponding conditions hold: predicate(*i, *(first2 + (i - first1))) != false. 
	/// Otherwise, returns false.
	///
	/// Complexity: At most last1 first1 applications of the corresponding predicate.
	///
	/// To consider: Make specializations of this for scalar types and random access
	/// iterators that uses memcmp or some trick memory comparison function. 
	/// We should verify that such a thing results in an improvement.
	///
	template <typename InputIterator1, typename InputIterator2>
	inline bool
	equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
	{
		for(; first1 != last1; ++first1, ++first2)
		{
			if(!(*first1 == *first2)) // Note that we always express value comparisons in terms of < or ==.
				return false;
		}
		return true;
	}

	/* Enable the following if there was shown to be some benefit. A glance and Microsoft VC++ memcmp
		shows that it is not optimized in any way, much less one that would benefit us here.

	inline bool equal(const bool* first1, const bool* last1, const bool* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const char* first1, const char* last1, const char* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const unsigned char* first1, const unsigned char* last1, const unsigned char* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const signed char* first1, const signed char* last1, const signed char* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	#ifndef EASTL_WCHAR_T_NON_NATIVE // EABase defines this. If you are getting a compiler error here, then somebody has taken away EABase or broken it.
		inline bool equal(const wchar_t* first1, const wchar_t* last1, const wchar_t* first2)
			{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }
	#endif

	inline bool equal(const int16_t* first1, const int16_t* last1, const int16_t* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const uint16_t* first1, const uint16_t* last1, const uint16_t* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const int32_t* first1, const int32_t* last1, const int32_t* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const uint32_t* first1, const uint32_t* last1, const uint32_t* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const int64_t* first1, const int64_t* last1, const int64_t* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const uint64_t* first1, const uint64_t* last1, const uint64_t* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const float* first1, const float* last1, const float* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const double* first1, const double* last1, const double* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }

	inline bool equal(const long double* first1, const long double* last1, const long double* first2)
		{ return (memcmp(first1, first2, (size_t)((uintptr_t)last1 - (uintptr_t)first1)) == 0); }
	*/



	/// equal
	///
	/// Returns: true if for every iterator i in the range [first1, last1) the 
	/// following corresponding conditions hold: pred(*i, *(first2 + (i first1))) != false. 
	/// Otherwise, returns false.
	///
	/// Complexity: At most last1 first1 applications of the corresponding predicate.
	///
	template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
	inline bool
	equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate predicate)
	{
		for(; first1 != last1; ++first1, ++first2)
		{
			if(!predicate(*first1, *first2))
				return false;
		}
		return true;
	}



	/// identical
	///
	/// Returns true if the two input ranges are equivalent.
	/// There is a subtle difference between this algorithm and 
	/// the 'equal' algorithm. The equal algorithm assumes the 
	/// two ranges are of equal length. This algorithm efficiently
	/// compares two ranges for both length equality and for 
	/// element equality. There is no other standard algorithm
	/// that can do this.
	///
	/// Returns: true if the sequence of elements defined by the range 
	/// [first1, last1) is of the same length as the sequence of
	/// elements defined by the range of [first2, last2) and if
	/// the elements in these ranges are equal as per the 
	/// equal algorithm.
	///
	/// Complexity: At most 'min((last1 - first1), (last2 - first2))' applications 
	/// of the corresponding comparison.
	///
	template <typename InputIterator1, typename InputIterator2>
	bool identical(InputIterator1 first1, InputIterator1 last1,
				   InputIterator2 first2, InputIterator2 last2)
	{
		while((first1 != last1) && (first2 != last2) && (*first1 == *first2))
		{
			++first1;
			++first2;
		}
		return (first1 == last1) && (first2 == last2);
	}


	/// identical
	///
	template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
	bool identical(InputIterator1 first1, InputIterator1 last1,
				   InputIterator2 first2, InputIterator2 last2, BinaryPredicate predicate)
	{
		while((first1 != last1) && (first2 != last2) && predicate(*first1, *first2))
		{
			++first1;
			++first2;
		}
		return (first1 == last1) && (first2 == last2);
	}



	/// lexicographicalCompare
	///
	/// Returns: true if the sequence of elements defined by the range 
	/// [first1, last1) is lexicographically less than the sequence of 
	/// elements defined by the range [first2, last2). Returns false otherwise.
	///
	/// Complexity: At most 'min((last1 - first1), (last2 - first2))' applications 
	/// of the corresponding comparison.
	///
	/// Note: If two sequences have the same number of elements and their 
	/// corresponding elements are equivalent, then neither sequence is 
	/// lexicographically less than the other. If one sequence is a prefix 
	/// of the other, then the shorter sequence is lexicographically less 
	/// than the longer sequence. Otherwise, the lexicographical comparison 
	/// of the sequences yields the same result as the comparison of the first 
	/// corresponding pair of elements that are not equivalent.
	///
	template <typename InputIterator1, typename InputIterator2>
	inline bool
	lexicographicalCompare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
	{
		for(; (first1 != last1) && (first2 != last2); ++first1, ++first2)
		{
			if(*first1 < *first2)
				return true;
			if(*first2 < *first1)
				return false;
		}
		return (first1 == last1) && (first2 != last2);
	}

	inline bool     // Specialization for const char*.
	lexicographicalCompare(const char* first1, const char* last1, const char* first2, const char* last2)
	{
		const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
		const int result = memcmp(first1, first2, (size_t)eastl::minAlt(n1, n2));
		return result ? (result < 0) : (n1 < n2);
	}

	inline bool     // Specialization for char*.
	lexicographicalCompare(char* first1, char* last1, char* first2, char* last2)
	{
		const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
		const int result = memcmp(first1, first2, (size_t)eastl::minAlt(n1, n2));
		return result ? (result < 0) : (n1 < n2);
	}

	inline bool     // Specialization for const unsigned char*.
	lexicographicalCompare(const unsigned char* first1, const unsigned char* last1, const unsigned char* first2, const unsigned char* last2)
	{
		const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
		const int result = memcmp(first1, first2, (size_t)eastl::minAlt(n1, n2));
		return result ? (result < 0) : (n1 < n2);
	}

	inline bool     // Specialization for unsigned char*.
	lexicographicalCompare(unsigned char* first1, unsigned char* last1, unsigned char* first2, unsigned char* last2)
	{
		const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
		const int result = memcmp(first1, first2, (size_t)eastl::minAlt(n1, n2));
		return result ? (result < 0) : (n1 < n2);
	}

	inline bool     // Specialization for const signed char*.
	lexicographicalCompare(const signed char* first1, const signed char* last1, const signed char* first2, const signed char* last2)
	{
		const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
		const int result = memcmp(first1, first2, (size_t)eastl::minAlt(n1, n2));
		return result ? (result < 0) : (n1 < n2);
	}

	inline bool     // Specialization for signed char*.
	lexicographicalCompare(signed char* first1, signed char* last1, signed char* first2, signed char* last2)
	{
		const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
		const int result = memcmp(first1, first2, (size_t)eastl::minAlt(n1, n2));
		return result ? (result < 0) : (n1 < n2);
	}

	#if defined(_MSC_VER) // If using the VC++ compiler (and thus bool is known to be a single byte)...
		//Not sure if this is a good idea.
		//inline bool     // Specialization for const bool*.
		//lexicographicalCompare(const bool* first1, const bool* last1, const bool* first2, const bool* last2)
		//{
		//    const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
		//    const int result = memcmp(first1, first2, (size_t)eastl::minAlt(n1, n2));
		//    return result ? (result < 0) : (n1 < n2);
		//}
		//
		//inline bool     // Specialization for bool*.
		//lexicographicalCompare(bool* first1, bool* last1, bool* first2, bool* last2)
		//{
		//    const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
		//    const int result = memcmp(first1, first2, (size_t)eastl::minAlt(n1, n2));
		//    return result ? (result < 0) : (n1 < n2);
		//}
	#endif



	/// lexicographicalCompare
	///
	/// Returns: true if the sequence of elements defined by the range 
	/// [first1, last1) is lexicographically less than the sequence of 
	/// elements defined by the range [first2, last2). Returns false otherwise.
	///
	/// Complexity: At most 'min((last1 -first1), (last2 - first2))' applications 
	/// of the corresponding comparison.
	///
	/// Note: If two sequences have the same number of elements and their 
	/// corresponding elements are equivalent, then neither sequence is 
	/// lexicographically less than the other. If one sequence is a prefix 
	/// of the other, then the shorter sequence is lexicographically less 
	/// than the longer sequence. Otherwise, the lexicographical comparison 
	/// of the sequences yields the same result as the comparison of the first 
	/// corresponding pair of elements that are not equivalent.
	///
	/// Note: False is always returned if range 1 is exhausted before range 2.
	/// The result of this is that you can't do a successful reverse compare
	/// (e.g. use greater<> as the comparison instead of less<>) unless the 
	/// two sequences are of identical length. What you want to do is reverse
	/// the order of the arguments in order to get the desired effect.
	///
	template <typename InputIterator1, typename InputIterator2, typename Compare>
	inline bool
	lexicographicalCompare(InputIterator1 first1, InputIterator1 last1, 
							InputIterator2 first2, InputIterator2 last2, Compare compare)
	{
		for(; (first1 != last1) && (first2 != last2); ++first1, ++first2)
		{
			if(compare(*first1, *first2))
				return true;
			if(compare(*first2, *first1))
				return false;
		}
		return (first1 == last1) && (first2 != last2);
	}


	/// mismatch
	///
	/// Finds the first position where the two ranges [first1, last1) and 
	/// [first2, first2 + (last1 - first1)) differ. The two versions of  
	/// mismatch use different tests for whether elements differ.
	///
	/// Returns: A pair of iterators i and j such that j == first2 + (i - first1)
	/// and i is the first iterator in the range [first1, last1) for which the 
	/// following corresponding condition holds: !(*i == *(first2 + (i - first1))).
	/// Returns the pair last1 and first2 + (last1 - first1) if such an iterator 
	/// i is not found.
	///
	/// Complexity: At most last1 first1 applications of the corresponding predicate.
	///
	template <class InputIterator1, class InputIterator2>
	inline eastl::pair<InputIterator1, InputIterator2>
	mismatch(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2) // , InputIterator2 last2)
	{
		while((first1 != last1) && (*first1 == *first2)) // && (first2 != last2) <- C++ standard mismatch function doesn't check first2/last2.
		{
			++first1;
			++first2;
		}

		return eastl::pair<InputIterator1, InputIterator2>(first1, first2);
	}


	/// mismatch
	///
	/// Finds the first position where the two ranges [first1, last1) and 
	/// [first2, first2 + (last1 - first1)) differ. The two versions of  
	/// mismatch use different tests for whether elements differ.
	///
	/// Returns: A pair of iterators i and j such that j == first2 + (i - first1)
	/// and i is the first iterator in the range [first1, last1) for which the 
	/// following corresponding condition holds: pred(*i, *(first2 + (i - first1))) == false.
	/// Returns the pair last1 and first2 + (last1 - first1) if such an iterator 
	/// i is not found.
	///
	/// Complexity: At most last1 first1 applications of the corresponding predicate.
	///
	template <class InputIterator1, class InputIterator2, class BinaryPredicate>
	inline eastl::pair<InputIterator1, InputIterator2>
	mismatch(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, // InputIterator2 last2,
			 BinaryPredicate predicate)
	{
		while((first1 != last1) && predicate(*first1, *first2)) // && (first2 != last2) <- C++ standard mismatch function doesn't check first2/last2.
		{
			++first1;
			++first2;
		}

		return eastl::pair<InputIterator1, InputIterator2>(first1, first2);
	}


	/// lowerBound
	///
	/// Finds the position of the first element in a sorted range that has a value 
	/// greater than or equivalent to a specified value.
	///
	/// Effects: Finds the first position into which value can be inserted without 
	/// violating the ordering.
	/// 
	/// Returns: The furthermost iterator i in the range [first, last) such that 
	/// for any iterator j in the range [first, i) the following corresponding 
	/// condition holds: *j < value.
	///
	/// Complexity: At most 'log(last - first) + 1' comparisons.
	///
	/// Optimizations: We have no need to specialize this implementation for random 
	/// access iterators (e.g. contiguous array), as the code below will already 
	/// take advantage of them.
	///
	template <typename ForwardIterator, typename T>
	ForwardIterator
	lowerBound(ForwardIterator first, ForwardIterator last, const T& value)
	{
		typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;

		DifferenceType d = eastl::distance(first, last); // This will be efficient for a random access iterator such as an array.

		while(d > 0)
		{
			ForwardIterator i  = first;
			DifferenceType  d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.

			eastl::advance(i, d2); // This will be efficient for a random access iterator such as an array.

			if(*i < value)
			{
				// Disabled because std::lowerBound doesn't specify (23.3.3.3, p3) this can be done: EASTL_VALIDATE_COMPARE(!(value < *i)); // Validate that the compare function is sane.
				first = ++i;
				d    -= d2 + 1;
			}
			else
				d = d2;
		}
		return first;
	}


	/// lowerBound
	///
	/// Finds the position of the first element in a sorted range that has a value 
	/// greater than or equivalent to a specified value. The input Compare function
	/// takes two arguments and returns true if the first argument is less than
	/// the second argument.
	///
	/// Effects: Finds the first position into which value can be inserted without 
	/// violating the ordering.
	/// 
	/// Returns: The furthermost iterator i in the range [first, last) such that 
	/// for any iterator j in the range [first, i) the following corresponding 
	/// condition holds: compare(*j, value) != false.
	///
	/// Complexity: At most 'log(last - first) + 1' comparisons.
	///
	/// Optimizations: We have no need to specialize this implementation for random 
	/// access iterators (e.g. contiguous array), as the code below will already 
	/// take advantage of them.
	///
	template <typename ForwardIterator, typename T, typename Compare>
	ForwardIterator
	lowerBound(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
	{
		typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;

		DifferenceType d = eastl::distance(first, last); // This will be efficient for a random access iterator such as an array.

		while(d > 0)
		{
			ForwardIterator i  = first;
			DifferenceType  d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.

			eastl::advance(i, d2); // This will be efficient for a random access iterator such as an array.

			if(compare(*i, value))
			{
				// Disabled because std::lowerBound doesn't specify (23.3.3.1, p3) this can be done: EASTL_VALIDATE_COMPARE(!compare(value, *i)); // Validate that the compare function is sane.
				first = ++i;
				d    -= d2 + 1;
			}
			else
				d = d2;
		}
		return first;
	}



	/// upperBound
	///
	/// Finds the position of the first element in a sorted range that has a 
	/// value that is greater than a specified value.
	///
	/// Effects: Finds the furthermost position into which value can be inserted 
	/// without violating the ordering.
	///
	/// Returns: The furthermost iterator i in the range [first, last) such that 
	/// for any iterator j in the range [first, i) the following corresponding 
	/// condition holds: !(value < *j).
	///
	/// Complexity: At most 'log(last - first) + 1' comparisons.
	///
	template <typename ForwardIterator, typename T>
	ForwardIterator
	upperBound(ForwardIterator first, ForwardIterator last, const T& value)
	{
		typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;

		DifferenceType len = eastl::distance(first, last);

		while(len > 0)
		{
			ForwardIterator i    = first;
			DifferenceType  len2 = len >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.

			eastl::advance(i, len2);

			if(!(value < *i)) // Note that we always express value comparisons in terms of < or ==.
			{
				first = ++i;
				len -= len2 + 1;
			}
			else
			{
				// Disabled because std::upperBound doesn't specify (23.3.3.2, p3) this can be done: EASTL_VALIDATE_COMPARE(!(*i < value)); // Validate that the compare function is sane.
				len = len2;
			}
		}
		return first;
	}


	/// upperBound
	///
	/// Finds the position of the first element in a sorted range that has a 
	/// value that is greater than a specified value. The input Compare function
	/// takes two arguments and returns true if the first argument is less than
	/// the second argument.
	///
	/// Effects: Finds the furthermost position into which value can be inserted 
	/// without violating the ordering.
	///
	/// Returns: The furthermost iterator i in the range [first, last) such that 
	/// for any iterator j in the range [first, i) the following corresponding 
	/// condition holds: compare(value, *j) == false.
	///
	/// Complexity: At most 'log(last - first) + 1' comparisons.
	///
	template <typename ForwardIterator, typename T, typename Compare>
	ForwardIterator
	upperBound(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
	{
		typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;

		DifferenceType len = eastl::distance(first, last);

		while(len > 0)
		{
			ForwardIterator i    = first;
			DifferenceType  len2 = len >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.

			eastl::advance(i, len2);

			if(!compare(value, *i))
			{
				first = ++i;
				len -= len2 + 1;
			}
			else
			{
				// Disabled because std::upperBound doesn't specify (23.3.3.2, p3) this can be done: EASTL_VALIDATE_COMPARE(!compare(*i, value)); // Validate that the compare function is sane.
				len = len2;
			}
		}
		return first;
	}


	/// equalRange
	///
	/// Effects: Finds the largest subrange [i, j) such that the value can be inserted 
	/// at any iterator k in it without violating the ordering. k satisfies the 
	/// corresponding conditions: !(*k < value) && !(value < *k).
	/// 
	/// Complexity: At most '2 * log(last - first) + 1' comparisons.
	///
	template <typename ForwardIterator, typename T>
	pair<ForwardIterator, ForwardIterator>
	equalRange(ForwardIterator first, ForwardIterator last, const T& value)
	{
		typedef pair<ForwardIterator, ForwardIterator> ResultType;
		typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;

		DifferenceType d = eastl::distance(first, last);

		while(d > 0)
		{
			ForwardIterator i(first);
			DifferenceType  d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.

			eastl::advance(i, d2);

			if(*i < value)
			{
				EASTL_VALIDATE_COMPARE(!(value < *i)); // Validate that the compare function is sane.
				first = ++i;
				d    -= d2 + 1;
			}
			else if(value < *i)
			{
				EASTL_VALIDATE_COMPARE(!(*i < value)); // Validate that the compare function is sane.
				d    = d2;
				last = i;
			}
			else
			{
				ForwardIterator j(i);

				return ResultType(eastl::lowerBound(first, i, value), 
								  eastl::upperBound(++j, last, value));
			}
		}
		return ResultType(first, first);
	}


	/// equalRange
	///
	/// Effects: Finds the largest subrange [i, j) such that the value can be inserted 
	/// at any iterator k in it without violating the ordering. k satisfies the 
	/// corresponding conditions: compare(*k, value) == false && compare(value, *k) == false.
	/// 
	/// Complexity: At most '2 * log(last - first) + 1' comparisons.
	///
	template <typename ForwardIterator, typename T, typename Compare>
	pair<ForwardIterator, ForwardIterator>
	equalRange(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
	{
		typedef pair<ForwardIterator, ForwardIterator> ResultType;
		typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;

		DifferenceType d = eastl::distance(first, last);

		while(d > 0)
		{
			ForwardIterator i(first);
			DifferenceType  d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.

			eastl::advance(i, d2);

			if(compare(*i, value))
			{
				EASTL_VALIDATE_COMPARE(!compare(value, *i)); // Validate that the compare function is sane.
				first = ++i;
				d    -= d2 + 1;
			}
			else if(compare(value, *i))
			{
				EASTL_VALIDATE_COMPARE(!compare(*i, value)); // Validate that the compare function is sane.
				d    = d2;
				last = i;
			}
			else
			{
				ForwardIterator j(i);

				return ResultType(eastl::lowerBound(first, i, value, compare), 
								  eastl::upperBound(++j, last, value, compare));
			}
		}
		return ResultType(first, first);
	}


	/// replace
	///
	/// Effects: Substitutes elements referred by the iterator i in the range [first, last) 
	/// with new_value, when the following corresponding conditions hold: *i == old_value.
	/// 
	/// Complexity: Exactly 'last - first' applications of the corresponding predicate.
	///
	/// Note: The predicate version of replace is replaceIf and not another variation of replace.
	/// This is because both versions would have the same parameter count and there could be ambiguity.
	///
	template <typename ForwardIterator, typename T>
	inline void
	replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
	{
		for(; first != last; ++first)
		{
			if(*first == old_value)
				*first = new_value;
		}
	}


	/// replaceIf
	///
	/// Effects: Substitutes elements referred by the iterator i in the range [first, last) 
	/// with new_value, when the following corresponding conditions hold: predicate(*i) != false.
	/// 
	/// Complexity: Exactly 'last - first' applications of the corresponding predicate.
	///
	/// Note: The predicate version of replaceIf is replace and not another variation of replaceIf.
	/// This is because both versions would have the same parameter count and there could be ambiguity.
	///
	template <typename ForwardIterator, typename Predicate, typename T>
	inline void
	replaceIf(ForwardIterator first, ForwardIterator last, Predicate predicate, const T& new_value)
	{
		for(; first != last; ++first)
		{
			if(predicate(*first))
				*first = new_value;
		}
	}


	/// removeCopy
	///
	/// Effects: Copies all the elements referred to by the iterator i in the range 
	/// [first, last) for which the following corresponding condition does not hold: 
	/// *i == value.
	///
	/// Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
	///
	/// Returns: The end of the resulting range.
	///
	/// Complexity: Exactly 'last - first' applications of the corresponding predicate.
	///
	template <typename InputIterator, typename OutputIterator, typename T>
	inline OutputIterator
	removeCopy(InputIterator first, InputIterator last, OutputIterator result, const T& value)
	{
		for(; first != last; ++first)
		{
			if(!(*first == value)) // Note that we always express value comparisons in terms of < or ==.
			{
				*result = *first;
				++result;
			}
		}
		return result;
	}


	/// removeCopyIf
	///
	/// Effects: Copies all the elements referred to by the iterator i in the range 
	/// [first, last) for which the following corresponding condition does not hold: 
	/// predicate(*i) != false.
	///
	/// Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
	///
	/// Returns: The end of the resulting range.
	///
	/// Complexity: Exactly 'last - first' applications of the corresponding predicate.
	///
	template <typename InputIterator, typename OutputIterator, typename Predicate>
	inline OutputIterator
	removeCopyIf(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate)
	{
		for(; first != last; ++first)
		{
			if(!predicate(*first))
			{
				*result = *first;
				++result;
			}
		}
		return result;
	}


	/// remove
	///
	/// Effects: Eliminates all the elements referred to by iterator i in the 
	/// range [first, last) for which the following corresponding condition
	/// holds: *i == value.
	///
	/// Returns: The end of the resulting range.
	///
	/// Complexity: Exactly 'last - first' applications of the corresponding predicate.
	///
	/// Note: The predicate version of remove is removeIf and not another variation of remove.
	/// This is because both versions would have the same parameter count and there could be ambiguity.
	///
	/// Note: Since this function moves the element to the back of the heap and 
	/// doesn't actually remove it from the given container, the user must call
	/// the container erase function if the user wants to erase the element 
	/// from the container.
	///
	/// Example usage:
	///    vector<int> intArray;
	///    ...
	///    intArray.erase(remove(intArray.begin(), intArray.end(), 4), intArray.end()); // Erase all elements of value 4.
	///
	template <typename ForwardIterator, typename T>
	inline ForwardIterator
	remove(ForwardIterator first, ForwardIterator last, const T& value)
	{
		first = eastl::find(first, last, value);
		if(first != last)
		{
			ForwardIterator i(first);
			return eastl::removeCopy(++i, last, first, value);
		}
		return first;
	}


	/// removeIf
	///
	/// Effects: Eliminates all the elements referred to by iterator i in the 
	/// range [first, last) for which the following corresponding condition 
	/// holds: predicate(*i) != false.
	///
	/// Returns: The end of the resulting range.
	///
	/// Complexity: Exactly 'last - first' applications of the corresponding predicate.
	///
	/// Note: The predicate version of removeIf is remove and not another variation of removeIf.
	/// This is because both versions would have the same parameter count and there could be ambiguity.
	///
	/// Note: Since this function moves the element to the back of the heap and 
	/// doesn't actually remove it from the given container, the user must call
	/// the container erase function if the user wants to erase the element 
	/// from the container.
	///
	/// Example usage:
	///    vector<int> intArray;
	///    ...
	///    intArray.erase(remove(intArray.begin(), intArray.end(), bind2nd(less<int>(), (int)3)), intArray.end()); // Erase all elements less than 3.
	///
	template <typename ForwardIterator, typename Predicate>
	inline ForwardIterator
	removeIf(ForwardIterator first, ForwardIterator last, Predicate predicate)
	{
		first = eastl::findIf(first, last, predicate);
		if(first != last)
		{
			ForwardIterator i(first);
			return eastl::removeCopyIf<ForwardIterator, ForwardIterator, Predicate>(++i, last, first, predicate);
		}
		return first;
	}


	/// replaceCopy
	///
	/// Effects: Assigns to every iterator i in the range [result, result + (last - first))
	/// either new_value or *(first + (i - result)) depending on whether the following 
	/// corresponding conditions hold: *(first + (i - result)) == old_value.
	///
	/// Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
	///
	/// Returns: result + (last - first).
	///
	/// Complexity: Exactly 'last - first' applications of the corresponding predicate.
	///
	/// Note: The predicate version of replaceCopy is replaceCopyIf and not another variation of replaceCopy.
	/// This is because both versions would have the same parameter count and there could be ambiguity.
	///
	template <typename InputIterator, typename OutputIterator, typename T>
	inline OutputIterator
	replaceCopy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value)
	{
		for(; first != last; ++first, ++result)
			*result = (*first == old_value) ? new_value : *first;
		return result;
	}


	/// replaceCopyIf
	///
	/// Effects: Assigns to every iterator i in the range [result, result + (last - first))
	/// either new_value or *(first + (i - result)) depending on whether the following 
	/// corresponding conditions hold: predicate(*(first + (i - result))) != false.
	///
	/// Requires: The ranges [first, last) and [result, result+(lastfirst)) shall not overlap.
	///
	/// Returns: result + (last - first).
	///
	/// Complexity: Exactly 'last - first' applications of the corresponding predicate.
	///
	/// Note: The predicate version of replaceCopyIf is replaceCopy and not another variation of replaceCopyIf.
	/// This is because both versions would have the same parameter count and there could be ambiguity.
	///
	template <typename InputIterator, typename OutputIterator, typename Predicate, typename T>
	inline OutputIterator
	replaceCopyIf(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate, const T& new_value)
	{
		for(; first != last; ++first, ++result)
			*result = predicate(*first) ? new_value : *first;
		return result;
	}




	// reverse
	//
	// We provide helper functions which allow reverse to be implemented more  
	// efficiently for some types of iterators and types.
	//
	template <typename BidirectionalIterator>
	inline void reverse_impl(BidirectionalIterator first, BidirectionalIterator last, EASTL_ITC_NS::bidirectional_iterator_tag)
	{
		for(; (first != last) && (first != --last); ++first) // We are not allowed to use operator <, <=, >, >= with a
			eastl::iterSwap(first, last);                   // generic (bidirectional or otherwise) iterator.
	}

	template <typename RandomAccessIterator>
	inline void reverse_impl(RandomAccessIterator first, RandomAccessIterator last, EASTL_ITC_NS::random_access_iterator_tag)
	{
		if(first != last)
		{
			for(; first < --last; ++first)      // With a random access iterator, we can use operator < to more efficiently implement
				eastl::iterSwap(first, last);  // this algorithm. A generic iterator doesn't necessarily have an operator < defined.
		}
	}

	/// reverse
	///
	/// Reverses the values within the range [first, last).
	///
	/// Effects: For each nonnegative integer i <= (last - first) / 2, 
	/// applies swap to all pairs of iterators first + i, (last i) - 1.
	///
	/// Complexity: Exactly '(last - first) / 2' swaps.
	///
	template <typename BidirectionalIterator>
	inline void reverse(BidirectionalIterator first, BidirectionalIterator last)
	{
		typedef typename eastl::iterator_traits<BidirectionalIterator>::iterator_category IC;
		eastl::reverse_impl(first, last, IC());
	}



	/// reverseCopy
	///
	/// Copies the range [first, last) in reverse order to the result.
	///
	/// Effects: Copies the range [first, last) to the range 
	/// [result, result + (last - first)) such that for any nonnegative
	/// integer i < (last - first) the following assignment takes place:
	/// *(result + (last - first) - i) = *(first + i)
	///
	/// Requires: The ranges [first, last) and [result, result + (last - first))
	/// shall not overlap.
	///
	/// Returns: result + (last - first). That is, returns the end of the output range.
	///
	/// Complexity: Exactly 'last - first' assignments.
	///
	template <typename BidirectionalIterator, typename OutputIterator>
	inline OutputIterator
	reverseCopy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
	{
		for(; first != last; ++result)
			*result = *--last;
		return result;
	}



	/// search
	///
	/// Search finds a subsequence within the range [first1, last1) that is identical to [first2, last2) 
	/// when compared element-by-element. It returns an iterator pointing to the beginning of that 
	/// subsequence, or else last1 if no such subsequence exists. As such, it is very much like 
	/// the C strstr function, with the primary difference being that strstr uses 0-terminated strings
	/// whereas search uses an end iterator to specify the end of a string.
	///
	/// Returns: The first iterator i in the range [first1, last1 - (last2 - first2)) such that for
	/// any nonnegative integer n less than 'last2 - first2' the following corresponding condition holds:
	/// *(i + n) == *(first2 + n). Returns last1 if no such iterator is found.
	///
	/// Complexity: At most (last1 first1) * (last2 first2) applications of the corresponding predicate.
	///
	template <typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1
	search(ForwardIterator1 first1, ForwardIterator1 last1, 
		   ForwardIterator2 first2, ForwardIterator2 last2)
	{
		if(first2 != last2) // If there is anything to search for...
		{
			// We need to make a special case for a pattern of one element,
			// as the logic below prevents one element patterns from working.
			ForwardIterator2 temp2(first2);
			++temp2;

			if(temp2 != last2) // If what we are searching for has a length > 1...
			{
				ForwardIterator1 cur1(first1);
				ForwardIterator2 p2;

				while(first1 != last1)
				{
					// The following loop is the equivalent of eastl::find(first1, last1, *first2)
					while((first1 != last1) && !(*first1 == *first2))
						++first1;

					if(first1 != last1)
					{
						p2   = temp2;
						cur1 = first1;

						if(++cur1 != last1)
						{
							while(*cur1 == *p2)
							{
								if(++p2 == last2)
									return first1;

								if(++cur1 == last1)
									return last1;
							}

							++first1;
							continue;
						}
					}
					return last1;
				}

				// Fall through to the end.
			}
			else
				return eastl::find(first1, last1, *first2);
		}

		return first1;


		#if 0
		/*  Another implementation which is a little more simpler but executes a little slower on average.
			typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type_1;
			typedef typename eastl::iterator_traits<ForwardIterator2>::difference_type difference_type_2;

			const difference_type_2 d2 = eastl::distance(first2, last2);

			for(difference_type_1 d1 = eastl::distance(first1, last1); d1 >= d2; ++first1, --d1)
			{
				ForwardIterator1 temp1 = first1;

				for(ForwardIterator2 temp2 = first2; ; ++temp1, ++temp2)
				{
					if(temp2 == last2)
						return first1;
					if(!(*temp1 == *temp2))
						break;
				}
			}

			return last1;
		*/
		#endif
	}


	/// search
	///
	/// Search finds a subsequence within the range [first1, last1) that is identical to [first2, last2) 
	/// when compared element-by-element. It returns an iterator pointing to the beginning of that 
	/// subsequence, or else last1 if no such subsequence exists. As such, it is very much like 
	/// the C strstr function, with the only difference being that strstr uses 0-terminated strings
	/// whereas search uses an end iterator to specify the end of a string.
	///
	/// Returns: The first iterator i in the range [first1, last1 - (last2 - first2)) such that for
	/// any nonnegative integer n less than 'last2 - first2' the following corresponding condition holds:
	/// predicate(*(i + n), *(first2 + n)) != false. Returns last1 if no such iterator is found.
	///
	/// Complexity: At most (last1 first1) * (last2 first2) applications of the corresponding predicate.
	///
	template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1
	search(ForwardIterator1 first1, ForwardIterator1 last1, 
		   ForwardIterator2 first2, ForwardIterator2 last2,
		   BinaryPredicate predicate)
	{
		typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type_1;
		typedef typename eastl::iterator_traits<ForwardIterator2>::difference_type difference_type_2;

		difference_type_2 d2 = eastl::distance(first2, last2);

		if(d2 != 0)
		{
			ForwardIterator1 i(first1);
			eastl::advance(i, d2);

			for(difference_type_1 d1 = eastl::distance(first1, last1); d1 >= d2; --d1)
			{
				if(eastl::equal<ForwardIterator1, ForwardIterator2, BinaryPredicate>(first1, i, first2, predicate))
					return first1;
				if(d1 > d2) // To do: Find a way to make the algorithm more elegant.
				{
					++first1;
					++i;
				}
			}
			return last1;
		}
		return first1; // Just like with strstr, we return first1 if the match string is empty.
	}



	// searchN helper functions
	//
	template <typename ForwardIterator, typename Size, typename T>
	ForwardIterator     // Generic implementation.
	searchN_impl(ForwardIterator first, ForwardIterator last, Size count, const T& value, EASTL_ITC_NS::forward_iterator_tag)
	{
		if(count <= 0)
			return first;

		Size d1 = (Size)eastl::distance(first, last); // Should d1 be of type Size, ptrdiff_t, or iterator_traits<ForwardIterator>::difference_type?
													  // The problem with using iterator_traits<ForwardIterator>::difference_type is that 
		if(count > d1)                                // ForwardIterator may not be a true iterator but instead something like a pointer.
			return last;

		for(; d1 >= count; ++first, --d1)
		{
			ForwardIterator i(first);

			for(Size n = 0; n < count; ++n, ++i, --d1)
			{
				if(!(*i == value)) // Note that we always express value comparisons in terms of < or ==.
					goto not_found;
			}
			return first;

			not_found:
			first = i;
		}
		return last;
	}

	template <typename RandomAccessIterator, typename Size, typename T> inline
	RandomAccessIterator    // Random access iterator implementation. Much faster than generic implementation.
	searchN_impl(RandomAccessIterator first, RandomAccessIterator last, Size count, const T& value, EASTL_ITC_NS::random_access_iterator_tag)
	{
		if(count <= 0)
			return first;
		else if(count == 1)
			return find(first, last, value);
		else if(last > first)
		{
			RandomAccessIterator lookAhead;
			RandomAccessIterator backTrack;

			Size skipOffset = (count - 1);
			Size tailSize = (Size)(last - first);
			Size remainder;
			Size prevRemainder;

			for(lookAhead = first + skipOffset; tailSize >= count; lookAhead += count)
			{
				tailSize -= count;

				if(*lookAhead == value)
				{
					remainder = skipOffset;

					for(backTrack = lookAhead - 1; *backTrack == value; --backTrack)
					{
						if(--remainder == 0)
							return (lookAhead - skipOffset); // success
					}

					if(remainder <= tailSize)
					{
						prevRemainder = remainder;

						while(*(++lookAhead) == value)
						{
							if(--remainder == 0)
								return (backTrack + 1); // success
						}
						tailSize -= (prevRemainder - remainder);
					}
					else
						return last; // failure
				}

				// lookAhead here is always pointing to the element of the last mismatch.
			}
		}

		return last; // failure
	}


	/// searchN
	///
	/// Returns: The first iterator i in the range [first, last count) such that 
	/// for any nonnegative integer n less than count the following corresponding 
	/// conditions hold: *(i + n) == value, pred(*(i + n),value) != false. 
	/// Returns last if no such iterator is found.
	///
	/// Complexity: At most '(last1 - first1) * count' applications of the corresponding predicate.
	///
	template <typename ForwardIterator, typename Size, typename T>
	ForwardIterator
	searchN(ForwardIterator first, ForwardIterator last, Size count, const T& value)
	{
		typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC;
		return eastl::searchN_impl(first, last, count, value, IC());
	}


	/// binarySearch
	///
	/// Returns: true if there is an iterator i in the range [first last) that 
	/// satisfies the corresponding conditions: !(*i < value) && !(value < *i).
	///
	/// Complexity: At most 'log(last - first) + 2' comparisons.
	///
	/// Note: The reason binarySearch returns bool instead of an iterator is
	/// that searchN, lowerBound, or equalRange already return an iterator. 
	/// However, there are arguments that binarySearch should return an iterator.
	/// Note that we provide binarySearchI (STL extension) to return an iterator.
	///
	/// To use searchN to find an item, do this:
	///     iterator i = searchN(begin, end, 1, value);
	/// To use lowerBound to find an item, do this:
	///     iterator i = lowerBound(begin, end, value);
	///     if((i != last) && !(value < *i))
	///         <use the iterator>
	/// It turns out that the above lowerBound method is as fast as binarySearch
	/// would be if it returned an iterator.
	///
	template <typename ForwardIterator, typename T>
	inline bool
	binarySearch(ForwardIterator first, ForwardIterator last, const T& value)
	{
		// To do: This can be made slightly faster by not using lowerBound.
		ForwardIterator i(eastl::lowerBound<ForwardIterator, T>(first, last, value));
		return ((i != last) && !(value < *i)); // Note that we always express value comparisons in terms of < or ==.
	}


	/// binarySearch
	///
	/// Returns: true if there is an iterator i in the range [first last) that 
	/// satisfies the corresponding conditions: compare(*i, value) == false && 
	/// compare(value, *i) == false.
	///
	/// Complexity: At most 'log(last - first) + 2' comparisons.
	///
	/// Note: See comments above regarding the bool return value of binarySearch.
	///
	template <typename ForwardIterator, typename T, typename Compare>
	inline bool
	binarySearch(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
	{
		// To do: This can be made slightly faster by not using lowerBound.
		ForwardIterator i(eastl::lowerBound<ForwardIterator, T, Compare>(first, last, value, compare));
		return ((i != last) && !compare(value, *i));
	}


	/// binarySearchI
	///
	/// Returns: iterator if there is an iterator i in the range [first last) that 
	/// satisfies the corresponding conditions: !(*i < value) && !(value < *i).
	/// Returns last if the value is not found.
	///
	/// Complexity: At most 'log(last - first) + 2' comparisons.
	///
	template <typename ForwardIterator, typename T>
	inline ForwardIterator
	binarySearchI(ForwardIterator first, ForwardIterator last, const T& value)
	{
		// To do: This can be made slightly faster by not using lowerBound.
		ForwardIterator i(eastl::lowerBound<ForwardIterator, T>(first, last, value));
		if((i != last) && !(value < *i)) // Note that we always express value comparisons in terms of < or ==.
			return i;
		return last;
	}


	/// binarySearchI
	///
	/// Returns: iterator if there is an iterator i in the range [first last) that 
	/// satisfies the corresponding conditions: !(*i < value) && !(value < *i).
	/// Returns last if the value is not found.
	///
	/// Complexity: At most 'log(last - first) + 2' comparisons.
	///
	template <typename ForwardIterator, typename T, typename Compare>
	inline ForwardIterator
	binarySearchI(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
	{
		// To do: This can be made slightly faster by not using lowerBound.
		ForwardIterator i(eastl::lowerBound<ForwardIterator, T, Compare>(first, last, value, compare));
		if((i != last) && !compare(value, *i))
			return i;
		return last;
	}


	/// unique
	///
	/// Given a sorted range, this function removes duplicated items.
	/// Note that if you have a container then you will probably want 
	/// to call erase on the container with the return value if your 
	/// goal is to remove the duplicated items from the container.
	///
	/// Effects: Eliminates all but the first element from every consecutive 
	/// group of equal elements referred to by the iterator i in the range 
	/// [first, last) for which the following corresponding condition holds:
	/// *i == *(i - 1).
	///
	/// Returns: The end of the resulting range.
	///
	/// Complexity: If the range (last - first) is not empty, exactly (last - first)
	/// applications of the corresponding predicate, otherwise no applications of the predicate.
	///
	/// Example usage:
	///    vector<int> intArray;
	///    ...
	///    intArray.erase(unique(intArray.begin(), intArray.end()), intArray.end());
	///
	template <typename ForwardIterator>
	ForwardIterator unique(ForwardIterator first, ForwardIterator last)
	{
		first = eastl::adjacentFind<ForwardIterator>(first, last);

		if(first != last) // We expect that there are duplicated items, else the user wouldn't be calling this function.
		{
			ForwardIterator dest(first);
			
			for(++first; first != last; ++first)
			{
				if(!(*dest == *first)) // Note that we always express value comparisons in terms of < or ==.
					*++dest = *first;
			}
			return ++dest;
		}
		return last;
	}


	/// unique
	///
	/// Given a sorted range, this function removes duplicated items.
	/// Note that if you have a container then you will probably want 
	/// to call erase on the container with the return value if your 
	/// goal is to remove the duplicated items from the container.
	///
	/// Effects: Eliminates all but the first element from every consecutive 
	/// group of equal elements referred to by the iterator i in the range 
	/// [first, last) for which the following corresponding condition holds:
	/// predicate(*i, *(i - 1)) != false.
	///
	/// Returns: The end of the resulting range.
	///
	/// Complexity: If the range (last - first) is not empty, exactly (last - first)
	/// applications of the corresponding predicate, otherwise no applications of the predicate.
	///
	template <typename ForwardIterator, typename BinaryPredicate>
	ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate predicate)
	{
		first = eastl::adjacentFind<ForwardIterator, BinaryPredicate>(first, last, predicate);

		if(first != last) // We expect that there are duplicated items, else the user wouldn't be calling this function.
		{
			ForwardIterator dest(first);
			
			for(++first; first != last; ++first)
			{
				if(!predicate(*dest, *first))
					*++dest = *first;
			}
			return ++dest;
		}
		return last;
	}



	// findEnd
	//
	// We provide two versions here, one for a bidirectional iterators and one for
	// regular forward iterators. Given that we are searching backward, it's a bit 
	// more efficient if we can use backwards iteration to implement our search, 
	// though this requires an iterator that can be reversed.
	//
	template <typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1
	findEnd_impl(ForwardIterator1 first1, ForwardIterator1 last1,
				  ForwardIterator2 first2, ForwardIterator2 last2,
				  EASTL_ITC_NS::forward_iterator_tag, EASTL_ITC_NS::forward_iterator_tag)
	{
		if(first2 != last2) // We have to do this check because the search algorithm below will return first1 (and not last1) if the first2/last2 range is empty.
		{
			for(ForwardIterator1 result(last1); ; )
			{
				const ForwardIterator1 resultNext(eastl::search(first1, last1, first2, last2));

				if(resultNext != last1) // If another sequence was found...
				{
					first1 = result = resultNext;
					++first1;
				}
				else
					return result;
			}
		}
		return last1;
	}

	template <typename BidirectionalIterator1, typename BidirectionalIterator2>
	BidirectionalIterator1
	findEnd_impl(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
				  BidirectionalIterator2 first2, BidirectionalIterator2 last2,
				  EASTL_ITC_NS::bidirectional_iterator_tag, EASTL_ITC_NS::bidirectional_iterator_tag)
	{
		typedef eastl::reverse_iterator<BidirectionalIterator1> reverse_iterator1;
		typedef eastl::reverse_iterator<BidirectionalIterator2> reverse_iterator2;

		reverse_iterator1 rresult(eastl::search(reverse_iterator1(last1), reverse_iterator1(first1), 
												reverse_iterator2(last2), reverse_iterator2(first2)));
		if(rresult.base() != first1) // If we found something...
		{
			BidirectionalIterator1 result(rresult.base());

			eastl::advance(result, -eastl::distance(first2, last2)); // We have an opportunity to optimize this, as the 
			return result;                                           // search function already calculates this distance.
		}
		return last1;
	}

	/// findEnd
	///
	/// Finds the last occurrence of the second sequence in the first sequence.
	/// As such, this function is much like the C string function strrstr and it 
	/// is also the same as a reversed version of 'search'. It is called findEnd
	/// instead of the possibly more consistent search_end simply because the C++
	/// standard algorithms have such naming.
	///
	/// Returns an iterator between first1 and last1 if the sequence is found.
	/// returns last1 (the end of the first seqence) if the sequence is not found.
	///
	template <typename ForwardIterator1, typename ForwardIterator2>
	inline ForwardIterator1
	findEnd(ForwardIterator1 first1, ForwardIterator1 last1,
			 ForwardIterator2 first2, ForwardIterator2 last2)
	{
		typedef typename eastl::iterator_traits<ForwardIterator1>::iterator_category IC1;
		typedef typename eastl::iterator_traits<ForwardIterator2>::iterator_category IC2;

		return eastl::findEnd_impl(first1, last1, first2, last2, IC1(), IC2());
	}




	// To consider: Fold the predicate and non-predicate versions of 
	//              this algorithm into a single function.
	template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1
	findEnd_impl(ForwardIterator1 first1, ForwardIterator1 last1,
				  ForwardIterator2 first2, ForwardIterator2 last2,
				  BinaryPredicate predicate,
				  EASTL_ITC_NS::forward_iterator_tag, EASTL_ITC_NS::forward_iterator_tag)
	{
		if(first2 != last2) // We have to do this check because the search algorithm below will return first1 (and not last1) if the first2/last2 range is empty.
		{
			for(ForwardIterator1 result = last1; ; )
			{
				const ForwardIterator1 resultNext(eastl::search<ForwardIterator1, ForwardIterator2, BinaryPredicate>(first1, last1, first2, last2, predicate));

				if(resultNext != last1) // If another sequence was found...
				{
					first1 = result = resultNext;
					++first1;
				}
				else
					return result;
			}
		}
		return last1;
	}

	template <typename BidirectionalIterator1, typename BidirectionalIterator2, typename BinaryPredicate>
	BidirectionalIterator1
	findEnd_impl(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
				  BidirectionalIterator2 first2, BidirectionalIterator2 last2,
				  BinaryPredicate predicate, 
				  EASTL_ITC_NS::bidirectional_iterator_tag, EASTL_ITC_NS::bidirectional_iterator_tag)
	{
		typedef eastl::reverse_iterator<BidirectionalIterator1> reverse_iterator1;
		typedef eastl::reverse_iterator<BidirectionalIterator2> reverse_iterator2;

		reverse_iterator1 rresult(eastl::search<reverse_iterator1, reverse_iterator2, BinaryPredicate>
											   (reverse_iterator1(last1), reverse_iterator1(first1), 
												reverse_iterator2(last2), reverse_iterator2(first2),
												predicate));
		if(rresult.base() != first1) // If we found something...
		{
			BidirectionalIterator1 result(rresult.base());
			eastl::advance(result, -eastl::distance(first2, last2));
			return result;
		}
		return last1;
	}


	/// findEnd
	///
	/// Effects: Finds a subsequence of equal values in a sequence.
	///
	/// Returns: The last iterator i in the range [first1, last1 - (last2 - first2))
	/// such that for any nonnegative integer n < (last2 - first2), the following 
	/// corresponding conditions hold: pred(*(i+n),*(first2+n)) != false. Returns 
	/// last1 if no such iterator is found.
	///
	/// Complexity: At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1)
	/// applications of the corresponding predicate.
	///
	template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	inline ForwardIterator1
	findEnd(ForwardIterator1 first1, ForwardIterator1 last1,
			 ForwardIterator2 first2, ForwardIterator2 last2,
			 BinaryPredicate predicate)
	{
		typedef typename eastl::iterator_traits<ForwardIterator1>::iterator_category IC1;
		typedef typename eastl::iterator_traits<ForwardIterator2>::iterator_category IC2;

		return eastl::findEnd_impl<ForwardIterator1, ForwardIterator2, BinaryPredicate>
								   (first1, last1, first2, last2, predicate, IC1(), IC2());
	}



	/// setDifference
	///
	/// setDifference iterates over both input ranges and copies elements present 
	/// in the first range but not the second to the output range.
	///
	/// Effects: Copies the elements of the range [first1, last1) which are not 
	/// present in the range [first2, last2) to the range beginning at result. 
	/// The elements in the constructed range are sorted.
	/// 
	/// Requires: The input ranges must be sorted.
	/// Requires: The output range shall not overlap with either of the original ranges.
	/// 
	/// Returns: The end of the output range.
	/// 
	/// Complexity: At most (2 * ((last1 - first1) + (last2 - first2)) - 1) comparisons.
	///
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator setDifference(InputIterator1 first1, InputIterator1 last1,
								  InputIterator2 first2, InputIterator2 last2, 
								  OutputIterator result) 
	{
		while((first1 != last1) && (first2 != last2))
		{
			if(*first1 < *first2) 
			{
				*result = *first1;
				++first1;
				++result;
			}
			else if(*first2 < *first1)
				++first2;
			else 
			{
				++first1;
				++first2;
			}
		}

		return eastl::copy(first1, last1, result);
	}


	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator setDifference(InputIterator1 first1, InputIterator1 last1,
								  InputIterator2 first2, InputIterator2 last2, 
								  OutputIterator result, Compare compare) 
	{
		while((first1 != last1) && (first2 != last2))
		{
			if(compare(*first1, *first2)) 
			{
				EASTL_VALIDATE_COMPARE(!compare(*first2, *first1)); // Validate that the compare function is sane.
				*result = *first1;
				++first1;
				++result;
			}
			else if(compare(*first2, *first1))
			{
				EASTL_VALIDATE_COMPARE(!compare(*first1, *first2)); // Validate that the compare function is sane.
				++first2;
			}
			else 
			{
				++first1;
				++first2;
			}
		}

		return eastl::copy(first1, last1, result);
	}



	/// set_symmetric_difference
	///
	/// setDifference iterates over both input ranges and copies elements present 
	/// in the either range but not the other to the output range.
	///
	/// Effects: Copies the elements of the range [first1, last1) which are not 
	/// present in the range [first2, last2), and the elements of the range [first2, last2) 
	/// which are not present in the range [first1, last1) to the range beginning at result. 
	/// The elements in the constructed range are sorted.
	///
	/// Requires: The input ranges must be sorted.
	/// Requires: The resulting range shall not overlap with either of the original ranges.
	///
	/// Returns: The end of the constructed range.
	///
	/// Complexity: At most (2 * ((last1 - first1) + (last2 - first2)) - 1) comparisons.
	/// 
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
											InputIterator2 first2, InputIterator2 last2,
											OutputIterator result)
	{
		while((first1 != last1) && (first2 != last2))
		{
			if(*first1 < *first2)
			{
				*result = *first1;
				++first1;
				++result;
			}
			else if(*first2 < *first1)
			{
				*result = *first2;
				++first2;
				++result;
			}
			else
			{
				++first1;
				++first2;
			}
		}
	
		return eastl::copy(first2, last2, eastl::copy(first1, last1, result));
	}


	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
											InputIterator2 first2, InputIterator2 last2,
											OutputIterator result, Compare compare)
	{
		while((first1 != last1) && (first2 != last2))
		{
			if(compare(*first1, *first2))
			{
				EASTL_VALIDATE_COMPARE(!compare(*first2, *first1)); // Validate that the compare function is sane.
				*result = *first1;
				++first1;
				++result;
			}
			else if(compare(*first2, *first1))
			{
				EASTL_VALIDATE_COMPARE(!compare(*first1, *first2)); // Validate that the compare function is sane.
				*result = *first2;
				++first2;
				++result;
			}
			else
			{
				++first1;
				++first2;
			}
		}
	
		return eastl::copy(first2, last2, eastl::copy(first1, last1, result));
	}




	/// set_intersection
	///
	/// set_intersection over both ranges and copies elements present in
	/// both ranges to the output range. 
	///
	/// Effects: Constructs a sorted intersection of the elements from the 
	/// two ranges; that is, the set of elements that are present in both of the ranges.
	///
	/// Requires: The input ranges must be sorted.
	/// Requires: The resulting range shall not overlap with either of the original ranges.
	///  
	/// Returns: The end of the constructed range.
	/// 
	/// Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1)  comparisons.
	/// 
	/// Note: The copying operation is stable; if an element is present in both ranges, 
	/// the one from the first range is copied.
	/// 
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
									InputIterator2 first2, InputIterator2 last2,
									OutputIterator result)
	{
		while((first1 != last1) && (first2 != last2))
		{
			if(*first1 < *first2)
				++first1;
			else if(*first2 < *first1)
				++first2;
			else
			{
				*result = *first1;
				++first1;
				++first2;
				++result;
			}
		}

		return result;
	}


	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
									InputIterator2 first2, InputIterator2 last2,
									OutputIterator result, Compare compare)
	{
		while((first1 != last1) && (first2 != last2))
		{
			if(compare(*first1, *first2))
			{
				EASTL_VALIDATE_COMPARE(!compare(*first2, *first1)); // Validate that the compare function is sane.
				++first1;
			}
			else if(compare(*first2, *first1))
			{
				EASTL_VALIDATE_COMPARE(!compare(*first1, *first2)); // Validate that the compare function is sane.
				++first2;
			}
			else
			{
				*result = *first1;
				++first1;
				++first2;
				++result;
			}
		}

		return result;
	}



	/// set_union
	///
	/// set_union iterators over both ranges and copies elements present in
	/// both ranges to the output range.
	///
	/// Effects: Constructs a sorted union of the elements from the two ranges; 
	/// that is, the set of elements that are present in one or both of the ranges.
	///
	/// Requires: The input ranges must be sorted.
	/// Requires: The resulting range shall not overlap with either of the original ranges.
	///
	/// Returns: The end of the constructed range.
	///
	/// Complexity: At most (2 * ((last1 - first1) + (last2 - first2)) - 1) comparisons.
	///
	/// Note: The copying operation is stable; if an element is present in both ranges, 
	/// the one from the first range is copied.
	///
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
							 InputIterator2 first2, InputIterator2 last2,
							 OutputIterator result)
	{
		while((first1 != last1) && (first2 != last2))
		{
			if(*first1 < *first2)
			{
				*result = *first1;
				++first1;
			}
			else if(*first2 < *first1)
			{
				*result = *first2;
				++first2;
			}
			else
			{
				*result = *first1;
				++first1;
				++first2;
			}
			++result;
		}

		return eastl::copy(first2, last2, eastl::copy(first1, last1, result));
	}


	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
							 InputIterator2 first2, InputIterator2 last2,
							 OutputIterator result, Compare compare)
	{
		while((first1 != last1) && (first2 != last2))
		{
			if(compare(*first1, *first2))
			{
				EASTL_VALIDATE_COMPARE(!compare(*first2, *first1)); // Validate that the compare function is sane.
				*result = *first1;
				++first1;
			}
			else if(compare(*first2, *first1))
			{
				EASTL_VALIDATE_COMPARE(!compare(*first1, *first2)); // Validate that the compare function is sane.
				*result = *first2;
				++first2;
			}
			else
			{
				*result = *first1;
				++first1;
				++first2;
			}
			++result;
		}

		return eastl::copy(first2, last2, eastl::copy(first1, last1, result));
	}


	/// is_permutation
	///
	template<typename ForwardIterator1, typename ForwardIterator2>
	bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
	{
		typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type;

		// Skip past any equivalent initial elements.
		while((first1 != last1) && (*first1 == *first2))
		{
			++first1;
			++first2;
		}

		if(first1 != last1)
		{
			const difference_type first1Size = eastl::distance(first1, last1);
			ForwardIterator2 last2 = first2;
			eastl::advance(last2, first1Size);

			for(ForwardIterator1 i = first1; i != last1; ++i)
			{
				if(i == eastl::find(first1, i, *i)) 
				{
					const difference_type c = eastl::count(first2, last2, *i);

					if((c == 0) || (c != eastl::count(i, last1, *i)))
						return false;
				}
			}
		}

		return true;
	}

	/// is_permutation
	///
	template<typename ForwardIterator1, typename ForwardIterator2, class BinaryPredicate>
	bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate predicate)
	{
		typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type;

		// Skip past any equivalent initial elements.
		while((first1 != last1) && predicate(*first1, *first2))
		{
			++first1;
			++first2;
		}

		if(first1 != last1)
		{
			const difference_type first1Size = eastl::distance(first1, last1);
			ForwardIterator2 last2 = first2;
			eastl::advance(last2, first1Size);

			for(ForwardIterator1 i = first1; i != last1; ++i)
			{
				if(i == eastl::find(first1, i, *i, predicate)) 
				{
					const difference_type c = eastl::count(first2, last2, *i, predicate);

					if((c == 0) || (c != eastl::count(i, last1, *i, predicate)))
						return false;
				}
			}
		}

		return true;
	}


	/// next_permutation
	///
	/// mutates the range [first, last) to the next permutation. Returns true if the 
	/// new range is not the final permutation (sorted like the starting permutation).
	/// Permutations start with a sorted range, and false is returned when next_permutation
	/// results in the initial sorted range, or if the range has <= 1 element.
	/// Note that elements are compared by operator < (as usual) and that elements deemed
	/// equal via this are not rearranged.
	///
	/// http://marknelson.us/2002/03/01/next-permutation/
	/// Basically we start with an ordered range and reverse it's order one specifically
	/// chosen swap and reverse at a time. It happens that this require going through every 
	/// permutation of the range. We use the same variable names as the document above.
	///
	/// To consider: Significantly improved permutation/combination functionality: 
	///    http://home.roadrunner.com/~hinnant/combinations.html
	///
	/// Example usage:
	///     vector<int> intArray;
	///     // <populate intArray>
	///     sort(intArray.begin(), intArray.end());
	///     do {
	///         // <do something with intArray>
	///     } while(next_permutation(intArray.begin(), intArray.end()));
	///

	template<typename BidirectionalIterator, typename Compare>
	bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare compare)
	{
		if(first != last) // If there is anything in the range...
		{
			BidirectionalIterator i = last;

			if(first != --i) // If the range has more than one item...
			{
				for(;;)
				{
					BidirectionalIterator ii(i), j;
 
					if(compare(*--i, *ii)) // Find two consecutive values where the first is less than the second.
					{
						j = last;
						while(!compare(*i, *--j)) // Find the final value that's greater than the first (it may be equal to the second).
							{}
						eastl::iterSwap(i, j);     // Swap the first and the final.
						eastl::reverse(ii, last);   // Reverse the ranget from second to last. 
						return true;
					}

					if(i == first) // There are no two consecutive values where the first is less than the second, meaning the range is in reverse order. The reverse ordered range is always the last permutation.
					{
						eastl::reverse(first, last);
						break; // We are done.
					}
				}
			}
		}

		return false;
	}

	template<typename BidirectionalIterator>
	bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
	{
		typedef typename eastl::iterator_traits<BidirectionalIterator>::value_type value_type;

		return next_permutation(first, last, eastl::less<value_type>());
	}



	/// rotate
	///
	/// Effects: For each non-negative integer i < (last - first), places the element from the 
	/// position first + i into position first + (i + (last - middle)) % (last - first).
	///
	/// Returns: first + (last - middle). That is, returns where first went to.
	/// 
	/// Remarks: This is a left rotate.
	/// 
	/// Requires: [first,middle) and [middle,last) shall be valid ranges. ForwardIterator shall 
	/// satisfy the requirements of ValueSwappable (17.6.3.2). The type of *first shall satisfy 
	/// the requirements of MoveConstructible (Table 20) and the requirements of MoveAssignable.
	///
	/// Complexity: At most last - first swaps.
	///
	/// Note: While rotate works on ForwardIterators (e.g. slist) and BidirectionalIterators (e.g. list), 
	/// you can get much better performance (O(1) instead of O(n)) with slist and list rotation by 
	/// doing splice operations on those lists instead of calling this rotate function. 
	///
	/// http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf / http://books.google.com/books?id=kse_7qbWbjsC&pg=PA14&lpg=PA14&dq=Programming+Pearls+flipping+hands
	/// http://books.google.com/books?id=tjOlkl7ecVQC&pg=PA189&lpg=PA189&dq=stepanov+Elements+of+Programming+rotate
	/// http://stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast
	///
	/// Strategy:
	///     - We handle the special case of (middle == first) and (middle == last) no-ops
	///       up front in the main rotate entry point.
	///     - There's a basic ForwardIterator implementation (rotate_general_impl) which is 
	///       a fallback implementation that's not as fast as others but works for all cases.
	///     - There's a slightly better BidirectionalIterator implementation.
	///     - We have specialized versions for rotating elements that are is_trivially_move_assignable.
	///       These versions will use memmove for when we have a RandomAccessIterator.
	///     - We have a specialized version for rotating by only a single position, as that allows us
	///       (with any iterator type) to avoid a lot of logic involved with algorithms like "flipping hands"
	///       and achieve near optimal O(n) behavior. it turns out that rotate-by-one is a common use
	///       case in practice.
	/// 
	namespace Internal
	{
		template<typename ForwardIterator>
		ForwardIterator rotate_general_impl(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
		{
			ForwardIterator current = middle;

			do {
				swap(*first++, *current++);

				if(first == middle)
					middle = current;
			} while(current != last);

			ForwardIterator result = first;
			current = middle;

			while(current != last)
			{
				swap(*first++, *current++);

				if(first == middle)
					middle = current;
				else if(current == last)
					current = middle;
			}

			return result; // result points to first + (last - middle).
		}


		template <typename ForwardIterator>
		ForwardIterator move_rotate_left_by_one(ForwardIterator first, ForwardIterator last)
		{
			typedef typename eastl::iterator_traits<ForwardIterator>::value_type value_type;

			value_type temp(eastl::move(*first));
			ForwardIterator result = eastl::move(eastl::next(first), last, first); // Note that while our template type is BidirectionalIterator, if the actual
			*result = eastl::move(temp);                                           // iterator is a RandomAccessIterator then this move will be a memmove for trivial types.

			return result; // result points to the final element in the range.
		}


		template <typename BidirectionalIterator>
		BidirectionalIterator move_rotate_right_by_one(BidirectionalIterator first, BidirectionalIterator last)
		{
			typedef typename eastl::iterator_traits<BidirectionalIterator>::value_type value_type;

			BidirectionalIterator beforeLast = eastl::prev(last);
			value_type temp(eastl::move(*beforeLast));
			BidirectionalIterator result = eastl::move_backward(first, beforeLast, last); // Note that while our template type is BidirectionalIterator, if the actual
			*first = eastl::move(temp);                                                   // iterator is a RandomAccessIterator then this move will be a memmove for trivial types.

			return result; // result points to the first element in the range.
		}

		template <typename /*IteratorCategory*/, bool /*is_trivially_move_assignable*/>
		struct rotate_helper
		{
			template <typename ForwardIterator>
			static ForwardIterator rotate_impl(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
				{ return Internal::rotate_general_impl(first, middle, last); }
		};

		template <> 
		struct rotate_helper<EASTL_ITC_NS::forward_iterator_tag, true>
		{
			template <typename ForwardIterator>
			static ForwardIterator rotate_impl(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
			{
				if(eastl::next(first) == middle) // If moving trivial types by a single element, memcpy is fast for that case.
					return Internal::move_rotate_left_by_one(first, last);
				return Internal::rotate_general_impl(first, middle, last);
			}
		};

		template <> 
		struct rotate_helper<EASTL_ITC_NS::bidirectional_iterator_tag, false>
		{
			template <typename BidirectionalIterator>
			static BidirectionalIterator rotate_impl(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
				{ return Internal::rotate_general_impl(first, middle, last); } // rotate_general_impl outperforms the flipping hands algorithm.

			/* 
			// Simplest "flipping hands" implementation. Disabled because it's slower on average than rotate_general_impl.
			template <typename BidirectionalIterator>
			static BidirectionalIterator rotate_impl(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
			{ 
				eastl::reverse(first, middle);
				eastl::reverse(middle, last);
				eastl::reverse(first, last);
				return first + (last - middle); // This can be slow for large ranges because operator + and - are O(n).
			}

			// Smarter "flipping hands" implementation, but still disabled because benchmarks are showing it to be slower than rotate_general_impl.
			template <typename BidirectionalIterator>
			static BidirectionalIterator rotate_impl(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
			{
				// This is the "flipping hands" algorithm.
				eastl::reverse_impl(first,  middle, EASTL_ITC_NS::bidirectional_iterator_tag()); // Reverse the left side.
				eastl::reverse_impl(middle, last,   EASTL_ITC_NS::bidirectional_iterator_tag()); // Reverse the right side.

				// Reverse the entire range.
				while((first != middle) && (middle != last)) 
				{
					eastl::iterSwap(first, --last);
					++first;
				}

				if(first == middle) // Finish reversing the entire range.
				{
					eastl::reverse_impl(middle, last, bidirectional_iterator_tag());
					return last;
				}
				else
				{
					eastl::reverse_impl(first, middle, bidirectional_iterator_tag());
					return first;
				}
			}
			*/
		};

		template <> 
		struct rotate_helper<EASTL_ITC_NS::bidirectional_iterator_tag, true>
		{
			template <typename BidirectionalIterator>
			static BidirectionalIterator rotate_impl(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
			{
				if(eastl::next(first) == middle) // If moving trivial types by a single element, memcpy is fast for that case. 
					return Internal::move_rotate_left_by_one(first, last);
				if(eastl::next(middle) == last)
					return Internal::move_rotate_right_by_one(first, last);
				return Internal::rotate_general_impl(first, middle, last);
			}
		};

		template <typename Integer>
		inline Integer greatest_common_divisor(Integer x, Integer y)
		{
			do {
				Integer t = (x % y);
				x = y;
				y = t;
			} while(y);

			return x;
		}

		template <> 
		struct rotate_helper<EASTL_ITC_NS::random_access_iterator_tag, false>
		{
			// This is the juggling algorithm, using move operations.
			// In practice this implementation is about 25% faster than rotate_general_impl. We may want to 
			// consider sticking with just rotate_general_impl and avoid the code generation of this function.
			template <typename RandomAccessIterator>
			static RandomAccessIterator rotate_impl(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
			{
				typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
				typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;

				const difference_type m1 = (middle - first);
				const difference_type m2 = (last - middle);
				const difference_type g  = Internal::greatest_common_divisor(m1, m2);
				value_type temp;

				for(RandomAccessIterator p = first + g; p != first;)
				{
					temp = eastl::move(*--p);
					RandomAccessIterator p1 = p;
					RandomAccessIterator p2 = p + m1;
					do
					{
						*p1 = eastl::move(*p2);
						p1 = p2;
						const difference_type d = (last - p2);

						if(m1 < d)
							p2 += m1;
						else
							p2 = first + (m1 - d);
					} while(p2 != p);

					*p1 = eastl::move(temp);
				}

				return first + m2;
			}
		};

		template <> 
		struct rotate_helper<EASTL_ITC_NS::random_access_iterator_tag, true>
		{
			// Experiments were done which tested the performance of using an intermediate buffer
			// to do memcpy's to as opposed to executing a swapping algorithm. It turns out this is 
			// actually slower than even rotate_general_impl, partly because the average case involves
			// memcpy'ing a quarter of the element range twice. Experiments were done with various kinds 
			// of PODs with various element counts.

			template <typename RandomAccessIterator>
			static RandomAccessIterator rotate_impl(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
			{
				if(eastl::next(first) == middle) // If moving trivial types by a single element, memcpy is fast for that case. 
					return Internal::move_rotate_left_by_one(first, last);
				if(eastl::next(middle) == last)
					return Internal::move_rotate_right_by_one(first, last);
				if((last - first) < 32) // For small ranges rotate_general_impl is faster.
					return Internal::rotate_general_impl(first, middle, last);
				return Internal::rotate_helper<EASTL_ITC_NS::random_access_iterator_tag, false>::rotate_impl(first, middle, last);
			}
		};

	} // namespace Internal


	template <typename ForwardIterator>
	ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
	{
		if(middle != first)
		{
			if(middle != last)
			{
				typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC;
				typedef typename eastl::iterator_traits<ForwardIterator>::value_type        value_type;

				return Internal::rotate_helper<IC, eastl::is_trivially_move_assignable<value_type>::value || // This is the best way of telling if we can move types via memmove, but without a conforming C++11 compiler it usually returns false.
												   eastl::is_pod<value_type>::value                       || // This is a more conservative way of telling if we can move types via memmove, and most compilers support it, but it doesn't have as full of coverage as is_trivially_move_assignable.
												   eastl::is_scalar<value_type>::value>                      // This is the most conservative means and works with all compilers, but works only for scalars.
											   ::rotate_impl(first, middle, last);
			}

			return first;
		}

		return last;
	}



	/// rotate_copy
	///
	/// Similar to rotate except writes the output to the OutputIterator and  
	/// returns an OutputIterator to the element past the last element copied
	/// (i.e. result + (last - first))
	///
	template <typename ForwardIterator, typename OutputIterator>
	OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result)
	{
		return eastl::copy(first, middle, eastl::copy(middle, last, result));
	}



} // namespace eastl


#endif // Header include guard