stl_tree.h

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

    {
      _Link_type __x = (_Link_type) __x_;
      _Link_type __y = (_Link_type) __y_;
      _Link_type __z;
      
      if (__y == _M_header || __x != 0 || 
	  _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) 
	{
	  __z = _M_create_node(__v);
	  _S_left(__y) = __z;               // also makes _M_leftmost() = __z 
	  //    when __y == _M_header
	  if (__y == _M_header) 
	    {
	      _M_root() = __z;
	      _M_rightmost() = __z;
	    }
	  else if (__y == _M_leftmost())
	    _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
	}
      else 
	{
	  __z = _M_create_node(__v);
	  _S_right(__y) = __z;
	  // Maintain _M_rightmost() pointing to max node.
	  if (__y == _M_rightmost())
	    _M_rightmost() = __z; 
	}
      _S_parent(__z) = __y;
      _S_left(__z) = 0;
      _S_right(__z) = 0;
      _Rb_tree_rebalance(__z, _M_header->_M_parent);
      ++_M_node_count;
      return iterator(__z);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    insert_equal(const _Val& __v)
    {
      _Link_type __y = _M_header;
      _Link_type __x = _M_root();
      while (__x != 0) 
	{
	  __y = __x;
	  __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 
	    _S_left(__x) : _S_right(__x);
	}
      return _M_insert(__x, __y, __v);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, 
    bool>
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    insert_unique(const _Val& __v)
    {
      _Link_type __y = _M_header;
      _Link_type __x = _M_root();
      bool __comp = true;
      while (__x != 0) 
	{
	  __y = __x;
	  __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
	  __x = __comp ? _S_left(__x) : _S_right(__x);
	}
      iterator __j = iterator(__y);   
      if (__comp)
	if (__j == begin())     
	  return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
	else
	  --__j;
      if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
	return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
      return pair<iterator,bool>(__j, false);
    }
  

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    insert_unique(iterator __position, const _Val& __v)
    {
      if (__position._M_node == _M_header->_M_left) 
	{ 
	  // begin()
	  if (size() > 0 && 
	      _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
	    return _M_insert(__position._M_node, __position._M_node, __v);
	  // first argument just needs to be non-null 
	  else
	    return insert_unique(__v).first;
	} 
      else if (__position._M_node == _M_header) 
	{ 
	  // end()
	  if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
	    return _M_insert(0, _M_rightmost(), __v);
	  else
	    return insert_unique(__v).first;
	} 
      else 
	{
	  iterator __before = __position;
	  --__before;
	  if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) 
	      && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node)))
	    {
	      if (_S_right(__before._M_node) == 0)
		return _M_insert(0, __before._M_node, __v); 
	      else
		return _M_insert(__position._M_node, __position._M_node, __v);
	      // first argument just needs to be non-null 
	    } 
	  else
	    return insert_unique(__v).first;
	}
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    insert_equal(iterator __position, const _Val& __v)
    {
      if (__position._M_node == _M_header->_M_left) 
	{ 
	  // begin()
	  if (size() > 0 && 
	      !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
	    return _M_insert(__position._M_node, __position._M_node, __v);
	  // first argument just needs to be non-null 
	  else
	    return insert_equal(__v);
	} 
      else if (__position._M_node == _M_header) 
	{
	  // end()
	  if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
	    return _M_insert(0, _M_rightmost(), __v);
	  else
	    return insert_equal(__v);
	} 
      else 
	{
	  iterator __before = __position;
	  --__before;
	  if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
	      && !_M_key_compare(_S_key(__position._M_node),
				 _KeyOfValue()(__v))) 
	    {
	      if (_S_right(__before._M_node) == 0)
		return _M_insert(0, __before._M_node, __v); 
	      else
		return _M_insert(__position._M_node, __position._M_node, __v);
	      // first argument just needs to be non-null 
	    } 
	  else
	    return insert_equal(__v);
	}
    }

  template<typename _Key, typename _Val, typename _KoV, 
           typename _Cmp, typename _Alloc>
    template<class _II>
      void 
      _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
      insert_equal(_II __first, _II __last)
      {
	for ( ; __first != __last; ++__first)
	  insert_equal(*__first);
      }

  template<typename _Key, typename _Val, typename _KoV, 
           typename _Cmp, typename _Alloc> 
    template<class _II>
    void 
    _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
    insert_unique(_II __first, _II __last) 
    {
      for ( ; __first != __last; ++__first)
	insert_unique(*__first);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    inline void 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
    {
      _Link_type __y = 
	(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
						  _M_header->_M_parent,
						  _M_header->_M_left,
						  _M_header->_M_right);
      destroy_node(__y);
      --_M_node_count;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
    {
      pair<iterator,iterator> __p = equal_range(__x);
      size_type __n = distance(__p.first, __p.second);
      erase(__p.first, __p.second);
      return __n;
    }

  template<typename _Key, typename _Val, typename _KoV, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 
    _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
    _M_copy(_Link_type __x, _Link_type __p)
    {
      // Structural copy.  __x and __p must be non-null.
      _Link_type __top = _M_clone_node(__x);
      __top->_M_parent = __p;
      
      try 
	{
	  if (__x->_M_right)
	    __top->_M_right = _M_copy(_S_right(__x), __top);
	  __p = __top;
	  __x = _S_left(__x);
	  
	  while (__x != 0) 
	    {
	      _Link_type __y = _M_clone_node(__x);
	      __p->_M_left = __y;
	      __y->_M_parent = __p;
	      if (__x->_M_right)
		__y->_M_right = _M_copy(_S_right(__x), __y);
	      __p = __y;
	      __x = _S_left(__x);
	    }
	}
      catch(...)
	{
	  _M_erase(__top);
	  __throw_exception_again; 
	}
      return __top;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    void 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
    {
      // Erase without rebalancing.
      while (__x != 0) 
	{
	  _M_erase(_S_right(__x));
	  _Link_type __y = _S_left(__x);
	  destroy_node(__x);
	  __x = __y;
	}
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    void 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    erase(iterator __first, iterator __last)
    {
      if (__first == begin() && __last == end())
	clear();
      else
	while (__first != __last) erase(__first++);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    void 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    erase(const _Key* __first, const _Key* __last) 
    { 
      while (__first != __last) 
	erase(*__first++); 
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
    {
      _Link_type __y = _M_header;  // Last node which is not less than __k. 
      _Link_type __x = _M_root();  // Current node. 
      
      while (__x != 0) 
	if (!_M_key_compare(_S_key(__x), __k))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);
      
      iterator __j = iterator(__y);   
      return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? 
	end() : __j;
    }
  
  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    find(const _Key& __k) const
    {
      _Link_type __y = _M_header; // Last node which is not less than __k. 
      _Link_type __x = _M_root(); // Current node. 
 
     while (__x != 0) 
       {
	 if (!_M_key_compare(_S_key(__x), __k))
	   __y = __x, __x = _S_left(__x);
	 else
	   __x = _S_right(__x);
       } 
     const_iterator __j = const_iterator(__y);   
     return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
       end() : __j;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    count(const _Key& __k) const
    {
      pair<const_iterator, const_iterator> __p = equal_range(__k);
      size_type __n = distance(__p.first, __p.second);
      return __n;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    lower_bound(const _Key& __k)
    {
      _Link_type __y = _M_header; /* Last node which is not less than __k. */
      _Link_type __x = _M_root(); /* Current node. */
      
      while (__x != 0) 
	if (!_M_key_compare(_S_key(__x), __k))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);
      
      return iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    lower_bound(const _Key& __k) const
    {
      _Link_type __y = _M_header; /* Last node which is not less than __k. */
      _Link_type __x = _M_root(); /* Current node. */
      
      while (__x != 0) 
	if (!_M_key_compare(_S_key(__x), __k))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);
      
      return const_iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    upper_bound(const _Key& __k)
    {
      _Link_type __y = _M_header; /* Last node which is greater than __k. */
      _Link_type __x = _M_root(); /* Current node. */
      
      while (__x != 0) 
	if (_M_key_compare(__k, _S_key(__x)))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);
      
      return iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    upper_bound(const _Key& __k) const
    {
      _Link_type __y = _M_header; /* Last node which is greater than __k. */
      _Link_type __x = _M_root(); /* Current node. */
      
      while (__x != 0) 
	if (_M_key_compare(__k, _S_key(__x)))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);
      
      return const_iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    inline 
    pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
								   typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    equal_range(const _Key& __k)
    { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }

  template<typename _Key, typename _Val, typename _KoV, 
           typename _Compare, typename _Alloc>
  inline 
  pair<typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator,
								typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
  _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>
  ::equal_range(const _Key& __k) const
  {
    return pair<const_iterator,const_iterator>(lower_bound(__k),
					       upper_bound(__k));
  }

  inline int
  __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
  {
    if (__node == 0)
      return 0;
    int __sum = 0;
    do 
      {
	if (__node->_M_color == _M_black) 
	  ++__sum;
	if (__node == __root) 
	  break;
	__node = __node->_M_parent;
      } 
    while (1);
    return __sum;
  }

  template<typename _Key, typename _Val, typename _KeyOfValue, 
           typename _Compare, typename _Alloc>
    bool 
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
    {
    if (_M_node_count == 0 || begin() == end())
      return _M_node_count == 0 && begin() == end() &&
	_M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
  
    int __len = __black_count(_M_leftmost(), _M_root());
    for (const_iterator __it = begin(); __it != end(); ++__it) 
      {
	_Link_type __x = (_Link_type) __it._M_node;
	_Link_type __L = _S_left(__x);
	_Link_type __R = _S_right(__x);
	
	if (__x->_M_color == _M_red)
	  if ((__L && __L->_M_color == _M_red) 
	      || (__R && __R->_M_color == _M_red))
	    return false;
	
	if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
	  return false;
	if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
	  return false;

	if (!__L && !__R && __black_count(__x, _M_root()) != __len)
	  return false;
      }
    
    if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
      return false;
    if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
      return false;
    return true;
    }
} // namespace std 

#endif