//modified for KDE:  enum _Redbl {_Red, _Black};
//  need to cast the enum to be a char in == comparisons otherwise the
//  compiler can't choose between char/int builtin and a Qt type (QChar)
//  that could also take the value of the enum

// xtree internal header
#ifndef _XTREE_
#define _XTREE_
#include <functional>
#include <memory>
#include <stdexcept>

namespace std {

		// TEMPLATE CLASS _Tree_nod
template<class _Traits>
	class _Tree_nod
		: public _Traits	// traits form ultimate base
	{	// base class for _Tree_ptr to hold allocator _Alnod
protected:
	typedef typename _Traits::allocator_type allocator_type;
	typedef typename _Traits::key_compare key_compare;
	typedef typename _Traits::value_type value_type;
	typedef typename allocator_type::template
		rebind<void>::other::pointer _Genptr;	// generic node pointer

	struct _Node;
	friend struct _Node;
	struct _Node
		{	// tree node
		_Genptr _Left;	// left subtree, or smallest element if head
		_Genptr _Parent;	// parent, or root of tree if head
		_Genptr _Right;	// right subtree, or largest element if head
		value_type _Myval;	// the stored value, unused if head
		char _Color;	// _Red or _Black, _Black if head
		char _Isnil;	// true only if head (also nil) node
		};

	_Tree_nod(const key_compare& _Parg,
		allocator_type _Al)
		: _Traits(_Parg), _Alnod(_Al)
		{}	// construct traits from _Parg and allocator from _Al

	typename allocator_type::template rebind<_Node>::other
		_Alnod;	// allocator object for nodes
	};

		// TEMPLATE CLASS _Tree_ptr
template<class _Traits>
	class _Tree_ptr
		: public _Tree_nod<_Traits>
	{	// base class for _Tree_val to hold allocator _Alptr
protected:
	typedef typename _Tree_nod<_Traits>::_Node _Node;
	typedef typename _Traits::allocator_type allocator_type;
	typedef typename _Traits::key_compare key_compare;
	typedef typename allocator_type::template
		rebind<_Node>::other::pointer _Nodeptr;

	_Tree_ptr(const key_compare& _Parg,
		allocator_type _Al)
		: _Tree_nod<_Traits>(_Parg, _Al), _Alptr(_Al)
		{}	// construct base, and allocator from _Al

	typename allocator_type::template rebind<_Nodeptr>::other
		_Alptr;	// allocator object for pointers to nodes
	};

		// TEMPLATE CLASS _Tree_val
template<class _Traits>
	class _Tree_val
		: public _Tree_ptr<_Traits>
	{	// base class for _Tree to hold allocator _Alval
protected:
	typedef typename _Traits::allocator_type allocator_type;
	typedef typename _Traits::key_compare key_compare;

	_Tree_val(const key_compare& _Parg,
		allocator_type _Al)
		: _Tree_ptr<_Traits>(_Parg, _Al), _Alval(_Al)
		{}	// construct base, and allocator from _Al

	allocator_type _Alval;	// allocator object for values stored in nodes
	};

		// TEMPLATE CLASS _Tree
template<class _Traits>
	class _Tree
		: public _Tree_val<_Traits>
	{	// ordered red-black tree for [multi_]{map set}
public:
	typedef _Tree<_Traits> _Myt;
	typedef _Tree_val<_Traits> _Mybase;
	typedef typename _Traits::key_type key_type;
	typedef typename _Traits::key_compare key_compare;
	typedef typename _Traits::value_compare value_compare;
	typedef typename _Traits::value_type value_type;
	typedef typename _Traits::allocator_type allocator_type;
	typedef typename _Traits::_ITptr _ITptr;
	typedef typename _Traits::_IReft _IReft;

protected:
	typedef typename _Tree_nod<_Traits>::_Genptr _Genptr;
	typedef typename _Tree_nod<_Traits>::_Node _Node;

	enum _Redbl
		{	// colors for link to parent
		_Red, _Black};
	typedef _POINTER_X(_Node, allocator_type) _Nodeptr;
	typedef _REFERENCE_X(_Nodeptr, allocator_type) _Nodepref;
	typedef _CREFERENCE_X(key_type, allocator_type) _Keyref;
	typedef _REFERENCE_X(char, allocator_type) _Charref;
	typedef _REFERENCE_X(value_type, allocator_type) _Vref;

	static _Charref _Color(_Nodeptr _Pnode)
		{	// return reference to color in node
		return ((_Charref)(*_Pnode)._Color); }

	static _Charref _Isnil(_Nodeptr _Pnode)
		{	// return reference to nil flag in node
		return ((_Charref)(*_Pnode)._Isnil); }

	static _Keyref _Key(_Nodeptr _Pnode)
		{	// return reference to key in node
		return (_Kfn()(_Myval(_Pnode))); }

	static _Nodepref _Left(_Nodeptr _Pnode)
		{	// return reference to left pointer in node
		return ((_Nodepref)(*_Pnode)._Left); }

	static _Nodepref _Parent(_Nodeptr _Pnode)
		{	// return reference to parent pointer in node
		return ((_Nodepref)(*_Pnode)._Parent); }

	static _Nodepref _Right(_Nodeptr _Pnode)
		{	// return reference to right pointer in node
		return ((_Nodepref)(*_Pnode)._Right); }

	static _Vref _Myval(_Nodeptr _Pnode)
		{	// return reference to value in node
		return ((_Vref)(*_Pnode)._Myval); }

public:
	typedef typename allocator_type::size_type size_type;
	typedef typename allocator_type::difference_type _Dift;
	typedef _Dift difference_type;
	typedef _POINTER_X(value_type, allocator_type) _Tptr;
	typedef _CPOINTER_X(value_type, allocator_type) _Ctptr;
	typedef _REFERENCE_X(value_type, allocator_type) _Reft;
	typedef _Tptr pointer;
	typedef _Ctptr const_pointer;
	typedef _Reft reference;
	typedef _CREFERENCE_X(value_type, allocator_type)
		const_reference;

		// CLASS const_iterator
	class const_iterator;
	friend class const_iterator;

	class const_iterator
		: public _Bidit<value_type, _Dift, _Ctptr, const_reference>
	{	// iterator for nonmutable _Tree
	public:
		typedef bidirectional_iterator_tag iterator_category;
		typedef _Dift difference_type;
		typedef _Ctptr pointer;
		typedef const_reference reference;

		const_iterator()
			: _Ptr(0)
			{}	// construct with null node pointer

		const_iterator(_Nodeptr _Pnode)
			: _Ptr(_Pnode)
			{}	// construct with node pointer _Pnode

		const_reference operator*() const
			{	// return designated value
			return (_Myval(_Ptr)); }

		_Ctptr operator->() const
			{	// return pointer to class object
			return (&**this); }

		const_iterator& operator++()
			{	// preincrement
			_Inc();
			return (*this); }

		const_iterator operator++(int)
			{	// postincrement
			const_iterator _Tmp = *this;
			++*this;
			return (_Tmp); }

		const_iterator& operator--()
			{	// predecrement
			_Dec();
			return (*this); }

		const_iterator operator--(int)
			{	// postdecrement
			const_iterator _Tmp = *this;
			--*this;
			return (_Tmp); }

		bool operator==(const const_iterator& _Right) const
			{	// test for iterator equality
			return (_Ptr == _Right._Ptr); }

		bool operator!=(const const_iterator& _Right) const
			{	// test for iterator inequality
			return (!(*this == _Right)); }

		void _Dec()
			{	// move to node with next smaller value
			if (_Isnil(_Ptr))
				_Ptr = _Right(_Ptr);	// end() ==> rightmost
			else if (!_Isnil(_Left(_Ptr)))
				_Ptr = _Max(_Left(_Ptr));	// ==> largest of left subtree
			else
				{	// climb looking for left subtree
				_Nodeptr _Pnode;
				while (!_Isnil(_Pnode = _Parent(_Ptr))
					&& _Ptr == _Left(_Pnode))
					_Ptr = _Pnode;	// ==> parent while left subtree
				if (!_Isnil(_Pnode))
					_Ptr = _Pnode; }}	// ==> parent if not head

		void _Inc()
			{	// move to node with next larger value
			if (_Isnil(_Ptr))
				;	// end() shouldn't be incremented, don't move
			else if (!_Isnil(_Right(_Ptr)))
				_Ptr = _Min(_Right(_Ptr));	// ==> smallest of right subtree
			else
				{	// climb looking for right subtree
				_Nodeptr _Pnode;
				while (!_Isnil(_Pnode = _Parent(_Ptr))
					&& _Ptr == _Right(_Pnode))
					_Ptr = _Pnode;	// ==> parent while right subtree
				_Ptr = _Pnode; }}	// ==> parent (head if end())

		_Nodeptr _Mynode() const
			{	// return node pointer
			return (_Ptr); }

	protected:
		_Nodeptr _Ptr;	// pointer to node
		};

		// CLASS iterator
	class iterator;
	friend class iterator;

	class iterator
		: public const_iterator
	{	// iterator for mutable _Tree
	public:
		typedef bidirectional_iterator_tag iterator_category;
		typedef _Dift difference_type;
		typedef _ITptr pointer;
		typedef _IReft reference;

		iterator()
			: const_iterator(0)
			{}	// construct with null node pointer

		iterator(_Nodeptr _Pnode)
			: const_iterator(_Pnode)
			{}	// construct with node pointer _Pnode

		reference operator*() const
			{	// return designated value
			return (_Myval(_Ptr)); }

		pointer operator->() const
			{	// return pointer to class object
			return (&**this); }

		iterator& operator++()
			{	// preincrement
			_Inc();
			return (*this); }

		iterator operator++(int)
			{	// postincrement
			iterator _Tmp = *this;
			++*this;
			return (_Tmp); }

		iterator& operator--()
			{	// predecrement
			_Dec();
			return (*this); }

		iterator operator--(int)
			{	// postdecrement
			iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		};

	typedef std::reverse_iterator<iterator> reverse_iterator;
	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
	typedef pair<iterator, bool> _Pairib;
	typedef pair<iterator, iterator> _Pairii;
	typedef pair<const_iterator, const_iterator> _Paircc;

	explicit _Tree(const key_compare& _Parg,
		const allocator_type& _Al)
		: _Mybase(_Parg, _Al)
		{	// construct empty tree
		_Init(); }

	_Tree(const value_type *_First, const value_type *_Last,
		const key_compare& _Parg, const allocator_type& _Al)
		: _Mybase(_Parg, _Al)
		{	// construct tree from [_First, _Last) array
		_Init();
		insert(_First, _Last); }

	_Tree(const _Myt& _Right)
		: _Mybase(_Right.key_comp(), _Right.get_allocator())
		{	// construct tree by copying _Right
		_Init();
		_Copy(_Right); }

	~_Tree()
		{	// destroy tree
		erase(begin(), end());
		_Freenode(_Myhead);
		_Myhead = 0, _Mysize = 0; }

	_Myt& operator=(const _Myt& _Right)
		{	// replace contents from _Right
		if (this != &_Right)
			{	// worth doing
			erase(begin(), end());
			comp = _Right.comp;
			_Copy(_Right); }
		return (*this); }

	iterator begin()
		{	// return iterator for beginning of mutable sequence
		return (iterator(_Lmost())); }

	const_iterator begin() const
		{	// return iterator for beginning of nonmutable sequence
		return (const_iterator(_Lmost())); }

	iterator end()
		{	// return iterator for end of mutable sequence
		return (iterator(_Myhead)); }

	const_iterator end() const
		{	// return iterator for end of nonmutable sequence
		return (const_iterator(_Myhead)); }

	reverse_iterator rbegin()
		{	// return iterator for beginning of reversed mutable sequence
		return (reverse_iterator(end())); }

	const_reverse_iterator rbegin() const
		{	// return iterator for beginning of reversed nonmutable sequence
		return (const_reverse_iterator(end())); }

	reverse_iterator rend()
		{	// return iterator for end of reversed mutable sequence
		return (reverse_iterator(begin())); }

	const_reverse_iterator rend() const
		{	// return iterator for end of reversed nonmutable sequence
		return (const_reverse_iterator(begin())); }

	size_type size() const
		{	// return length of sequence
		return (_Mysize); }

	size_type max_size() const
		{	// return maximum possible length of sequence
		return (_Alval.max_size()); }

	bool empty() const
		{	// return true only if sequence is empty
		return (size() == 0); }

	allocator_type get_allocator() const
		{	// return allocator object for values
		return (_Alval); }

	key_compare key_comp() const
		{	// return object for comparing keys
		return (comp); }

	value_compare value_comp() const
		{	// return object for comparing values
		return (value_compare(key_comp())); }

	_Pairib insert(const value_type& _Val)
		{	// try to insert node with value _Val
		_Nodeptr _Trynode = _Root();
		_Nodeptr _Wherenode = _Myhead;
		bool _Addleft = true;	// add to left of head if tree empty
		while (!_Isnil(_Trynode))
			{	// look for leaf to insert before (_Addleft) or after
			_Wherenode = _Trynode;
			_Addleft = comp(_Kfn()(_Val), _Key(_Trynode));
			_Trynode = _Addleft ? _Left(_Trynode) : _Right(_Trynode); }

		if (_Multi)
			return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
		else
			{	// insert only if unique
			iterator _Where = iterator(_Wherenode);
			if (!_Addleft)
				;	// need to test if insert after is okay
			else if (_Where == begin())
				return (_Pairib(_Insert(true, _Wherenode, _Val), true));
			else
				--_Where;	// need to test if insert before is okay

			if (comp(_Key(_Where._Mynode()), _Kfn()(_Val)))
				return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
			else
				return (_Pairib(_Where, false)); }}

	iterator insert(iterator _Where, const value_type& _Val)
		{	// try to insert node with value _Val using _Where as a hint
		if (size() == 0)
			return (_Insert(true, _Myhead, _Val));	// insert into empty tree
		else if (_Multi)
			{	// insert even if duplicate
			if (_Where == begin())
				{	// insert at beginning if before first element
				if (!comp(_Key(_Where._Mynode()), _Kfn()(_Val)))
					return (_Insert(true, _Where._Mynode(), _Val)); }
			else if (_Where == end())
				{	// insert at end if after last element
				if (!comp(_Kfn()(_Val), _Key(_Rmost())))
					return (_Insert(false, _Rmost(), _Val)); }
			else
				{	// insert after or before _Where if in order
				iterator _Before = _Where;
				if ((comp(_Kfn()(_Val), _Key((_Before)._Mynode()))
						|| comp(_Key(_Where._Mynode()), _Kfn()(_Val)))
					&& (comp(_Kfn()(_Val), _Key((--_Before)._Mynode()))
						|| comp(_Key(_Where._Mynode()), _Kfn()(_Val))))
					;	// after and before don't meet ordering requirements
				else if (_Isnil(_Right(_Before._Mynode())))
					return (_Insert(false, _Before._Mynode(), _Val));
				else
					return (_Insert(true, _Where._Mynode(), _Val)); }}
		else
			{	// insert only if unique
			if (_Where == begin())
				{	// insert at beginning if before first element
				if (comp(_Kfn()(_Val), _Key(_Where._Mynode())))
					return (_Insert(true, _Where._Mynode(), _Val)); }
			else if (_Where == end())
				{	// insert at end if after last element
				if (comp(_Key(_Rmost()), _Kfn()(_Val)))
					return (_Insert(false, _Rmost(), _Val)); }
			else
				{	// insert before _Where if in order
				iterator _Before = _Where;
				if (!comp(_Key((--_Before)._Mynode()), _Kfn()(_Val))
					|| !comp(_Kfn()(_Val), _Key(_Where._Mynode())))
					;	// doesn't meet ordering requirements
				else if (_Isnil(_Right(_Before._Mynode())))
					return (_Insert(false, _Before._Mynode(), _Val));
				else
					return (_Insert(true, _Where._Mynode(), _Val)); }}

		return (insert(_Val).first); }	// try usual insert if all else fails

	template<class _Iter>
		void insert(_Iter _First, _Iter _Last)
		{	// insert [_First, _Last) one at a time
		for (; _First != _Last; ++_First)
			insert(*_First); }

	iterator erase(iterator _Where)
		{	// erase element at _Where
		if (_Isnil(_Where._Mynode()))
			throw out_of_range("invalid map/set<T> iterator");
		_Nodeptr _Fixnode;	// the node to recolor as needed
		_Nodeptr _Fixnodeparent;	// parent of _Fixnode (which may be nil)
		_Nodeptr _Erasednode = _Where._Mynode();	// node to erase
		_Nodeptr _Pnode = _Erasednode;
		++_Where;	// save successor iterator for return

		if (_Isnil(_Left(_Pnode)))
			_Fixnode = _Right(_Pnode);	// must stitch up right subtree
		else if (_Isnil(_Right(_Pnode)))
			_Fixnode = _Left(_Pnode);	// must stitch up left subtree
		else
			{	// two subtrees, must lift successor node to replace erased
			_Pnode = _Where._Mynode();	// _Pnode is successor node
			_Fixnode = _Right(_Pnode); }	// _Fixnode is its only subtree

		if (_Pnode == _Erasednode)
			{	// at most one subtree, relink it
			_Fixnodeparent = _Parent(_Erasednode);
			if (!_Isnil(_Fixnode))
				_Parent(_Fixnode) = _Fixnodeparent;	// link up

			if (_Root() == _Erasednode)
				_Root() = _Fixnode;	// link down from root
			else if (_Left(_Fixnodeparent) == _Erasednode)
				_Left(_Fixnodeparent) = _Fixnode;	// link down to left
			else
				_Right(_Fixnodeparent) = _Fixnode;	// link down to right

			if (_Lmost() == _Erasednode)
				_Lmost() = _Isnil(_Fixnode)
					? _Fixnodeparent	// smallest is parent of erased node
					: _Min(_Fixnode);	// smallest in relinked subtree

			if (_Rmost() == _Erasednode)
				_Rmost() = _Isnil(_Fixnode)
					? _Fixnodeparent	// largest is parent of erased node
					: _Max(_Fixnode); }	// largest in relinked subtree
		else
			{	// erased has two subtrees, _Pnode is successor to erased
			_Parent(_Left(_Erasednode)) = _Pnode;	// link left up
			_Left(_Pnode) = _Left(_Erasednode);	// link successor down

			if (_Pnode == _Right(_Erasednode))
				_Fixnodeparent = _Pnode;	// successor is next to erased
			else
				{	// successor further down, link in place of erased
				_Fixnodeparent = _Parent(_Pnode);	// parent is successor's
				if (!_Isnil(_Fixnode))
					_Parent(_Fixnode) = _Fixnodeparent;	// link fix up
				_Left(_Fixnodeparent) = _Fixnode;	// link fix down
				_Right(_Pnode) = _Right(_Erasednode);	// link successor down
				_Parent(_Right(_Erasednode)) = _Pnode; }	// link right up

			if (_Root() == _Erasednode)
				_Root() = _Pnode;	// link down from root
			else if (_Left(_Parent(_Erasednode)) == _Erasednode)
				_Left(_Parent(_Erasednode)) = _Pnode;	// link down to left
			else
				_Right(_Parent(_Erasednode)) = _Pnode;	// link down to right

			_Parent(_Pnode) = _Parent(_Erasednode);	// link successor up
			std::swap(_Color(_Pnode), _Color(_Erasednode)); }	// recolor it

		if (_Color(_Erasednode) == (char) _Black)
			{	// erasing black link, must recolor/rebalance tree
			for (; _Fixnode != _Root() && _Color(_Fixnode) == (char) _Black;
				_Fixnodeparent = _Parent(_Fixnode))
				if (_Fixnode == _Left(_Fixnodeparent))
					{	// fixup left subtree
					_Pnode = _Right(_Fixnodeparent);
					if (_Color(_Pnode) == (char) _Red)
						{	// rotate red up from right subtree
						_Color(_Pnode) = _Black;
						_Color(_Fixnodeparent) = _Red;
						_Lrotate(_Fixnodeparent);
						_Pnode = _Right(_Fixnodeparent); }

					if (_Isnil(_Pnode))
						_Fixnode = _Fixnodeparent;	// shouldn't happen
					else if (_Color(_Left(_Pnode)) == (char) _Black
						&& _Color(_Right(_Pnode)) == (char) _Black)
						{	// redden right subtree with black children
						_Color(_Pnode) = _Red;
						_Fixnode = _Fixnodeparent; }
					else
						{	// must rearrange right subtree
						if (_Color(_Right(_Pnode)) == (char) _Black)
							{	// rotate red up from left sub-subtree
							_Color(_Left(_Pnode)) = _Black;
							_Color(_Pnode) = _Red;
							_Rrotate(_Pnode);
							_Pnode = _Right(_Fixnodeparent); }

						_Color(_Pnode) = _Color(_Fixnodeparent);
						_Color(_Fixnodeparent) = _Black;
						_Color(_Right(_Pnode)) = _Black;
						_Lrotate(_Fixnodeparent);
						break; }}	// tree now recolored/rebalanced
				else
					{	// fixup right subtree
					_Pnode = _Left(_Fixnodeparent);
					if (_Color(_Pnode) == (char) _Red)
						{	// rotate red up from left subtree
						_Color(_Pnode) = _Black;
						_Color(_Fixnodeparent) = _Red;
						_Rrotate(_Fixnodeparent);
						_Pnode = _Left(_Fixnodeparent); }
					if (_Isnil(_Pnode))
						_Fixnode = _Fixnodeparent;	// shouldn't happen
					else if (_Color(_Right(_Pnode)) == (char) _Black
						&& _Color(_Left(_Pnode)) == (char) _Black)
						{	// redden left subtree with black children
						_Color(_Pnode) = _Red;
						_Fixnode = _Fixnodeparent; }
					else
						{	// must rearrange left subtree
						if (_Color(_Left(_Pnode)) == (char) _Black)
							{	// rotate red up from right sub-subtree
							_Color(_Right(_Pnode)) = _Black;
							_Color(_Pnode) = _Red;
							_Lrotate(_Pnode);
							_Pnode = _Left(_Fixnodeparent); }

						_Color(_Pnode) = _Color(_Fixnodeparent);
						_Color(_Fixnodeparent) = _Black;
						_Color(_Left(_Pnode)) = _Black;
						_Rrotate(_Fixnodeparent);
						break; }}	// tree now recolored/rebalanced

			_Color(_Fixnode) = _Black; }	// ensure stopping node is black

		_Destval(&_Myval(_Erasednode));	// destroy and free erased node
		_Freenode(_Erasednode);
		if (0 < _Mysize)
			--_Mysize;

		return (_Where); }	// return successor iterator

	iterator erase(iterator _First, iterator _Last)
		{	// erase [_First, _Last)
		if (_First == begin() && _Last == end())
			{	// erase all
			clear();
			return (begin()); }
		else
			{	// partial erase, one at a time
			while (_First != _Last)
				erase(_First++);
			return (_First); }}

	size_type erase(const key_type& _Keyval)
		{	// erase and count all that match _Keyval
		_Pairii _Where = equal_range(_Keyval);
		size_type _Num = 0;
		_Distance(_Where.first, _Where.second, _Num);
		erase(_Where.first, _Where.second);
		return (_Num); }

	void erase(const key_type *_First, const key_type *_Last)
		{	// erase all that match array of keys [_First, _Last)
		while (_First != _Last)
			erase(*_First++); }

	void clear()
		{	// erase all
		_Erase(_Root());
		_Root() = _Myhead, _Mysize = 0;
		_Lmost() = _Myhead, _Rmost() = _Myhead; }

	iterator find(const key_type& _Keyval)
		{	// find an element in mutable sequence that matches _Keyval
		iterator _Where = lower_bound(_Keyval);
		return (_Where == end() || comp(_Keyval, _Key(_Where._Mynode()))
			? end() : _Where); }

	const_iterator find(const key_type& _Keyval) const
		{	// find an element in nonmutable sequence that matches _Keyval
		const_iterator _Where = lower_bound(_Keyval);
		return (_Where == end() || comp(_Keyval, _Key(_Where._Mynode()))
			? end() : _Where); }

	size_type count(const key_type& _Keyval) const
		{	// count all elements that match _Keyval
		_Paircc _Ans = equal_range(_Keyval);
		size_type _Num = 0;
		_Distance(_Ans.first, _Ans.second, _Num);
		return (_Num); }

	iterator lower_bound(const key_type& _Keyval)
		{	// find leftmost node not less than _Keyval in mutable tree
		return (iterator(_Lbound(_Keyval))); }

	const_iterator lower_bound(const key_type& _Keyval) const
		{	// find leftmost node not less than _Keyval in nonmutable tree
		return (const_iterator(_Lbound(_Keyval))); }

	iterator upper_bound(const key_type& _Keyval)
		{	// find leftmost node greater than _Keyval in mutable tree
		return (iterator(_Ubound(_Keyval))); }

	const_iterator upper_bound(const key_type& _Keyval) const
		{	// find leftmost node greater than _Keyval in nonmutable tree
		return (const_iterator(_Ubound(_Keyval))); }

	_Pairii equal_range(const key_type& _Keyval)
		{	// find range equivalent to _Keyval in mutable tree
		return (_Pairii(lower_bound(_Keyval), upper_bound(_Keyval))); }

	_Paircc equal_range(const key_type& _Keyval) const
		{	// find range equivalent to _Keyval in nonmutable tree
		return (_Paircc(lower_bound(_Keyval), upper_bound(_Keyval))); }

	void swap(_Myt& _Right)
		{	// exchange contents with _Right
		if (get_allocator() == _Right.get_allocator())
			{	// same allocator, swap control information
			std::swap(comp, _Right.comp);
			std::swap(_Myhead, _Right._Myhead);
			std::swap(_Mysize, _Right._Mysize); }
		else
			{	// different allocator, do multiple assigns
			_Myt _Tmp = *this; *this = _Right, _Right = _Tmp; }}

protected:
	void _Copy(const _Myt& _Right)
		{	// copy entire tree from _Right
		_Root() = _Copy(_Right._Root(), _Myhead);
		_Mysize = _Right.size();
		if (!_Isnil(_Root()))
			{	// nonempty tree, look for new smallest and largest
			_Lmost() = _Min(_Root());
			_Rmost() = _Max(_Root()); }
		else
			_Lmost() = _Myhead, _Rmost() = _Myhead; }	// empty tree

	_Nodeptr _Copy(_Nodeptr _Rootnode, _Nodeptr _Wherenode)
		{	// copy entire subtree, recursively
		_Nodeptr _Newroot = _Myhead;	// point at nil node

		if (!_Isnil(_Rootnode))
			{	// copy a node, then any subtrees
			_Nodeptr _Pnode = _Buynode(_Wherenode, _Color(_Rootnode));

			try {
			_Consval(&_Myval(_Pnode), _Myval(_Rootnode));
			 } catch (...) {
			_Freenode(_Pnode);	// value constructor failed, bail out
			_Erase(_Newroot);
			throw;
			}

			_Left(_Pnode) = _Myhead;	// left subtree is nil
			_Right(_Pnode) = _Myhead;	// right subtree is nil
			if (_Isnil(_Newroot))
				_Newroot = _Pnode;	// memorize new root

			try {
			_Left(_Pnode) = _Copy(_Left(_Rootnode), _Pnode);
			_Right(_Pnode) = _Copy(_Right(_Rootnode), _Pnode);
			 } catch (...) {
			_Erase(_Newroot);	// subtree copy failed, bail out
			throw;
			}}

		return (_Newroot); }	// return newly constructed tree

	void _Erase(_Nodeptr _Rootnode)
		{	// free entire subtree, recursively
		for (_Nodeptr _Pnode = _Rootnode; !_Isnil(_Pnode); _Rootnode = _Pnode)
			{	// free subtrees, then node
			_Erase(_Right(_Pnode));
			_Pnode = _Left(_Pnode);
			_Destval(&_Myval(_Rootnode));
			_Freenode(_Rootnode); }}

	void _Init()
		{	// create head/nil node and make tree empty
		_Myhead = _Buynode(0, _Black);
		_Isnil(_Myhead) = true;
		_Root() = _Myhead;
		_Lmost() = _Myhead, _Rmost() = _Myhead;
		_Mysize = 0; }

	iterator _Insert(bool _Addleft, _Nodeptr _Wherenode,
		const value_type& _Val)
		{	// add node with value next to _Wherenode, to left if _Addnode
		if (max_size() - 1 <= _Mysize)
			throw length_error("map/set<T> too long");
		_Nodeptr _Newnode = _Buynode(_Wherenode, _Red);
		_Left(_Newnode) = _Myhead, _Right(_Newnode) = _Myhead;

		try {
		_Consval(&_Myval(_Newnode), _Val);
		 } catch (...) {
		_Freenode(_Newnode);	// value constructor failed, bail out
		throw;
		}

		++_Mysize;
		if (_Wherenode == _Myhead)
			{	// first node in tree, just set head values
			_Root() = _Newnode;
			_Lmost() = _Newnode, _Rmost() = _Newnode; }
		else if (_Addleft)
			{	// add to left of _Wherenode
			_Left(_Wherenode) = _Newnode;
			if (_Wherenode == _Lmost())
				_Lmost() = _Newnode; }
		else
			{	// add to right of _Wherenode
			_Right(_Wherenode) = _Newnode;
			if (_Wherenode == _Rmost())
				_Rmost() = _Newnode; }

		for (_Nodeptr _Pnode = _Newnode; _Color(_Parent(_Pnode)) == (char) _Red; )
			if (_Parent(_Pnode) == _Left(_Parent(_Parent(_Pnode))))
				{	// fixup red-red in left subtree
				_Wherenode = _Right(_Parent(_Parent(_Pnode)));
				if (_Color(_Wherenode) == (char) _Red)
					{	// parent has two red children, blacken both
					_Color(_Parent(_Pnode)) = _Black;
					_Color(_Wherenode) = _Black;
					_Color(_Parent(_Parent(_Pnode))) = _Red;
					_Pnode = _Parent(_Parent(_Pnode)); }
				else
					{	// parent has red and black children
					if (_Pnode == _Right(_Parent(_Pnode)))
						{	// rotate right child to left
						_Pnode = _Parent(_Pnode);
						_Lrotate(_Pnode); }
					_Color(_Parent(_Pnode)) = _Black;	// propagate red up
					_Color(_Parent(_Parent(_Pnode))) = _Red;
					_Rrotate(_Parent(_Parent(_Pnode))); }}
			else
				{	// fixup red-red in right subtree
				_Wherenode = _Left(_Parent(_Parent(_Pnode)));
				if (_Color(_Wherenode) == (char) _Red)
					{	// parent has two red children, blacken both
					_Color(_Parent(_Pnode)) = _Black;
					_Color(_Wherenode) = _Black;
					_Color(_Parent(_Parent(_Pnode))) = _Red;
					_Pnode = _Parent(_Parent(_Pnode)); }
				else
					{	// parent has red and black children
					if (_Pnode == _Left(_Parent(_Pnode)))
						{	// rotate left child to right
						_Pnode = _Parent(_Pnode);
						_Rrotate(_Pnode); }
					_Color(_Parent(_Pnode)) = _Black;	// propagate red up
					_Color(_Parent(_Parent(_Pnode))) = _Red;
					_Lrotate(_Parent(_Parent(_Pnode))); }}

		_Color(_Root()) = _Black;	// root is always black
		return (iterator(_Newnode)); }

	_Nodeptr _Lbound(const key_type& _Keyval) const
		{	// find leftmost node not less than _Keyval
		_Nodeptr _Pnode = _Root();
		_Nodeptr _Wherenode = _Myhead;	// end() if search fails

		while (!_Isnil(_Pnode))
			if (comp(_Key(_Pnode), _Keyval))
				_Pnode = _Right(_Pnode);	// descend right subtree
			else
				{	// _Pnode not less than _Keyval, remember it
				_Wherenode = _Pnode;
				_Pnode = _Left(_Pnode); }	// descend left subtree

		return (_Wherenode); }	// return best remembered candidate

	_Nodeptr& _Lmost()
		{	// return leftmost node in mutable tree
		return (_Left(_Myhead)); }

	_Nodeptr& _Lmost() const
		{	// return leftmost node in nonmutable tree
		return (_Left(_Myhead)); }

	void _Lrotate(_Nodeptr _Wherenode)
		{	// promote right node to root of subtree
		_Nodeptr _Pnode = _Right(_Wherenode);
		_Right(_Wherenode) = _Left(_Pnode);

		if (!_Isnil(_Left(_Pnode)))
			_Parent(_Left(_Pnode)) = _Wherenode;
		_Parent(_Pnode) = _Parent(_Wherenode);

		if (_Wherenode == _Root())
			_Root() = _Pnode;
		else if (_Wherenode == _Left(_Parent(_Wherenode)))
			_Left(_Parent(_Wherenode)) = _Pnode;
		else
			_Right(_Parent(_Wherenode)) = _Pnode;

		_Left(_Pnode) = _Wherenode;
		_Parent(_Wherenode) = _Pnode; }

	static _Nodeptr _Max(_Nodeptr _Pnode)
		{	// return rightmost node in subtree at _Pnode
		while (!_Isnil(_Right(_Pnode)))
			_Pnode = _Right(_Pnode);
		return (_Pnode); }

	static _Nodeptr _Min(_Nodeptr _Pnode)
		{	// return leftmost node in subtree at _Pnode
		while (!_Isnil(_Left(_Pnode)))
			_Pnode = _Left(_Pnode);
		return (_Pnode); }

	_Nodeptr& _Rmost()
		{	// return rightmost node in mutable tree
		return (_Right(_Myhead)); }

	_Nodeptr& _Rmost() const
		{	// return rightmost node in nonmutable tree
		return (_Right(_Myhead)); }

	_Nodeptr& _Root()
		{	// return root of mutable tree
		return (_Parent(_Myhead)); }

	_Nodeptr& _Root() const
		{	// return root of nonmutable tree
		return (_Parent(_Myhead)); }

	void _Rrotate(_Nodeptr _Wherenode)
		{	// promote left node to root of subtree
		_Nodeptr _Pnode = _Left(_Wherenode);
		_Left(_Wherenode) = _Right(_Pnode);

		if (!_Isnil(_Right(_Pnode)))
			_Parent(_Right(_Pnode)) = _Wherenode;
		_Parent(_Pnode) = _Parent(_Wherenode);

		if (_Wherenode == _Root())
			_Root() = _Pnode;
		else if (_Wherenode == _Right(_Parent(_Wherenode)))
			_Right(_Parent(_Wherenode)) = _Pnode;
		else
			_Left(_Parent(_Wherenode)) = _Pnode;

		_Right(_Pnode) = _Wherenode;
		_Parent(_Wherenode) = _Pnode; }

	_Nodeptr _Ubound(const key_type& _Keyval) const
		{	// find leftmost node greater than _Keyval
		_Nodeptr _Pnode = _Root();
		_Nodeptr _Wherenode = _Myhead;	// end() if search fails

		while (!_Isnil(_Pnode))
			if (comp(_Keyval, _Key(_Pnode)))
				{	// _Pnode greater than _Keyval, remember it
				_Wherenode = _Pnode;
				_Pnode = _Left(_Pnode); }	// descend left subtree
			else
				_Pnode = _Right(_Pnode);	// descend right subtree

		return (_Wherenode); }	// return best remembered candidate

	_Nodeptr _Buynode(_Nodeptr _Parg, char _Carg)
		{	// allocate a node with specified parent and color
		_Nodeptr _Wherenode = _Alnod.allocate(1, (void *)0);
		_Alptr.construct(&_Left(_Wherenode), 0);
		_Alptr.construct(&_Right(_Wherenode), 0);
		_Alptr.construct(&_Parent(_Wherenode), _Parg);
		_Color(_Wherenode) = _Carg;
		_Isnil(_Wherenode) = false;
		return (_Wherenode); }

	void _Consval(_Tptr _Pval, const value_type& _Val)
		{	// construct value within a node
		_Alval.construct(_Pval, _Val); }

	void _Freenode(_Nodeptr _Wherenode)
		{	// free a node
		_Alptr.destroy(&_Parent(_Wherenode));
		_Alptr.destroy(&_Right(_Wherenode));
		_Alptr.destroy(&_Left(_Wherenode));
		_Alnod.deallocate(_Wherenode, 1); }

	void _Destval(_Tptr _Pval)
		{	// destroy a value within a node
		_Alval.destroy(_Pval); }

	_Nodeptr _Myhead;	// pointer to head node
	size_type _Mysize;	// number of elements
	};

		// _Tree TEMPLATE OPERATORS
template<class _Traits> inline
	void swap(_Tree<_Traits>& _Left, _Tree<_Traits>& _Right)
	{	// swap _Left and _Right trees
	_Left.swap(_Right); }

template<class _Traits> inline
	bool operator==(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
	{	// test for _Tree equality
	return (_Left.size() == _Right.size()
		&& equal(_Left.begin(), _Left.end(), _Right.begin())); }

template<class _Traits> inline
	bool operator!=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
	{	// test for _Tree inequality
	return (!(_Left == _Right)); }

template<class _Traits> inline
	bool operator<(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
	{	// test if _Less < _Right for _Trees
	return (lexicographical_compare(_Left.begin(), _Left.end(),
		_Right.begin(), _Right.end(), _Left.value_comp())); }

template<class _Traits> inline
	bool operator>(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
	{	// test if _Less > _Right for _Trees
	return (_Right < _Left); }

template<class _Traits> inline
	bool operator<=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
	{	// test if _Less <= _Right for _Trees
	return (!(_Right < _Left)); }

template<class _Traits> inline
	bool operator>=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
	{	// test if _Less >= _Right for _Trees
	return (!(_Left < _Right)); }

}	// namespace std
#endif /* _XTREE_ */

/*
 * Copyright (c) 1995-2000 by P.J. Plauger.  ALL RIGHTS RESERVED. 
 * Consult your license regarding permissions and restrictions.
 */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
V3.01:0477 */
