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