libstdc++
binomial_heap_base_/debug_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the terms
00008 // of the GNU General Public License as published by the Free Software
00009 // Foundation; either version 3, or (at your option) any later
00010 // version.
00011 
00012 // This library is distributed in the hope that it will be useful, but
00013 // WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 // General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00027 
00028 // Permission to use, copy, modify, sell, and distribute this software
00029 // is hereby granted without fee, provided that the above copyright
00030 // notice appears in all copies, and that both that copyright notice
00031 // and this permission notice appear in supporting documentation. None
00032 // of the above authors, nor IBM Haifa Research Laboratories, make any
00033 // representation about the suitability of this software for any
00034 // purpose. It is provided "as is" without express or implied
00035 // warranty.
00036 
00037 /**
00038  * @file binomial_heap_base_/debug_fn_imps.hpp
00039  * Contains an implementation class for a base of binomial heaps.
00040  */
00041 
00042 #ifdef _GLIBCXX_DEBUG
00043 
00044 PB_DS_CLASS_T_DEC
00045 void
00046 PB_DS_CLASS_C_DEC::
00047 assert_valid(bool strictly_binomial, const char* __file, int __line) const
00048 {
00049   base_type::assert_valid(__file, __line);
00050   assert_node_consistent(base_type::m_p_root, strictly_binomial, true,
00051              __file, __line);
00052   assert_max(__file, __line);
00053 }
00054 
00055 PB_DS_CLASS_T_DEC
00056 void
00057 PB_DS_CLASS_C_DEC::
00058 assert_max(const char* __file, int __line) const
00059 {
00060   if (m_p_max == 0)
00061     return;
00062   PB_DS_DEBUG_VERIFY(base_type::parent(m_p_max) == 0);
00063   for (const_iterator it = base_type::begin(); it != base_type::end(); ++it)
00064     PB_DS_DEBUG_VERIFY(!Cmp_Fn::operator()(m_p_max->m_value,
00065                        it.m_p_nd->m_value));
00066 }
00067 
00068 PB_DS_CLASS_T_DEC
00069 void
00070 PB_DS_CLASS_C_DEC::
00071 assert_node_consistent(node_const_pointer p_nd, bool strictly_binomial,
00072                bool increasing, const char* __file, int __line) const
00073 {
00074   PB_DS_DEBUG_VERIFY(increasing || strictly_binomial);
00075   base_type::assert_node_consistent(p_nd, false, __file, __line);
00076   if (p_nd == 0)
00077     return;
00078   PB_DS_DEBUG_VERIFY(p_nd->m_metadata == base_type::degree(p_nd));
00079   PB_DS_DEBUG_VERIFY(base_type::size_under_node(p_nd) ==
00080            static_cast<size_type>(1 << p_nd->m_metadata));
00081   assert_node_consistent(p_nd->m_p_next_sibling, strictly_binomial, increasing,
00082              __file, __line);
00083   assert_node_consistent(p_nd->m_p_l_child, true, false, __file, __line);
00084   if (p_nd->m_p_next_sibling != 0)
00085     {
00086       if (increasing)
00087     {
00088       if (strictly_binomial)
00089         PB_DS_DEBUG_VERIFY(p_nd->m_metadata
00090                   < p_nd->m_p_next_sibling->m_metadata);
00091       else
00092         PB_DS_DEBUG_VERIFY(p_nd->m_metadata
00093                   <= p_nd->m_p_next_sibling->m_metadata);
00094     }
00095       else
00096     PB_DS_DEBUG_VERIFY(p_nd->m_metadata
00097                   > p_nd->m_p_next_sibling->m_metadata);
00098     }
00099 }
00100 
00101 #endif