xtree

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

// xtree stl/clr header
#ifndef _CLI_XTREE_
 #define _CLI_XTREE_
#include <cliext/functional>	// for Binary/UnaryDelegate
#include <cliext/iterator>

namespace cliext {
	namespace impl {
//
// GENERIC REF CLASS tree_node
//
template<typename _Key_t,
	typename _Value_t>
	ref class tree_node
	:	public _STLCLR Generic::INode<_Value_t>
	{	// tree node
public:
	typedef tree_node<_Key_t, _Value_t> _Mytype_t;
	typedef _STLCLR Generic::INode<_Value_t> _Mynode_it;
	typedef _STLCLR Generic::IBidirectionalContainer<_Value_t> _Mycont_it;
	typedef _Value_t value_type;

	tree_node()
		{	// construct an empty node
		}

	tree_node(_Mytype_t^ _Larg, _Mytype_t^ _Parg,
		_Mytype_t^ _Rarg, _Mytype_t^ _Harg,
		value_type _Val, signed char _Carg)
		:	_Left(_Larg), _Parent(_Parg), _Right(_Rarg),
			_Head(_Harg), _Myval(_Val), _Color(_Carg),
			_Mycont(nullptr)
		{	// construct a node with value
		}

	_Mycont_it^ container()
		{	// return owning container
		return (_Head == nullptr ? nullptr : _Head->_Mycont);
		}

	bool is_head()
		{	// test if head node
		return (_Mycont != nullptr);
		}

	_Mytype_t^ max_node()
		{	// return rightmost node in subtree
		_Mytype_t^ _Node = this;

		for (; !_Node->_Right->is_head(); )
			_Node = _Node->_Right;	// descend along right subtrees
		return (_Node);
		}

	_Mytype_t^ min_node()
		{	// return leftmost node in subtree
		_Mytype_t^ _Node = this;

		for (; !_Node->_Left->is_head(); )
			_Node = _Node->_Left;	// descend along left subtrees
		return (_Node);
		}

	_Mytype_t^ next_node()
		{	// return successor node
		if (this == _Head || _Head == nullptr)
			throw gcnew System::InvalidOperationException();
		else if (!_Right->is_head())
			return (_Right->min_node());
		else
			{	// climb looking for right subtree
			_Mytype_t^ _Node = this;
			_Mytype_t^ _Nextnode;

			for (; !(_Nextnode = _Node->_Parent)->is_head()
				&& _Node == _Nextnode->_Right; )
				_Node = _Nextnode;	// go up while right subtree exists

			return (_Nextnode);	// go to parent (head if end())
			}
		}

	_Mytype_t^ prev_node()
		{	// return predecessor node
		if (_Head == nullptr)
			throw gcnew System::InvalidOperationException();

		if (is_head())
			return(_Right);	// go to rightmost
		else if (!_Left->is_head())
			return (_Left->max_node());	// go to largest on left
		else
			{	// climb looking for left subtree
			_Mytype_t^ _Node = this;
			_Mytype_t^ _Nextnode;

			for (; !(_Nextnode = _Node->_Parent)->is_head()
				&& _Node == _Nextnode->_Left; )
				_Node = _Nextnode;	// go up while left subtree exists

			if (_Nextnode->is_head())
				throw gcnew System::InvalidOperationException();
			return (_Nextnode);	// go to parent (if not head)
			}
		}

	property _Value_t% _Value
		{	// get or set _Myval
		virtual _Value_t% get()
			{	// get _Myval element
			if (this == _Head || _Head == nullptr)
				throw gcnew System::InvalidOperationException();
			return (_Myval);
			}

		virtual void set(_Value_t% _Val)
			{	// set _Myval element
			if (this == _Head || _Head == nullptr)
				throw gcnew System::InvalidOperationException();
			_Myval = _Val;
			}
		};

	// data members
	_Mycont_it^ _Mycont;	// pointer to owning tree
	_Mytype_t^ _Head;	// pointer to head node
	_Mytype_t^ _Left;	// pointer to left subtree
	_Mytype_t^ _Parent;	// pointer to parent
	_Mytype_t^ _Right;	// pointer to right subtree
	value_type _Myval;		// the stored value
	signed char _Color;	// _Red or _Black

private:
	virtual _Mycont_it^ container_virtual() sealed
		= _Mynode_it::container
		{	// return owning container
		return (container());
		}

	virtual bool is_head_virtual() sealed
		= _Mynode_it::is_head
		{	// test if head node
		return (is_head());
		}

	virtual _Mynode_it^ next_node_virtual() sealed
		= _Mynode_it::next_node
		{	// return successor node
		return (next_node());
		}

	virtual _Mynode_it^ prev_node_virtual() sealed
		= _Mynode_it::prev_node
		{	// return predecessor node
		return (prev_node());
		}
	};

//
// TEMPLATE FUNCTION _Key_compare
//
template<typename _Key_t> inline
	bool _Key_compare(_Key_t _Left, _Key_t _Right)
	{	// test if _Left < _Right
	return (_Left < _Right);
	}

inline bool _Key_compare(System::String^ _Left, System::String^ _Right)
	{	// test if _Left < _Right for String
	return (_Left->CompareTo(_Right) < 0);
	}

//
// TEMPLATE CLASS tree
//
template<typename _Traits_t>
	ref class tree
	:	public _Traits_t,
		_STLCLR ITree<typename _Traits_t::key_type,
			typename _Traits_t::value_type>
	{	// ordered red-black tree of elements
public:
	// types
	typedef tree<_Traits_t> _Mytype_t;
	typedef _Traits_t _Mybase_t;
	typedef typename _Traits_t::key_type _Key_t;
	typedef typename _Traits_t::value_type _Value_t;
	typedef _STLCLR ITree<_Key_t, _Value_t> _Mycont_it;
	typedef System::Collections::Generic::IEnumerable<_Value_t> _Myenum_it;
	typedef cli::array<_Value_t> _Myarray_t;

	typedef tree_node<_Key_t, _Value_t> node_type;

	typedef BidirectionalIterator<_Mytype_t>
		iterator;
	typedef ConstBidirectionalIterator<_Mytype_t>
		const_iterator;
	typedef ReverseBidirectionalIterator<_Mytype_t>
		reverse_iterator;
	typedef ReverseBidirectionalIterator<_Mytype_t>
		const_reverse_iterator;

	typedef typename _Traits_t::key_type key_type;
	typedef typename _Traits_t::value_type value_type;
	typedef typename _Traits_t::key_compare key_compare;
	typedef typename _Traits_t::value_compare value_compare;

	typedef int size_type;
	typedef int difference_type;
//	typedef _Value_t value_type;
	typedef value_type% reference;
	typedef value_type% const_reference;

	typedef _Mycont_it generic_container;
	typedef value_type generic_value;
	typedef _STLCLR Generic::ContainerBidirectionalIterator<_Value_t>
		generic_iterator;
	typedef _STLCLR Generic::ReverseBidirectionalIterator<_Value_t>
		generic_reverse_iterator;

	typedef _STLCLR GenericPair<iterator, bool> pair_iter_bool;
	typedef _STLCLR GenericPair<iterator, iterator> pair_iter_iter;
	typedef _STLCLR GenericPair<node_type^, bool> _Pairnb;
	typedef _STLCLR GenericPair<node_type^, node_type^> _Pairnn;

	typedef _STLCLR GenericPair<generic_iterator^, bool>
		generic_pair_iter_bool;
	typedef _STLCLR GenericPair<generic_iterator^, generic_iterator^>
		generic_pair_iter_iter;

	// constants
	static const int _Maxsize = MAX_CONTAINER_SIZE;

	static const int _Black = 0;	// colors for a node
	static const int _Red = 1;

	// basics
	tree()
		{	// construct empty tree from default comparator
		_Init();
		}

	tree(tree% _Right)
		:	_Mybase_t(_Right.key_comp())
		{	// construct by copying _Right
		_Init();
		_Copy(%_Right);
		}

	tree% operator=(tree% _Right)
		{	// assign
		if ((Object^)this != %_Right)
			{	// worth doing, do it
			clear();
			_Copy(%_Right);
			}
		return (*this);
		}

	operator _Mycont_it^()
		{	// convert to interface
		return (this);
		}

	// constructors
	explicit tree(key_compare^ _Pred)
		:	_Mybase_t(_Pred)
		{	// construct empty tree from comparator
		_Init();
		}

	// destructor
	~tree()
		{	// destroy the object
		clear();
		_Myhead->_Mycont = nullptr;	// orphan all iterators
		_Myhead = nullptr;
		_Mysize = 0;
		++_Mygen;
		}

	// accessors
	unsigned long get_generation()
		{	// get underlying container generation
		return (_Mygen);
		}

	node_type^ get_node(iterator _Where)
		{	// get node from valid iterator
		node_type^ _Node = (node_type^)_Where.get_node();

		if (_Node == nullptr || _Node->container() != (System::Object^)this)
			throw gcnew System::InvalidOperationException();
		return (_Node);
		}

	node_type^ front_node()
		{	// return leftmost node in tree
		return (head_node()->_Left);
		}

	node_type^ back_node()
		{	// return rightmost node in tree
		return (head_node()->_Right);
		}

	node_type^ root_node()
		{	// return root of tree
		return (head_node()->_Parent);
		}

	node_type^ head_node()
		{	// get head node
		return (_Myhead);
		}

//	property reference default[/* size_type */];
//	property value_type front_item;
//	property value_type back_item;
//	reference front();
//	reference back();

	// converters
	_Myarray_t^ to_array()
		{	// convert to array
		_Myarray_t^ _Ans = gcnew _Myarray_t(size());
		node_type^ _Node = head_node();

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

	key_compare^ key_comp() new
		{	// return object for comparing keys
		return (_Mybase_t::key_comp());
		}

	value_compare^ value_comp() new
		{	// return object for comparing keys
		return (_Mybase_t::value_comp());
		}

	// iterator generators
	iterator make_iterator(node_type^ _Node)
		{	// return iterator for node
		return (iterator(_Node));
		}

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

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

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

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

	// size controllers
//	void reserve(size_type _Capacity);
//	size_type capacity();
//	void resize(size_type _Newsize);
//	void resize(size_type _Newsize, value_type _Val);

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

	bool empty()
		{	// test if sequence is empty
		return (size() == 0);
		}

	// mutators
//	void push_front(value_type _Val);
//	void pop_front();
//	void push_back(value_type _Val);
//	void pop_back();

//	void assign(size_type _Count, value_type _Val);
//	template<typename _Iter_t>
//		void assign(_Iter_t _First, _Iter_t _Last);
//	void assign(System::Collections::Generic::IEnumerable<_Value_t>^);

	pair_iter_bool insert(value_type _Val)
		{	// try to insert node with value _Val, return iterator, bool
		_Pairnb _Ans = insert_node(_Val);

		return (pair_iter_bool(iterator(_Ans.first),
			_Ans.second));
		}

	iterator insert(iterator _Where, value_type _Val)
		{	// try to insert node with value _Val at _Where, return iterator
		return (make_iterator(insert_node(get_node(_Where), _Val)));
		}

	template<typename _Iter_t>
		void insert(_Iter_t _First, _Iter_t _Last)
		{	// insert [_First, _Last) one at a time
#pragma warning(push)
#pragma warning(disable: 4127)
		if (_Iter_container(_First) != this)
			for (; _First != _Last; ++_First)
				insert_node(*_First);
		else if (_Multi)
			{	// worth assigning to self
			node_type^ _Node = nullptr;

			for (; _First != _Last; ++_First)
				_Node = _Buynode(nullptr, nullptr, _Node,
					(value_type)*_First, 0);
			for (; _Node != nullptr; _Node = _Node->_Right)
				insert_node(_Node->_Myval);	// insert accumulated sequence
			}
#pragma warning(pop)
		}

	void insert(
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last)
		{	// insert [_First, _Last) one at a time
#pragma warning(push)
#pragma warning(disable: 4127)
		if (_Iter_container(_First) != this)
			for (; !_First->equal_to(_Last); _First->next())
				insert_node((value_type%)_First->get_cref());
		else if (_Multi)
			{	// worth assigning to self
			node_type^ _Node = nullptr;

			for (; !_First->equal_to(_Last); _First->next())
				_Node = _Buynode(nullptr, nullptr, _Node,
					(value_type)_First->get_cref(), 0);
			for (; _Node != nullptr; _Node = _Node->_Right)
				insert_node(_Node->_Myval);	// insert accumulated sequence
			}
#pragma warning(pop)
		}

	void insert(_Myenum_it^ _Right)
		{	// insert enumerable
		node_type^ _Node = nullptr;

		for each (value_type _Val in _Right)
			_Node = _Buynode(nullptr, nullptr, _Node,
				_Val, 0);
		for (; _Node != nullptr; _Node = _Node->_Right)
			insert_node(_Node->_Myval);	// insert accumulated sequence
		}

//	void insert(iterator _Where, size_type _Count, value_type _Val);
//	template<typename _Iter_t>
//		void insert(iterator _Where, _Iter_t _First, _Iter_t _Last);
//	void insert(iterator _Where,
//		System::Collections::Generic::IEnumerable<_Value_t>^ _Right);

	void insert_iter(
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last)
		{	// insert [_First, _Last) one at a time
#pragma warning(push)
#pragma warning(disable: 4127)
		if (_First->container() != this)
			for (; !_First->equal_to(_Last); _First->next())
				insert_node((value_type%)_First->get_cref());
		else if (_Multi)
			{	// worth assigning to self
			node_type^ _Node = nullptr;

			for (; !_First->equal_to(_Last); _First->next())