_tree.h

MONA是为数不多的C++语言编写的一个很小的操作系统

public:
                                // allocation/deallocation
  _Rb_tree()
    : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
    { _M_empty_initialize(); }

  _Rb_tree(const _Compare& __comp)
    : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 
    { _M_empty_initialize(); }

  _Rb_tree(const _Compare& __comp, const allocator_type& __a)
    : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp) 
    { _M_empty_initialize(); }

  _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) 
    : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
      _M_node_count(0), _M_key_compare(__x._M_key_compare)
  { 
    if (__x._M_root() == 0)
      _M_empty_initialize();
    else {
      _S_color(this->_M_header._M_data) = _S_rb_tree_red;
      _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data);
      _M_leftmost() = _S_minimum(_M_root());
      _M_rightmost() = _S_maximum(_M_root());
    }
    _M_node_count = __x._M_node_count;
  }
  ~_Rb_tree() { clear(); }
  _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);

private:
  void _M_empty_initialize() {
    _S_color(this->_M_header._M_data) = _S_rb_tree_red; // used to distinguish header from 
                                          // __root, in iterator.operator++
    _M_root() = 0;
    _M_leftmost() = this->_M_header._M_data;
    _M_rightmost() = this->_M_header._M_data;
  }

public:    
                                // accessors:
  _Compare key_comp() const { return _M_key_compare; }

  iterator begin() { return iterator(_M_leftmost()); }
  const_iterator begin() const { return const_iterator(_M_leftmost()); }
  iterator end() { return iterator(this->_M_header._M_data); }
  const_iterator end() const { return const_iterator(this->_M_header._M_data); }

  reverse_iterator rbegin() { return reverse_iterator(end()); }
  const_reverse_iterator rbegin() const { 
    return const_reverse_iterator(end()); 
  }
  reverse_iterator rend() { return reverse_iterator(begin()); }
  const_reverse_iterator rend() const { 
    return const_reverse_iterator(begin());
  } 
  bool empty() const { return _M_node_count == 0; }
  size_type size() const { return _M_node_count; }
  size_type max_size() const { return size_type(-1); }

  void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {
    _STLP_STD::swap(this->_M_header, __t._M_header);
    _STLP_STD::swap(_M_node_count, __t._M_node_count);
    _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
  }
    
public:
                                // insert/erase
  pair<iterator,bool> insert_unique(const value_type& __x);
  iterator insert_equal(const value_type& __x);

  iterator insert_unique(iterator __position, const value_type& __x);
  iterator insert_equal(iterator __position, const value_type& __x);

#ifdef _STLP_MEMBER_TEMPLATES  
  template<class _II> void insert_equal(_II __first, _II __last) {
    for ( ; __first != __last; ++__first)
      insert_equal(*__first);
  }
  template<class _II> void insert_unique(_II __first, _II __last) {
    for ( ; __first != __last; ++__first)
      insert_unique(*__first);
  }
#else /* _STLP_MEMBER_TEMPLATES */
  void insert_unique(const_iterator __first, const_iterator __last) {
    for ( ; __first != __last; ++__first)
      insert_unique(*__first);
  }
  void insert_unique(const value_type* __first, const value_type* __last) {
    for ( ; __first != __last; ++__first)
      insert_unique(*__first);
  }
  void insert_equal(const_iterator __first, const_iterator __last) {
    for ( ; __first != __last; ++__first)
      insert_equal(*__first);
  }
  void insert_equal(const value_type* __first, const value_type* __last) {
    for ( ; __first != __last; ++__first)
      insert_equal(*__first);
  }
#endif /* _STLP_MEMBER_TEMPLATES */

  void erase(iterator __position) {
    _Link_type __y = 
      (_Link_type) _Rb_global_inst::_Rebalance_for_erase(__position._M_node,
							 this->_M_header._M_data->_M_parent,
							 this->_M_header._M_data->_M_left,
							 this->_M_header._M_data->_M_right);
    _STLP_STD::_Destroy(&__y->_M_value_field);
    this->_M_header.deallocate(__y,1);
    --_M_node_count;
  }
  
  size_type erase(const key_type& __x) {
    pair<iterator,iterator> __p = equal_range(__x);
    size_type __n = distance(__p.first, __p.second);
    erase(__p.first, __p.second);
    return __n;
  }
  
  void erase(iterator __first, iterator __last) {
    if (__first == begin() && __last == end())
      clear();
    else
      while (__first != __last) erase(__first++);
  }

  void erase(const key_type* __first, const key_type* __last) {
    while (__first != __last) erase(*__first++);
  }

  void clear() {
    if (_M_node_count != 0) {
      _M_erase(_M_root());
      _M_leftmost() = this->_M_header._M_data;
      _M_root() = 0;
      _M_rightmost() = this->_M_header._M_data;
      _M_node_count = 0;
    }
  }      

public:
                                // set operations:
# if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !defined(__MRC__) && !(defined(__SC__) && !defined(__DMC__))
  template <class _KT> iterator find(const _KT& __x) { return iterator(_M_find(__x)); }
  template <class _KT> const_iterator find(const _KT& __x) const { return const_iterator(_M_find(__x)); }
private:
  template <class _KT> _Rb_tree_node<_Value>* _M_find(const _KT& __k) const
# else
  iterator find(const key_type& __x) { return iterator(_M_find(__x)); }
  const_iterator find(const key_type& __x) const { return const_iterator(_M_find(__x)); }
private:
  _Rb_tree_node<_Value>* _M_find(const key_type& __k) const
# endif
  {
    _Link_type __y = this->_M_header._M_data;      // 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);
    if (__y == this->_M_header._M_data || _M_key_compare(__k, _S_key(__y)))
      __y = this->_M_header._M_data;
    return __y;
  }
  
  _Link_type _M_lower_bound(const key_type& __k) const {
    _Link_type __y = this->_M_header._M_data; /* 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 __y;
  }

  _Link_type _M_upper_bound(const key_type& __k) const {
    _Link_type __y = this->_M_header._M_data; /* 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 __y;
  }
  
public:  
  size_type count(const key_type& __x) const;
  iterator lower_bound(const key_type& __x) { return iterator(_M_lower_bound(__x)); }
  const_iterator lower_bound(const key_type& __x) const { return const_iterator(_M_lower_bound(__x)); }
  iterator upper_bound(const key_type& __x) { return iterator(_M_upper_bound(__x)); }
  const_iterator upper_bound(const key_type& __x) const { return const_iterator(_M_upper_bound(__x)); }
  pair<iterator,iterator> equal_range(const key_type& __x) {
    return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x));
  }
  pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {
    return pair<const_iterator,const_iterator>(lower_bound(__x),
					       upper_bound(__x));
  }

public:
                                // Debugging.
  bool __rb_verify() const;
};

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc> inline bool _STLP_CALL 
operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
  return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin());
}

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc> inline bool _STLP_CALL 
operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
          const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
  return lexicographical_compare(__x.begin(), __x.end(), 
                                 __y.begin(), __y.end());
}

#ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc> inline bool _STLP_CALL 
operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  return !(__x == __y);
}

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc> inline bool _STLP_CALL 
operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
          const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  return __y < __x;
}

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc> inline bool _STLP_CALL 
operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  return !(__y < __x);
}

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc> inline bool _STLP_CALL 
operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  return !(__x < __y);
}

#endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */

#ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc> inline void _STLP_CALL 
swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
     _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
  __x.swap(__y);
}

#endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */
         
_STLP_END_NAMESPACE

# if !defined (_STLP_LINK_TIME_INSTANTIATION)
#  include <stl/_tree.c> 
# endif

# undef _Rb_tree

#if defined (_STLP_DEBUG)
# include <stl/debug/_tree.h> 
#endif

_STLP_BEGIN_NAMESPACE
// Class rb_tree is not part of the C++ standard.  It is provided for
// compatibility with the HP STL.

template <class _Key, class _Value, class _KeyOfValue, class _Compare,
          _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> {
  typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
  typedef typename _Base::allocator_type allocator_type;

  rb_tree()
     : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(_Compare(), allocator_type()) {}
  rb_tree(const _Compare& __comp,
          const allocator_type& __a = allocator_type())
    : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(__comp, __a) {} 
  ~rb_tree() {}
};
_STLP_END_NAMESPACE

#endif /* _STLP_INTERNAL_TREE_H */

// Local Variables:
// mode:C++
// End: