^^&&^^

Edit File: stl_tree.h

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

// Copyright (C) 2001-2013 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 3, 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.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/*
 *
 * 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 bits/stl_tree.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{map,set}
 */

#ifndef _STL_TREE_H
#define _STL_TREE_H 1

#include <bits/stl_algobase.h>
#include <bits/allocator.h>
#include <bits/stl_function.h>
#include <bits/cpp_type_traits.h>
#if __cplusplus >= 201103L
#include <bits/alloc_traits.h>
#endif

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

// 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;

#if __cplusplus >= 201103L
      template<typename... _Args>
        _Rb_tree_node(_Args&&... __args)
	: _Rb_tree_node_base(),
	  _M_value_field(std::forward<_Args>(__args)...) { }
#endif
    };

_GLIBCXX_PURE _Rb_tree_node_base*
  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();

_GLIBCXX_PURE const _Rb_tree_node_base*
  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();

_GLIBCXX_PURE _Rb_tree_node_base*
  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();

_GLIBCXX_PURE const _Rb_tree_node_base*
  _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();

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()
      : _M_node() { }

explicit
      _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 std::__addressof(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()
      : _M_node() { }

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

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

iterator
      _M_const_cast() const
      { return iterator(static_cast<typename iterator::_Link_type>
			(const_cast<typename iterator::_Base_ptr>(_M_node))); }