_tree.h

realview22.rar

    _C_link_t& _C_leftmost  () const { return _C_header->_C_left ();   }
    _C_link_t& _C_rightmost () const { return _C_header->_C_right();   }
    
    size_type  _C_node_count;    // Keeps track of size of tree.
    bool       _C_insert_always; // Controls whether an element already in the
                                 // tree is inserted again.
    _Comp      _C_key_comp;

public:
    

#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

    typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef _STD::reverse_iterator<iterator>       reverse_iterator;

#else

    typedef __reverse_bi_iterator<const_iterator, 
        _STD::bidirectional_iterator_tag, value_type, 
        const_reference, const_pointer, difference_type>
    const_reverse_iterator;

    typedef __reverse_bi_iterator<iterator, 
        _STD::bidirectional_iterator_tag, value_type,
        reference, pointer, difference_type>
    reverse_iterator;

#endif   // _RWSTD_NO_CLASS_PARTIAL_SPEC

  private:

    iterator     _C_insert (_C_link_t __x, _C_link_t __y, 
                            const value_type& __v);
    _C_link_t _C_copy   (_C_link_t __x, _C_link_t __p);
    void         _C_erase  (_C_link_t __x);
    inline void  _C_erase_leaf  (_C_link_t __x);

    void _C_init ()
    {
      _C_buf_list    = 0;
      _C_free_list   = _C_next_avail = _C_last = 0;
      _C_header      = _C_get_node();
      _C_root()      = 0;
      _C_leftmost()  = _C_header;
      _C_rightmost() = _C_header;
    }

  public:

    __rb_tree (const _Comp& _RWSTD_COMP = _Comp(),
               bool __always = true,
               const _Alloc& __alloc =  _Alloc()) 
      : allocator_type (__alloc),_C_buf_list(0), _C_header(0), _C_node_count(0),
        _C_insert_always(__always), _C_key_comp(_RWSTD_COMP)
    {
      _C_init();
    }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class _InputIter>
    __rb_tree (_InputIter __first, _InputIter __last, 
             const _Comp& __cmp = _Comp(), bool __always = true,
             const _Alloc& __alloc = _Alloc())
      : allocator_type(__alloc),_C_buf_list(0), _C_header(0), _C_node_count(0), 
        _C_insert_always(__always), _C_key_comp(__cmp)
    { 
      _C_init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(__first, __last);
      } catch(...) {
        _C_deallocate_buffers();
        throw;
      }
#else
      insert(__first, __last);
#endif // _RWSTD_NO_EXCEPTIONS
    }
#else
    __rb_tree (const value_type* __first, const value_type* __last, 
               const _Comp& _RWSTD_COMP = _Comp(),
               bool __always = true,
               const _Alloc& __alloc = _Alloc())
      : allocator_type(__alloc),_C_buf_list(0), _C_header(0), _C_node_count(0), 
        _C_insert_always(__always), _C_key_comp(_RWSTD_COMP)
    { 
      _C_init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(__first, __last);
      } catch(...) {
        _C_deallocate_buffers();
        throw;
      }
#else
      insert(__first, __last);
#endif // _RWSTD_NO_EXCEPTIONS
    }
    __rb_tree (const_iterator __first, const_iterator __last, 
               const _Comp& _RWSTD_COMP = _Comp(),
               bool __always = true,
               const _Alloc& __alloc = _Alloc())
      : allocator_type(__alloc), _C_buf_list(0), _C_header(0), _C_node_count(0), 
        _C_insert_always(__always), _C_key_comp(_RWSTD_COMP)
    { 
      _C_init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(__first, __last);
      } catch(...) {
        _C_deallocate_buffers();
        throw;
      }
#else
      insert(__first, __last);
#endif // _RWSTD_NO_EXCEPTIONS
    }
   
#endif

    __rb_tree (const __rb_tree<_Key,_Val,_KeyOf,_Comp,_Alloc>& __x,
             bool __always = true)
      : allocator_type(__x.get_allocator()), _C_buf_list(0), _C_header(0), 
        _C_node_count(__x._C_node_count), _C_insert_always(__always), 
        _C_key_comp(__x._C_key_comp)
    { 
      _C_free_list          = _C_next_avail = _C_last = 0;
      _C_header             = _C_get_node();
      _C_header->_C_color() = _C_node_t::_C_red;
      _TRY { 
          _C_root() = _C_copy(__x._C_root(), _C_header);
      }
      _CATCH (...) {
          _C_deallocate_buffers();
          _RETHROW;
      }
      if (_C_root()) {
        _C_leftmost()  = _C_node_t::_C_minimum(_C_root());
        _C_rightmost() = _C_node_t::_C_maximum(_C_root());
      }
      else {
        _C_leftmost()  = _C_header;
        _C_rightmost() = _C_header;
      }
    }

    ~__rb_tree () {
        if ((void*)_C_header) {
            erase (begin(), end ());
            _C_put_node (_C_header, false);
            _C_deallocate_buffers ();
      }
    }

    __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& 
    operator= (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __x);

    _Comp     key_comp () const { return _C_key_comp; }
    _C_val_alloc_t get_allocator() const
    {
      return _C_val_alloc_t(*this);
    }

    iterator begin () {
        return _C_make_iter (_C_leftmost ());
    }

    const_iterator begin () const {
        return _C_make_iter (_C_leftmost ());
    }

    iterator end () {
        return _C_make_iter (_C_header);
    }

    const_iterator end () const {
        return _C_make_iter (_C_header);
    }

    reverse_iterator rbegin () { 
        return reverse_iterator(end());
    }
    
    reverse_iterator rend () { 
        return reverse_iterator (begin());
    } 

    const_reverse_iterator rbegin () const { 
        return const_reverse_iterator (end());
    }
    
    const_reverse_iterator rend () const { 
        return const_reverse_iterator(begin());
    } 

    bool      empty    () const {
        return _C_node_count == 0;
    }

    size_type size     () const {
        return _C_node_count;
    }

    size_type max_size () const { 
      return _C_node_alloc_t(*this).max_size(); 
    }
    
    void swap (__rb_tree &__t) {
      if(get_allocator() == __t.get_allocator()) {
          _STD::swap (_C_buf_list, __t._C_buf_list);
          _STD::swap (_C_free_list, __t._C_free_list);
          _STD::swap (_C_next_avail, __t._C_next_avail);
          _STD::swap (_C_last, __t._C_last);
          _STD::swap (_C_header, __t._C_header);
          _STD::swap (_C_node_count, __t._C_node_count);
          _STD::swap (_C_insert_always, __t._C_insert_always);
          _STD::swap (_C_key_comp, __t._C_key_comp);
      }
      else {
          __rb_tree __x = *this;
          *this = __t;
          __t = __x;
      } 
    }

    _STD::pair<iterator, bool> insert (const value_type&);

    iterator insert (iterator, const value_type&);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class _Iterator>
    void      insert (_Iterator __first, _Iterator __last);
#else
    void      insert (const_iterator __first, const_iterator __last);
    void      insert (const value_type* __first, const value_type* __last);
#endif

    iterator  erase  (iterator);
    size_type erase  (const key_type&);
    iterator  erase  (iterator, iterator);
    void      erase  (const key_type*, const key_type*);

    iterator find (const key_type&);

    const_iterator find (const key_type& __x) const {
        return _RWSTD_CONST_CAST (__rb_tree*, this)->find (__x);
    }

    size_type count (const key_type& __x) const;

    iterator lower_bound (const key_type& __x);

    const_iterator lower_bound (const key_type& __x) const {
        return _RWSTD_CONST_CAST (__rb_tree*, this)->lower_bound (__x);
    }

    iterator upper_bound (const key_type& __x);

    const_iterator upper_bound (const key_type& __x) const {
        return _RWSTD_CONST_CAST (__rb_tree*, this)->upper_bound (__x);
    }

    _STD::pair<iterator, iterator> equal_range (const key_type& __x);

    _STD::pair<const_iterator, const_iterator>
    equal_range (const key_type& __x) const {
        _STD::pair<iterator, iterator> __tmp =
            _RWSTD_CONST_CAST (__rb_tree*, this)->equal_range (__x);
        return _STD::pair<const_iterator, const_iterator>
            (__tmp.first, __tmp.second);
    }

    inline void __rotate_left  (_C_link_t __x);
    inline void __rotate_right (_C_link_t __x);

};


//
// Inline functions
//

template <class _Key, class _Val, class _KeyOf, 
class _Comp, class _Alloc>
inline bool
operator== (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __x, 
            const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __y)
{
    return    __x.size () == __y.size ()
           && equal (__x.begin (), __x.end (), __y.begin ());
}


template <class _Key, class _Val, class _KeyOf, 
class _Comp, class _Alloc>
inline bool
operator< (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __x, 
           const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __y)
{
    return lexicographical_compare (__x.begin (), __x.end (),
                                    __y.begin (), __y.end ());
}


template <class _Key,class _Val,class _KeyOf,class _Comp,class _Alloc>
inline void   
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_erase_leaf (_C_link_t __x)
{
    // Remove a leaf node from the tree
    _C_link_t __y = __x->_C_parent();
    if (__y == _C_header)
    {
      _C_leftmost() = _C_rightmost() = __y;
      _C_root() = 0;
    }
    else if (__y->_C_left() == __x)
    {
      __y->_C_left() = 0;
      if (_C_leftmost() == __x)
        _C_leftmost() = __y;
    }
    else
    {
      __y->_C_right() = 0;
      if (_C_rightmost() == __x)
        _C_rightmost() = __y;
    }
  }


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__rotate_left (_C_link_t __x)
{
    _RWSTD_ASSERT (0 != (void*)__x);

    _C_link_t __y   = __x->_C_right();
    __x->_C_right() = __y->_C_left();

    if ((void*)__y->_C_left ())
        __y->_C_left()->_C_parent() = __x;

    __y->_C_parent() = __x->_C_parent();

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

    __y->_C_left ()  = __x;
    __x->_C_parent() = __y;
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__rotate_right (_C_link_t __x)
{
    _RWSTD_ASSERT (0 != (void*)__x);
      
    _C_link_t __y   = __x->_C_left();
    __x->_C_left () = __y->_C_right();

    if ((void*)__y->_C_right ())
        __y->_C_right()->_C_parent() = __x;

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

    __y->_C_right ()  = __x;
    __x->_C_parent () = __y;
}


#ifndef _RWSTD_NO_MEMBER_TEMPLATES

template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
template<class _Iterator>
inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
insert (_Iterator __first, _Iterator __last)
{
    for (; __first != __last; ++__first)
        insert(*__first);
}

#else

template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
insert (const_iterator __first, const_iterator __last)
{
    for (; __first != __last; ++__first)
        insert(*__first);
}

template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
insert (const _Val* __first, const _Val* __last)
{
    for (; __first != __last; ++__first)
        insert(*__first);
}

#endif   // _RWSTD_NO_MEMBER_TEMPLATES
         

template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
erase (const _Key* __first, const _Key* __last)
{
    for (; __first != __last; ++__first)
        erase(*__first);
}


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type 
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::count (const _Key& __k) const
{
    _STD::pair<const_iterator, const_iterator> __p = equal_range(__k);
    size_type __n = _DISTANCE (__p.first, __p.second, size_type);
    return __n;
}


#define _RWSTD_RB_TREE_ITER _TYPENAME __rb_tree<_Key, _Val, _KeyOf, \
                                               _Comp, _Alloc>::iterator
                                               
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
inline _STD::pair<_RWSTD_RB_TREE_ITER , _RWSTD_RB_TREE_ITER >
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::equal_range (const _Key& __k)
{
    return _STD::pair<iterator, iterator>(lower_bound (__k), upper_bound (__k));
}

#undef _RWSTD_RB_TREE_ITER


_RWSTD_NAMESPACE_END   // __rw


#ifdef _RWSTD_COMPILE_INSTANTIATE
#  include <rw/_tree.cc>
#endif

#endif   // _RWSTD_TREE_H_INCLUDED