xtree

C语言库函数的原型,有用的拿去

		}

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

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

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

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

	void swap(_Myt& _Right)
		{	// exchange contents with _Right
		if (this == &_Right)
			;	// same object, do nothing
		else if (get_allocator() == _Right.get_allocator())
			{	// same allocator, swap control information
			this->_Swap_all(_Right);
			_Swap_adl(this->comp, _Right.comp);
			_STD swap(this->_Myhead, _Right._Myhead);
			_STD swap(this->_Mysize, _Right._Mysize);
			}
		else
			{	// different allocator, do multiple assigns
			_Myt _Tmp = _Move(*this);

			*this = _Move(_Right);
			_Right = _Move(_Tmp);
			}
		}

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

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

		if (!this->_Isnil(_Rootnode))
			{	// copy a node, then any subtrees
			_Nodeptr _Pnode = this->_Buynode(this->_Myval(_Rootnode));
			_Pnode->_Parent = _Wherenode;
			_Pnode->_Color = this->_Color(_Rootnode);
			if (this->_Isnil(_Newroot))
				_Newroot = _Pnode;	// memorize new root

			_TRY_BEGIN
			this->_Left(_Pnode) = _Copy(this->_Left(_Rootnode), _Pnode);
			this->_Right(_Pnode) = _Copy(this->_Right(_Rootnode), _Pnode);
			_CATCH_ALL
			_Erase(_Newroot);	// subtree copy failed, bail out
			_RERAISE;
			_CATCH_END
			}

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

	_Paircc _Eqrange(const key_type& _Keyval) const
		{	// find leftmost node not less than _Keyval
		_Nodeptr _Pnode = _Root();
		_Nodeptr _Lonode = this->_Myhead;	// end() if search fails
		_Nodeptr _Hinode = this->_Myhead;	// end() if search fails

		while (!this->_Isnil(_Pnode))
			if (_DEBUG_LT_PRED(this->comp, this->_Key(_Pnode), _Keyval))
				_Pnode = this->_Right(_Pnode);	// descend right subtree
			else
				{	// _Pnode not less than _Keyval, remember it
				if (this->_Isnil(_Hinode)
						&& _DEBUG_LT_PRED(this->comp, _Keyval,
						this->_Key(_Pnode)))
					_Hinode = _Pnode;	// _Pnode greater, remember it
				_Lonode = _Pnode;
				_Pnode = this->_Left(_Pnode);	// descend left subtree
				}

		_Pnode = this->_Isnil(_Hinode) ? _Root()
			: this->_Left(_Hinode);	// continue scan for upper bound
		while (!this->_Isnil(_Pnode))
			if (_DEBUG_LT_PRED(this->comp, _Keyval, this->_Key(_Pnode)))
				{	// _Pnode greater than _Keyval, remember it
				_Hinode = _Pnode;
				_Pnode = this->_Left(_Pnode);	// descend left subtree
				}
			else
				_Pnode = this->_Right(_Pnode);	// descend right subtree

		const_iterator _First = const_iterator(_Lonode, this);
		const_iterator _Last = const_iterator(_Hinode, this);
		return (_Paircc(_First, _Last));
		}

	_Pairii _Eqrange(const key_type& _Keyval)
		{	// find leftmost node not less than _Keyval
		_Nodeptr _Pnode = _Root();
		_Nodeptr _Lonode = this->_Myhead;	// end() if search fails
		_Nodeptr _Hinode = this->_Myhead;	// end() if search fails

		while (!this->_Isnil(_Pnode))
			if (_DEBUG_LT_PRED(this->comp, this->_Key(_Pnode), _Keyval))
				_Pnode = this->_Right(_Pnode);	// descend right subtree
			else
				{	// _Pnode not less than _Keyval, remember it
				if (this->_Isnil(_Hinode)
						&& _DEBUG_LT_PRED(this->comp, _Keyval,
						 this->_Key(_Pnode)))
					_Hinode = _Pnode;	// _Pnode greater, remember it
				_Lonode = _Pnode;
				_Pnode = this->_Left(_Pnode);	// descend left subtree
				}

		_Pnode = this->_Isnil(_Hinode) ? _Root()
			: this->_Left(_Hinode);	// continue scan for upper bound
		while (!this->_Isnil(_Pnode))
			if (_DEBUG_LT_PRED(this->comp, _Keyval, this->_Key(_Pnode)))
				{	// _Pnode greater than _Keyval, remember it
				_Hinode = _Pnode;
				_Pnode = this->_Left(_Pnode);	// descend left subtree
				}
			else
				_Pnode = this->_Right(_Pnode);	// descend right subtree

		iterator _First = iterator(_Lonode, this);
		iterator _Last = iterator(_Hinode, this);
		return (_Pairii(_First, _Last));
		}

	void _Erase(_Nodeptr _Rootnode)
		{	// free entire subtree, recursively
		for (_Nodeptr _Pnode = _Rootnode;
			!this->_Isnil(_Pnode); _Rootnode = _Pnode)
			{	// free subtrees, then node
			_Erase(this->_Right(_Pnode));
			_Pnode = this->_Left(_Pnode);
			_Dest_val(this->_Alval,
				_STD addressof(this->_Myval(_Rootnode)));

			this->_Alnod.deallocate(_Rootnode, 1);
			}
		}

	iterator _Insert(bool _Addleft, _Nodeptr _Wherenode,
		const value_type& _Val)
		{	// add value next to _Wherenode, to left if _Addleft
		return (_Insert(_Addleft, _Wherenode, this->_Buynode(_Val)));
		}

	iterator _Insert(bool _Addleft, _Nodeptr _Wherenode,
		_Nodeptr _Newnode)
		{	// add node with value next to _Wherenode, to left if _Addleft
		if (max_size() - 1 <= this->_Mysize)
			{	// tree would get too big, fail
			_Dest_val(this->_Alval,
				_STD addressof(this->_Myval(_Newnode)));

			this->_Alnod.deallocate(_Newnode, 1);

			_Xlength_error("map/set<T> too long");
			}
		++this->_Mysize;
		_Newnode->_Parent = _Wherenode;

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

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

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

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

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

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

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

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

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

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

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

		if (!this->_Isnil(this->_Left(_Pnode)))
			this->_Parent(this->_Left(_Pnode)) = _Wherenode;
		this->_Parent(_Pnode) = this->_Parent(_Wherenode);

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

		this->_Left(_Pnode) = _Wherenode;
		this->_Parent(_Wherenode) = _Pnode;
		}

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

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

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

		if (!this->_Isnil(this->_Right(_Pnode)))
			this->_Parent(this->_Right(_Pnode)) = _Wherenode;
		this->_Parent(_Pnode) = this->_Parent(_Wherenode);

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

		this->_Right(_Pnode) = _Wherenode;
		this->_Parent(_Wherenode) = _Pnode;
		}

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

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

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

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

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

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

 #if _ITERATOR_DEBUG_LEVEL == 2
	void _Orphan_ptr(_Myt& _Cont, _Nodeptr _Ptr) const
		{	// orphan iterators with specified node pointers
		_Lockit _Lock(_LOCK_DEBUG);
		const_iterator **_Pnext = (const_iterator **)_Cont._Getpfirst();
		if (_Pnext != 0)
			while (*_Pnext != 0)
				if ((*_Pnext)->_Ptr == this->_Myhead
					|| _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr)
					_Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
				else
					{	// orphan the iterator
					(*_Pnext)->_Clrcont();
					*_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
					}
		}
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

	void _Tidy()
		{	// free all storage
		erase(begin(), end());
		}
	};

		// _Tree TEMPLATE OPERATORS
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()));
	}

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

 #pragma warning(pop)
 #pragma pack(pop)

#endif /* RC_INVOKED */
#endif /* _XTREE_ */

/*
 * 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.
 */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V5.20:0009 */