map.h

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


#ifndef EASTL_MAP_H
#define EASTL_MAP_H


#include <eastl/internal/config.h>
#include <eastl/internal/red_black_tree.h>
#include <eastl/functional.h>
#include <eastl/utility.h>

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



namespace eastl
{

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


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


	/// EASTL_MAP_DEFAULT_ALLOCATOR
	///
	#ifndef EASTL_MAP_DEFAULT_ALLOCATOR
		#define EASTL_MAP_DEFAULT_ALLOCATOR allocator_type(EASTL_MAP_DEFAULT_NAME)
	#endif

	/// EASTL_MULTIMAP_DEFAULT_ALLOCATOR
	///
	#ifndef EASTL_MULTIMAP_DEFAULT_ALLOCATOR
		#define EASTL_MULTIMAP_DEFAULT_ALLOCATOR allocator_type(EASTL_MULTIMAP_DEFAULT_NAME)
	#endif



	/// map
	///
	/// Implements a canonical map. 
	///
	/// The large majority of the implementation of this class is found in the rbtree
	/// base class. We control the behaviour of rbtree via template parameters.
	///
	/// Pool allocation
	/// If you want to make a custom memory pool for a map container, your pool 
	/// needs to contain items of type map::node_type. So if you have a memory
	/// pool that has a constructor that takes the size of pool items and the
	/// count of pool items, you would do this (assuming that MemoryPool implements
	/// the Allocator interface):
	///     typedef map<Widget, int, less<Widget>, MemoryPool> WidgetMap;  // Delare your WidgetMap type.
	///     MemoryPool myPool(sizeof(WidgetMap::node_type), 100);          // Make a pool of 100 Widget nodes.
	///     WidgetMap myMap(&myPool);                                      // Create a map that uses the pool.
	///
	template <typename Key, typename T, typename Compare = eastl::less<Key>, typename Allocator = EASTLAllocatorType>
	class map
		: public rbtree<Key, eastl::pair<const Key, T>, Compare, Allocator, eastl::useFirst<eastl::pair<const Key, T> >, true, true>
	{
	public:
		typedef rbtree<Key, eastl::pair<const Key, T>, Compare, Allocator,
						eastl::useFirst<eastl::pair<const Key, T> >, true, true>   base_type;
		typedef map<Key, T, Compare, Allocator>                                     this_type;
		typedef typename base_type::size_type                                       size_type;
		typedef typename base_type::key_type                                        key_type;
		typedef T                                                                   mapped_type;
		typedef typename base_type::value_type                                      value_type;
		typedef typename base_type::node_type                                       node_type;
		typedef typename base_type::iterator                                        iterator;
		typedef typename base_type::const_iterator                                  const_iterator;
		typedef typename base_type::allocator_type                                  allocator_type;
		typedef typename base_type::insert_return_type                              insert_return_type;
		typedef typename base_type::extract_key                                     extract_key;
		// Other types are inherited from the base class.

		using base_type::begin;
		using base_type::end;
		using base_type::find;
		using base_type::lowerBound;
		using base_type::upperBound;
		using base_type::mCompare;
		using base_type::insert;
		using base_type::erase;

		class value_compare 
		{
		protected:
			friend class map;
			Compare compare;
			value_compare(Compare c) : compare(c) {}

		public:
			typedef bool       result_type;
			typedef value_type first_argument_type;
			typedef value_type second_argument_type;

			bool operator()(const value_type& x, const value_type& y) const 
				{ return compare(x.first, y.first); }
		};

	public:
		map(const allocator_type& allocator = EASTL_MAP_DEFAULT_ALLOCATOR);
		map(const Compare& compare, const allocator_type& allocator = EASTL_MAP_DEFAULT_ALLOCATOR);
		map(const this_type& x);
		#if EASTL_MOVE_SEMANTICS_ENABLED
		map(this_type&& x);
		map(this_type&& x, const allocator_type& allocator);
		#endif
		map(std::initializer_list<value_type> ilist, const Compare& compare = Compare(), const allocator_type& allocator = EASTL_MAP_DEFAULT_ALLOCATOR);

		template <typename Iterator>
		map(Iterator itBegin, Iterator itEnd); // allocator arg removed because VC7.1 fails on the default arg. To consider: Make a second version of this function without a default arg.

		#if EASTL_MOVE_SEMANTICS_ENABLED // The (this_type&& x) ctor above has the side effect of forcing us to make operator= visible in this subclass.
			this_type& operator=(const this_type& x) { return (this_type&)base_type::operator=(x); }
			this_type& operator=(std::initializer_list<value_type> ilist) { return (this_type&)base_type::operator=(ilist); }
			this_type& operator=(this_type&& x) { return (this_type&)base_type::operator=(eastl::move(x)); }
		#endif

	public:
		/// This is an extension to the C++ standard. We insert a default-constructed 
		/// element with the given key. The reason for this is that we can avoid the 
		/// potentially expensive operation of creating and/or copying a mapped_type
		/// object on the stack. Note that C++11 move insertions and variadic emplace
		/// support make this extension mostly no longer necessary.
		insert_return_type insert(const Key& key);

		value_compare value_comp() const;

		size_type erase(const Key& key);
		size_type count(const Key& key) const;

		eastl::pair<iterator, iterator>             equalRange(const Key& key);
		eastl::pair<const_iterator, const_iterator> equalRange(const Key& key) const;

		T& operator[](const Key& key); // Of map, multimap, set, and multimap, only map has operator[].

	}; // map






	/// multimap
	///
	/// Implements a canonical multimap.
	///
	/// The large majority of the implementation of this class is found in the rbtree
	/// base class. We control the behaviour of rbtree via template parameters.
	///
	/// Pool allocation
	/// If you want to make a custom memory pool for a multimap container, your pool 
	/// needs to contain items of type multimap::node_type. So if you have a memory
	/// pool that has a constructor that takes the size of pool items and the
	/// count of pool items, you would do this (assuming that MemoryPool implements
	/// the Allocator interface):
	///     typedef multimap<Widget, int, less<Widget>, MemoryPool> WidgetMap;  // Delare your WidgetMap type.
	///     MemoryPool myPool(sizeof(WidgetMap::node_type), 100);               // Make a pool of 100 Widget nodes.
	///     WidgetMap myMap(&myPool);                                           // Create a map that uses the pool.
	///
	template <typename Key, typename T, typename Compare = eastl::less<Key>, typename Allocator = EASTLAllocatorType>
	class multimap
		: public rbtree<Key, eastl::pair<const Key, T>, Compare, Allocator, eastl::useFirst<eastl::pair<const Key, T> >, true, false>
	{
	public:
		typedef rbtree<Key, eastl::pair<const Key, T>, Compare, Allocator, 
						eastl::useFirst<eastl::pair<const Key, T> >, true, false>  base_type;
		typedef multimap<Key, T, Compare, Allocator>                                this_type;
		typedef typename base_type::size_type                                       size_type;
		typedef typename base_type::key_type                                        key_type;
		typedef T                                                                   mapped_type;
		typedef typename base_type::value_type                                      value_type;
		typedef typename base_type::node_type                                       node_type;
		typedef typename base_type::iterator                                        iterator;
		typedef typename base_type::const_iterator                                  const_iterator;
		typedef typename base_type::allocator_type                                  allocator_type;
		typedef typename base_type::insert_return_type                              insert_return_type;
		typedef typename base_type::extract_key                                     extract_key;
		// Other types are inherited from the base class.

		using base_type::begin;
		using base_type::end;
		using base_type::find;
		using base_type::lowerBound;
		using base_type::upperBound;
		using base_type::mCompare;
		using base_type::insert;
		using base_type::erase;

		class value_compare 
		{
		protected:
			friend class multimap;
			Compare compare;
			value_compare(Compare c) : compare(c) {}

		public:
			typedef bool       result_type;
			typedef value_type first_argument_type;
			typedef value_type second_argument_type;

			bool operator()(const value_type& x, const value_type& y) const 
				{ return compare(x.first, y.first); }
		};

	public:
		multimap(const allocator_type& allocator = EASTL_MULTIMAP_DEFAULT_ALLOCATOR);
		multimap(const Compare& compare, const allocator_type& allocator = EASTL_MULTIMAP_DEFAULT_ALLOCATOR);
		multimap(const this_type& x);
		#if EASTL_MOVE_SEMANTICS_ENABLED
		multimap(this_type&& x);
		multimap(this_type&& x, const allocator_type& allocator);
		#endif
		multimap(std::initializer_list<value_type> ilist, const Compare& compare = Compare(), const allocator_type& allocator = EASTL_MULTIMAP_DEFAULT_ALLOCATOR);

		template <typename Iterator>
		multimap(Iterator itBegin, Iterator itEnd); // allocator arg removed because VC7.1 fails on the default arg. To consider: Make a second version of this function without a default arg.

		#if EASTL_MOVE_SEMANTICS_ENABLED // The (this_type&& x) ctor above has the side effect of forcing us to make operator= visible in this subclass.
			this_type& operator=(const this_type& x) { return (this_type&)base_type::operator=(x); }
			this_type& operator=(std::initializer_list<value_type> ilist) { return (this_type&)base_type::operator=(ilist); }
			this_type& operator=(this_type&& x) { return (this_type&)base_type::operator=(eastl::move(x)); }
		#endif

	public:
		/// This is an extension to the C++ standard. We insert a default-constructed 
		/// element with the given key. The reason for this is that we can avoid the 
		/// potentially expensive operation of creating and/or copying a mapped_type
		/// object on the stack. Note that C++11 move insertions and variadic emplace
		/// support make this extension mostly no longer necessary.
		insert_return_type insert(const Key& key);

		value_compare value_comp() const;

		size_type erase(const Key& key);
		size_type count(const Key& key) const;

		eastl::pair<iterator, iterator>             equalRange(const Key& key);
		eastl::pair<const_iterator, const_iterator> equalRange(const Key& key) const;

		/// equalRange_small
		/// This is a special version of equalRange which is optimized for the 
		/// case of there being few or no duplicated keys in the tree.
		eastl::pair<iterator, iterator>             equalRange_small(const Key& key);
		eastl::pair<const_iterator, const_iterator> equalRange_small(const Key& key) const;

	}; // multimap





	///////////////////////////////////////////////////////////////////////
	// map
	///////////////////////////////////////////////////////////////////////

	template <typename Key, typename T, typename Compare, typename Allocator>
	inline map<Key, T, Compare, Allocator>::map(const allocator_type& allocator)
		: base_type(allocator)
	{
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline map<Key, T, Compare, Allocator>::map(const Compare& compare, const allocator_type& allocator)
		: base_type(compare, allocator)
	{
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline map<Key, T, Compare, Allocator>::map(const this_type& x)
		: base_type(x)
	{
	}


	#if EASTL_MOVE_SEMANTICS_ENABLED
		template <typename Key, typename T, typename Compare, typename Allocator>
		inline map<Key, T, Compare, Allocator>::map(this_type&& x)
			: base_type(eastl::move(x))
		{
		}

		template <typename Key, typename T, typename Compare, typename Allocator>
		inline map<Key, T, Compare, Allocator>::map(this_type&& x, const allocator_type& allocator)
			: base_type(eastl::move(x), allocator)
		{
		}
	#endif


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline map<Key, T, Compare, Allocator>::map(std::initializer_list<value_type> ilist, const Compare& compare, const allocator_type& allocator)
		: base_type(ilist.begin(), ilist.end(), compare, allocator)
	{
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	template <typename Iterator>
	inline map<Key, T, Compare, Allocator>::map(Iterator itBegin, Iterator itEnd)
		: base_type(itBegin, itEnd, Compare(), EASTL_MAP_DEFAULT_ALLOCATOR)
	{
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline typename map<Key, T, Compare, Allocator>::insert_return_type
	map<Key, T, Compare, Allocator>::insert(const Key& key)
	{
		return base_type::DoInsertKey(true_type(), key);
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline typename map<Key, T, Compare, Allocator>::value_compare 
	map<Key, T, Compare, Allocator>::value_comp() const
	{
		return value_compare(mCompare);
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline typename map<Key, T, Compare, Allocator>::size_type
	map<Key, T, Compare, Allocator>::erase(const Key& key)
	{
		const iterator it(find(key));

		if(it != end()) // If it exists...
		{
			base_type::erase(it);
			return 1;
		}
		return 0;
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline typename map<Key, T, Compare, Allocator>::size_type
	map<Key, T, Compare, Allocator>::count(const Key& key) const
	{
		const const_iterator it(find(key));
		return (it != end()) ? 1 : 0;
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline eastl::pair<typename map<Key, T, Compare, Allocator>::iterator,
					   typename map<Key, T, Compare, Allocator>::iterator>
	map<Key, T, Compare, Allocator>::equalRange(const Key& key)
	{
		// The resulting range will either be empty or have one element,
		// so instead of doing two tree searches (one for lowerBound and 
		// one for upperBound), we do just lowerBound and see if the 
		// result is a range of size zero or one.
		const iterator itLower(lowerBound(key));

		if((itLower == end()) || mCompare(key, itLower.mpNode->mValue.first)) // If at the end or if (key is < itLower)...
			return eastl::pair<iterator, iterator>(itLower, itLower);

		iterator itUpper(itLower);
		return eastl::pair<iterator, iterator>(itLower, ++itUpper);
	}
	

	template <typename Key, typename T, typename Compare, typename Allocator>
	inline eastl::pair<typename map<Key, T, Compare, Allocator>::const_iterator, 
					   typename map<Key, T, Compare, Allocator>::const_iterator>
	map<Key, T, Compare, Allocator>::equalRange(const Key& key) const
	{
		// See equalRange above for comments.
		const const_iterator itLower(lowerBound(key));

		if((itLower == end()) || mCompare(key, itLower.mpNode->mValue.first)) // If at the end or if (key is < itLower)...
			return eastl::pair<const_iterator, const_iterator>(itLower, itLower);

		const_iterator itUpper(itLower);
		return eastl::pair<const_iterator, const_iterator>(itLower, ++itUpper);
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline T& map<Key, T, Compare, Allocator>::operator[](const Key& key)
	{
		iterator itLower(lowerBound(key)); // itLower->first is >= key.

		if((itLower == end()) || mCompare(key, (*itLower).first))
		{
			itLower = base_type::DoInsertKey(true_type(), itLower, key);
		}

		return (*itLower).second;

		// Reference implementation of this function, which may not be as fast:
		//iterator it(base_type::insert(eastl::pair<iterator, iterator>(key, T())).first);
		//return it->second;
	}






	///////////////////////////////////////////////////////////////////////
	// multimap
	///////////////////////////////////////////////////////////////////////

	template <typename Key, typename T, typename Compare, typename Allocator>
	inline multimap<Key, T, Compare, Allocator>::multimap(const allocator_type& allocator)
		: base_type(allocator)
	{
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline multimap<Key, T, Compare, Allocator>::multimap(const Compare& compare, const allocator_type& allocator)
		: base_type(compare, allocator)
	{
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline multimap<Key, T, Compare, Allocator>::multimap(const this_type& x)
		: base_type(x)
	{
	}


	#if EASTL_MOVE_SEMANTICS_ENABLED
		template <typename Key, typename T, typename Compare, typename Allocator>
		inline multimap<Key, T, Compare, Allocator>::multimap(this_type&& x)
			: base_type(eastl::move(x))
		{
		}

		template <typename Key, typename T, typename Compare, typename Allocator>
		inline multimap<Key, T, Compare, Allocator>::multimap(this_type&& x, const allocator_type& allocator)
			: base_type(eastl::move(x), allocator)
		{
		}
	#endif


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline multimap<Key, T, Compare, Allocator>::multimap(std::initializer_list<value_type> ilist, const Compare& compare, const allocator_type& allocator)
		: base_type(ilist.begin(), ilist.end(), compare, allocator)
	{
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	template <typename Iterator>
	inline multimap<Key, T, Compare, Allocator>::multimap(Iterator itBegin, Iterator itEnd)
		: base_type(itBegin, itEnd, Compare(), EASTL_MULTIMAP_DEFAULT_ALLOCATOR)
	{
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline typename multimap<Key, T, Compare, Allocator>::insert_return_type
	multimap<Key, T, Compare, Allocator>::insert(const Key& key)
	{
		return base_type::DoInsertKey(false_type(), key);
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline typename multimap<Key, T, Compare, Allocator>::value_compare 
	multimap<Key, T, Compare, Allocator>::value_comp() const
	{
		return value_compare(mCompare);
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline typename multimap<Key, T, Compare, Allocator>::size_type
	multimap<Key, T, Compare, Allocator>::erase(const Key& key)
	{
		const eastl::pair<iterator, iterator> range(equalRange(key));
		const size_type n = (size_type)eastl::distance(range.first, range.second);
		base_type::erase(range.first, range.second);
		return n;
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline typename multimap<Key, T, Compare, Allocator>::size_type
	multimap<Key, T, Compare, Allocator>::count(const Key& key) const
	{
		const eastl::pair<const_iterator, const_iterator> range(equalRange(key));
		return (size_type)eastl::distance(range.first, range.second);
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline eastl::pair<typename multimap<Key, T, Compare, Allocator>::iterator,
					   typename multimap<Key, T, Compare, Allocator>::iterator>
	multimap<Key, T, Compare, Allocator>::equalRange(const Key& key)
	{
		// There are multiple ways to implement equalRange. The implementation mentioned
		// in the C++ standard and which is used by most (all?) commercial STL implementations
		// is this:
		//    return eastl::pair<iterator, iterator>(lowerBound(key), upperBound(key));
		//
		// This does two tree searches -- one for the lower bound and one for the 
		// upper bound. This works well for the case whereby you have a large container
		// and there are lots of duplicated values. We provide an alternative version
		// of equalRange called equalRange_small for cases where the user is confident
		// that the number of duplicated items is only a few.

		return eastl::pair<iterator, iterator>(lowerBound(key), upperBound(key));
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline eastl::pair<typename multimap<Key, T, Compare, Allocator>::const_iterator, 
					   typename multimap<Key, T, Compare, Allocator>::const_iterator>
	multimap<Key, T, Compare, Allocator>::equalRange(const Key& key) const
	{
		// See comments above in the non-const version of equalRange.
		return eastl::pair<const_iterator, const_iterator>(lowerBound(key), upperBound(key));
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline eastl::pair<typename multimap<Key, T, Compare, Allocator>::iterator,
					   typename multimap<Key, T, Compare, Allocator>::iterator>
	multimap<Key, T, Compare, Allocator>::equalRange_small(const Key& key)
	{
		// We provide alternative version of equalRange here which works faster
		// for the case where there are at most small number of potential duplicated keys.
		const iterator itLower(lowerBound(key));
		iterator       itUpper(itLower);

		while((itUpper != end()) && !mCompare(key, itUpper.mpNode->mValue.first))
			++itUpper;

		return eastl::pair<iterator, iterator>(itLower, itUpper);
	}


	template <typename Key, typename T, typename Compare, typename Allocator>
	inline eastl::pair<typename multimap<Key, T, Compare, Allocator>::const_iterator, 
					   typename multimap<Key, T, Compare, Allocator>::const_iterator>
	multimap<Key, T, Compare, Allocator>::equalRange_small(const Key& key) const
	{
		// We provide alternative version of equalRange here which works faster
		// for the case where there are at most small number of potential duplicated keys.
		const const_iterator itLower(lowerBound(key));
		const_iterator       itUpper(itLower);

		while((itUpper != end()) && !mCompare(key, itUpper.mpNode->mValue.first))
			++itUpper;

		return eastl::pair<const_iterator, const_iterator>(itLower, itUpper);
	}




} // namespace eastl


#endif // Header include guard