41 #ifndef PB_DS_DEBUG_MAP_BASE_HPP
42 #define PB_DS_DEBUG_MAP_BASE_HPP
58 template<
typename _CharT,
typename _Traits,
typename _Tp1,
typename _Tp2>
60 operator<<(std::basic_ostream<_CharT, _Traits>& __out,
62 {
return (__out <<
'(' << p.first <<
',' << p.second <<
')'); }
64 #define PB_DS_CLASS_T_DEC \
65 template<typename Key, class Eq_Fn, typename Const_Key_Reference>
67 #define PB_DS_CLASS_C_DEC \
68 debug_map_base<Key, Eq_Fn, Const_Key_Reference>
70 template<
typename Key,
class Eq_Fn,
typename Const_Key_Reference>
76 typedef typename key_allocator::size_type size_type;
78 typedef Const_Key_Reference const_key_reference;
83 debug_map_base(
const PB_DS_CLASS_C_DEC& other);
88 insert_new(const_key_reference r_key);
91 erase_existing(const_key_reference r_key);
97 check_key_exists(const_key_reference r_key)
const;
100 check_key_does_not_exist(const_key_reference r_key)
const;
103 check_size(size_type size)
const;
106 swap(PB_DS_CLASS_C_DEC& other);
108 template<
typename Cmp_Fn>
110 split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
113 join(PB_DS_CLASS_C_DEC& other);
117 typedef typename key_set::iterator key_set_iterator;
118 typedef typename key_set::const_iterator const_key_set_iterator;
120 #ifdef _GLIBCXX_DEBUG
122 assert_valid()
const;
125 const_key_set_iterator
126 find(const_key_reference r_key)
const;
129 find(const_key_reference r_key);
138 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
142 debug_map_base(
const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set)
143 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
148 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
153 insert_new(const_key_reference r_key)
155 _GLIBCXX_DEBUG_ONLY(assert_valid();)
157 const double orig_throw_prob = alloc.get_throw_prob();
158 alloc.set_throw_prob(0);
159 if (find(r_key) != m_key_set.end())
167 m_key_set.push_back(r_key);
174 alloc.set_throw_prob(orig_throw_prob);
175 _GLIBCXX_DEBUG_ONLY(assert_valid();)
181 erase_existing(const_key_reference r_key)
183 _GLIBCXX_DEBUG_ONLY(assert_valid();)
184 key_set_iterator it = find(r_key);
185 if (it == m_key_set.end())
191 _GLIBCXX_DEBUG_ONLY(assert_valid();)
199 _GLIBCXX_DEBUG_ONLY(assert_valid();)
201 _GLIBCXX_DEBUG_ONLY(assert_valid();)
207 check_key_exists(const_key_reference r_key)
const
209 _GLIBCXX_DEBUG_ONLY(assert_valid();)
210 if (find(r_key) == m_key_set.end())
215 _GLIBCXX_DEBUG_ONLY(assert_valid();)
221 check_key_does_not_exist(const_key_reference r_key)
const
223 _GLIBCXX_DEBUG_ONLY(assert_valid();)
224 if (find(r_key) != m_key_set.end())
228 cerr <<
"check_key_does_not_exist" << r_key <<
endl;
236 check_size(size_type size)
const
238 _GLIBCXX_DEBUG_ONLY(assert_valid();)
239 const size_type key_set_size = m_key_set.size();
240 if (size != key_set_size)
246 _GLIBCXX_DEBUG_ONLY(assert_valid();)
252 swap(PB_DS_CLASS_C_DEC& other)
254 _GLIBCXX_DEBUG_ONLY(assert_valid();)
255 m_key_set.swap(other.m_key_set);
256 _GLIBCXX_DEBUG_ONLY(assert_valid();)
260 typename PB_DS_CLASS_C_DEC::const_key_set_iterator
262 find(const_key_reference r_key)
const
264 _GLIBCXX_DEBUG_ONLY(assert_valid();)
265 typedef const_key_set_iterator iterator_type;
266 for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
267 if (m_eq(*it, r_key))
269 return m_key_set.end();
273 typename PB_DS_CLASS_C_DEC::key_set_iterator
275 find(const_key_reference r_key)
277 _GLIBCXX_DEBUG_ONLY(assert_valid();)
278 key_set_iterator it = m_key_set.begin();
279 while (it != m_key_set.end())
281 if (m_eq(*it, r_key))
286 _GLIBCXX_DEBUG_ONLY(assert_valid();)
289 #ifdef _GLIBCXX_DEBUG
295 const_key_set_iterator prime_it = m_key_set.begin();
296 while (prime_it != m_key_set.end())
298 const_key_set_iterator sec_it = prime_it;
300 while (sec_it != m_key_set.end())
302 _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it));
303 _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it));
312 template<
typename Cmp_Fn>
315 split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
318 const double orig_throw_prob = alloc.get_throw_prob();
319 alloc.set_throw_prob(0);
321 key_set_iterator it = m_key_set.begin();
322 while (it != m_key_set.end())
323 if (cmp_fn(r_key, * it))
325 other.insert_new(*it);
326 it = m_key_set.erase(it);
330 alloc.set_throw_prob(orig_throw_prob);
336 join(PB_DS_CLASS_C_DEC& other)
339 const double orig_throw_prob = alloc.get_throw_prob();
340 alloc.set_throw_prob(0);
341 key_set_iterator it = other.m_key_set.begin();
342 while (it != other.m_key_set.end())
345 it = other.m_key_set.erase(it);
347 _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
348 alloc.set_throw_prob(orig_throw_prob);
351 #undef PB_DS_CLASS_T_DEC
352 #undef PB_DS_CLASS_C_DEC
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
pair holds two objects of arbitrary type.
basic_ostream< _CharT, _Traits > & endl(basic_ostream< _CharT, _Traits > &__os)
Write a newline and flush the stream.
ostream cerr
Linked to standard error (unbuffered)
Allocator class with logging and exception control.
The "standard" allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manu...
Controlling output.This is the base class for all output streams. It provides text formatting of all ...