_tree.cc

realview22.rar

        __z->_C_parent()->_C_right() = __y;

      __y->_C_parent() = __z->_C_parent();
      if (!(void*)__x)
        __x = __y;       // Don't want to start balancing with nil

      _STD::swap(__y->_C_color(), __z->_C_color());

      __y = __z;        // __y points to node to be actually deleted.
    }
    else if (!__deleted) {
      //
      // __y == __z
      //
      __x->_C_parent() = __y->_C_parent();   
      if (_C_root() == __z)
        _C_root() = __x;
      else  {
        if (__z->_C_parent()->_C_left() == __z)
          __z->_C_parent()->_C_left() = __x;
        else
          __z->_C_parent()->_C_right() = __x;
      }
      if (_C_leftmost() == __z)  {
        if (!(void*)__z->_C_right())  // __z->_C_left() must be NIL also.
          _C_leftmost() = __z->_C_parent();
        else
          _C_leftmost() = _C_node_t::_C_minimum(__x);
      }
      if (_C_rightmost() == __z)   {
        if (!(void*)__z->_C_left()) // __z->_C_right() must be NIL also.
          _C_rightmost() = __z->_C_parent();
        else
          _C_rightmost() = _C_node_t::_C_maximum(__x);
      }
    }
    if (__x != _C_header && __y->_C_color() != _C_node_t::_C_red) {
      while (__x != _C_root() && __x->_C_color() == _C_node_t::_C_black) {
        if (__x == __x->_C_parent()->_C_left()) {
          _C_link_t __w = __x->_C_parent()->_C_right();
          if (!(void*)__w) {
            __x->_C_color() = _C_node_t::_C_red;
            __x = __x->_C_parent();
          }
          else {
            if (__w->_C_color() == _C_node_t::_C_red) {
              __w->_C_color()         = _C_node_t::_C_black;
              __x->_C_parent()->_C_color() = _C_node_t::_C_red;
              __rotate_left(__x->_C_parent());
              __w = __x->_C_parent()->_C_right();
            }
            if (!(void*)__w) {
              __x->_C_color() = _C_node_t::_C_red;
              __x = __x->_C_parent();
            }
            else if ((   !(void*)__w->_C_left()
                      || __w->_C_left()->_C_color() == _C_node_t::_C_black) && 
                     (  !(void*)__w->_C_right()
                      || __w->_C_right()->_C_color() == _C_node_t::_C_black)) {
              __w->_C_color() = _C_node_t::_C_red;
              __x = __x->_C_parent();
            }
            else {
              if (   !(void*)__w->_C_right()
                  || __w->_C_right()->_C_color() == _C_node_t::_C_black) {
                if ((void*)__w->_C_left())
                  __w->_C_left()->_C_color() = _C_node_t::_C_black;
                __w->_C_color()       = _C_node_t::_C_red;
                __rotate_right(__w);
                __w = __x->_C_parent()->_C_right();
              }
              if ((void*)__w) {
                __w->_C_color() = __x->_C_parent()->_C_color();
                __x->_C_parent()->_C_color() = _C_node_t::_C_black;
                if ((void*)__w->_C_right())
                  __w->_C_right()->_C_color()  = _C_node_t::_C_black;
                __rotate_left(__x->_C_parent());
              }
              break;
            }
          }
        }
        else {
          //
          // Same as then clause with "right" and "left" exchanged.
          //
          _C_link_t __w = __x->_C_parent()->_C_left();
          if (!(void*)__w) {
            __x->_C_color() = _C_node_t::_C_red;
            __x = __x->_C_parent();
          }
          else {
            if (__w->_C_color() == _C_node_t::_C_red) {
              __w->_C_color()         = _C_node_t::_C_black;
              __x->_C_parent()->_C_color() = _C_node_t::_C_red;
              __rotate_right(__x->_C_parent());
              __w = __x->_C_parent()->_C_left();
            }
            if (!(void*)__w) {
              __x->_C_color() = _C_node_t::_C_red;
              __x = __x->_C_parent();
            }
            else if (   (   !(void*)__w->_C_right()
                         || __w->_C_right()->_C_color() == _C_node_t::_C_black)
                     && (   !(void*)__w->_C_left()
                         || __w->_C_left()->_C_color() == _C_node_t::_C_black)) {
              __w->_C_color() = _C_node_t::_C_red; __x = __x->_C_parent();
            }
            else {
              if (   !(void*)__w->_C_left()
                  || __w->_C_left()->_C_color() == _C_node_t::_C_black) {
                if ((void*)__w->_C_right())
                  __w->_C_right()->_C_color() = _C_node_t::_C_black;
                __w->_C_color()        = _C_node_t::_C_red;
                __rotate_left(__w);
                __w = __x->_C_parent()->_C_left();
              }
              if ((void*)__w) {
                __w->_C_color() = __x->_C_parent()->_C_color();
                __x->_C_parent()->_C_color() = _C_node_t::_C_black;
                if ((void*)__w->_C_left())
                  __w->_C_left()->_C_color()   = _C_node_t::_C_black;
                __rotate_right(__x->_C_parent());
              }
              break;
            }
          }
        }
      }
      __x->_C_color() = _C_node_t::_C_black;
    }
    _C_put_node(__y);
    --_C_node_count;
    return __tmp;
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (const _Key& __x)
{
    _STD::pair<iterator, iterator> __p = equal_range(__x);
    size_type __n = _DISTANCE(__p.first, __p.second, size_type);
    erase(__p.first, __p.second);
    return __n;
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_link_t 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
_C_copy (_C_link_t __x, _C_link_t __p)
{
    // Structural copy.
    _C_link_t __res = __x;

    while ((void*)__x) {
      _C_link_t __y = _C_get_node(__x->_C_value());
      if (__res == __x)
          __res = __y;  // Save for return value.

      __p->_C_left()   = __y;
      __y->_C_parent() = __p;
      __y->_C_color()  = __x->_C_color();
      __y->_C_right()  = _C_copy(__x->_C_right(), __y);
      __p              = __y;
      __x              = __x->_C_left();
    }
    __p->_C_left() = 0;
    return __res;
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_erase (_C_link_t __x)
{
    //
    // Erase without rebalancing.
    //
    while ((void*)__x) {
        _C_erase(__x->_C_right());
        _C_link_t __y = __x->_C_left();
        _C_put_node(__x);
        __x = __y;
    }
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (iterator __first, 
                                                     iterator __last)
{
    _RWSTD_ASSERT_RANGE (begin (), __first);
    _RWSTD_ASSERT_RANGE (__first, __last);

    iterator __tmp = end();
    if (__first == begin() && __last == end() && _C_node_count != 0) {
      _C_erase(_C_root());
      _C_leftmost()  = _C_header;
      _C_root()      = 0;
      _C_rightmost() = _C_header;
      _C_node_count  = 0;
      __tmp = end();
    } else {
        while (__first != __last)
            __tmp =  erase(__first++);
    }
    return __tmp;
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::find (const _Key& __k)
{
    _C_link_t __y = _C_header;  // __last node that is not less than __k.
    _C_link_t __x = _C_root();  // Current node.

    while ((void*)__x) {
      if (!_C_key_comp(__x->_C_key(), __k))
        __y = __x, __x = __x->_C_left();
      else
        __x = __x->_C_right();
    }

    iterator __j = _C_make_iter (__y);
    return (   __j == end()
            || _C_key_comp (__k, _ITER_NODE (__j)->_C_key ())) ? end () : __j;
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::lower_bound (const _Key& __k)
{
    _C_link_t __y = _C_header;  // __last node that is not less than __k.
    _C_link_t __x = _C_root();  // Current node.

    while ((void*)__x) {
      if (!_C_key_comp(__x->_C_key(), __k))
        __y = __x, __x = __x->_C_left();
      else
        __x = __x->_C_right();
    }

    return _C_make_iter (__y);
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::upper_bound (const _Key& __k)
{
    _C_link_t __y = _C_header;  // __last node that is greater than __k.
    _C_link_t __x = _C_root();  // Current node.

    while ((void*)__x) {
      if (_C_key_comp(__k,__x->_C_key()))
        __y = __x, __x = __x->_C_left();
      else
        __x = __x->_C_right();
    }

    return _C_make_iter (__y);
}


_RWSTD_NAMESPACE_END   // __rw


#undef _ITER_NODE