home *** CD-ROM | disk | FTP | other *** search
/ PC Format (South-Africa) 2001 June / PCFJune.iso / Xenon / C++ / FreeCommandLineTools.exe / Include / Rw / tree.cc < prev    next >
Encoding:
C/C++ Source or Header  |  2000-01-31  |  20.0 KB  |  637 lines
  1. #ifndef __TREE_CC
  2. #define __TREE_CC
  3. #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
  4.  
  5. /***************************************************************************
  6.  *
  7.  * tree.cc - Non-nline tree definitions for the Standard Library
  8.  *
  9.  ***************************************************************************
  10.  *
  11.  * Copyright (c) 1994
  12.  * Hewlett-Packard Company
  13.  *
  14.  * Permission to use, copy, modify, distribute and sell this software
  15.  * and its documentation for any purpose is hereby granted without fee,
  16.  * provided that the above copyright notice appear in all copies and
  17.  * that both that copyright notice and this permission notice appear
  18.  * in supporting documentation.  Hewlett-Packard Company makes no
  19.  * representations about the suitability of this software for any
  20.  * purpose.  It is provided "as is" without express or implied warranty.
  21.  *
  22.  *
  23.  ***************************************************************************
  24.  *
  25.  * Copyright (c) 1994-1999 Rogue Wave Software, Inc.  All Rights Reserved.
  26.  *
  27.  * This computer software is owned by Rogue Wave Software, Inc. and is
  28.  * protected by U.S. copyright laws and other laws and by international
  29.  * treaties.  This computer software is furnished by Rogue Wave Software,
  30.  * Inc. pursuant to a written license agreement and may be used, copied,
  31.  * transmitted, and stored only in accordance with the terms of such
  32.  * license and with the inclusion of the above copyright notice.  This
  33.  * computer software or any other copies thereof may not be provided or
  34.  * otherwise made available to any other person.
  35.  *
  36.  * U.S. Government Restricted Rights.  This computer software is provided
  37.  * with Restricted Rights.  Use, duplication, or disclosure by the
  38.  * Government is subject to restrictions as set forth in subparagraph (c)
  39.  * (1) (ii) of The Rights in Technical Data and Computer Software clause
  40.  * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
  41.  * Commercial Computer Software รป Restricted Rights at 48 CFR 52.227-19,
  42.  * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
  43.  * Flatiron Parkway, Boulder, Colorado 80301 USA.
  44.  *
  45.  **************************************************************************/
  46.  
  47. #include <stdcomp.h>
  48.  
  49. #ifndef _RWSTD_NO_NAMESPACE
  50. namespace __rwstd {
  51. #endif
  52.  
  53.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  54.   void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__deallocate_buffers ()
  55.   {
  56.     while (__buffer_list.data())
  57.     {
  58.       __buffer_pointer tmp = __buffer_list;
  59.       __buffer_list        = (__buffer_pointer)(__buffer_list.data()->next_buffer);
  60.       __node_alloc_type(__buffer_list).deallocate(tmp->buffer,tmp->size);
  61.       __buffer_alloc_type(__buffer_list).deallocate(tmp,1);
  62.     }
  63.   }
  64.  
  65.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  66.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& 
  67.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
  68.   operator= (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x)
  69.   {
  70.     if (!(this == &x))
  71.     {
  72.       //
  73.       // Can't be done as in list because _Key may be a constant type.
  74.       //
  75.       erase(begin(), end());
  76.       __root() = __copy(x.__root(), __header);
  77.       if (__isNil(__root()))
  78.       {
  79.         __leftmost()  = __header; __rightmost() = __header;
  80.       }
  81.       else
  82.       {
  83.         __leftmost()  = __minimum(__root()); __rightmost() = __maximum(__root());
  84.       }
  85.       __node_count = x.__node_count;
  86.     }
  87.     return *this;
  88.   }
  89.  
  90.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  91.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
  92.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
  93.   __insert (__link_type x, __link_type y, const _Val& v)
  94.   {
  95.     __link_type z = __get_node(v);
  96.     ++__node_count;
  97.     if (y == __header || !__isNil(x) || __key_compare(_KeyOf()(v), __key(y)))
  98.     {
  99.       __left(y) = z;  // Also makes __leftmost() = z when y == __header.
  100.       if (y == __header)
  101.       {
  102.         __root() = z; __rightmost() = z;
  103.       }
  104.       else if (y == __leftmost())
  105.         __leftmost() = z;   // Maintain __leftmost() pointing to minimum node.
  106.     }
  107.     else
  108.     {
  109.       __right(y) = z;
  110.       if (y == __rightmost())
  111.         __rightmost() = z;  // Maintain __rightmost() pointing to maximum node.
  112.     }
  113.     __parent(z) = y;
  114.     x = z;  // Recolor and rebalance the tree.
  115.     while (x != __root() && __color(__parent(x)) == __rb_red) 
  116.     {
  117.       if (__parent(x) == __left(__parent(__parent(x))))
  118.       {
  119.         y = __right(__parent(__parent(x)));
  120.         if (!__isNil(y) && __color(y) == __rb_red)
  121.         {
  122.           __color(__parent(x))         = __rb_black;
  123.           __color(y)                 = __rb_black;
  124.           __color(__parent(__parent(x))) = __rb_red;
  125.           x                        = __parent(__parent(x));
  126.         }
  127.         else
  128.         {
  129.           if (x == __right(__parent(x)))
  130.           {
  131.             x = __parent(x); 
  132.             __rotate_left(x);
  133.           }
  134.           __color(__parent(x)) = __rb_black;
  135.           __color(__parent(__parent(x))) = __rb_red;
  136.           __rotate_right(__parent(__parent(x)));
  137.         }
  138.       }
  139.       else
  140.       {
  141.         y = __left(__parent(__parent(x)));
  142.         if (!__isNil(y) && __color(y) == __rb_red)
  143.         {
  144.           __color(__parent(x))         = __rb_black;
  145.           __color(y)                 = __rb_black;
  146.           __color(__parent(__parent(x))) = __rb_red;
  147.           x                        = __parent(__parent(x));
  148.         }
  149.         else
  150.         {
  151.           if (x == __left(__parent(x)))
  152.           {
  153.             x = __parent(x); 
  154.             __rotate_right(x);
  155.           }
  156.           __color(__parent(x))         = __rb_black;
  157.           __color(__parent(__parent(x))) = __rb_red;
  158.           __rotate_left(__parent(__parent(x)));
  159.         }
  160.       }
  161.     }
  162.     __color(__root()) = __rb_black;
  163.     return iterator(z);
  164.   }
  165.  
  166.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  167.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::pair_iterator_bool
  168.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (const _Val& v)
  169.   {
  170.     __link_type y = __header;
  171.     __link_type x = __root();
  172.     bool _RWSTD_COMP   = true;
  173.     while (!__isNil(x))
  174.     {
  175.       y    = x;
  176.       _RWSTD_COMP = __key_compare(_KeyOf()(v), __key(x));
  177.       x    = _RWSTD_COMP ? __left(x) : __right(x);
  178.     }
  179.     if (__insert_always)
  180.     {
  181.       pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  182.     }
  183.     iterator j = iterator(y);   
  184.     if (_RWSTD_COMP)
  185.     {
  186.       if (j == begin())  
  187.       {
  188.         pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  189.       }
  190.       else
  191.         --j;
  192.     }
  193.     if (__key_compare(__key(j.node), _KeyOf()(v)))
  194.     {
  195.       pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  196.     }
  197.     pair_iterator_bool tmp(j, false);
  198.     return tmp;
  199.   }
  200.  
  201.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  202.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
  203.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (iterator position,
  204.                                                         const _Val& v)
  205.   {
  206.     if (position == iterator(begin()))
  207.     {
  208.       if (size() > 0 && __key_compare(_KeyOf()(v), __key(position.node)))
  209.         return __insert(position.node, position.node, v);
  210.       //
  211.       // First argument just needs to be non-NIL.
  212.       //
  213.       else
  214.         return insert(v).first;
  215.     }
  216.     else if (position == iterator(end()))
  217.     {
  218.       if (__key_compare(__key(__rightmost()), _KeyOf()(v)))
  219.         return __insert(__nil(), __rightmost(), v);
  220.       else
  221.         return insert(v).first;
  222.     }
  223.     else
  224.     {
  225.       iterator before = --position;
  226.       if (__key_compare(__key(before.node), _KeyOf()(v))
  227.           && __key_compare(_KeyOf()(v), __key(position.node)))
  228.       {
  229.         if (__isNil(__right(before.node)))
  230.           return __insert(__nil(), before.node, v); 
  231.         else
  232.           return __insert(position.node, position.node, v);
  233.         //
  234.         // First argument just needs to be non-NIL.
  235.         //
  236.       }
  237.       else
  238.         return insert(v).first;
  239.     }
  240.   }
  241.  
  242. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  243.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  244.   template<class Iterator>
  245.   void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (Iterator first, 
  246.                                                              Iterator last)
  247.   {
  248.     while (first != last) insert(*first++);
  249.   }
  250. #else
  251.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  252.   void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (const_iterator first, 
  253.                                                              const_iterator last)
  254.   {
  255.     while (first != last) insert(*first++);
  256.   }
  257.  
  258.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  259.   void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (const _Val* first, 
  260.                                                              const _Val* last)
  261.   {
  262.     while (first != last) insert(*first++);
  263.   }
  264. #endif
  265.          
  266.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  267.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
  268.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (iterator position)
  269.   {
  270.     iterator tmp = position; // Retain 'next' position for return
  271.     if (tmp != end())
  272.       tmp++;
  273.  
  274.     __link_type z;
  275.     _RW_STD::__initialize(z, __link_type(position.node));
  276.     __link_type y = z;
  277.     __link_type x;
  278.     bool __deleted = false;
  279.     if (__isNil(__left(y)))
  280.     {
  281.       if (__isNil(__right(y)))
  282.       {
  283.         x = __parent(y);
  284.         __erase_leaf(y);
  285.         __deleted = true;
  286.       }
  287.       else
  288.         x = __right(y); 
  289.     }
  290.     else
  291.     {
  292.       if (__isNil(__right(y))) 
  293.         x = __left(y);
  294.       else
  295.       {
  296.         y = __right(y);
  297.         while (!__isNil(__left(y))) y = __left(y);
  298.         x = __right(y);
  299.       }
  300.     }
  301.     if (!__deleted && y != z)
  302.     {
  303.       //
  304.       // Relink y in place of z.
  305.       //
  306.       __parent(__left(z)) = y; 
  307.       __left(y) = __left(z);
  308.       if (y != __right(z))
  309.       {
  310.         if (!__isNil(x))
  311.           __parent(x)        = __parent(y);
  312.         __left(__parent(y))  = x;         // Y must be a left child.
  313.         __right(y)         = __right(z);
  314.         __parent(__right(z)) = y;
  315.       }
  316.       else if (!__isNil(x))
  317.         __parent(x) = y;  
  318.  
  319.       if (__root() == z)
  320.         __root() = y;
  321.       else if (__left(__parent(z)) == z)
  322.         __left(__parent(z)) = y;
  323.       else 
  324.         __right(__parent(z)) = y;
  325.  
  326.       __parent(y) = __parent(z);
  327.       if (__isNil(x))
  328.         x = y;       // Don't want to start balancing with nil
  329. #ifndef _RWSTD_NO_NAMESPACE
  330.       std::swap(__color(y), __color(z));
  331. #else
  332.       ::swap(__color(y), __color(z));
  333. #endif
  334.       y = z;        // y points to node to be actually deleted.
  335.     }
  336.     else if (!__deleted)
  337.     {
  338.       //
  339.       // y == z
  340.       //
  341.       __parent(x) = __parent(y);   
  342.       if (__root() == z)
  343.         __root() = x;
  344.       else 
  345.       {
  346.         if (__left(__parent(z)) == z)
  347.           __left(__parent(z)) = x;
  348.         else
  349.           __right(__parent(z)) = x;
  350.       }
  351.       if (__leftmost() == z) 
  352.       {
  353.         if (__isNil(__right(z)))  // __left(z) must be NIL also.
  354.           __leftmost() = __parent(z);
  355.         else
  356.           __leftmost() = __minimum(x);
  357.       }
  358.       if (__rightmost() == z)  
  359.       {
  360.         if (__isNil(__left(z))) // __right(z) must be NIL also.
  361.           __rightmost() = __parent(z);
  362.         else
  363.           __rightmost() = __maximum(x);
  364.       }
  365.     }
  366.     if (x != __header && __color(y) != __rb_red)
  367.     { 
  368.       while (x != __root() && __color(x) == __rb_black)
  369.       {
  370.         if (x == __left(__parent(x)))
  371.         {
  372.           __link_type w = __right(__parent(x));
  373.           if (__isNil(w))
  374.           {
  375.             __color(x) = __rb_red;
  376.             x = __parent(x);
  377.           }
  378.           else
  379.           {
  380.             if (__color(w) == __rb_red)
  381.             {
  382.               __color(w)         = __rb_black;
  383.               __color(__parent(x)) = __rb_red;
  384.               __rotate_left(__parent(x));
  385.               w = __right(__parent(x));
  386.             }
  387.             if (__isNil(w))
  388.             {
  389.               __color(x) = __rb_red;
  390.               x = __parent(x);
  391.             }
  392.             else if ((__isNil(__left(w)) || __color(__left(w)) == __rb_black) && 
  393.                 (__isNil(__right(w)) || __color(__right(w)) == __rb_black))
  394.             {
  395.               __color(w) = __rb_red;
  396.               x = __parent(x);
  397.             }
  398.             else
  399.             {
  400.               if (__isNil(__right(w)) || __color(__right(w)) == __rb_black)
  401.               {
  402.                 if (!__isNil(__left(w)))
  403.                   __color(__left(w)) = __rb_black;
  404.                 __color(w)       = __rb_red;
  405.                 __rotate_right(w);
  406.                 w = __right(__parent(x));
  407.               }
  408.               if (!__isNil(w))
  409.               {
  410.                 __color(w) = __color(__parent(x));
  411.                 __color(__parent(x)) = __rb_black;
  412.                 if (!__isNil(__right(w)))
  413.                   __color(__right(w))  = __rb_black;
  414.                 __rotate_left(__parent(x));
  415.               }          
  416.               break;
  417.             }
  418.           }
  419.         }
  420.         else
  421.         {
  422.           //
  423.           // Same as then clause with "right" and "left" exchanged.
  424.           //
  425.           __link_type w = __left(__parent(x));
  426.           if (__isNil(w))
  427.           {
  428.             __color(x) = __rb_red;
  429.             x = __parent(x);
  430.           }
  431.           else
  432.           {
  433.             if (__color(w) == __rb_red)
  434.             {
  435.               __color(w)         = __rb_black;
  436.               __color(__parent(x)) = __rb_red;
  437.               __rotate_right(__parent(x));
  438.               w = __left(__parent(x));
  439.             }
  440.             if (__isNil(w))
  441.             {
  442.               __color(x) = __rb_red;
  443.               x = __parent(x);
  444.             }
  445.             else if ((__isNil(__right(w)) || __color(__right(w)) == __rb_black) &&
  446.               (__isNil(__left(w)) || __color(__left(w)) == __rb_black))
  447.             {
  448.               __color(w) = __rb_red; x = __parent(x);
  449.             }
  450.             else
  451.             {
  452.               if (__isNil(__left(w)) || __color(__left(w)) == __rb_black)
  453.               {
  454.                 if (!__isNil(__right(w)))
  455.                   __color(__right(w)) = __rb_black;
  456.                 __color(w)        = __rb_red;
  457.                 __rotate_left(w);
  458.                 w = __left(__parent(x));
  459.               }
  460.               if (!__isNil(w))
  461.               {
  462.                 __color(w) = __color(__parent(x));
  463.                 __color(__parent(x)) = __rb_black;
  464.                 if (!__isNil(__left(w)))
  465.                   __color(__left(w))   = __rb_black;
  466.                 __rotate_right(__parent(x));
  467.               }
  468.               break;
  469.             }
  470.           }
  471.         }
  472.       }
  473.       __color(x) = __rb_black;
  474.     }
  475.     __put_node(y);
  476.     --__node_count;
  477.     return tmp;
  478.   }
  479.  
  480.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  481.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type 
  482.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (const _Key& x)
  483.   {
  484.     pair_iterator_iterator p = equal_range(x);
  485.     size_type n;
  486.     _RW_STD::__initialize(n, size_type(0));
  487.     _RW_STD::distance(p.first, p.second, n);
  488.     erase(p.first, p.second);
  489.     return n;
  490.   }
  491.  
  492.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  493.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__link_type 
  494.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__copy (__link_type x, __link_type p)
  495.   {
  496.     //
  497.     // Structural copy.
  498.     // 
  499.     __link_type r = x;
  500.     while (!__isNil(x))
  501.     {
  502.       __link_type y = __get_node(__value(x));
  503.       if (r == x) r = y;  // Save for return value.
  504.       __left(p)   = y;
  505.       __parent(y) = p;
  506.       __color(y)  = __color(x);
  507.       __right(y)  = __copy(__right(x), y);
  508.       p         = y;
  509.       x         = __left(x);
  510.     }
  511.     __left(p) = __nil();
  512.     return r;
  513.   }
  514.  
  515.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  516.   void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__erase (__link_type x)
  517.   {
  518.     //
  519.     // Erase without rebalancing.
  520.     //
  521.     while (!__isNil(x))
  522.     {
  523.       __erase(__right(x));
  524.       __link_type y = __left(x);
  525.       __put_node(x);
  526.       x = y;
  527.     }
  528.   }
  529.  
  530.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  531.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
  532.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (iterator first, 
  533.                                                        iterator locallast)
  534.   {
  535.     iterator tmp = end();
  536.     if (first == begin() && locallast == end() && __node_count != 0)
  537.     {
  538.       __erase(__root());
  539.       __leftmost()  = __header;
  540.       __root()      = __nil();
  541.       __rightmost() = __header;
  542.       __node_count  = 0;
  543.       tmp = end();
  544.     } else
  545.     {
  546.       while (first != locallast) 
  547.         tmp =  erase(first++);
  548.     }
  549.     return tmp;
  550.   }
  551.  
  552.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  553.   void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (const _Key* first, 
  554.                                                             const _Key* last)
  555.   {
  556.     while (first != last) erase(*first++);
  557.   }
  558.  
  559.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  560.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
  561.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::find (const _Key& k) const
  562.   {
  563.     __link_type y = __header;  // Last node that is not less than k.
  564.     __link_type x = __root();  // Current node.
  565.  
  566.     while (!__isNil(x))
  567.     {
  568.       if (!__key_compare(__key(x), k))
  569.         y = x, x = __left(x);
  570.       else
  571.         x = __right(x);
  572.     }
  573.     iterator j = iterator(y);
  574.     return (j == end() || __key_compare(k, __key(j.node))) ? end() : j;
  575.   }
  576.  
  577.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  578.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type 
  579.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::count (const _Key& k) const
  580.   {
  581.     _RW_STD::pair<iterator, iterator> p = equal_range(k);
  582.     size_type n;
  583.     _RW_STD::__initialize(n, size_type(0));
  584.     _RW_STD::distance(p.first, p.second, n);
  585.     return n;
  586.   }
  587.  
  588.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  589.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
  590.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::lower_bound (const _Key& k) const
  591.   {
  592.     __link_type y = __header;  // Last node that is not less than k.
  593.     __link_type x = __root();  // Current node.
  594.  
  595.     while (!__isNil(x))
  596.     {
  597.       if (!__key_compare(__key(x), k))
  598.         y = x, x = __left(x);
  599.       else
  600.         x = __right(x);
  601.     }
  602.  
  603.     return iterator(y);
  604.   }
  605.  
  606.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  607.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator 
  608.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::upper_bound (const _Key& k) const
  609.   {
  610.     __link_type y = __header;  // Last node that is greater than k.
  611.     __link_type x = __root();  // Current node.
  612.  
  613.     while (!__isNil(x))
  614.     {
  615.       if (__key_compare(k, __key(x)))
  616.         y = x, x = __left(x);
  617.       else
  618.         x = __right(x);
  619.     }
  620.  
  621.     return iterator(y);
  622.   }
  623.  
  624.   template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
  625.   _TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::pair_iterator_iterator 
  626.   __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::equal_range (const _Key& k) const
  627.   {
  628.     pair_iterator_iterator tmp(lower_bound(k), upper_bound(k));
  629.     return tmp;
  630.   }
  631.  
  632. #ifndef _RWSTD_NO_NAMESPACE
  633. }
  634. #endif
  635. #pragma option pop
  636. #endif /* __TREE_CC */
  637.