stl_tree.h

symbian上STL模板库的实现

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

// Copyright (C) 2001, 2002, 2003, 2004 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 _TREE_H
#define _TREE_H 1

#include <bits/stl_algobase.h>
#include <bits/allocator.h>
#include <bits/stl_construct.h>
#include <bits/stl_function.h>
#include <bits/cpp_type_traits.h>

namespace std
{
    // 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.

    enum _Rb_tree_color { _S_red = false, _S_black = true };

    struct _Rb_tree_node_base
    {
        typedef _Rb_tree_node_base* _Base_ptr;
        typedef const _Rb_tree_node_base* _Const_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 _Const_Base_ptr
            _S_minimum(_Const_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;
            }

        static _Const_Base_ptr
            _S_maximum(_Const_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;
    };

    _Rb_tree_node_base*
        _Rb_tree_increment(_Rb_tree_node_base* __x);

    const _Rb_tree_node_base*
        _Rb_tree_increment(const _Rb_tree_node_base* __x);

    _Rb_tree_node_base*
        _Rb_tree_decrement(_Rb_tree_node_base* __x);

    const _Rb_tree_node_base*
        _Rb_tree_decrement(const _Rb_tree_node_base* __x);

    template<typename _Tp>
        struct _Rb_tree_iterator
        {
            typedef _Tp  value_type;
            typedef _Tp& reference;
            typedef _Tp* pointer;

            typedef bidirectional_iterator_tag iterator_category;
            typedef ptrdiff_t                  difference_type;

            typedef _Rb_tree_iterator<_Tp>        _Self;
            typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
            typedef _Rb_tree_node<_Tp>*           _Link_type;

            _Rb_tree_iterator() { }

            _Rb_tree_iterator(_Link_type __x)
                : _M_node(__x) { }

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

            pointer
                operator->() const
                { return &static_cast<_Link_type>(_M_node)->_M_value_field; }

            _Self&
                operator++()
                {
                    _M_node = _Rb_tree_increment(_M_node);
                    return *this;
                }

            _Self
                operator++(int)
                {
                    _Self __tmp = *this;
                    _M_node = _Rb_tree_increment(_M_node);
                    return __tmp;
                }

            _Self&
                operator--()
                {
                    _M_node = _Rb_tree_decrement(_M_node);
                    return *this;
                }

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

            bool
                operator==(const _Self& __x) const
                { return _M_node == __x._M_node; }

            bool
                operator!=(const _Self& __x) const
                { return _M_node != __x._M_node; }

            _Base_ptr _M_node;
        };

    template<typename _Tp>
        struct _Rb_tree_const_iterator
        {
            typedef _Tp        value_type;
            typedef const _Tp& reference;
            typedef const _Tp* pointer;

            typedef _Rb_tree_iterator<_Tp> iterator;

            typedef bidirectional_iterator_tag iterator_category;
            typedef ptrdiff_t                  difference_type;

            typedef _Rb_tree_const_iterator<_Tp>        _Self;
            typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
            typedef const _Rb_tree_node<_Tp>*           _Link_type;

            _Rb_tree_const_iterator() { }

            _Rb_tree_const_iterator(_Link_type __x)
                : _M_node(__x) { }

            _Rb_tree_const_iterator(const iterator& __it)
                : _M_node(__it._M_node) { }

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

            pointer
                operator->() const
                { return &static_cast<_Link_type>(_M_node)->_M_value_field; }

            _Self&
                operator++()
                {
                    _M_node = _Rb_tree_increment(_M_node);
                    return *this;
                }

            _Self
                operator++(int)
                {
                    _Self __tmp = *this;
                    _M_node = _Rb_tree_increment(_M_node);
                    return __tmp;
                }

            _Self&
                operator--()
                {
                    _M_node = _Rb_tree_decrement(_M_node);
                    return *this;
                }

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

            bool
                operator==(const _Self& __x) const
                { return _M_node == __x._M_node; }

            bool
                operator!=(const _Self& __x) const
                { return _M_node != __x._M_node; }

            _Base_ptr _M_node;
        };

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

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

    void
        _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
                _Rb_tree_node_base*& __root);

    void
        _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
                _Rb_tree_node_base*& __root);

    void
        _Rb_tree_insert_and_rebalance(const bool __insert_left,
                _Rb_tree_node_base* __x,
                _Rb_tree_node_base* __p,
                _Rb_tree_node_base& __header);

    _Rb_tree_node_base*
        _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
                _Rb_tree_node_base& __header);


    template<typename _Key, typename _Val, typename _KeyOfValue,
        typename _Compare, typename _Alloc = allocator<_Val> >
            class _Rb_tree