|
|
|
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 |
|
|
|
|
|