_tree.cc

realview22.rar

/***************************************************************************
 *
 * _tree.cc - Non-inline tree definitions for the Standard Library
 *
 * $Id: _tree.cc,v 1.1.1.1 2002/01/10 17:38:30 vkorstan Exp $
 *
 ***************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 ***************************************************************************
 *
 * Copyright (c) 1994-2001 Rogue Wave Software, Inc.  All Rights Reserved.
 *
 * This computer software is owned by Rogue Wave Software, Inc. and is
 * protected by U.S. copyright laws and other laws and by international
 * treaties.  This computer software is furnished by Rogue Wave Software,
 * Inc. pursuant to a written license agreement and may be used, copied,
 * transmitted, and stored only in accordance with the terms of such
 * license and with the inclusion of the above copyright notice.  This
 * computer software or any other copies thereof may not be provided or
 * otherwise made available to any other person.
 *
 * U.S. Government Restricted Rights.  This computer software is provided
 * with Restricted Rights.  Use, duplication, or disclosure by the
 * Government is subject to restrictions as set forth in subparagraph (c)
 * (1) (ii) of The Rights in Technical Data and Computer Software clause
 * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
 * Commercial Computer Software--Restricted Rights at 48 CFR 52.227-19,
 * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
 * Flatiron Parkway, Boulder, Colorado 80301 USA.
 *
 **************************************************************************/

// for convenience
#define _ITER_NODE(it)   (_ITER_BASE (it)._C_node)


_RWSTD_NAMESPACE_BEGIN (__rw)


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_deallocate_buffers ()
{
    while ((void*)_C_buf_list) {
        _C_buf_ptr_t __tmp = _C_buf_list;
        _C_buf_list        = (_C_buf_ptr_t)(_C_buf_list->_C_next_buffer);
        _C_node_alloc_t(*this).deallocate(__tmp->_C_buffer,__tmp->size);
        _C_buf_alloc_t(*this).deallocate(__tmp,1);
    }
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
operator= (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __x)
{
    if (!(this == &__x)) {
      erase(begin(), end());
      _C_root() = _C_copy(__x._C_root(), _C_header);
      if (!(void*)_C_root()) {
        _C_leftmost()  = _C_header; _C_rightmost() = _C_header;
      }
      else {
        _C_leftmost()  = _C_node_t::_C_minimum(_C_root());
        _C_rightmost() = _C_node_t::_C_maximum(_C_root());
      }
      _C_node_count = __x._C_node_count;
    }
    return *this;
  }


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>::
_C_insert (_C_link_t __x, _C_link_t __y, const _Val& __v)
{
    _C_link_t __z = _C_get_node(__v);
    ++_C_node_count;
    if (   __y == _C_header || (void*)__x
        || _C_key_comp(_KeyOf()(__v), __y->_C_key ())) {
        // Also makes _C_leftmost() = `z' when `y' == _C_header.
        __y->_C_left() = __z;
      if (__y == _C_header) {
        _C_root() = __z; _C_rightmost() = __z;
      }
      else if (__y == _C_leftmost())
        _C_leftmost() = __z;   // Maintain _C_leftmost() pointing to minimum node.
    }
    else {
      __y->_C_right() = __z;
      if (__y == _C_rightmost())
        _C_rightmost() = __z;  // Maintain _C_rightmost() pointing to maximum node.
    }
    __z->_C_parent() = __y;
    __x = __z;  // Recolor and rebalance the tree.
    while (__x != _C_root() && __x->_C_parent()->_C_color() == _C_node_t::_C_red) {
      if (__x->_C_parent() == __x->_C_parent()->_C_parent()->_C_left()) {
        __y = __x->_C_parent()->_C_parent()->_C_right();
        if ((void*)__y && __y->_C_color() == _C_node_t::_C_red) {
          __x->_C_parent()->_C_color()         = _C_node_t::_C_black;
          __y->_C_color()                 = _C_node_t::_C_black;
          __x->_C_parent()->_C_parent()->_C_color() = _C_node_t::_C_red;
          __x                        = __x->_C_parent()->_C_parent();
        }
        else {
          if (__x == __x->_C_parent()->_C_right()) {
            __x = __x->_C_parent(); 
            __rotate_left(__x);
          }
          __x->_C_parent()->_C_color() = _C_node_t::_C_black;
          __x->_C_parent()->_C_parent()->_C_color() = _C_node_t::_C_red;
          __rotate_right(__x->_C_parent()->_C_parent());
        }
      }
      else {
        __y = __x->_C_parent()->_C_parent()->_C_left();
        if ((void*)__y && __y->_C_color() == _C_node_t::_C_red) {
          __x->_C_parent()->_C_color()         = _C_node_t::_C_black;
          __y->_C_color()                 = _C_node_t::_C_black;
          __x->_C_parent()->_C_parent()->_C_color() = _C_node_t::_C_red;
          __x                        = __x->_C_parent()->_C_parent();
        }
        else {
          if (__x == __x->_C_parent()->_C_left()) {
            __x = __x->_C_parent(); 
            __rotate_right(__x);
          }
          __x->_C_parent()->_C_color()         = _C_node_t::_C_black;
          __x->_C_parent()->_C_parent()->_C_color() = _C_node_t::_C_red;
          __rotate_left(__x->_C_parent()->_C_parent());
        }
      }
    }
    _C_root()->_C_color() = _C_node_t::_C_black;
    return _C_make_iter (__z);
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_STD::pair<_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator,
           bool>
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (const _Val& __v)
{
    _C_link_t __y = _C_header;
    _C_link_t __x = _C_root();
    bool _RWSTD_COMP   = true;
    while ((void*)__x) {
        __y         = __x;
        _RWSTD_COMP = _C_key_comp(_KeyOf()(__v), __x->_C_key());
        __x         = _RWSTD_COMP ? __x->_C_left() : __x->_C_right();
    }
    if (_C_insert_always) {
      return _STD::pair<iterator, bool>(_C_insert(__x, __y, __v), true);
    }
    iterator __j = _C_make_iter(__y);   
    if (_RWSTD_COMP) {
      if (__j == begin())   {
        return _STD::pair<iterator, bool>(_C_insert(__x, __y, __v), true);
      }
      else
        --__j;
    }
    if (_C_key_comp (_ITER_NODE (__j)->_C_key (), _KeyOf ()(__v))) {
        return _STD::pair<iterator, bool>(_C_insert(__x, __y, __v), true);
    }
    return _STD::pair<iterator, bool>(__j, false);
}


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>::insert (iterator __it,
                                                      const _Val& __v)
{
    _RWSTD_ASSERT_RANGE (begin (), __it);

    if (__it == begin ()) {
        if (   size() > 0
            && _C_key_comp (_KeyOf()(__v), _ITER_NODE (__it)->_C_key ()))
            return _C_insert (_ITER_NODE (__it), _ITER_NODE (__it), __v);
        return insert(__v).first;
    }
    else if (__it == end()) {
      if (_C_key_comp(_C_rightmost()->_C_key(), _KeyOf()(__v)))
        return _C_insert(0, _C_rightmost(), __v);
      else
        return insert(__v).first;
    }
    else {
        iterator __prev = --__it;
        if (   _C_key_comp (_ITER_NODE (__prev)->_C_key (), _KeyOf ()(__v))
            && _C_key_comp (_KeyOf()(__v), _ITER_NODE (__it)->_C_key ())) {
            if (!(void*)_ITER_NODE (__prev)->_C_right ())
                return _C_insert(0, _ITER_NODE (__prev), __v); 
            return _C_insert (_ITER_NODE (__it), _ITER_NODE (__it), __v);
        }
        return insert (__v).first;
    }
}


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 __it)
{
    _RWSTD_ASSERT_RANGE (begin (), __it);

    iterator __tmp = __it; 

    if (__tmp == end())
        // Attempting to erase an empty container.
        return end ();
    else
        // Retain 'next' __it for return.
        ++__tmp;


    _C_link_t __z (_ITER_NODE (__it));
    _C_link_t __y = __z;
    _C_link_t __x;
    bool __deleted = false;
    if (!(void*)__y->_C_left()) {
      if (!(void*)__y->_C_right()) {
        __x = __y->_C_parent();
        _C_erase_leaf(__y);
        __deleted = true;
      }
      else
        __x = __y->_C_right(); 
    }
    else {
      if (!(void*)__y->_C_right())
        __x = __y->_C_left();
      else {
        __y = __y->_C_right();
        while ((void*)__y->_C_left())
            __y = __y->_C_left();
        __x = __y->_C_right();
      }
    }
    if (!__deleted && __y != __z) {
      //
      // Relink __y in place of __z.
      //
      __z->_C_left()->_C_parent() = __y; 
      __y->_C_left() = __z->_C_left();
      if (__y != __z->_C_right()) {
        if ((void*)__x)
          __x->_C_parent()        = __y->_C_parent();
        __y->_C_parent()->_C_left()  = __x;         // __y must be a left child.
        __y->_C_right()         = __z->_C_right();
        __z->_C_right()->_C_parent() = __y;
      }
      else if ((void*)__x)
        __x->_C_parent() = __y;  

      if (_C_root() == __z)
        _C_root() = __y;
      else if (__z->_C_parent()->_C_left() == __z)
        __z->_C_parent()->_C_left() = __y;
      else