home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / include / xtree < prev    next >
Encoding:
Text File  |  1998-06-16  |  30.0 KB  |  669 lines
  1. // tree internal header
  2.  
  3. #if     _MSC_VER > 1000
  4. #pragma once
  5. #endif
  6.  
  7. #ifndef _XTREE_
  8. #define _XTREE_
  9. #include <cstddef>
  10. #include <iterator>
  11. #include <memory>
  12. #include <xutility>
  13.  
  14. #ifdef  _MSC_VER
  15. #pragma pack(push,8)
  16. #endif  /* _MSC_VER */
  17. _STD_BEGIN
  18.                 // TEMPLATE CLASS _Tree
  19. template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
  20.         class _Tree {
  21. protected:
  22.         enum _Redbl {_Red, _Black};
  23.         struct _Node;
  24.         friend struct _Node;
  25.         typedef _POINTER_X(_Node, _A) _Nodeptr;
  26.         struct _Node {
  27.                 _Nodeptr _Left, _Parent, _Right;
  28.                 _Ty _Value;
  29.                 _Redbl _Color;
  30.                 };
  31.         typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;
  32.         typedef _REFERENCE_X(const _K, _A) _Keyref;
  33.         typedef _REFERENCE_X(_Redbl, _A) _Rbref;
  34.         typedef _REFERENCE_X(_Ty, _A) _Vref;
  35.         static _Rbref _Color(_Nodeptr _P)
  36.                 {return ((_Rbref)(*_P)._Color); }
  37.         static _Keyref _Key(_Nodeptr _P)
  38.                 {return (_Kfn()(_Value(_P))); }
  39.         static _Nodepref _Left(_Nodeptr _P)
  40.                 {return ((_Nodepref)(*_P)._Left); }
  41.         static _Nodepref _Parent(_Nodeptr _P)
  42.                 {return ((_Nodepref)(*_P)._Parent); }
  43.         static _Nodepref _Right(_Nodeptr _P)
  44.                 {return ((_Nodepref)(*_P)._Right); }
  45.         static _Vref _Value(_Nodeptr _P)
  46.                 {return ((_Vref)(*_P)._Value); }
  47. public:
  48.         typedef _Tree<_K, _Ty, _Kfn, _Pr, _A> _Myt;
  49.         typedef _K key_type;
  50.         typedef _Ty value_type;
  51.         typedef _A::size_type size_type;
  52.         typedef _A::difference_type difference_type;
  53.         typedef _POINTER_X(_Ty, _A) _Tptr;
  54.         typedef _POINTER_X(const _Ty, _A) _Ctptr;
  55.         typedef _REFERENCE_X(_Ty, _A) reference;
  56.         typedef _REFERENCE_X(const _Ty, _A) const_reference;
  57.                 // CLASS const_iterator
  58.         class iterator;
  59.         class const_iterator;
  60.         friend class const_iterator;
  61.         class const_iterator : public _Bidit<_Ty, difference_type> {
  62.         public:
  63.                 const_iterator()
  64.                         {}
  65.                 const_iterator(_Nodeptr _P)
  66.                         : _Ptr(_P) {}
  67.                 const_iterator(const iterator& _X)
  68.                         : _Ptr(_X._Ptr) {}
  69.                 const_reference operator*() const
  70.                         {return (_Value(_Ptr)); }
  71.                 _Ctptr operator->() const
  72.                         {return (&**this); }
  73.                 const_iterator& operator++()
  74.                         {_Inc();
  75.                         return (*this); }
  76.                 const_iterator operator++(int)
  77.                         {const_iterator _Tmp = *this;
  78.                         ++*this;
  79.                         return (_Tmp); }
  80.                 const_iterator& operator--()
  81.                         {_Dec();
  82.                         return (*this); }
  83.                 const_iterator operator--(int)
  84.                         {const_iterator _Tmp = *this;
  85.                         --*this;
  86.                         return (_Tmp); }
  87.                 bool operator==(const const_iterator& _X) const
  88.                         {return (_Ptr == _X._Ptr); }
  89.                 bool operator!=(const const_iterator& _X) const
  90.                         {return (!(*this == _X)); }
  91.                 void _Dec()
  92.                         {_Lockit _Lk;
  93.                         if (_Color(_Ptr) == _Red
  94.                                 && _Parent(_Parent(_Ptr)) == _Ptr)
  95.                                 _Ptr = _Right(_Ptr);
  96.                         else if (_Left(_Ptr) != _Nil)
  97.                                 _Ptr = _Max(_Left(_Ptr));
  98.                         else
  99.                                 {_Nodeptr _P;
  100.                                 while (_Ptr == _Left(_P = _Parent(_Ptr)))
  101.                                         _Ptr = _P;
  102.                                 _Ptr = _P; }}
  103.                 void _Inc()
  104.                         {_Lockit _Lk;
  105.                         if (_Right(_Ptr) != _Nil)
  106.                                 _Ptr = _Min(_Right(_Ptr));
  107.                         else
  108.                                 {_Nodeptr _P;
  109.                                 while (_Ptr == _Right(_P = _Parent(_Ptr)))
  110.                                         _Ptr = _P;
  111.                                 if (_Right(_Ptr) != _P)
  112.                                         _Ptr = _P; }}
  113.                 _Nodeptr _Mynode() const
  114.                         {return (_Ptr); }
  115.         protected:
  116.                 _Nodeptr _Ptr;
  117.                 };
  118.                 // CLASS iterator
  119.         friend class iterator;
  120.         class iterator : public const_iterator {
  121.         public:
  122.                 iterator()
  123.                         {}
  124.                 iterator(_Nodeptr _P)
  125.                         : const_iterator(_P) {}
  126.                 reference operator*() const
  127.                         {return (_Value(_Ptr)); }
  128.                 _Tptr operator->() const
  129.                         {return (&**this); }
  130.                 iterator& operator++()
  131.                         {_Inc();
  132.                         return (*this); }
  133.                 iterator operator++(int)
  134.                         {iterator _Tmp = *this;
  135.                         ++*this;
  136.                         return (_Tmp); }
  137.                 iterator& operator--()
  138.                         {_Dec();
  139.                         return (*this); }
  140.                 iterator operator--(int)
  141.                         {iterator _Tmp = *this;
  142.                         --*this;
  143.                         return (_Tmp); }
  144.                 bool operator==(const iterator& _X) const
  145.                         {return (_Ptr == _X._Ptr); }
  146.                 bool operator!=(const iterator& _X) const
  147.                         {return (!(*this == _X)); }
  148.                 };
  149.         typedef reverse_bidirectional_iterator<iterator,
  150.                 value_type, reference, _Tptr, difference_type>
  151.                         reverse_iterator;
  152.         typedef reverse_bidirectional_iterator<const_iterator,
  153.                 value_type, const_reference, _Ctptr, difference_type>
  154.                         const_reverse_iterator;
  155.         typedef pair<iterator, bool> _Pairib;
  156.         typedef pair<iterator, iterator> _Pairii;
  157.         typedef pair<const_iterator, const_iterator> _Paircc;
  158.         explicit _Tree(const _Pr& _Parg, bool _Marg = true,
  159.                 const _A& _Al = _A())
  160.                 : allocator(_Al),
  161.                 key_compare(_Parg), _Multi(_Marg)
  162.                 {_Init(); }
  163.         _Tree(const _Ty *_F, const _Ty *_L,
  164.                 const _Pr& _Parg, bool _Marg = true,
  165.                 const _A& _Al = _A())
  166.                 : allocator(_Al),
  167.                 key_compare(_Parg), _Multi(_Marg)
  168.                 {_Init();
  169.                 insert(_F, _L); }
  170.         _Tree(const _Myt& _X)
  171.                 : allocator(_X.allocator),
  172.                 key_compare(_X.key_compare), _Multi(_X._Multi)
  173.                 {_Init();
  174.                 _Copy(_X); }
  175.         ~_Tree()
  176.                 {erase(begin(), end());
  177.                 _Freenode(_Head);
  178.                 _Head = 0, _Size = 0;
  179.                         {_Lockit _Lk;
  180.                         if (--_Nilrefs == 0)
  181.                                 {_Freenode(_Nil);
  182.                                 _Nil = 0; }}}
  183.         _Myt& operator=(const _Myt& _X)
  184.                 {if (this != &_X)
  185.                         {erase(begin(), end());
  186.                         key_compare = _X.key_compare;
  187.                         _Copy(_X); }
  188.                 return (*this); }
  189.         iterator begin()
  190.                 {return (iterator(_Lmost())); }
  191.         const_iterator begin() const
  192.                 {return (const_iterator(_Lmost())); }
  193.         iterator end()
  194.                 {return (iterator(_Head)); }
  195.         const_iterator end() const
  196.                 {return (const_iterator(_Head)); }
  197.         reverse_iterator rbegin()
  198.                 {return (reverse_iterator(end())); }
  199.         const_reverse_iterator rbegin() const
  200.                 {return (const_reverse_iterator(end())); }
  201.         reverse_iterator rend()
  202.                 {return (reverse_iterator(begin())); }
  203.         const_reverse_iterator rend() const
  204.                 {return (const_reverse_iterator(begin())); }
  205.         size_type size() const
  206.                 {return (_Size); }
  207.         size_type max_size() const
  208.                 {return (allocator.max_size()); }
  209.         bool empty() const
  210.                 {return (size() == 0); }
  211.         _A get_allocator() const
  212.                 {return (allocator); }
  213.         _Pr key_comp() const
  214.                 {return (key_compare); }
  215.         _Pairib insert(const value_type& _V)
  216.                 {_Nodeptr _X = _Root();
  217.                 _Nodeptr _Y = _Head;
  218.                 bool _Ans = true;
  219.                 { _Lockit Lk;
  220.                         while (_X != _Nil)
  221.                                 {_Y = _X;
  222.                                 _Ans = key_compare(_Kfn()(_V), _Key(_X));
  223.                                 _X = _Ans ? _Left(_X) : _Right(_X); }
  224.                 }
  225.                 if (_Multi)
  226.                         return (_Pairib(_Insert(_X, _Y, _V), true));
  227.                 iterator _P = iterator(_Y);
  228.                 if (!_Ans)
  229.                         ;
  230.                 else if (_P == begin())
  231.                         return (_Pairib(_Insert(_X, _Y, _V), true));
  232.                 else
  233.                         --_P;
  234.                 if (key_compare(_Key(_P._Mynode()), _Kfn()(_V)))
  235.                         return (_Pairib(_Insert(_X, _Y, _V), true));
  236.                 return (_Pairib(_P, false)); }
  237.         iterator insert(iterator _P, const value_type& _V)
  238.                 {if (size() == 0)
  239.                         ;
  240.                 else if (_P == begin())
  241.                         {if (key_compare(_Kfn()(_V), _Key(_P._Mynode())))
  242.                                 return (_Insert(_Head, _P._Mynode(), _V)); }
  243.                 else if (_P == end())
  244.                         {_Lockit Lk;
  245.                         if (key_compare(_Key(_Rmost()), _Kfn()(_V)))
  246.                                 return (_Insert(_Nil, _Rmost(), _V)); }
  247.                 else
  248.                         {iterator _Pb = _P;
  249.                         if (key_compare(_Key((--_Pb)._Mynode()), _Kfn()(_V))
  250.                                 && key_compare(_Kfn()(_V), _Key(_P._Mynode())))
  251.                                 {_Lockit _Lk;
  252.                                 if (_Right(_Pb._Mynode()) == _Nil)
  253.                                         return (_Insert(_Nil, _Pb._Mynode(), _V));
  254.                                 else
  255.                                         return (_Insert(_Head, _P._Mynode(), _V)); }}
  256.                 return (insert(_V).first); }
  257.         void insert(iterator _F, iterator _L)
  258.                 {for (; _F != _L; ++_F)
  259.                         insert(*_F); }
  260.         void insert(const value_type *_F, const value_type *_L)
  261.                 {for (; _F != _L; ++_F)
  262.                         insert(*_F); }
  263.         iterator erase(iterator _P)
  264.                 {_Nodeptr _X;
  265.                 _Nodeptr _Y = (_P++)._Mynode();
  266.                 _Nodeptr _Z = _Y;
  267.                 _Lockit _Lk;
  268.                 if (_Left(_Y) == _Nil)
  269.                         _X = _Right(_Y);
  270.                 else if (_Right(_Y) == _Nil)
  271.                         _X = _Left(_Y);
  272.                 else
  273.                         _Y = _Min(_Right(_Y)), _X = _Right(_Y);
  274.                 if (_Y != _Z)
  275.                         {_Parent(_Left(_Z)) = _Y;
  276.                         _Left(_Y) = _Left(_Z);
  277.                         if (_Y == _Right(_Z))
  278.                                 _Parent(_X) = _Y;
  279.                         else
  280.                                 {_Parent(_X) = _Parent(_Y);
  281.                                 _Left(_Parent(_Y)) = _X;
  282.                                 _Right(_Y) = _Right(_Z);
  283.                                 _Parent(_Right(_Z)) = _Y; }
  284.                         if (_Root() == _Z)
  285.                                 _Root() = _Y;
  286.                         else if (_Left(_Parent(_Z)) == _Z)
  287.                                 _Left(_Parent(_Z)) = _Y;
  288.                         else
  289.                                 _Right(_Parent(_Z)) = _Y;
  290.                         _Parent(_Y) = _Parent(_Z);
  291.                         std::swap(_Color(_Y), _Color(_Z));
  292.                         _Y = _Z; }
  293.                 else
  294.                         {_Parent(_X) = _Parent(_Y);
  295.                         if (_Root() == _Z)
  296.                                 _Root() = _X;
  297.                         else if (_Left(_Parent(_Z)) == _Z)
  298.                                 _Left(_Parent(_Z)) = _X;
  299.                         else
  300.                                 _Right(_Parent(_Z)) = _X;
  301.                         if (_Lmost() != _Z)
  302.                                 ;
  303.                         else if (_Right(_Z) == _Nil)
  304.                                 _Lmost() = _Parent(_Z);
  305.                         else
  306.                                 _Lmost() = _Min(_X);
  307.                         if (_Rmost() != _Z)
  308.                                 ;
  309.                         else if (_Left(_Z) == _Nil)
  310.                                 _Rmost() = _Parent(_Z);
  311.                         else
  312.                                 _Rmost() = _Max(_X); }
  313.                 if (_Color(_Y) == _Black)
  314.                         {while (_X != _Root() && _Color(_X) == _Black)
  315.                                 if (_X == _Left(_Parent(_X)))
  316.                                         {_Nodeptr _W = _Right(_Parent(_X));
  317.                                         if (_Color(_W) == _Red)
  318.                                                 {_Color(_W) = _Black;
  319.                                                 _Color(_Parent(_X)) = _Red;
  320.                                                 _Lrotate(_Parent(_X));
  321.                                                 _W = _Right(_Parent(_X)); }
  322.                                         if (_Color(_Left(_W)) == _Black
  323.                                                 && _Color(_Right(_W)) == _Black)
  324.                                                 {_Color(_W) = _Red;
  325.                                                 _X = _Parent(_X); }
  326.                                         else
  327.                                                 {if (_Color(_Right(_W)) == _Black)
  328.                                                         {_Color(_Left(_W)) = _Black;
  329.                                                         _Color(_W) = _Red;
  330.                                                         _Rrotate(_W);
  331.                                                         _W = _Right(_Parent(_X)); }
  332.                                                 _Color(_W) = _Color(_Parent(_X));
  333.                                                 _Color(_Parent(_X)) = _Black;
  334.                                                 _Color(_Right(_W)) = _Black;
  335.                                                 _Lrotate(_Parent(_X));
  336.                                                 break; }}
  337.                                 else
  338.                                         {_Nodeptr _W = _Left(_Parent(_X));
  339.                                         if (_Color(_W) == _Red)
  340.                                                 {_Color(_W) = _Black;
  341.                                                 _Color(_Parent(_X)) = _Red;
  342.                                                 _Rrotate(_Parent(_X));
  343.                                                 _W = _Left(_Parent(_X)); }
  344.                                         if (_Color(_Right(_W)) == _Black
  345.                                                 && _Color(_Left(_W)) == _Black)
  346.                                                 {_Color(_W) = _Red;
  347.                                                 _X = _Parent(_X); }
  348.                                         else
  349.                                                 {if (_Color(_Left(_W)) == _Black)
  350.                                                         {_Color(_Right(_W)) = _Black;
  351.                                                         _Color(_W) = _Red;
  352.                                                         _Lrotate(_W);
  353.                                                         _W = _Left(_Parent(_X)); }
  354.                                                 _Color(_W) = _Color(_Parent(_X));
  355.                                                 _Color(_Parent(_X)) = _Black;
  356.                                                 _Color(_Left(_W)) = _Black;
  357.                                                 _Rrotate(_Parent(_X));
  358.                                                 break; }}
  359.                         _Color(_X) = _Black; }
  360.                 _Destval(&_Value(_Y));
  361.                 _Freenode(_Y);
  362.                 --_Size;
  363.                 return (_P); }
  364.         iterator erase(iterator _F, iterator _L)
  365.                 {if (size() == 0 || _F != begin() || _L != end())
  366.                         {while (_F != _L)
  367.                                 erase(_F++);
  368.                         return (_F); }
  369.                 else
  370.                         {_Lockit Lk;
  371.                         _Erase(_Root());
  372.                         _Root() = _Nil, _Size = 0;
  373.                         _Lmost() = _Head, _Rmost() = _Head;
  374.                         return (begin()); }}
  375.         size_type erase(const _K& _X)
  376.                 {_Pairii _P = equal_range(_X);
  377.                 size_type _N = 0;
  378.                 _Distance(_P.first, _P.second, _N);
  379.                 erase(_P.first, _P.second);
  380.                 return (_N); }
  381.         void erase(const _K *_F, const _K *_L)
  382.                 {for (; _F != _L; ++_F)
  383.                         erase(*_F); }
  384.         void clear()
  385.                 {erase(begin(), end()); }
  386.         iterator find(const _K& _Kv)
  387.                 {iterator _P = lower_bound(_Kv);
  388.                 return (_P == end()
  389.                         || key_compare(_Kv, _Key(_P._Mynode()))
  390.                                 ? end() : _P); }
  391.         const_iterator find(const _K& _Kv) const
  392.                 {const_iterator _P = lower_bound(_Kv);
  393.                 return (_P == end()
  394.                         || key_compare(_Kv, _Key(_P._Mynode()))
  395.                                 ? end() : _P); }
  396.         size_type count(const _K& _Kv) const
  397.                 {_Paircc _Ans = equal_range(_Kv);
  398.                 size_type _N = 0;
  399.                 _Distance(_Ans.first, _Ans.second, _N);
  400.                 return (_N); }
  401.         iterator lower_bound(const _K& _Kv)
  402.                 {return (iterator(_Lbound(_Kv))); }
  403.         const_iterator lower_bound(const _K& _Kv) const
  404.                 {return (const_iterator(_Lbound(_Kv))); }
  405.         iterator upper_bound(const _K& _Kv)
  406.                 {return (iterator(_Ubound(_Kv))); }
  407.         const_iterator upper_bound(const _K& _Kv) const
  408.                 {return (iterator(_Ubound(_Kv))); }
  409.         _Pairii equal_range(const _K& _Kv)
  410.                 {return (_Pairii(lower_bound(_Kv), upper_bound(_Kv))); }
  411.         _Paircc equal_range(const _K& _Kv) const
  412.                 {return (_Paircc(lower_bound(_Kv), upper_bound(_Kv))); }
  413.         void swap(_Myt& _X)
  414.                 {std::swap(key_compare, _X.key_compare);
  415.                 if (allocator == _X.allocator)
  416.                         {std::swap(_Head, _X._Head);
  417.                         std::swap(_Multi, _X._Multi);
  418.                         std::swap(_Size, _X._Size); }
  419.                 else
  420.                         {_Myt _Ts = *this; *this = _X, _X = _Ts; }}
  421.         friend void swap(_Myt& _X, _Myt& _Y)
  422.                 {_X.swap(_Y); }
  423. protected:
  424.         static _Nodeptr _Nil;
  425.         static size_t _Nilrefs;
  426.         void _Copy(const _Myt& _X)
  427.                 {_Lockit _Lk;
  428.                 _Root() = _Copy(_X._Root(), _Head);
  429.                 _Size = _X.size();
  430.                 if (_Root() != _Nil)
  431.                         {_Lmost() = _Min(_Root());
  432.                         _Rmost() = _Max(_Root()); }
  433.                 else
  434.                         _Lmost() = _Head, _Rmost() = _Head; }
  435.         _Nodeptr _Copy(_Nodeptr _X, _Nodeptr _P)
  436.                 {_Lockit _Lk;
  437.                 _Nodeptr _R = _X;
  438.                 for (; _X != _Nil; _X = _Left(_X))
  439.                         {_Nodeptr _Y = _Buynode(_P, _Color(_X));
  440.                         if (_R == _X)
  441.                                 _R = _Y;
  442.                         _Right(_Y) = _Copy(_Right(_X), _Y);
  443.                         _Consval(&_Value(_Y), _Value(_X));
  444.                         _Left(_P) = _Y;
  445.                         _P = _Y; }
  446.                 _Left(_P) = _Nil;
  447.                 return (_R); }
  448.         void _Erase(_Nodeptr _X)
  449.                 {_Lockit _Lk;
  450.                 for (_Nodeptr _Y = _X; _Y != _Nil; _X = _Y)
  451.                         {_Erase(_Right(_Y));
  452.                         _Y = _Left(_Y);
  453.                         _Destval(&_Value(_X));
  454.                         _Freenode(_X); }}
  455.         void _Init()
  456.                 {_Lockit _Lk;
  457.                 if (_Nil == 0)
  458.                         {_Nil = _Buynode(0, _Black);
  459.                         _Left(_Nil) = 0, _Right(_Nil) = 0; }
  460.                 ++_Nilrefs;
  461.                 _Head = _Buynode(_Nil, _Red), _Size = 0;
  462.                 _Lmost() = _Head, _Rmost() = _Head; }
  463.         iterator _Insert(_Nodeptr _X, _Nodeptr _Y, const _Ty& _V)
  464.                 {_Lockit _Lk;
  465.                 _Nodeptr _Z = _Buynode(_Y, _Red);
  466.                 _Left(_Z) = _Nil, _Right(_Z) = _Nil;
  467.                 _Consval(&_Value(_Z), _V);
  468.                 ++_Size;
  469.                 if (_Y == _Head || _X != _Nil
  470.                         || key_compare(_Kfn()(_V), _Key(_Y)))
  471.                         {_Left(_Y) = _Z;
  472.                         if (_Y == _Head)
  473.                                 {_Root() = _Z;
  474.                                 _Rmost() = _Z; }
  475.                         else if (_Y == _Lmost())
  476.                                 _Lmost() = _Z; }
  477.                 else
  478.                         {_Right(_Y) = _Z;
  479.                         if (_Y == _Rmost())
  480.                                 _Rmost() = _Z; }
  481.                 for (_X = _Z; _X != _Root()
  482.                         && _Color(_Parent(_X)) == _Red; )
  483.                         if (_Parent(_X) == _Left(_Parent(_Parent(_X))))
  484.                                 {_Y = _Right(_Parent(_Parent(_X)));
  485.                                 if (_Color(_Y) == _Red)
  486.                                         {_Color(_Parent(_X)) = _Black;
  487.                                         _Color(_Y) = _Black;
  488.                                         _Color(_Parent(_Parent(_X))) = _Red;
  489.                                         _X = _Parent(_Parent(_X)); }
  490.                                 else
  491.                                         {if (_X == _Right(_Parent(_X)))
  492.                                                 {_X = _Parent(_X);
  493.                                                 _Lrotate(_X); }
  494.                                         _Color(_Parent(_X)) = _Black;
  495.                                         _Color(_Parent(_Parent(_X))) = _Red;
  496.                                         _Rrotate(_Parent(_Parent(_X))); }}
  497.                         else
  498.                                 {_Y = _Left(_Parent(_Parent(_X)));
  499.                                 if (_Color(_Y) == _Red)
  500.                                         {_Color(_Parent(_X)) = _Black;
  501.                                         _Color(_Y) = _Black;
  502.                                         _Color(_Parent(_Parent(_X))) = _Red;
  503.                                         _X = _Parent(_Parent(_X)); }
  504.                                 else
  505.                                         {if (_X == _Left(_Parent(_X)))
  506.                                                 {_X = _Parent(_X);
  507.                                                 _Rrotate(_X); }
  508.                                         _Color(_Parent(_X)) = _Black;
  509.                                         _Color(_Parent(_Parent(_X))) = _Red;
  510.                                         _Lrotate(_Parent(_Parent(_X))); }}
  511.                 _Color(_Root()) = _Black;
  512.                 return (iterator(_Z)); }
  513.         _Nodeptr _Lbound(const _K& _Kv) const
  514.                 {_Lockit _Lk;
  515.                 _Nodeptr _X = _Root();
  516.                 _Nodeptr _Y = _Head;
  517.                 while (_X != _Nil)
  518.                         if (key_compare(_Key(_X), _Kv))
  519.                                 _X = _Right(_X);
  520.                         else
  521.                                 _Y = _X, _X = _Left(_X);
  522.                 return (_Y); }
  523.         _Nodeptr& _Lmost()
  524.                 {return (_Left(_Head)); }
  525.         _Nodeptr& _Lmost() const
  526.                 {return (_Left(_Head)); }
  527.         void _Lrotate(_Nodeptr _X)
  528.                 {_Lockit _Lk;
  529.                 _Nodeptr _Y = _Right(_X);
  530.                 _Right(_X) = _Left(_Y);
  531.                 if (_Left(_Y) != _Nil)
  532.                         _Parent(_Left(_Y)) = _X;
  533.                 _Parent(_Y) = _Parent(_X);
  534.                 if (_X == _Root())
  535.                         _Root() = _Y;
  536.                 else if (_X == _Left(_Parent(_X)))
  537.                         _Left(_Parent(_X)) = _Y;
  538.                 else
  539.                         _Right(_Parent(_X)) = _Y;
  540.                 _Left(_Y) = _X;
  541.                 _Parent(_X) = _Y; }
  542.         static _Nodeptr _Max(_Nodeptr _P)
  543.                 {_Lockit _Lk;
  544.                 while (_Right(_P) != _Nil)
  545.                         _P = _Right(_P);
  546.                 return (_P); }
  547.         static _Nodeptr _Min(_Nodeptr _P)
  548.                 {_Lockit _Lk;
  549.                 while (_Left(_P) != _Nil)
  550.                         _P = _Left(_P);
  551.                 return (_P); }
  552.         _Nodeptr& _Rmost()
  553.                 {return (_Right(_Head)); }
  554.         _Nodeptr& _Rmost() const
  555.                 {return (_Right(_Head)); }
  556.         _Nodeptr& _Root()
  557.                 {return (_Parent(_Head)); }
  558.         _Nodeptr& _Root() const
  559.                 {return (_Parent(_Head)); }
  560.         void _Rrotate(_Nodeptr _X)
  561.                 {_Lockit _Lk;
  562.                 _Nodeptr _Y = _Left(_X);
  563.                 _Left(_X) = _Right(_Y);
  564.                 if (_Right(_Y) != _Nil)
  565.                         _Parent(_Right(_Y)) = _X;
  566.                 _Parent(_Y) = _Parent(_X);
  567.                 if (_X == _Root())
  568.                         _Root() = _Y;
  569.                 else if (_X == _Right(_Parent(_X)))
  570.                         _Right(_Parent(_X)) = _Y;
  571.                 else
  572.                         _Left(_Parent(_X)) = _Y;
  573.                 _Right(_Y) = _X;
  574.                 _Parent(_X) = _Y; }
  575.         _Nodeptr _Ubound(const _K& _Kv) const
  576.                 {_Lockit _Lk;
  577.                 _Nodeptr _X = _Root();
  578.                 _Nodeptr _Y = _Head;
  579.                 while (_X != _Nil)
  580.                         if (key_compare(_Kv, _Key(_X)))
  581.                                 _Y = _X, _X = _Left(_X);
  582.                         else
  583.                                 _X = _Right(_X);
  584.                 return (_Y); }
  585.         _Nodeptr _Buynode(_Nodeptr _Parg, _Redbl _Carg)
  586.                 {_Nodeptr _S = (_Nodeptr)allocator._Charalloc(
  587.                         1 * sizeof (_Node));
  588.                 _Parent(_S) = _Parg;
  589.                 _Color(_S) = _Carg;
  590.                 return (_S); }
  591.         void _Consval(_Tptr _P, const _Ty& _V)
  592.                 {_Construct(&*_P, _V); }
  593.         void _Destval(_Tptr _P)
  594.                 {_Destroy(&*_P); }
  595.         void _Freenode(_Nodeptr _S)
  596.                 {allocator.deallocate(_S, 1); }
  597.         _A allocator;
  598.         _Pr key_compare;
  599.         _Nodeptr _Head;
  600.         bool _Multi;
  601.         size_type _Size;
  602.         };
  603. template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
  604.         _Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nodeptr
  605.                 _Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nil = 0;
  606. template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
  607.         size_t _Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nilrefs = 0;
  608.                 // tree TEMPLATE OPERATORS
  609. template<class _K, class _Ty, class _Kfn,
  610.         class _Pr, class _A> inline
  611.         bool operator==(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
  612.                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
  613.         {return (_X.size() == _Y.size()
  614.                 && equal(_X.begin(), _X.end(), _Y.begin())); }
  615. template<class _K, class _Ty, class _Kfn,
  616.         class _Pr, class _A> inline
  617.         bool operator!=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
  618.                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
  619.         {return (!(_X == _Y)); }
  620. template<class _K, class _Ty, class _Kfn,
  621.         class _Pr, class _A> inline
  622.         bool operator<(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
  623.                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
  624.         {return (lexicographical_compare(_X.begin(), _X.end(),
  625.                 _Y.begin(), _Y.end())); }
  626. template<class _K, class _Ty, class _Kfn,
  627.         class _Pr, class _A> inline
  628.         bool operator>(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
  629.                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
  630.         {return (_Y < _X); }
  631. template<class _K, class _Ty, class _Kfn,
  632.         class _Pr, class _A> inline
  633.         bool operator<=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
  634.                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
  635.         {return (!(_Y < _X)); }
  636. template<class _K, class _Ty, class _Kfn,
  637.         class _Pr, class _A> inline
  638.         bool operator>=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
  639.                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
  640.         {return (!(_X < _Y)); }
  641. _STD_END
  642. #ifdef  _MSC_VER
  643. #pragma pack(pop)
  644. #endif  /* _MSC_VER */
  645.  
  646. #endif /* _XTREE_ */
  647.  
  648. /*
  649.  * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
  650.  * Consult your license regarding permissions and restrictions.
  651.  */
  652.  
  653. /*
  654.  * This file is derived from software bearing the following
  655.  * restrictions:
  656.  *
  657.  * Copyright (c) 1994
  658.  * Hewlett-Packard Company
  659.  *
  660.  * Permission to use, copy, modify, distribute and sell this
  661.  * software and its documentation for any purpose is hereby
  662.  * granted without fee, provided that the above copyright notice
  663.  * appear in all copies and that both that copyright notice and
  664.  * this permission notice appear in supporting documentation.
  665.  * Hewlett-Packard Company makes no representations about the
  666.  * suitability of this software for any purpose. It is provided
  667.  * "as is" without express or implied warranty.
  668.  */
  669.