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