This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Implementing normal algorithms using predicate versions
chris <caj@cs.york.ac.uk> writes:
| Paolo Carlini wrote:
|
| > chris wrote:
| >
| >> I was intending on using something like (warning: away from C++
| >> compiler, I haven't even compiled this code!)
| >>
| >> template<typename __T1, typename __T2>
| >> struct __default_predicate {
| >> bool
| >> operator()(const __T1& __t1, const __T2& __t2) { return __t1<__t2;}
| >> };
| >
| >
| > Ah, yes, this - or slight variations - look good. Maybe we should
| > discuss a bit
| > more the optimization thing and then, possibly, actually implement
| > the idea
| > in v7... :)
| >
| While we are discussing optimisations, I wonder if a liberal spreading
| of "inline" might not be useful? I'm not so much thinking about
I don't know. We should be careful in applying "inline". We should
not throw it randomly. I'm immune against the idea that programmers
should randomly throw "inline" and expect the compiler to randomly
apply his own idea of "inline".
In particular, I've been wondering for a long time whether we really
really want the following (in 3.3.x) to be inline :-)
inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*&
__root)
{
__x->_M_color = _M_red;
while (__x != __root
&& __x->_M_parent->_M_color == _M_red)
{
if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left)
{
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
if (__y && __y->_M_color == _M_red)
{
__x->_M_parent->_M_color = _M_black;
__y->_M_color = _M_black;
__x->_M_parent->_M_parent->_M_color = _M_red;
__x = __x->_M_parent->_M_parent;
}
else
{
if (__x == __x->_M_parent->_M_right)
{
__x = __x->_M_parent;
_Rb_tree_rotate_left(__x, __root);
}
__x->_M_parent->_M_color = _M_black;
__x->_M_parent->_M_parent->_M_color = _M_red;
_Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
}
}
else
{
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
if (__y && __y->_M_color == _M_red)
{
__x->_M_parent->_M_color = _M_black;
__y->_M_color = _M_black;
__x->_M_parent->_M_parent->_M_color = _M_red;
__x = __x->_M_parent->_M_parent;
}
else
{
if (__x == __x->_M_parent->_M_left)
{
__x = __x->_M_parent;
_Rb_tree_rotate_right(__x, __root);
}
__x->_M_parent->_M_color = _M_black;
__x->_M_parent->_M_parent->_M_color = _M_red;
_Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
}
}
}
__root->_M_color = _M_black;
}
inline _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
_Rb_tree_node_base*& __root,
_Rb_tree_node_base*& __leftmost,
_Rb_tree_node_base*& __rightmost)
{
_Rb_tree_node_base* __y = __z;
_Rb_tree_node_base* __x = 0;
_Rb_tree_node_base* __x_parent = 0;
if (__y->_M_left == 0) // __z has at most one non-null child. y == z.
__x = __y->_M_right; // __x might be null.
else
if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
__x = __y->_M_left; // __x is not null.
else
{
// __z has two non-null children. Set __y to
__y = __y->_M_right; // __z's successor. __x might be null.
while (__y->_M_left != 0)
__y = __y->_M_left;
__x = __y->_M_right;
}
if (__y != __z)
{
// relink y in place of z. y is z's successor
__z->_M_left->_M_parent = __y;
__y->_M_left = __z->_M_left;
if (__y != __z->_M_right)
{
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
__y->_M_parent->_M_left = __x; // __y must be a child of _M_left
__y->_M_right = __z->_M_right;
__z->_M_right->_M_parent = __y;
}
else
__x_parent = __y;
if (__root == __z)
__root = __y;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __y;
else
__z->_M_parent->_M_right = __y;
__y->_M_parent = __z->_M_parent;
std::swap(__y->_M_color, __z->_M_color);
__y = __z;
// __y now points to node to be actually deleted
}
else
{ // __y == __z
__x_parent = __y->_M_parent;
if (__x)
__x->_M_parent = __y->_M_parent;
if (__root == __z)
__root = __x;
else
if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __x;
else
__z->_M_parent->_M_right = __x;
if (__leftmost == __z)
if (__z->_M_right == 0) // __z->_M_left must be null also
__leftmost = __z->_M_parent;
// makes __leftmost == _M_header if __z == __root
else
__leftmost = _Rb_tree_node_base::_S_minimum(__x);
if (__rightmost == __z)
if (__z->_M_left == 0) // __z->_M_right must be nul also
__rightmost = __z->_M_parent;
// makes __rightmost == _M_header if __z == __root
else // __x == __z->_M_left
__rightmost = _Rb_tree_node_base::_S_maximum(__x);
}
if (__y->_M_color != _M_red)
{
while (__x != __root && (__x == 0 || __x->_M_color == _M_black))
if (__x == __x_parent->_M_left)
{
_Rb_tree_node_base* __w = __x_parent->_M_right;
if (__w->_M_color == _M_red)
{
__w->_M_color = _M_black;
__x_parent->_M_color = _M_red;
_Rb_tree_rotate_left(__x_parent, __root);
__w = __x_parent->_M_right;
}
if ((__w->_M_left == 0 ||
__w->_M_left->_M_color == _M_black) &&
(__w->_M_right == 0 ||
__w->_M_right->_M_color == _M_black))
{
__w->_M_color = _M_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
}
else
{
if (__w->_M_right == 0
|| __w->_M_right->_M_color == _M_black)
{
__w->_M_left->_M_color = _M_black;
__w->_M_color = _M_red;
_Rb_tree_rotate_right(__w, __root);
__w = __x_parent->_M_right;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _M_black;
if (__w->_M_right)
__w->_M_right->_M_color = _M_black;
_Rb_tree_rotate_left(__x_parent, __root);
break;
}
}
else
{
// same as above, with _M_right <-> _M_left.
_Rb_tree_node_base* __w = __x_parent->_M_left;
if (__w->_M_color == _M_red)
{
__w->_M_color = _M_black;
__x_parent->_M_color = _M_red;
_Rb_tree_rotate_right(__x_parent, __root);
__w = __x_parent->_M_left;
}
if ((__w->_M_right == 0 ||
__w->_M_right->_M_color == _M_black) &&
(__w->_M_left == 0 ||
__w->_M_left->_M_color == _M_black))
{
__w->_M_color = _M_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
}
else
{
if (__w->_M_left == 0 || __w->_M_left->_M_color == _M_black)
{
__w->_M_right->_M_color = _M_black;
__w->_M_color = _M_red;
_Rb_tree_rotate_left(__w, __root);
__w = __x_parent->_M_left;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _M_black;
if (__w->_M_left)
__w->_M_left->_M_color = _M_black;
_Rb_tree_rotate_right(__x_parent, __root);
break;
}
}
if (__x) __x->_M_color = _M_black;
}
return __y;
}
:-)
-- Gaby