xtree

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

			}
		return (_Newroot);
		}

	void _Init()
		{	// create header/nil node and make tree empty
		_Mysize = 0;
		_Myhead = _Buynode();
		_Mygen = 0;
		}

	node_type^ _Insert_node(bool _Addleft, node_type^ _Where,
		value_type _Val)
		{	// add node with value next to _Where, to left if _Addleft

		if (_Maxsize <= _Mysize)
			throw gcnew System::InvalidOperationException();

		node_type^ _Newnode = _Buynode(head_node(), _Where, head_node(),
			_Val, _Red);

		if (_Where == head_node())
			{	// first node in tree, just set head values
			head_node()->_Left = _Newnode;
			head_node()->_Parent = _Newnode;
			head_node()->_Right = _Newnode;
			}
		else if (_Addleft)
			{	// add to left of _Where
			_Where->_Left = _Newnode;
			if (_Where == front_node())
				head_node()->_Left = _Newnode;
			}
		else
			{	// add to right of _Where
			_Where->_Right = _Newnode;
			if (_Where == back_node())
				head_node()->_Right = _Newnode;
			}

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

		root_node()->_Color = _Black;	// root is always black
		++_Mysize;
		++_Mygen;
		return (_Newnode);
		}

	key_type _Key(node_type^ _Where)
		{	// get key value from node
		return (this->get_key(_Where->_Myval));
		}

	void _Lrotate(node_type^ _Where)
		{	// promote right node to root of subtree
		node_type^ _Node = _Where->_Right;
		_Where->_Right = _Node->_Left;

		if (!_Node->_Left->is_head())
			_Node->_Left->_Parent = _Where;
		_Node->_Parent = _Where->_Parent;

		if (_Where == root_node())
			head_node()->_Parent = _Node;
		else if (_Where == _Where->_Parent->_Left)
			_Where->_Parent->_Left = _Node;
		else
			_Where->_Parent->_Right = _Node;

		_Node->_Left = _Where;
		_Where->_Parent = _Node;
		}

	void _Rrotate(node_type^ _Where)
		{	// promote left node to root of subtree
		node_type^ _Node = _Where->_Left;
		_Where->_Left = _Node->_Right;

		if (!_Node->_Right->is_head())
			_Node->_Right->_Parent = _Where;
		_Node->_Parent = _Where->_Parent;

		if (_Where == root_node())
			head_node()->_Parent = _Node;
		else if (_Where == _Where->_Parent->_Right)
			_Where->_Parent->_Right = _Node;
		else
			_Where->_Parent->_Left = _Node;

		_Node->_Right = _Where;
		_Where->_Parent = _Node;
		}

	// data members
	node_type^ _Myhead;	// pointer to head node
	size_type _Mysize;	// number of elements
	unsigned long _Mygen;	// current change generation

	// interfaces
public:
	virtual System::Object^ Clone()
		{	// clone the tree
		return (gcnew tree(*this));
		}

private:
	property size_type Count
		{	// element count
		virtual size_type get() sealed
			= System::Collections::ICollection::Count::get
			{	// get element count
			return (size());
			}
		};

	property bool IsSynchronized
		{	// synchronized status
		virtual bool get() sealed
			= System::Collections::ICollection::IsSynchronized::get
			{	// test if synchronized
			return (false);
			}
		};

	property System::Object^ SyncRoot
		{	// synchronizer
		virtual System::Object^ get() sealed
			= System::Collections::ICollection::SyncRoot::get
			{	// get synchronizer
			return (this);
			}
		};

	virtual void CopyTo(System::Array^ _Dest_arg, int _First) sealed
		= System::Collections::ICollection::CopyTo
		{	// copy to _Dest_arg, beginning at _First
		cli::array<System::Object^>^ _Dest =
			(cli::array<System::Object ^>^)_Dest_arg;
		node_type^ _Node = head_node();

		for (int _Idx = size(); 0 <= --_Idx; )
			{	// copy back to front
			_Node = _Node->prev_node();
			_Dest[_First + _Idx] = _Node->_Myval;
			}
		}

	virtual System::Collections::IEnumerator^ GetEnumerator() sealed
		= System::Collections::IEnumerable::GetEnumerator
		{	// get enumerator for the container
		return (gcnew
			_STLCLR TreeEnumerator<_Key_t, _Value_t>(front_node()));
		}

	virtual unsigned long get_generation_virtual() sealed
		= _Mycont_it::get_generation
		{	// get underlying container generation
		return (get_generation());
		}

//	virtual bool valid_bias_virtual(size_type _Bias);
//	virtual reference at_virtual(size_type _Pos);
//	virtual reference at_bias_virtual(size_type _Bias);

//	virtual reference front_virtual();
//	virtual reference back_virtual();

	// converters
	virtual key_compare^ key_comp_virtual() sealed
		= _Mycont_it::key_comp
		{	// return object for comparing keys
		return (key_comp());
		}

	virtual value_compare^ value_comp_virtual() sealed
		= _Mycont_it::value_comp
		{	// return object for comparing keys
		return (value_comp());
		}

	// iterator generators
	virtual generic_iterator begin_virtual() sealed
		= _Mycont_it::begin
		{	// return iterator for beginning of mutable sequence
		return (begin());
		}
	virtual generic_iterator end_virtual() sealed
		= _Mycont_it::end
		{	// return iterator for end of mutable sequence
		return (end());
		}

	virtual generic_reverse_iterator rbegin_virtual() sealed
		= _Mycont_it::rbegin
		{	// return reverse iterator for beginning of mutable sequence
		return (generic_reverse_iterator(end()));
		}

	virtual generic_reverse_iterator rend_virtual() sealed
		= _Mycont_it::rend
		{	// return reverse iterator for end of mutable sequence
		return (generic_reverse_iterator(begin()));
		}

	// size controllers
//	virtual void reserve_virtual(size_type _Capacity);
//	virtual size_type capacity_virtual();
//	virtual void resize_virtual(size_type _Newsize);
//	virtual void resize_virtual(size_type _Newsize, value_type _Val);

	virtual size_type size_virtual() sealed
		= _Mycont_it::size
		{	// return length of sequence
		return (size());
		}

	virtual bool empty_virtual() sealed
		= _Mycont_it::empty
		{	// test if sequence is empty
		return (empty());
		}

	// mutators
//	virtual void push_front_virtual(value_type _Val);
//	virtual void pop_front_virtual();
//	virtual void push_back_virtual(value_type _Val);
//	virtual void pop_back_virtual();

//	virtual void assign_virtual(size_type _Count, value_type _Val);
//	virtual void assign_virtual(
//		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
//		_STLCLR Generic::IInputIterator<_Value_t>^ _Last);
//	virtual void assign_virtual(_Myenum_it^ _Right);

	virtual generic_pair_iter_bool insert_virtual(value_type _Val) sealed
		= _Mycont_it::insert
		{	// try to insert node with value _Val, return iterator, bool
		_Pairnb _Ans = insert_node(_Val);
		return (generic_pair_iter_bool(gcnew generic_iterator(_Ans.first),
			_Ans.second));
		}

	virtual generic_iterator insert_virtual(generic_iterator _Where,
		value_type _Val) sealed
		= _Mycont_it::insert
		{	// insert _Val at _Where
		return (insert(iterator(_Where), _Val));
		}

//	virtual void insert_virtual(generic_iterator _Where,
//		size_type _Count, value_type _Val);
//	virtual void insert_virtual(generic_iterator _Where_iter,
//		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
//		_STLCLR Generic::IInputIterator<_Value_t>^ _Last);
//	virtual void insert_virtual(generic_iterator _Where_iter,
//		_Myenum_it^ _Right);

	virtual void insert_virtual(
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last) sealed
		= _Mycont_it::insert
		{	// insert [_First, _Last) one at a time
		insert(_First, _Last);
		}

	virtual void insert_virtual(_Myenum_it^ _Right) sealed
		= _Mycont_it::insert
		{	// insert enumerable
		insert(_Right);
		}

	virtual generic_iterator erase_virtual(generic_iterator _Where) sealed
		= _Mycont_it::erase
		{	// erase element at _Where
		return (erase(iterator(_Where)));
		}

	virtual generic_iterator erase_virtual(generic_iterator _First,
		generic_iterator _Last) sealed
		= _Mycont_it::erase
		{	// erase [_First, _Last)
		return (erase(iterator(_First), iterator(_Last)));
		}

	virtual size_type erase_virtual(key_type _Keyval) sealed
		= _Mycont_it::erase
		{	// erase and count all that match _Keyval
		return (erase(_Keyval));
		}

	virtual void clear_virtual() sealed
		= _Mycont_it::clear
		{	// erase all
		clear();
		}

	virtual void swap_virtual(_Mycont_it^ _Right) sealed
		= _Mycont_it::swap
		{	// exchange contents with _Right
		swap(*(_Mytype_t^)_Right);
		}

	// searches
	virtual generic_iterator find_virtual(key_type _Keyval) sealed
		= _Mycont_it::find
		{	// find an element that matches _Keyval, return iterator
		return (find(_Keyval));
		}

	virtual size_type count_virtual(key_type _Keyval) sealed
		= _Mycont_it::count
		{	// count all elements that match _Keyval
		return (count(_Keyval));
		}

	virtual generic_iterator lower_bound_virtual(key_type _Keyval) sealed
		= _Mycont_it::lower_bound
		{	// find leftmost node not less than _Keyval
		return (lower_bound(_Keyval));
		}

	virtual generic_iterator upper_bound_virtual(key_type _Keyval) sealed
		= _Mycont_it::upper_bound
		{	// find leftmost node greater than _Keyval
		return (upper_bound(_Keyval));
		}

	virtual generic_pair_iter_iter equal_range_virtual(
		key_type _Keyval) sealed
			= _Mycont_it::equal_range
		{	// find range equivalent to _Keyval
		_Pairnn _Ans = equal_range_node(_Keyval);
		return (generic_pair_iter_iter(gcnew generic_iterator(_Ans.first),
			gcnew generic_iterator(_Ans.second)));
		}
	};
	}	// namespace cliext::impl

//
// TEMPLATE COMPARISONS
//
template<typename _Traits_t> inline
	bool operator==(cliext::impl::tree<_Traits_t>% _Left,
		cliext::impl::tree<_Traits_t>% _Right)
	{	// test if _Left == _Right
	typedef cliext::impl::tree<_Traits_t> _Mytype_t;

	_Mytype_t::size_type _Size = _Left.size();

	if (_Size != _Right.size())
		return (false);
	else
		{	// same length, compare elements
		_Mytype_t::node_type^ _Pleft = _Left.front_node();
		_Mytype_t::node_type^ _Pright = _Right.front_node();
		_Mytype_t::key_compare^ _Pred = _Left.key_comp();

		for (; 0 < _Size; --_Size)
			{	// compare next two elements
				if (_Pred(_Left.get_key(_Pleft->_Myval),
						_Right.get_key(_Pright->_Myval))
					|| _Pred(_Right.get_key(_Pright->_Myval),
						_Left.get_key(_Pleft->_Myval)))
				return (false);
			_Pleft = _Pleft->next_node();
			_Pright = _Pright->next_node();
			}
		return (true);
		}
	}

template<typename _Traits_t> inline
	bool operator!=(cliext::impl::tree<_Traits_t>% _Left,
		cliext::impl::tree<_Traits_t>% _Right)
	{	// test if _Left != _Right
	return (!(_Left == _Right));
	}

template<typename _Traits_t> inline
	bool operator<(cliext::impl::tree<_Traits_t>% _Left,
		cliext::impl::tree<_Traits_t>% _Right)
	{	// test if _Left < _Right
	typedef cliext::impl::tree<_Traits_t> _Mytype_t;

	_Mytype_t::size_type _Idx = 0;
	_Mytype_t::node_type^ _Pleft = _Left.front_node();
	_Mytype_t::node_type^ _Pright = _Right.front_node();
	_Mytype_t::key_compare^ _Pred = _Left.key_comp();

	for (; _Idx != _Left.size() && _Idx != _Right.size(); ++_Idx)
		{	// compare next two elements
		if (_Pred(_Left.get_key(_Pleft->_Myval),
			_Right.get_key(_Pright->_Myval)))
			return (true);
		else if (_Pred(_Right.get_key(_Pright->_Myval),
			_Left.get_key(_Pleft->_Myval)))
			return (false);
		_Pleft = _Pleft->next_node();
		_Pright = _Pright->next_node();
		}
	return (_Idx == _Left.size() && _Idx != _Right.size());
	}

template<typename _Traits_t> inline
	bool operator>=(cliext::impl::tree<_Traits_t>% _Left,
		cliext::impl::tree<_Traits_t>% _Right)
	{	// test if _Left >= _Right
	return (!(_Left < _Right));
	}

template<typename _Traits_t> inline
	bool operator>(cliext::impl::tree<_Traits_t>% _Left,
		cliext::impl::tree<_Traits_t>% _Right)
	{	// test if _Left > _Right
	return (_Right < _Left);
	}

template<typename _Traits_t> inline
	bool operator<=(cliext::impl::tree<_Traits_t>% _Left,
		cliext::impl::tree<_Traits_t>% _Right)
	{	// test if _Left <= _Right
	return (!(_Right < _Left));
	}

//
// TEMPLATE FUNCTION swap
//
template<typename _Traits_t> inline
	void swap(cliext::impl::tree<_Traits_t>% _Left,
		cliext::impl::tree<_Traits_t>% _Right)
	{	// swap two trees
	_Left.swap(_Right);
	}
}	// namespace cliext
#endif // _CLI_XTREE_

/*
 * Copyright (c) 2004-2007 by Dinkumware, Ltd.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V5.03:0009 */