|
|
Space-efficient geometric algorithms and data structuresBy Ilya Katz and Hervé Brönnimann |
00001 //TODO: when do we need to update header.left, header.right, header.parent in swap_nodes 00002 //TODO:is _M_header_PQ ever used? 00003 //TODO:insert unique was chnaged to allow duplicates 00004 //TODO:copy constructor 00005 //TODO:the parameter to is not prececise Val! 00006 00007 // RB tree implementation -*- C++ -*- 00008 00009 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 00010 // 00011 // This file is part of the GNU ISO C++ Library. This library is free 00012 // software; you can redistribute it and/or modify it under the 00013 // terms of the GNU General Public License as published by the 00014 // Free Software Foundation; either version 2, or (at your option) 00015 // any later version. 00016 00017 // This library is distributed in the hope that it will be useful, 00018 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00019 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00020 // GNU General Public License for more details. 00021 00022 // You should have received a copy of the GNU General Public License along 00023 // with this library; see the file COPYING. If not, write to the Free 00024 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00025 // USA. 00026 00027 // As a special exception, you may use this file as part of a free software 00028 // library without restriction. Specifically, if other files instantiate 00029 // templates or use macros or inline functions from this file, or you compile 00030 // this file and link it with other files to produce an executable, this 00031 // file does not by itself cause the resulting executable to be covered by 00032 // the GNU General Public License. This exception does not however 00033 // invalidate any other reasons why the executable file might be covered by 00034 // the GNU General Public License. 00035 00036 /* 00037 * 00038 * Copyright (c) 1996,1997 00039 * Silicon Graphics Computer Systems, Inc. 00040 * 00041 * Permission to use, copy, modify, distribute and sell this software 00042 * and its documentation for any purpose is hereby granted without fee, 00043 * provided that the above copyright notice appear in all copies and 00044 * that both that copyright notice and this permission notice appear 00045 * in supporting documentation. Silicon Graphics makes no 00046 * representations about the suitability of this software for any 00047 * purpose. It is provided "as is" without express or implied warranty. 00048 * 00049 * 00050 * Copyright (c) 1994 00051 * Hewlett-Packard Company 00052 * 00053 * Permission to use, copy, modify, distribute and sell this software 00054 * and its documentation for any purpose is hereby granted without fee, 00055 * provided that the above copyright notice appear in all copies and 00056 * that both that copyright notice and this permission notice appear 00057 * in supporting documentation. Hewlett-Packard Company makes no 00058 * representations about the suitability of this software for any 00059 * purpose. It is provided "as is" without express or implied warranty. 00060 * 00061 * 00062 */ 00063 00069 #ifndef _BLOCK_TREE_HEAP_INTERNAL_TREE_H 00070 #define _BLOCK_TREE_HEAP_INTERNAL_TREE_H 1 00071 00072 #include <bits/stl_algobase.h> 00073 #include <bits/allocator.h> 00074 #include <bits/stl_construct.h> 00075 #include <bits/stl_function.h> 00076 #include <bits/cpp_type_traits.h> 00077 00078 #include <iostream> 00079 #include <iterator> 00080 00081 //using namespace std; 00082 namespace inplaceds 00083 { 00084 namespace block 00085 { 00086 // Red-black tree class, designed for use in implementing STL 00087 // associative containers (set, multiset, map, and multimap). The 00088 // insertion and deletion algorithms are based on those in Cormen, 00089 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 00090 // 1990), except that 00091 // 00092 // (1) the header cell is maintained with links not only to the root 00093 // but also to the leftmost node of the tree, to enable constant 00094 // time begin(), and to the rightmost node of the tree, to enable 00095 // linear time performance when used with the generic set algorithms 00096 // (set_union, etc.) 00097 // 00098 // (2) when a node being deleted has two children its successor node 00099 // is relinked into its place, rather than copied, so that the only 00100 // iterators invalidated are those referring to the deleted node. 00101 00102 enum _Rb_tree_color { _S_red = false, _S_black = true }; 00103 00104 struct _Rb_tree_node_base 00105 { 00106 typedef _Rb_tree_node_base* _Base_ptr; 00107 typedef const _Rb_tree_node_base* _Const_Base_ptr; 00108 00109 _Rb_tree_color _M_color; 00110 00111 _Base_ptr _M_parent; 00112 _Base_ptr _M_left; 00113 _Base_ptr _M_right; 00114 00115 _Base_ptr _M_parent_pq; 00116 _Base_ptr _M_left_pq; 00117 _Base_ptr _M_right_pq; 00118 00120 _Base_ptr _M_prev_gap; 00121 _Base_ptr _M_next_gap; 00122 00123 00124 00125 static _Base_ptr 00126 _S_minimum(_Base_ptr __x) 00127 { 00128 while (__x->_M_left != 0) __x = __x->_M_left; 00129 return __x; 00130 } 00131 00132 static _Const_Base_ptr 00133 _S_minimum(_Const_Base_ptr __x) 00134 { 00135 while (__x->_M_left != 0) __x = __x->_M_left; 00136 return __x; 00137 } 00138 00139 static _Base_ptr 00140 _S_maximum(_Base_ptr __x) 00141 { 00142 while (__x->_M_right != 0) __x = __x->_M_right; 00143 return __x; 00144 } 00145 00146 static _Const_Base_ptr 00147 _S_maximum(_Const_Base_ptr __x) 00148 { 00149 while (__x->_M_right != 0) __x = __x->_M_right; 00150 return __x; 00151 } 00152 }; 00153 00154 template<typename _Val> 00155 struct _Rb_tree_node : public _Rb_tree_node_base 00156 { 00157 typedef _Rb_tree_node<_Val>* _Link_type; 00158 _Val _M_value_field; 00159 }; 00160 00161 _Rb_tree_node_base* 00162 _Rb_tree_increment(_Rb_tree_node_base* __x) 00163 { 00164 if (__x->_M_right != 0) 00165 { 00166 __x = __x->_M_right; 00167 while (__x->_M_left != 0) 00168 __x = __x->_M_left; 00169 } 00170 else 00171 { 00172 _Rb_tree_node_base* __y = __x->_M_parent; 00173 while (__x == __y->_M_right) 00174 { 00175 __x = __y; 00176 __y = __y->_M_parent; 00177 } 00178 if (__x->_M_right != __y) 00179 __x = __y; 00180 } 00181 return __x; 00182 } 00183 00184 const _Rb_tree_node_base* 00185 _Rb_tree_increment(const _Rb_tree_node_base* __x) 00186 { 00187 return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x)); 00188 } 00189 00190 _Rb_tree_node_base* 00191 _Rb_tree_decrement(_Rb_tree_node_base* __x) 00192 { 00193 if (__x->_M_color == _S_red 00194 && __x->_M_parent->_M_parent == __x) 00195 __x = __x->_M_right; 00196 else if (__x->_M_left != 0) 00197 { 00198 _Rb_tree_node_base* __y = __x->_M_left; 00199 while (__y->_M_right != 0) 00200 __y = __y->_M_right; 00201 __x = __y; 00202 } 00203 else 00204 { 00205 _Rb_tree_node_base* __y = __x->_M_parent; 00206 while (__x == __y->_M_left) 00207 { 00208 __x = __y; 00209 __y = __y->_M_parent; 00210 } 00211 __x = __y; 00212 } 00213 return __x; 00214 } 00215 00216 const _Rb_tree_node_base* 00217 _Rb_tree_decrement(const _Rb_tree_node_base* __x) 00218 { 00219 return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x)); 00220 } 00221 00222 template<typename _Tp> 00223 struct _Rb_tree_iterator 00224 { 00225 00226 typedef _Tp value_type; 00227 typedef _Tp& reference; 00228 typedef _Tp* pointer; 00229 00230 typedef std::bidirectional_iterator_tag iterator_category; 00231 typedef std::ptrdiff_t difference_type; 00232 00233 typedef _Rb_tree_iterator<_Tp> _Self; 00234 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 00235 typedef _Rb_tree_node<_Tp>* _Link_type; 00236 00237 _Rb_tree_iterator() 00238 : _M_node() { } 00239 00240 _Rb_tree_iterator(_Link_type __x) 00241 : _M_node(__x) { } 00242 00243 reference 00244 operator*() const 00245 { return static_cast<_Link_type>(_M_node)->_M_value_field; } 00246 00247 pointer 00248 operator->() const 00249 {return &static_cast<_Link_type>(_M_node)->_M_value_field; } 00250 00251 _Self& 00252 operator++() 00253 { 00254 _M_node = _Rb_tree_increment(_M_node); 00255 return *this; 00256 } 00257 00258 _Self 00259 operator++(int) 00260 { 00261 _Self __tmp = *this; 00262 _M_node = _Rb_tree_increment(_M_node); 00263 return __tmp; 00264 } 00265 00266 _Self& 00267 operator--() 00268 { 00269 _M_node = _Rb_tree_decrement(_M_node); 00270 return *this; 00271 } 00272 00273 _Self 00274 operator--(int) 00275 { 00276 _Self __tmp = *this; 00277 _M_node = _Rb_tree_decrement(_M_node); 00278 return __tmp; 00279 } 00280 00281 bool 00282 operator==(const _Self& __x) const 00283 { return _M_node == __x._M_node; } 00284 00285 bool 00286 operator!=(const _Self& __x) const 00287 { return _M_node != __x._M_node; } 00288 00289 _Base_ptr _M_node; 00290 }; 00291 00292 template<typename _Tp> 00293 struct _Rb_tree_const_iterator 00294 { 00295 typedef _Tp value_type; 00296 typedef const _Tp& reference; 00297 typedef const _Tp* pointer; 00298 00299 typedef _Rb_tree_iterator<_Tp> iterator; 00300 00301 typedef std::bidirectional_iterator_tag iterator_category; 00302 typedef std::ptrdiff_t difference_type; 00303 00304 typedef _Rb_tree_const_iterator<_Tp> _Self; 00305 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 00306 typedef const _Rb_tree_node<_Tp>* _Link_type; 00307 00308 _Rb_tree_const_iterator() 00309 : _M_node() { } 00310 00311 _Rb_tree_const_iterator(_Link_type __x) 00312 : _M_node(__x) { } 00313 00314 _Rb_tree_const_iterator(const iterator& __it) 00315 : _M_node(__it._M_node) { } 00316 00317 reference 00318 operator*() const 00319 { return static_cast<_Link_type>(_M_node)->_M_value_field; } 00320 00321 pointer 00322 operator->() const 00323 { return &static_cast<_Link_type>(_M_node)->_M_value_field; } 00324 00325 _Self& 00326 operator++() 00327 { 00328 _M_node = _Rb_tree_increment(_M_node); 00329 return *this; 00330 } 00331 00332 _Self 00333 operator++(int) 00334 { 00335 _Self __tmp = *this; 00336 _M_node = _Rb_tree_increment(_M_node); 00337 return __tmp; 00338 } 00339 00340 _Self& 00341 operator--() 00342 { 00343 _M_node = _Rb_tree_decrement(_M_node); 00344 return *this; 00345 } 00346 00347 _Self 00348 operator--(int) 00349 { 00350 _Self __tmp = *this; 00351 _M_node = _Rb_tree_decrement(_M_node); 00352 return __tmp; 00353 } 00354 00355 bool 00356 operator==(const _Self& __x) const 00357 { return _M_node == __x._M_node; } 00358 00359 bool 00360 operator!=(const _Self& __x) const 00361 { return _M_node != __x._M_node; } 00362 00363 _Base_ptr _M_node; 00364 }; 00365 00366 template<typename _Val> 00367 inline bool 00368 operator==(const _Rb_tree_iterator<_Val>& __x, 00369 const _Rb_tree_const_iterator<_Val>& __y) 00370 { return __x._M_node == __y._M_node; } 00371 00372 template<typename _Val> 00373 inline bool 00374 operator!=(const _Rb_tree_iterator<_Val>& __x, 00375 const _Rb_tree_const_iterator<_Val>& __y) 00376 { return __x._M_node != __y._M_node; } 00377 00378 void 00379 _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 00380 _Rb_tree_node_base*& __root) 00381 { 00382 _Rb_tree_node_base* const __y = __x->_M_right; 00383 00384 __x->_M_right = __y->_M_left; 00385 if (__y->_M_left !=0) 00386 __y->_M_left->_M_parent = __x; 00387 __y->_M_parent = __x->_M_parent; 00388 00389 if (__x == __root) 00390 __root = __y; 00391 else if (__x == __x->_M_parent->_M_left) 00392 __x->_M_parent->_M_left = __y; 00393 else 00394 __x->_M_parent->_M_right = __y; 00395 __y->_M_left = __x; 00396 __x->_M_parent = __y; 00397 } 00398 00399 void 00400 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 00401 _Rb_tree_node_base*& __root) 00402 { 00403 _Rb_tree_node_base* const __y = __x->_M_left; 00404 00405 __x->_M_left = __y->_M_right; 00406 if (__y->_M_right != 0) 00407 __y->_M_right->_M_parent = __x; 00408 __y->_M_parent = __x->_M_parent; 00409 00410 if (__x == __root) 00411 __root = __y; 00412 else if (__x == __x->_M_parent->_M_right) 00413 __x->_M_parent->_M_right = __y; 00414 else 00415 __x->_M_parent->_M_left = __y; 00416 __y->_M_right = __x; 00417 __x->_M_parent = __y; 00418 } 00419 00420 void 00421 _Rb_tree_insert_and_rebalance(const bool __insert_left, 00422 _Rb_tree_node_base* __x, 00423 _Rb_tree_node_base* __p, 00424 _Rb_tree_node_base& __header) 00425 { 00426 _Rb_tree_node_base *& __root = __header._M_parent; 00427 00428 // Initialize fields in new node to insert. 00429 __x->_M_parent = __p; 00430 __x->_M_left = 0; 00431 __x->_M_right = 0; 00432 __x->_M_color = _S_red; 00433 00434 // Insert. 00435 // Make new node child of parent and maintain root, leftmost and 00436 // rightmost nodes. 00437 // N.B. First node is always inserted left. 00438 if (__insert_left) 00439 { 00440 __p->_M_left = __x; // also makes leftmost = __x when __p == &__header 00441 00442 if (__p == &__header) 00443 { 00444 __header._M_parent = __x; 00445 __header._M_right = __x; 00446 } 00447 else if (__p == __header._M_left) 00448 __header._M_left = __x; // maintain leftmost pointing to min node 00449 } 00450 else 00451 { 00452 __p->_M_right = __x; 00453 00454 if (__p == __header._M_right) 00455 __header._M_right = __x; // maintain rightmost pointing to max node 00456 } 00457 // Rebalance. 00458 while (__x != __root 00459 && __x->_M_parent->_M_color == _S_red) 00460 { 00461 _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent; 00462 00463 if (__x->_M_parent == __xpp->_M_left) 00464 { 00465 _Rb_tree_node_base* const __y = __xpp->_M_right; 00466 if (__y && __y->_M_color == _S_red) 00467 { 00468 __x->_M_parent->_M_color = _S_black; 00469 __y->_M_color = _S_black; 00470 __xpp->_M_color = _S_red; 00471 __x = __xpp; 00472 } 00473 else 00474 { 00475 if (__x == __x->_M_parent->_M_right) 00476 { 00477 __x = __x->_M_parent; 00478 _Rb_tree_rotate_left(__x, __root); 00479 } 00480 __x->_M_parent->_M_color = _S_black; 00481 __xpp->_M_color = _S_red; 00482 _Rb_tree_rotate_right(__xpp, __root); 00483 } 00484 } 00485 else 00486 { 00487 _Rb_tree_node_base* const __y = __xpp->_M_left; 00488 if (__y && __y->_M_color == _S_red) 00489 { 00490 __x->_M_parent->_M_color = _S_black; 00491 __y->_M_color = _S_black; 00492 __xpp->_M_color = _S_red; 00493 __x = __xpp; 00494 } 00495 else 00496 { 00497 if (__x == __x->_M_parent->_M_left) 00498 { 00499 __x = __x->_M_parent; 00500 _Rb_tree_rotate_right(__x, __root); 00501 } 00502 __x->_M_parent->_M_color = _S_black; 00503 __xpp->_M_color = _S_red; 00504 _Rb_tree_rotate_left(__xpp, __root); 00505 } 00506 } 00507 } 00508 __root->_M_color = _S_black; 00509 } 00510 00511 _Rb_tree_node_base* 00512 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 00513 _Rb_tree_node_base& __header) 00514 { 00515 _Rb_tree_node_base *& __root = __header._M_parent; 00516 _Rb_tree_node_base *& __leftmost = __header._M_left; 00517 _Rb_tree_node_base *& __rightmost = __header._M_right; 00518 _Rb_tree_node_base* __y = __z; 00519 _Rb_tree_node_base* __x = 0; 00520 _Rb_tree_node_base* __x_parent = 0; 00521 00522 if (__y->_M_left == 0) // __z has at most one non-null child. y == z. 00523 __x = __y->_M_right; // __x might be null. 00524 else 00525 if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. 00526 __x = __y->_M_left; // __x is not null. 00527 else 00528 { 00529 // __z has two non-null children. Set __y to 00530 __y = __y->_M_right; // __z's successor. __x might be null. 00531 while (__y->_M_left != 0) 00532 __y = __y->_M_left; 00533 __x = __y->_M_right; 00534 } 00535 if (__y != __z) 00536 { 00537 // relink y in place of z. y is z's successor 00538 __z->_M_left->_M_parent = __y; 00539 __y->_M_left = __z->_M_left; 00540 if (__y != __z->_M_right) 00541 { 00542 __x_parent = __y->_M_parent; 00543 if (__x) __x->_M_parent = __y->_M_parent; 00544 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left 00545 __y->_M_right = __z->_M_right; 00546 __z->_M_right->_M_parent = __y; 00547 } 00548 else 00549 __x_parent = __y; 00550 if (__root == __z) 00551 __root = __y; 00552 else if (__z->_M_parent->_M_left == __z) 00553 __z->_M_parent->_M_left = __y; 00554 else 00555 __z->_M_parent->_M_right = __y; 00556 __y->_M_parent = __z->_M_parent; 00557 std::swap(__y->_M_color, __z->_M_color); 00558 __y = __z; 00559 // __y now points to node to be actually deleted 00560 } 00561 else 00562 { // __y == __z 00563 __x_parent = __y->_M_parent; 00564 if (__x) 00565 __x->_M_parent = __y->_M_parent; 00566 if (__root == __z) 00567 __root = __x; 00568 else 00569 if (__z->_M_parent->_M_left == __z) 00570 __z->_M_parent->_M_left = __x; 00571 else 00572 __z->_M_parent->_M_right = __x; 00573 if (__leftmost == __z) 00574 if (__z->_M_right == 0) // __z->_M_left must be null also 00575 __leftmost = __z->_M_parent; 00576 // makes __leftmost == _M_header if __z == __root 00577 else 00578 __leftmost = _Rb_tree_node_base::_S_minimum(__x); 00579 if (__rightmost == __z) 00580 if (__z->_M_left == 0) // __z->_M_right must be null also 00581 __rightmost = __z->_M_parent; 00582 // makes __rightmost == _M_header if __z == __root 00583 else // __x == __z->_M_left 00584 __rightmost = _Rb_tree_node_base::_S_maximum(__x); 00585 } 00586 if (__y->_M_color != _S_red) 00587 { 00588 while (__x != __root && (__x == 0 || __x->_M_color == _S_black)) 00589 if (__x == __x_parent->_M_left) 00590 { 00591 _Rb_tree_node_base* __w = __x_parent->_M_right; 00592 if (__w->_M_color == _S_red) 00593 { 00594 __w->_M_color = _S_black; 00595 __x_parent->_M_color = _S_red; 00596 _Rb_tree_rotate_left(__x_parent, __root); 00597 __w = __x_parent->_M_right; 00598 } 00599 if ((__w->_M_left == 0 || 00600 __w->_M_left->_M_color == _S_black) && 00601 (__w->_M_right == 0 || 00602 __w->_M_right->_M_color == _S_black)) 00603 { 00604 __w->_M_color = _S_red; 00605 __x = __x_parent; 00606 __x_parent = __x_parent->_M_parent; 00607 } 00608 else 00609 { 00610 if (__w->_M_right == 0 00611 || __w->_M_right->_M_color == _S_black) 00612 { 00613 __w->_M_left->_M_color = _S_black; 00614 __w->_M_color = _S_red; 00615 _Rb_tree_rotate_right(__w, __root); 00616 __w = __x_parent->_M_right; 00617 } 00618 __w->_M_color = __x_parent->_M_color; 00619 __x_parent->_M_color = _S_black; 00620 if (__w->_M_right) 00621 __w->_M_right->_M_color = _S_black; 00622 _Rb_tree_rotate_left(__x_parent, __root); 00623 break; 00624 } 00625 } 00626 else 00627 { 00628 // same as above, with _M_right <-> _M_left. 00629 _Rb_tree_node_base* __w = __x_parent->_M_left; 00630 if (__w->_M_color == _S_red) 00631 { 00632 __w->_M_color = _S_black; 00633 __x_parent->_M_color = _S_red; 00634 _Rb_tree_rotate_right(__x_parent, __root); 00635 __w = __x_parent->_M_left; 00636 } 00637 if ((__w->_M_right == 0 || 00638 __w->_M_right->_M_color == _S_black) && 00639 (__w->_M_left == 0 || 00640 __w->_M_left->_M_color == _S_black)) 00641 { 00642 __w->_M_color = _S_red; 00643 __x = __x_parent; 00644 __x_parent = __x_parent->_M_parent; 00645 } 00646 else 00647 { 00648 if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black) 00649 { 00650 __w->_M_right->_M_color = _S_black; 00651 __w->_M_color = _S_red; 00652 _Rb_tree_rotate_left(__w, __root); 00653 __w = __x_parent->_M_left; 00654 } 00655 __w->_M_color = __x_parent->_M_color; 00656 __x_parent->_M_color = _S_black; 00657 if (__w->_M_left) 00658 __w->_M_left->_M_color = _S_black; 00659 _Rb_tree_rotate_right(__x_parent, __root); 00660 break; 00661 } 00662 } 00663 if (__x) __x->_M_color = _S_black; 00664 } 00665 return __y; 00666 } 00667 00668 00669 template<typename _Key, typename _Val, typename _KeyOfValue, 00670 typename _Compare, typename _Compare_PQ , typename _Alloc = std::allocator<_Val> > 00671 class _Rb_tree 00672 { 00673 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other 00674 _Node_allocator; 00675 00676 protected: 00677 typedef _Rb_tree_node_base* _Base_ptr; 00678 typedef const _Rb_tree_node_base* _Const_Base_ptr; 00679 typedef _Rb_tree_node<_Val> _Rb_tree_node; 00680 00681 public: 00682 typedef _Key key_type; 00683 typedef _Val value_type; 00684 typedef value_type* pointer; 00685 typedef const value_type* const_pointer; 00686 typedef value_type& reference; 00687 typedef const value_type& const_reference; 00688 typedef _Rb_tree_node* _Link_type; 00689 typedef const _Rb_tree_node* _Const_Link_type; 00690 typedef size_t size_type; 00691 typedef ptrdiff_t difference_type; 00692 typedef _Alloc allocator_type; 00693 00694 allocator_type 00695 get_allocator() const 00696 { return *static_cast<const _Node_allocator*>(&this->_M_impl); } 00697 00698 protected: 00699 _Rb_tree_node* 00700 _M_get_node() 00701 { return _M_impl._Node_allocator::allocate(1); } 00702 00703 void 00704 _M_put_node(_Rb_tree_node* __p) 00705 { _M_impl._Node_allocator::deallocate(__p, 1); } 00706 00707 template <class Iter> 00708 _Link_type 00709 _M_create_node(const Iter& __x) 00710 { 00711 _Link_type __tmp = _M_get_node(); 00712 __tmp->_M_left_pq = 0; 00713 __tmp->_M_right_pq = 0; 00714 __tmp->_M_parent_pq = 0; 00715 try 00716 { std::_Construct(&__tmp->_M_value_field, __x); } 00717 catch(...) 00718 { 00719 _M_put_node(__tmp); 00720 __throw_exception_again; 00721 } 00722 return __tmp; 00723 } 00724 00725 _Link_type 00726 _M_clone_node(_Const_Link_type __x) 00727 { 00728 _Link_type __tmp = _M_create_node(__x->_M_value_field); 00729 __tmp->_M_color = __x->_M_color; 00730 __tmp->_M_left = 0; 00731 __tmp->_M_right = 0; 00732 __tmp->_M_left_pq = 0; 00733 __tmp->_M_right_pq = 0; 00734 return __tmp; 00735 } 00736 00737 void 00738 destroy_node(_Link_type __p) 00739 { 00740 /* (__p->_M_value_field)[0][0]=-99; 00741 (__p->_M_value_field)[0][1]=-99; 00742 (__p->_M_value_field)[1][0]=-99; 00743 (__p->_M_value_field)[1][1]=-99; 00744 */ 00745 // (__p->_M_value_field).line[0][0]=-99; 00746 // (__p->_M_value_field).line[0][1]=-99; 00747 // (__p->_M_value_field).line[1][0]=-99; 00748 // (__p->_M_value_field).line[1][1]=-99; 00749 00750 std::_Destroy(&__p->_M_value_field); 00751 _M_put_node(__p); 00752 } 00753 00754 protected: 00755 template<typename _Key_compare, 00756 typename _Key_compare_pq = _Key_compare, 00757 bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type 00758 > 00759 struct _Rb_tree_impl : public _Node_allocator 00760 { 00761 _Key_compare _M_key_compare; 00762 _Key_compare_pq _M_key_compare_pq; 00763 00764 00765 _Rb_tree_node_base _M_header; 00766 _Base_ptr _M_header_PQ; 00767 00768 size_type _M_node_count; // Keeps track of size of tree. 00769 00770 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), 00771 const _Key_compare& __comp = _Key_compare(), 00772 const _Key_compare_pq& __comp_pq = _Key_compare_pq()) 00773 : _Node_allocator(__a), _M_key_compare(__comp), 00774 _M_key_compare_pq(__comp_pq), _M_node_count(0) 00775 { 00776 this->_M_header._M_color = _S_red; 00777 this->_M_header._M_parent = 0; 00778 this->_M_header._M_left = &this->_M_header; 00779 this->_M_header._M_right = &this->_M_header; 00780 00781 this->_M_header._M_left_pq=0; 00782 this->_M_header._M_right_pq=0; 00783 this->_M_header._M_parent_pq = 0; 00784 00785 _M_header_PQ = 0; 00786 ; 00787 } 00788 }; 00789 00790 // Specialization for _Comparison types that are not capable of 00791 // being base classes / super classes. 00792 template<typename _Key_compare, typename _Key_compare_pq> 00793 struct _Rb_tree_impl<_Key_compare, _Key_compare_pq ,true> : public _Node_allocator 00794 { 00795 _Key_compare _M_key_compare; 00796 _Key_compare_pq _M_key_compare_pq; 00797 00798 _Rb_tree_node_base _M_header; 00799 _Rb_tree_node_base _M_header_PQ; 00800 00801 size_type _M_node_count; // Keeps track of size of tree. 00802 00803 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), 00804 const _Key_compare& __comp = _Key_compare(), 00805 const _Key_compare& __comp_pq = _Key_compare_pq()) 00806 : _Node_allocator(__a), _M_key_compare(__comp), 00807 _M_key_compare_pq(__comp_pq),_M_node_count(0) 00808 { 00809 this->_M_header._M_color = _S_red; 00810 this->_M_header._M_parent = 0; 00811 this->_M_header._M_left = &this->_M_header; 00812 this->_M_header._M_right = &this->_M_header; 00813 00814 this->_M_header._M_left_pq=0; 00815 this->_M_header._M_right_pq=0; 00816 this->_M_header._M_parent_pq = 0; 00817 00818 _M_header_PQ = 0; 00819 } 00820 }; 00821 00822 _Rb_tree_impl<_Compare, _Compare_PQ> _M_impl; 00823 00824 protected: 00825 _Base_ptr& 00826 _M_root() 00827 { return this->_M_impl._M_header._M_parent; } 00828 00829 _Const_Base_ptr 00830 _M_root() const 00831 { return this->_M_impl._M_header._M_parent; } 00832 00833 _Base_ptr& 00834 _M_leftmost() 00835 { return this->_M_impl._M_header._M_left; } 00836 00837 _Const_Base_ptr 00838 _M_leftmost() const 00839 { return this->_M_impl._M_header._M_left; } 00840 00841 _Base_ptr& 00842 _M_rightmost() 00843 { return this->_M_impl._M_header._M_right; } 00844 00845 _Const_Base_ptr 00846 _M_rightmost() const 00847 { return this->_M_impl._M_header._M_right; } 00848 00849 _Link_type 00850 _M_begin() 00851 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 00852 00853 _Const_Link_type 00854 _M_begin() const 00855 { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_parent); } 00856 00857 _Link_type 00858 _M_begin_PQ() 00859 { return static_cast<_Link_type>(this->_M_impl._M_header_PQ); } 00860 00861 _Const_Link_type 00862 _M_begin_PQ() const 00863 { return static_cast<_Const_Link_type>(this->_M_impl._M_header_PQ); } 00864 00865 _Link_type 00866 _M_end() 00867 { return static_cast<_Link_type>(&this->_M_impl._M_header); } 00868 00869 _Const_Link_type 00870 _M_end() const 00871 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 00872 00873 static const_reference 00874 _S_value(_Const_Link_type __x) 00875 { return __x->_M_value_field; } 00876 00877 static const _Key& 00878 _S_key(_Const_Link_type __x) 00879 { return _KeyOfValue()(_S_value(__x)); } 00880 00881 static _Link_type 00882 _S_left(_Base_ptr __x) 00883 { return static_cast<_Link_type>(__x->_M_left); } 00884 00885 static _Const_Link_type 00886 _S_left(_Const_Base_ptr __x) 00887 { return static_cast<_Const_Link_type>(__x->_M_left); } 00888 00889 static _Link_type 00890 _S_right(_Base_ptr __x) 00891 { return static_cast<_Link_type>(__x->_M_right); } 00892 00893 static _Const_Link_type 00894 _S_right(_Const_Base_ptr __x) 00895 { return static_cast<_Const_Link_type>(__x->_M_right); } 00896 00897 static const_reference 00898 _S_value(_Const_Base_ptr __x) 00899 { return static_cast<_Const_Link_type>(__x)->_M_value_field; } 00900 00901 static const _Key& 00902 _S_key(_Const_Base_ptr __x) 00903 { return _KeyOfValue()(_S_value(__x)); } 00904 00905 static _Base_ptr 00906 _S_minimum(_Base_ptr __x) 00907 { return _Rb_tree_node_base::_S_minimum(__x); } 00908 00909 static _Const_Base_ptr 00910 _S_minimum(_Const_Base_ptr __x) 00911 { return _Rb_tree_node_base::_S_minimum(__x); } 00912 00913 static _Base_ptr 00914 _S_maximum(_Base_ptr __x) 00915 { return _Rb_tree_node_base::_S_maximum(__x); } 00916 00917 static _Const_Base_ptr 00918 _S_maximum(_Const_Base_ptr __x) 00919 { return _Rb_tree_node_base::_S_maximum(__x); } 00920 00921 public: 00922 typedef _Rb_tree_iterator<value_type> iterator; 00923 typedef _Rb_tree_const_iterator<value_type> const_iterator; 00924 00925 typedef std::reverse_iterator<iterator> reverse_iterator; 00926 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00927 00928 private: 00929 iterator 00930 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 00931 00938 _Link_type 00939 _M_copy(_Const_Link_type __x, _Link_type __p); 00940 00941 void 00942 _M_erase(_Link_type __x); 00943 00944 public: 00945 // allocation/deallocation 00946 _Rb_tree() 00947 { } 00948 00949 _Rb_tree(const _Compare& __comp, const _Compare_PQ& __comp_pq) 00950 : _M_impl(allocator_type(), __comp, __comp_pq) 00951 { } 00952 00953 _Rb_tree(const _Compare& __comp, const _Compare_PQ& __comp_pq, const allocator_type& __a) 00954 : _M_impl(__a, __comp, __comp_pq) 00955 { } 00956 00957 _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x) 00958 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare, __x._M_impl._M_key_compare_pq) 00959 { 00960 if (__x._M_root() != 0) 00961 { 00962 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00963 _M_leftmost() = _S_minimum(_M_root()); 00964 _M_rightmost() = _S_maximum(_M_root()); 00965 _M_impl._M_node_count = __x._M_impl._M_node_count; 00966 } 00967 } 00968 00969 ~_Rb_tree() 00970 { _M_erase(_M_begin()); } 00971 00972 //------------------------------------------------------------------- 00973 00975 #define DEFINE_POINTER_MAP( name, m_pointer ) \ 00976 struct name { \ 00977 _Base_ptr& operator[](_Base_ptr t) const { return (*t).m_pointer; } \ 00978 }; 00979 00980 00981 DEFINE_POINTER_MAP(PQ_leftPointer, _M_left_pq) 00982 DEFINE_POINTER_MAP(PQ_rightPointer, _M_right_pq) 00983 DEFINE_POINTER_MAP(PQ_parentPointer, _M_parent_pq) 00984 00985 DEFINE_POINTER_MAP(BST_leftPointer, _M_left) 00986 DEFINE_POINTER_MAP(BST_rightPointer, _M_right) 00987 DEFINE_POINTER_MAP(BST_parentPointer, _M_parent) 00988 00989 DEFINE_POINTER_MAP(GAP_next, _M_next_gap) 00990 DEFINE_POINTER_MAP(GAP_prev, _M_prev_gap) 00991 #undef DEFINE_POINTER_MAP 00993 00994 typedef BST_leftPointer leftBSTptr; 00995 typedef BST_rightPointer rightBSTptr; 00996 typedef BST_parentPointer parentBSTptr; 00997 00998 typedef PQ_leftPointer leftPQptr; 00999 typedef PQ_rightPointer rightPQptr; 01000 typedef PQ_parentPointer parentPQptr; 01001 01002 01003 01004 rightBSTptr right; 01005 leftBSTptr left; 01006 parentBSTptr parent; 01007 01008 rightPQptr rightPQ; 01009 leftPQptr leftPQ; 01010 parentPQptr parentPQ; 01011 01012 GAP_next nextGap; 01013 GAP_prev prevGap; 01018 void print(iterator it) 01019 { 01020 } 01021 01022 01023 01024 void preOrderPQ(_Base_ptr root) 01025 { 01026 std::cout<<*(_S_value(root).line); 01027 // <<" l:"; 01028 // if(leftPQ[root]!=NULL) 01029 // std::cout<<_S_value(leftPQ[root]).line[0][0]; 01030 // else 01031 // std::cout<<0; 01032 // std::cout<<" r:"; 01033 // if(rightPQ[root]!=NULL) 01034 // std::cout<<_S_value(rightPQ[root]).line[0][0]; 01035 // else 01036 // std::cout<<0; 01037 // std::cout<<" p:"; 01038 // if(parentPQ[root]!=NULL) 01039 // std::cout<<_S_value(parentPQ[root]).line[0][0]; 01040 // else 01041 // std::cout<<"0"; 01042 std::cout<<std::endl; 01043 if(leftPQ[root]!=0) 01044 preOrderPQ(leftPQ[root]); 01045 if(rightPQ[root]!=0) 01046 preOrderPQ(rightPQ[root]); 01047 } 01048 01049 void preOrder(_Base_ptr root) 01050 { 01051 std::cout<<*(_S_value(root).line) 01052 <<" "<<(_S_value(root).point) 01053 <<endl; 01054 /* <<" l:"; 01055 if(left[root]!=NULL) 01056 std::cout<<_S_value(left[root]).line[0][0]; 01057 else 01058 std::cout<<0; 01059 std::cout<<" r:"; 01060 if(right[root]!=NULL) 01061 std::cout<<_S_value(right[root]).line[0][0]; 01062 else 01063 std::cout<<"0"; 01064 std::cout<<" p:"; 01065 if(root!=_M_root()) 01066 std::cout<<_S_value(parent[root]).line[0][0]; 01067 else 01068 std::cout<<"0"; 01069 std::cout<<std::endl; 01070 */ if(left[root]!=0) 01071 preOrder(left[root]); 01072 if(right[root]!=0) 01073 preOrder(right[root]); 01074 } 01075 01079 iterator PQ_insert(const iterator & __x) 01080 { 01081 return iterator(static_cast<_Link_type>(PQ_insert( __x._M_node))); 01082 } 01083 01084 01085 //TODO: make call by reference 01089 void set_gap_next( iterator x, iterator y) 01090 { 01091 nextGap[x._M_node]=y._M_node; 01092 } 01093 01094 iterator get_gap_next(iterator x) 01095 { 01096 return iterator(static_cast<_Link_type>(nextGap[x._M_node])); 01097 } 01098 01099 void set_gap_prev( iterator x, iterator y) 01100 { 01101 prevGap[x._M_node]=y._M_node; 01102 } 01103 01104 iterator get_gap_prev(const iterator x) 01105 { 01106 return iterator(static_cast<_Link_type>(prevGap[x._M_node])); 01107 } 01108 01109 void swap_gap_next(iterator x, iterator y) 01110 { 01111 //TODO:if these are adjucent, is there a problem? 01112 std::swap(nextGap[x._M_node], nextGap[y._M_node]); 01113 if(nextGap[x._M_node]==x._M_node) 01114 { 01115 nextGap[x._M_node]=y._M_node; 01116 } 01117 if(nextGap[y._M_node]==y._M_node) 01118 { 01119 nextGap[y._M_node]=x._M_node; 01120 } 01121 } 01122 01123 void swap_gap_prev(iterator x, iterator y) 01124 { 01125 std::swap(prevGap[x._M_node], prevGap[y._M_node]); 01126 if(prevGap[x._M_node]==x._M_node) 01127 { 01128 prevGap[x._M_node]=y._M_node; 01129 } 01130 if(prevGap[y._M_node]==y._M_node) 01131 { 01132 prevGap[y._M_node]=x._M_node; 01133 } 01134 } 01138 _Base_ptr 01139 PQ_insert(_Base_ptr newNode) 01140 { 01141 if(_M_impl._M_header_PQ == NULL){ 01142 _M_impl._M_header_PQ = newNode; 01143 leftPQ[_M_impl._M_header_PQ]=NULL; 01144 rightPQ[_M_impl._M_header_PQ]=NULL; 01145 return newNode; 01146 } 01147 01148 _Base_ptr hole = this->_M_impl._M_header_PQ; 01149 while(_M_impl._M_key_compare_pq(_S_key(hole), _S_key(newNode) )){ 01150 01151 if(leftPQ[hole] == NULL){ 01152 leftPQ[hole]= newNode; 01153 parentPQ[newNode] = hole; 01154 return leftPQ[hole]; 01155 01156 } 01157 if(rightPQ[hole] == NULL){ 01158 rightPQ[hole] = newNode; 01159 parentPQ[newNode] = hole; 01160 return rightPQ[hole]; 01161 } 01162 hole = _M_impl._M_key_compare_pq(_S_key(rightPQ[hole]), _S_key(leftPQ[hole]))? 01163 leftPQ[hole]: 01164 rightPQ[hole]; 01165 } 01166 01167 if(hole==_M_impl._M_header_PQ){ 01168 _M_impl._M_header_PQ=newNode; 01169 leftPQ[newNode]=hole; 01170 parentPQ[hole]=newNode; 01171 return newNode; 01172 } 01173 if(leftPQ[parentPQ[hole]] == hole){ 01174 leftPQ[parentPQ[hole]]=newNode; 01175 } 01176 else{ 01177 rightPQ[parentPQ[hole]]=newNode; 01178 } 01179 01180 parentPQ[newNode]=parentPQ[hole]; 01181 parentPQ[hole]=newNode; 01182 leftPQ[newNode]=hole; 01183 rightPQ[newNode]=NULL; 01184 return newNode; 01185 } 01186 01187 iterator 01188 get_top() const 01189 {iterator(static_cast<_Link_type>(_M_impl._M_header_PQ));} 01190 01191 01196 void 01197 _M_swap_nodes(_Base_ptr a, _Base_ptr b) 01198 { 01199 _Base_ptr root_parent = parent[_M_root()]; 01200 std::swap(left[a],left[b]); 01201 std::swap(right[a],right[b]); 01202 std::swap(parent[a],parent[b]); 01203 std::swap(a->_M_color, b->_M_color); 01204 01205 // cerr<<"left[h] = "<<_M_impl._M_header._M_left<<endl; 01206 // cerr<<"right[h] = "<<_M_impl._M_header._M_right<<endl; 01207 01208 //if b is not the root 01209 if(parent[b]!=root_parent) 01210 { 01211 if(parent[b]==b) 01212 { 01213 parent[b]=a; 01214 } 01215 if(left[parent[b]]==a) 01216 { 01217 left[parent[b]]=b; 01218 } 01219 else 01220 { 01221 right[parent[b]]=b; 01222 } 01223 } 01224 else //set the root to be b 01225 { 01226 _M_root()=b; 01227 } 01228 01229 //if a is not the root 01230 if(parent[a]!=root_parent) 01231 { 01232 if(parent[a]==a) 01233 { 01234 parent[a]=b; 01235 } 01236 if(left[parent[a]]==b) 01237 { 01238 left[parent[a]]=a; 01239 } 01240 else 01241 { 01242 right[parent[a]]=a; 01243 } 01244 01245 } 01246 else 01247 { 01248 _M_root()=a; 01249 } 01250 01251 01252 if(left[a]!=NULL) 01253 { 01254 if(left[a]==a) 01255 { 01256 left[a]=b; 01257 } 01258 parent[left[a]]=a; 01259 } 01260 01261 01262 if(right[a]!=NULL) 01263 { 01264 if(right[a]==a) 01265 { 01266 right[a]=b; 01267 } 01268 parent[right[a]]=a; 01269 } 01270 01271 if(_M_leftmost()==a) 01272 { 01273 _M_leftmost()=b; 01274 } 01275 else if(_M_leftmost()==b) 01276 { 01277 _M_leftmost()=a; 01278 } 01279 else if(_M_rightmost()==a) 01280 { 01281 _M_rightmost()=b; 01282 } 01283 else if(_M_rightmost()==b) 01284 { 01285 _M_rightmost()=a; 01286 } 01287 01288 if(left[b]!=NULL) 01289 { 01290 if(left[b]==b) 01291 { 01292 left[b]=a; 01293 } 01294 parent[left[b]]=b; 01295 } 01296 if(right[b]!=NULL) 01297 { 01298 if(right[b]==b) 01299 { 01300 right[b]=a; 01301 } 01302 parent[right[b]]=b; 01303 } 01304 } 01305 01311 inline 01312 void segment_right_event(_Base_ptr it) 01313 { 01314 static_cast<_Link_type>(it)->_M_value_field.right_event(); 01315 adjust_PQ(it); 01316 } 01317 01318 template<class point_type> 01319 inline 01320 void segment_intersection_event (_Base_ptr it, point_type point, _Base_ptr intersecting) 01321 { 01322 static_cast<_Link_type>(it)->_M_value_field.intersection_event(point, 01323 &((static_cast<_Link_type>(intersecting))->_M_value_field) ); 01324 adjust_PQ(it); 01325 } 01326 01333 inline void 01334 adjust_PQ(_Base_ptr node) 01335 { 01336 percolate_down(node); 01337 percolate_up(node); 01338 } 01339 01340 inline void 01341 adjust_PQ(iterator it) 01342 { 01343 adjust_PQ(it._M_node); 01344 } 01345 01346 01351 void 01352 percolate_down(_Base_ptr node) 01353 { 01354 _Base_ptr hole=node; 01355 01356 while(true) 01357 { 01358 if(leftPQ[hole]==NULL) 01359 { 01360 if(rightPQ[hole]!=NULL)//only right child 01361 { 01362 if(_M_impl._M_key_compare_pq(_S_key(rightPQ[hole]), _S_key(hole))) 01363 { 01364 update_node(hole, rightPQ[hole]); 01365 } 01366 else break; 01367 } 01368 else break; //no children 01369 } 01370 else if(rightPQ[hole]==NULL) 01371 { 01372 if(leftPQ[hole]!=NULL)//only left child 01373 { 01374 if(_M_impl._M_key_compare_pq(_S_key(leftPQ[hole]), _S_key(hole))) 01375 { 01376 update_node(hole, leftPQ[hole]); 01377 } 01378 else break; 01379 } 01380 } 01381 else //both children 01382 { 01383 //choose the smaller one 01384 if(_M_impl._M_key_compare_pq(_S_key(leftPQ[hole]), _S_key(rightPQ[hole]))) 01385 { 01386 if(_M_impl._M_key_compare_pq(_S_key(leftPQ[hole]), _S_key(hole))) 01387 { 01388 // cerr<<"**Switching :"<<_S_key(hole)<<" "<<_S_key(leftPQ[hole])<<" "<<endl; 01389 update_node(hole, leftPQ[hole]); 01390 } 01391 else break; 01392 } 01393 else 01394 { 01395 if(_M_impl._M_key_compare_pq(_S_key(rightPQ[hole]), _S_key(hole))) 01396 { 01397 // cerr<<"**Switching :"<<_S_key(hole)<<" "<<_S_key(leftPQ[hole])<<" "<<endl; 01398 update_node(hole, rightPQ[hole]); 01399 } 01400 else break; 01401 } 01402 } 01403 } 01404 01405 } 01406 01411 void 01412 percolate_up(_Base_ptr node) 01413 { 01414 _Base_ptr hole = node; 01415 while(parentPQ[hole]!=NULL) 01416 { 01417 if(_M_impl._M_key_compare_pq(_S_value(hole), _S_value(parentPQ[hole]))) 01418 // if(PQcomp(data[hole],data[parentPQ[hole]])) 01419 { 01420 update_node(parentPQ[hole],hole); 01421 } 01422 else 01423 { 01424 break; 01425 } 01426 } 01427 } 01428 01429 01430 01431 //------------------------------------------------------------------- 01432 01433 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& 01434 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x); 01435 01436 // Accessors. 01437 _Compare 01438 key_comp() const 01439 { return _M_impl._M_key_compare; } 01440 01441 iterator 01442 begin() 01443 { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); } 01444 01445 const_iterator 01446 begin() const 01447 { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); } 01448 01449 iterator 01450 end() 01451 { return static_cast<_Link_type>(&this->_M_impl._M_header); } 01452 01453 /* const_iterator 01454 end() const 01455 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 01456 */ 01457 reverse_iterator 01458 rbegin() 01459 { return reverse_iterator(end()); } 01460 01461 const_reverse_iterator 01462 rbegin() const 01463 { return const_reverse_iterator(end()); } 01464 01465 reverse_iterator 01466 rend() 01467 { return reverse_iterator(begin()); } 01468 01469 const_reverse_iterator 01470 rend() const 01471 { return const_reverse_iterator(begin()); } 01472 01473 bool 01474 empty() const 01475 { return _M_impl._M_header_PQ == 0;} 01476 01477 size_type 01478 size() const 01479 { return _M_impl._M_node_count; } 01480 01481 size_type 01482 max_size() const 01483 { return size_type(-1); } 01484 01485 void 01486 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __t); 01487 01488 // Insert/erase. 01489 std::pair<iterator,bool> 01490 insert_unique(const value_type& __x); 01491 01492 void 01493 erase(_Base_ptr __position); 01494 01500 _Base_ptr 01501 erase_top_PQ(); 01502 01509 _Base_ptr 01510 _M_erase_PQ(_Base_ptr __position); 01511 01516 inline void 01517 update_node(_Base_ptr __position, _Base_ptr __position1); 01518 01519 01520 size_type 01521 erase(const key_type& __x); 01522 01523 void 01524 erase(iterator __first, iterator __last); 01525 01526 void 01527 erase(const key_type* __first, const key_type* __last); 01528 01529 void 01530 clear() 01531 { 01532 _M_erase(_M_begin()); 01533 _M_leftmost() = _M_end(); 01534 _M_root() = 0; 01535 _M_rightmost() = _M_end(); 01536 _M_impl._M_node_count = 0; 01537 } 01538 01539 // Set operations. 01540 iterator 01541 find(const key_type& __x); 01542 01543 const_iterator 01544 find(const key_type& __x) const; 01545 01546 size_type 01547 count(const key_type& __x) const; 01548 01549 // Debugging. 01550 bool 01551 __rb_verify() const; 01552 }; 01553 01554 template<typename _Key, typename _Val, typename _KeyOfValue, 01555 typename _Compare , typename _Compare_PQ, typename _Alloc> 01556 inline bool 01557 operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x, 01558 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __y) 01559 { 01560 return __x.size() == __y.size() 01561 && std::equal(__x.begin(), __x.end(), __y.begin()); 01562 } 01563 01564 template<typename _Key, typename _Val, typename _KeyOfValue, 01565 typename _Compare , typename _Compare_PQ, typename _Alloc> 01566 inline bool 01567 operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x, 01568 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __y) 01569 { 01570 return std::lexicographical_compare(__x.begin(), __x.end(), 01571 __y.begin(), __y.end()); 01572 } 01573 01574 template<typename _Key, typename _Val, typename _KeyOfValue, 01575 typename _Compare , typename _Compare_PQ, typename _Alloc> 01576 inline bool 01577 operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x, 01578 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __y) 01579 { return !(__x == __y); } 01580 01581 template<typename _Key, typename _Val, typename _KeyOfValue, 01582 typename _Compare , typename _Compare_PQ, typename _Alloc> 01583 inline bool 01584 operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x, 01585 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __y) 01586 { return __y < __x; } 01587 01588 template<typename _Key, typename _Val, typename _KeyOfValue, 01589 typename _Compare , typename _Compare_PQ, typename _Alloc> 01590 inline bool 01591 operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x, 01592 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __y) 01593 { return !(__y < __x); } 01594 01595 template<typename _Key, typename _Val, typename _KeyOfValue, 01596 typename _Compare , typename _Compare_PQ, typename _Alloc> 01597 inline bool 01598 operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x, 01599 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __y) 01600 { return !(__x < __y); } 01601 01602 template<typename _Key, typename _Val, typename _KeyOfValue, 01603 typename _Compare , typename _Compare_PQ, typename _Alloc> 01604 inline void 01605 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x, 01606 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __y) 01607 { __x.swap(__y); } 01608 01609 template<typename _Key, typename _Val, typename _KeyOfValue, 01610 typename _Compare , typename _Compare_PQ, typename _Alloc> 01611 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& 01612 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>:: 01613 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>& __x) 01614 { 01615 if (this != &__x) 01616 { 01617 // Note that _Key may be a constant type. 01618 clear(); 01619 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 01620 if (__x._M_root() != 0) 01621 { 01622 _M_root() = _M_copy(__x._M_begin(), _M_end()); 01623 _M_leftmost() = _S_minimum(_M_root()); 01624 _M_rightmost() = _S_maximum(_M_root()); 01625 _M_impl._M_node_count = __x._M_impl._M_node_count; 01626 } 01627 } 01628 return *this; 01629 } 01630 01631 01632 01633 template<typename _Key, typename _Val, typename _KeyOfValue, 01634 typename _Compare , typename _Compare_PQ, typename _Alloc> 01635 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::iterator 01636 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>:: 01637 01638 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 01639 { 01640 _Link_type __z = _M_create_node(__v); 01641 01642 bool __insert_left; 01643 01644 __insert_left = __x != 0 || __p == _M_end() 01645 || _M_impl._M_key_compare(_KeyOfValue()(__v), 01646 _S_key(__p)); 01647 01648 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01649 this->_M_impl._M_header); 01650 ++_M_impl._M_node_count; 01651 return iterator(__z); 01652 } 01653 01654 template<typename _Key, typename _Val, typename _KeyOfValue, 01655 typename _Compare , typename _Compare_PQ, typename _Alloc> 01656 std::pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::iterator, 01657 bool> 01658 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>:: 01659 insert_unique(const _Val& __v) 01660 { 01661 cerr<<"In val insert"<<endl; 01662 _Link_type __x = _M_begin(); 01663 _Link_type __y = _M_end(); 01664 bool __comp = true; 01665 while (__x != 0) 01666 { 01667 __y = __x; 01668 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 01669 __x = __comp ? _S_left(__x) : _S_right(__x); 01670 } 01671 iterator __j = iterator(__y); 01672 if (__comp) 01673 if (__j == begin()) 01674 return std::pair<iterator,bool>(_M_insert(__x, __y, __v), true); 01675 else 01676 --__j; 01677 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 01678 return std::pair<iterator,bool>(_M_insert(__x, __y, __v), true); 01679 return std::pair<iterator,bool>(__j, false); 01680 } 01681 01682 01683 template<typename _Key, typename _Val, typename _KeyOfValue, 01684 typename _Compare , typename _Compare_PQ, typename _Alloc> 01685 inline void 01686 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::erase(_Base_ptr __position) 01687 { 01688 _Link_type __y = 01689 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position, 01690 this->_M_impl._M_header)); 01691 destroy_node(__y); 01692 --_M_impl._M_node_count; 01693 } 01694 01695 template<typename _Key, typename _Val, typename _KeyOfValue, 01696 typename _Compare , typename _Compare_PQ, typename _Alloc> 01697 inline 01698 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::_Base_ptr 01699 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::erase_top_PQ() 01700 { 01701 if(leftPQ[_M_impl._M_header_PQ]!=NULL || rightPQ[_M_impl._M_header_PQ]!=NULL) 01702 { 01703 _Base_ptr tmp = _M_erase_PQ(_M_impl._M_header_PQ); 01704 01705 // if(parentPQ[tmp]!=NULL){ 01706 if(leftPQ[parentPQ[tmp]]==tmp) 01707 { 01708 leftPQ[parentPQ[tmp]]=NULL; 01709 } 01710 else if(rightPQ[parentPQ[tmp]]==tmp) 01711 { 01712 rightPQ[parentPQ[tmp]]=NULL; 01713 } 01714 // } 01715 return tmp; 01716 } 01717 else 01718 { 01719 _Base_ptr tmp = _M_impl._M_header_PQ; 01720 _M_impl._M_header_PQ=NULL; 01721 return tmp; 01722 } 01723 01724 } 01725 01726 template<typename _Key, typename _Val, typename _KeyOfValue, 01727 typename _Compare , typename _Compare_PQ, typename _Alloc> 01728 inline 01729 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::_Base_ptr 01730 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::_M_erase_PQ(_Base_ptr __position) 01731 { 01732 _Base_ptr hole=__position; 01733 01734 while(hole!=NULL) 01735 { 01736 if(leftPQ[hole]!=NULL) 01737 { 01738 if(rightPQ[hole]!=NULL) 01739 { 01740 if(_M_impl._M_key_compare_pq(_S_key(leftPQ[hole]), _S_key(rightPQ[hole]))) 01741 { 01742 update_node(hole, leftPQ[hole]); 01743 //hole=leftPQ[hole]; 01744 } 01745 else 01746 { 01747 update_node(hole, rightPQ[hole]); 01748 //hole=rightPQ[hole]; 01749 } 01750 } 01751 else 01752 {//only left child present 01753 update_node(hole, leftPQ[hole]); 01754 //hole=leftPQ[hole]; 01755 } 01756 } 01757 else if(rightPQ[hole]!=NULL) 01758 //only right child present 01759 { 01760 update_node(hole, rightPQ[hole]); 01761 //hole=rightPQ[hole]; 01762 } 01763 else{ 01764 //no children, stop 01765 return hole; 01766 } 01767 } 01768 } 01769 01770 01771 template<typename _Key, typename _Val, typename _KeyOfValue, 01772 typename _Compare , typename _Compare_PQ, typename _Alloc> 01773 inline void 01774 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::update_node( 01775 _Base_ptr hole, 01776 _Base_ptr newNode) 01777 { 01778 if(parentPQ[hole]==NULL) 01779 { 01780 parentPQ[newNode]=NULL; 01781 _M_impl._M_header_PQ=newNode; 01782 } 01783 else 01784 { 01785 std::swap(parentPQ[newNode], parentPQ[hole]); 01786 01787 if(leftPQ[parentPQ[newNode]]==hole) 01788 { 01789 leftPQ[parentPQ[newNode]]=newNode; 01790 } 01791 else 01792 { 01793 rightPQ[parentPQ[newNode]]=newNode; 01794 } 01795 } 01796 01797 std::swap(leftPQ[hole],leftPQ[newNode]); 01798 if(leftPQ[hole]!=NULL) 01799 { 01800 parentPQ[leftPQ[hole]]=hole; 01801 } 01802 if(leftPQ[newNode]==newNode) 01803 { 01804 leftPQ[newNode]=hole; 01805 } 01806 if(leftPQ[newNode]!=NULL) 01807 { 01808 parentPQ[leftPQ[newNode]]=newNode; 01809 } 01810 01811 std::swap(rightPQ[hole],rightPQ[newNode]); 01812 if(rightPQ[hole]!=NULL) 01813 { 01814 parentPQ[rightPQ[hole]]=hole; 01815 } 01816 if(rightPQ[newNode]==newNode) 01817 { 01818 rightPQ[newNode]=hole; 01819 } 01820 if(rightPQ[newNode]!=NULL) 01821 { 01822 parentPQ[rightPQ[newNode]]=newNode; 01823 } 01824 01825 } 01826 01827 01828 01829 01830 template<typename _Key, typename _Val, typename _KeyOfValue, 01831 typename _Compare , typename _Compare_PQ, typename _Alloc> 01832 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::size_type 01833 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::erase(const _Key& __x) 01834 { 01835 std::pair<iterator,iterator> __p = equal_range(__x); 01836 size_type __n = std::distance(__p.first, __p.second); 01837 erase(__p.first, __p.second); 01838 return __n; 01839 } 01840 01841 template<typename _Key, typename _Val, typename _KoV, 01842 typename _Compare , typename _Compare_PQ, typename _Alloc> 01843 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Compare_PQ, _Alloc>::_Link_type 01844 _Rb_tree<_Key,_Val,_KoV,_Compare,_Compare_PQ,_Alloc>:: 01845 _M_copy(_Const_Link_type __x, _Link_type __p) 01846 { 01847 // Structural copy. __x and __p must be non-null. 01848 _Link_type __top = _M_clone_node(__x); 01849 __top->_M_parent = __p; 01850 01851 try 01852 { 01853 if (__x->_M_right) 01854 __top->_M_right = _M_copy(_S_right(__x), __top); 01855 __p = __top; 01856 __x = _S_left(__x); 01857 01858 while (__x != 0) 01859 { 01860 _Link_type __y = _M_clone_node(__x); 01861 __p->_M_left = __y; 01862 __y->_M_parent = __p; 01863 if (__x->_M_right) 01864 __y->_M_right = _M_copy(_S_right(__x), __y); 01865 __p = __y; 01866 __x = _S_left(__x); 01867 } 01868 } 01869 catch(...) 01870 { 01871 _M_erase(__top); 01872 __throw_exception_again; 01873 } 01874 return __top; 01875 } 01876 01877 template<typename _Key, typename _Val, typename _KeyOfValue, 01878 typename _Compare , typename _Compare_PQ, typename _Alloc> 01879 void 01880 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::_M_erase(_Link_type __x) 01881 { 01882 // Erase without rebalancing. 01883 while (__x != 0) 01884 { 01885 _M_erase(_S_right(__x)); 01886 _Link_type __y = _S_left(__x); 01887 destroy_node(__x); 01888 __x = __y; 01889 } 01890 } 01891 01892 template<typename _Key, typename _Val, typename _KeyOfValue, 01893 typename _Compare , typename _Compare_PQ, typename _Alloc> 01894 void 01895 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>:: 01896 erase(iterator __first, iterator __last) 01897 { 01898 if (__first == begin() && __last == end()) 01899 clear(); 01900 else 01901 while (__first != __last) erase(__first++); 01902 } 01903 01904 template<typename _Key, typename _Val, typename _KeyOfValue, 01905 typename _Compare , typename _Compare_PQ, typename _Alloc> 01906 void 01907 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>:: 01908 erase(const _Key* __first, const _Key* __last) 01909 { 01910 while (__first != __last) 01911 erase(*__first++); 01912 } 01913 01917 template<typename _Key, typename _Val, typename _KeyOfValue, 01918 typename _Compare , typename _Compare_PQ, typename _Alloc> 01919 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::iterator 01920 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::find(const _Key& __k) 01921 { 01922 _Compare c; 01923 c(__k, __k); 01924 _Link_type __x = _M_begin(); // Current node. 01925 _Link_type __y = _M_end(); // Last node which is not less than __k. 01926 // cerr<<"In key find "<<endl; 01927 01928 while (__x != 0) 01929 { 01930 // cerr<<*_S_key(__x)<<" "<<*__k<<" "<<_Compare()(_S_key(__x), __k)<<endl; 01931 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01932 { 01933 // cerr<<"Going left"<<endl; 01934 __y = __x, __x = _S_left(__x); 01935 } 01936 else 01937 { 01938 // cerr<<"Going right"<<endl; 01939 __x = _S_right(__x); 01940 01941 } 01942 } 01943 // cerr<<"In key find finished loop"<<endl; 01944 iterator __j = iterator(__y); 01945 return __j; 01946 return (__j == end() 01947 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; 01948 01949 } 01950 01951 template<typename _Key, typename _Val, typename _KeyOfValue, 01952 typename _Compare , typename _Compare_PQ, typename _Alloc> 01953 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::const_iterator 01954 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>:: 01955 find(const _Key& __k) const 01956 { 01957 cerr<<"In key find"<<endl; 01958 _Const_Link_type __x = _M_begin(); // Current node. 01959 _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 01960 01961 while (__x != 0) 01962 { 01963 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01964 __y = __x, __x = _S_left(__x); 01965 else 01966 __x = _S_right(__x); 01967 } 01968 const_iterator __j = const_iterator(__y); 01969 return __j; 01970 return (__j == end() 01971 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; 01972 } 01973 01974 template<typename _Key, typename _Val, typename _KeyOfValue, 01975 typename _Compare , typename _Compare_PQ, typename _Alloc> 01976 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::size_type 01977 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>:: 01978 count(const _Key& __k) const 01979 { 01980 std::pair<const_iterator, const_iterator> __p = equal_range(__k); 01981 const size_type __n = std::distance(__p.first, __p.second); 01982 return __n; 01983 } 01984 01985 unsigned int 01986 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 01987 const _Rb_tree_node_base* __root); 01988 01989 template<typename _Key, typename _Val, typename _KeyOfValue, 01990 typename _Compare , typename _Compare_PQ, typename _Alloc> 01991 bool 01992 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Compare_PQ, _Alloc>::__rb_verify() const 01993 { 01994 if (_M_impl._M_node_count == 0 || begin() == end()) 01995 return _M_impl._M_node_count == 0 && begin() == end() 01996 && this->_M_impl._M_header._M_left == _M_end() 01997 && this->_M_impl._M_header._M_right == _M_end(); 01998 01999 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 02000 for (const_iterator __it = begin(); __it != end(); ++__it) 02001 { 02002 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 02003 _Const_Link_type __L = _S_left(__x); 02004 _Const_Link_type __R = _S_right(__x); 02005 02006 if (__x->_M_color == _S_red) 02007 if ((__L && __L->_M_color == _S_red) 02008 || (__R && __R->_M_color == _S_red)) 02009 return false; 02010 02011 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 02012 return false; 02013 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 02014 return false; 02015 02016 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 02017 return false; 02018 } 02019 02020 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 02021 return false; 02022 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 02023 return false; 02024 return true; 02025 } 02026 }//namespace space_tree_heap 02027 } // namespace inplaceds 02028 02029 #endif 02030
Code Documentation generated Using Doxygen
Copyright © Ilya Katz and Hervé Brönnimann, 2005, 2006.