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