libstdc++
pat_trie_.hpp
Go to the documentation of this file.
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