xtree

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

// xtree internal header
#pragma once
#ifndef _XTREE_
#define _XTREE_
#ifndef RC_INVOKED
#include <xfunctional>
#include <memory>
#include <stdexcept>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)

 #pragma warning(disable: 4127)
_STD_BEGIN
		// TEMPLATE CLASS _Tree_unchecked_const_iterator
template<class _Mytree,
	class _Base = _Iterator_base0>
	class _Tree_unchecked_const_iterator
		: public _Iterator012<bidirectional_iterator_tag,
			typename _Mytree::value_type,
			typename _Mytree::difference_type,
			typename _Mytree::const_pointer,
			typename _Mytree::const_reference,
			_Base>
	{	// unchecked iterator for nonmutable tree
public:
	typedef _Tree_unchecked_const_iterator<_Mytree, _Base> _Myiter;
	typedef bidirectional_iterator_tag iterator_category;

	typedef typename _Mytree::_Nodeptr _Nodeptr;
	typedef typename _Mytree::value_type value_type;
	typedef typename _Mytree::difference_type difference_type;
	typedef typename _Mytree::const_pointer pointer;
	typedef typename _Mytree::const_reference reference;

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

	_Tree_unchecked_const_iterator(_Nodeptr _Pnode, const _Mytree *_Plist)
		: _Ptr(_Pnode)
		{	// construct with node pointer _Pnode
		this->_Adopt(_Plist);
		}

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

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

	_Myiter& operator++()
		{	// preincrement
		if (_Mytree::_Isnil(_Ptr))
			;	// end() shouldn't be incremented, don't move
		else if (!_Mytree::_Isnil(_Mytree::_Right(_Ptr)))
			_Ptr = _Mytree::_Min(
				_Mytree::_Right(_Ptr));	// ==> smallest of right subtree
		else
			{	// climb looking for right subtree
			_Nodeptr _Pnode;
			while (!_Mytree::_Isnil(_Pnode = _Mytree::_Parent(_Ptr))
				&& _Ptr == _Mytree::_Right(_Pnode))
				_Ptr = _Pnode;	// ==> parent while right subtree
			_Ptr = _Pnode;	// ==> parent (head if end())
			}
		return (*this);
		}

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

	_Myiter& operator--()
		{	// predecrement
		if (_Mytree::_Isnil(_Ptr))
			_Ptr = _Mytree::_Right(_Ptr);	// end() ==> rightmost
		else if (!_Mytree::_Isnil(_Mytree::_Left(_Ptr)))
			_Ptr = _Mytree::_Max(
				_Mytree::_Left(_Ptr));	// ==> largest of left subtree
		else
			{	// climb looking for left subtree
			_Nodeptr _Pnode;
			while (!_Mytree::_Isnil(_Pnode = _Mytree::_Parent(_Ptr))
				&& _Ptr == _Mytree::_Left(_Pnode))
				_Ptr = _Pnode;	// ==> parent while left subtree
			if (_Mytree::_Isnil(_Ptr))
				;	// begin() shouldn't be decremented, don't move
			else
				_Ptr = _Pnode;	// ==> parent if not head
			}
		return (*this);
		}

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

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

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

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

	_Nodeptr _Ptr;	// pointer to node
	};

	// TEMPLATE CLASS _Tree_unchecked_iterator
template<class _Mytree>
	class _Tree_unchecked_iterator
		: public _Tree_unchecked_const_iterator<_Mytree>
	{	// unchecked iterator for mutable tree
public:
	typedef _Tree_unchecked_iterator<_Mytree> _Myiter;
	typedef _Tree_unchecked_const_iterator<_Mytree> _Mybase;
	typedef bidirectional_iterator_tag iterator_category;

	typedef typename _Mytree::_Nodeptr _Nodeptr;
	typedef typename _Mytree::value_type value_type;
	typedef typename _Mytree::difference_type difference_type;
	typedef typename _Mytree::pointer pointer;
	typedef typename _Mytree::reference reference;

	_Tree_unchecked_iterator()
		{	// construct with null node
		}

	_Tree_unchecked_iterator(_Nodeptr _Pnode, const _Mytree *_Plist)
		: _Mybase(_Pnode, _Plist)
		{	// construct with node pointer _Pnode
		}

	reference operator*() const
		{	// return designated value
		return ((reference)**(_Mybase *)this);
		}

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

	_Myiter& operator++()
		{	// preincrement
		++(*(_Mybase *)this);
		return (*this);
		}

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

	_Myiter& operator--()
		{	// predecrement
		--(*(_Mybase *)this);
		return (*this);
		}

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

	// TEMPLATE CLASS _Tree_const_iterator
template<class _Mytree>
	class _Tree_const_iterator
		: public _Tree_unchecked_const_iterator<_Mytree, _Iterator_base>
	{	// iterator for nonmutable tree
public:
	typedef _Tree_const_iterator<_Mytree> _Myiter;
	typedef _Tree_unchecked_const_iterator<_Mytree, _Iterator_base> _Mybase;
	typedef bidirectional_iterator_tag iterator_category;

	typedef typename _Mytree::_Nodeptr _Nodeptr;
	typedef typename _Mytree::value_type value_type;
	typedef typename _Mytree::difference_type difference_type;
	typedef typename _Mytree::const_pointer pointer;
	typedef typename _Mytree::const_reference reference;

	_Tree_const_iterator()
		: _Mybase()
		{	// construct with null node pointer
		}

	_Tree_const_iterator(_Nodeptr _Pnode, const _Mytree *_Plist)
		: _Mybase(_Pnode, _Plist)
		{	// construct with node pointer _Pnode
		}

	typedef _Tree_unchecked_const_iterator<_Mytree> _Unchecked_type;

	_Myiter& _Rechecked(_Unchecked_type _Right)
		{	// reset from unchecked iterator
		this->_Ptr = _Right._Ptr;
		return (*this);
		}

	_Unchecked_type _Unchecked() const
		{	// make an unchecked iterator
		return (_Unchecked_type(this->_Ptr, (_Mytree *)this->_Getcont()));
		}

	reference operator*() const
		{	// return designated value
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Getcont() == 0
			|| this->_Ptr == 0
			|| this->_Ptr == ((_Mytree *)this->_Getcont())->_Myhead)
			{	// report error
			_DEBUG_ERROR("map/set iterator not dereferencable");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0);
		_SCL_SECURE_VALIDATE_RANGE(this->_Ptr !=
			((_Mytree *)this->_Getcont())->_Myhead);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		return (_Mytree::_Myval(this->_Ptr));
		}

	_Myiter& operator++()
		{	// preincrement
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Getcont() == 0
			|| this->_Ptr == 0
			|| _Mytree::_Isnil(this->_Ptr))
			{	// report error
			_DEBUG_ERROR("map/set iterator not incrementable");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0);
		_SCL_SECURE_VALIDATE_RANGE(!_Mytree::_Isnil(this->_Ptr));
 #endif /* _ITERATOR_DEBUG_LEVEL */

		++(*(_Mybase *)this);
		return (*this);
		}

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

	_Myiter& operator--()
		{	// predecrement
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Getcont() == 0
			|| this->_Ptr == 0)
			{	// report error
			_DEBUG_ERROR("map/set iterator not decrementable");
			_SCL_SECURE_OUT_OF_RANGE;
			}

		_Nodeptr _Ptrsav = this->_Ptr;
		--(*(_Mybase *)this);
		if (_Ptrsav == this->_Ptr)
			{	// report error
			_DEBUG_ERROR("map/set iterator not decrementable");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0);

		_Nodeptr _Ptrsav = this->_Ptr;
		--(*(_Mybase *)this);
		_SCL_SECURE_VALIDATE(_Ptrsav != this->_Ptr);

 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
		--(*(_Mybase *)this);
 #endif /* _ITERATOR_DEBUG_LEVEL */

		return (*this);
		}

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

	bool operator==(const _Myiter& _Right) const
		{	// test for iterator equality
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (this->_Getcont() == 0
			|| this->_Getcont() != _Right._Getcont())
			{	// report error
			_DEBUG_ERROR("map/set iterators incompatible");
			_SCL_SECURE_INVALID_ARGUMENT;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE(this->_Getcont() != 0
			&& this->_Getcont() == _Right._Getcont());
 #endif /* _ITERATOR_DEBUG_LEVEL */

		return (this->_Ptr == _Right._Ptr);
		}

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

template<class _Mytree> inline
	typename _Tree_const_iterator<_Mytree>::_Unchecked_type
		_Unchecked(_Tree_const_iterator<_Mytree> _Iter)
	{	// convert to unchecked
	return (_Iter._Unchecked());
	}

template<class _Mytree> inline
	_Tree_const_iterator<_Mytree>&
		_Rechecked(_Tree_const_iterator<_Mytree>& _Iter,
			typename _Tree_const_iterator<_Mytree>
				::_Unchecked_type _Right)
	{	// convert to checked
	return (_Iter._Rechecked(_Right));
	}

	// TEMPLATE CLASS _Tree_iterator
template<class _Mytree>
	class _Tree_iterator
		: public _Tree_const_iterator<_Mytree>
	{	// iterator for mutable tree
public:
	typedef _Tree_iterator<_Mytree> _Myiter;
	typedef _Tree_const_iterator<_Mytree> _Mybase;
	typedef bidirectional_iterator_tag iterator_category;

	typedef typename _Mytree::_Nodeptr _Nodeptr;
	typedef typename _Mytree::value_type value_type;
	typedef typename _Mytree::difference_type difference_type;

	typedef typename _Mytree::pointer pointer;
	typedef typename _Mytree::reference reference;

	_Tree_iterator()
		{	// construct with null node
		}

	_Tree_iterator(_Nodeptr _Pnode, const _Mytree *_Plist)
		: _Mybase(_Pnode, _Plist)
		{	// construct with node pointer _Pnode
		}

	typedef _Tree_unchecked_iterator<_Mytree> _Unchecked_type;

	_Myiter& _Rechecked(_Unchecked_type _Right)
		{	// reset from unchecked iterator
		this->_Ptr = _Right._Ptr;
		return (*this);
		}

	_Unchecked_type _Unchecked() const
		{	// make an unchecked iterator
		return (_Unchecked_type(this->_Ptr, (_Mytree *)this->_Getcont()));
		}

	reference operator*() const
		{	// return designated value
		return ((reference)**(_Mybase *)this);
		}

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

	_Myiter& operator++()
		{	// preincrement
		++(*(_Mybase *)this);
		return (*this);
		}

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

	_Myiter& operator--()
		{	// predecrement
		--(*(_Mybase *)this);
		return (*this);
		}

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

template<class _Mytree> inline
	typename _Tree_iterator<_Mytree>::_Unchecked_type
		_Unchecked(_Tree_iterator<_Mytree> _Iter)
	{	// convert to unchecked
	return (_Iter._Unchecked());
	}

template<class _Mytree> inline
	_Tree_iterator<_Mytree>&
		_Rechecked(_Tree_iterator<_Mytree>& _Iter,
			typename _Tree_iterator<_Mytree>
				::_Unchecked_type _Right)
	{	// convert to checked
	return (_Iter._Rechecked(_Right));
	}

		// TEMPLATE CLASS _Tree_nod
template<class _Traits>
	class _Tree_nod
		: public _Traits	// traits form ultimate base
	{	// base class for _Tree_ptr to hold storage
public:
	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<value_type>::other
		_Alty;
	typedef typename _Alty::size_type size_type;

	struct _Node;
	typedef _Node *_Nodeptr;	// _Node allocator must have ordinary pointers
	typedef _Nodeptr& _Nodepref;

	struct _Node
		{	// tree node
		_Nodeptr _Left;	// left subtree, or smallest element if head
		_Nodeptr _Parent;	// parent, or root of tree if head
		_Nodeptr _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

	private:
		_Node& operator=(const _Node&);
		};

 #if _ITERATOR_DEBUG_LEVEL == 0
	_Tree_nod(const key_compare& _Parg,
		allocator_type _Al)
		: _Traits(_Parg), _Alnod(_Al), _Alval(_Al)
		{	// construct traits from _Parg and allocators from _Al
		}

 #else /* _ITERATOR_DEBUG_LEVEL == 0 */