xtree

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

				_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)
		}

	_Pairnb insert_node(value_type _Val)
		{	// try to insert node with value _Val, return node pointer, bool
#pragma warning(push)
#pragma warning(disable: 4127)
		node_type^ _Node = root_node();
		node_type^ _Where = head_node();
		bool _Addleft = true;	// add to left of head if tree empty

		while (!_Node->is_head())
			{	// look for leaf to insert before (_Addleft) or after
			_Where = _Node;
			_Addleft = this->comp(this->get_key(_Val), _Key(_Node));
			_Node = _Addleft ? _Node->_Left : _Node->_Right;
			}

		if (this->_Multi)
			return (_Pairnb(_Insert_node(_Addleft, _Where, _Val),
				true));
		else
			{	// insert only if unique
			if (!_Addleft)
				_Node = _Where;	// need to test if insert after is okay
			else if (_Where == front_node())
				return (_Pairnb(_Insert_node(true, _Where, _Val),
					true));
			else	// need to test if before is okay
				_Node = _Where->prev_node();

			if (this->comp(_Key(_Node), this->get_key(_Val)))
				return (_Pairnb(_Insert_node(_Addleft, _Where, _Val),
					true));
			else
				return (_Pairnb(_Node, false));
			}
#pragma warning(pop)
		}

	node_type^ insert_node(node_type^ _Where_node, value_type _Val)
		{	// try to insert node with value _Val at _Where, return node
#pragma warning(push)
#pragma warning(disable: 4127)
		node_type^ _Where = (node_type^)_Where_node;
		node_type^ _Next;

		if (_Where->container() != this)
			throw gcnew System::ArgumentException();

		if (empty())
			return (_Insert_node(true, head_node(), _Val));
		else if (this->_Multi)
			{	// insert even if duplicate
			if (_Where == front_node())
				{	// insert at beginning if before first element
				if (!this->comp(_Key(_Where), this->get_key(_Val)))
					return (_Insert_node(true, _Where, _Val));
				}
			else if (_Where == head_node())
				{	// insert at end if after last element
				if (!this->comp(this->get_key(_Val), _Key(back_node())))
					return (_Insert_node(false, back_node(), _Val));
				}
			else if (!this->comp(_Key(_Where), this->get_key(_Val))
				&& !this->comp(this->get_key(_Val),
					_Key(_Next = _Where->prev_node())))
				{	// insert before _Where
				if (_Next->_Right->is_head())
					return (_Insert_node(false, _Next, _Val));
				else
					return (_Insert_node(true, _Where, _Val));
				}
			else if (!this->comp(this->get_key(_Val), _Key(_Where))
				&& ((_Next = _Where->next_node())
					== head_node()
					|| !this->comp(_Key(_Next), this->get_key(_Val))))
				{	// insert after _Where
				if (_Where->_Right->is_head())
					return (_Insert_node(false, _Where, _Val));
				else
					return (_Insert_node(true, _Next, _Val));
				}
			}
		else
			{	// insert only if unique
			if (_Where == front_node())
				{	// insert at beginning if before first element
				if (this->comp(this->get_key(_Val), _Key(_Where)))
					return (_Insert_node(true, _Where, _Val));
				}
			else if (_Where == head_node())
				{	// insert at end if after last element
				if (this->comp(_Key(back_node()), this->get_key(_Val)))
					return (_Insert_node(false, back_node(), _Val));
				}
			else if (this->comp(this->get_key(_Val), _Key(_Where))
				&& this->comp(_Key(
					_Next = _Where->prev_node()),
					this->get_key(_Val)))
				{	// insert before _Where
				if (_Next->_Right->is_head())
					return (_Insert_node(false, _Next, _Val));
				else
					return (_Insert_node(true, _Where, _Val));
				}
			else if (this->comp(_Key(_Where), this->get_key(_Val))
				&& ((_Next = _Where->next_node())
					== head_node()
					|| this->comp(this->get_key(_Val), _Key(_Next))))
				{	// insert after _Where
				if (_Where->_Right->is_head())
					return (_Insert_node(false, _Where, _Val));
				else
					return (_Insert_node(true, _Next, _Val));
				}
			}

		return (insert_node(_Val).first);	// try usual insert
#pragma warning(pop)
		}

	iterator erase(iterator _Where)
		{	// erase element at _Where
		return (make_iterator(erase_node(get_node(_Where))));
		}

	iterator erase(iterator _First, iterator _Last)
		{	// erase [_First, _Last)
		node_type^ _First_node = get_node(_First);
		node_type^ _Last_node = get_node(_Last);

		if (_First_node == front_node() && _Last_node == head_node())
			clear();	// erase all
		else
			for (; _First_node != _Last_node; )
				_First_node = erase_node(_First_node);
		return (_Last);
		}

	size_type erase(key_type _Keyval)
		{	// erase and count all that match _Keyval
		node_type^ _First = lower_bound_node(_Keyval);
		node_type^ _Last = upper_bound_node(_Keyval);
		size_type _Num = 0;

		for (; _First != _Last; ++_Num)
			_First = erase_node(_First);	// erase an element matching key
		return (_Num);
		}

	node_type^ erase_node(node_type^ _Where_node)
		{	// erase node _Where
		node_type^ _Where = (node_type^)_Where_node;
		node_type^ _Next = _Where->next_node();	// for return value
		node_type^ _Fixnode;	// the node to recolor as needed
		node_type^ _Fixnodeparent;	// parent of _Fixnode (may be nil)
		node_type^ _Node = _Where;	// the node to erase

		if (_Where->container() != this)
			throw gcnew System::InvalidOperationException();

		if (_Node->_Left->is_head())
			_Fixnode = _Node->_Right;	// must stitch up right subtree
		else if (_Node->_Right->is_head())
			_Fixnode = _Node->_Left;	// must stitch up left subtree
		else
			{	// two subtrees, must lift successor node to replace erased
			_Node = _Next;	// _Node is successor node
			_Fixnode = _Node->_Right;	// _Fixnode is its only subtree
			}

		if (_Node == _Where)
			{	// at most one subtree, relink it
			_Fixnodeparent = _Where->_Parent;
			if (!_Fixnode->is_head())
				_Fixnode->_Parent = _Fixnodeparent;	// link up

			if (root_node() == _Where)
				head_node()->_Parent = _Fixnode;	// link down from root
			else if (_Fixnodeparent->_Left == _Where)
				_Fixnodeparent->_Left = _Fixnode;	// link down to left
			else
				_Fixnodeparent->_Right = _Fixnode;	// link down to right

			if (front_node() == _Where)
				head_node()->_Left = _Fixnode->is_head()
					? _Fixnodeparent	// smallest is parent of erased node
					: _Fixnode->min_node();	// smallest in relinked subtree

			if (back_node() == _Where)
				head_node()->_Right = _Fixnode->is_head()
					? _Fixnodeparent	// largest is parent of erased node
					: _Fixnode->max_node();	// largest in relinked subtree
			}
		else
			{	// erased has two subtrees, _Node is successor to erased
			_Where->_Left->_Parent = _Node;	// link left up
			_Node->_Left = _Where->_Left;	// link successor down

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

			if (root_node() == _Where)
				head_node()->_Parent = _Node;	// link down from root
			else if (_Where->_Parent->_Left == _Where)
				_Where->_Parent->_Left = _Node;	// link down to left
			else
				_Where->_Parent->_Right = _Node;	// link down to right

			_Node->_Parent = _Where->_Parent;	// link successor up

			signed char _Color = _Node->_Color;

			_Node->_Color = _Where->_Color;
			_Where->_Color = _Color;	// recolor it
			}

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

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

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

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

			_Fixnode->_Color = _Black;	// ensure stopping node is black
			}

		_Mybase_t::unmake_value(_Where->_Myval);
		_Where->_Head = nullptr;	// orphan corresponding iterators
		--_Mysize;
		++_Mygen;
		return (_Next);
		}

	void clear()
		{	// erase all
		for (; front_node() != head_node(); )
			erase_node(front_node());
		}

	void swap(_Mytype_t% _Right)
		{	// exchange contents with _Right
		if ((Object^)this != %_Right)
			{	// worth doing, swap
			tree^ _Temp = gcnew tree(_Right);

			_Right._Copy(this);
			_Copy(_Temp);
			}
		}

	// searches
	iterator find(key_type _Keyval)
		{	// find an element that matches _Keyval, return iterator
		node_type^ _Where = lower_bound_node(_Keyval);

		return (make_iterator(_Where == head_node()
			|| this->comp(_Keyval, _Key(_Where))
				? head_node() : _Where));
		}

	size_type count(key_type _Keyval)
		{	// count all elements that match _Keyval
		node_type^ _First = lower_bound_node(_Keyval);
		node_type^ _Last = upper_bound_node(_Keyval);
		size_type _Num = 0;

		for (; _First != _Last; _First = _First->next_node())
			++_Num;
		return (_Num);
		}

	iterator lower_bound(key_type _Keyval)
		{	// find leftmost node not less than _Keyval
		return (make_iterator(lower_bound_node(_Keyval)));
		}

	node_type^ lower_bound_node(key_type _Keyval)
		{	// find leftmost node not less than _Keyval
		node_type^ _Node = root_node();
		node_type^ _Where = head_node();	// end() if search fails

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

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

	iterator upper_bound(key_type _Keyval)
		{	// find leftmost node greater than _Keyval
		return (make_iterator(upper_bound_node(_Keyval)));
		}

	node_type^ upper_bound_node(key_type _Keyval)
		{	// find leftmost node greater than _Keyval
		node_type^ _Node = root_node();
		node_type^ _Where = head_node();	// end() if search fails

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

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

	pair_iter_iter equal_range(key_type _Keyval)
		{	// find range equivalent to _Keyval
		_Pairnn _Ans = equal_range_node(_Keyval);
		return (pair_iter_iter(iterator(_Ans.first),
			iterator(_Ans.second)));
		}

	_Pairnn equal_range_node(key_type _Keyval)
		{	// find range equivalent to _Keyval
		return (_Pairnn(lower_bound_node(_Keyval),
			upper_bound_node(_Keyval)));
		}

_STLCLR_FIELD_ACCESS:
	node_type^ _Buynode()
		{	// allocate a head node and set links
		node_type^ _Node = gcnew node_type;

		_Node->_Left = _Node;
		_Node->_Parent = _Node;
		_Node->_Right = _Node;
		_Node->_Head = _Node;
		_Node->_Color = _Black;
		_Node->_Mycont = this;
		return (_Node);
		}

	node_type^ _Buynode(node_type^ _Larg, node_type^ _Parg,
		node_type^ _Rarg, value_type _Val, signed char _Carg)
		{	// allocate a node and set links
		node_type^ _Node = gcnew node_type(
				_Larg, _Parg, _Rarg, _Myhead, _Val, _Carg);

		return (_Node);
		}

	void _Chown(node_type^ _Node, node_type^ _Head, tree^ _Owner)
		{	// change ownership of subtree
		if (_Node->_Left->is_head())
			_Node->_Left = _Head;
		else
			_Chown(_Node->_Left, _Head, _Owner);

		if (_Node->_Right->is_head())
			_Node->_Right = _Head;
		else
			_Chown(_Node->_Right, _Head, _Owner);

		if (_Node->is_head())
			_Node->_Parent = _Head;

		_Node->_Mycont = _Owner;
		}

	void _Copy(tree^ _Right)
		{	// copy entire tree from _Right
		_Myhead->_Parent = _Copy(_Right->root_node(), head_node());
		_Mysize = _Right->size();
		if (!root_node()->is_head())
			{	// nonempty tree, look for new smallest and largest
			head_node()->_Left = root_node()->min_node();
			head_node()->_Right = root_node()->max_node();
			}
		else
			{	// empty tree, cauterize smallest and largest
			head_node()->_Left = head_node();
			head_node()->_Right = head_node();
			}
		++_Mygen;
		}

	node_type^ _Copy(node_type^ _Oldroot,
		node_type^ _Newparent)
		{	// copy entire subtree, recursively
		node_type^ _Newroot = head_node();

		if (!_Oldroot->is_head())
			{	// copy a node, then any subtrees
			node_type^ _Node = _Buynode(head_node(), _Newparent,
				head_node(), _Oldroot->_Myval, _Oldroot->_Color);

			if (_Newroot->is_head())
				_Newroot = _Node;	// memorize new root first time

			_Node->_Left = _Copy(_Oldroot->_Left, _Node);
			_Node->_Right = _Copy(_Oldroot->_Right, _Node);