libstdc++
ov_tree_map_.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005-2015 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 ov_tree_map_/ov_tree_map_.hpp
00038  * Contains an implementation class for ov_tree.
00039  */
00040 
00041 #include <map>
00042 #include <set>
00043 #include <ext/pb_ds/exception.hpp>
00044 #include <ext/pb_ds/tree_policy.hpp>
00045 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
00046 #include <ext/pb_ds/detail/types_traits.hpp>
00047 #include <ext/pb_ds/detail/type_utils.hpp>
00048 #include <ext/pb_ds/detail/tree_trace_base.hpp>
00049 #ifdef _GLIBCXX_DEBUG
00050 #include <ext/pb_ds/detail/debug_map_base.hpp>
00051 #endif
00052 #include <utility>
00053 #include <functional>
00054 #include <algorithm>
00055 #include <vector>
00056 #include <assert.h>
00057 #include <debug/debug.h>
00058 
00059 namespace __gnu_pbds
00060 {
00061   namespace detail
00062   {
00063 #ifdef PB_DS_DATA_TRUE_INDICATOR
00064 #define PB_DS_OV_TREE_NAME ov_tree_map
00065 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_map
00066 #endif
00067 
00068 #ifdef PB_DS_DATA_FALSE_INDICATOR
00069 #define PB_DS_OV_TREE_NAME ov_tree_set
00070 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_set
00071 #endif
00072 
00073 #define PB_DS_CLASS_T_DEC \
00074     template<typename Key, typename Mapped, typename Cmp_Fn, \
00075              typename Node_And_It_Traits, typename _Alloc>
00076 
00077 #define PB_DS_CLASS_C_DEC \
00078    PB_DS_OV_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
00079 
00080 #define PB_DS_OV_TREE_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, Cmp_Fn>, \
00086         typename _Alloc::template rebind<Key>::other::const_reference>
00087 #endif
00088 
00089 #ifdef PB_DS_TREE_TRACE
00090 #define PB_DS_TREE_TRACE_BASE_C_DEC \
00091     tree_trace_base<typename Node_And_It_Traits::node_const_iterator,   \
00092                     typename Node_And_It_Traits::node_iterator,         \
00093                     Cmp_Fn, false, _Alloc>
00094 #endif
00095 
00096 #ifndef PB_DS_CHECK_KEY_EXISTS
00097 #  error Missing definition
00098 #endif
00099 
00100     /**
00101      *  @brief Ordered-vector tree associative-container.
00102      *  @ingroup branch-detail
00103      */
00104     template<typename Key, typename Mapped, typename Cmp_Fn,
00105              typename Node_And_It_Traits, typename _Alloc>
00106     class PB_DS_OV_TREE_NAME :
00107 #ifdef _GLIBCXX_DEBUG
00108       protected PB_DS_DEBUG_MAP_BASE_C_DEC,
00109 #endif
00110 #ifdef PB_DS_TREE_TRACE
00111       public PB_DS_TREE_TRACE_BASE_C_DEC,
00112 #endif
00113       public Cmp_Fn,
00114       public Node_And_It_Traits::node_update,
00115       public PB_DS_OV_TREE_TRAITS_BASE
00116     {
00117     private:
00118       typedef PB_DS_OV_TREE_TRAITS_BASE                 traits_base;
00119       typedef Node_And_It_Traits                        traits_type;
00120 
00121       typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type;
00122 
00123       typedef typename _Alloc::template rebind<non_const_value_type>::other value_allocator;
00124       typedef typename value_allocator::pointer         value_vector;
00125 
00126 #ifdef _GLIBCXX_DEBUG
00127       typedef PB_DS_DEBUG_MAP_BASE_C_DEC                debug_base;
00128 #endif
00129 
00130 #ifdef PB_DS_TREE_TRACE
00131       typedef PB_DS_TREE_TRACE_BASE_C_DEC               trace_base;
00132 #endif
00133 
00134       typedef typename traits_base::pointer             mapped_pointer_;
00135       typedef typename traits_base::const_pointer       mapped_const_pointer_;
00136 
00137       typedef typename traits_type::metadata_type       metadata_type;
00138 
00139       typedef typename _Alloc::template rebind<metadata_type>::other metadata_allocator;
00140       typedef typename metadata_allocator::pointer      metadata_pointer;
00141       typedef typename metadata_allocator::const_reference metadata_const_reference;
00142       typedef typename metadata_allocator::reference    metadata_reference;
00143 
00144       typedef typename traits_type::null_node_update_pointer
00145       null_node_update_pointer;
00146 
00147     public:
00148       typedef ov_tree_tag                                container_category;
00149       typedef _Alloc                                    allocator_type;
00150       typedef typename _Alloc::size_type                size_type;
00151       typedef typename _Alloc::difference_type          difference_type;
00152       typedef Cmp_Fn                                    cmp_fn;
00153 
00154       typedef typename traits_base::key_type            key_type;
00155       typedef typename traits_base::key_pointer         key_pointer;
00156       typedef typename traits_base::key_const_pointer   key_const_pointer;
00157       typedef typename traits_base::key_reference       key_reference;
00158       typedef typename traits_base::key_const_reference key_const_reference;
00159       typedef typename traits_base::mapped_type         mapped_type;
00160       typedef typename traits_base::mapped_pointer      mapped_pointer;
00161       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
00162       typedef typename traits_base::mapped_reference    mapped_reference;
00163       typedef typename traits_base::mapped_const_reference mapped_const_reference;
00164       typedef typename traits_base::value_type          value_type;
00165       typedef typename traits_base::pointer             pointer;
00166       typedef typename traits_base::const_pointer       const_pointer;
00167       typedef typename traits_base::reference           reference;
00168       typedef typename traits_base::const_reference     const_reference;
00169 
00170       typedef const_pointer                             point_const_iterator;
00171 #ifdef PB_DS_DATA_TRUE_INDICATOR
00172       typedef pointer                                   point_iterator;
00173 #else
00174       typedef point_const_iterator                      point_iterator;
00175 #endif
00176 
00177       typedef point_iterator                            iterator;
00178       typedef point_const_iterator                      const_iterator;
00179 
00180       /// Conditional destructor.
00181       template<typename Size_Type>
00182         class cond_dtor
00183         {
00184         public:
00185           cond_dtor(value_vector a_vec, iterator& r_last_it, 
00186                     Size_Type total_size) 
00187           : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size),
00188             m_no_action(false)
00189           { }
00190 
00191           ~cond_dtor()
00192           {
00193             if (m_no_action)
00194               return;
00195             iterator it = m_a_vec;
00196             while (it != m_r_last_it)
00197               {
00198                 it->~value_type();
00199                 ++it;
00200               }
00201             
00202             if (m_max_size > 0)
00203               value_allocator().deallocate(m_a_vec, m_max_size);
00204           }
00205 
00206           inline void
00207           set_no_action()
00208           { m_no_action = true; }
00209           
00210         protected:
00211           value_vector          m_a_vec;
00212           iterator&             m_r_last_it;
00213           const Size_Type       m_max_size;
00214           bool                  m_no_action;
00215        };
00216       
00217       typedef typename traits_type::node_update         node_update;
00218       typedef typename traits_type::node_iterator       node_iterator;
00219       typedef typename traits_type::node_const_iterator node_const_iterator;
00220 
00221 
00222       PB_DS_OV_TREE_NAME();
00223 
00224       PB_DS_OV_TREE_NAME(const Cmp_Fn&);
00225 
00226       PB_DS_OV_TREE_NAME(const Cmp_Fn&, const node_update&);
00227 
00228       PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC&);
00229 
00230       ~PB_DS_OV_TREE_NAME();
00231 
00232       void
00233       swap(PB_DS_CLASS_C_DEC&);
00234 
00235       template<typename It>
00236       void
00237       copy_from_range(It, It);
00238 
00239       inline size_type
00240       max_size() const;
00241 
00242       inline bool
00243       empty() const;
00244 
00245       inline size_type
00246       size() const;
00247 
00248       Cmp_Fn&
00249       get_cmp_fn();
00250 
00251       const Cmp_Fn&
00252       get_cmp_fn() const;
00253 
00254       inline mapped_reference
00255       operator[](key_const_reference r_key)
00256       {
00257 #ifdef PB_DS_DATA_TRUE_INDICATOR
00258         PB_DS_ASSERT_VALID((*this))
00259         point_iterator it = lower_bound(r_key);
00260         if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
00261           {
00262             PB_DS_CHECK_KEY_EXISTS(r_key)
00263             PB_DS_ASSERT_VALID((*this))
00264              return it->second;
00265           }
00266         return insert_new_val(it, std::make_pair(r_key, mapped_type()))->second;
00267 #else
00268         insert(r_key);
00269         return traits_base::s_null_type;
00270 #endif
00271       }
00272 
00273       inline std::pair<point_iterator, bool>
00274       insert(const_reference r_value)
00275       {
00276         PB_DS_ASSERT_VALID((*this))
00277         key_const_reference r_key = PB_DS_V2F(r_value);
00278         point_iterator it = lower_bound(r_key);
00279 
00280         if (it != end()&&  !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
00281           {
00282             PB_DS_ASSERT_VALID((*this))
00283             PB_DS_CHECK_KEY_EXISTS(r_key)
00284             return std::make_pair(it, false);
00285           }
00286 
00287         return std::make_pair(insert_new_val(it, r_value), true);
00288       }
00289 
00290       inline point_iterator
00291       lower_bound(key_const_reference r_key)
00292       {
00293         pointer it = m_a_values;
00294         pointer e_it = m_a_values + m_size;
00295         while (it != e_it)
00296           {
00297             pointer mid_it = it + ((e_it - it) >> 1);
00298             if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key))
00299               it = ++mid_it;
00300             else
00301               e_it = mid_it;
00302           }
00303         return it;
00304       }
00305 
00306       inline point_const_iterator
00307       lower_bound(key_const_reference r_key) const
00308       { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); }
00309 
00310       inline point_iterator
00311       upper_bound(key_const_reference r_key)
00312       {
00313         iterator pot_it = lower_bound(r_key);
00314         if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
00315           {
00316             PB_DS_CHECK_KEY_EXISTS(r_key)
00317             return ++pot_it;
00318           }
00319 
00320         PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
00321         return pot_it;
00322       }
00323 
00324       inline point_const_iterator
00325       upper_bound(key_const_reference r_key) const
00326       { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); }
00327 
00328       inline point_iterator
00329       find(key_const_reference r_key)
00330       {
00331         PB_DS_ASSERT_VALID((*this))
00332         iterator pot_it = lower_bound(r_key);
00333         if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
00334           {
00335             PB_DS_CHECK_KEY_EXISTS(r_key)
00336             return pot_it;
00337           }
00338 
00339         PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
00340         return end();
00341       }
00342 
00343       inline point_const_iterator
00344       find(key_const_reference r_key) const
00345       { return (const_cast<PB_DS_CLASS_C_DEC&>(*this).find(r_key)); }
00346 
00347       bool
00348       erase(key_const_reference);
00349 
00350       template<typename Pred>
00351       inline size_type
00352       erase_if(Pred);
00353 
00354       inline iterator
00355       erase(iterator it)
00356       { return erase_imp<iterator>(it); }
00357 
00358       void
00359       clear();
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       { return m_a_values; }
00370 
00371       inline const_iterator
00372       begin() const
00373       { return m_a_values; }
00374 
00375       inline iterator
00376       end()
00377       { return m_end_it; }
00378 
00379       inline const_iterator
00380       end() const
00381       { return m_end_it; }
00382 
00383       /// Returns a const node_iterator corresponding to the node at the
00384       /// root of the tree.
00385       inline node_const_iterator
00386       node_begin() const;
00387 
00388       /// Returns a node_iterator corresponding to the node at the
00389       /// root of the tree.
00390       inline node_iterator
00391       node_begin();
00392 
00393       /// Returns a const node_iterator corresponding to a node just
00394       /// after a leaf of the tree.
00395       inline node_const_iterator
00396       node_end() const;
00397 
00398       /// Returns a node_iterator corresponding to a node just
00399       /// after a leaf of the tree.
00400       inline node_iterator
00401       node_end();
00402 
00403     private:
00404 
00405       inline void
00406       update(node_iterator, null_node_update_pointer);
00407 
00408       template<typename Node_Update>
00409       void
00410       update(node_iterator, Node_Update*);
00411 
00412       void
00413       reallocate_metadata(null_node_update_pointer, size_type);
00414 
00415       template<typename Node_Update_>
00416       void
00417       reallocate_metadata(Node_Update_*, size_type);
00418 
00419       template<typename It>
00420       void
00421       copy_from_ordered_range(It, It);
00422 
00423       void
00424       value_swap(PB_DS_CLASS_C_DEC&);
00425 
00426       template<typename It>
00427       void
00428       copy_from_ordered_range(It, It, It, It);
00429 
00430       template<typename Ptr>
00431       inline static Ptr
00432       mid_pointer(Ptr p_begin, Ptr p_end)
00433       {
00434         _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
00435         return (p_begin + (p_end - p_begin) / 2);
00436       }
00437 
00438       inline iterator
00439       insert_new_val(iterator it, const_reference r_value)
00440       {
00441 #ifdef PB_DS_REGRESSION
00442         typename _Alloc::group_adjustor adjust(m_size);
00443 #endif
00444 
00445         PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_value))
00446 
00447         value_vector a_values = s_value_alloc.allocate(m_size + 1);
00448 
00449         iterator source_it = begin();
00450         iterator source_end_it = end();
00451         iterator target_it = a_values;
00452         iterator ret_it;
00453 
00454         cond_dtor<size_type> cd(a_values, target_it, m_size + 1);
00455         while (source_it != it)
00456           {
00457             new (const_cast<void*>(static_cast<const void*>(target_it)))
00458               value_type(*source_it++);
00459             ++target_it;
00460           }
00461 
00462         new (const_cast<void*>(static_cast<const void*>(ret_it = target_it)))
00463           value_type(r_value);
00464         ++target_it;
00465 
00466         while (source_it != source_end_it)
00467           {
00468             new (const_cast<void*>(static_cast<const void*>(target_it)))
00469               value_type(*source_it++);
00470             ++target_it;
00471           }
00472 
00473         reallocate_metadata((node_update*)this, m_size + 1);
00474         cd.set_no_action();
00475         if (m_size != 0)
00476           {
00477             cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
00478           }
00479 
00480         ++m_size;
00481         m_a_values = a_values;
00482         m_end_it = m_a_values + m_size;
00483         _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value)));
00484         update(node_begin(), (node_update* )this);
00485         PB_DS_ASSERT_VALID((*this))
00486         return ret_it;
00487       }
00488 
00489 #ifdef _GLIBCXX_DEBUG
00490       void
00491       assert_valid(const char*, int) const;
00492 
00493       void
00494       assert_iterators(const char*, int) const;
00495 #endif
00496 
00497       template<typename It>
00498       It
00499       erase_imp(It);
00500 
00501       inline node_const_iterator
00502       PB_DS_node_begin_imp() const;
00503 
00504       inline node_const_iterator
00505       PB_DS_node_end_imp() const;
00506 
00507       inline node_iterator
00508       PB_DS_node_begin_imp();
00509 
00510       inline node_iterator
00511       PB_DS_node_end_imp();
00512 
00513     private:
00514       static value_allocator    s_value_alloc;
00515       static metadata_allocator s_metadata_alloc;
00516 
00517       value_vector              m_a_values;
00518       metadata_pointer          m_a_metadata;
00519       iterator                  m_end_it;
00520       size_type                 m_size;
00521     };
00522 
00523 #include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp>
00524 #include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp>
00525 #include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp>
00526 #include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp>
00527 #include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp>
00528 #include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp>
00529 #include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp>
00530 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
00531 
00532 #undef PB_DS_CLASS_C_DEC
00533 #undef PB_DS_CLASS_T_DEC
00534 #undef PB_DS_OV_TREE_NAME
00535 #undef PB_DS_OV_TREE_TRAITS_BASE
00536 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
00537 #ifdef PB_DS_TREE_TRACE
00538 #undef PB_DS_TREE_TRACE_BASE_C_DEC
00539 #endif
00540 #undef PB_DS_CONST_NODE_ITERATOR_NAME
00541   } // namespace detail
00542 } // namespace __gnu_pbds