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
00077 typedef typename key_allocator::size_type size_type;
00078
00079 typedef Const_Key_Reference const_key_reference;
00080
00081 protected:
00082 debug_map_base();
00083
00084 debug_map_base(const PB_DS_CLASS_C_DEC& other);
00085
00086 ~debug_map_base();
00087
00088 inline void
00089 insert_new(const_key_reference r_key);
00090
00091 inline void
00092 erase_existing(const_key_reference r_key);
00093
00094 void
00095 clear();
00096
00097 inline void
00098 check_key_exists(const_key_reference r_key) const;
00099
00100 inline void
00101 check_key_does_not_exist(const_key_reference r_key) const;
00102
00103 inline void
00104 check_size(size_type size) const;
00105
00106 void
00107 swap(PB_DS_CLASS_C_DEC& other);
00108
00109 template<typename Cmp_Fn>
00110 void
00111 split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
00112
00113 void
00114 join(PB_DS_CLASS_C_DEC& other);
00115
00116 private:
00117 typedef std::list< Key> key_set;
00118 typedef typename key_set::iterator key_set_iterator;
00119 typedef typename key_set::const_iterator const_key_set_iterator;
00120
00121 #ifdef _GLIBCXX_DEBUG
00122 void
00123 assert_valid() const;
00124 #endif
00125
00126 const_key_set_iterator
00127 find(const_key_reference r_key) const;
00128
00129 key_set_iterator
00130 find(const_key_reference r_key);
00131
00132 key_set m_key_set;
00133 Eq_Fn m_eq;
00134 };
00135
00136 PB_DS_CLASS_T_DEC
00137 PB_DS_CLASS_C_DEC::
00138 debug_map_base()
00139 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00140
00141 PB_DS_CLASS_T_DEC
00142 PB_DS_CLASS_C_DEC::
00143 debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set)
00144 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00145
00146 PB_DS_CLASS_T_DEC
00147 PB_DS_CLASS_C_DEC::
00148 ~debug_map_base()
00149 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
00150
00151 PB_DS_CLASS_T_DEC
00152 inline void
00153 PB_DS_CLASS_C_DEC::
00154 insert_new(const_key_reference r_key)
00155 {
00156 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00157
00158
00159
00160
00161 if (find(r_key) != m_key_set.end())
00162 {
00163 std::cerr << "insert_new" << r_key << std::endl;
00164 std::abort();
00165 }
00166
00167 __try
00168 {
00169 m_key_set.push_back(r_key);
00170 }
00171 __catch(...)
00172 {
00173 std::cerr << "insert_new" << r_key << std::endl;
00174 std::abort();
00175 }
00176
00177 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00178 }
00179
00180 PB_DS_CLASS_T_DEC
00181 inline void
00182 PB_DS_CLASS_C_DEC::
00183 erase_existing(const_key_reference r_key)
00184 {
00185 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00186 key_set_iterator it = find(r_key);
00187 if (it == m_key_set.end())
00188 {
00189 std::cerr << "erase_existing" << r_key << std::endl;
00190 std::abort();
00191 }
00192 m_key_set.erase(it);
00193 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00194 }
00195
00196 PB_DS_CLASS_T_DEC
00197 void
00198 PB_DS_CLASS_C_DEC::
00199 clear()
00200 {
00201 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00202 m_key_set.clear();
00203 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00204 }
00205
00206 PB_DS_CLASS_T_DEC
00207 inline void
00208 PB_DS_CLASS_C_DEC::
00209 check_key_exists(const_key_reference r_key) const
00210 {
00211 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00212 if (find(r_key) == m_key_set.end())
00213 {
00214 std::cerr << "check_key_exists" << r_key << std::endl;
00215 std::abort();
00216 }
00217 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00218 }
00219
00220 PB_DS_CLASS_T_DEC
00221 inline void
00222 PB_DS_CLASS_C_DEC::
00223 check_key_does_not_exist(const_key_reference r_key) const
00224 {
00225 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00226 if (find(r_key) != m_key_set.end())
00227 {
00228 using std::cerr;
00229 using std::endl;
00230 cerr << "check_key_does_not_exist" << r_key << endl;
00231 std::abort();
00232 }
00233 }
00234
00235 PB_DS_CLASS_T_DEC
00236 inline void
00237 PB_DS_CLASS_C_DEC::
00238 check_size(size_type size) const
00239 {
00240 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00241 const size_type key_set_size = m_key_set.size();
00242 if (size != key_set_size)
00243 {
00244 std::cerr << "check_size " << size
00245 << " " << key_set_size << std::endl;
00246 std::abort();
00247 }
00248 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00249 }
00250
00251 PB_DS_CLASS_T_DEC
00252 void
00253 PB_DS_CLASS_C_DEC::
00254 swap(PB_DS_CLASS_C_DEC& other)
00255 {
00256 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00257 m_key_set.swap(other.m_key_set);
00258 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00259 }
00260
00261 PB_DS_CLASS_T_DEC
00262 typename PB_DS_CLASS_C_DEC::const_key_set_iterator
00263 PB_DS_CLASS_C_DEC::
00264 find(const_key_reference r_key) const
00265 {
00266 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00267 typedef const_key_set_iterator iterator_type;
00268 for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
00269 if (m_eq(*it, r_key))
00270 return it;
00271 return m_key_set.end();
00272 }
00273
00274 PB_DS_CLASS_T_DEC
00275 typename PB_DS_CLASS_C_DEC::key_set_iterator
00276 PB_DS_CLASS_C_DEC::
00277 find(const_key_reference r_key)
00278 {
00279 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00280 key_set_iterator it = m_key_set.begin();
00281 while (it != m_key_set.end())
00282 {
00283 if (m_eq(*it, r_key))
00284 return it;
00285 ++it;
00286 }
00287 return it;
00288 _GLIBCXX_DEBUG_ONLY(assert_valid();)
00289 }
00290
00291 #ifdef _GLIBCXX_DEBUG
00292 PB_DS_CLASS_T_DEC
00293 void
00294 PB_DS_CLASS_C_DEC::
00295 assert_valid() const
00296 {
00297 const_key_set_iterator prime_it = m_key_set.begin();
00298 while (prime_it != m_key_set.end())
00299 {
00300 const_key_set_iterator sec_it = prime_it;
00301 ++sec_it;
00302 while (sec_it != m_key_set.end())
00303 {
00304 _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it));
00305 _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it));
00306 ++sec_it;
00307 }
00308 ++prime_it;
00309 }
00310 }
00311 #endif
00312
00313 PB_DS_CLASS_T_DEC
00314 template<typename Cmp_Fn>
00315 void
00316 PB_DS_CLASS_C_DEC::
00317 split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
00318 {
00319
00320
00321
00322
00323 other.clear();
00324 key_set_iterator it = m_key_set.begin();
00325 while (it != m_key_set.end())
00326 if (cmp_fn(r_key, * it))
00327 {
00328 other.insert_new(*it);
00329 it = m_key_set.erase(it);
00330 }
00331 else
00332 ++it;
00333
00334 }
00335
00336 PB_DS_CLASS_T_DEC
00337 void
00338 PB_DS_CLASS_C_DEC::
00339 join(PB_DS_CLASS_C_DEC& other)
00340 {
00341
00342
00343
00344
00345 key_set_iterator it = other.m_key_set.begin();
00346 while (it != other.m_key_set.end())
00347 {
00348 insert_new(*it);
00349 it = other.m_key_set.erase(it);
00350 }
00351 _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
00352
00353 }
00354
00355 #undef PB_DS_CLASS_T_DEC
00356 #undef PB_DS_CLASS_C_DEC
00357
00358 }
00359 }
00360
00361 #endif
00362
00363 #endif
00364