1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2007, 2009 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 68namespace __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