Terimber Corporation

00001 /*
00002  * The Software License
00003  * =================================================================================
00004  * Copyright (c) 2003-.The Terimber Corporation. All rights reserved.
00005  * =================================================================================
00006  * Redistributions of source code must retain the above copyright notice, 
00007  * this list of conditions and the following disclaimer.
00008  * Redistributions in binary form must reproduce the above copyright notice, 
00009  * this list of conditions and the following disclaimer in the documentation 
00010  * and/or other materials provided with the distribution.
00011  * The end-user documentation included with the redistribution, if any, 
00012  * must include the following acknowledgment:
00013  * "This product includes software developed by the Terimber Corporation."
00014  * =================================================================================
00015  * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED WARRANTIES, 
00016  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 
00017  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  
00018  * IN NO EVENT SHALL THE TERIMBER CORPORATION OR ITS CONTRIBUTORS BE LIABLE FOR 
00019  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
00020  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
00021  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 
00022  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00023  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00024  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00025  * ================================================================================
00026 */
00027 
00028 #ifndef _terimber_map_hpp_
00029 #define _terimber_map_hpp_
00030 
00031 #include "base/map.h"
00032 #include "base/common.hpp"
00033 
00034 BEGIN_TERIMBER_NAMESPACE
00035 #pragma pack(4)
00036 
00037 template< class T >
00038 inline
00039 bool
00040 less< T >::operator()(const T& first, const T& second) const
00041 { 
00042         return first < second; 
00043 }
00044 
00046 template < class T1, class T2 > 
00047 pair< T1, T2 >::pair() :
00048         first(T1()), second(T2())
00049 {
00050 }
00051 
00052 template < class T1, class T2 > 
00053 pair< T1, T2 >::pair(const T1& v1, const T2& v2) : 
00054         first(v1), second(v2)
00055 {
00056 }
00057 
00058 template < class T1, class T2 > 
00059 pair< T1, T2 >::pair(const pair< T1, T2 >& x) : 
00060         first(x.first), second(x.second)
00061 {
00062 }
00063 
00064 template < class T1, class T2 > 
00065 inline
00066 bool
00067 pair< T1, T2 >::operator==(const pair< T1, T2 >& x) const
00068 { 
00069         return first == x.first && second == x.second; 
00070 }
00071 
00072 template < class T1, class T2 > 
00073 inline 
00074 bool 
00075 pair< T1, T2 >::operator<(const pair< T1, T2 >& x) const
00076 { 
00077         return first != x.first ? first < x.first : second < x.second; 
00078 }
00079 
00080 template < class T1, class T2 > 
00081 inline 
00082 bool 
00083 pair< T1, T2 >::operator!=(const pair< T1, T2 >& x) const
00084 { 
00085         return !(*this == x); 
00086 }
00087 
00089 template < class K, class T, class Pr, bool M >
00090 //explicit 
00091 base_map< K, T, Pr, M >::base_map(const Pr& pr) : 
00092         key_compare(pr), _head(), _size(0) 
00093 {
00094         clear();
00095 }
00096 
00097 template < class K, class T, class Pr, bool M >
00098 base_map< K, T, Pr, M >::~base_map()    
00099 {
00100 }
00101 
00102 template < class K, class T, class Pr, bool M >
00103 base_map< K, T, Pr, M >::base_map(const base_map< K, T, Pr, M >& x) : 
00104         key_compare(x.key_compare), _head(), _size(x._size) 
00105 { 
00106         clear(); 
00107 }
00108 
00109 template < class K, class T, class Pr, bool M >
00110 inline 
00111 const Pr&
00112 base_map< K, T, Pr, M >::comp() const
00113 { 
00114         return key_compare; 
00115 }
00116 
00117 template < class K, class T, class Pr, bool M >
00118 inline 
00119 TYPENAME base_map< K, T, Pr, M >::iterator
00120 base_map< K, T, Pr, M >::begin() 
00121 { 
00122         return iterator(_head._left); 
00123 }
00124 
00125 template < class K, class T, class Pr, bool M >
00126 inline 
00127 TYPENAME base_map< K, T, Pr, M >::const_iterator
00128 base_map< K, T, Pr, M >::begin() const 
00129 { 
00130         return const_iterator(head()->_left); 
00131 }
00132 
00133 template < class K, class T, class Pr, bool M >
00134 inline 
00135 TYPENAME base_map< K, T, Pr, M >::iterator
00136 base_map< K, T, Pr, M >::end() 
00137 { 
00138         return iterator(head()); 
00139 }
00140 
00141 template < class K, class T, class Pr, bool M >
00142 inline 
00143 TYPENAME base_map< K, T, Pr, M >::const_iterator
00144 base_map< K, T, Pr, M >::end() const 
00145 { 
00146         return const_iterator(head()); 
00147 }
00148 
00149 template < class K, class T, class Pr, bool M >
00150 inline 
00151 size_t
00152 base_map< K, T, Pr, M >::size() const 
00153 { 
00154         return _size; 
00155 }
00156 
00157 template < class K, class T, class Pr, bool M >
00158 inline 
00159 bool
00160 base_map< K, T, Pr, M >::empty() const 
00161 { 
00162         return !_size; 
00163 }
00164 
00165 template < class K, class T, class Pr, bool M >
00166 inline 
00167 TYPENAME base_map< K, T, Pr, M >::iterator
00168 base_map< K, T, Pr, M >::find(const K& k)
00169 {
00170         TYPENAME base_map< K, T, Pr, M >::iterator p = lower_bound(k);
00171         return p == end() || key_compare(k, p.key()) ? end() : p; 
00172 }
00173 
00174 template < class K, class T, class Pr, bool M >
00175 inline 
00176 TYPENAME base_map< K, T, Pr, M >::const_iterator
00177 base_map< K, T, Pr, M >::find(const K& k) const
00178 {
00179         TYPENAME base_map< K, T, Pr, M >::const_iterator p = lower_bound(k);
00180         return p == end() || key_compare(k, p.key()) ? end() : p; 
00181 }
00182 
00183 template < class K, class T, class Pr, bool M >
00184 inline 
00185 TYPENAME base_map< K, T, Pr, M >::iterator
00186 base_map< K, T, Pr, M >::lower_bound(const K& k) 
00187 { 
00188         return iterator(_lbound(k)); 
00189 }
00190 
00191 template < class K, class T, class Pr, bool M >
00192 inline 
00193 TYPENAME base_map< K, T, Pr, M >::const_iterator
00194 base_map< K, T, Pr, M >::lower_bound(const K& k) const 
00195 { 
00196         return const_iterator(_lbound(k)); 
00197 }
00198 
00199 template < class K, class T, class Pr, bool M >
00200 inline 
00201 TYPENAME base_map< K, T, Pr, M >::iterator
00202 base_map< K, T, Pr, M >::upper_bound(const K& k) 
00203 { 
00204         return iterator(_ubound(k)); 
00205 }
00206 
00207 template < class K, class T, class Pr, bool M >
00208 inline 
00209 TYPENAME base_map< K, T, Pr, M >::const_iterator
00210 base_map< K, T, Pr, M >::upper_bound(const K& k) const 
00211 { 
00212         return iterator(_ubound(k)); 
00213 }
00214 
00215 template < class K, class T, class Pr, bool M >
00216 inline 
00217 TYPENAME base_map< K, T, Pr, M >::pairii_t
00218 base_map< K, T, Pr, M >::equal_range(const K& k) 
00219 { 
00220         return TYPENAME base_map< K, T, Pr, M >::pairii_t(lower_bound(k), upper_bound(k)); 
00221 }
00222 
00223 template < class K, class T, class Pr, bool M >
00224 inline 
00225 TYPENAME base_map< K, T, Pr, M >::paircc_t
00226 base_map< K, T, Pr, M >::equal_range(const K& k) const 
00227 { 
00228         return TYPENAME base_map< K, T, Pr, M >::paircc_t(lower_bound(k), upper_bound(k)); 
00229 }
00230 
00231 template < class K, class T, class Pr, bool M >
00232 inline 
00233 void
00234 base_map< K, T, Pr, M >::clear()
00235 { 
00236         _size = 0;
00237         _head._color = c_black;
00238         _head._type = t_head;
00239         _head._parent = _head._left = _head._right = head();
00240 }
00241 
00242 template < class K, class T, class Pr, bool M >
00243 inline 
00244 TYPENAME base_map< K, T, Pr, M >::iterator
00245 base_map< K, T, Pr, M >::_insert(bool left, TYPENAME base_map< K, T, Pr, M >::_node* w, TYPENAME base_map< K, T, Pr, M >::_node* n, const K& k, const T& v)
00246 {
00247         n->_left = n->_right = head();
00248         _consval(&n->_value, v);
00249         _conskey(&n->_key, k);
00250 
00251         ++_size;
00252         if (w == head())
00253         {
00254                 _head._parent = n;
00255                 _head._left = n;
00256                 _head._right = n;
00257         }
00258         else if (left)
00259         {
00260                 w->_left = n;
00261                 if (w == _head._left)
00262                         _head._left = n;
00263         }
00264         else
00265         {
00266                 w->_right = n;
00267                 if (w == _head._right)
00268                         _head._right = n;
00269         }
00270 
00271         for (_node* p = n; p->_parent->_color == c_red; )
00272                 if (p->_parent == p->_parent->_parent->_left)
00273                 {
00274                         w = p->_parent->_parent->_right;
00275                         if (w->_color == c_red)
00276                         {
00277                                 p->_parent->_color = c_black;
00278                                 w->_color = c_black;
00279                                 p->_parent->_parent->_color = c_red;
00280                                 p = p->_parent->_parent;
00281                         }
00282                         else
00283                         {
00284                                 if (p == p->_parent->_right)
00285                                 {
00286                                         p = p->_parent;
00287                                         _lrotate(p);
00288                                 }
00289                                 p->_parent->_color = c_black;
00290                                 p->_parent->_parent->_color = c_red;
00291                                 _rrotate(p->_parent->_parent);
00292                         }
00293                 }
00294                 else
00295                 {
00296                         w = p->_parent->_parent->_left;
00297                         if (w->_color == c_red)
00298                         {
00299                                 p->_parent->_color = c_black;
00300                                 w->_color = c_black;
00301                                 p->_parent->_parent->_color = c_red;
00302                                 p = p->_parent->_parent;
00303                         }
00304                         else
00305                         {
00306                                 if (p == p->_parent->_left)
00307                                 {
00308                                         p = p->_parent;
00309                                         _rrotate(p);
00310                                 }
00311                                 p->_parent->_color = c_black;
00312                                 p->_parent->_parent->_color = c_red;
00313                                 _lrotate(p->_parent->_parent);
00314                         }
00315                 }
00316 
00317         _head._parent->_color = c_black;
00318         return TYPENAME base_map< K, T, Pr, M >::iterator(n);
00319 }
00320 
00321 template < class K, class T, class Pr, bool M >
00322 inline 
00323 TYPENAME base_map< K, T, Pr, M >::iterator
00324 base_map< K, T, Pr, M >::_erase(TYPENAME base_map< K, T, Pr, M >::iterator w, TYPENAME base_map< K, T, Pr, M >::_node*& e)
00325 {
00326         if (!_size)
00327                 return this->end();
00328 
00329         TYPENAME base_map< K, T, Pr, M >::_node* x, *px = 0;
00330         TYPENAME base_map< K, T, Pr, M >::_node* p = e = (w++).node();
00331         if (p->_left->_type == t_head)
00332                 x = p->_right;
00333         else if (p->_right->_type == t_head)
00334                 x = p->_left;
00335         else
00336                 p = w.node(), x = p->_right;
00337 
00338         if (p == e)
00339         {
00340                 px = e->_parent;
00341                 if (x->_type != t_head)
00342                         x->_parent = px;
00343 
00344                 if (_head._parent == e)
00345                         _head._parent = x;
00346                 else if (px->_left == e)
00347                         px->_left = x;
00348                 else
00349                         px->_right = x;
00350 
00351                 if (_head._left == e)
00352                         _head._left = (x->_type == t_head ? px : _node::_min(x));
00353 
00354                 if (_head._right == e)
00355                         _head._right = (x->_type == t_head ? px : _node::_max(x)); 
00356         }
00357         else
00358         {
00359                 e->_left->_parent = p;
00360                 p->_left = e->_left;
00361                 if (p == e->_right)
00362                         px = p;
00363                 else
00364                 {
00365                         px = p->_parent;
00366                         if (x->_type != t_head)
00367                                 x->_parent = px;
00368             px->_left = x;
00369                         p->_right = e->_right;
00370                         e->_right->_parent = p; 
00371                 }
00372 
00373                 if (_head._parent == e)
00374                         _head._parent = p;
00375                 else if (e->_parent->_left == e)
00376                         e->_parent->_left = p;
00377                 else
00378                         e->_parent->_right = p;
00379         p->_parent = e->_parent;
00380                 redblack c = p->_color;
00381                 p->_color = e->_color;
00382                 e->_color = c;
00383         }
00384 
00385         if (e->_color == c_black)
00386         {       
00387                 for (;x != _head._parent && x->_color == c_black; px = x->_parent)
00388                         if (x == px->_left)
00389                         {
00390                                 p = px->_right;
00391                                 if (p->_color == c_red)
00392                                 {
00393                                         p->_color = c_black;
00394                                         px->_color = c_red;
00395                                         _lrotate(px);
00396                                         p = px->_right; 
00397                                 }
00398                                 if (p->_left->_color == c_black && p->_right->_color == c_black)
00399                                 {
00400                                         p->_color = c_red;
00401                                         x = px; 
00402                                 }
00403                                 else
00404                 {
00405                                         if (p->_right->_color == c_black)
00406                                         {
00407                                                 p->_left->_color = c_black;
00408                                                 p->_color = c_red;
00409                                                 _rrotate(p);
00410                                                 p = px->_right; 
00411                                         }
00412                                         p->_color = px->_color;
00413                                         px->_color = c_black;
00414                                         p->_right->_color = c_black;
00415                                         _lrotate(px);
00416                                         break; 
00417                                 }
00418                         }
00419                         else
00420                         {
00421                                 p = px->_left;
00422                                 if (p->_color == c_red)
00423                                 {
00424                                         p->_color = c_black;
00425                                         px->_color = c_red;
00426                                         _rrotate(px);
00427                                         p = px->_left; 
00428                                 }
00429                                 if (p->_right->_color == c_black && p->_left->_color == c_black)
00430                                 {
00431                                         p->_color = c_red;
00432                                         x = px; 
00433                                 }
00434                                 else
00435                                 {
00436                                         if (p->_left->_color == c_black)
00437                                         {
00438                                                 p->_right->_color = c_black;
00439                                                 p->_color = c_red;
00440                                                 _lrotate(p);
00441                                                 p = px->_left; 
00442                                         }
00443                                         p->_color = px->_color;
00444                                         px->_color = c_black;
00445                                         p->_left->_color = c_black;
00446                                         _rrotate(px);
00447                                         break; 
00448                                 }
00449                         }
00450                         x->_color = c_black; 
00451         }
00452         
00453         --_size;
00454         return w; 
00455 }
00456 
00457 template < class K, class T, class Pr, bool M >
00458 inline 
00459 TYPENAME base_map< K, T, Pr, M >::_node*
00460 base_map< K, T, Pr, M >::_lbound(const K& k) const
00461 {
00462         TYPENAME base_map< K, T, Pr, M >::_node* p = _head._parent;
00463         TYPENAME base_map< K, T, Pr, M >::_node* r = head();
00464         while (p->_type != t_head)
00465         if (key_compare(p->_key, k))
00466                 p = p->_right;
00467         else
00468                 r = p, p = p->_left;
00469         return r; 
00470 }
00471 
00472 template < class K, class T, class Pr, bool M >
00473 inline 
00474 TYPENAME base_map< K, T, Pr, M >::_node*
00475 base_map< K, T, Pr, M >::_ubound(const K& k) const
00476 {
00477         TYPENAME base_map< K, T, Pr, M >::_node* p = _head._parent;
00478         TYPENAME base_map< K, T, Pr, M >::_node* r = head();
00479         while (p->_type != t_head)
00480                 if (key_compare(k, p->_key))
00481                         r = p, p = p->_left;
00482                 else
00483                         p = p->_right;
00484         return r; 
00485 }
00486  
00487 template < class K, class T, class Pr, bool M >
00488 inline 
00489 TYPENAME base_map< K, T, Pr, M >::_node*&
00490 base_map< K, T, Pr, M >::lmost() 
00491 { 
00492         return _head._left; 
00493 }
00494 
00495 template < class K, class T, class Pr, bool M >
00496 inline 
00497 TYPENAME base_map< K, T, Pr, M >::_node*&
00498 base_map< K, T, Pr, M >::lmost() const 
00499 { 
00500         return head()->_left; 
00501 }
00502 
00503 template < class K, class T, class Pr, bool M >
00504 inline 
00505 TYPENAME base_map< K, T, Pr, M >::_node*&
00506 base_map< K, T, Pr, M >::rmost()
00507 { 
00508         return _head._right; 
00509 }
00510 
00511 template < class K, class T, class Pr, bool M >
00512 inline 
00513 TYPENAME base_map< K, T, Pr, M >::_node*&
00514 base_map< K, T, Pr, M >::rmost() const 
00515 { 
00516         return head()->_right; 
00517 }
00518 
00519 template < class K, class T, class Pr, bool M >
00520 inline 
00521 TYPENAME base_map< K, T, Pr, M >::_node*&
00522 base_map< K, T, Pr, M >::root() 
00523 { 
00524         return _head._parent; 
00525 }
00526 
00527 template < class K, class T, class Pr, bool M >
00528 inline 
00529 TYPENAME base_map< K, T, Pr, M >::_node*&
00530 base_map< K, T, Pr, M >::root() const 
00531 { 
00532         return head()->_parent; 
00533 }
00534 
00535 template < class K, class T, class Pr, bool M >
00536 inline 
00537 TYPENAME base_map< K, T, Pr, M >::_node*
00538 base_map< K, T, Pr, M >::head() 
00539 { 
00540         return static_cast< TYPENAME base_map< K, T, Pr, M >::_node* >(&_head); 
00541 }
00542 
00543 template < class K, class T, class Pr, bool M >
00544 inline 
00545 TYPENAME base_map< K, T, Pr, M >::_node*
00546 base_map< K, T, Pr, M >::head() const 
00547 { 
00548         return const_cast< TYPENAME base_map< K, T, Pr, M >::_node* >(static_cast< const TYPENAME base_map< K, T, Pr, M >::_node* >(&_head)); 
00549 }
00550 
00551 template < class K, class T, class Pr, bool M >
00552 inline 
00553 void
00554 base_map< K, T, Pr, M >::_lrotate(TYPENAME base_map< K, T, Pr, M >::_node* w)
00555 {
00556         TYPENAME base_map< K, T, Pr, M >::_node* p = w->_right;
00557         w->_right = p->_left;
00558         if (p->_left->_type != t_head)
00559                 p->_left->_parent = w;
00560         p->_parent = w->_parent;
00561         if (w == _head._parent)
00562                 _head._parent = p;
00563         else if (w == w->_parent->_left)
00564                 w->_parent->_left = p;
00565         else
00566                 w->_parent->_right = p;
00567         p->_left = w;
00568         w->_parent = p; 
00569 }
00570 
00571 template < class K, class T, class Pr, bool M >
00572 inline 
00573 void
00574 base_map< K, T, Pr, M >::_rrotate(TYPENAME base_map< K, T, Pr, M >::_node* w)
00575 {
00576         TYPENAME base_map< K, T, Pr, M >::_node* p = w->_left;
00577         w->_left = p->_right;
00578         if (p->_right->_type != t_head)
00579                 p->_right->_parent = w;
00580         p->_parent = w->_parent;
00581         if (w == _head._parent)
00582                 _head._parent = p;
00583         else if (w == w->_parent->_right)
00584                 w->_parent->_right = p;
00585         else
00586                 w->_parent->_left = p;
00587         p->_right = w;
00588         w->_parent = p; 
00589 }
00590 
00591 template < class K, class T, class Pr, bool M >
00592 inline 
00593 void
00594 base_map< K, T, Pr, M >::_consval(T* p, const T& v) 
00595 { 
00596         new(p) T(v); 
00597 }
00598 
00599 template < class K, class T, class Pr, bool M >
00600 inline 
00601 void
00602 base_map< K, T, Pr, M >::_conskey(K* p, const K& k) 
00603 { 
00604         new(p) K(k); 
00605 }
00606 
00607 template < class K, class T, class Pr, bool M >
00608 inline 
00609 void
00610 base_map< K, T, Pr, M >::_destval(T* p) 
00611 { 
00612         p->~T(); 
00613 }
00614 
00615 template < class K, class T, class Pr, bool M >
00616 inline 
00617 void
00618 base_map< K, T, Pr, M >::_destkey(K* p) 
00619 { 
00620         p->~K(); 
00621 }
00622 
00624 template < class K, class T, class A, class Pr, bool M >
00625 _map< K, T, A, Pr, M >::_map(const Pr& pr) : 
00626         base_map<K, T, Pr, M>(pr) 
00627 { 
00628         base_map< K, T, Pr, M >::clear(); 
00629 }
00630 
00631 template < class K, class T, class A, class Pr, bool M >
00632 _map< K, T, A, Pr, M >::~_map() 
00633 {
00634 } 
00635 
00636 template < class K, class T, class A, class Pr, bool M >
00637 _map< K, T, A, Pr, M >::_map(const _map< K, T, A, Pr, M >& x) : 
00638         base_map<K, T, Pr, M>(x) 
00639 {
00640 }
00641 
00642 template < class K, class T, class A, class Pr, bool M >
00643 inline
00644 void
00645 _map< K, T, A, Pr, M >::assign(A& allocator_, const _map< K, T, A, Pr, M >& x)
00646 { 
00647         base_map< K, T, Pr, M >::clear(); 
00648         for (TYPENAME _map< K, T, A, Pr, M >::const_iterator I = x.begin(); I != x.end(); ++I) 
00649                 insert(allocator_, I.key(), *I); 
00650 }
00651 
00652 /*
00653 template < class K, class T, class A, class Pr, bool M >
00654 inline
00655 TYPENAME _map< K, T, A, Pr, M >::iterator
00656 _map< K, T, A, Pr, M >::insert(A& allocator_, const K& k, const T& v)
00657 { 
00658         TYPENAME _map< K, T, A, Pr, M >::_node* x = this->_head._parent;
00659         TYPENAME _map< K, T, A, Pr, M >::_node* w = this->head();
00660 
00661         bool left = true;
00662         while (x->_type != t_head)
00663         {
00664                 w = x;
00665                 left = key_compare(k, x->_key);
00666                 x = left ? x->_left : x->_right; 
00667         }
00668 
00669         if (M) return _insert(allocator_, left, w, k, v);
00670         
00671         TYPENAME base_map< K, T, Pr, M >::iterator p =  TYPENAME base_map< K, T, Pr, M >::iterator(w);
00672 
00673         if (!left) 
00674                 ;
00675         else if (p == this->begin())
00676                 return _insert(allocator_, left, w, k, v);
00677         else
00678                 --p;
00679 
00680     if (key_compare(p.key(), k))
00681                 return _insert(allocator_, left, w, k, v);
00682         
00683         return p; 
00684 }
00685 */
00686 template < class K, class T, class A, class Pr, bool M >
00687 inline
00688 TYPENAME 
00689 _map< K, T, A, Pr, M >::pairib_t
00690 _map< K, T, A, Pr, M >::insert(A& allocator_, const K& k, const T& v)
00691 { 
00692         TYPENAME _map< K, T, A, Pr, M >::_node* x = this->_head._parent;
00693         TYPENAME _map< K, T, A, Pr, M >::_node* w = this->head();
00694 
00695         bool left = true;
00696         while (x->_type != t_head)
00697         {
00698                 w = x;
00699                 left = key_compare(k, x->_key);
00700                 x = left ? x->_left : x->_right; 
00701         }
00702 
00703         if (M) return TYPENAME _map< K, T, A, Pr, M >::pairib_t(_insert(allocator_, left, w, k, v), true);
00704         
00705         TYPENAME base_map< K, T, Pr, M >::iterator p =  TYPENAME base_map< K, T, Pr, M >::iterator(w);
00706 
00707         if (!left) 
00708                 ;
00709         else if (p == this->begin())
00710                 return TYPENAME _map< K, T, A, Pr, M >::pairib_t(_insert(allocator_, left, w, k, v), true);
00711         else
00712                 --p;
00713 
00714     if (key_compare(p.key(), k))
00715                 return TYPENAME _map< K, T, A, Pr, M >::pairib_t(_insert(allocator_, left, w, k, v), true);
00716         
00717         return TYPENAME _map< K, T, A, Pr, M >::pairib_t(p, false); 
00718 }
00719 
00720 template < class K, class T, class A, class Pr, bool M >
00721 inline
00722 TYPENAME 
00723 _map< K, T, A, Pr, M >::iterator
00724 _map< K, T, A, Pr, M >::erase(TYPENAME _map< K, T, A, Pr, M >::iterator p)
00725 {
00726         TYPENAME _map< K, T, A, Pr, M >::_node* e = 0;
00727         return base_map<K, T, Pr, M>::_erase(p, e);
00728 }
00729 
00730 template < class K, class T, class A, class Pr, bool M >
00731 inline 
00732 TYPENAME 
00733 _map< K, T, A, Pr, M >::iterator 
00734 _map< K, T, A, Pr, M >::erase(node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, TYPENAME _map< K, T, A, Pr, M >::iterator p)
00735 {
00736         TYPENAME _map< K, T, A, Pr, M >::_node* e = 0;
00737         TYPENAME _map< K, T, A, Pr, M >::iterator r = base_map<K, T, Pr, M>::_erase(p, e);
00738         if (e)
00739         {
00740                 _destval(&e->_value);
00741                 _destkey(&e->_key);
00742                 _freenode(allocator_, e);
00743         }
00744 
00745         return r;
00746 }
00747 
00748 template < class K, class T, class A, class Pr, bool M >
00749 inline
00750 void
00751 _map< K, T, A, Pr, M >::erase(const K& x)
00752 {
00753         if (!this->_size) 
00754                 return;
00755         TYPENAME _map< K, T, A, Pr, M >::pairii_t p = equal_range(x);
00756         erase(p.first, p.second);
00757 }
00758 
00759 template < class K, class T, class A, class Pr, bool M >
00760 inline
00761 void
00762 _map< K, T, A, Pr, M >::erase(node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, const K& x)
00763 {
00764         if (!this->_size) 
00765                 return;
00766         TYPENAME _map< K, T, A, Pr, M >::pairii_t p = equal_range(x);
00767         erase(allocator_, p.first, p.second);
00768 }
00769 
00770 template < class K, class T, class A, class Pr, bool M >
00771 inline
00772 TYPENAME _map< K, T, A, Pr, M >::iterator
00773 _map< K, T, A, Pr, M >::erase(TYPENAME _map< K, T, A, Pr, M >::iterator first, TYPENAME _map< K, T, A, Pr, M >::iterator last)
00774 {
00775         if (first == this->begin() && last == this->end())
00776         {
00777                 _erase(this->_head._parent);
00778                 base_map<K, T, Pr, M>::clear();
00779                 return this->begin(); 
00780         }
00781         else
00782         {
00783                 while (first != last) erase(first++);
00784                 return first; 
00785         }
00786 }
00787 
00788 template < class K, class T, class A, class Pr, bool M >
00789 inline
00790 TYPENAME _map< K, T, A, Pr, M >::iterator
00791 _map< K, T, A, Pr, M >::erase(node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, TYPENAME _map< K, T, A, Pr, M >::iterator first, TYPENAME _map< K, T, A, Pr, M >::iterator last)
00792 {
00793         if (first == this->begin() && last == this->end())
00794         {
00795                 _erase(allocator_, this->_head._parent);
00796                 base_map<K, T, Pr, M>::clear();
00797                 return this->begin(); 
00798         }
00799         else
00800         {
00801                 while (first != last) erase(allocator_, first++);
00802                 return first; 
00803         }
00804 }
00805 
00806 template < class K, class T, class A, class Pr, bool M >
00807 inline
00808 void
00809 _map< K, T, A, Pr, M >::_erase(TYPENAME _map< K, T, A, Pr, M >::_node* e)
00810 { 
00811         for (TYPENAME _map< K, T, A, Pr, M >::_node* p = e; p->_type != t_head; e = p)
00812         {
00813                 _erase(p->_right);
00814                 p = p->_left; 
00815         }
00816 }
00817 
00818 template < class K, class T, class A, class Pr, bool M >
00819 inline
00820 void
00821 _map< K, T, A, Pr, M >::_erase(node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, TYPENAME _map< K, T, A, Pr, M >::_node* e)
00822 { 
00823         for (TYPENAME _map< K, T, A, Pr, M >::_node* p = e; p->_type != t_head; e = p)
00824         {
00825                 _erase(allocator_, p->_right);
00826                 p = p->_left; 
00827         }
00828 }
00829 
00830 template < class K, class T, class A, class Pr, bool M >
00831 inline
00832 TYPENAME _map< K, T, A, Pr, M >::iterator
00833 _map< K, T, A, Pr, M >::_insert(A& _allocator, bool left, TYPENAME _map< K, T, A, Pr, M >::_node* w, const K& k, const T& v)
00834 { 
00835         TYPENAME _map< K, T, A, Pr, M >::_node* n = _buynode(_allocator, w, c_red, t_leaf); 
00836         if (!n)
00837                 return this->end();
00838         return base_map<K, T, Pr, M>::_insert(left, w, n, k, v); 
00839 }
00840 
00841 template < class K, class T, class A, class Pr, bool M >
00842 inline
00843 TYPENAME _map< K, T, A, Pr, M >::_node*
00844 _map< K, T, A, Pr, M >::_buynode(byte_allocator& allocator_, TYPENAME _map< K, T, A, Pr, M >::_node* p, TYPENAME _map< K, T, A, Pr, M >::redblack c, TYPENAME _map< K, T, A, Pr, M >::nodetype t)
00845 {
00846         void* ptr = allocator_.allocate(sizeof(TYPENAME _map< K, T, A, Pr, M >::_node));
00847         if (!ptr)       
00848                 return 0;
00849 
00850         TYPENAME _map< K, T, A, Pr, M >::_node* s = (TYPENAME _map< K, T, A, Pr, M >::_node*)ptr;
00851         s->_parent = p;
00852         s->_color = c;
00853         s->_type = t;
00854         s->_right = s->_left = this->head();
00855         return s; 
00856 }
00857 
00858 template < class K, class T, class A, class Pr, bool M >
00859 inline
00860 TYPENAME _map< K, T, A, Pr, M >::_node*
00861 _map< K, T, A, Pr, M >::_buynode(node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, TYPENAME _map< K, T, A, Pr, M >::_node* p, TYPENAME _map< K, T, A, Pr, M >::redblack c, TYPENAME _map< K, T, A, Pr, M >::nodetype t)
00862 {
00863         void* ptr = allocator_.allocate();
00864         if (!ptr)       
00865                 return 0;
00866         TYPENAME _map< K, T, A, Pr, M >::_node* s = (TYPENAME _map< K, T, A, Pr, M >::_node*)ptr;
00867         s->_parent = p;
00868         s->_color = c;
00869         s->_right = s->_left = this->head();
00870         s->_type = t;
00871         return s; 
00872 }
00873 
00874 template < class K, class T, class A, class Pr, bool M >
00875 inline 
00876 void 
00877 _map< K, T, A, Pr, M >::_freenode(node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& _allocator, TYPENAME _map< K, T, A, Pr, M >::_node* s)
00878 {
00879         _allocator.deallocate(s); 
00880 }
00881 
00882 
00884 template < class K, class T, class Pr, bool M >
00885 map< K, T, Pr, M >::map(const Pr& pr, size_t size) : 
00886         base_map<K, T, Pr, M>(pr), _allocator(size) 
00887 {
00888 }
00889 
00890 template < class K, class T, class Pr, bool M >
00891 map< K, T, Pr, M >::~map() 
00892 {
00893 }
00894 
00895 template < class K, class T, class Pr, bool M >
00896 map< K, T, Pr, M >::map(const map< K, T, Pr, M >& x) : 
00897         base_map<K, T, Pr, M>(x), _allocator(x._allocator.capacity()) 
00898 { 
00899         *this = x; 
00900 }
00901 
00902 template < class K, class T, class Pr, bool M >
00903 inline
00904 map< K, T, Pr, M >&
00905 map< K, T, Pr, M >::operator=(const map< K, T, Pr, M >& x)
00906 {
00907         if (&x != this)
00908         {
00909                 this->clear();
00910                 this->key_compare = x.key_compare;
00911                 // copy
00912                 for (TYPENAME map< K, T, Pr, M >::const_iterator I = x.begin(); I != x.end(); ++I)
00913                         insert(I.key(), *I);
00914         }
00915 
00916         return *this;
00917 }
00918 
00919 /*
00920 template < class K, class T, class Pr, bool M >
00921 inline
00922 TYPENAME map< K, T, Pr, M >::iterator
00923 map< K, T, Pr, M >::insert(const K& k, const T& v)
00924 { 
00925         TYPENAME map< K, T, Pr, M >::_node* x = this->_head._parent;
00926         TYPENAME map< K, T, Pr, M >::_node* w = this->head();
00927 
00928         bool left = true;
00929         while (x->_type != t_head)
00930         {
00931                 w = x;
00932                 left = key_compare(k, x->_key);
00933                 x = left ? x->_left : x->_right; 
00934         } 
00935 
00936         if (M) return _insert(left, w, k, v);
00937         
00938         TYPENAME base_map< K, T, Pr, M >::iterator p =  TYPENAME base_map< K, T, Pr, M >::iterator(w);
00939 
00940         if (!left) 
00941                 ;
00942         else if (p == this->begin())
00943                 return _insert(true, w, k, v);
00944         else
00945                 --p;
00946 
00947     if (key_compare(p.key(), k))
00948                 return _insert(left, w, k, v);
00949         
00950         return p; 
00951 }
00952 */
00953 
00954 template < class K, class T, class Pr, bool M >
00955 inline
00956 TYPENAME 
00957 map< K, T, Pr, M >::pairib_t
00958 map< K, T, Pr, M >::insert(const K& k, const T& v)
00959 { 
00960         TYPENAME map< K, T, Pr, M >::_node* x = this->_head._parent;
00961         TYPENAME map< K, T, Pr, M >::_node* w = this->head();
00962 
00963         bool left = true;
00964         while (x->_type != t_head)
00965         {
00966                 w = x;
00967                 left = key_compare(k, x->_key);
00968                 x = left ? x->_left : x->_right; 
00969         } 
00970 
00971         if (M) return TYPENAME map< K, T, Pr, M >::pairib_t(_insert(left, w, k, v), true);
00972         
00973         TYPENAME base_map< K, T, Pr, M >::iterator p =  TYPENAME base_map< K, T, Pr, M >::iterator(w);
00974 
00975         if (!left) 
00976                 ;
00977         else if (p == this->begin())
00978                 return TYPENAME map< K, T, Pr, M >::pairib_t(_insert(true, w, k, v), true);
00979         else
00980                 --p;
00981 
00982     if (key_compare(p.key(), k))
00983                 return TYPENAME map< K, T, Pr, M >::pairib_t(_insert(left, w, k, v), true);
00984         
00985         return TYPENAME map< K, T, Pr, M >::pairib_t(p, false); 
00986 }
00987 
00988 template < class K, class T, class Pr, bool M >
00989 inline
00990 TYPENAME map< K, T, Pr, M >::iterator
00991 map< K, T, Pr, M >::erase(TYPENAME map< K, T, Pr, M >::iterator p)
00992 {
00993         TYPENAME map< K, T, Pr, M >::_node* y = 0;
00994         TYPENAME map< K, T, Pr, M >::iterator r = base_map<K, T, Pr, M>::_erase(p, y);
00995         if (y)
00996         {
00997                 _destval(&y->_value);
00998                 _destkey(&y->_key);
00999                 _freenode(y);
01000         }
01001 
01002         return r;
01003 }
01004 
01005 template < class K, class T, class Pr, bool M >
01006 inline
01007 void
01008 map< K, T, Pr, M >::erase(const K& x)
01009 {
01010         if (!this->_size)
01011                 return;
01012 
01013         TYPENAME map< K, T, Pr, M >::pairii_t p = equal_range(x);
01014         erase(p.first, p.second);
01015 }
01016 
01017 // NO memory deallocation
01018 // calls only destructors
01019 template < class K, class T, class Pr, bool M >
01020 inline
01021 void
01022 map< K, T, Pr, M >::clear()
01023 { 
01024         if (!this->_size)
01025         {
01026                 _allocator.clear_all();
01027                 return;
01028         }
01029 
01030         erase(this->begin(), this->end());
01031         // clear iterator here
01032         base_map<K, T, Pr, M>::clear();
01033         _allocator.clear_all();
01034 }
01035 
01036 template < class K, class T, class Pr, bool M >
01037 inline
01038 TYPENAME map< K, T, Pr, M >::iterator
01039 map< K, T, Pr, M >::erase(TYPENAME map< K, T, Pr, M >::iterator first, TYPENAME map< K, T, Pr, M >::iterator last)
01040 {
01041         if (first == this->begin() && last == this->end())
01042         {
01043                 _erase(this->_head._parent);
01044                 base_map<K, T, Pr, M>::clear();
01045                 return this->begin(); 
01046         }
01047         else
01048         {
01049                 while (first != last) erase(first++);
01050                 return first; 
01051         }
01052 }
01053 
01054 template < class K, class T, class Pr, bool M >
01055 inline
01056 void
01057 map< K, T, Pr, M >::_erase(TYPENAME map< K, T, Pr, M >::_node* x)
01058 {
01059         for (TYPENAME map< K, T, Pr, M >::_node* y = x; y->_type != t_head; x = y)
01060         {
01061                 _erase(y->_right);
01062                 y = y->_left;
01063                 _destval(&x->_value);
01064                 _destkey(&x->_key);
01065         _freenode(x); 
01066         }
01067 }
01068 
01069 template < class K, class T, class Pr, bool M >
01070 inline
01071 TYPENAME map< K, T, Pr, M >::iterator
01072 map< K, T, Pr, M >::_insert(bool left, TYPENAME map< K, T, Pr, M >::_node* w, const K& k, const T& v)
01073 {
01074         TYPENAME map< K, T, Pr, M >::_node* n = _buynode(w, c_red, t_leaf);
01075         if (!n)
01076                 return this->end();
01077 
01078         return base_map<K, T, Pr, M>::_insert(left, w, n, k, v);
01079 }
01080     
01081 template < class K, class T, class Pr, bool M >
01082 inline
01083 TYPENAME map< K, T, Pr, M >::_node*
01084 map< K, T, Pr, M >::_buynode(TYPENAME map< K, T, Pr, M >::_node* p, TYPENAME map< K, T, Pr, M >::redblack c, TYPENAME map< K, T, Pr, M >::nodetype t)
01085 {
01086         TYPENAME map< K, T, Pr, M >::_node* s = _allocator.allocate();
01087         if (!s)
01088                 return 0;
01089         s->_parent = p;
01090         s->_color = c;
01091         s->_right = s->_left = this->head();
01092         s->_type = t;
01093         return s; 
01094 }
01095 
01096 template < class K, class T, class Pr, bool M >
01097 inline
01098 void
01099 map< K, T, Pr, M >::_freenode(TYPENAME map< K, T, Pr, M >::_node* s) 
01100 { 
01101         _allocator.deallocate(s); 
01102 }
01103 
01104 #pragma pack()
01105 END_TERIMBER_NAMESPACE
01106 
01107 #endif // _terimber_map_hpp_
01108
map.hpp
