libstdc++
pat_trie_.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the terms
00008 // of the GNU General Public License as published by the Free Software
00009 // Foundation; either version 3, or (at your option) any later
00010 // version.
00011 
00012 // This library is distributed in the hope that it will be useful, but
00013 // WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 // General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00027 
00028 // Permission to use, copy, modify, sell, and distribute this software
00029 // is hereby granted without fee, provided that the above copyright
00030 // notice appears in all copies, and that both that copyright notice
00031 // and this permission notice appear in supporting documentation. None
00032 // of the above authors, nor IBM Haifa Research Laboratories, make any
00033 // representation about the suitability of this software for any
00034 // purpose. It is provided "as is" without express or implied
00035 // warranty.
00036 
00037 /**
00038  * @file pat_trie_/pat_trie_.hpp
00039  * Contains an implementation class for a patricia tree.
00040  */
00041 
00042 #include <iterator>
00043 #include <utility>
00044 #include <algorithm>
00045 #include <functional>
00046 #include <assert.h>
00047 #include <list>
00048 #include <ext/pb_ds/exception.hpp>
00049 #include <ext/pb_ds/tag_and_trait.hpp>
00050 #include <ext/pb_ds/tree_policy.hpp>
00051 #include <ext/pb_ds/detail/cond_dealtor.hpp>
00052 #include <ext/pb_ds/detail/type_utils.hpp>
00053 #include <ext/pb_ds/detail/types_traits.hpp>
00054 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
00055 #include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp>
00056 #include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp>
00057 #ifdef _GLIBCXX_DEBUG
00058 #include <ext/pb_ds/detail/debug_map_base.hpp>
00059 #endif
00060 #include <debug/debug.h>
00061 
00062 namespace __gnu_pbds
00063 {
00064   namespace detail
00065   {
00066 #ifdef PB_DS_DATA_TRUE_INDICATOR
00067 #define PB_DS_PAT_TRIE_NAME pat_trie_map
00068 #endif
00069 
00070 #ifdef PB_DS_DATA_FALSE_INDICATOR
00071 #define PB_DS_PAT_TRIE_NAME pat_trie_set
00072 #endif
00073 
00074 #define PB_DS_CLASS_T_DEC \
00075     template<typename Key, typename Mapped, typename Node_And_It_Traits, \
00076          typename _Alloc>
00077 
00078 #define PB_DS_CLASS_C_DEC \
00079     PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc>
00080 
00081 #define PB_DS_PAT_TRIE_TRAITS_BASE \
00082     types_traits<Key, Mapped, _Alloc, false>
00083 
00084 #ifdef _GLIBCXX_DEBUG
00085 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
00086     debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \
00087          typename _Alloc::template rebind<Key>::other::const_reference>
00088 #endif
00089 
00090 
00091     /**
00092      *  @brief PATRICIA trie.
00093      *  @ingroup branch-detail
00094      *
00095      *  This implementation loosely borrows ideas from:
00096      *  1) Fast Mergeable Integer Maps, Okasaki, Gill 1998
00097      *  2) Ptset: Sets of integers implemented as Patricia trees,
00098      *     Jean-Christophe Filliatr, 2000
00099      */
00100     template<typename Key, typename Mapped, typename Node_And_It_Traits,
00101          typename _Alloc>
00102     class PB_DS_PAT_TRIE_NAME :
00103 #ifdef _GLIBCXX_DEBUG
00104       public PB_DS_DEBUG_MAP_BASE_C_DEC,
00105 #endif
00106       public Node_And_It_Traits::synth_access_traits,
00107       public Node_And_It_Traits::node_update,
00108       public PB_DS_PAT_TRIE_TRAITS_BASE,
00109       public pat_trie_base
00110     {
00111     private:
00112       typedef pat_trie_base             base_type;
00113       typedef PB_DS_PAT_TRIE_TRAITS_BASE            traits_base;
00114       typedef Node_And_It_Traits            traits_type;
00115 
00116       typedef typename traits_type::synth_access_traits synth_access_traits;
00117       typedef typename synth_access_traits::const_iterator a_const_iterator;
00118 
00119       typedef typename traits_type::node        node;
00120       typedef typename _Alloc::template rebind<node>    __rebind_n;
00121       typedef typename __rebind_n::other::const_pointer node_const_pointer;
00122       typedef typename __rebind_n::other::pointer   node_pointer;
00123 
00124       typedef typename traits_type::head        head;
00125       typedef typename _Alloc::template rebind<head>    __rebind_h;
00126       typedef typename __rebind_h::other        head_allocator;
00127       typedef typename head_allocator::pointer      head_pointer;
00128 
00129       typedef typename traits_type::leaf        leaf;
00130       typedef typename _Alloc::template rebind<leaf>    __rebind_l;
00131       typedef typename __rebind_l::other        leaf_allocator;
00132       typedef typename leaf_allocator::pointer      leaf_pointer;
00133       typedef typename leaf_allocator::const_pointer    leaf_const_pointer;
00134 
00135       typedef typename traits_type::inode       inode;
00136       typedef typename inode::iterator          inode_iterator;
00137       typedef typename _Alloc::template rebind<inode>   __rebind_in;
00138       typedef typename __rebind_in::other       __rebind_ina;
00139       typedef typename __rebind_in::other               inode_allocator;
00140       typedef typename __rebind_ina::pointer        inode_pointer;
00141       typedef typename __rebind_ina::const_pointer  inode_const_pointer;
00142 
00143 
00144       /// Conditional deallocator.
00145       class cond_dealtor
00146       {
00147       protected:
00148     leaf_pointer        m_p_nd;
00149     bool            m_no_action_dtor;
00150     bool            m_call_destructor;
00151 
00152       public:
00153     cond_dealtor(leaf_pointer p_nd)
00154     : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false)
00155     { }
00156 
00157     void
00158     set_no_action_dtor()
00159     { m_no_action_dtor = true; }
00160 
00161     void
00162     set_call_destructor()
00163     { m_call_destructor = true; }
00164 
00165     ~cond_dealtor()
00166     {
00167       if (m_no_action_dtor)
00168         return;
00169 
00170       if (m_call_destructor)
00171         m_p_nd->~leaf();
00172 
00173       s_leaf_allocator.deallocate(m_p_nd, 1);
00174     }
00175       };
00176 
00177 
00178       /// Branch bag, for split-join.
00179       class branch_bag
00180       {
00181       private:
00182     typedef inode_pointer                   __inp;
00183     typedef typename _Alloc::template rebind<__inp>::other  __rebind_inp;
00184 
00185 #ifdef _GLIBCXX_DEBUG
00186     typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp>  bag_type;
00187 #else
00188     typedef std::list<__inp, __rebind_inp>          bag_type;
00189 #endif
00190 
00191     bag_type                        m_bag;
00192       public:
00193     void
00194     add_branch()
00195     {
00196       inode_pointer p_nd = s_inode_allocator.allocate(1);
00197       __try
00198         {
00199           m_bag.push_back(p_nd);
00200         }
00201       __catch(...)
00202         {
00203           s_inode_allocator.deallocate(p_nd, 1);
00204           __throw_exception_again;
00205         }
00206     }
00207 
00208     inode_pointer
00209     get_branch()
00210     {
00211       _GLIBCXX_DEBUG_ASSERT(!m_bag.empty());
00212       inode_pointer p_nd = *m_bag.begin();
00213       m_bag.pop_front();
00214       return p_nd;
00215     }
00216 
00217     ~branch_bag()
00218     {
00219       while (!m_bag.empty())
00220         {
00221           inode_pointer p_nd = *m_bag.begin();
00222           s_inode_allocator.deallocate(p_nd, 1);
00223           m_bag.pop_front();
00224         }
00225     }
00226 
00227     inline bool
00228     empty() const
00229     { return m_bag.empty(); }
00230       };
00231 
00232 #ifdef _GLIBCXX_DEBUG
00233       typedef PB_DS_DEBUG_MAP_BASE_C_DEC        debug_base;
00234 #endif
00235 
00236       typedef typename traits_type::null_node_update_pointer null_node_update_pointer;
00237 
00238     public:
00239       typedef pat_trie_tag              container_category;
00240       typedef _Alloc                    allocator_type;
00241       typedef typename _Alloc::size_type        size_type;
00242       typedef typename _Alloc::difference_type      difference_type;
00243 
00244       typedef typename traits_base::key_type        key_type;
00245       typedef typename traits_base::key_pointer     key_pointer;
00246       typedef typename traits_base::key_const_pointer   key_const_pointer;
00247       typedef typename traits_base::key_reference   key_reference;
00248       typedef typename traits_base::key_const_reference key_const_reference;
00249       typedef typename traits_base::mapped_type     mapped_type;
00250       typedef typename traits_base::mapped_pointer  mapped_pointer;
00251       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
00252       typedef typename traits_base::mapped_reference    mapped_reference;
00253       typedef typename traits_base::mapped_const_reference mapped_const_reference;
00254       typedef typename traits_base::value_type      value_type;
00255       typedef typename traits_base::pointer         pointer;
00256       typedef typename traits_base::const_pointer   const_pointer;
00257       typedef typename traits_base::reference       reference;
00258       typedef typename traits_base::const_reference     const_reference;
00259 
00260       typedef typename traits_type::access_traits   access_traits;
00261       typedef typename traits_type::const_iterator  point_const_iterator;
00262       typedef typename traits_type::iterator        point_iterator;
00263       typedef point_const_iterator          const_iterator;
00264       typedef point_iterator                iterator;
00265 
00266       typedef typename traits_type::reverse_iterator    reverse_iterator;
00267       typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
00268       typedef typename traits_type::node_const_iterator node_const_iterator;
00269       typedef typename traits_type::node_iterator   node_iterator;
00270       typedef typename traits_type::node_update     node_update;
00271 
00272       PB_DS_PAT_TRIE_NAME();
00273 
00274       PB_DS_PAT_TRIE_NAME(const access_traits&);
00275 
00276       PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&);
00277 
00278       void
00279       swap(PB_DS_CLASS_C_DEC&);
00280 
00281       ~PB_DS_PAT_TRIE_NAME();
00282 
00283       inline bool
00284       empty() const;
00285 
00286       inline size_type
00287       size() const;
00288 
00289       inline size_type
00290       max_size() const;
00291 
00292       access_traits&
00293       get_access_traits();
00294 
00295       const access_traits&
00296       get_access_traits() const;
00297 
00298       node_update&
00299       get_node_update();
00300 
00301       const node_update&
00302       get_node_update() const;
00303 
00304       inline std::pair<point_iterator, bool>
00305       insert(const_reference);
00306 
00307       inline mapped_reference
00308       operator[](key_const_reference r_key)
00309       {
00310 #ifdef PB_DS_DATA_TRUE_INDICATOR
00311     return insert(std::make_pair(r_key, mapped_type())).first->second;
00312 #else
00313     insert(r_key);
00314     return traits_base::s_null_type;
00315 #endif
00316       }
00317 
00318       inline point_iterator
00319       find(key_const_reference);
00320 
00321       inline point_const_iterator
00322       find(key_const_reference) const;
00323 
00324       inline point_iterator
00325       lower_bound(key_const_reference);
00326 
00327       inline point_const_iterator
00328       lower_bound(key_const_reference) const;
00329 
00330       inline point_iterator
00331       upper_bound(key_const_reference);
00332 
00333       inline point_const_iterator
00334       upper_bound(key_const_reference) const;
00335 
00336       void
00337       clear();
00338 
00339       inline bool
00340       erase(key_const_reference);
00341 
00342       inline const_iterator
00343       erase(const_iterator);
00344 
00345 #ifdef PB_DS_DATA_TRUE_INDICATOR
00346       inline iterator
00347       erase(iterator);
00348 #endif
00349 
00350       inline const_reverse_iterator
00351       erase(const_reverse_iterator);
00352 
00353 #ifdef PB_DS_DATA_TRUE_INDICATOR
00354       inline reverse_iterator
00355       erase(reverse_iterator);
00356 #endif
00357 
00358       template<typename Pred>
00359       inline size_type
00360       erase_if(Pred);
00361 
00362       void
00363       join(PB_DS_CLASS_C_DEC&);
00364 
00365       void
00366       split(key_const_reference, PB_DS_CLASS_C_DEC&);
00367 
00368       inline iterator
00369       begin();
00370 
00371       inline const_iterator
00372       begin() const;
00373 
00374       inline iterator
00375       end();
00376 
00377       inline const_iterator
00378       end() const;
00379 
00380       inline reverse_iterator
00381       rbegin();
00382 
00383       inline const_reverse_iterator
00384       rbegin() const;
00385 
00386       inline reverse_iterator
00387       rend();
00388 
00389       inline const_reverse_iterator
00390       rend() const;
00391 
00392       /// Returns a const node_iterator corresponding to the node at the
00393       /// root of the tree.
00394       inline node_const_iterator
00395       node_begin() const;
00396 
00397       /// Returns a node_iterator corresponding to the node at the
00398       /// root of the tree.
00399       inline node_iterator
00400       node_begin();
00401 
00402       /// Returns a const node_iterator corresponding to a node just
00403       /// after a leaf of the tree.
00404       inline node_const_iterator
00405       node_end() const;
00406 
00407       /// Returns a node_iterator corresponding to a node just
00408       /// after a leaf of the tree.
00409       inline node_iterator
00410       node_end();
00411 
00412 #ifdef PB_DS_PAT_TRIE_TRACE_
00413       void
00414       trace() const;
00415 #endif
00416 
00417     protected:
00418       template<typename It>
00419       void
00420       copy_from_range(It, It);
00421 
00422       void
00423       value_swap(PB_DS_CLASS_C_DEC&);
00424 
00425       node_pointer
00426       recursive_copy_node(node_const_pointer);
00427 
00428     private:
00429       void
00430       initialize();
00431 
00432       inline void
00433       apply_update(node_pointer, null_node_update_pointer);
00434 
00435       template<typename Node_Update_>
00436       inline void
00437       apply_update(node_pointer, Node_Update_*);
00438 
00439       bool
00440       join_prep(PB_DS_CLASS_C_DEC&, branch_bag&);
00441 
00442       void
00443       rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&);
00444 
00445       void
00446       rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&);
00447 
00448       void
00449       rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&);
00450 
00451       void
00452       rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&);
00453 
00454       void
00455       rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&);
00456 
00457       node_pointer
00458       rec_join(node_pointer, node_pointer, size_type, branch_bag&);
00459 
00460       node_pointer
00461       rec_join(leaf_pointer, leaf_pointer, branch_bag&);
00462 
00463       node_pointer
00464       rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&);
00465 
00466       node_pointer
00467       rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&);
00468 
00469       node_pointer
00470       rec_join(inode_pointer, inode_pointer, branch_bag&);
00471 
00472       size_type
00473       keys_diff_ind(typename access_traits::const_iterator,
00474             typename access_traits::const_iterator,
00475             typename access_traits::const_iterator,
00476             typename access_traits::const_iterator);
00477 
00478       inode_pointer
00479       insert_branch(node_pointer, node_pointer, branch_bag&);
00480 
00481       void
00482       update_min_max_for_inserted_leaf(leaf_pointer);
00483 
00484       void
00485       erase_leaf(leaf_pointer);
00486 
00487       inline void
00488       actual_erase_leaf(leaf_pointer);
00489 
00490       void
00491       clear_imp(node_pointer);
00492 
00493       void
00494       erase_fixup(inode_pointer);
00495 
00496       void
00497       update_min_max_for_erased_leaf(leaf_pointer);
00498 
00499       static inline a_const_iterator
00500       pref_begin(node_const_pointer);
00501 
00502       static inline a_const_iterator
00503       pref_end(node_const_pointer);
00504 
00505       inline node_pointer
00506       find_imp(key_const_reference);
00507 
00508       inline node_pointer
00509       lower_bound_imp(key_const_reference);
00510 
00511       inline node_pointer
00512       upper_bound_imp(key_const_reference);
00513 
00514       inline static leaf_const_pointer
00515       leftmost_descendant(node_const_pointer);
00516 
00517       inline static leaf_pointer
00518       leftmost_descendant(node_pointer);
00519 
00520       inline static leaf_const_pointer
00521       rightmost_descendant(node_const_pointer);
00522 
00523       inline static leaf_pointer
00524       rightmost_descendant(node_pointer);
00525 
00526 #ifdef _GLIBCXX_DEBUG
00527       void
00528       assert_valid(const char*, int) const;
00529 
00530       void
00531       assert_iterators(const char*, int) const;
00532 
00533       void
00534       assert_reverse_iterators(const char*, int) const;
00535 
00536       static size_type
00537       recursive_count_leafs(node_const_pointer, const char*, int);
00538 #endif
00539 
00540 #ifdef PB_DS_PAT_TRIE_TRACE_
00541       static void
00542       trace_node(node_const_pointer, size_type);
00543 
00544       template<typename Metadata_>
00545       static void
00546       trace_node_metadata(node_const_pointer, type_to_type<Metadata_>);
00547 
00548       static void
00549       trace_node_metadata(node_const_pointer, type_to_type<null_type>);
00550 #endif
00551 
00552       leaf_pointer
00553       split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&);
00554 
00555       node_pointer
00556       rec_split(node_pointer, a_const_iterator, a_const_iterator,
00557         PB_DS_CLASS_C_DEC&, branch_bag&);
00558 
00559       void
00560       split_insert_branch(size_type, a_const_iterator, inode_iterator,
00561               size_type, branch_bag&);
00562 
00563       static head_allocator         s_head_allocator;
00564       static inode_allocator        s_inode_allocator;
00565       static leaf_allocator         s_leaf_allocator;
00566 
00567       head_pointer          m_p_head;
00568       size_type             m_size;
00569     };
00570 
00571 #define PB_DS_ASSERT_NODE_VALID(X) \
00572   _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);)
00573 
00574 #define PB_DS_RECURSIVE_COUNT_LEAFS(X) \
00575   recursive_count_leafs(X, __FILE__, __LINE__)
00576 
00577 #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp>
00578 #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp>
00579 #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp>
00580 #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp>
00581 #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp>
00582 #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp>
00583 #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp>
00584 #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp>
00585 #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp>
00586 #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp>
00587 #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp>
00588 
00589 #undef PB_DS_RECURSIVE_COUNT_LEAFS
00590 #undef PB_DS_ASSERT_NODE_VALID
00591 #undef PB_DS_CLASS_C_DEC
00592 #undef PB_DS_CLASS_T_DEC
00593 #undef PB_DS_PAT_TRIE_NAME
00594 #undef PB_DS_PAT_TRIE_TRAITS_BASE
00595 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
00596   } // namespace detail
00597 } // namespace __gnu_pbds