stl_tree.h

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

// RB tree implementation -*- C++ -*-

// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * 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.  Silicon Graphics 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
 * 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.
 *
 *
 */

/** @file stl_tree.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef __GLIBCPP_INTERNAL_TREE_H
#define __GLIBCPP_INTERNAL_TREE_H

/*

Red-black tree class, designed for use in implementing STL
associative containers (set, multiset, map, and multimap). The
insertion and deletion algorithms are based on those in Cormen,
Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
except that

(1) the header cell is maintained with links not only to the root
but also to the leftmost node of the tree, to enable constant time
begin(), and to the rightmost node of the tree, to enable linear time
performance when used with the generic set algorithms (set_union,
etc.);

(2) when a node being deleted has two children its successor node is
relinked into its place, rather than copied, so that the only
iterators invalidated are those referring to the deleted node.

*/

#include <bits/stl_algobase.h>
#include <bits/stl_alloc.h>
#include <bits/stl_construct.h>
#include <bits/stl_function.h>

namespace std
{ 
  enum _Rb_tree_color { _M_red = false, _M_black = true };

  struct _Rb_tree_node_base
  {
    typedef _Rb_tree_node_base* _Base_ptr;
    
    _Rb_tree_color 	_M_color; 
    _Base_ptr 		_M_parent;
    _Base_ptr 		_M_left;
    _Base_ptr 		_M_right;
    
    static _Base_ptr 
    _S_minimum(_Base_ptr __x)
    {
      while (__x->_M_left != 0) __x = __x->_M_left;
      return __x;
    }

    static _Base_ptr 
    _S_maximum(_Base_ptr __x)
    {
      while (__x->_M_right != 0) __x = __x->_M_right;
      return __x;
    }
  };

  template<typename _Val>
    struct _Rb_tree_node : public _Rb_tree_node_base
    {
      typedef _Rb_tree_node<_Val>* _Link_type;
      _Val _M_value_field;
    };
  
  struct _Rb_tree_base_iterator
  {
    typedef _Rb_tree_node_base::_Base_ptr 	_Base_ptr;
    typedef bidirectional_iterator_tag 		iterator_category;
    typedef ptrdiff_t 				difference_type;

    _Base_ptr _M_node;

    void 
    _M_increment()
    {
      if (_M_node->_M_right != 0) 
	{
	  _M_node = _M_node->_M_right;
	  while (_M_node->_M_left != 0)
	    _M_node = _M_node->_M_left;
	}
      else 
	{
	  _Base_ptr __y = _M_node->_M_parent;
	  while (_M_node == __y->_M_right) 
	    {
	      _M_node = __y;
	      __y = __y->_M_parent;
	    }
	  if (_M_node->_M_right != __y)
	    _M_node = __y;
	}
    }

    void 
    _M_decrement()
    {
      if (_M_node->_M_color == _M_red 
	  && _M_node->_M_parent->_M_parent == _M_node)
	_M_node = _M_node->_M_right;
      else if (_M_node->_M_left != 0) 
	{
	  _Base_ptr __y = _M_node->_M_left;
	  while (__y->_M_right != 0)
	    __y = __y->_M_right;
	  _M_node = __y;
	}
      else 
	{
	  _Base_ptr __y = _M_node->_M_parent;
	  while (_M_node == __y->_M_left) 
	    {
	      _M_node = __y;
	      __y = __y->_M_parent;
	    }
	  _M_node = __y;
	}
    }
  };

  template<typename _Val, typename _Ref, typename _Ptr>
    struct _Rb_tree_iterator : public _Rb_tree_base_iterator
    {
      typedef _Val value_type;
      typedef _Ref reference;
      typedef _Ptr pointer;
      typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator;
      typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*> 
      const_iterator;
      typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self;
      typedef _Rb_tree_node<_Val>* _Link_type;
      
      _Rb_tree_iterator() {}
      _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
      _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }

      reference 
      operator*() const { return _Link_type(_M_node)->_M_value_field; }

      pointer 
      operator->() const { return &(operator*()); }

      _Self& 
      operator++() 
      { 
	_M_increment(); 
	return *this; 
      }

      _Self 
      operator++(int) 
      {
	_Self __tmp = *this;
	_M_increment();
	return __tmp;
      }
    
      _Self& 
      operator--() { _M_decrement(); return *this; }

      _Self 
      operator--(int) 
      {
	_Self __tmp = *this;
	_M_decrement();
	return __tmp;
      }
  };

  template<typename _Val, typename _Ref, typename _Ptr>
    inline bool 
    operator==(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x,
	       const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y) 
    { return __x._M_node == __y._M_node; }

  template<typename _Val>
    inline bool 
    operator==(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x,
	       const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y) 
    { return __x._M_node == __y._M_node; }

  template<typename _Val>
    inline bool 
    operator==(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x,
	       const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) 
    { return __x._M_node == __y._M_node; }

  template<typename _Val, typename _Ref, typename _Ptr>
    inline bool 
    operator!=(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x,
	       const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y) 
    { return __x._M_node != __y._M_node; }

  template<typename _Val>
    inline bool 
    operator!=(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x,
	       const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y) 
    { return __x._M_node != __y._M_node; }

  template<typename _Val>
    inline bool 
    operator!=(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x,
	       const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) 
    { return __x._M_node != __y._M_node; }

  inline void 
  _Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
  {
    _Rb_tree_node_base* __y = __x->_M_right;
    __x->_M_right = __y->_M_left;
    if (__y->_M_left !=0)
      __y->_M_left->_M_parent = __x;
    __y->_M_parent = __x->_M_parent;
    
    if (__x == __root)
      __root = __y;
    else if (__x == __x->_M_parent->_M_left)
      __x->_M_parent->_M_left = __y;
    else
      __x->_M_parent->_M_right = __y;
    __y->_M_left = __x;
    __x->_M_parent = __y;
  }

  inline void 
  _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
  {
    _Rb_tree_node_base* __y = __x->_M_left;
    __x->_M_left = __y->_M_right;
    if (__y->_M_right != 0)
      __y->_M_right->_M_parent = __x;
    __y->_M_parent = __x->_M_parent;

    if (__x == __root)
      __root = __y;
    else if (__x == __x->_M_parent->_M_right)
      __x->_M_parent->_M_right = __y;
    else
      __x->_M_parent->_M_left = __y;
    __y->_M_right = __x;
    __x->_M_parent = __y;
  }

  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 null 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)) 
		{