?? xtree
字號:
// 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())
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -