libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the terms 00008 // of the GNU General Public License as published by the Free Software 00009 // Foundation; either version 3, or (at your option) any later 00010 // version. 00011 00012 // This library is distributed in the hope that it will be useful, but 00013 // WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 // General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00027 00028 // Permission to use, copy, modify, sell, and distribute this software 00029 // is hereby granted without fee, provided that the above copyright 00030 // notice appears in all copies, and that both that copyright notice 00031 // and this permission notice appear in supporting documentation. None 00032 // of the above authors, nor IBM Haifa Research Laboratories, make any 00033 // representation about the suitability of this software for any 00034 // purpose. It is provided "as is" without express or implied 00035 // warranty. 00036 00037 /** 00038 * @file pat_trie_/pat_trie_.hpp 00039 * Contains an implementation class for a patricia tree. 00040 */ 00041 00042 #include <iterator> 00043 #include <utility> 00044 #include <algorithm> 00045 #include <functional> 00046 #include <assert.h> 00047 #include <list> 00048 #include <ext/pb_ds/exception.hpp> 00049 #include <ext/pb_ds/tag_and_trait.hpp> 00050 #include <ext/pb_ds/tree_policy.hpp> 00051 #include <ext/pb_ds/detail/cond_dealtor.hpp> 00052 #include <ext/pb_ds/detail/type_utils.hpp> 00053 #include <ext/pb_ds/detail/types_traits.hpp> 00054 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 00055 #include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp> 00056 #include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp> 00057 #ifdef _GLIBCXX_DEBUG 00058 #include <ext/pb_ds/detail/debug_map_base.hpp> 00059 #endif 00060 #include <debug/debug.h> 00061 00062 namespace __gnu_pbds 00063 { 00064 namespace detail 00065 { 00066 #ifdef PB_DS_DATA_TRUE_INDICATOR 00067 #define PB_DS_PAT_TRIE_NAME pat_trie_map 00068 #endif 00069 00070 #ifdef PB_DS_DATA_FALSE_INDICATOR 00071 #define PB_DS_PAT_TRIE_NAME pat_trie_set 00072 #endif 00073 00074 #define PB_DS_CLASS_T_DEC \ 00075 template<typename Key, typename Mapped, typename Node_And_It_Traits, \ 00076 typename _Alloc> 00077 00078 #define PB_DS_CLASS_C_DEC \ 00079 PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc> 00080 00081 #define PB_DS_PAT_TRIE_TRAITS_BASE \ 00082 types_traits<Key, Mapped, _Alloc, false> 00083 00084 #ifdef _GLIBCXX_DEBUG 00085 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 00086 debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \ 00087 typename _Alloc::template rebind<Key>::other::const_reference> 00088 #endif 00089 00090 00091 /** 00092 * @brief PATRICIA trie. 00093 * @ingroup branch-detail 00094 * 00095 * This implementation loosely borrows ideas from: 00096 * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 00097 * 2) Ptset: Sets of integers implemented as Patricia trees, 00098 * Jean-Christophe Filliatr, 2000 00099 */ 00100 template<typename Key, typename Mapped, typename Node_And_It_Traits, 00101 typename _Alloc> 00102 class PB_DS_PAT_TRIE_NAME : 00103 #ifdef _GLIBCXX_DEBUG 00104 public PB_DS_DEBUG_MAP_BASE_C_DEC, 00105 #endif 00106 public Node_And_It_Traits::synth_access_traits, 00107 public Node_And_It_Traits::node_update, 00108 public PB_DS_PAT_TRIE_TRAITS_BASE, 00109 public pat_trie_base 00110 { 00111 private: 00112 typedef pat_trie_base base_type; 00113 typedef PB_DS_PAT_TRIE_TRAITS_BASE traits_base; 00114 typedef Node_And_It_Traits traits_type; 00115 00116 typedef typename traits_type::synth_access_traits synth_access_traits; 00117 typedef typename synth_access_traits::const_iterator a_const_iterator; 00118 00119 typedef typename traits_type::node node; 00120 typedef typename _Alloc::template rebind<node> __rebind_n; 00121 typedef typename __rebind_n::other::const_pointer node_const_pointer; 00122 typedef typename __rebind_n::other::pointer node_pointer; 00123 00124 typedef typename traits_type::head head; 00125 typedef typename _Alloc::template rebind<head> __rebind_h; 00126 typedef typename __rebind_h::other head_allocator; 00127 typedef typename head_allocator::pointer head_pointer; 00128 00129 typedef typename traits_type::leaf leaf; 00130 typedef typename _Alloc::template rebind<leaf> __rebind_l; 00131 typedef typename __rebind_l::other leaf_allocator; 00132 typedef typename leaf_allocator::pointer leaf_pointer; 00133 typedef typename leaf_allocator::const_pointer leaf_const_pointer; 00134 00135 typedef typename traits_type::inode inode; 00136 typedef typename inode::iterator inode_iterator; 00137 typedef typename _Alloc::template rebind<inode> __rebind_in; 00138 typedef typename __rebind_in::other __rebind_ina; 00139 typedef typename __rebind_in::other inode_allocator; 00140 typedef typename __rebind_ina::pointer inode_pointer; 00141 typedef typename __rebind_ina::const_pointer inode_const_pointer; 00142 00143 00144 /// Conditional deallocator. 00145 class cond_dealtor 00146 { 00147 protected: 00148 leaf_pointer m_p_nd; 00149 bool m_no_action_dtor; 00150 bool m_call_destructor; 00151 00152 public: 00153 cond_dealtor(leaf_pointer p_nd) 00154 : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false) 00155 { } 00156 00157 void 00158 set_no_action_dtor() 00159 { m_no_action_dtor = true; } 00160 00161 void 00162 set_call_destructor() 00163 { m_call_destructor = true; } 00164 00165 ~cond_dealtor() 00166 { 00167 if (m_no_action_dtor) 00168 return; 00169 00170 if (m_call_destructor) 00171 m_p_nd->~leaf(); 00172 00173 s_leaf_allocator.deallocate(m_p_nd, 1); 00174 } 00175 }; 00176 00177 00178 /// Branch bag, for split-join. 00179 class branch_bag 00180 { 00181 private: 00182 typedef inode_pointer __inp; 00183 typedef typename _Alloc::template rebind<__inp>::other __rebind_inp; 00184 00185 #ifdef _GLIBCXX_DEBUG 00186 typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp> bag_type; 00187 #else 00188 typedef std::list<__inp, __rebind_inp> bag_type; 00189 #endif 00190 00191 bag_type m_bag; 00192 public: 00193 void 00194 add_branch() 00195 { 00196 inode_pointer p_nd = s_inode_allocator.allocate(1); 00197 __try 00198 { 00199 m_bag.push_back(p_nd); 00200 } 00201 __catch(...) 00202 { 00203 s_inode_allocator.deallocate(p_nd, 1); 00204 __throw_exception_again; 00205 } 00206 } 00207 00208 inode_pointer 00209 get_branch() 00210 { 00211 _GLIBCXX_DEBUG_ASSERT(!m_bag.empty()); 00212 inode_pointer p_nd = *m_bag.begin(); 00213 m_bag.pop_front(); 00214 return p_nd; 00215 } 00216 00217 ~branch_bag() 00218 { 00219 while (!m_bag.empty()) 00220 { 00221 inode_pointer p_nd = *m_bag.begin(); 00222 s_inode_allocator.deallocate(p_nd, 1); 00223 m_bag.pop_front(); 00224 } 00225 } 00226 00227 inline bool 00228 empty() const 00229 { return m_bag.empty(); } 00230 }; 00231 00232 #ifdef _GLIBCXX_DEBUG 00233 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 00234 #endif 00235 00236 typedef typename traits_type::null_node_update_pointer null_node_update_pointer; 00237 00238 public: 00239 typedef pat_trie_tag container_category; 00240 typedef _Alloc allocator_type; 00241 typedef typename _Alloc::size_type size_type; 00242 typedef typename _Alloc::difference_type difference_type; 00243 00244 typedef typename traits_base::key_type key_type; 00245 typedef typename traits_base::key_pointer key_pointer; 00246 typedef typename traits_base::key_const_pointer key_const_pointer; 00247 typedef typename traits_base::key_reference key_reference; 00248 typedef typename traits_base::key_const_reference key_const_reference; 00249 typedef typename traits_base::mapped_type mapped_type; 00250 typedef typename traits_base::mapped_pointer mapped_pointer; 00251 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 00252 typedef typename traits_base::mapped_reference mapped_reference; 00253 typedef typename traits_base::mapped_const_reference mapped_const_reference; 00254 typedef typename traits_base::value_type value_type; 00255 typedef typename traits_base::pointer pointer; 00256 typedef typename traits_base::const_pointer const_pointer; 00257 typedef typename traits_base::reference reference; 00258 typedef typename traits_base::const_reference const_reference; 00259 00260 typedef typename traits_type::access_traits access_traits; 00261 typedef typename traits_type::const_iterator point_const_iterator; 00262 typedef typename traits_type::iterator point_iterator; 00263 typedef point_const_iterator const_iterator; 00264 typedef point_iterator iterator; 00265 00266 typedef typename traits_type::reverse_iterator reverse_iterator; 00267 typedef typename traits_type::const_reverse_iterator const_reverse_iterator; 00268 typedef typename traits_type::node_const_iterator node_const_iterator; 00269 typedef typename traits_type::node_iterator node_iterator; 00270 typedef typename traits_type::node_update node_update; 00271 00272 PB_DS_PAT_TRIE_NAME(); 00273 00274 PB_DS_PAT_TRIE_NAME(const access_traits&); 00275 00276 PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&); 00277 00278 void 00279 swap(PB_DS_CLASS_C_DEC&); 00280 00281 ~PB_DS_PAT_TRIE_NAME(); 00282 00283 inline bool 00284 empty() const; 00285 00286 inline size_type 00287 size() const; 00288 00289 inline size_type 00290 max_size() const; 00291 00292 access_traits& 00293 get_access_traits(); 00294 00295 const access_traits& 00296 get_access_traits() const; 00297 00298 node_update& 00299 get_node_update(); 00300 00301 const node_update& 00302 get_node_update() const; 00303 00304 inline std::pair<point_iterator, bool> 00305 insert(const_reference); 00306 00307 inline mapped_reference 00308 operator[](key_const_reference r_key) 00309 { 00310 #ifdef PB_DS_DATA_TRUE_INDICATOR 00311 return insert(std::make_pair(r_key, mapped_type())).first->second; 00312 #else 00313 insert(r_key); 00314 return traits_base::s_null_type; 00315 #endif 00316 } 00317 00318 inline point_iterator 00319 find(key_const_reference); 00320 00321 inline point_const_iterator 00322 find(key_const_reference) const; 00323 00324 inline point_iterator 00325 lower_bound(key_const_reference); 00326 00327 inline point_const_iterator 00328 lower_bound(key_const_reference) const; 00329 00330 inline point_iterator 00331 upper_bound(key_const_reference); 00332 00333 inline point_const_iterator 00334 upper_bound(key_const_reference) const; 00335 00336 void 00337 clear(); 00338 00339 inline bool 00340 erase(key_const_reference); 00341 00342 inline const_iterator 00343 erase(const_iterator); 00344 00345 #ifdef PB_DS_DATA_TRUE_INDICATOR 00346 inline iterator 00347 erase(iterator); 00348 #endif 00349 00350 inline const_reverse_iterator 00351 erase(const_reverse_iterator); 00352 00353 #ifdef PB_DS_DATA_TRUE_INDICATOR 00354 inline reverse_iterator 00355 erase(reverse_iterator); 00356 #endif 00357 00358 template<typename Pred> 00359 inline size_type 00360 erase_if(Pred); 00361 00362 void 00363 join(PB_DS_CLASS_C_DEC&); 00364 00365 void 00366 split(key_const_reference, PB_DS_CLASS_C_DEC&); 00367 00368 inline iterator 00369 begin(); 00370 00371 inline const_iterator 00372 begin() const; 00373 00374 inline iterator 00375 end(); 00376 00377 inline const_iterator 00378 end() const; 00379 00380 inline reverse_iterator 00381 rbegin(); 00382 00383 inline const_reverse_iterator 00384 rbegin() const; 00385 00386 inline reverse_iterator 00387 rend(); 00388 00389 inline const_reverse_iterator 00390 rend() const; 00391 00392 /// Returns a const node_iterator corresponding to the node at the 00393 /// root of the tree. 00394 inline node_const_iterator 00395 node_begin() const; 00396 00397 /// Returns a node_iterator corresponding to the node at the 00398 /// root of the tree. 00399 inline node_iterator 00400 node_begin(); 00401 00402 /// Returns a const node_iterator corresponding to a node just 00403 /// after a leaf of the tree. 00404 inline node_const_iterator 00405 node_end() const; 00406 00407 /// Returns a node_iterator corresponding to a node just 00408 /// after a leaf of the tree. 00409 inline node_iterator 00410 node_end(); 00411 00412 #ifdef PB_DS_PAT_TRIE_TRACE_ 00413 void 00414 trace() const; 00415 #endif 00416 00417 protected: 00418 template<typename It> 00419 void 00420 copy_from_range(It, It); 00421 00422 void 00423 value_swap(PB_DS_CLASS_C_DEC&); 00424 00425 node_pointer 00426 recursive_copy_node(node_const_pointer); 00427 00428 private: 00429 void 00430 initialize(); 00431 00432 inline void 00433 apply_update(node_pointer, null_node_update_pointer); 00434 00435 template<typename Node_Update_> 00436 inline void 00437 apply_update(node_pointer, Node_Update_*); 00438 00439 bool 00440 join_prep(PB_DS_CLASS_C_DEC&, branch_bag&); 00441 00442 void 00443 rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&); 00444 00445 void 00446 rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&); 00447 00448 void 00449 rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&); 00450 00451 void 00452 rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&); 00453 00454 void 00455 rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&); 00456 00457 node_pointer 00458 rec_join(node_pointer, node_pointer, size_type, branch_bag&); 00459 00460 node_pointer 00461 rec_join(leaf_pointer, leaf_pointer, branch_bag&); 00462 00463 node_pointer 00464 rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&); 00465 00466 node_pointer 00467 rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&); 00468 00469 node_pointer 00470 rec_join(inode_pointer, inode_pointer, branch_bag&); 00471 00472 size_type 00473 keys_diff_ind(typename access_traits::const_iterator, 00474 typename access_traits::const_iterator, 00475 typename access_traits::const_iterator, 00476 typename access_traits::const_iterator); 00477 00478 inode_pointer 00479 insert_branch(node_pointer, node_pointer, branch_bag&); 00480 00481 void 00482 update_min_max_for_inserted_leaf(leaf_pointer); 00483 00484 void 00485 erase_leaf(leaf_pointer); 00486 00487 inline void 00488 actual_erase_leaf(leaf_pointer); 00489 00490 void 00491 clear_imp(node_pointer); 00492 00493 void 00494 erase_fixup(inode_pointer); 00495 00496 void 00497 update_min_max_for_erased_leaf(leaf_pointer); 00498 00499 static inline a_const_iterator 00500 pref_begin(node_const_pointer); 00501 00502 static inline a_const_iterator 00503 pref_end(node_const_pointer); 00504 00505 inline node_pointer 00506 find_imp(key_const_reference); 00507 00508 inline node_pointer 00509 lower_bound_imp(key_const_reference); 00510 00511 inline node_pointer 00512 upper_bound_imp(key_const_reference); 00513 00514 inline static leaf_const_pointer 00515 leftmost_descendant(node_const_pointer); 00516 00517 inline static leaf_pointer 00518 leftmost_descendant(node_pointer); 00519 00520 inline static leaf_const_pointer 00521 rightmost_descendant(node_const_pointer); 00522 00523 inline static leaf_pointer 00524 rightmost_descendant(node_pointer); 00525 00526 #ifdef _GLIBCXX_DEBUG 00527 void 00528 assert_valid(const char*, int) const; 00529 00530 void 00531 assert_iterators(const char*, int) const; 00532 00533 void 00534 assert_reverse_iterators(const char*, int) const; 00535 00536 static size_type 00537 recursive_count_leafs(node_const_pointer, const char*, int); 00538 #endif 00539 00540 #ifdef PB_DS_PAT_TRIE_TRACE_ 00541 static void 00542 trace_node(node_const_pointer, size_type); 00543 00544 template<typename Metadata_> 00545 static void 00546 trace_node_metadata(node_const_pointer, type_to_type<Metadata_>); 00547 00548 static void 00549 trace_node_metadata(node_const_pointer, type_to_type<null_type>); 00550 #endif 00551 00552 leaf_pointer 00553 split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&); 00554 00555 node_pointer 00556 rec_split(node_pointer, a_const_iterator, a_const_iterator, 00557 PB_DS_CLASS_C_DEC&, branch_bag&); 00558 00559 void 00560 split_insert_branch(size_type, a_const_iterator, inode_iterator, 00561 size_type, branch_bag&); 00562 00563 static head_allocator s_head_allocator; 00564 static inode_allocator s_inode_allocator; 00565 static leaf_allocator s_leaf_allocator; 00566 00567 head_pointer m_p_head; 00568 size_type m_size; 00569 }; 00570 00571 #define PB_DS_ASSERT_NODE_VALID(X) \ 00572 _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);) 00573 00574 #define PB_DS_RECURSIVE_COUNT_LEAFS(X) \ 00575 recursive_count_leafs(X, __FILE__, __LINE__) 00576 00577 #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp> 00578 #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp> 00579 #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp> 00580 #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp> 00581 #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp> 00582 #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp> 00583 #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp> 00584 #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp> 00585 #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp> 00586 #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp> 00587 #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp> 00588 00589 #undef PB_DS_RECURSIVE_COUNT_LEAFS 00590 #undef PB_DS_ASSERT_NODE_VALID 00591 #undef PB_DS_CLASS_C_DEC 00592 #undef PB_DS_CLASS_T_DEC 00593 #undef PB_DS_PAT_TRIE_NAME 00594 #undef PB_DS_PAT_TRIE_TRAITS_BASE 00595 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 00596 } // namespace detail 00597 } // namespace __gnu_pbds