libstdc++
bin_search_tree_.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 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 bin_search_tree_/bin_search_tree_.hpp
00038  *  Contains an implementation class for binary search tree.
00039  */
00040 
00041 #include <ext/pb_ds/exception.hpp>
00042 #include <ext/pb_ds/tree_policy.hpp>
00043 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
00044 #include <ext/pb_ds/detail/types_traits.hpp>
00045 #include <ext/pb_ds/detail/cond_dealtor.hpp>
00046 #include <ext/pb_ds/detail/type_utils.hpp>
00047 #include <ext/pb_ds/detail/tree_trace_base.hpp>
00048 #ifdef _GLIBCXX_DEBUG
00049 #include <ext/pb_ds/detail/debug_map_base.hpp>
00050 #endif
00051 #include <utility>
00052 #include <functional>
00053 #include <debug/debug.h>
00054 
00055 namespace __gnu_pbds
00056 {
00057   namespace detail
00058   {
00059 #ifdef PB_DS_DATA_TRUE_INDICATOR
00060 #define PB_DS_BIN_TREE_NAME bin_search_tree_map
00061 #endif
00062 
00063 #ifdef PB_DS_DATA_FALSE_INDICATOR
00064 #define PB_DS_BIN_TREE_NAME bin_search_tree_set
00065 #endif
00066 
00067 #define PB_DS_CLASS_T_DEC \
00068     template<typename Key, typename Mapped, typename Cmp_Fn, \
00069          typename Node_And_It_Traits, typename _Alloc>
00070 
00071 #define PB_DS_CLASS_C_DEC \
00072     PB_DS_BIN_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
00073 
00074 #define PB_DS_BIN_TREE_TRAITS_BASE \
00075     types_traits<Key, Mapped, _Alloc, false>
00076 
00077 #ifdef _GLIBCXX_DEBUG
00078 #define PB_DS_DEBUG_MAP_BASE_C_DEC  \
00079     debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
00080           typename _Alloc::template rebind<Key>::other::const_reference>
00081 #endif
00082 
00083 #ifdef PB_DS_TREE_TRACE
00084 #define PB_DS_TREE_TRACE_BASE_C_DEC \
00085     tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \
00086             typename Node_And_It_Traits::node_iterator,       \
00087             Cmp_Fn, true, _Alloc>
00088 #endif
00089 
00090 
00091     /*
00092      *  @brief Binary search tree (BST).
00093      *
00094      *  This implementation uses an idea from the SGI STL (using a @a
00095      *  header node which is needed for efficient iteration).
00096      */
00097     template<typename Key, typename Mapped, typename Cmp_Fn,
00098          typename Node_And_It_Traits, typename _Alloc>
00099     class PB_DS_BIN_TREE_NAME :
00100 #ifdef _GLIBCXX_DEBUG
00101       public PB_DS_DEBUG_MAP_BASE_C_DEC,
00102 #endif
00103 #ifdef PB_DS_TREE_TRACE
00104       public PB_DS_TREE_TRACE_BASE_C_DEC,
00105 #endif
00106       public Cmp_Fn,
00107       public PB_DS_BIN_TREE_TRAITS_BASE,
00108       public Node_And_It_Traits::node_update
00109     {
00110       typedef Node_And_It_Traits            traits_type;
00111 
00112     protected:
00113       typedef PB_DS_BIN_TREE_TRAITS_BASE            traits_base;
00114 
00115       typedef
00116       typename _Alloc::template rebind<typename traits_type::node>::other
00117       node_allocator;
00118 
00119       typedef typename node_allocator::value_type   node;
00120       typedef typename node_allocator::pointer      node_pointer;
00121 
00122       typedef typename traits_type::null_node_update_pointer
00123       null_node_update_pointer;
00124 
00125     private:
00126       typedef cond_dealtor<node, _Alloc>        cond_dealtor_t;
00127 
00128 #ifdef _GLIBCXX_DEBUG
00129       typedef PB_DS_DEBUG_MAP_BASE_C_DEC        debug_base;
00130 #endif
00131 
00132     public:
00133       typedef typename _Alloc::size_type        size_type;
00134       typedef typename _Alloc::difference_type  difference_type;
00135       typedef typename traits_base::key_type        key_type;
00136       typedef typename traits_base::key_pointer     key_pointer;
00137       typedef typename traits_base::key_const_pointer   key_const_pointer;
00138       typedef typename traits_base::key_reference   key_reference;
00139       typedef typename traits_base::key_const_reference key_const_reference;
00140 
00141 #ifdef PB_DS_DATA_TRUE_INDICATOR
00142       typedef typename traits_base::mapped_type     mapped_type;
00143       typedef typename traits_base::mapped_pointer  mapped_pointer;
00144       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
00145       typedef typename traits_base::mapped_reference    mapped_reference;
00146       typedef typename traits_base::mapped_const_reference mapped_const_reference;
00147 #endif
00148 
00149       typedef typename traits_base::value_type      value_type;
00150       typedef typename traits_base::pointer         pointer;
00151       typedef typename traits_base::const_pointer   const_pointer;
00152       typedef typename traits_base::reference       reference;
00153       typedef typename traits_base::const_reference     const_reference;
00154       typedef typename traits_type::point_const_iterator point_const_iterator;
00155 
00156       typedef point_const_iterator          const_iterator;
00157       typedef typename traits_type::point_iterator  point_iterator;
00158       typedef point_iterator                iterator;
00159 
00160       typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
00161 
00162       typedef typename traits_type::reverse_iterator    reverse_iterator;
00163       typedef typename traits_type::node_const_iterator node_const_iterator;
00164       typedef typename traits_type::node_iterator   node_iterator;
00165       typedef typename traits_type::node_update     node_update;
00166 
00167       typedef Cmp_Fn                    cmp_fn;
00168       typedef _Alloc                    allocator_type;
00169 
00170       PB_DS_BIN_TREE_NAME();
00171 
00172       PB_DS_BIN_TREE_NAME(const Cmp_Fn&);
00173 
00174       PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&);
00175 
00176       PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&);
00177 
00178       void
00179       swap(PB_DS_CLASS_C_DEC&);
00180 
00181       ~PB_DS_BIN_TREE_NAME();
00182 
00183       inline bool
00184       empty() const;
00185 
00186       inline size_type
00187       size() const;
00188 
00189       inline size_type
00190       max_size() const;
00191 
00192       Cmp_Fn&
00193       get_cmp_fn();
00194 
00195       const Cmp_Fn&
00196       get_cmp_fn() const;
00197 
00198       inline point_iterator
00199       lower_bound(key_const_reference);
00200 
00201       inline point_const_iterator
00202       lower_bound(key_const_reference) const;
00203 
00204       inline point_iterator
00205       upper_bound(key_const_reference);
00206 
00207       inline point_const_iterator
00208       upper_bound(key_const_reference) const;
00209 
00210       inline point_iterator
00211       find(key_const_reference);
00212 
00213       inline point_const_iterator
00214       find(key_const_reference) const;
00215 
00216       inline iterator
00217       begin();
00218 
00219       inline const_iterator
00220       begin() const;
00221 
00222       inline iterator
00223       end();
00224 
00225       inline const_iterator
00226       end() const;
00227 
00228       inline reverse_iterator
00229       rbegin();
00230 
00231       inline const_reverse_iterator
00232       rbegin() const;
00233 
00234       inline reverse_iterator
00235       rend();
00236 
00237       inline const_reverse_iterator
00238       rend() const;
00239 
00240       /// Returns a const node_iterator corresponding to the node at the
00241       /// root of the tree.
00242       inline node_const_iterator
00243       node_begin() const;
00244 
00245       /// Returns a node_iterator corresponding to the node at the
00246       /// root of the tree.
00247       inline node_iterator
00248       node_begin();
00249 
00250       /// Returns a const node_iterator corresponding to a node just
00251       /// after a leaf of the tree.
00252       inline node_const_iterator
00253       node_end() const;
00254 
00255       /// Returns a node_iterator corresponding to a node just
00256       /// after a leaf of the tree.
00257       inline node_iterator
00258       node_end();
00259 
00260       void
00261       clear();
00262 
00263     protected:
00264       void
00265       value_swap(PB_DS_CLASS_C_DEC&);
00266 
00267       void
00268       initialize_min_max();
00269 
00270       inline iterator
00271       insert_imp_empty(const_reference);
00272 
00273       inline iterator
00274       insert_leaf_new(const_reference, node_pointer, bool);
00275 
00276       inline node_pointer
00277       get_new_node_for_leaf_insert(const_reference, false_type);
00278 
00279       inline node_pointer
00280       get_new_node_for_leaf_insert(const_reference, true_type);
00281 
00282       inline void
00283       actual_erase_node(node_pointer);
00284 
00285       inline std::pair<node_pointer, bool>
00286       erase(node_pointer);
00287 
00288       inline void
00289       update_min_max_for_erased_node(node_pointer);
00290 
00291       static void
00292       clear_imp(node_pointer);
00293 
00294       inline std::pair<point_iterator, bool>
00295       insert_leaf(const_reference);
00296 
00297       inline void
00298       rotate_left(node_pointer);
00299 
00300       inline void
00301       rotate_right(node_pointer);
00302 
00303       inline void
00304       rotate_parent(node_pointer);
00305 
00306       inline void
00307       apply_update(node_pointer, null_node_update_pointer);
00308 
00309       template<typename Node_Update_>
00310     inline void
00311     apply_update(node_pointer, Node_Update_*);
00312 
00313       inline void
00314       update_to_top(node_pointer, null_node_update_pointer);
00315 
00316       template<typename Node_Update_>
00317     inline void
00318     update_to_top(node_pointer, Node_Update_*);
00319 
00320       bool
00321       join_prep(PB_DS_CLASS_C_DEC&);
00322 
00323       void
00324       join_finish(PB_DS_CLASS_C_DEC&);
00325 
00326       bool
00327       split_prep(key_const_reference, PB_DS_CLASS_C_DEC&);
00328 
00329       void
00330       split_finish(PB_DS_CLASS_C_DEC&);
00331 
00332       size_type
00333       recursive_count(node_pointer) const;
00334 
00335 #ifdef _GLIBCXX_DEBUG
00336       void
00337       assert_valid(const char*, int) const;
00338 
00339       void
00340       structure_only_assert_valid(const char*, int) const;
00341 
00342       void
00343       assert_node_consistent(const node_pointer, const char*, int) const;
00344 #endif
00345 
00346     private:
00347 #ifdef _GLIBCXX_DEBUG
00348       void
00349       assert_iterators(const char*, int) const;
00350 
00351       void
00352       assert_consistent_with_debug_base(const char*, int) const;
00353 
00354       void
00355       assert_node_consistent_with_left(const node_pointer,
00356                        const char*, int) const;
00357 
00358       void
00359       assert_node_consistent_with_right(const node_pointer,
00360                     const char*, int) const;
00361 
00362       void
00363       assert_consistent_with_debug_base(const node_pointer,
00364                     const char*, int) const;
00365 
00366       void
00367       assert_min(const char*, int) const;
00368 
00369       void
00370       assert_min_imp(const node_pointer, const char*, int) const;
00371 
00372       void
00373       assert_max(const char*, int) const;
00374 
00375       void
00376       assert_max_imp(const node_pointer, const char*, int) const;
00377 
00378       void
00379       assert_size(const char*, int) const;
00380 
00381       typedef std::pair<const_pointer, const_pointer> node_consistent_t;
00382 
00383       node_consistent_t
00384       assert_node_consistent_(const node_pointer, const char*, int) const;
00385 #endif
00386 
00387       void
00388       initialize();
00389 
00390       node_pointer
00391       recursive_copy_node(const node_pointer);
00392 
00393     protected:
00394       node_pointer      m_p_head;
00395       size_type         m_size;
00396       static node_allocator     s_node_allocator;
00397     };
00398 
00399 #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X)               \
00400   _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);)
00401 
00402 #define PB_DS_ASSERT_NODE_CONSISTENT(_Node)             \
00403   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, __FILE__, __LINE__);)
00404 
00405 #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
00406 #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
00407 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
00408 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
00409 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
00410 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
00411 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
00412 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
00413 #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
00414 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
00415 
00416 #undef PB_DS_ASSERT_NODE_CONSISTENT
00417 #undef PB_DS_STRUCT_ONLY_ASSERT_VALID
00418 #undef PB_DS_CLASS_C_DEC
00419 #undef PB_DS_CLASS_T_DEC
00420 #undef PB_DS_BIN_TREE_NAME
00421 #undef PB_DS_BIN_TREE_TRAITS_BASE
00422 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
00423 
00424 #ifdef PB_DS_TREE_TRACE
00425 #undef PB_DS_TREE_TRACE_BASE_C_DEC
00426 #endif
00427   } // namespace detail
00428 } // namespace __gnu_pbds