Falcon_Core: /home/gian/Progetti/falcon/core/include/falcon/xtree

00001 // tree internal header
00002 
00003 #if     _MSC_VER > 1000
00004 #pragma once
00005 #endif
00006 
00007 #ifndef _XTREE_
00008 #define _XTREE_
00009 
00010 #pragma message ("Using modified VC6 XTREE for Falcon...")
00011 
00012 #include <cstddef>
00013 #include <iterator>
00014 #include <memory>
00015 #include <xutility>
00016 
00017 #define _IsNil( x ) (_Left(x) == 0)
00018 #define _IsNotNil( x ) (_Left(x) != 0)
00019 
00020 #ifdef  _MSC_VER
00021 #pragma pack(push,8)
00022 #endif  /* _MSC_VER */
00023 _STD_BEGIN
00024                 // TEMPLATE CLASS _Tree
00025 template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
00026         class _Tree {
00027 protected:
00028         enum _Redbl {_Red, _Black};
00029         struct _Node;
00030         friend struct _Node;
00031         typedef _POINTER_X(_Node, _A) _Nodeptr;
00032         struct _Node {
00033                 _Nodeptr _Left, _Parent, _Right;
00034                 _Ty _Value;
00035                 _Redbl _Color;
00036                 };
00037         typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;
00038         typedef _REFERENCE_X(const _K, _A) _Keyref;
00039         typedef _REFERENCE_X(_Redbl, _A) _Rbref;
00040         typedef _REFERENCE_X(_Ty, _A) _Vref;
00041         static _Rbref _Color(_Nodeptr _P)
00042                 {return ((_Rbref)(*_P)._Color); }
00043         static _Keyref _Key(_Nodeptr _P)
00044                 {return (_Kfn()(_Value(_P))); }
00045         static _Nodepref _Left(_Nodeptr _P)
00046                 {return ((_Nodepref)(*_P)._Left); }
00047         static _Nodepref _Parent(_Nodeptr _P)
00048                 {return ((_Nodepref)(*_P)._Parent); }
00049         static _Nodepref _Right(_Nodeptr _P)
00050                 {return ((_Nodepref)(*_P)._Right); }
00051         static _Vref _Value(_Nodeptr _P)
00052                 {return ((_Vref)(*_P)._Value); }
00053 public:
00054         typedef _Tree<_K, _Ty, _Kfn, _Pr, _A> _Myt;
00055         typedef _K key_type;
00056         typedef _Ty value_type;
00057         typedef _A::size_type size_type;
00058         typedef _A::difference_type difference_type;
00059         typedef _POINTER_X(_Ty, _A) _Tptr;
00060         typedef _POINTER_X(const _Ty, _A) _Ctptr;
00061         typedef _REFERENCE_X(_Ty, _A) reference;
00062         typedef _REFERENCE_X(const _Ty, _A) const_reference;
00063                 // CLASS const_iterator
00064         class iterator;
00065         class const_iterator;
00066         friend class const_iterator;
00067         class const_iterator : public _Bidit<_Ty, difference_type> {
00068         public:
00069                 const_iterator()
00070                         {}
00071                 const_iterator(_Nodeptr _P)
00072                         : _Ptr(_P) {}
00073                 const_iterator(const iterator& _X)
00074                         : _Ptr(_X._Ptr) {}
00075                 const_reference operator*() const
00076                         {return (_Value(_Ptr)); }
00077                 _Ctptr operator->() const
00078                         {return (&**this); }
00079                 const_iterator& operator++()
00080                         {_Inc();
00081                         return (*this); }
00082                 const_iterator operator++(int)
00083                         {const_iterator _Tmp = *this;
00084                         ++*this;
00085                         return (_Tmp); }
00086                 const_iterator& operator--()
00087                         {_Dec();
00088                         return (*this); }
00089                 const_iterator operator--(int)
00090                         {const_iterator _Tmp = *this;
00091                         --*this;
00092                         return (_Tmp); }
00093                 bool operator==(const const_iterator& _X) const
00094                         {return (_Ptr == _X._Ptr); }
00095                 bool operator!=(const const_iterator& _X) const
00096                         {return (!(*this == _X)); }
00097                 void _Dec()
00098                         {if (_Color(_Ptr) == _Red
00099                                 && _Parent(_Parent(_Ptr)) == _Ptr)
00100                                 _Ptr = _Right(_Ptr);
00101                         /* JC else if (_Left(_Ptr) != _Nil) */
00102                         else if ( _IsNotNil(_Left(_Ptr)) )
00103                                 _Ptr = _Max(_Left(_Ptr));
00104                         else
00105                                 {_Nodeptr _P;
00106                                 while (_Ptr == _Left(_P = _Parent(_Ptr)))
00107                                         _Ptr = _P;
00108                                 _Ptr = _P; }}
00109                 void _Inc()
00110                         {/* JC if (_Right(_Ptr) != _Nil)*/
00111                          if ( _IsNotNil(_Right(_Ptr)) ) 
00112                                 _Ptr = _Min(_Right(_Ptr));
00113                         else
00114                                 {_Nodeptr _P;
00115                                 while (_Ptr == _Right(_P = _Parent(_Ptr)))
00116                                         _Ptr = _P;
00117                                 if (_Right(_Ptr) != _P)
00118                                         _Ptr = _P; }}
00119                 _Nodeptr _Mynode() const
00120                         {return (_Ptr); }
00121         protected:
00122                 _Nodeptr _Ptr;
00123                 };
00124                 // CLASS iterator
00125         friend class iterator;
00126         class iterator : public const_iterator {
00127         public:
00128                 iterator()
00129                         {}
00130                 iterator(_Nodeptr _P)
00131                         : const_iterator(_P) {}
00132                 reference operator*() const
00133                         {return (_Value(_Ptr)); }
00134                 _Tptr operator->() const
00135                         {return (&**this); }
00136                 iterator& operator++()
00137                         {_Inc();
00138                         return (*this); }
00139                 iterator operator++(int)
00140                         {iterator _Tmp = *this;
00141                         ++*this;
00142                         return (_Tmp); }
00143                 iterator& operator--()
00144                         {_Dec();
00145                         return (*this); }
00146                 iterator operator--(int)
00147                         {iterator _Tmp = *this;
00148                         --*this;
00149                         return (_Tmp); }
00150                 bool operator==(const iterator& _X) const
00151                         {return (_Ptr == _X._Ptr); }
00152                 bool operator!=(const iterator& _X) const
00153                         {return (!(*this == _X)); }
00154                 };
00155         typedef reverse_bidirectional_iterator<iterator,
00156                 value_type, reference, _Tptr, difference_type>
00157                         reverse_iterator;
00158         typedef reverse_bidirectional_iterator<const_iterator,
00159                 value_type, const_reference, _Ctptr, difference_type>
00160                         const_reverse_iterator;
00161         typedef pair<iterator, bool> _Pairib;
00162         typedef pair<iterator, iterator> _Pairii;
00163         typedef pair<const_iterator, const_iterator> _Paircc;
00164         explicit _Tree(const _Pr& _Parg, bool _Marg = true,
00165                 const _A& _Al = _A())
00166                 : allocator(_Al),
00167                 key_compare(_Parg), _Multi(_Marg)
00168                 {_Init(); }
00169         _Tree(const _Ty *_F, const _Ty *_L,
00170                 const _Pr& _Parg, bool _Marg = true,
00171                 const _A& _Al = _A())
00172                 : allocator(_Al),
00173                 key_compare(_Parg), _Multi(_Marg)
00174                 {_Init();
00175                 insert(_F, _L); }
00176         _Tree(const _Myt& _X)
00177                 : allocator(_X.allocator),
00178                 key_compare(_X.key_compare), _Multi(_X._Multi)
00179                 {_Init();
00180                 _Copy(_X); }
00181         ~_Tree()
00182                 {erase(begin(), end());
00183                 _Freenode(_Head);
00184                 _Head = 0, _Size = 0;
00185                 _Nodeptr _Tmp = 0;
00186                         {_Lockit _Lk;
00187                         if (--_Nilrefs == 0)
00188                                 {_Tmp = _Nil;
00189                                 _Nil = 0; }}
00190                 if (_Tmp != 0)
00191                         _Freenode(_Tmp); }
00192         _Myt& operator=(const _Myt& _X)
00193                 {if (this != &_X)
00194                         {erase(begin(), end());
00195                         key_compare = _X.key_compare;
00196                         _Copy(_X); }
00197                 return (*this); }
00198         iterator begin()
00199                 {return (iterator(_Lmost())); }
00200         const_iterator begin() const
00201                 {return (const_iterator(_Lmost())); }
00202         iterator end()
00203                 {return (iterator(_Head)); }
00204         const_iterator end() const
00205                 {return (const_iterator(_Head)); }
00206         reverse_iterator rbegin()
00207                 {return (reverse_iterator(end())); }
00208         const_reverse_iterator rbegin() const
00209                 {return (const_reverse_iterator(end())); }
00210         reverse_iterator rend()
00211                 {return (reverse_iterator(begin())); }
00212         const_reverse_iterator rend() const
00213                 {return (const_reverse_iterator(begin())); }
00214         size_type size() const
00215                 {return (_Size); }
00216         size_type max_size() const
00217                 {return (allocator.max_size()); }
00218         bool empty() const
00219                 {return (size() == 0); }
00220         _A get_allocator() const
00221                 {return (allocator); }
00222         _Pr key_comp() const
00223                 {return (key_compare); }
00224         _Pairib insert(const value_type& _V)
00225                 {_Nodeptr _X = _Root();
00226                 _Nodeptr _Y = _Head;
00227                 bool _Ans = true;
00228                         /* JC while (_X != _Nil) */
00229                         while( _IsNotNil(_X) )
00230                                 {_Y = _X;
00231                                 _Ans = key_compare(_Kfn()(_V), _Key(_X));
00232                                 _X = _Ans ? _Left(_X) : _Right(_X); }
00233                 if (_Multi)
00234                         return (_Pairib(_Insert(_X, _Y, _V), true));
00235                 iterator _P = iterator(_Y);
00236                 if (!_Ans)
00237                         ;
00238                 else if (_P == begin())
00239                         return (_Pairib(_Insert(_X, _Y, _V), true));
00240                 else
00241                         --_P;
00242                 if (key_compare(_Key(_P._Mynode()), _Kfn()(_V)))
00243                         return (_Pairib(_Insert(_X, _Y, _V), true));
00244                 return (_Pairib(_P, false)); }
00245         iterator insert(iterator _P, const value_type& _V)
00246                 {if (size() == 0)
00247                         ;
00248                 else if (_P == begin())
00249                         {if (key_compare(_Kfn()(_V), _Key(_P._Mynode())))
00250                                 return (_Insert(_Head, _P._Mynode(), _V)); }
00251                 else if (_P == end())
00252                         {if (key_compare(_Key(_Rmost()), _Kfn()(_V)))
00253                                 return (_Insert(_Nil, _Rmost(), _V)); }
00254                 else
00255                         {iterator _Pb = _P;
00256                         if (key_compare(_Key((--_Pb)._Mynode()), _Kfn()(_V))
00257                                 && key_compare(_Kfn()(_V), _Key(_P._Mynode())))
00258                                 { /* JC if (_Right(_Pb._Mynode()) == _Nil) */
00259                                   if ( _IsNil(_Right(_Pb._Mynode())) )
00260                                         return (_Insert(_Nil, _Pb._Mynode(), _V));
00261                                 else
00262                                         return (_Insert(_Head, _P._Mynode(), _V)); }}
00263                 return (insert(_V).first); }
00264         void insert(iterator _F, iterator _L)
00265                 {for (; _F != _L; ++_F)
00266                         insert(*_F); }
00267         void insert(const value_type *_F, const value_type *_L)
00268                 {for (; _F != _L; ++_F)
00269                         insert(*_F); }
00270         iterator erase(iterator _P)
00271                 {_Nodeptr _X;
00272                 _Nodeptr _Y = (_P++)._Mynode();
00273                 _Nodeptr _Z = _Y;
00274                 /* JC if (_Left(_Y) == _Nil) */
00275                 if ( _IsNil(_Left(_Y)) )
00276                         _X = _Right(_Y);
00277                 /* JC else if (_Right(_Y) == _Nil) */
00278                 else if (_IsNil(_Right(_Y)))
00279                         _X = _Left(_Y);
00280                 else
00281                         _Y = _Min(_Right(_Y)), _X = _Right(_Y);
00282                 { _Lockit _Lk;
00283                 if (_Y != _Z)
00284                         {_Parent(_Left(_Z)) = _Y;
00285                         _Left(_Y) = _Left(_Z);
00286                         if (_Y == _Right(_Z))
00287                                 _Parent(_X) = _Y;
00288                         else
00289                                 {_Parent(_X) = _Parent(_Y);
00290                                 _Left(_Parent(_Y)) = _X;
00291                                 _Right(_Y) = _Right(_Z);
00292                                 _Parent(_Right(_Z)) = _Y; }
00293                         if (_Root() == _Z)
00294                                 _Root() = _Y;
00295                         else if (_Left(_Parent(_Z)) == _Z)
00296                                 _Left(_Parent(_Z)) = _Y;
00297                         else
00298                                 _Right(_Parent(_Z)) = _Y;
00299                         _Parent(_Y) = _Parent(_Z);
00300                         std::swap(_Color(_Y), _Color(_Z));
00301                         _Y = _Z; }
00302                 else
00303                         {_Parent(_X) = _Parent(_Y);
00304                         if (_Root() == _Z)
00305                                 _Root() = _X;
00306                         else if (_Left(_Parent(_Z)) == _Z)
00307                                 _Left(_Parent(_Z)) = _X;
00308                         else
00309                                 _Right(_Parent(_Z)) = _X;
00310                         if (_Lmost() != _Z)
00311                                 ;
00312                         /* JC else if (_Right(_Z) == _Nil) */
00313                         else if ( _IsNil(_Right(_Z)) )
00314                                 _Lmost() = _Parent(_Z);
00315                         else
00316                                 _Lmost() = _Min(_X);
00317                         if (_Rmost() != _Z)
00318                                 ;
00319                         /* JC else if (_Left(_Z) == _Nil) */
00320                         else if ( _IsNil(_Left(_Z)) )
00321                                 _Rmost() = _Parent(_Z);
00322                         else
00323                                 _Rmost() = _Max(_X); }
00324                 if (_Color(_Y) == _Black)
00325                         {while (_X != _Root() && _Color(_X) == _Black)
00326                                 if (_X == _Left(_Parent(_X)))
00327                                         {_Nodeptr _W = _Right(_Parent(_X));
00328                                         if (_Color(_W) == _Red)
00329                                                 {_Color(_W) = _Black;
00330                                                 _Color(_Parent(_X)) = _Red;
00331                                                 _Lrotate(_Parent(_X));
00332                                                 _W = _Right(_Parent(_X)); }
00333                                         if (_Color(_Left(_W)) == _Black
00334                                                 && _Color(_Right(_W)) == _Black)
00335                                                 {_Color(_W) = _Red;
00336                                                 _X = _Parent(_X); }
00337                                         else
00338                                                 {if (_Color(_Right(_W)) == _Black)
00339                                                         {_Color(_Left(_W)) = _Black;
00340                                                         _Color(_W) = _Red;
00341                                                         _Rrotate(_W);
00342                                                         _W = _Right(_Parent(_X)); }
00343                                                 _Color(_W) = _Color(_Parent(_X));
00344                                                 _Color(_Parent(_X)) = _Black;
00345                                                 _Color(_Right(_W)) = _Black;
00346                                                 _Lrotate(_Parent(_X));
00347                                                 break; }}
00348                                 else
00349                                         {_Nodeptr _W = _Left(_Parent(_X));
00350                                         if (_Color(_W) == _Red)
00351                                                 {_Color(_W) = _Black;
00352                                                 _Color(_Parent(_X)) = _Red;
00353                                                 _Rrotate(_Parent(_X));
00354                                                 _W = _Left(_Parent(_X)); }
00355                                         if (_Color(_Right(_W)) == _Black
00356                                                 && _Color(_Left(_W)) == _Black)
00357                                                 {_Color(_W) = _Red;
00358                                                 _X = _Parent(_X); }
00359                                         else
00360                                                 {if (_Color(_Left(_W)) == _Black)
00361                                                         {_Color(_Right(_W)) = _Black;
00362                                                         _Color(_W) = _Red;
00363                                                         _Lrotate(_W);
00364                                                         _W = _Left(_Parent(_X)); }
00365                                                 _Color(_W) = _Color(_Parent(_X));
00366                                                 _Color(_Parent(_X)) = _Black;
00367                                                 _Color(_Left(_W)) = _Black;
00368                                                 _Rrotate(_Parent(_X));
00369                                                 break; }}
00370                         _Color(_X) = _Black; }
00371                 }
00372                 _Destval(&_Value(_Y));
00373                 _Freenode(_Y);
00374                 --_Size;
00375                 return (_P); }
00376         iterator erase(iterator _F, iterator _L)
00377                 {if (size() == 0 || _F != begin() || _L != end())
00378                         {while (_F != _L)
00379                                 erase(_F++);
00380                         return (_F); }
00381                 else
00382                         {_Erase(_Root());
00383                         _Root() = _Nil, _Size = 0;
00384                         _Lmost() = _Head, _Rmost() = _Head;
00385                         return (begin()); }}
00386         size_type erase(const _K& _X)
00387                 {_Pairii _P = equal_range(_X);
00388                 size_type _N = 0;
00389                 _Distance(_P.first, _P.second, _N);
00390                 erase(_P.first, _P.second);
00391                 return (_N); }
00392         void erase(const _K *_F, const _K *_L)
00393                 {for (; _F != _L; ++_F)
00394                         erase(*_F); }
00395         void clear()
00396                 {erase(begin(), end()); }
00397         iterator find(const _K& _Kv)
00398                 {iterator _P = lower_bound(_Kv);
00399                 return (_P == end()
00400                         || key_compare(_Kv, _Key(_P._Mynode()))
00401                                 ? end() : _P); }
00402         const_iterator find(const _K& _Kv) const
00403                 {const_iterator _P = lower_bound(_Kv);
00404                 return (_P == end()
00405                         || key_compare(_Kv, _Key(_P._Mynode()))
00406                                 ? end() : _P); }
00407         size_type count(const _K& _Kv) const
00408                 {_Paircc _Ans = equal_range(_Kv);
00409                 size_type _N = 0;
00410                 _Distance(_Ans.first, _Ans.second, _N);
00411                 return (_N); }
00412         iterator lower_bound(const _K& _Kv)
00413                 {return (iterator(_Lbound(_Kv))); }
00414         const_iterator lower_bound(const _K& _Kv) const
00415                 {return (const_iterator(_Lbound(_Kv))); }
00416         iterator upper_bound(const _K& _Kv)
00417                 {return (iterator(_Ubound(_Kv))); }
00418         const_iterator upper_bound(const _K& _Kv) const
00419                 {return (iterator(_Ubound(_Kv))); }
00420         _Pairii equal_range(const _K& _Kv)
00421                 {return (_Pairii(lower_bound(_Kv), upper_bound(_Kv))); }
00422         _Paircc equal_range(const _K& _Kv) const
00423                 {return (_Paircc(lower_bound(_Kv), upper_bound(_Kv))); }
00424         void swap(_Myt& _X)
00425                 {std::swap(key_compare, _X.key_compare);
00426                 if (allocator == _X.allocator)
00427                         {std::swap(_Head, _X._Head);
00428                         std::swap(_Multi, _X._Multi);
00429                         std::swap(_Size, _X._Size); }
00430                 else
00431                         {_Myt _Ts = *this; *this = _X, _X = _Ts; }}
00432         friend void swap(_Myt& _X, _Myt& _Y)
00433                 {_X.swap(_Y); }
00434 protected:
00435         static _Nodeptr _Nil;
00436         static size_t _Nilrefs;
00437         void _Copy(const _Myt& _X)
00438                 {_Root() = _Copy(_X._Root(), _Head);
00439                 _Size = _X.size();
00440                 /* JC if (_Root() != _Nil ) */
00441                 if ( _IsNotNil(_Root()) )
00442                         {_Lmost() = _Min(_Root());
00443                         _Rmost() = _Max(_Root()); }
00444                 else
00445                         _Lmost() = _Head, _Rmost() = _Head; }
00446         _Nodeptr _Copy(_Nodeptr _X, _Nodeptr _P)
00447                 {_Nodeptr _R = _X;
00448                 /* JC1 for (; _X != _Nil; _X = _Left(_X)) */
00449                 for (; _IsNotNil(_X); _X = _Left(_X))
00450                         {_Nodeptr _Y = _Buynode(_P, _Color(_X));
00451                         if (_R == _X)
00452                                 _R = _Y;
00453                         _Right(_Y) = _Copy(_Right(_X), _Y);
00454                         _Consval(&_Value(_Y), _Value(_X));
00455                         _Left(_P) = _Y;
00456                         _P = _Y; }
00457                 _Left(_P) = _Nil;
00458                 return (_R); }
00459         void _Erase(_Nodeptr _X)
00460                 {/* JC for (_Nodeptr _Y = _X; _Y != _Nil; _X = _Y) */
00461                 for (_Nodeptr _Y = _X; _IsNotNil(_Y); _X = _Y)
00462                         {_Erase(_Right(_Y));
00463                         _Y = _Left(_Y);
00464                         _Destval(&_Value(_X));
00465                         _Freenode(_X); }}
00466         void _Init()
00467                 {_Nodeptr _Tmp = _Buynode(0, _Black);
00468                 {_Lockit _Lk;
00469                 if (_Nil == 0)
00470                                 {_Nil = _Tmp;
00471                                 _Tmp = 0;
00472                         _Left(_Nil) = 0, _Right(_Nil) = 0; }
00473                         ++_Nilrefs;  } 
00474                 if (_Tmp != 0)
00475                         _Freenode(_Tmp);
00476                 _Head = _Buynode(_Nil, _Red), _Size = 0;
00477                 _Lmost() = _Head, _Rmost() = _Head; }
00478         iterator _Insert(_Nodeptr _X, _Nodeptr _Y, const _Ty& _V)
00479                 {_Nodeptr _Z = _Buynode(_Y, _Red);
00480                 _Left(_Z) = _Nil, _Right(_Z) = _Nil;
00481                 _Consval(&_Value(_Z), _V);
00482                 ++_Size;
00483                 /* JC if (_Y == _Head || _X != _Nil */
00484                if (_Y == _Head || _IsNotNil(_X)
00485                         || key_compare(_Kfn()(_V), _Key(_Y)))
00486                         {_Left(_Y) = _Z;
00487                         if (_Y == _Head)
00488                                 {_Root() = _Z;
00489                                 _Rmost() = _Z; }
00490                         else if (_Y == _Lmost())
00491                                 _Lmost() = _Z; }
00492                 else
00493                         {_Right(_Y) = _Z;
00494                         if (_Y == _Rmost())
00495                                 _Rmost() = _Z; }
00496                 for (_X = _Z; _X != _Root()
00497                         && _Color(_Parent(_X)) == _Red; )
00498                         if (_Parent(_X) == _Left(_Parent(_Parent(_X))))
00499                                 {_Y = _Right(_Parent(_Parent(_X)));
00500                                 if (_Color(_Y) == _Red)
00501                                         {_Color(_Parent(_X)) = _Black;
00502                                         _Color(_Y) = _Black;
00503                                         _Color(_Parent(_Parent(_X))) = _Red;
00504                                         _X = _Parent(_Parent(_X)); }
00505                                 else
00506                                         {if (_X == _Right(_Parent(_X)))
00507                                                 {_X = _Parent(_X);
00508                                                 _Lrotate(_X); }
00509                                         _Color(_Parent(_X)) = _Black;
00510                                         _Color(_Parent(_Parent(_X))) = _Red;
00511                                         _Rrotate(_Parent(_Parent(_X))); }}
00512                         else
00513                                 {_Y = _Left(_Parent(_Parent(_X)));
00514                                 if (_Color(_Y) == _Red)
00515                                         {_Color(_Parent(_X)) = _Black;
00516                                         _Color(_Y) = _Black;
00517                                         _Color(_Parent(_Parent(_X))) = _Red;
00518                                         _X = _Parent(_Parent(_X)); }
00519                                 else
00520                                         {if (_X == _Left(_Parent(_X)))
00521                                                 {_X = _Parent(_X);
00522                                                 _Rrotate(_X); }
00523                                         _Color(_Parent(_X)) = _Black;
00524                                         _Color(_Parent(_Parent(_X))) = _Red;
00525                                         _Lrotate(_Parent(_Parent(_X))); }}
00526                 _Color(_Root()) = _Black;
00527                 return (iterator(_Z)); }
00528         _Nodeptr _Lbound(const _K& _Kv) const
00529                 {_Nodeptr _X = _Root();
00530                 _Nodeptr _Y = _Head;
00531                 /* JC while (_X != _Nil) */
00532                 while ( _IsNotNil(_X) )
00533                         if (key_compare(_Key(_X), _Kv))
00534                                 _X = _Right(_X);
00535                         else
00536                                 _Y = _X, _X = _Left(_X);
00537                 return (_Y); }
00538         _Nodeptr& _Lmost()
00539                 {return (_Left(_Head)); }
00540         _Nodeptr& _Lmost() const
00541                 {return (_Left(_Head)); }
00542         void _Lrotate(_Nodeptr _X)
00543                 {_Nodeptr _Y = _Right(_X);
00544                 _Right(_X) = _Left(_Y);
00545                 /* JC if (_Left(_Y) != _Nil) */
00546                 if ( _IsNotNil(_Left(_Y)) )
00547                         _Parent(_Left(_Y)) = _X;
00548                 _Parent(_Y) = _Parent(_X);
00549                 if (_X == _Root())
00550                         _Root() = _Y;
00551                 else if (_X == _Left(_Parent(_X)))
00552                         _Left(_Parent(_X)) = _Y;
00553                 else
00554                         _Right(_Parent(_X)) = _Y;
00555                 _Left(_Y) = _X;
00556                 _Parent(_X) = _Y; }
00557         static _Nodeptr _Max(_Nodeptr _P)
00558                 {/* JC while (_Right(_P) != _Nil) */
00559                   while ( _IsNotNil(_Right(_P)) )
00560                         _P = _Right(_P);
00561                 return (_P); }
00562         static _Nodeptr _Min(_Nodeptr _P)
00563                 {/* JC while (_Left(_P) != _Nil) */
00564                   while ( _IsNotNil(_Left(_P)) )
00565                         _P = _Left(_P);
00566                 return (_P); }
00567         _Nodeptr& _Rmost()
00568                 {return (_Right(_Head)); }
00569         _Nodeptr& _Rmost() const
00570                 {return (_Right(_Head)); }
00571         _Nodeptr& _Root()
00572                 {return (_Parent(_Head)); }
00573         _Nodeptr& _Root() const
00574                 {return (_Parent(_Head)); }
00575         void _Rrotate(_Nodeptr _X)
00576                 {_Nodeptr _Y = _Left(_X);
00577                 _Left(_X) = _Right(_Y);
00578                 /* JC1 if (_Right(_Y) != _Nil) */
00579                   if ( _IsNotNil( _Right(_Y) ))
00580                         _Parent(_Right(_Y)) = _X;
00581                 _Parent(_Y) = _Parent(_X);
00582                 if (_X == _Root())
00583                         _Root() = _Y;
00584                 else if (_X == _Right(_Parent(_X)))
00585                         _Right(_Parent(_X)) = _Y;
00586                 else
00587                         _Left(_Parent(_X)) = _Y;
00588                 _Right(_Y) = _X;
00589                 _Parent(_X) = _Y; }
00590         _Nodeptr _Ubound(const _K& _Kv) const
00591                 {_Nodeptr _X = _Root();
00592                 _Nodeptr _Y = _Head;
00593                 /* JC while (_X != _Nil) */
00594                 while ( _IsNotNil(_X) )
00595                         if (key_compare(_Kv, _Key(_X)))
00596                                 _Y = _X, _X = _Left(_X);
00597                         else
00598                                 _X = _Right(_X);
00599                 return (_Y); }
00600         _Nodeptr _Buynode(_Nodeptr _Parg, _Redbl _Carg)
00601                 {_Nodeptr _S = (_Nodeptr)allocator._Charalloc(
00602                         1 * sizeof (_Node));
00603                 _Parent(_S) = _Parg;
00604                 _Color(_S) = _Carg;
00605                 return (_S); }
00606         void _Consval(_Tptr _P, const _Ty& _V)
00607                 {_Construct(&*_P, _V); }
00608         void _Destval(_Tptr _P)
00609                 {_Destroy(&*_P); }
00610         void _Freenode(_Nodeptr _S)
00611                 {allocator.deallocate(_S, 1); }
00612         _A allocator;
00613         _Pr key_compare;
00614         _Nodeptr _Head;
00615         bool _Multi;
00616         size_type _Size;
00617         };
00618 template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
00619         _Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nodeptr
00620                 _Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nil = 0;
00621 template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
00622         size_t _Tree<_K, _Ty, _Kfn, _Pr, _A>::_Nilrefs = 0;
00623                 // tree TEMPLATE OPERATORS
00624 template<class _K, class _Ty, class _Kfn,
00625         class _Pr, class _A> inline
00626         bool operator==(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
00627                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
00628         {return (_X.size() == _Y.size()
00629                 && equal(_X.begin(), _X.end(), _Y.begin())); }
00630 template<class _K, class _Ty, class _Kfn,
00631         class _Pr, class _A> inline
00632         bool operator!=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
00633                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
00634         {return (!(_X == _Y)); }
00635 template<class _K, class _Ty, class _Kfn,
00636         class _Pr, class _A> inline
00637         bool operator<(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
00638                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
00639         {return (lexicographical_compare(_X.begin(), _X.end(),
00640                 _Y.begin(), _Y.end())); }
00641 template<class _K, class _Ty, class _Kfn,
00642         class _Pr, class _A> inline
00643         bool operator>(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
00644                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
00645         {return (_Y < _X); }
00646 template<class _K, class _Ty, class _Kfn,
00647         class _Pr, class _A> inline
00648         bool operator<=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
00649                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
00650         {return (!(_Y < _X)); }
00651 template<class _K, class _Ty, class _Kfn,
00652         class _Pr, class _A> inline
00653         bool operator>=(const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _X,
00654                 const _Tree<_K, _Ty, _Kfn, _Pr, _A>& _Y)
00655         {return (!(_X < _Y)); }
00656 _STD_END
00657 #ifdef  _MSC_VER
00658 #pragma pack(pop)
00659 #endif  /* _MSC_VER */
00660 
00661 #endif /* _XTREE_ */
00662 
00663 /*
00664  * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
00665  * Consult your license regarding permissions and restrictions.
00666  */
00667 
00668 /*
00669  * This file is derived from software bearing the following
00670  * restrictions:
00671  *
00672  * Copyright (c) 1994
00673  * Hewlett-Packard Company
00674  *
00675  * Permission to use, copy, modify, distribute and sell this
00676  * software and its documentation for any purpose is hereby
00677  * granted without fee, provided that the above copyright notice
00678  * appear in all copies and that both that copyright notice and
00679  * this permission notice appear in supporting documentation.
00680  * Hewlett-Packard Company makes no representations about the
00681  * suitability of this software for any purpose. It is provided
00682  * "as is" without express or implied warranty.
00683  */
00684 
00685 /*
00686  * File modified to make it work across DLL calls by Giancarlo Niccolai
00687  * Parts changed are marked by JC comment.
00688  *
00689  * Copyright (C) 2004 Giancarlo Niccolai
00690  *
00691  * The changes are distributed under the same statement as above,
00692  * including, but not limited to, the exclusion of any express or implied
00693  * warranty 
00694  */
/home/gian/Progetti/falcon/core/include/falcon/xtree_fix.h
