3 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
37 * @file debug_fn_imps.hpp
38 * Contains an implementation class for bin_search_tree_.
48 structure_only_assert_valid();
49 assert_consistent_with_debug_base();
52 if (m_p_head->m_p_parent == NULL)
54 _GLIBCXX_DEBUG_ASSERT(m_size == 0);
58 _GLIBCXX_DEBUG_ASSERT(m_size > 0);
65 structure_only_assert_valid() const
67 _GLIBCXX_DEBUG_ASSERT(m_p_head != NULL);
68 if (m_p_head->m_p_parent == NULL)
70 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head);
71 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head);
75 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent->m_p_parent == m_p_head);
76 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left != m_p_head);
77 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right != m_p_head);
80 if (m_p_head->m_p_parent != NULL)
81 assert_node_consistent(m_p_head->m_p_parent);
89 assert_node_consistent(const node_pointer p_nd) const
91 assert_node_consistent_(p_nd);
95 typename PB_DS_CLASS_C_DEC::node_consistent_t
97 assert_node_consistent_(const node_pointer p_nd) const
100 return (std::make_pair((const_pointer)NULL,(const_pointer)NULL));
102 assert_node_consistent_with_left(p_nd);
103 assert_node_consistent_with_right(p_nd);
105 const std::pair<const_pointer, const_pointer>
106 l_range = assert_node_consistent_(p_nd->m_p_left);
108 if (l_range.second != NULL)
109 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second),
110 PB_DS_V2F(p_nd->m_value)));
112 const std::pair<const_pointer, const_pointer>
113 r_range = assert_node_consistent_(p_nd->m_p_right);
115 if (r_range.first != NULL)
116 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value),
117 PB_DS_V2F(*r_range.first)));
119 return (std::make_pair((l_range.first != NULL)? l_range.first :& p_nd->m_value,(r_range.second != NULL)? r_range.second :& p_nd->m_value));
125 assert_node_consistent_with_left(const node_pointer p_nd) const
127 if (p_nd->m_p_left == NULL)
129 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left->m_p_parent == p_nd);
130 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value),
131 PB_DS_V2F(p_nd->m_p_left->m_value)));
137 assert_node_consistent_with_right(const node_pointer p_nd) const
139 if (p_nd->m_p_right == NULL)
141 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right->m_p_parent == p_nd);
142 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_p_right->m_value),
143 PB_DS_V2F(p_nd->m_value)));
151 assert_min_imp(m_p_head->m_p_parent);
157 assert_min_imp(const node_pointer p_nd) const
161 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head);
165 if (p_nd->m_p_left == NULL)
167 _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_left);
170 assert_min_imp(p_nd->m_p_left);
178 assert_max_imp(m_p_head->m_p_parent);
184 assert_max_imp(const node_pointer p_nd) const
188 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head);
192 if (p_nd->m_p_right == NULL)
194 _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_right);
198 assert_max_imp(p_nd->m_p_right);
204 assert_iterators() const
206 size_type iterated_num = 0;
207 const_iterator prev_it = end();
208 for (const_iterator it = begin(); it != end(); ++it)
211 _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)).m_p_nd == it.m_p_nd);
212 const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it));
214 _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == it.m_p_nd);
216 if (prev_it != end())
217 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*prev_it),
222 _GLIBCXX_DEBUG_ASSERT(iterated_num == m_size);
223 size_type reverse_iterated_num = 0;
224 const_reverse_iterator reverse_prev_it = rend();
225 for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend();
228 ++reverse_iterated_num;
229 _GLIBCXX_DEBUG_ASSERT(lower_bound(
230 PB_DS_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd);
232 const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*reverse_it));
234 _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == reverse_it.m_p_nd);
235 if (reverse_prev_it != rend())
236 _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it),
237 PB_DS_V2F(*reverse_it)));
238 reverse_prev_it = reverse_it;
240 _GLIBCXX_DEBUG_ASSERT(reverse_iterated_num == m_size);
246 assert_consistent_with_debug_base() const
248 debug_base::check_size(m_size);
249 assert_consistent_with_debug_base(m_p_head->m_p_parent);
255 assert_consistent_with_debug_base(const node_pointer p_nd) const
259 debug_base::check_key_exists(PB_DS_V2F(p_nd->m_value));
260 assert_consistent_with_debug_base(p_nd->m_p_left);
261 assert_consistent_with_debug_base(p_nd->m_p_right);
269 _GLIBCXX_DEBUG_ASSERT(recursive_count(m_p_head->m_p_parent) == m_size);