Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 #ifndef PB_DS_DEBUG_MAP_BASE_HPP
00043 #define PB_DS_DEBUG_MAP_BASE_HPP
00044
00045 #ifdef _GLIBCXX_DEBUG
00046
00047 #include <list>
00048 #include <utility>
00049 #include <cstdlib>
00050 #include <iostream>
00051 #include <ext/throw_allocator.h>
00052 #include <debug/debug.h>
00053
00054 namespace __gnu_pbds
00055 {
00056 namespace detail
00057 {
00058
00059 template<typename _CharT, typename _Traits, typename _Tp1, typename _Tp2>
00060 inline std::basic_ostream<_CharT, _Traits>&
00061 operator<<(std::basic_ostream<_CharT, _Traits>& __out,
00062 const std::pair<_Tp1, _Tp2>& p)
00063 { return (__out << '(' << p.first << ',' << p.second << ')'); }
00064
00065 #define PB_DS_CLASS_T_DEC \
00066 template<typename Key, class Eq_Fn, typename Const_Key_Reference>
00067
00068 #define PB_DS_CLASS_C_DEC \
00069 debug_map_base<Key, Eq_Fn, Const_Key_Reference>
00070
00071 template<typename Key, class Eq_Fn, typename Const_Key_Reference>
00072 class debug_map_base
00073 {
00074 private:
00075 typedef typename std::allocator<Key> key_allocator;
00076 typedef typename key_allocator::size_type size_type;
00077 typedef Const_Key_Reference const_key_reference;
00078 typedef std::_GLIBCXX_STD_C::list<Key> key_set;
00079 typedef typename key_set::iterator key_set_iterator;
00080 typedef typename key_set::const_iterator const_key_set_iterator;
00081 typedef __gnu_cxx::throw_allocator_random<Key> key_db_allocator;
00082 typedef typename key_db_allocator::never_adjustor never_adjustor;
00083
00084 protected:
00085 debug_map_base();
00086
00087 debug_map_base(const PB_DS_CLASS_C_DEC& other);
00088
00089 ~debug_map_base();
00090
00091 inline void
00092 insert_new(const_key_reference r_key);
00093
00094 inline void
00095 erase_existing(const_key_reference r_key);
00096
00097 void
00098 clear();
00099
00100 inline void
00101 check_key_exists(const_key_reference r_key) const;
00102
00103 inline void
00104 check_key_does_not_exist(const_key_reference r_key) const;
00105
00106 inline void
00107 check_size(size_type size) const;
00108
00109 void
00110 swap(PB_DS_CLASS_C_DEC& other);
00111
00112 template<typename Cmp_Fn>
00113 void
00114 split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
00115
00116 void
00117 join(PB_DS_CLASS_C_DEC& other);
00118
00119 private:
00120 void
00121 assert_valid() const;
00122
00123 const_key_set_iterator
00124 find(const_key_reference r_key) const;
00125
00126 key_set_iterator
00127 find(const_key_reference r_key);
00128
00129 key_set m_key_set;
00130 Eq_Fn m_eq;
00131 };
00132
00133 PB_DS_CLASS_T_DEC
00134 PB_DS_CLASS_C_DEC::
00135 debug_map_base()
00136 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00137
00138 PB_DS_CLASS_T_DEC
00139 PB_DS_CLASS_C_DEC::
00140 debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set)
00141 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00142
00143 PB_DS_CLASS_T_DEC
00144 PB_DS_CLASS_C_DEC::
00145 ~debug_map_base()
00146 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00147
00148 PB_DS_CLASS_T_DEC
00149 inline void
00150 PB_DS_CLASS_C_DEC::
00151 insert_new(const_key_reference r_key)
00152 {
00153 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00154
00155 if (find(r_key) != m_key_set.end())
00156 {
00157 std::cerr << "insert_new key already present " << r_key << std::endl;
00158 std::abort;
00159 }
00160
00161 never_adjustor never;
00162 __try
00163 {
00164 m_key_set.push_back(r_key);
00165 }
00166 __catch(...)
00167 {
00168 std::cerr << "insert_new " << r_key << std::endl;
00169 std::abort();
00170 }
00171
00172 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00173 }
00174
00175 PB_DS_CLASS_T_DEC
00176 inline void
00177 PB_DS_CLASS_C_DEC::
00178 erase_existing(const_key_reference r_key)
00179 {
00180 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00181 key_set_iterator it = find(r_key);
00182 if (it == m_key_set.end())
00183 {
00184 std::cerr << "erase_existing" << r_key << std::endl;
00185 std::abort();
00186 }
00187 m_key_set.erase(it);
00188 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00189 }
00190
00191 PB_DS_CLASS_T_DEC
00192 void
00193 PB_DS_CLASS_C_DEC::
00194 clear()
00195 {
00196 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00197 m_key_set.clear();
00198 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00199 }
00200
00201 PB_DS_CLASS_T_DEC
00202 inline void
00203 PB_DS_CLASS_C_DEC::
00204 check_key_exists(const_key_reference r_key) const
00205 {
00206 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00207 if (find(r_key) == m_key_set.end())
00208 {
00209 std::cerr << "check_key_exists " << r_key << std::endl;
00210 std::abort();
00211 }
00212 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00213 }
00214
00215 PB_DS_CLASS_T_DEC
00216 inline void
00217 PB_DS_CLASS_C_DEC::
00218 check_key_does_not_exist(const_key_reference r_key) const
00219 {
00220 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00221 if (find(r_key) != m_key_set.end())
00222 {
00223 using std::cerr;
00224 using std::endl;
00225 cerr << "check_key_does_not_exist " << r_key << endl;
00226 std::abort();
00227 }
00228 }
00229
00230 PB_DS_CLASS_T_DEC
00231 inline void
00232 PB_DS_CLASS_C_DEC::
00233 check_size(size_type size) const
00234 {
00235 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00236 const size_type key_set_size = m_key_set.size();
00237 if (size != key_set_size)
00238 {
00239 std::cerr << "check_size " << size
00240 << " " << key_set_size << std::endl;
00241 std::abort();
00242 }
00243 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00244 }
00245
00246 PB_DS_CLASS_T_DEC
00247 void
00248 PB_DS_CLASS_C_DEC::
00249 swap(PB_DS_CLASS_C_DEC& other)
00250 {
00251 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00252 m_key_set.swap(other.m_key_set);
00253 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00254 }
00255
00256 PB_DS_CLASS_T_DEC
00257 typename PB_DS_CLASS_C_DEC::const_key_set_iterator
00258 PB_DS_CLASS_C_DEC::
00259 find(const_key_reference r_key) const
00260 {
00261 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00262 typedef const_key_set_iterator iterator_type;
00263 for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
00264 if (m_eq(*it, r_key))
00265 return it;
00266 return m_key_set.end();
00267 }
00268
00269 PB_DS_CLASS_T_DEC
00270 typename PB_DS_CLASS_C_DEC::key_set_iterator
00271 PB_DS_CLASS_C_DEC::
00272 find(const_key_reference r_key)
00273 {
00274 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00275 key_set_iterator it = m_key_set.begin();
00276 while (it != m_key_set.end())
00277 {
00278 if (m_eq(*it, r_key))
00279 return it;
00280 ++it;
00281 }
00282 return it;
00283 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00284 }
00285
00286 PB_DS_CLASS_T_DEC
00287 void
00288 PB_DS_CLASS_C_DEC::
00289 assert_valid() const
00290 {
00291 const_key_set_iterator prime_it = m_key_set.begin();
00292 while (prime_it != m_key_set.end())
00293 {
00294 const_key_set_iterator sec_it = prime_it;
00295 ++sec_it;
00296 while (sec_it != m_key_set.end())
00297 {
00298 _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it));
00299 _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it));
00300 ++sec_it;
00301 }
00302 ++prime_it;
00303 }
00304 }
00305
00306 PB_DS_CLASS_T_DEC
00307 template<typename Cmp_Fn>
00308 void
00309 PB_DS_CLASS_C_DEC::
00310 split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
00311 {
00312 other.clear();
00313 key_set_iterator it = m_key_set.begin();
00314 while (it != m_key_set.end())
00315 if (cmp_fn(r_key, * it))
00316 {
00317 other.insert_new(*it);
00318 it = m_key_set.erase(it);
00319 }
00320 else
00321 ++it;
00322 }
00323
00324 PB_DS_CLASS_T_DEC
00325 void
00326 PB_DS_CLASS_C_DEC::
00327 join(PB_DS_CLASS_C_DEC& other)
00328 {
00329 key_set_iterator it = other.m_key_set.begin();
00330 while (it != other.m_key_set.end())
00331 {
00332 insert_new(*it);
00333 it = other.m_key_set.erase(it);
00334 }
00335 _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
00336 }
00337
00338 #undef PB_DS_CLASS_T_DEC
00339 #undef PB_DS_CLASS_C_DEC
00340
00341 }
00342 }
00343
00344 #endif
00345
00346 #endif