libstdc++
lu_map_.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 list_update_map_/lu_map_.hpp
00038  * Contains a list update map.
00039  */
00040 
00041 #include <utility>
00042 #include <iterator>
00043 #include <ext/pb_ds/detail/cond_dealtor.hpp>
00044 #include <ext/pb_ds/tag_and_trait.hpp>
00045 #include <ext/pb_ds/detail/types_traits.hpp>
00046 #include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp>
00047 #include <ext/pb_ds/exception.hpp>
00048 #ifdef _GLIBCXX_DEBUG
00049 #include <ext/pb_ds/detail/debug_map_base.hpp>
00050 #endif
00051 #ifdef PB_DS_LU_MAP_TRACE_
00052 #include <iostream>
00053 #endif
00054 #include <debug/debug.h>
00055 
00056 namespace __gnu_pbds
00057 {
00058   namespace detail
00059   {
00060 #ifdef PB_DS_DATA_TRUE_INDICATOR
00061 #define PB_DS_LU_NAME lu_map
00062 #endif
00063 
00064 #ifdef PB_DS_DATA_FALSE_INDICATOR
00065 #define PB_DS_LU_NAME lu_set
00066 #endif
00067 
00068 #define PB_DS_CLASS_T_DEC \
00069     template<typename Key, typename Mapped, typename Eq_Fn, \
00070          typename _Alloc, typename Update_Policy>
00071 
00072 #define PB_DS_CLASS_C_DEC \
00073     PB_DS_LU_NAME<Key, Mapped, Eq_Fn, _Alloc, Update_Policy>
00074 
00075 #define PB_DS_LU_TRAITS_BASE \
00076     types_traits<Key, Mapped, _Alloc, false>
00077 
00078 #ifdef _GLIBCXX_DEBUG
00079 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
00080     debug_map_base<Key, Eq_Fn, \
00081           typename _Alloc::template rebind<Key>::other::const_reference>
00082 #endif
00083 
00084     /// list-based (with updates) associative container.
00085     /// Skip to the lu, my darling.
00086     template<typename Key,
00087          typename Mapped,
00088          typename Eq_Fn,
00089          typename _Alloc,
00090          typename Update_Policy>
00091     class PB_DS_LU_NAME :
00092 #ifdef _GLIBCXX_DEBUG
00093       protected PB_DS_DEBUG_MAP_BASE_C_DEC,
00094 #endif
00095       public PB_DS_LU_TRAITS_BASE
00096     {
00097     private:
00098       typedef PB_DS_LU_TRAITS_BASE          traits_base;
00099 
00100       struct entry
00101      : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
00102       {
00103     typename traits_base::value_type m_value;
00104     typename _Alloc::template rebind<entry>::other::pointer m_p_next;
00105       };
00106 
00107       typedef typename _Alloc::template rebind<entry>::other entry_allocator;
00108       typedef typename entry_allocator::pointer entry_pointer;
00109       typedef typename entry_allocator::const_pointer const_entry_pointer;
00110       typedef typename entry_allocator::reference entry_reference;
00111       typedef typename entry_allocator::const_reference const_entry_reference;
00112 
00113       typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator;
00114       typedef typename entry_pointer_allocator::pointer entry_pointer_array;
00115 
00116       typedef typename traits_base::value_type value_type_;
00117       typedef typename traits_base::pointer pointer_;
00118       typedef typename traits_base::const_pointer const_pointer_;
00119       typedef typename traits_base::reference reference_;
00120       typedef typename traits_base::const_reference const_reference_;
00121 
00122 #define PB_DS_GEN_POS entry_pointer
00123 
00124 #include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp>
00125 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
00126 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
00127 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
00128 
00129 #undef PB_DS_GEN_POS
00130 
00131 
00132 #ifdef _GLIBCXX_DEBUG
00133       typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
00134 #endif
00135 
00136       typedef cond_dealtor<entry, _Alloc> cond_dealtor_t;
00137 
00138     public:
00139       typedef _Alloc allocator_type;
00140       typedef typename _Alloc::size_type size_type;
00141       typedef typename _Alloc::difference_type difference_type;
00142       typedef Eq_Fn eq_fn;
00143       typedef Update_Policy update_policy;
00144       typedef typename Update_Policy::metadata_type update_metadata;
00145       typedef typename traits_base::key_type key_type;
00146       typedef typename traits_base::key_pointer key_pointer;
00147       typedef typename traits_base::key_const_pointer key_const_pointer;
00148       typedef typename traits_base::key_reference key_reference;
00149       typedef typename traits_base::key_const_reference key_const_reference;
00150       typedef typename traits_base::mapped_type mapped_type;
00151       typedef typename traits_base::mapped_pointer mapped_pointer;
00152       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
00153       typedef typename traits_base::mapped_reference mapped_reference;
00154       typedef typename traits_base::mapped_const_reference mapped_const_reference;
00155       typedef typename traits_base::value_type value_type;
00156       typedef typename traits_base::pointer pointer;
00157       typedef typename traits_base::const_pointer const_pointer;
00158       typedef typename traits_base::reference reference;
00159       typedef typename traits_base::const_reference const_reference;
00160 
00161 #ifdef PB_DS_DATA_TRUE_INDICATOR
00162       typedef point_iterator_           point_iterator;
00163 #endif
00164 
00165 #ifdef PB_DS_DATA_FALSE_INDICATOR
00166       typedef point_const_iterator_         point_iterator;
00167 #endif
00168 
00169       typedef point_const_iterator_         point_const_iterator;
00170 
00171 #ifdef PB_DS_DATA_TRUE_INDICATOR
00172       typedef iterator_             iterator;
00173 #endif
00174 
00175 #ifdef PB_DS_DATA_FALSE_INDICATOR
00176       typedef const_iterator_           iterator;
00177 #endif
00178 
00179       typedef const_iterator_           const_iterator;
00180 
00181     public:
00182       PB_DS_LU_NAME();
00183 
00184       PB_DS_LU_NAME(const PB_DS_CLASS_C_DEC&);
00185 
00186       virtual
00187       ~PB_DS_LU_NAME();
00188 
00189       template<typename It>
00190       PB_DS_LU_NAME(It, It);
00191 
00192       void
00193       swap(PB_DS_CLASS_C_DEC&);
00194 
00195       inline size_type
00196       size() const;
00197 
00198       inline size_type
00199       max_size() const;
00200 
00201       inline bool
00202       empty() const;
00203 
00204       inline mapped_reference
00205       operator[](key_const_reference r_key)
00206       {
00207 #ifdef PB_DS_DATA_TRUE_INDICATOR
00208     _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
00209     return insert(std::make_pair(r_key, mapped_type())).first->second;
00210 #else
00211     insert(r_key);
00212     return traits_base::s_null_type;
00213 #endif
00214       }
00215 
00216       inline std::pair<point_iterator, bool>
00217       insert(const_reference);
00218 
00219       inline point_iterator
00220       find(key_const_reference r_key)
00221       {
00222     _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
00223     entry_pointer p_e = find_imp(r_key);
00224     return point_iterator(p_e == 0 ? 0: &p_e->m_value);
00225       }
00226 
00227       inline point_const_iterator
00228       find(key_const_reference r_key) const
00229       {
00230     _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
00231     entry_pointer p_e = find_imp(r_key);
00232     return point_const_iterator(p_e == 0 ? 0: &p_e->m_value);
00233       }
00234 
00235       inline bool
00236       erase(key_const_reference);
00237 
00238       template<typename Pred>
00239       inline size_type
00240       erase_if(Pred);
00241 
00242       void
00243       clear();
00244 
00245       inline iterator
00246       begin();
00247 
00248       inline const_iterator
00249       begin() const;
00250 
00251       inline iterator
00252       end();
00253 
00254       inline const_iterator
00255       end() const;
00256 
00257 #ifdef _GLIBCXX_DEBUG
00258       void
00259       assert_valid(const char* file, int line) const;
00260 #endif
00261 
00262 #ifdef PB_DS_LU_MAP_TRACE_
00263       void
00264       trace() const;
00265 #endif
00266 
00267     protected:
00268 
00269       template<typename It>
00270       void
00271       copy_from_range(It, It);
00272 
00273     private:
00274 #ifdef PB_DS_DATA_TRUE_INDICATOR
00275       friend class iterator_;
00276 #endif
00277 
00278       friend class const_iterator_;
00279 
00280       inline entry_pointer
00281       allocate_new_entry(const_reference, false_type);
00282 
00283       inline entry_pointer
00284       allocate_new_entry(const_reference, true_type);
00285 
00286       template<typename Metadata>
00287       inline static void
00288       init_entry_metadata(entry_pointer, type_to_type<Metadata>);
00289 
00290       inline static void
00291       init_entry_metadata(entry_pointer, type_to_type<null_type>);
00292 
00293       void
00294       deallocate_all();
00295 
00296       void
00297       erase_next(entry_pointer);
00298 
00299       void
00300       actual_erase_entry(entry_pointer);
00301 
00302       void
00303       inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const
00304       {
00305     r_pos = r_pos->m_p_next;
00306     r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value;
00307       }
00308 
00309       template<typename Metadata>
00310       inline static bool
00311       apply_update(entry_pointer, type_to_type<Metadata>);
00312 
00313       inline static bool
00314       apply_update(entry_pointer, type_to_type<null_type>);
00315 
00316       inline entry_pointer
00317       find_imp(key_const_reference) const;
00318 
00319       static entry_allocator            s_entry_allocator;
00320       static Eq_Fn              s_eq_fn;
00321       static Update_Policy          s_update_policy;
00322       static type_to_type<update_metadata>  s_metadata_type_indicator;
00323       static null_type              s_null_type;
00324 
00325       mutable entry_pointer             m_p_l;
00326     };
00327 
00328 #include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp>
00329 #include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp>
00330 #include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp>
00331 #include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp>
00332 #include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp>
00333 #include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp>
00334 #include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp>
00335 #include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp>
00336 
00337 #undef PB_DS_CLASS_T_DEC
00338 #undef PB_DS_CLASS_C_DEC
00339 #undef PB_DS_LU_TRAITS_BASE
00340 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
00341 #undef PB_DS_LU_NAME
00342   } // namespace detail
00343 } // namespace __gnu_pbds