1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file pat_trie_.hpp 44169691Skan * Contains an implementation class for a patricia tree. 45169691Skan */ 46169691Skan 47169691Skan/** 48169691Skan * This implementation loosely borrows ideas from: 49169691Skan * 1) "Fast Mergeable Integer Maps", Okasaki, Gill 1998 50169691Skan * 2) "Ptset: Sets of integers implemented as Patricia trees", 51169691Skan * Jean-Christophe Filliatr, 2000 52169691Skan **/ 53169691Skan 54169691Skan#include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp> 55169691Skan#include <ext/pb_ds/detail/pat_trie_/node_base.hpp> 56169691Skan#include <ext/pb_ds/exception.hpp> 57169691Skan#include <ext/pb_ds/tag_and_trait.hpp> 58169691Skan#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 59169691Skan#include <ext/pb_ds/detail/types_traits.hpp> 60169691Skan#include <ext/pb_ds/tree_policy.hpp> 61169691Skan#include <ext/pb_ds/detail/cond_dealtor.hpp> 62169691Skan#include <ext/pb_ds/detail/type_utils.hpp> 63169691Skan#include <iterator> 64169691Skan#include <utility> 65169691Skan#include <algorithm> 66169691Skan#include <functional> 67169691Skan#include <assert.h> 68169691Skan#include <list> 69169691Skan#ifdef _GLIBCXX_DEBUG 70169691Skan#include <ext/pb_ds/detail/map_debug_base.hpp> 71169691Skan#endif 72169691Skan#include <debug/debug.h> 73169691Skan 74169691Skannamespace pb_ds 75169691Skan{ 76169691Skan namespace detail 77169691Skan { 78169691Skan#define PB_DS_CLASS_T_DEC \ 79169691Skan template<typename Key, typename Mapped, typename Node_And_It_Traits, \ 80169691Skan typename Allocator> 81169691Skan 82169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 83169691Skan#define PB_DS_CLASS_NAME pat_trie_data_ 84169691Skan#endif 85169691Skan 86169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 87169691Skan#define PB_DS_CLASS_NAME pat_trie_no_data_ 88169691Skan#endif 89169691Skan 90169691Skan#define PB_DS_CLASS_C_DEC \ 91169691Skan PB_DS_CLASS_NAME<Key, Mapped, Node_And_It_Traits, Allocator> 92169691Skan 93169691Skan#define PB_DS_TYPES_TRAITS_C_DEC \ 94169691Skan types_traits<Key, Mapped, Allocator, false> 95169691Skan 96169691Skan#ifdef _GLIBCXX_DEBUG 97169691Skan#define PB_DS_MAP_DEBUG_BASE_C_DEC \ 98169691Skan map_debug_base<Key, eq_by_less<Key, \ 99169691Skan std::less<Key> >, typename Allocator::template rebind<Key>::other::const_reference> 100169691Skan#endif 101169691Skan 102169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 103169691Skan#define PB_DS_V2F(X) (X).first 104169691Skan#define PB_DS_V2S(X) (X).second 105169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value) 106169691Skan#endif 107169691Skan 108169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 109169691Skan#define PB_DS_V2F(X) (X) 110169691Skan#define PB_DS_V2S(X) Mapped_Data() 111169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value.first) 112169691Skan#endif 113169691Skan 114169691Skan#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 115169691Skan typedef static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \ 116169691Skan UNIQUE##static_assert_type 117169691Skan 118169691Skan /** 119169691Skan * class description = PATRICIA trie implementation."> 120169691Skan **/ 121169691Skan template<typename Key, 122169691Skan typename Mapped, 123169691Skan typename Node_And_It_Traits, 124169691Skan typename Allocator> 125169691Skan class PB_DS_CLASS_NAME : 126169691Skan#ifdef _GLIBCXX_DEBUG 127169691Skan public PB_DS_MAP_DEBUG_BASE_C_DEC, 128169691Skan#endif 129169691Skan public Node_And_It_Traits::synth_e_access_traits, 130169691Skan public Node_And_It_Traits::node_update, 131169691Skan public PB_DS_TYPES_TRAITS_C_DEC 132169691Skan { 133169691Skan private: 134169691Skan typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 135169691Skan 136169691Skan typedef typename Node_And_It_Traits::synth_e_access_traits synth_e_access_traits; 137169691Skan typedef typename Allocator::template rebind<synth_e_access_traits>::other::const_pointer const_e_access_traits_pointer; 138169691Skan typedef typename synth_e_access_traits::const_iterator const_e_iterator; 139169691Skan 140169691Skan typedef typename Node_And_It_Traits::node node; 141169691Skan typedef typename Allocator::template rebind<node>::other::const_pointer const_node_pointer; 142169691Skan 143169691Skan typedef typename Allocator::template rebind<node>::other::pointer node_pointer; 144169691Skan 145169691Skan typedef typename Node_And_It_Traits::head head; 146169691Skan typedef typename Allocator::template rebind<head>::other head_allocator; 147169691Skan typedef typename head_allocator::pointer head_pointer; 148169691Skan 149169691Skan typedef typename Node_And_It_Traits::leaf leaf; 150169691Skan typedef typename Allocator::template rebind<leaf>::other leaf_allocator; 151169691Skan typedef typename leaf_allocator::const_pointer const_leaf_pointer; 152169691Skan typedef typename leaf_allocator::pointer leaf_pointer; 153169691Skan 154169691Skan typedef typename Node_And_It_Traits::internal_node internal_node; 155169691Skan typedef typename Allocator::template rebind<internal_node>::other internal_node_allocator; 156169691Skan typedef typename internal_node_allocator::const_pointer const_internal_node_pointer; 157169691Skan typedef typename internal_node_allocator::pointer internal_node_pointer; 158169691Skan 159169691Skan#include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp> 160169691Skan 161169691Skan#ifdef _GLIBCXX_DEBUG 162169691Skan typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; 163169691Skan#endif 164169691Skan 165169691Skan#include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp> 166169691Skan 167169691Skan typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer; 168169691Skan 169169691Skan public: 170169691Skan typedef pat_trie_tag container_category; 171169691Skan typedef Allocator allocator; 172169691Skan typedef typename Allocator::size_type size_type; 173169691Skan typedef typename Allocator::difference_type difference_type; 174169691Skan 175169691Skan typedef typename traits_base::key_type key_type; 176169691Skan typedef typename traits_base::key_pointer key_pointer; 177169691Skan typedef typename traits_base::const_key_pointer const_key_pointer; 178169691Skan typedef typename traits_base::key_reference key_reference; 179169691Skan typedef typename traits_base::const_key_reference const_key_reference; 180169691Skan typedef typename traits_base::mapped_type mapped_type; 181169691Skan typedef typename traits_base::mapped_pointer mapped_pointer; 182169691Skan typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 183169691Skan typedef typename traits_base::mapped_reference mapped_reference; 184169691Skan typedef typename traits_base::const_mapped_reference const_mapped_reference; 185169691Skan typedef typename traits_base::value_type value_type; 186169691Skan typedef typename traits_base::pointer pointer; 187169691Skan typedef typename traits_base::const_pointer const_pointer; 188169691Skan typedef typename traits_base::reference reference; 189169691Skan typedef typename traits_base::const_reference const_reference; 190169691Skan 191169691Skan typedef typename Node_And_It_Traits::const_iterator const_point_iterator; 192169691Skan typedef typename Node_And_It_Traits::iterator point_iterator; 193169691Skan typedef const_point_iterator const_iterator; 194169691Skan typedef point_iterator iterator; 195169691Skan 196169691Skan typedef typename Node_And_It_Traits::const_reverse_iterator const_reverse_iterator; 197169691Skan typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; 198169691Skan typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator; 199169691Skan typedef typename Node_And_It_Traits::node_iterator node_iterator; 200169691Skan typedef typename Node_And_It_Traits::e_access_traits e_access_traits; 201169691Skan typedef typename Node_And_It_Traits::node_update node_update; 202169691Skan 203169691Skan PB_DS_CLASS_NAME(); 204169691Skan 205169691Skan PB_DS_CLASS_NAME(const e_access_traits&); 206169691Skan 207169691Skan PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 208169691Skan 209169691Skan void 210169691Skan swap(PB_DS_CLASS_C_DEC&); 211169691Skan 212169691Skan ~PB_DS_CLASS_NAME(); 213169691Skan 214169691Skan inline bool 215169691Skan empty() const; 216169691Skan 217169691Skan inline size_type 218169691Skan size() const; 219169691Skan 220169691Skan inline size_type 221169691Skan max_size() const; 222169691Skan 223169691Skan e_access_traits& 224169691Skan get_e_access_traits(); 225169691Skan 226169691Skan const e_access_traits& 227169691Skan get_e_access_traits() const; 228169691Skan 229169691Skan node_update& 230169691Skan get_node_update(); 231169691Skan 232169691Skan const node_update& 233169691Skan get_node_update() const; 234169691Skan 235169691Skan inline std::pair<point_iterator, bool> 236169691Skan insert(const_reference); 237169691Skan 238169691Skan inline mapped_reference 239169691Skan operator[](const_key_reference r_key) 240169691Skan { 241169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 242169691Skan return insert(std::make_pair(r_key, mapped_type())).first->second; 243169691Skan#else 244169691Skan insert(r_key); 245169691Skan return traits_base::s_null_mapped; 246169691Skan#endif 247169691Skan } 248169691Skan 249169691Skan inline point_iterator 250169691Skan find(const_key_reference); 251169691Skan 252169691Skan inline const_point_iterator 253169691Skan find(const_key_reference) const; 254169691Skan 255169691Skan inline point_iterator 256169691Skan lower_bound(const_key_reference); 257169691Skan 258169691Skan inline const_point_iterator 259169691Skan lower_bound(const_key_reference) const; 260169691Skan 261169691Skan inline point_iterator 262169691Skan upper_bound(const_key_reference); 263169691Skan 264169691Skan inline const_point_iterator 265169691Skan upper_bound(const_key_reference) const; 266169691Skan 267169691Skan void 268169691Skan clear(); 269169691Skan 270169691Skan inline bool 271169691Skan erase(const_key_reference); 272169691Skan 273169691Skan inline const_iterator 274169691Skan erase(const_iterator); 275169691Skan 276169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 277169691Skan inline iterator 278169691Skan erase(iterator); 279169691Skan#endif 280169691Skan 281169691Skan inline const_reverse_iterator 282169691Skan erase(const_reverse_iterator); 283169691Skan 284169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 285169691Skan inline reverse_iterator 286169691Skan erase(reverse_iterator); 287169691Skan#endif 288169691Skan 289169691Skan template<typename Pred> 290169691Skan inline size_type 291169691Skan erase_if(Pred); 292169691Skan 293169691Skan void 294169691Skan join(PB_DS_CLASS_C_DEC&); 295169691Skan 296169691Skan void 297169691Skan split(const_key_reference, PB_DS_CLASS_C_DEC&); 298169691Skan 299169691Skan inline iterator 300169691Skan begin(); 301169691Skan 302169691Skan inline const_iterator 303169691Skan begin() const; 304169691Skan 305169691Skan inline iterator 306169691Skan end(); 307169691Skan 308169691Skan inline const_iterator 309169691Skan end() const; 310169691Skan 311169691Skan inline reverse_iterator 312169691Skan rbegin(); 313169691Skan 314169691Skan inline const_reverse_iterator 315169691Skan rbegin() const; 316169691Skan 317169691Skan inline reverse_iterator 318169691Skan rend(); 319169691Skan 320169691Skan inline const_reverse_iterator 321169691Skan rend() const; 322169691Skan 323169691Skan inline const_node_iterator 324169691Skan node_begin() const; 325169691Skan 326169691Skan inline node_iterator 327169691Skan node_begin(); 328169691Skan 329169691Skan inline const_node_iterator 330169691Skan node_end() const; 331169691Skan 332169691Skan inline node_iterator 333169691Skan node_end(); 334169691Skan 335169691Skan#ifdef PB_DS_PAT_TRIE_TRACE_ 336169691Skan void 337169691Skan trace() const; 338169691Skan#endif 339169691Skan 340169691Skan protected: 341169691Skan 342169691Skan template<typename It> 343169691Skan void 344169691Skan copy_from_range(It, It); 345169691Skan 346169691Skan void 347169691Skan value_swap(PB_DS_CLASS_C_DEC&); 348169691Skan 349169691Skan node_pointer 350169691Skan recursive_copy_node(const_node_pointer); 351169691Skan 352169691Skan private: 353169691Skan 354169691Skan void 355169691Skan initialize(); 356169691Skan 357169691Skan inline void 358169691Skan apply_update(node_pointer, null_node_update_pointer); 359169691Skan 360169691Skan template<typename Node_Update_> 361169691Skan inline void 362169691Skan apply_update(node_pointer, Node_Update_*); 363169691Skan 364169691Skan bool 365169691Skan join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&); 366169691Skan 367169691Skan void 368169691Skan rec_join_prep(const_node_pointer, const_node_pointer, 369169691Skan split_join_branch_bag&); 370169691Skan 371169691Skan void 372169691Skan rec_join_prep(const_leaf_pointer, const_leaf_pointer, 373169691Skan split_join_branch_bag&); 374169691Skan 375169691Skan void 376169691Skan rec_join_prep(const_leaf_pointer, const_internal_node_pointer, 377169691Skan split_join_branch_bag&); 378169691Skan 379169691Skan void 380169691Skan rec_join_prep(const_internal_node_pointer, const_leaf_pointer, 381169691Skan split_join_branch_bag&); 382169691Skan 383169691Skan void 384169691Skan rec_join_prep(const_internal_node_pointer, const_internal_node_pointer, 385169691Skan split_join_branch_bag&); 386169691Skan 387169691Skan node_pointer 388169691Skan rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&); 389169691Skan 390169691Skan node_pointer 391169691Skan rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&); 392169691Skan 393169691Skan node_pointer 394169691Skan rec_join(leaf_pointer, internal_node_pointer, size_type, 395169691Skan split_join_branch_bag&); 396169691Skan 397169691Skan node_pointer 398169691Skan rec_join(internal_node_pointer, leaf_pointer, size_type, 399169691Skan split_join_branch_bag&); 400169691Skan 401169691Skan node_pointer 402169691Skan rec_join(internal_node_pointer, internal_node_pointer, 403169691Skan split_join_branch_bag&); 404169691Skan 405169691Skan size_type 406169691Skan 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); 407169691Skan 408169691Skan internal_node_pointer 409169691Skan insert_branch(node_pointer, node_pointer, split_join_branch_bag&); 410169691Skan 411169691Skan void 412169691Skan update_min_max_for_inserted_leaf(leaf_pointer); 413169691Skan 414169691Skan void 415169691Skan erase_leaf(leaf_pointer); 416169691Skan 417169691Skan inline void 418169691Skan actual_erase_leaf(leaf_pointer); 419169691Skan 420169691Skan void 421169691Skan clear_imp(node_pointer); 422169691Skan 423169691Skan void 424169691Skan erase_fixup(internal_node_pointer); 425169691Skan 426169691Skan void 427169691Skan update_min_max_for_erased_leaf(leaf_pointer); 428169691Skan 429169691Skan static inline const_e_iterator 430169691Skan pref_begin(const_node_pointer); 431169691Skan 432169691Skan static inline const_e_iterator 433169691Skan pref_end(const_node_pointer); 434169691Skan 435169691Skan inline node_pointer 436169691Skan find_imp(const_key_reference); 437169691Skan 438169691Skan inline node_pointer 439169691Skan lower_bound_imp(const_key_reference); 440169691Skan 441169691Skan inline node_pointer 442169691Skan upper_bound_imp(const_key_reference); 443169691Skan 444169691Skan inline static const_leaf_pointer 445169691Skan leftmost_descendant(const_node_pointer); 446169691Skan 447169691Skan inline static leaf_pointer 448169691Skan leftmost_descendant(node_pointer); 449169691Skan 450169691Skan inline static const_leaf_pointer 451169691Skan rightmost_descendant(const_node_pointer); 452169691Skan 453169691Skan inline static leaf_pointer 454169691Skan rightmost_descendant(node_pointer); 455169691Skan 456169691Skan#ifdef _GLIBCXX_DEBUG 457169691Skan void 458169691Skan assert_valid() const; 459169691Skan 460169691Skan void 461169691Skan assert_iterators() const; 462169691Skan 463169691Skan void 464169691Skan assert_reverse_iterators() const; 465169691Skan 466169691Skan static size_type 467169691Skan recursive_count_leafs(const_node_pointer); 468169691Skan#endif 469169691Skan 470169691Skan#ifdef PB_DS_PAT_TRIE_TRACE_ 471169691Skan static void 472169691Skan trace_node(const_node_pointer, size_type); 473169691Skan 474169691Skan template<typename Metadata_> 475169691Skan static void 476169691Skan trace_node_metadata(const_node_pointer, type_to_type<Metadata_>); 477169691Skan 478169691Skan static void 479169691Skan trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>); 480169691Skan#endif 481169691Skan 482169691Skan leaf_pointer 483169691Skan split_prep(const_key_reference, PB_DS_CLASS_C_DEC&, 484169691Skan split_join_branch_bag&); 485169691Skan 486169691Skan node_pointer 487169691Skan rec_split(node_pointer, const_e_iterator, const_e_iterator, 488169691Skan PB_DS_CLASS_C_DEC&, split_join_branch_bag&); 489169691Skan 490169691Skan void 491169691Skan split_insert_branch(size_type, const_e_iterator, 492169691Skan typename internal_node::iterator, 493169691Skan size_type, split_join_branch_bag&); 494169691Skan 495169691Skan static head_allocator s_head_allocator; 496169691Skan static internal_node_allocator s_internal_node_allocator; 497169691Skan static leaf_allocator s_leaf_allocator; 498169691Skan 499169691Skan head_pointer m_p_head; 500169691Skan size_type m_size; 501169691Skan }; 502169691Skan 503169691Skan#include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp> 504169691Skan#include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp> 505169691Skan#include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp> 506169691Skan#include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp> 507169691Skan#include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp> 508169691Skan#include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp> 509169691Skan#include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp> 510169691Skan#include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp> 511169691Skan#include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp> 512169691Skan#include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp> 513169691Skan#include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp> 514169691Skan 515169691Skan#undef PB_DS_CLASS_C_DEC 516169691Skan#undef PB_DS_CLASS_T_DEC 517169691Skan#undef PB_DS_CLASS_NAME 518169691Skan#undef PB_DS_TYPES_TRAITS_C_DEC 519169691Skan#undef PB_DS_MAP_DEBUG_BASE_C_DEC 520169691Skan#undef PB_DS_V2F 521169691Skan#undef PB_DS_EP2VP 522169691Skan#undef PB_DS_V2S 523169691Skan#undef PB_DS_STATIC_ASSERT 524169691Skan 525169691Skan } // namespace detail 526169691Skan} // namespace pb_ds 527