|
|
|
| 1 |
|
// xtree stl/clr header |
| 2 |
|
#ifndef _CLI_XTREE_ |
| 3 |
|
#define _CLI_XTREE_ |
| 4 |
|
#include <cliext/functional> // for Binary/UnaryDelegate |
| 5 |
|
#include <cliext/iterator> |
| 6 |
|
|
| 7 |
|
namespace cliext { |
| 8 |
|
namespace impl { |
| 9 |
|
// |
| 10 |
|
// GENERIC REF CLASS tree_node |
| 11 |
|
// |
| 12 |
|
template<typename _Key_t, |
| 13 |
|
typename _Value_t> |
| 14 |
|
ref class tree_node |
| 15 |
|
: public _STLCLR Generic::INode<_Value_t> |
| 16 |
|
{ // tree node |
| 17 |
|
public: |
| 18 |
|
typedef tree_node<_Key_t, _Value_t> _Mytype_t; |
| 19 |
|
typedef _STLCLR Generic::INode<_Value_t> _Mynode_it; |
| 20 |
|
typedef _STLCLR Generic::IBidirectionalContainer<_Value_t> _Mycont_it; |
| 21 |
|
typedef _Value_t value_type; |
| 22 |
|
|
| 23 |
|
tree_node() |
| 24 |
|
{ // construct an empty node |
| 25 |
|
} |
| 26 |
|
|
| 27 |
|
tree_node(_Mytype_t^ _Larg, _Mytype_t^ _Parg, |
| 28 |
|
_Mytype_t^ _Rarg, _Mytype_t^ _Harg, |
| 29 |
|
value_type _Val, signed char _Carg) |
| 30 |
|
: _Left(_Larg), _Parent(_Parg), _Right(_Rarg), |
| 31 |
|
_Head(_Harg), _Myval(_Val), _Color(_Carg), |
| 32 |
|
_Mycont(nullptr) |
| 33 |
|
{ // construct a node with value |
| 34 |
|
} |
| 35 |
|
|
| 36 |
|
_Mycont_it^ container() |
| 37 |
|
{ // return owning container |
| 38 |
|
return (_Head == nullptr ? nullptr : _Head->_Mycont); |
| 39 |
|
} |
| 40 |
|
|
| 41 |
|
bool is_head() |
| 42 |
|
{ // test if head node |
| 43 |
|
return (_Mycont != nullptr); |
| 44 |
|
} |
| 45 |
|
|
| 46 |
|
_Mytype_t^ max_node() |
| 47 |
|
{ // return rightmost node in subtree |
| 48 |
|
_Mytype_t^ _Node = this; |
| 49 |
|
|
| 50 |
|
for (; !_Node->_Right->is_head(); ) |
| 51 |
|
_Node = _Node->_Right; // descend along right subtrees |
| 52 |
|
return (_Node); |
| 53 |
|
} |
| 1410 |
|
_Right.get_key(_Pright->_Myval))) |
| 1411 |
|
return (true); |
| 1412 |
|
else if (_Pred(_Right.get_key(_Pright->_Myval), |
| 1413 |
|
_Left.get_key(_Pleft->_Myval))) |
| 1414 |
|
return (false); |
| 1415 |
|
_Pleft = _Pleft->next_node(); |
| 1416 |
|
_Pright = _Pright->next_node(); |
| 1417 |
|
} |
| 1418 |
|
return (_Idx == _Left.size() && _Idx != _Right.size()); |
| 1419 |
|
} |
| 1420 |
|
|
| 1421 |
|
template<typename _Traits_t> inline |
| 1422 |
|
bool operator>=(cliext::impl::tree<_Traits_t>% _Left, |
| 1423 |
|
cliext::impl::tree<_Traits_t>% _Right) |
| 1424 |
|
{ // test if _Left >= _Right |
| 1425 |
|
return (!(_Left < _Right)); |
| 1426 |
|
} |
| 1427 |
|
|
| 1428 |
|
template<typename _Traits_t> inline |
| 1429 |
|
bool operator>(cliext::impl::tree<_Traits_t>% _Left, |
| 1430 |
|
cliext::impl::tree<_Traits_t>% _Right) |
| 1431 |
|
{ // test if _Left > _Right |
| 1432 |
|
return (_Right < _Left); |
| 1433 |
|
} |
| 1434 |
|
|
| 1435 |
|
template<typename _Traits_t> inline |
| 1436 |
|
bool operator<=(cliext::impl::tree<_Traits_t>% _Left, |
| 1437 |
|
cliext::impl::tree<_Traits_t>% _Right) |
| 1438 |
|
{ // test if _Left <= _Right |
| 1439 |
|
return (!(_Right < _Left)); |
| 1440 |
|
} |
| 1441 |
|
|
| 1442 |
|
// |
| 1443 |
|
// TEMPLATE FUNCTION swap |
| 1444 |
|
// |
| 1445 |
|
template<typename _Traits_t> inline |
| 1446 |
|
void swap(cliext::impl::tree<_Traits_t>% _Left, |
| 1447 |
|
cliext::impl::tree<_Traits_t>% _Right) |
| 1448 |
|
{ // swap two trees |
| 1449 |
|
_Left.swap(_Right); |
| 1450 |
|
} |
| 1451 |
|
} // namespace cliext |
| 1452 |
|
#endif // _CLI_XTREE_ |
| 1453 |
|
|
| 1454 |
|
/* |
| 1455 |
|
* Copyright (c) 2004-2007 by Dinkumware, Ltd. ALL RIGHTS RESERVED. |
| 1456 |
|
* Consult your license regarding permissions and restrictions. |
| 1457 |
|
V5.03:0009 */ |
| 1458 |
|
|
|
|
|