1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2009, 2010 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the terms 7 // of the GNU General Public License as published by the Free Software 8 // Foundation; either version 3, or (at your option) any later 9 // version. 10 11 // This library is distributed in the hope that it will be useful, but 12 // WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 // General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27 // Permission to use, copy, modify, sell, and distribute this software 28 // is hereby granted without fee, provided that the above copyright 29 // notice appears in all copies, and that both that copyright notice 30 // and this permission notice appear in supporting documentation. None 31 // of the above authors, nor IBM Haifa Research Laboratories, make any 32 // representation about the suitability of this software for any 33 // purpose. It is provided "as is" without express or implied 34 // warranty. 35 36 /** 37 * @file pat_trie_.hpp 38 * Contains an implementation class for a patricia tree. 39 */ 40 41 /** 42 * This implementation loosely borrows ideas from: 43 * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 44 * 2) Ptset: Sets of integers implemented as Patricia trees, 45 * Jean-Christophe Filliatr, 2000 46 **/ 47 48 #include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp> 49 #include <ext/pb_ds/detail/pat_trie_/node_base.hpp> 50 #include <ext/pb_ds/exception.hpp> 51 #include <ext/pb_ds/tag_and_trait.hpp> 52 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 53 #include <ext/pb_ds/detail/types_traits.hpp> 54 #include <ext/pb_ds/tree_policy.hpp> 55 #include <ext/pb_ds/detail/cond_dealtor.hpp> 56 #include <ext/pb_ds/detail/type_utils.hpp> 57 #include <iterator> 58 #include <utility> 59 #include <algorithm> 60 #include <functional> 61 #include <assert.h> 62 #include <list> 63 #ifdef _GLIBCXX_DEBUG 64 #include <ext/pb_ds/detail/debug_map_base.hpp> 65 #endif 66 #include <debug/debug.h> 67 68 namespace __gnu_pbds 69 { 70 namespace detail 71 { 72 #define PB_DS_CLASS_T_DEC \ 73 template<typename Key, typename Mapped, typename Node_And_It_Traits, \ 74 typename Allocator> 75 76 #ifdef PB_DS_DATA_TRUE_INDICATOR 77 #define PB_DS_CLASS_NAME pat_trie_data_ 78 #endif 79 80 #ifdef PB_DS_DATA_FALSE_INDICATOR 81 #define PB_DS_CLASS_NAME pat_trie_no_data_ 82 #endif 83 84 #define PB_DS_CLASS_C_DEC \ 85 PB_DS_CLASS_NAME<Key, Mapped, Node_And_It_Traits, Allocator> 86 87 #define PB_DS_TYPES_TRAITS_C_DEC \ 88 types_traits<Key, Mapped, Allocator, false> 89 90 #ifdef _GLIBCXX_DEBUG 91 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 92 debug_map_base<Key, eq_by_less<Key, \ 93 std::less<Key> >, typename Allocator::template rebind<Key>::other::const_reference> 94 #endif 95 96 #ifdef PB_DS_DATA_TRUE_INDICATOR 97 #define PB_DS_V2F(X) (X).first 98 #define PB_DS_V2S(X) (X).second 99 #define PB_DS_EP2VP(X)& ((X)->m_value) 100 #endif 101 102 #ifdef PB_DS_DATA_FALSE_INDICATOR 103 #define PB_DS_V2F(X) (X) 104 #define PB_DS_V2S(X) Mapped_Data() 105 #define PB_DS_EP2VP(X)& ((X)->m_value.first) 106 #endif 107 108 /** 109 * class description = PATRICIA trie implementation."> 110 **/ 111 template<typename Key, 112 typename Mapped, 113 typename Node_And_It_Traits, 114 typename Allocator> 115 class PB_DS_CLASS_NAME : 116 #ifdef _GLIBCXX_DEBUG 117 public PB_DS_DEBUG_MAP_BASE_C_DEC, 118 #endif 119 public Node_And_It_Traits::synth_e_access_traits, 120 public Node_And_It_Traits::node_update, 121 public PB_DS_TYPES_TRAITS_C_DEC 122 { 123 private: 124 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 125 126 typedef typename Node_And_It_Traits::synth_e_access_traits synth_e_access_traits; 127 typedef typename Allocator::template rebind<synth_e_access_traits>::other::const_pointer const_e_access_traits_pointer; 128 typedef typename synth_e_access_traits::const_iterator const_e_iterator; 129 130 typedef typename Node_And_It_Traits::node node; 131 typedef typename Allocator::template rebind<node>::other::const_pointer const_node_pointer; 132 133 typedef typename Allocator::template rebind<node>::other::pointer node_pointer; 134 135 typedef typename Node_And_It_Traits::head head; 136 typedef typename Allocator::template rebind<head>::other head_allocator; 137 typedef typename head_allocator::pointer head_pointer; 138 139 typedef typename Node_And_It_Traits::leaf leaf; 140 typedef typename Allocator::template rebind<leaf>::other leaf_allocator; 141 typedef typename leaf_allocator::const_pointer const_leaf_pointer; 142 typedef typename leaf_allocator::pointer leaf_pointer; 143 144 typedef typename Node_And_It_Traits::internal_node internal_node; 145 typedef typename Allocator::template rebind<internal_node>::other internal_node_allocator; 146 typedef typename internal_node_allocator::const_pointer const_internal_node_pointer; 147 typedef typename internal_node_allocator::pointer internal_node_pointer; 148 149 #include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp> 150 151 #ifdef _GLIBCXX_DEBUG 152 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 153 #endif 154 155 #include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp> 156 157 typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer; 158 159 public: 160 typedef pat_trie_tag container_category; 161 typedef Allocator allocator_type; 162 typedef typename Allocator::size_type size_type; 163 typedef typename Allocator::difference_type difference_type; 164 165 typedef typename traits_base::key_type key_type; 166 typedef typename traits_base::key_pointer key_pointer; 167 typedef typename traits_base::const_key_pointer const_key_pointer; 168 typedef typename traits_base::key_reference key_reference; 169 typedef typename traits_base::const_key_reference const_key_reference; 170 typedef typename traits_base::mapped_type mapped_type; 171 typedef typename traits_base::mapped_pointer mapped_pointer; 172 typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 173 typedef typename traits_base::mapped_reference mapped_reference; 174 typedef typename traits_base::const_mapped_reference const_mapped_reference; 175 typedef typename traits_base::value_type value_type; 176 typedef typename traits_base::pointer pointer; 177 typedef typename traits_base::const_pointer const_pointer; 178 typedef typename traits_base::reference reference; 179 typedef typename traits_base::const_reference const_reference; 180 181 typedef typename Node_And_It_Traits::const_iterator const_point_iterator; 182 typedef typename Node_And_It_Traits::iterator point_iterator; 183 typedef const_point_iterator const_iterator; 184 typedef point_iterator iterator; 185 186 typedef typename Node_And_It_Traits::const_reverse_iterator const_reverse_iterator; 187 typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; 188 typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator; 189 typedef typename Node_And_It_Traits::node_iterator node_iterator; 190 typedef typename Node_And_It_Traits::e_access_traits e_access_traits; 191 typedef typename Node_And_It_Traits::node_update node_update; 192 193 PB_DS_CLASS_NAME(); 194 195 PB_DS_CLASS_NAME(const e_access_traits&); 196 197 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 198 199 void 200 swap(PB_DS_CLASS_C_DEC&); 201 202 ~PB_DS_CLASS_NAME(); 203 204 inline bool 205 empty() const; 206 207 inline size_type 208 size() const; 209 210 inline size_type 211 max_size() const; 212 213 e_access_traits& 214 get_e_access_traits(); 215 216 const e_access_traits& 217 get_e_access_traits() const; 218 219 node_update& 220 get_node_update(); 221 222 const node_update& 223 get_node_update() const; 224 225 inline std::pair<point_iterator, bool> 226 insert(const_reference); 227 228 inline mapped_reference 229 operator[](const_key_reference r_key) 230 { 231 #ifdef PB_DS_DATA_TRUE_INDICATOR 232 return insert(std::make_pair(r_key, mapped_type())).first->second; 233 #else 234 insert(r_key); 235 return traits_base::s_null_mapped; 236 #endif 237 } 238 239 inline point_iterator 240 find(const_key_reference); 241 242 inline const_point_iterator 243 find(const_key_reference) const; 244 245 inline point_iterator 246 lower_bound(const_key_reference); 247 248 inline const_point_iterator 249 lower_bound(const_key_reference) const; 250 251 inline point_iterator 252 upper_bound(const_key_reference); 253 254 inline const_point_iterator 255 upper_bound(const_key_reference) const; 256 257 void 258 clear(); 259 260 inline bool 261 erase(const_key_reference); 262 263 inline const_iterator 264 erase(const_iterator); 265 266 #ifdef PB_DS_DATA_TRUE_INDICATOR 267 inline iterator 268 erase(iterator); 269 #endif 270 271 inline const_reverse_iterator 272 erase(const_reverse_iterator); 273 274 #ifdef PB_DS_DATA_TRUE_INDICATOR 275 inline reverse_iterator 276 erase(reverse_iterator); 277 #endif 278 279 template<typename Pred> 280 inline size_type 281 erase_if(Pred); 282 283 void 284 join(PB_DS_CLASS_C_DEC&); 285 286 void 287 split(const_key_reference, PB_DS_CLASS_C_DEC&); 288 289 inline iterator 290 begin(); 291 292 inline const_iterator 293 begin() const; 294 295 inline iterator 296 end(); 297 298 inline const_iterator 299 end() const; 300 301 inline reverse_iterator 302 rbegin(); 303 304 inline const_reverse_iterator 305 rbegin() const; 306 307 inline reverse_iterator 308 rend(); 309 310 inline const_reverse_iterator 311 rend() const; 312 313 inline const_node_iterator 314 node_begin() const; 315 316 inline node_iterator 317 node_begin(); 318 319 inline const_node_iterator 320 node_end() const; 321 322 inline node_iterator 323 node_end(); 324 325 #ifdef PB_DS_PAT_TRIE_TRACE_ 326 void 327 trace() const; 328 #endif 329 330 protected: 331 332 template<typename It> 333 void 334 copy_from_range(It, It); 335 336 void 337 value_swap(PB_DS_CLASS_C_DEC&); 338 339 node_pointer 340 recursive_copy_node(const_node_pointer); 341 342 private: 343 344 void 345 initialize(); 346 347 inline void 348 apply_update(node_pointer, null_node_update_pointer); 349 350 template<typename Node_Update_> 351 inline void 352 apply_update(node_pointer, Node_Update_*); 353 354 bool 355 join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&); 356 357 void 358 rec_join_prep(const_node_pointer, const_node_pointer, 359 split_join_branch_bag&); 360 361 void 362 rec_join_prep(const_leaf_pointer, const_leaf_pointer, 363 split_join_branch_bag&); 364 365 void 366 rec_join_prep(const_leaf_pointer, const_internal_node_pointer, 367 split_join_branch_bag&); 368 369 void 370 rec_join_prep(const_internal_node_pointer, const_leaf_pointer, 371 split_join_branch_bag&); 372 373 void 374 rec_join_prep(const_internal_node_pointer, const_internal_node_pointer, 375 split_join_branch_bag&); 376 377 node_pointer 378 rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&); 379 380 node_pointer 381 rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&); 382 383 node_pointer 384 rec_join(leaf_pointer, internal_node_pointer, size_type, 385 split_join_branch_bag&); 386 387 node_pointer 388 rec_join(internal_node_pointer, leaf_pointer, size_type, 389 split_join_branch_bag&); 390 391 node_pointer 392 rec_join(internal_node_pointer, internal_node_pointer, 393 split_join_branch_bag&); 394 395 size_type 396 keys_diff_ind(typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator); 397 398 internal_node_pointer 399 insert_branch(node_pointer, node_pointer, split_join_branch_bag&); 400 401 void 402 update_min_max_for_inserted_leaf(leaf_pointer); 403 404 void 405 erase_leaf(leaf_pointer); 406 407 inline void 408 actual_erase_leaf(leaf_pointer); 409 410 void 411 clear_imp(node_pointer); 412 413 void 414 erase_fixup(internal_node_pointer); 415 416 void 417 update_min_max_for_erased_leaf(leaf_pointer); 418 419 static inline const_e_iterator 420 pref_begin(const_node_pointer); 421 422 static inline const_e_iterator 423 pref_end(const_node_pointer); 424 425 inline node_pointer 426 find_imp(const_key_reference); 427 428 inline node_pointer 429 lower_bound_imp(const_key_reference); 430 431 inline node_pointer 432 upper_bound_imp(const_key_reference); 433 434 inline static const_leaf_pointer 435 leftmost_descendant(const_node_pointer); 436 437 inline static leaf_pointer 438 leftmost_descendant(node_pointer); 439 440 inline static const_leaf_pointer 441 rightmost_descendant(const_node_pointer); 442 443 inline static leaf_pointer 444 rightmost_descendant(node_pointer); 445 446 #ifdef _GLIBCXX_DEBUG 447 void 448 assert_valid() const; 449 450 void 451 assert_iterators() const; 452 453 void 454 assert_reverse_iterators() const; 455 456 static size_type 457 recursive_count_leafs(const_node_pointer); 458 #endif 459 460 #ifdef PB_DS_PAT_TRIE_TRACE_ 461 static void 462 trace_node(const_node_pointer, size_type); 463 464 template<typename Metadata_> 465 static void 466 trace_node_metadata(const_node_pointer, type_to_type<Metadata_>); 467 468 static void 469 trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>); 470 #endif 471 472 leaf_pointer 473 split_prep(const_key_reference, PB_DS_CLASS_C_DEC&, 474 split_join_branch_bag&); 475 476 node_pointer 477 rec_split(node_pointer, const_e_iterator, const_e_iterator, 478 PB_DS_CLASS_C_DEC&, split_join_branch_bag&); 479 480 void 481 split_insert_branch(size_type, const_e_iterator, 482 typename internal_node::iterator, 483 size_type, split_join_branch_bag&); 484 485 static head_allocator s_head_allocator; 486 static internal_node_allocator s_internal_node_allocator; 487 static leaf_allocator s_leaf_allocator; 488 489 head_pointer m_p_head; 490 size_type m_size; 491 }; 492 493 #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp> 494 #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp> 495 #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp> 496 #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp> 497 #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp> 498 #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp> 499 #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp> 500 #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp> 501 #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp> 502 #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp> 503 #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp> 504 505 #undef PB_DS_CLASS_C_DEC 506 #undef PB_DS_CLASS_T_DEC 507 #undef PB_DS_CLASS_NAME 508 #undef PB_DS_TYPES_TRAITS_C_DEC 509 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 510 #undef PB_DS_V2F 511 #undef PB_DS_EP2VP 512 #undef PB_DS_V2S 513 514 } // namespace detail 515 } // namespace __gnu_pbds 516
