_tree.h

symbian 上的stl_port进过编译的。

  { return this->_M_header._M_data._M_left; }
  _Base_ptr& _M_rightmost()
  { return this->_M_header._M_data._M_right; }

  static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x)
  { return __x->_M_left; }
  static _Base_ptr& _STLP_CALL _S_right(_Base_ptr __x)
  { return __x->_M_right; }
  static _Base_ptr& _STLP_CALL _S_parent(_Base_ptr __x)
  { return __x->_M_parent; }
  static value_type& _STLP_CALL _S_value(_Base_ptr __x)
  { return __STATIC_CAST(_Link_type, __x)->_M_value_field; }
  static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
  { return _KeyOfValue()(_S_value(__x));}
  static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)
  { return (_Color_type&)(__x->_M_color); }

  static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
  { return _Rb_tree_node_base::_S_minimum(__x); }

  static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
  { return _Rb_tree_node_base::_S_maximum(__x); }

public:
  typedef typename _Traits::_NonConstTraits _NonConstTraits;
  typedef typename _Traits::_ConstTraits _ConstTraits;
  typedef _Rb_tree_iterator<value_type, _NonConstTraits> iterator;
  typedef _Rb_tree_iterator<value_type, _ConstTraits> const_iterator;
  _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;

private:
  iterator _M_insert(_Base_ptr __parent, const value_type& __val, _Base_ptr __on_left = 0, _Base_ptr __on_right = 0);
  _Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p);
  void _M_erase(_Base_ptr __x);

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

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

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

  _Rb_tree(const _Self& __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) {
      _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(__move_source<_Self> src)
    : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())),
      _M_node_count(src.get()._M_node_count),
      _M_key_compare(_AsMoveSource(src.get()._M_key_compare)) {
    src.get()._M_node_count = 0;
  }

  ~_Rb_tree() { clear(); }
  _Self& operator=(const _Self& __x);

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(__CONST_CAST(_Base_ptr, &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(_Self& __t) {
    if (__t.empty()) {
      if (this->empty()) return;
      __t._M_header.swap(this->_M_header);
      __t._M_rebind(&this->_M_header._M_data);
      this->_M_empty_initialize();
    }
    else if (this->empty()) {
      __t.swap(*this);
      return;
    }
    else {
      this->_M_header.swap(__t._M_header);
      this->_M_rebind(&__t._M_header._M_data);
      __t._M_rebind(&this->_M_header._M_data);
    }
    _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 __pos, const value_type& __x);
  iterator insert_equal(iterator __pos, const value_type& __x);

#if defined (_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
  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

  void erase(iterator __pos) {
    _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._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(&_S_value(__x));
    this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 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;
  }

  size_type erase_unique(const key_type& __x) {
    iterator __i = find(__x);
    if (__i._M_node != &this->_M_header._M_data) {
      erase(__i);
      return 1;
    }
    return 0;
  }

  void erase(iterator __first, iterator __last) {
    if (__first._M_node == this->_M_header._M_data._M_left && // begin()
        __last._M_node == &this->_M_header._M_data)           // 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:
  _STLP_TEMPLATE_FOR_CONT_EXT
  iterator find(const _KT& __k) { return iterator(_M_find(__k)); }
  _STLP_TEMPLATE_FOR_CONT_EXT
  const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); }
private:
  _STLP_TEMPLATE_FOR_CONT_EXT
  _Base_ptr _M_find(const _KT& __k) const {
    _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);      // Last node which is not less than __k.
    _Base_ptr __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) {
      if (_M_key_compare(__k, _S_key(__y))) {
        __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
      }
    }
    return __y;
  }

  _STLP_TEMPLATE_FOR_CONT_EXT
  _Base_ptr _M_lower_bound(const _KT& __k) const {
    _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */
    _Base_ptr __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;
  }

  _STLP_TEMPLATE_FOR_CONT_EXT
  _Base_ptr _M_upper_bound(const _KT& __k) const {
    _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */
    _Base_ptr __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:
  _STLP_TEMPLATE_FOR_CONT_EXT
  size_type count(const _KT& __x) const {
    pair<const_iterator, const_iterator> __p = equal_range(__x);
    return distance(__p.first, __p.second);
  }
  _STLP_TEMPLATE_FOR_CONT_EXT
  iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); }
  _STLP_TEMPLATE_FOR_CONT_EXT
  const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); }
  _STLP_TEMPLATE_FOR_CONT_EXT
  iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); }
  _STLP_TEMPLATE_FOR_CONT_EXT
  const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); }
  _STLP_TEMPLATE_FOR_CONT_EXT
  pair<iterator,iterator> equal_range(const _KT& __x)
  { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); }
  _STLP_TEMPLATE_FOR_CONT_EXT
  pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
  { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); }
  _STLP_TEMPLATE_FOR_CONT_EXT
  pair<iterator,iterator> equal_range_unique(const _KT& __x) {
    pair<iterator, iterator> __p;
    __p.second = lower_bound(__x);
    if (__p.second._M_node != &this->_M_header._M_data &&
        !_M_key_compare(__x, _S_key(__p.second._M_node))) {
      __p.first = __p.second++;
    }
    else {
      __p.first = __p.second;
    }
    return __p;
  }
  _STLP_TEMPLATE_FOR_CONT_EXT
  pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const {
    pair<const_iterator, const_iterator> __p;
    __p.second = lower_bound(__x);
    if (__p.second._M_node != &this->_M_header._M_data &&
        !_M_key_compare(__x, _S_key(__p.second._M_node))) {
      __p.first = __p.second++;
    }
    else {
      __p.first = __p.second;
    }
    return __p;
  }

#if defined (_STLP_DEBUG)
public:
  // Debugging.
  bool __rb_verify() const;
#endif //_STLP_DEBUG
};

#if defined (_STLP_DEBUG)
#  undef _Rb_tree
#endif

_STLP_MOVE_TO_STD_NAMESPACE

_STLP_END_NAMESPACE

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

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

_STLP_BEGIN_NAMESPACE

#define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
#define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>
#include <stl/_relops_cont.h>
#undef _STLP_TEMPLATE_CONTAINER
#undef _STLP_TEMPLATE_HEADER

#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
struct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> >
  : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {};
#endif

_STLP_END_NAMESPACE

#endif /* _STLP_INTERNAL_TREE_H */

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