// -*- C++ -*-
#ifndef __STD_TREE__
#define __STD_TREE__

/***************************************************************************
 *
 * tree - Declarations for the Standard Library tree classes
 *
 ***************************************************************************
 *    
 *  Copyright 2000 Compaq Computer Corporation
 *
 *  COMPAQ Registered in U.S. Patent and Trademark Office.
 *
 *  Confidential computer software. Valid license from Compaq required for
 *  possession, use or copying. Consistent with FAR 12.211 and 12.212,
 *  Commercial Computer Software, Computer Software Documentation, and
 *  Technical Data for Commercial Items are licensed to the U.S. Government
 *  under vendor's standard commercial license.
 *
 ****************************************************************************
 *
 * 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.
 *
 *
 ***************************************************************************
 *
 * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/

/*
**
** 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.
** 
*/

#include <stdcomp>
#include <algorithm>
#include <iterator>

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __save
#      pragma __environment __header_defaults
#   endif
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#pragma __extern_prefix __save
#pragma __extern_prefix "CXXL$" 
#endif


#ifndef _RWSTD_NO_NAMESPACE
namespace _RWrwstd {
#endif

#ifndef _RWrb_tree 
#define _RWrb_tree _RWrb_tree
#endif

  template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  class _RWrb_tree
  {
  protected:

    enum _RWcolor_type { _RWrb_red, _RWrb_black };

    struct _RWrb_tree_node;
    friend struct _RWrb_tree_node;

#ifdef _RWSTD_ALLOCATOR
    typedef _TYPENAME _Alloc::template rebind<_Val>::other  _RWvalue_alloc_type;
    typedef _TYPENAME _Alloc::template rebind<_Key>::other  _RWkey_alloc_type;
    typedef _TYPENAME _Alloc::template rebind<_RWrb_tree_node>::other  _RWnode_alloc_type;
#else
    typedef _RW_STD::allocator_interface<_Alloc,_Val>      _RWvalue_alloc_type;
    typedef _RW_STD::allocator_interface<_Alloc,_Key>        _RWkey_alloc_type;
    typedef _RW_STD::allocator_interface<_Alloc,_RWrb_tree_node> _RWnode_alloc_type;
#endif

    typedef _TYPENAME _RWnode_alloc_type::pointer          _RWlink_type;

    struct _RWrb_tree_node
    {
     ~_RWrb_tree_node() { ; }
      _RWcolor_type   color_field; 
      _RWlink_type parent_link;
      _RWlink_type left_link;
      _RWlink_type right_link;
      _Val        value_field;
    };

    typedef _TYPENAME _RWkey_alloc_type::const_reference    const_key_reference;

  public:

    typedef _Key                                    key_type;
    typedef _Val                                    value_type;
    typedef _Alloc                                  allocator_type;
    typedef _TYPENAME _RWvalue_alloc_type::pointer          pointer;
    typedef _TYPENAME _RWvalue_alloc_type::const_pointer    const_pointer;

#ifndef _RWSTD_NO_COMPLICATED_TYPEDEF
    typedef _TYPENAME _Alloc::size_type                 size_type;
    typedef _TYPENAME _Alloc::size_type                 difference_type;
    typedef _TYPENAME _RWvalue_alloc_type::reference       reference;
    typedef _TYPENAME _RWvalue_alloc_type::const_reference const_reference;
#else
    typedef size_t             size_type;
    typedef ptrdiff_t          difference_type;
    typedef _Val&              reference;
    typedef const _Val&        const_reference;
#endif  //_RWSTD_NO_COMPLICATED_TYPEDEF



  protected:
    size_type _RWbuffer_size;

    struct _RWrb_tree_node_buffer;
    friend struct _RWrb_tree_node_buffer;

#ifdef _RWSTD_ALLOCATOR
    typedef _TYPENAME allocator_type::template rebind<_RWrb_tree_node_buffer>::other  _RWbuffer_alloc_type;
#else
    typedef _RW_STD::allocator_interface<_Alloc,_RWrb_tree_node_buffer> _RWbuffer_alloc_type;
#endif
    typedef _TYPENAME _RWbuffer_alloc_type::pointer _RWbuffer_pointer;

    struct _RWrb_tree_node_buffer
    {
      ~_RWrb_tree_node_buffer() { ; }
       _RWbuffer_pointer  next_buffer;
      size_type size;
      _RWlink_type buffer;
    };

    __RWSTD::_RWrw_basis<_RWbuffer_pointer,allocator_type>   _RWbuffer_list;
    _RWlink_type                      _RWfree_list;
    _RWlink_type                      _RWnext_avail;
    _RWlink_type                      _RWlast;

    static bool _RWisNil(const _RWlink_type& l) 
    {  return l == _RWnil();  }

    void _RWadd_new_buffer ()
    {
      _RWbuffer_pointer tmp = _RWbuffer_alloc_type(_RWbuffer_list).allocate(_RWSTD_STATIC_CAST(size_type,1),_RWbuffer_list.data());
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        tmp->buffer        = _RWnode_alloc_type(_RWbuffer_list).allocate(_RWbuffer_size,_RWlast);
      } catch(...) {
        _RWbuffer_alloc_type(_RWbuffer_list).deallocate(tmp,1);
        throw;
      } 
#else
      tmp->buffer        = _RWnode_alloc_type(_RWbuffer_list).allocate(_RWbuffer_size,_RWlast);
#endif //  _RWSTD_NO_EXCEPTIONS     
      tmp->next_buffer   = _RWbuffer_list;
      tmp->size          = _RWbuffer_size;
      _RWbuffer_list        = tmp;
      _RWnext_avail         = _RWbuffer_list.data()->buffer;
      _RWlast               = _RWnext_avail + _RWbuffer_size;
    }
    void _RWdeallocate_buffers ();

    // 
    // Return a node from the free list or new storage
    //
    _RWlink_type _RWget_link()
    {
      _RWlink_type tmp = _RWfree_list;
      _RWlink_type tmp2 = _RWfree_list ? 
        (_RWfree_list = _RWSTD_STATIC_CAST(_RWlink_type,(_RWfree_list->right_link)), tmp) 
        : (_RWnext_avail == _RWlast ? (_RWadd_new_buffer(), _RWnext_avail++) 
          : _RWnext_avail++);
      tmp2->parent_link = _RWnil();
      tmp2->left_link = _RWnil();
      tmp2->right_link = _RWnil();
      tmp2->color_field = _RWrb_red;
      return tmp2;
    }

    //
    // Return a node from the free list or new storage with
    // the _Val v constructed on it.  Every call to _RWget_node
    // must eventually be followed by a call to _RWput_node.
    //
    _RWlink_type _RWget_node (const _Val& v)
    {
      _RWlink_type tmp2 = _RWget_link();
      _RWvalue_alloc_type va(_RWbuffer_list);
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        va.construct(va.address(_RWvalue(tmp2)),v);
      } catch(...) {
        _RWput_node(tmp2,false);
        throw;
      }      
#else
      va.construct(va.address(_RWvalue(tmp2)),v);
#endif // _RWSTD_NO_EXCEPTIONS
      return tmp2;
    }
    _RWlink_type _RWget_node ()
    {
      return _RWget_link();
    }

    // 
    // Return a node to the free list and destroy the value in it.
    //
    void _RWput_node (_RWlink_type p, bool do_destroy = true) 
    { 
      p->right_link = _RWfree_list; 
      if (do_destroy)      
      {
        _RWvalue_alloc_type va(_RWbuffer_list);
        va.destroy(va.address(_RWvalue(p)));  
      }
      _RWfree_list = p; 
    }

  protected:

    _RWlink_type  _RWheader;  
    _RWlink_type& _RWroot      ()       { return _RWparent(_RWheader); }
    _RWlink_type& _RWroot      () const { return _RWparent(_RWheader); }
    _RWlink_type& _RWleftmost  ()       { return _RWleft(_RWheader);   }
    _RWlink_type& _RWleftmost  () const { return _RWleft(_RWheader);   }
    _RWlink_type& _RWrightmost ()       { return _RWright(_RWheader);  }
    _RWlink_type& _RWrightmost () const { return _RWright(_RWheader);  }

    size_type  _RWnode_count;    // Keeps track of size of tree.
    bool       _RWinsert_always; // Controls whether an element already in the
    // tree is inserted again.
    _Comp      _RWkey_compare;

    static _RWlink_type _RWnil () { return NULL; }

    static _RWlink_type& _RWleft (_RWlink_type x)
    {
      return _RWSTD_REINTERPRET_CAST(_RWlink_type&,((*x).left_link));
    }
    static _RWlink_type& _RWright (_RWlink_type x)
    {
      return _RWSTD_REINTERPRET_CAST(_RWlink_type&,((*x).right_link));
    }
    static _RWlink_type& _RWparent (_RWlink_type x)
    {
      return _RWSTD_REINTERPRET_CAST(_RWlink_type&,((*x).parent_link));
    }
    static reference _RWvalue (_RWlink_type x) { return (*x).value_field; }
    static const_key_reference _RWkey (_RWlink_type x)
    {
      return _KeyOf()(_RWvalue(x));
    }
    static _RWcolor_type& _RWcolor (_RWlink_type x)
    {
      return _RWSTD_STATIC_CAST(_RWcolor_type&,(*x).color_field);
    }
    static _RWlink_type _RWminimum (_RWlink_type x)
    {
      while (!_RWisNil(_RWleft(x))) x = _RWleft(x);
      return x;
    }
    static _RWlink_type _RWmaximum (_RWlink_type x)
    {
      while (!_RWisNil(_RWright(x))) x = _RWright(x);
      return x;
    }

    typedef _RW_STD::iterator<_RW_STD::bidirectional_iterator_tag, value_type,
                    difference_type, pointer,reference> _RWit;
    typedef _RW_STD::iterator<_RW_STD::bidirectional_iterator_tag, value_type, 
                    difference_type, const_pointer, const_reference> _RWcit;

  public:

    class  iterator;
    friend class iterator;
    class  const_iterator;
    friend class const_iterator;

    class iterator : public _RWit
    {
      friend class _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>;
      friend class const_iterator;

    protected:

      _RWlink_type node;
      iterator (_RWlink_type x) : node(x) {}        

    public:

      iterator () {}
      bool operator== (const iterator& y) const { return node == y.node; }
      bool operator!= (const iterator& y) const { return node != y.node; }
      reference operator* () const { return _RWvalue(node); }
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
      pointer operator-> () const { return &(node->value_field); }
#endif
      iterator& operator++ ()
      {
        if (!_RWisNil(_RWright(node)))
        {
          node = _RWright(node);
          while (!_RWisNil(_RWleft(node))) node = _RWleft(node);
        }
        else
        {
          _RWlink_type y = _RWparent(node);
          while (node == _RWright(y))
          {
            node = y; y = _RWparent(y);
          }
          if (_RWright(node) != y) // Necessary because of rightmost.
            node = y;
        }
        return *this;
      }
      iterator operator++ (int)
      {
        iterator tmp = *this; ++*this; return tmp;
      }
      iterator& operator-- ()
      {
        if (_RWcolor(node) == _RWrb_red && _RWparent(_RWparent(node)) == node)  
          //
          // Check for header.
          //
          node = _RWright(node);   // Return rightmost.
        else if (!_RWisNil(_RWleft(node)))
        {
          _RWlink_type y = _RWleft(node);
          while (!_RWisNil(_RWright(y))) y = _RWright(y);
          node = y;
        }
        else
        {
          _RWlink_type y = _RWparent(node);
          while (node == _RWleft(y))
          {
            node = y; y = _RWparent(y);
          }
          node = y;
        }
        return *this;
      }
      iterator operator-- (int)
      {
        iterator tmp = *this; --*this; return tmp;
      }

    };  // End of definition of iterator.

    class const_iterator : public _RWcit
    {
      friend class _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>;
      friend class iterator;

    protected:

      _RWlink_type node;
      const_iterator (_RWlink_type x) : node(x) {}

    public:

      const_iterator () {}
#if defined(__DECCXX) && !defined(__DECFIXCXXL1195)
      const_iterator (const _TYPENAME _RWrb_tree::iterator& x) : node(x.node) {}
#else
      const_iterator (const iterator& x) : node(x.node) {}
#endif
      bool operator== (const const_iterator& y) const
      { 
        return node == y.node; 
      }
      bool operator!= (const const_iterator& y) const
      { 
        return node != y.node; 
      }
      const_reference operator* () const { return _RWvalue(node); }
#ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
      const_pointer operator-> () const { return &(node->value_field); }
#endif
      const_iterator& operator++ ()
      {
        if (!_RWisNil(_RWright(node)))
        {
          node = _RWright(node);
          while (!_RWisNil(_RWleft(node))) node = _RWleft(node);
        }
        else
        {
          _RWlink_type y = _RWparent(node);
          while (node == _RWright(y))
          {
            node = y; y = _RWparent(y);
          }
          if (_RWright(node) != y) // Necessary because of rightmost.
            node = y;
        }
        return *this;
      }
      const_iterator operator++ (int)
      {
        const_iterator tmp = *this; ++*this; return tmp;
      }
      const_iterator& operator-- ()
      {
        if (_RWcolor(node) == _RWrb_red && _RWparent(_RWparent(node)) == node)  
          //
          // Check for header.
          //
          node = _RWright(node);   // return rightmost
        else if (!_RWisNil(_RWleft(node)))
        {
          _RWlink_type y = _RWleft(node);
          while (!_RWisNil(_RWright(y))) y = _RWright(y);
          node = y;
        }
        else
        {
          _RWlink_type y = _RWparent(node);
          while (node == _RWleft(y))
          {
            node = y; y = _RWparent(y);
          }
          node = y;
        }
        return *this;
      }
      const_iterator operator-- (int)
      {
        const_iterator tmp = *this; --*this; return tmp;
      }
    };  // End of definition of const_iterator.

#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
    typedef _RW_STD::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef _RW_STD::reverse_iterator<iterator>  reverse_iterator;
#else
    typedef _RW_STD::_RWreverse_bi_iterator<const_iterator, 
      _RW_STD::bidirectional_iterator_tag, value_type, 
      const_reference, const_pointer, difference_type>
      const_reverse_iterator;
    typedef _RW_STD::_RWreverse_bi_iterator<iterator, 
      _RW_STD::bidirectional_iterator_tag, value_type,
      reference, pointer, difference_type>
      reverse_iterator;
#endif

  private:

    iterator  _RWinsert (_RWlink_type x, _RWlink_type y, const value_type& v);
    _RWlink_type _RWcopy   (_RWlink_type x, _RWlink_type p);
    void      _RWerase  (_RWlink_type x);
    inline void      _RWerase_leaf  (_RWlink_type x);
    void init ()
    {
      _RWbuffer_size = 1;
      _RWbuffer_list = 0;
      _RWfree_list = _RWnext_avail = _RWlast = 0;
      _RWheader        = _RWget_node();
      _RWroot()        = _RWnil();
      _RWleftmost()    = _RWheader;
      _RWrightmost()   = _RWheader;
      _RWbuffer_size   = 
      1 >__RWSTD::_RWrw_allocation_size((value_type*)0,(size_type)0,(size_type)0) ? 1 
           : __RWSTD::_RWrw_allocation_size((value_type*)0,(size_type)0,(size_type)0);
    }

  public:

    _RWrb_tree (const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true),
             const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc())) 
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(always), _RWbuffer_list(0,alloc)
    {
      init();
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    _RWrb_tree (void) 
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_Comp()), 
        _RWinsert_always(true), _RWbuffer_list(0,_Alloc())
    {
      init();
    }

    _RWrb_tree (const _Comp& _RWSTD_COMP) 
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(true), _RWbuffer_list(0,_Alloc())
    {
      init();
    }

    _RWrb_tree (const _Comp& _RWSTD_COMP , bool always = true)
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(always), _RWbuffer_list(0,_Alloc())
    {
      init();
    }
#endif

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    _RWrb_tree (InputIterator first, InputIterator last, 
             const _Comp& comp = _Comp(), bool always = true,
             const _Alloc& alloc = _Alloc())
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(comp), 
        _RWinsert_always(always), _RWbuffer_list(0,alloc)
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }
#else
    _RWrb_tree (const value_type* first, const value_type* last, 
             const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true),
             const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc()))
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(always), _RWbuffer_list(0,alloc)
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }
    _RWrb_tree (const_iterator first, const_iterator last, 
             const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true),
             const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc()))
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(always), _RWbuffer_list(0,alloc)
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }
   
#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    _RWrb_tree (const value_type* first, const value_type* last, 
             const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()))
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(true), _RWbuffer_list(0,_Alloc())
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }

    _RWrb_tree (const value_type* first, const value_type* last, 
             const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true))
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(always), the__Alloc(_Alloc())
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }

    _RWrb_tree (const_iterator first, const_iterator last, 
             const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()))
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(true), _RWbuffer_list(0,_Alloc())
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }

    _RWrb_tree (const_iterator first, const_iterator last, 
             const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true))
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_RWSTD_COMP), 
        _RWinsert_always(always), _RWbuffer_list(0,_Alloc())
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }
#endif
   
#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS    
    _RWrb_tree (const value_type* first, const value_type* last) 
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_Comp()), 
        _RWinsert_always(true), _RWbuffer_list(0,_Alloc())
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }

    _RWrb_tree (const_iterator first, const_iterator last) 
      : _RWnode_count(0), _RWheader(0), _RWkey_compare(_Comp()), 
        _RWinsert_always(true), _RWbuffer_list(0,_Alloc())
    { 
      init(); 
#ifndef _RWSTD_NO_EXCEPTIONS
      try {
        insert(first, last);
      } catch(...) {
        _RWdeallocate_buffers();
        throw;
      }
#else
      insert(first, last);
#endif // _RWSTD_NO_EXCEPTIONS
    }

#endif
#endif

    _RWrb_tree (const _RWrb_tree<_Key,_Val,_KeyOf,_Comp,_Alloc>& x,
             bool always = true)
      : _RWnode_count(x._RWnode_count), _RWheader(0), _RWkey_compare(x._RWkey_compare),
        _RWinsert_always(always), _RWbuffer_list(0,x.get_allocator())
    { 
      _RWbuffer_size   = 1;
      _RWfree_list     = _RWnext_avail = _RWlast = 0;
      _RWheader        = _RWget_node();
      _RWbuffer_size   = 
      1 >  __RWSTD::_RWrw_allocation_size((value_type*)0,(size_type)0,(size_type)0) ?
          1 : __RWSTD::_RWrw_allocation_size((value_type*)0,(size_type)0,(size_type)0);
      _RWcolor(_RWheader) = _RWrb_red;
      _RWroot()        = _RWcopy(x._RWroot(), _RWheader);
      if (_RWisNil(_RWroot()))
      {
        _RWleftmost() = _RWheader; _RWrightmost() = _RWheader;
      }
      else
      {
        _RWleftmost() = _RWminimum(_RWroot()); _RWrightmost() = _RWmaximum(_RWroot());
      }
    }
    ~_RWrb_tree ()
    {
      if (_RWheader)
      {
        erase(begin(), end());
        _RWput_node(_RWheader,false);
        _RWdeallocate_buffers();
      }
    }

    _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& 
    operator= (const _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x);

    _Comp     key_comp () const { return _RWkey_compare; }
    allocator_type get_allocator() const
    {
      return (allocator_type)_RWbuffer_list;
    }

    iterator       begin () const       { return _RWleftmost(); }
    iterator       end   () const       { return _RWheader;     }

#if defined(__DECCXX) && !defined(__DECFIXCXXL1017)
    reverse_iterator rbegin () 
    { 
      reverse_iterator tmp(end()); return tmp;
    }
    const_reverse_iterator rbegin () const
    { 
      const_reverse_iterator tmp(end()); return tmp;
    }
    reverse_iterator rend () 
    { 
      reverse_iterator tmp(begin()); return tmp;
    } 
    const_reverse_iterator rend () const
    { 
      const_reverse_iterator tmp(begin()); return tmp;
    } 
#else
    reverse_iterator rbegin () const
    {
      reverse_iterator tmp(end()); return tmp;
    }
    reverse_iterator rend () const
    {
      reverse_iterator tmp(begin()); return tmp;
    }
#endif
    bool      empty    () const { return _RWnode_count == 0; }
    size_type size     () const { return _RWnode_count;      }
    size_type max_size () const
    { 
      return _RWnode_alloc_type(_RWbuffer_list).max_size(); 
    }
    void swap (_RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& t)
    {
      if((allocator_type)_RWbuffer_list==(allocator_type)t._RWbuffer_list)
      {
#ifndef _RWSTD_NO_NAMESPACE
        std::swap(_RWbuffer_list, t._RWbuffer_list);
        std::swap(_RWfree_list, t._RWfree_list);
        std::swap(_RWnext_avail, t._RWnext_avail);
        std::swap(_RWlast, t._RWlast);
        std::swap(_RWheader, t._RWheader);
        std::swap(_RWnode_count, t._RWnode_count);
        std::swap(_RWinsert_always, t._RWinsert_always);
        std::swap(_RWkey_compare, t._RWkey_compare);
#else
        ::swap(_RWbuffer_list, t._RWbuffer_list);
        ::swap(_RWfree_list, t._RWfree_list);
        ::swap(_RWnext_avail, t._RWnext_avail);
        ::swap(_RWlast, t._RWlast);
        ::swap(_RWheader, t._RWheader);
        ::swap(_RWnode_count, t._RWnode_count);
        ::swap(_RWinsert_always, t._RWinsert_always);
        ::swap(_RWkey_compare, t._RWkey_compare);
#endif
      }
      else
      {
        _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc> _x = *this;
        *this = t;
        t = _x;
      } 
    }

    typedef  _RW_STD::pair<iterator, bool> pair_iterator_bool;
    //
    // typedef done to get around compiler bug.
    //

#ifndef _RWSTD_NO_RET_TEMPLATE
    _RW_STD::pair<iterator,bool> insert (const value_type& x);
#else
    pair_iterator_bool  insert (const value_type& x);
#endif

    iterator  insert (iterator position, const value_type& x);

#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 position);
    size_type erase  (const key_type& x);
    iterator  erase  (iterator first, iterator last);
    void      erase  (const key_type* first, const key_type* last);

    iterator find        (const key_type& x) const;
    size_type  count     (const key_type& x) const;
    iterator lower_bound (const key_type& x) const;
    iterator upper_bound (const key_type& x) const;

    typedef  _RW_STD::pair<iterator, iterator> pair_iterator_iterator; 
    //
    // typedef done to get around compiler bug.
    //
#ifndef _RWSTD_NO_RET_TEMPLATE
    _RW_STD::pair<iterator,iterator> equal_range (const key_type& x) const;
#else
    pair_iterator_iterator equal_range (const key_type& x) const;
#endif

    inline void _RWrotate_left  (_RWlink_type x);
    inline void _RWrotate_right (_RWlink_type x);

    // Query and set the allocation size
    size_type allocation_size() { return _RWbuffer_size; }
    size_type allocation_size(size_type new_size) 
    { 
      size_type tmp = _RWbuffer_size; 
      _RWbuffer_size = 1 > new_size ? 1 : new_size; //max((size_type)1,new_size);
      return tmp;
    }  
  };


//
// Inline functions
//

  template <class _Key, class _Val, class _KeyOf, 
  class _Comp, class _Alloc>
  inline bool operator== (const _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x, 
                          const _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& y)
  {
    return x.size() == y.size() && _RW_STD::equal(x.begin(), x.end(), y.begin());
  }

  template <class _Key, class _Val, class _KeyOf, 
  class _Comp, class _Alloc>
  inline bool operator< (const _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x, 
                         const _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& y)
  {
    return _RW_STD::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  }

  template <class _Key,class _Val,class _KeyOf,class _Comp,class _Alloc>
  inline  void   
  _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_RWerase_leaf (_RWlink_type x)
  {
    // Remove a leaf node from the tree
    _RWlink_type y = _RWparent(x);
    if (y == _RWheader)
    {
      _RWleftmost() = _RWrightmost() = y;
      _RWroot() = _RWnil();
    }
    else if (_RWleft(y) == x)
    {
      _RWleft(y) = _RWnil();
      if (_RWleftmost() == x)
        _RWleftmost() = y;
    }
    else
    {
      _RWright(y) = _RWnil();
      if (_RWrightmost() == x)
        _RWrightmost() = y;
    }
  }

  template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  inline void 
  _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_RWrotate_left (_RWlink_type x)
  {
    _RWlink_type y = _RWright(x);
    _RWright(x) = _RWleft(y);
    if (!_RWisNil(_RWleft(y)))
      _RWparent(_RWleft(y)) = x;
    _RWparent(y) = _RWparent(x);
    if (x == _RWroot())
      _RWroot() = y;
    else if (x == _RWleft(_RWparent(x)))
      _RWleft(_RWparent(x)) = y;
    else
      _RWright(_RWparent(x)) = y;
    _RWleft(y) = x;
    _RWparent(x) = y;
  }


  template <class _Key, class _Val, class _KeyOf, 
  class _Comp, class _Alloc>
  inline void 
  _RWrb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_RWrotate_right (_RWlink_type x)
  {
    _RWlink_type y = _RWleft(x);
    _RWleft(x) = _RWright(y);
    if (!_RWisNil(_RWright(y)))
      _RWparent(_RWright(y)) = x;
    _RWparent(y) = _RWparent(x);
    if (x == _RWroot())
      _RWroot() = y;
    else if (x == _RWright(_RWparent(x)))
      _RWright(_RWparent(x)) = y;
    else
      _RWleft(_RWparent(x)) = y;
    _RWright(y) = x;
    _RWparent(x) = y;
  }

#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#   pragma __extern_prefix __restore
#endif

#ifdef _RWSTD_COMPILE_INSTANTIATE
#include <tree.cc>
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __restore
#   endif
#endif

#endif /* __STD_TREE__ */

