set.h

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


#ifndef EASTL_SET_H
#define EASTL_SET_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_SET_DEFAULT_NAME
	///
	/// Defines a default container name in the absence of a user-provided name.
	///
	#ifndef EASTL_SET_DEFAULT_NAME
		#define EASTL_SET_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " set" // Unless the user overrides something, this is "EASTL set".
	#endif


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


	/// EASTL_SET_DEFAULT_ALLOCATOR
	///
	#ifndef EASTL_SET_DEFAULT_ALLOCATOR
		#define EASTL_SET_DEFAULT_ALLOCATOR allocator_type(EASTL_SET_DEFAULT_NAME)
	#endif

	/// EASTL_MULTISET_DEFAULT_ALLOCATOR
	///
	#ifndef EASTL_MULTISET_DEFAULT_ALLOCATOR
		#define EASTL_MULTISET_DEFAULT_ALLOCATOR allocator_type(EASTL_MULTISET_DEFAULT_NAME)
	#endif



	/// set
	///
	/// Implements a canonical set. 
	///
	/// 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.
	///
	/// Note that the 'bMutableIterators' template parameter to rbtree is set to false.
	/// This means that set::iterator is const and the same as set::const_iterator.
	/// This is by design and it follows the C++ standard defect report recommendation.
	/// If the user wants to modify a container element, the user needs to either use
	/// mutable data members or use const_cast on the iterator's data member. Both of 
	/// these solutions are recommended by the C++ standard defect report.
	/// To consider: Expose the bMutableIterators template policy here at the set level
	/// so the user can have non-const set iterators via a template parameter.
	///
	/// Pool allocation
	/// If you want to make a custom memory pool for a set container, your pool 
	/// needs to contain items of type set::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 set<Widget, less<Widget>, MemoryPool> WidgetSet;    // Delare your WidgetSet type.
	///     MemoryPool myPool(sizeof(WidgetSet::node_type), 100);       // Make a pool of 100 Widget nodes.
	///     WidgetSet mySet(&myPool);                                   // Create a map that uses the pool.
	///
	template <typename Key, typename Compare = eastl::less<Key>, typename Allocator = EASTLAllocatorType>
	class set
		: public rbtree<Key, Key, Compare, Allocator, eastl::useSelf<Key>, false, true>
	{
	public:
		typedef rbtree<Key, Key, Compare, Allocator, eastl::useSelf<Key>, false, true> base_type;
		typedef set<Key, Compare, Allocator>                                            this_type;
		typedef typename base_type::size_type                                           size_type;
		typedef typename base_type::value_type                                          value_type;
		typedef typename base_type::iterator                                            iterator;
		typedef typename base_type::const_iterator                                      const_iterator;
		typedef typename base_type::reverse_iterator                                    reverse_iterator;
		typedef typename base_type::const_reverse_iterator                              const_reverse_iterator;
		typedef typename base_type::allocator_type                                      allocator_type;
		typedef Compare                                                                 value_compare;
		// 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;

	protected:
		using base_type::compare;
		using base_type::get_compare;

	public:
		set(const allocator_type& allocator = EASTL_SET_DEFAULT_ALLOCATOR);
		set(const Compare& compare, const allocator_type& allocator = EASTL_SET_DEFAULT_ALLOCATOR);
		set(const this_type& x);
		set(this_type&& x);
		set(this_type&& x, const allocator_type& allocator);
		set(std::initializer_list<value_type> ilist, const Compare& compare = Compare(), const allocator_type& allocator = EASTL_SET_DEFAULT_ALLOCATOR);

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

		// 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)); }

	public:
		value_compare value_comp() const;

		size_type erase(const Key& k);
		iterator  erase(const_iterator position);
		iterator  erase(const_iterator first, const_iterator last);

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

		size_type count(const Key& k) const;

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

	}; // set





	/// multiset
	///
	/// Implements a canonical multiset.
	///
	/// 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.
	///
	/// See notes above in 'set' regarding multable iterators.
	///
	/// Pool allocation
	/// If you want to make a custom memory pool for a multiset container, your pool 
	/// needs to contain items of type multiset::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 multiset<Widget, less<Widget>, MemoryPool> WidgetSet;   // Delare your WidgetSet type.
	///     MemoryPool myPool(sizeof(WidgetSet::node_type), 100);           // Make a pool of 100 Widget nodes.
	///     WidgetSet mySet(&myPool);                                       // Create a map that uses the pool.
	///
	template <typename Key, typename Compare = eastl::less<Key>, typename Allocator = EASTLAllocatorType>
	class multiset
		: public rbtree<Key, Key, Compare, Allocator, eastl::useSelf<Key>, false, false>
	{
	public:
		typedef rbtree<Key, Key, Compare, Allocator, eastl::useSelf<Key>, false, false>    base_type;
		typedef multiset<Key, Compare, Allocator>                                           this_type;
		typedef typename base_type::size_type                                               size_type;
		typedef typename base_type::value_type                                              value_type;
		typedef typename base_type::iterator                                                iterator;
		typedef typename base_type::const_iterator                                          const_iterator;
		typedef typename base_type::reverse_iterator                                        reverse_iterator;
		typedef typename base_type::const_reverse_iterator                                  const_reverse_iterator;
		typedef typename base_type::allocator_type                                          allocator_type;
		typedef Compare                                                                     value_compare;
		// 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;

	protected:
		using base_type::compare;
		using base_type::get_compare;

	public:
		multiset(const allocator_type& allocator = EASTL_MULTISET_DEFAULT_ALLOCATOR);
		multiset(const Compare& compare, const allocator_type& allocator = EASTL_MULTISET_DEFAULT_ALLOCATOR);
		multiset(const this_type& x);
		multiset(this_type&& x);
		multiset(this_type&& x, const allocator_type& allocator);
		multiset(std::initializer_list<value_type> ilist, const Compare& compare = Compare(), const allocator_type& allocator = EASTL_MULTISET_DEFAULT_ALLOCATOR);

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

		// 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)); }

	public:
		value_compare value_comp() const;

		size_type erase(const Key& k);
		iterator  erase(const_iterator position);
		iterator  erase(const_iterator first, const_iterator last);

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

		size_type count(const Key& k) const;

		eastl::pair<iterator, iterator>             equalRange(const Key& k);
		eastl::pair<const_iterator, const_iterator> equalRange(const Key& k) 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& k);
		eastl::pair<const_iterator, const_iterator> equalRange_small(const Key& k) const;

	}; // multiset





	///////////////////////////////////////////////////////////////////////
	// set
	///////////////////////////////////////////////////////////////////////

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


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


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


	template <typename Key, typename Compare, typename Allocator>
	inline set<Key, Compare, Allocator>::set(this_type&& x)
		: base_type(eastl::move(x))
	{
	}

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


	template <typename Key, typename Compare, typename Allocator>
	inline set<Key, Compare, Allocator>::set(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 Compare, typename Allocator>
	template <typename Iterator>
	inline set<Key, Compare, Allocator>::set(Iterator itBegin, Iterator itEnd)
		: base_type(itBegin, itEnd, Compare(), EASTL_SET_DEFAULT_ALLOCATOR)
	{
	}


	template <typename Key, typename Compare, typename Allocator>
	inline typename set<Key, Compare, Allocator>::value_compare
	set<Key, Compare, Allocator>::value_comp() const
	{
		return get_compare();
	}


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

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


	template <typename Key, typename Compare, typename Allocator>
	inline typename set<Key, Compare, Allocator>::iterator
	set<Key, Compare, Allocator>::erase(const_iterator position)
	{
		// We need to provide this version because we override another version 
		// and C++ hiding rules would make the base version of this hidden.
		return base_type::erase(position);
	}


	template <typename Key, typename Compare, typename Allocator>
	inline typename set<Key, Compare, Allocator>::iterator
	set<Key, Compare, Allocator>::erase(const_iterator first, const_iterator last)
	{
		// We need to provide this version because we override another version 
		// and C++ hiding rules would make the base version of this hidden.
		return base_type::erase(first, last);
	}


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


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


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

		// Version which erases in order from last to first, but is slightly more efficient:
		return reverse_iterator(erase((++last).base(), (++first).base()));
	}


	template <typename Key, typename Compare, typename Allocator>
	inline eastl::pair<typename set<Key, Compare, Allocator>::iterator,
					   typename set<Key, Compare, Allocator>::iterator>
	set<Key, Compare, Allocator>::equalRange(const Key& k)
	{
		// 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(k));

		if((itLower == end()) || compare(k, *itLower)) // If at the end or if (k is < itLower)...
			return eastl::pair<iterator, iterator>(itLower, itLower);

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

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

		if((itLower == end()) || compare(k, *itLower)) // If at the end or if (k is < itLower)...
			return eastl::pair<const_iterator, const_iterator>(itLower, itLower);

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


	///////////////////////////////////////////////////////////////////////
	// erase_if 
	//
	// https://en.cppreference.com/w/cpp/container/set/erase_if
	///////////////////////////////////////////////////////////////////////
	template <class Key, class Compare, class Allocator, class Predicate>
	typename set<Key, Compare, Allocator>::size_type erase_if(set<Key, Compare, Allocator>& c, Predicate predicate)
	{
		auto oldSize = c.size();
		for (auto i = c.begin(), last = c.end(); i != last;)
		{
			if (predicate(*i))
			{
				i = c.erase(i);
			}
			else
			{
				++i;
			}
		}
		return oldSize - c.size();
	}

#if defined(EA_COMPILER_HAS_THREE_WAY_COMPARISON)
	template <class Key, class Compare, class Allocator>
	synth_three_way_result<Key> operator<=>(const set<Key, Compare, Allocator>& a, const set<Key, Compare, Allocator>& b)
	{
	    return eastl::lexicographicalCompare_three_way(a.begin(), a.end(), b.begin(), b.end(), synth_three_way{});
	}
#endif


	///////////////////////////////////////////////////////////////////////
	// multiset
	///////////////////////////////////////////////////////////////////////

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


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


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


	template <typename Key, typename Compare, typename Allocator>
	inline multiset<Key, Compare, Allocator>::multiset(this_type&& x)
		: base_type(eastl::move(x))
	{
	}

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


	template <typename Key, typename Compare, typename Allocator>
	inline multiset<Key, Compare, Allocator>::multiset(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 Compare, typename Allocator>
	template <typename Iterator>
	inline multiset<Key, Compare, Allocator>::multiset(Iterator itBegin, Iterator itEnd)
		: base_type(itBegin, itEnd, Compare(), EASTL_MULTISET_DEFAULT_ALLOCATOR)
	{
	}


	template <typename Key, typename Compare, typename Allocator>
	inline typename multiset<Key, Compare, Allocator>::value_compare
	multiset<Key, Compare, Allocator>::value_comp() const
	{
		return get_compare();
	}


	template <typename Key, typename Compare, typename Allocator>
	inline typename multiset<Key, Compare, Allocator>::size_type
	multiset<Key, Compare, Allocator>::erase(const Key& k)
	{
		const eastl::pair<iterator, iterator> range(equalRange(k));
		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 Compare, typename Allocator>
	inline typename multiset<Key, Compare, Allocator>::iterator
	multiset<Key, Compare, Allocator>::erase(const_iterator position)
	{
		// We need to provide this version because we override another version 
		// and C++ hiding rules would make the base version of this hidden.
		return base_type::erase(position);
	}


	template <typename Key, typename Compare, typename Allocator>
	inline typename multiset<Key, Compare, Allocator>::iterator
	multiset<Key, Compare, Allocator>::erase(const_iterator first, const_iterator last)
	{
		// We need to provide this version because we override another version 
		// and C++ hiding rules would make the base version of this hidden.
		return base_type::erase(first, last);
	}


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


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


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

		// Version which erases in order from last to first, but is slightly more efficient:
		return reverse_iterator(erase((++last).base(), (++first).base()));
	}


	template <typename Key, typename Compare, typename Allocator>
	inline eastl::pair<typename multiset<Key, Compare, Allocator>::iterator,
					   typename multiset<Key, Compare, Allocator>::iterator>
	multiset<Key, Compare, Allocator>::equalRange(const Key& k)
	{
		// 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(k), upperBound(k));
		//
		// 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(k), upperBound(k));
	}


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


	template <typename Key, typename Compare, typename Allocator>
	inline eastl::pair<typename multiset<Key, Compare, Allocator>::iterator,
					   typename multiset<Key, Compare, Allocator>::iterator>
	multiset<Key, Compare, Allocator>::equalRange_small(const Key& k)
	{
		// 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(k));
		iterator       itUpper(itLower);

		while((itUpper != end()) && !compare(k, *itUpper))
			++itUpper;

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


	template <typename Key, typename Compare, typename Allocator>
	inline eastl::pair<typename multiset<Key, Compare, Allocator>::const_iterator, 
					   typename multiset<Key, Compare, Allocator>::const_iterator>
	multiset<Key, Compare, Allocator>::equalRange_small(const Key& k) 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(k));
		const_iterator       itUpper(itLower);

		while((itUpper != end()) && !compare(k, *itUpper))
			++itUpper;

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


	///////////////////////////////////////////////////////////////////////
	// erase_if
	//
	// https://en.cppreference.com/w/cpp/container/multiset/erase_if
	///////////////////////////////////////////////////////////////////////
	template <class Key, class Compare, class Allocator, class Predicate>
	typename multiset<Key, Compare, Allocator>::size_type erase_if(multiset<Key, Compare, Allocator>& c, Predicate predicate)
	{
		auto oldSize = c.size();
		// Erases all elements that satisfy the predicate pred from the container.
		for (auto i = c.begin(), last = c.end(); i != last;)
		{
			if (predicate(*i))
			{
				i = c.erase(i);
			}
			else
			{
				++i;
			}
		}
		return oldSize - c.size();
	}

#if defined(EA_COMPILER_HAS_THREE_WAY_COMPARISON)
	template <class Key, class Compare, class Allocator>
	synth_three_way_result<Key> operator<=>(const multiset<Key, Compare, Allocator>& a, const multiset<Key, Compare, Allocator>& b)
	{
	    return eastl::lexicographicalCompare_three_way(a.begin(), a.end(), b.begin(), b.end(), synth_three_way{});
	}
#endif


} // namespace eastl


#endif // Header include guard