cliext::impl::tree< _Traits_t > Class Template Reference

Inheritance diagram for cliext::impl::tree< _Traits_t >:

Public Types
typedef tree< _Traits_t >	_Mytype_t
typedef _Traits_t	_Mybase_t
typedef _Traits_t::key_type	_Key_t
typedef _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 _Traits_t::key_type	key_type
typedef _Traits_t::value_type	value_type
typedef _Traits_t::key_compare	key_compare
typedef _Traits_t::value_compare	value_compare
typedef int	size_type
typedef int	difference_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

Public Member Functions
	tree ()
	tree (tree%_Right)
tree	operator= (tree%_Right)
	operator _Mycont_it^ ()
	tree (key_compare^_Pred)
	~tree ()
unsigned long	get_generation ()
node_type	get_node (iterator _Where)
node_type	front_node ()
node_type	back_node ()
node_type	root_node ()
node_type	head_node ()
_Myarray_t	to_array ()
key_compare	key_comp () new
value_compare	value_comp () new
iterator	make_iterator (node_type^_Node)
iterator	begin ()
iterator	end ()
reverse_iterator	rbegin ()
reverse_iterator	rend ()
size_type	size ()
bool	empty ()
pair_iter_bool	insert (value_type _Val)
iterator	insert (iterator _Where, value_type _Val)
template<typename _Iter_t >
void	insert (_Iter_t _First, _Iter_t _Last)
void	insert (_STLCLR Generic::IInputIterator< _Value_t >^_First, _STLCLR Generic::IInputIterator< _Value_t >^_Last)
void	insert (_Myenum_it^_Right)
void	insert_iter (_STLCLR Generic::IInputIterator< _Value_t >^_First, _STLCLR Generic::IInputIterator< _Value_t >^_Last)
_Pairnb	insert_node (value_type _Val)
node_type	insert_node (node_type^_Where_node, value_type _Val)
iterator	erase (iterator _Where)
iterator	erase (iterator _First, iterator _Last)
size_type	erase (key_type _Keyval)
node_type	erase_node (node_type^_Where_node)
void	clear ()
void	swap (_Mytype_t%_Right)
iterator	find (key_type _Keyval)
size_type	count (key_type _Keyval)
iterator	lower_bound (key_type _Keyval)
node_type	lower_bound_node (key_type _Keyval)
iterator	upper_bound (key_type _Keyval)
node_type	upper_bound_node (key_type _Keyval)
pair_iter_iter	equal_range (key_type _Keyval)
_Pairnn	equal_range_node (key_type _Keyval)
	return (_Node)
node_type	_Buynode (node_type^_Larg, node_type^_Parg, node_type^_Rarg, value_type _Val, signed char _Carg)
void	_Chown (node_type^_Node, node_type^_Head, tree^_Owner)
void	_Copy (tree^_Right)
node_type	_Copy (node_type^_Oldroot, node_type^_Newparent)
void	_Init ()
node_type	_Insert_node (bool _Addleft, node_type^_Where, value_type _Val)
key_type	_Key (node_type^_Where)
void	_Lrotate (node_type^_Where)
void	_Rrotate (node_type^_Where)
virtual System::Object	Clone ()

Public Attributes
_STLCLR_FIELD_ACCESS	__pad0__: node_type^ _Buynode() { node_type^ _Node = gcnew node_type
_Node	_Left = _Node
_Node	_Parent = _Node
_Node	_Right = _Node
_Node	_Head = _Node
_Node	_Color = _Black
_Node	_Mycont = this
node_type	_Myhead
size_type	_Mysize
unsigned long	_Mygen

Static Public Attributes
static const int	_Maxsize = MAX_CONTAINER_SIZE
static const int	_Black = 0
static const int	_Red = 1

Private Attributes
property size_type	Count
property bool	IsSynchronized
property System::Object	SyncRoot

Member Typedef Documentation

template<typename _Traits_t>

typedef _Traits_t::key_type cliext::impl::tree< _Traits_t >::_Key_t

template<typename _Traits_t>

typedef cli::array<_Value_t> cliext::impl::tree< _Traits_t >::_Myarray_t

template<typename _Traits_t>

typedef _Traits_t cliext::impl::tree< _Traits_t >::_Mybase_t

template<typename _Traits_t>

typedef _STLCLR ITree<_Key_t, _Value_t> cliext::impl::tree< _Traits_t >::_Mycont_it

template<typename _Traits_t>

typedef System::Collections::Generic::IEnumerable<_Value_t> cliext::impl::tree< _Traits_t >::_Myenum_it

template<typename _Traits_t>

typedef tree<_Traits_t> cliext::impl::tree< _Traits_t >::_Mytype_t

template<typename _Traits_t>

typedef _STLCLR GenericPair<node_type^, bool> cliext::impl::tree< _Traits_t >::_Pairnb

template<typename _Traits_t>

typedef _STLCLR GenericPair<node_type^, node_type^> cliext::impl::tree< _Traits_t >::_Pairnn

template<typename _Traits_t>

typedef _Traits_t::value_type cliext::impl::tree< _Traits_t >::_Value_t

template<typename _Traits_t>

typedef ConstBidirectionalIterator<_Mytype_t> cliext::impl::tree< _Traits_t >::const_iterator

template<typename _Traits_t>

typedef value_type cliext::impl::tree< _Traits_t >::const_reference

template<typename _Traits_t>

typedef ReverseBidirectionalIterator<_Mytype_t> cliext::impl::tree< _Traits_t >::const_reverse_iterator

template<typename _Traits_t>

typedef int cliext::impl::tree< _Traits_t >::difference_type

template<typename _Traits_t>

typedef _Mycont_it cliext::impl::tree< _Traits_t >::generic_container

template<typename _Traits_t>

typedef _STLCLR Generic::ContainerBidirectionalIterator<_Value_t> cliext::impl::tree< _Traits_t >::generic_iterator

template<typename _Traits_t>

typedef _STLCLR GenericPair<generic_iterator^, bool> cliext::impl::tree< _Traits_t >::generic_pair_iter_bool

template<typename _Traits_t>

typedef _STLCLR GenericPair<generic_iterator^, generic_iterator^> cliext::impl::tree< _Traits_t >::generic_pair_iter_iter

template<typename _Traits_t>

typedef _STLCLR Generic::ReverseBidirectionalIterator<_Value_t> cliext::impl::tree< _Traits_t >::generic_reverse_iterator

template<typename _Traits_t>

typedef value_type cliext::impl::tree< _Traits_t >::generic_value

template<typename _Traits_t>

typedef BidirectionalIterator<_Mytype_t> cliext::impl::tree< _Traits_t >::iterator

template<typename _Traits_t>

typedef _Traits_t::key_compare cliext::impl::tree< _Traits_t >::key_compare

template<typename _Traits_t>

typedef _Traits_t::key_type cliext::impl::tree< _Traits_t >::key_type

template<typename _Traits_t>

typedef tree_node<_Key_t, _Value_t> cliext::impl::tree< _Traits_t >::node_type

template<typename _Traits_t>

typedef _STLCLR GenericPair<iterator, bool> cliext::impl::tree< _Traits_t >::pair_iter_bool

template<typename _Traits_t>

typedef _STLCLR GenericPair<iterator, iterator> cliext::impl::tree< _Traits_t >::pair_iter_iter

template<typename _Traits_t>

typedef value_type cliext::impl::tree< _Traits_t >::reference

template<typename _Traits_t>

typedef ReverseBidirectionalIterator<_Mytype_t> cliext::impl::tree< _Traits_t >::reverse_iterator

template<typename _Traits_t>

typedef int cliext::impl::tree< _Traits_t >::size_type

template<typename _Traits_t>

typedef _Traits_t::value_compare cliext::impl::tree< _Traits_t >::value_compare

template<typename _Traits_t>

typedef _Traits_t::value_type cliext::impl::tree< _Traits_t >::value_type

Constructor & Destructor Documentation

template<typename _Traits_t>

cliext::impl::tree< _Traits_t >::tree ( )

inline

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

template<typename _Traits_t>

cliext::impl::tree< _Traits_t >::tree ( tree< _Traits_t >%  _Right )

inline

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

template<typename _Traits_t>

cliext::impl::tree< _Traits_t >::tree ( key_compare^  _Pred )

inlineexplicit

        :   _Mybase_t(_Pred)
        {   // construct empty tree from comparator
        _Init();
        }

template<typename _Traits_t>

cliext::impl::tree< _Traits_t >::~tree ( )

inline

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

Member Function Documentation

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::_Buynode ( node_type^  _Larg, node_type^  _Parg, node_type^  _Rarg, value_type  _Val, signed char  _Carg  )

inline

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

        return (_Node);
        }

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::_Chown ( node_type^  _Node, node_type^  _Head, tree< _Traits_t >^  _Owner  )

inline

        {   // 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;
        }

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::_Copy ( tree< _Traits_t >^  _Right )

inline

        {   // 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;
        }

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::_Copy ( node_type^  _Oldroot, node_type^  _Newparent  )

inline

        {   // 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);
            }
        return (_Newroot);
        }

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::_Init ( )

inline

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

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::_Insert_node ( bool  _Addleft, node_type^  _Where, value_type  _Val  )

inline

        {   // 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);
        }

template<typename _Traits_t>

key_type cliext::impl::tree< _Traits_t >::_Key ( node_type^  _Where )

inline

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

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::_Lrotate ( node_type^  _Where )

inline

        {   // 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;
        }

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::_Rrotate ( node_type^  _Where )

inline

        {   // 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;
        }

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::back_node ( )

inline

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

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::begin ( )

inline

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

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::clear ( )

inline

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

template<typename _Traits_t>

virtual System::Object cliext::impl::tree< _Traits_t >::Clone ( )

inlinevirtual

Reimplemented in cliext::multimap< _Key1_t, _Mapped_t >, cliext::map< _Key1_t, _Mapped_t >, cliext::multiset< _Key1_t >, and cliext::set< _Key1_t >.

        {   // clone the tree
        return (gcnew tree(*this));
        }

template<typename _Traits_t>

size_type cliext::impl::tree< _Traits_t >::count ( key_type  _Keyval )

inline

        {   // 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);
        }

template<typename _Traits_t>

bool cliext::impl::tree< _Traits_t >::empty ( )

inline

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

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::end ( )

inline

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

template<typename _Traits_t>

pair_iter_iter cliext::impl::tree< _Traits_t >::equal_range ( key_type  _Keyval )

inline

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

template<typename _Traits_t>

_Pairnn cliext::impl::tree< _Traits_t >::equal_range_node ( key_type  _Keyval )

inline

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

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::erase ( iterator  _Where )

inline

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

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::erase ( iterator  _First, iterator  _Last  )

inline

        {   // 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);
        }

template<typename _Traits_t>

size_type cliext::impl::tree< _Traits_t >::erase ( key_type  _Keyval )

inline

        {   // 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);
        }

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::erase_node ( node_type^  _Where_node )

inline

        {   // 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);
        }

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::find ( key_type  _Keyval )

inline

        {   // 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));
        }

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::front_node ( )

inline

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

template<typename _Traits_t>

unsigned long cliext::impl::tree< _Traits_t >::get_generation ( )

inline

        {   // get underlying container generation
        return (_Mygen);
        }

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::get_node ( iterator  _Where )

inline

        {   // 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);
        }

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::head_node ( )

inline

        {   // get head node
        return (_Myhead);
        }

template<typename _Traits_t>

pair_iter_bool cliext::impl::tree< _Traits_t >::insert ( value_type  _Val )

inline

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

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

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::insert ( iterator  _Where, value_type  _Val  )

inline

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

template<typename _Traits_t>

template<typename _Iter_t >

void cliext::impl::tree< _Traits_t >::insert ( _Iter_t  _First, _Iter_t  _Last  )

inline

        {   // 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)
        }

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::insert ( _STLCLR Generic::IInputIterator< _Value_t >^  _First, _STLCLR Generic::IInputIterator< _Value_t >^  _Last  )

inline

        {   // 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)
        }

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::insert ( _Myenum_it^  _Right )

inline

        {   // 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
        }

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::insert_iter ( _STLCLR Generic::IInputIterator< _Value_t >^  _First, _STLCLR Generic::IInputIterator< _Value_t >^  _Last  )

inline

        {   // 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())
                _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)
        }

template<typename _Traits_t>

_Pairnb cliext::impl::tree< _Traits_t >::insert_node ( value_type  _Val )

inline

        {   // 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)
        }

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::insert_node ( node_type^  _Where_node, value_type  _Val  )

inline

        {   // 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)
        }

template<typename _Traits_t>

key_compare cliext::impl::tree< _Traits_t >::key_comp ( )

inlinenew

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

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::lower_bound ( key_type  _Keyval )

inline

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

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::lower_bound_node ( key_type  _Keyval )

inline

        {   // 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
        }

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::make_iterator ( node_type^  _Node )

inline

        {   // return iterator for node
        return (iterator(_Node));
        }

template<typename _Traits_t>

cliext::impl::tree< _Traits_t >::operator _Mycont_it^ ( )

inline

        {   // convert to interface
        return (this);
        }

template<typename _Traits_t>

tree cliext::impl::tree< _Traits_t >::operator= ( tree< _Traits_t >%  _Right )

inline

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

template<typename _Traits_t>

reverse_iterator cliext::impl::tree< _Traits_t >::rbegin ( )

inline

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

template<typename _Traits_t>

reverse_iterator cliext::impl::tree< _Traits_t >::rend ( )

inline

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

template<typename _Traits_t>

cliext::impl::tree< _Traits_t >::return

(

_Node

)

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::root_node ( )

inline

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

template<typename _Traits_t>

size_type cliext::impl::tree< _Traits_t >::size ( )

inline

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

template<typename _Traits_t>

void cliext::impl::tree< _Traits_t >::swap ( _Mytype_t%  _Right )

inline

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

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

template<typename _Traits_t>

_Myarray_t cliext::impl::tree< _Traits_t >::to_array ( )

inline

        {   // 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);
        }

template<typename _Traits_t>

iterator cliext::impl::tree< _Traits_t >::upper_bound ( key_type  _Keyval )

inline

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

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::upper_bound_node ( key_type  _Keyval )

inline

        {   // 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
        }

template<typename _Traits_t>

value_compare cliext::impl::tree< _Traits_t >::value_comp ( )

inlinenew

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

Member Data Documentation

template<typename _Traits_t>

_STLCLR_FIELD_ACCESS cliext::impl::tree< _Traits_t >::__pad0__

template<typename _Traits_t>

const int cliext::impl::tree< _Traits_t >::_Black = 0

static

template<typename _Traits_t>

_Node cliext::impl::tree< _Traits_t >::_Color = _Black

template<typename _Traits_t>

_Node cliext::impl::tree< _Traits_t >::_Head = _Node

template<typename _Traits_t>

_Node cliext::impl::tree< _Traits_t >::_Left = _Node

template<typename _Traits_t>

const int cliext::impl::tree< _Traits_t >::_Maxsize = MAX_CONTAINER_SIZE

static

template<typename _Traits_t>

_Node cliext::impl::tree< _Traits_t >::_Mycont = this

template<typename _Traits_t>

unsigned long cliext::impl::tree< _Traits_t >::_Mygen

template<typename _Traits_t>

node_type cliext::impl::tree< _Traits_t >::_Myhead

template<typename _Traits_t>

size_type cliext::impl::tree< _Traits_t >::_Mysize

template<typename _Traits_t>

_Node cliext::impl::tree< _Traits_t >::_Parent = _Node

template<typename _Traits_t>

const int cliext::impl::tree< _Traits_t >::_Red = 1

static

template<typename _Traits_t>

_Node cliext::impl::tree< _Traits_t >::_Right = _Node

template<typename _Traits_t>

property size_type cliext::impl::tree< _Traits_t >::Count

private

Initial value:

{   
        virtual size_type get() sealed
            = System::Collections::ICollection::Count::get
            {   
            return (size());
            }
        }

template<typename _Traits_t>

property bool cliext::impl::tree< _Traits_t >::IsSynchronized

private

Initial value:

{   
        virtual bool get() sealed
            = System::Collections::ICollection::IsSynchronized::get
            {   
            return (false);
            }
        }

template<typename _Traits_t>

property System::Object cliext::impl::tree< _Traits_t >::SyncRoot

private

Initial value:

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

---

The documentation for this class was generated from the following file:

• VS2013/inc/cliext/xtree