home *** CD-ROM | disk | FTP | other *** search
/ PC Format (South-Africa) 2001 May / PCFMay2001.iso / Xenon / C++ / FreeCommandLineTools.exe / Include / Rw / tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-01-31  |  29.4 KB  |  944 lines
  1. #ifndef __TREE_H
  2. #define __TREE_H
  3. #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
  4. // -*- C++ -*-
  5. #ifndef __STD_TREE__
  6. #define __STD_TREE__
  7.  
  8. /***************************************************************************
  9.  *
  10.  * tree - Declarations for the Standard Library tree classes
  11.  *
  12.  ***************************************************************************
  13.  *
  14.  * Copyright (c) 1994
  15.  * Hewlett-Packard Company
  16.  *
  17.  * Permission to use, copy, modify, distribute and sell this software
  18.  * and its documentation for any purpose is hereby granted without fee,
  19.  * provided that the above copyright notice appear in all copies and
  20.  * that both that copyright notice and this permission notice appear
  21.  * in supporting documentation.  Hewlett-Packard Company makes no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied warranty.
  24.  *
  25.  *
  26.  ***************************************************************************
  27.  *
  28.  * Copyright (c) 1994-1999 Rogue Wave Software, Inc.  All Rights Reserved.
  29.  *
  30.  * This computer software is owned by Rogue Wave Software, Inc. and is
  31.  * protected by U.S. copyright laws and other laws and by international
  32.  * treaties.  This computer software is furnished by Rogue Wave Software,
  33.  * Inc. pursuant to a written license agreement and may be used, copied,
  34.  * transmitted, and stored only in accordance with the terms of such
  35.  * license and with the inclusion of the above copyright notice.  This
  36.  * computer software or any other copies thereof may not be provided or
  37.  * otherwise made available to any other person.
  38.  *
  39.  * U.S. Government Restricted Rights.  This computer software is provided
  40.  * with Restricted Rights.  Use, duplication, or disclosure by the
  41.  * Government is subject to restrictions as set forth in subparagraph (c)
  42.  * (1) (ii) of The Rights in Technical Data and Computer Software clause
  43.  * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
  44.  * Commercial Computer Software รป Restricted Rights at 48 CFR 52.227-19,
  45.  * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
  46.  * Flatiron Parkway, Boulder, Colorado 80301 USA.
  47.  *
  48.  **************************************************************************/
  49.  
  50. /*
  51. **
  52. ** Red-black tree class, designed for use in implementing STL
  53. ** associative containers (set, multiset, map, and multimap). The
  54. ** insertion and deletion algorithms are based on those in Cormen,
  55. ** Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
  56. ** except that:
  57. ** 
  58. ** (1) the header cell is maintained with links not only to the root
  59. ** but also to the leftmost node of the tree, to enable constant time
  60. ** begin(), and to the rightmost node of the tree, to enable linear time
  61. ** performance when used with the generic set algorithms (set_union,
  62. ** etc.);
  63. ** 
  64. ** (2) when a node being deleted has two children its successor node is
  65. ** relinked into its place, rather than copied, so that the only
  66. ** iterators invalidated are those referring to the deleted node.
  67. ** 
  68. */
  69.  
  70. #include <stdcomp.h>
  71. #include <algorithm>
  72. #include <iterator>
  73.  
  74. #ifndef _RWSTD_NO_NAMESPACE
  75. namespace __rwstd {
  76. #endif
  77.  
  78. #ifndef __rb_tree 
  79. #define __rb_tree __rb_tree
  80. #endif
  81.  
  82.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  83.   class __rb_tree
  84.   {
  85.   protected:
  86.  
  87.     enum __color_type { __rb_red, __rb_black };
  88.  
  89.     struct __rb_tree_node;
  90.     friend struct __rb_tree_node;
  91.  
  92. #ifdef _RWSTD_ALLOCATOR
  93.     typedef _TYPENAME _Alloc::template rebind<_Val>::other  __value_alloc_type;
  94.     typedef _TYPENAME _Alloc::template rebind<_Key>::other  __key_alloc_type;
  95.     typedef _TYPENAME _Alloc::template rebind<__rb_tree_node>::other  __node_alloc_type;
  96. #else
  97.     typedef _RW_STD::allocator_interface<_Alloc,_Val>      __value_alloc_type;
  98.     typedef _RW_STD::allocator_interface<_Alloc,_Key>        __key_alloc_type;
  99.     typedef _RW_STD::allocator_interface<_Alloc,__rb_tree_node> __node_alloc_type;
  100. #endif
  101.  
  102.     typedef _TYPENAME __node_alloc_type::pointer          __link_type;
  103.  
  104.     struct __rb_tree_node
  105.     {
  106.       __color_type   color_field; 
  107.       __link_type parent_link;
  108.       __link_type left_link;
  109.       __link_type right_link;
  110.       _Val        value_field;
  111.     };
  112.  
  113.     typedef _TYPENAME __key_alloc_type::const_reference    const_key_reference;
  114.  
  115.   public:
  116.  
  117.     typedef _Key                                    key_type;
  118.     typedef _Val                                    value_type;
  119.     typedef _Alloc                                  allocator_type;
  120.     typedef _TYPENAME __value_alloc_type::pointer          pointer;
  121.     typedef _TYPENAME __value_alloc_type::const_pointer    const_pointer;
  122.  
  123. #ifndef _RWSTD_NO_COMPLICATED_TYPEDEF
  124.     typedef _TYPENAME _Alloc::size_type                 size_type;
  125.     typedef _TYPENAME _Alloc::size_type                 difference_type;
  126.     typedef _TYPENAME __value_alloc_type::reference       reference;
  127.     typedef _TYPENAME __value_alloc_type::const_reference const_reference;
  128. #else
  129.     typedef size_t             size_type;
  130.     typedef ptrdiff_t          difference_type;
  131.     typedef _Val&              reference;
  132.     typedef const _Val&        const_reference;
  133. #endif  //_RWSTD_NO_COMPLICATED_TYPEDEF
  134.  
  135.   protected:
  136.     size_type __buffer_size;
  137.  
  138.     struct __rb_tree_node_buffer;
  139.     friend struct __rb_tree_node_buffer;
  140.  
  141. #ifdef _RWSTD_ALLOCATOR
  142.     typedef _TYPENAME allocator_type::template rebind<__rb_tree_node_buffer>::other  __buffer_alloc_type;
  143. #else
  144.     typedef _RW_STD::allocator_interface<_Alloc,__rb_tree_node_buffer> __buffer_alloc_type;
  145. #endif
  146.     typedef _TYPENAME __buffer_alloc_type::pointer __buffer_pointer;
  147.  
  148.     struct __rb_tree_node_buffer
  149.     {
  150.        __buffer_pointer  next_buffer;
  151.       size_type size;
  152.       __link_type buffer;
  153.     };
  154.  
  155.     __RWSTD::__rw_basis<__buffer_pointer,allocator_type>   __buffer_list;
  156.     __link_type                      __free_list;
  157.     __link_type                      __next_avail;
  158.     __link_type                      __last;
  159.  
  160.     static bool __isNil(const __link_type& l) 
  161.     {  return l == __nil();  }
  162.  
  163.     void __add_new_buffer ()
  164.     {
  165.       __buffer_pointer tmp = __buffer_alloc_type(__buffer_list).allocate(_RWSTD_STATIC_CAST(size_type,1),__buffer_list.data());
  166. #ifndef _RWSTD_NO_EXCEPTIONS
  167.       try {
  168.         tmp->buffer        = __node_alloc_type(__buffer_list).allocate(__buffer_size,__last);
  169.       } catch(...) {
  170.         __buffer_alloc_type(__buffer_list).deallocate(tmp,1);
  171.         throw;
  172.       } 
  173. #else
  174.       tmp->buffer        = __node_alloc_type(__buffer_list).allocate(__buffer_size,__last);
  175. #endif //  _RWSTD_NO_EXCEPTIONS     
  176.       tmp->next_buffer   = __buffer_list;
  177.       tmp->size          = __buffer_size;
  178.       __buffer_list        = tmp;
  179.       __next_avail         = __buffer_list.data()->buffer;
  180.       __last               = __next_avail + __buffer_size;
  181.     }
  182.     void __deallocate_buffers ();
  183.  
  184.     // 
  185.     // Return a node from the free list or new storage
  186.     //
  187.     __link_type __get_link()
  188.     {
  189.       __link_type tmp = __free_list;
  190.       __link_type tmp2 = __free_list ? 
  191.         (__free_list = _RWSTD_STATIC_CAST(__link_type,(__free_list->right_link)), tmp) 
  192.         : (__next_avail == __last ? (__add_new_buffer(), __next_avail++) 
  193.           : __next_avail++);
  194.       tmp2->parent_link = __nil();
  195.       tmp2->left_link = __nil();
  196.       tmp2->right_link = __nil();
  197.       tmp2->color_field = __rb_red;
  198.       return tmp2;
  199.     }
  200.  
  201.     //
  202.     // Return a node from the free list or new storage with
  203.     // the _Val v constructed on it.  Every call to __get_node
  204.     // must eventually be followed by a call to __put_node.
  205.     //
  206.     __link_type __get_node (const _Val& v)
  207.     {
  208.       __link_type tmp2 = __get_link();
  209.       __value_alloc_type va(__buffer_list);
  210. #ifndef _RWSTD_NO_EXCEPTIONS
  211.       try {
  212.         va.construct(va.address(__value(tmp2)),v);
  213.       } catch(...) {
  214.         __put_node(tmp2,false);
  215.         throw;
  216.       }      
  217. #else
  218.       va.construct(va.address(__value(tmp2)),v);
  219. #endif // _RWSTD_NO_EXCEPTIONS
  220.       return tmp2;
  221.     }
  222.     __link_type __get_node ()
  223.     {
  224.       return __get_link();
  225.     }
  226.  
  227.     // 
  228.     // Return a node to the free list and destroy the value in it.
  229.     //
  230.     void __put_node (__link_type p, bool do_destroy = true) 
  231.     { 
  232.       p->right_link = __free_list; 
  233.       if (do_destroy)      
  234.       {
  235.         __value_alloc_type va(__buffer_list);
  236.         va.destroy(va.address(__value(p)));  
  237.       }
  238.       __free_list = p; 
  239.     }
  240.  
  241.   protected:
  242.  
  243.     __link_type  __header;  
  244.     __link_type& __root      ()       { return __parent(__header); }
  245.     __link_type& __root      () const { return __parent(__header); }
  246.     __link_type& __leftmost  ()       { return __left(__header);   }
  247.     __link_type& __leftmost  () const { return __left(__header);   }
  248.     __link_type& __rightmost ()       { return __right(__header);  }
  249.     __link_type& __rightmost () const { return __right(__header);  }
  250.  
  251.     size_type  __node_count;    // Keeps track of size of tree.
  252.     bool       __insert_always; // Controls whether an element already in the
  253.     // tree is inserted again.
  254.     _Comp      __key_compare;
  255.  
  256.     static __link_type __nil () { return NULL; }
  257.  
  258.     static __link_type& __left (__link_type x)
  259.     {
  260.       return _RWSTD_REINTERPRET_CAST(__link_type&,((*x).left_link));
  261.     }
  262.     static __link_type& __right (__link_type x)
  263.     {
  264.       return _RWSTD_REINTERPRET_CAST(__link_type&,((*x).right_link));
  265.     }
  266.     static __link_type& __parent (__link_type x)
  267.     {
  268.       return _RWSTD_REINTERPRET_CAST(__link_type&,((*x).parent_link));
  269.     }
  270.     static reference __value (__link_type x) { return (*x).value_field; }
  271.     static const_key_reference __key (__link_type x)
  272.     {
  273.       return _KeyOf()(__value(x));
  274.     }
  275.     static __color_type& __color (__link_type x)
  276.     {
  277.       return _RWSTD_STATIC_CAST(__color_type&,(*x).color_field);
  278.     }
  279.     static __link_type __minimum (__link_type x)
  280.     {
  281.       while (!__isNil(__left(x))) x = __left(x);
  282.       return x;
  283.     }
  284.     static __link_type __maximum (__link_type x)
  285.     {
  286.       while (!__isNil(__right(x))) x = __right(x);
  287.       return x;
  288.     }
  289.  
  290.     typedef _RW_STD::iterator<_RW_STD::bidirectional_iterator_tag, value_type,
  291.                     difference_type, pointer,reference> __it;
  292.     typedef _RW_STD::iterator<_RW_STD::bidirectional_iterator_tag, value_type, 
  293.                     difference_type, const_pointer, const_reference> __cit;
  294.  
  295.   public:
  296.  
  297.     class  iterator;
  298.     friend class iterator;
  299.     class  const_iterator;
  300.     friend class const_iterator;
  301.  
  302.     class iterator : public __it
  303.     {
  304.       friend class __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>;
  305.       friend class const_iterator;
  306.  
  307.     protected:
  308.  
  309.       __link_type node;
  310.       iterator (__link_type x) : node(x) {}        
  311.  
  312.     public:
  313.  
  314.       iterator () {}
  315.       bool operator== (const iterator& y) const { return node == y.node; }
  316.       bool operator!= (const iterator& y) const { return node != y.node; }
  317.       reference operator* () const { return __value(node); }
  318. #ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
  319.       pointer operator-> () const { return &(node->value_field); }
  320. #endif
  321.       iterator& operator++ ()
  322.       {
  323.         if (!__isNil(__right(node)))
  324.         {
  325.           node = __right(node);
  326.           while (!__isNil(__left(node))) node = __left(node);
  327.         }
  328.         else
  329.         {
  330.           __link_type y = __parent(node);
  331.           while (node == __right(y))
  332.           {
  333.             node = y; y = __parent(y);
  334.           }
  335.           if (__right(node) != y) // Necessary because of rightmost.
  336.             node = y;
  337.         }
  338.         return *this;
  339.       }
  340.       iterator operator++ (int)
  341.       {
  342.         iterator tmp = *this; ++*this; return tmp;
  343.       }
  344.       iterator& operator-- ()
  345.       {
  346.         if (__color(node) == __rb_red && __parent(__parent(node)) == node)  
  347.           //
  348.           // Check for header.
  349.           //
  350.           node = __right(node);   // Return rightmost.
  351.         else if (!__isNil(__left(node)))
  352.         {
  353.           __link_type y = __left(node);
  354.           while (!__isNil(__right(y))) y = __right(y);
  355.           node = y;
  356.         }
  357.         else
  358.         {
  359.           __link_type y = __parent(node);
  360.           while (node == __left(y))
  361.           {
  362.             node = y; y = __parent(y);
  363.           }
  364.           node = y;
  365.         }
  366.         return *this;
  367.       }
  368.       iterator operator-- (int)
  369.       {
  370.         iterator tmp = *this; --*this; return tmp;
  371.       }
  372.  
  373.     };  // End of definition of iterator.
  374.  
  375.     class const_iterator : public __cit
  376.     {
  377.       friend class __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>;
  378.       friend class iterator;
  379.  
  380.     protected:
  381.  
  382.       __link_type node;
  383.       const_iterator (__link_type x) : node(x) {}
  384.  
  385.     public:
  386.  
  387.       const_iterator () {}
  388. #if !defined(_MSC_VER) || defined(__BORLANDC__)
  389.       const_iterator  (const _TYPENAME __rb_tree<_Key,_Val,_KeyOf,_Comp,_Alloc>::iterator& x) : node(x.node) {}
  390. #else
  391.       const_iterator  (const iterator& x) : node(x.node) {}
  392. #endif
  393.  
  394.       bool operator== (const const_iterator& y) const
  395.       { 
  396.         return node == y.node; 
  397.       }
  398.       bool operator!= (const const_iterator& y) const
  399.       { 
  400.         return node != y.node; 
  401.       }
  402.       const_reference operator* () const { return __value(node); }
  403. #ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN
  404.       const_pointer operator-> () const { return &(node->value_field); }
  405. #endif
  406.       const_iterator& operator++ ()
  407.       {
  408.         if (!__isNil(__right(node)))
  409.         {
  410.           node = __right(node);
  411.           while (!__isNil(__left(node))) node = __left(node);
  412.         }
  413.         else
  414.         {
  415.           __link_type y = __parent(node);
  416.           while (node == __right(y))
  417.           {
  418.             node = y; y = __parent(y);
  419.           }
  420.           if (__right(node) != y) // Necessary because of rightmost.
  421.             node = y;
  422.         }
  423.         return *this;
  424.       }
  425.       const_iterator operator++ (int)
  426.       {
  427.         const_iterator tmp = *this; ++*this; return tmp;
  428.       }
  429.       const_iterator& operator-- ()
  430.       {
  431.         if (__color(node) == __rb_red && __parent(__parent(node)) == node)  
  432.           //
  433.           // Check for header.
  434.           //
  435.           node = __right(node);   // return rightmost
  436.         else if (!__isNil(__left(node)))
  437.         {
  438.           __link_type y = __left(node);
  439.           while (!__isNil(__right(y))) y = __right(y);
  440.           node = y;
  441.         }
  442.         else
  443.         {
  444.           __link_type y = __parent(node);
  445.           while (node == __left(y))
  446.           {
  447.             node = y; y = __parent(y);
  448.           }
  449.           node = y;
  450.         }
  451.         return *this;
  452.       }
  453.       const_iterator operator-- (int)
  454.       {
  455.         const_iterator tmp = *this; --*this; return tmp;
  456.       }
  457.     };  // End of definition of const_iterator.
  458.  
  459. #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC 
  460.     typedef _RW_STD::reverse_iterator<const_iterator> const_reverse_iterator;
  461.     typedef _RW_STD::reverse_iterator<iterator>  reverse_iterator;
  462. #else
  463.     typedef _RW_STD::__reverse_bi_iterator<const_iterator, 
  464.       _RW_STD::bidirectional_iterator_tag, value_type, 
  465.       const_reference, const_pointer, difference_type>
  466.       const_reverse_iterator;
  467.     typedef _RW_STD::__reverse_bi_iterator<iterator, 
  468.       _RW_STD::bidirectional_iterator_tag, value_type,
  469.       reference, pointer, difference_type>
  470.       reverse_iterator;
  471. #endif
  472.  
  473.   private:
  474.  
  475.     iterator  __insert (__link_type x, __link_type y, const value_type& v);
  476.     __link_type __copy   (__link_type x, __link_type p);
  477.     void      __erase  (__link_type x);
  478.     inline void      __erase_leaf  (__link_type x);
  479.     void init ()
  480.     {
  481.       __buffer_size = 1;
  482.       __buffer_list = 0;
  483.       __free_list = __next_avail = __last = 0;
  484.       __header        = __get_node();
  485.       __root()        = __nil();
  486.       __leftmost()    = __header;
  487.       __rightmost()   = __header;
  488.       __buffer_size   = 
  489.       1 >__RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0) ? 1 
  490.            : __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0);
  491.     }
  492.  
  493.   public:
  494.  
  495.     __rb_tree (const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true),
  496.              const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc())) 
  497.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  498.         __insert_always(always), __buffer_list(0,alloc)
  499.     {
  500.       init();
  501.     }
  502.  
  503. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  504.     __rb_tree (void) 
  505.       : __node_count(0), __header(0), __key_compare(_Comp()), 
  506.         __insert_always(true), __buffer_list(0,_Alloc())
  507.     {
  508.       init();
  509.     }
  510.  
  511.     __rb_tree (const _Comp& _RWSTD_COMP) 
  512.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  513.         __insert_always(true), __buffer_list(0,_Alloc())
  514.     {
  515.       init();
  516.     }
  517.  
  518.     __rb_tree (const _Comp& _RWSTD_COMP , bool always = true)
  519.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  520.         __insert_always(always), __buffer_list(0,_Alloc())
  521.     {
  522.       init();
  523.     }
  524. #endif
  525.  
  526. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  527.     template<class InputIterator>
  528.     __rb_tree (InputIterator first, InputIterator last, 
  529.              const _Comp& comp = _Comp(), bool always = true,
  530.              const _Alloc& alloc = _Alloc())
  531.       : __node_count(0), __header(0), __key_compare(comp), 
  532.         __insert_always(always), __buffer_list(0,alloc)
  533.     { 
  534.       init(); 
  535. #ifndef _RWSTD_NO_EXCEPTIONS
  536.       try {
  537.         insert(first, last);
  538.       } catch(...) {
  539.         __deallocate_buffers();
  540.         throw;
  541.       }
  542. #else
  543.       insert(first, last);
  544. #endif // _RWSTD_NO_EXCEPTIONS
  545.     }
  546. #else
  547.     __rb_tree (const value_type* first, const value_type* last, 
  548.              const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true),
  549.              const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc()))
  550.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  551.         __insert_always(always), __buffer_list(0,alloc)
  552.     { 
  553.       init(); 
  554. #ifndef _RWSTD_NO_EXCEPTIONS
  555.       try {
  556.         insert(first, last);
  557.       } catch(...) {
  558.         __deallocate_buffers();
  559.         throw;
  560.       }
  561. #else
  562.       insert(first, last);
  563. #endif // _RWSTD_NO_EXCEPTIONS
  564.     }
  565.     __rb_tree (const_iterator first, const_iterator last, 
  566.              const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true),
  567.              const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc()))
  568.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  569.         __insert_always(always), __buffer_list(0,alloc)
  570.     { 
  571.       init(); 
  572. #ifndef _RWSTD_NO_EXCEPTIONS
  573.       try {
  574.         insert(first, last);
  575.       } catch(...) {
  576.         __deallocate_buffers();
  577.         throw;
  578.       }
  579. #else
  580.       insert(first, last);
  581. #endif // _RWSTD_NO_EXCEPTIONS
  582.     }
  583.    
  584. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  585.     __rb_tree (const value_type* first, const value_type* last, 
  586.              const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()))
  587.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  588.         __insert_always(true), __buffer_list(0,_Alloc())
  589.     { 
  590.       init(); 
  591. #ifndef _RWSTD_NO_EXCEPTIONS
  592.       try {
  593.         insert(first, last);
  594.       } catch(...) {
  595.         __deallocate_buffers();
  596.         throw;
  597.       }
  598. #else
  599.       insert(first, last);
  600. #endif // _RWSTD_NO_EXCEPTIONS
  601.     }
  602.  
  603.     __rb_tree (const value_type* first, const value_type* last, 
  604.              const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true))
  605.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  606.         __insert_always(always), the__Alloc(_Alloc())
  607.     { 
  608.       init(); 
  609. #ifndef _RWSTD_NO_EXCEPTIONS
  610.       try {
  611.         insert(first, last);
  612.       } catch(...) {
  613.         __deallocate_buffers();
  614.         throw;
  615.       }
  616. #else
  617.       insert(first, last);
  618. #endif // _RWSTD_NO_EXCEPTIONS
  619.     }
  620.  
  621.     __rb_tree (const_iterator first, const_iterator last, 
  622.              const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()))
  623.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  624.         __insert_always(true), __buffer_list(0,_Alloc())
  625.     { 
  626.       init(); 
  627. #ifndef _RWSTD_NO_EXCEPTIONS
  628.       try {
  629.         insert(first, last);
  630.       } catch(...) {
  631.         __deallocate_buffers();
  632.         throw;
  633.       }
  634. #else
  635.       insert(first, last);
  636. #endif // _RWSTD_NO_EXCEPTIONS
  637.     }
  638.  
  639.     __rb_tree (const_iterator first, const_iterator last, 
  640.              const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true))
  641.       : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), 
  642.         __insert_always(always), __buffer_list(0,_Alloc())
  643.     { 
  644.       init(); 
  645. #ifndef _RWSTD_NO_EXCEPTIONS
  646.       try {
  647.         insert(first, last);
  648.       } catch(...) {
  649.         __deallocate_buffers();
  650.         throw;
  651.       }
  652. #else
  653.       insert(first, last);
  654. #endif // _RWSTD_NO_EXCEPTIONS
  655.     }
  656. #endif
  657.    
  658. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS    
  659.     __rb_tree (const value_type* first, const value_type* last) 
  660.       : __node_count(0), __header(0), __key_compare(_Comp()), 
  661.         __insert_always(true), __buffer_list(0,_Alloc())
  662.     { 
  663.       init(); 
  664. #ifndef _RWSTD_NO_EXCEPTIONS
  665.       try {
  666.         insert(first, last);
  667.       } catch(...) {
  668.         __deallocate_buffers();
  669.         throw;
  670.       }
  671. #else
  672.       insert(first, last);
  673. #endif // _RWSTD_NO_EXCEPTIONS
  674.     }
  675.  
  676.     __rb_tree (const_iterator first, const_iterator last) 
  677.       : __node_count(0), __header(0), __key_compare(_Comp()), 
  678.         __insert_always(true), __buffer_list(0,_Alloc())
  679.     { 
  680.       init(); 
  681. #ifndef _RWSTD_NO_EXCEPTIONS
  682.       try {
  683.         insert(first, last);
  684.       } catch(...) {
  685.         __deallocate_buffers();
  686.         throw;
  687.       }
  688. #else
  689.       insert(first, last);
  690. #endif // _RWSTD_NO_EXCEPTIONS
  691.     }
  692.  
  693. #endif
  694. #endif
  695.  
  696.     __rb_tree (const __rb_tree<_Key,_Val,_KeyOf,_Comp,_Alloc>& x,
  697.              bool always = true)
  698.       : __node_count(x.__node_count), __header(0), __key_compare(x.__key_compare),
  699.         __insert_always(always), __buffer_list(0,x.get_allocator())
  700.     { 
  701.       __buffer_size   = 1;
  702.       __free_list     = __next_avail = __last = 0;
  703.       __header        = __get_node();
  704.       __buffer_size   = 
  705.       1 >  __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0) ?
  706.           1 : __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0);
  707.       __color(__header) = __rb_red;
  708.       __root()        = __copy(x.__root(), __header);
  709.       if (__isNil(__root()))
  710.       {
  711.         __leftmost() = __header; __rightmost() = __header;
  712.       }
  713.       else
  714.       {
  715.         __leftmost() = __minimum(__root()); __rightmost() = __maximum(__root());
  716.       }
  717.     }
  718.     ~__rb_tree ()
  719.     {
  720.       if (__header)
  721.       {
  722.         erase(begin(), end());
  723.         __put_node(__header,false);
  724.         __deallocate_buffers();
  725.       }
  726.     }
  727.  
  728.     __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& 
  729.     operator= (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x);
  730.  
  731.     _Comp     key_comp () const { return __key_compare; }
  732.     allocator_type get_allocator() const
  733.     {
  734.       return (allocator_type)__buffer_list;
  735.     }
  736.  
  737.     iterator begin () const { return __leftmost(); }
  738.     iterator end   () const { return __header;     }
  739.  
  740.     reverse_iterator rbegin ()
  741.     { 
  742.       reverse_iterator tmp(end()); return tmp;
  743.     }
  744.     reverse_iterator rend ()
  745.     { 
  746.       reverse_iterator tmp(begin()); return tmp;
  747.     } 
  748.  
  749.     const_reverse_iterator rbegin () const
  750.     { 
  751.       const_reverse_iterator tmp(end()); return tmp;
  752.     }
  753.     const_reverse_iterator rend () const
  754.     { 
  755.       const_reverse_iterator tmp(begin()); return tmp;
  756.     } 
  757.  
  758.     bool      empty    () const { return __node_count == 0; }
  759.     size_type size     () const { return __node_count;      }
  760.     size_type max_size () const
  761.     { 
  762.       return __node_alloc_type(__buffer_list).max_size(); 
  763.     }
  764.     void swap (__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& t)
  765.     {
  766.       if((allocator_type)__buffer_list==(allocator_type)t.__buffer_list)
  767.       {
  768. #ifndef _RWSTD_NO_NAMESPACE
  769.         std::swap(__buffer_list, t.__buffer_list);
  770.         std::swap(__free_list, t.__free_list);
  771.         std::swap(__next_avail, t.__next_avail);
  772.         std::swap(__last, t.__last);
  773.         std::swap(__header, t.__header);
  774.         std::swap(__node_count, t.__node_count);
  775.         std::swap(__insert_always, t.__insert_always);
  776.         std::swap(__key_compare, t.__key_compare);
  777. #else
  778.         ::swap(__buffer_list, t.__buffer_list);
  779.         ::swap(__free_list, t.__free_list);
  780.         ::swap(__next_avail, t.__next_avail);
  781.         ::swap(__last, t.__last);
  782.         ::swap(__header, t.__header);
  783.         ::swap(__node_count, t.__node_count);
  784.         ::swap(__insert_always, t.__insert_always);
  785.         ::swap(__key_compare, t.__key_compare);
  786. #endif
  787.       }
  788.       else
  789.       {
  790.         __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc> _x = *this;
  791.         *this = t;
  792.         t = _x;
  793.       } 
  794.     }
  795.  
  796.     typedef  _RW_STD::pair<iterator, bool> pair_iterator_bool;
  797.     //
  798.     // typedef done to get around compiler bug.
  799.     //
  800.  
  801. #ifndef _RWSTD_NO_RET_TEMPLATE
  802.     _RW_STD::pair<iterator,bool> insert (const value_type& x);
  803. #else
  804.     pair_iterator_bool  insert (const value_type& x);
  805. #endif
  806.  
  807.     iterator  insert (iterator position, const value_type& x);
  808.  
  809. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  810.     template<class Iterator>
  811.     void      insert (Iterator first, Iterator last);
  812. #else
  813.     void      insert (const_iterator first, const_iterator last);
  814.     void      insert (const value_type* first, const value_type* last);
  815. #endif
  816.  
  817.     iterator  erase  (iterator position);
  818.     size_type erase  (const key_type& x);
  819.     iterator  erase  (iterator first, iterator last);
  820.     void      erase  (const key_type* first, const key_type* last);
  821.  
  822.     iterator find        (const key_type& x) const;
  823.     size_type  count     (const key_type& x) const;
  824.     iterator lower_bound (const key_type& x) const;
  825.     iterator upper_bound (const key_type& x) const;
  826.  
  827.     typedef  _RW_STD::pair<iterator, iterator> pair_iterator_iterator; 
  828.     //
  829.     // typedef done to get around compiler bug.
  830.     //
  831. #ifndef _RWSTD_NO_RET_TEMPLATE
  832.     _RW_STD::pair<iterator,iterator> equal_range (const key_type& x) const;
  833. #else
  834.     pair_iterator_iterator equal_range (const key_type& x) const;
  835. #endif
  836.  
  837.     inline void __rotate_left  (__link_type x);
  838.     inline void __rotate_right (__link_type x);
  839.  
  840.     // Query and set the allocation size
  841.     size_type allocation_size() { return __buffer_size; }
  842.     size_type allocation_size(size_type new_size) 
  843.     { 
  844.       size_type tmp = __buffer_size; 
  845.       __buffer_size = 1 > new_size ? 1 : new_size; //max((size_type)1,new_size);
  846.       return tmp;
  847.     }  
  848.   };
  849. //
  850. // Inline functions
  851. //
  852.  
  853.   template <class _Key, class _Val, class _KeyOf, 
  854.   class _Comp, class _Alloc>
  855.   inline bool operator== (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x, 
  856.                           const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& y)
  857.   {
  858.     return x.size() == y.size() && _RW_STD::equal(x.begin(), x.end(), y.begin());
  859.   }
  860.  
  861.   template <class _Key, class _Val, class _KeyOf, 
  862.   class _Comp, class _Alloc>
  863.   inline bool operator< (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x, 
  864.                          const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& y)
  865.   {
  866.     return _RW_STD::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  867.   }
  868.  
  869.   template <class _Key,class _Val,class _KeyOf,class _Comp,class _Alloc>
  870.   inline  void   
  871.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__erase_leaf (__link_type x)
  872.   {
  873.     // Remove a leaf node from the tree
  874.     __link_type y = __parent(x);
  875.     if (y == __header)
  876.     {
  877.       __leftmost() = __rightmost() = y;
  878.       __root() = __nil();
  879.     }
  880.     else if (__left(y) == x)
  881.     {
  882.       __left(y) = __nil();
  883.       if (__leftmost() == x)
  884.         __leftmost() = y;
  885.     }
  886.     else
  887.     {
  888.       __right(y) = __nil();
  889.       if (__rightmost() == x)
  890.         __rightmost() = y;
  891.     }
  892.   }
  893.  
  894.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  895.   inline void 
  896.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__rotate_left (__link_type x)
  897.   {
  898.     __link_type y = __right(x);
  899.     __right(x) = __left(y);
  900.     if (!__isNil(__left(y)))
  901.       __parent(__left(y)) = x;
  902.     __parent(y) = __parent(x);
  903.     if (x == __root())
  904.       __root() = y;
  905.     else if (x == __left(__parent(x)))
  906.       __left(__parent(x)) = y;
  907.     else
  908.       __right(__parent(x)) = y;
  909.     __left(y) = x;
  910.     __parent(x) = y;
  911.   }
  912.   template <class _Key, class _Val, class _KeyOf, 
  913.   class _Comp, class _Alloc>
  914.   inline void 
  915.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__rotate_right (__link_type x)
  916.   {
  917.     __link_type y = __left(x);
  918.     __left(x) = __right(y);
  919.     if (!__isNil(__right(y)))
  920.       __parent(__right(y)) = x;
  921.     __parent(y) = __parent(x);
  922.     if (x == __root())
  923.       __root() = y;
  924.     else if (x == __right(__parent(x)))
  925.       __right(__parent(x)) = y;
  926.     else
  927.       __left(__parent(x)) = y;
  928.     __right(y) = x;
  929.     __parent(x) = y;
  930.   }
  931.  
  932. #ifndef _RWSTD_NO_NAMESPACE
  933. }
  934. #endif
  935.  
  936. #ifdef _RWSTD_NO_TEMPLATE_REPOSITORY
  937. #include <rw/tree.cc>
  938. #endif
  939.  
  940. #endif /* __STD_TREE__ */
  941.  
  942. #pragma option pop
  943. #endif /* __TREE_H */
  944.