Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2015 Free Software Foundation, Inc.
  4. //
  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
  9. // version.
  10.  
  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.
  15.  
  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.
  19.  
  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/>.
  24.  
  25. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26.  
  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
  34. // warranty.
  35.  
  36. /**
  37.  * @file left_child_next_sibling_heap_/debug_fn_imps.hpp
  38.  * Contains an implementation class for left_child_next_sibling_heap_.
  39.  */
  40.  
  41. #ifdef _GLIBCXX_DEBUG
  42.  
  43. PB_DS_CLASS_T_DEC
  44. void
  45. PB_DS_CLASS_C_DEC::
  46. assert_valid(const char* __file, int __line) const
  47. {
  48.   PB_DS_DEBUG_VERIFY(m_p_root == 0 || m_p_root->m_p_prev_or_parent == 0);
  49.  
  50.   if (m_p_root != 0)
  51.     assert_node_consistent(m_p_root, Single_Link_Roots, __file, __line);
  52.   assert_size(__file, __line);
  53.   assert_iterators(__file, __line);
  54. }
  55.  
  56. PB_DS_CLASS_T_DEC
  57. void
  58. PB_DS_CLASS_C_DEC::
  59. assert_node_consistent(node_const_pointer p_nd, bool single_link,
  60.                        const char* __file, int __line) const
  61. {
  62.   if (p_nd == 0)
  63.     return;
  64.  
  65.   assert_node_consistent(p_nd->m_p_l_child, false, __file, __line);
  66.   assert_node_consistent(p_nd->m_p_next_sibling, single_link, __file, __line);
  67.  
  68.   if (single_link)
  69.     PB_DS_DEBUG_VERIFY(p_nd->m_p_prev_or_parent == 0);
  70.   else if (p_nd->m_p_next_sibling != 0)
  71.     PB_DS_DEBUG_VERIFY(p_nd->m_p_next_sibling->m_p_prev_or_parent == p_nd);
  72.  
  73.   if (p_nd->m_p_l_child == 0)
  74.     return;
  75.  
  76.   node_const_pointer p_child = p_nd->m_p_l_child;
  77.   while (p_child != 0)
  78.     {
  79.       node_const_pointer p_next_child = p_child->m_p_next_sibling;
  80.       PB_DS_DEBUG_VERIFY(!Cmp_Fn::operator()(p_nd->m_value, p_child->m_value));
  81.       p_child = p_next_child;
  82.     }
  83.   PB_DS_DEBUG_VERIFY(p_nd->m_p_l_child->m_p_prev_or_parent == p_nd);
  84. }
  85.  
  86. PB_DS_CLASS_T_DEC
  87. void
  88. PB_DS_CLASS_C_DEC::
  89. assert_iterators(const char* __file, int __line) const
  90. {
  91.   PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) == size());
  92. }
  93.  
  94. PB_DS_CLASS_T_DEC
  95. void
  96. PB_DS_CLASS_C_DEC::
  97. assert_size(const char* __file, int __line) const
  98. {
  99.   PB_DS_DEBUG_VERIFY(size_from_node(m_p_root) == m_size);
  100. }
  101.  
  102. PB_DS_CLASS_T_DEC
  103. typename PB_DS_CLASS_C_DEC::size_type
  104. PB_DS_CLASS_C_DEC::
  105. size_under_node(node_const_pointer p_nd)
  106. { return 1 + size_from_node(p_nd->m_p_l_child); }
  107.  
  108. PB_DS_CLASS_T_DEC
  109. typename PB_DS_CLASS_C_DEC::size_type
  110. PB_DS_CLASS_C_DEC::
  111. size_from_node(node_const_pointer p_nd)
  112. {
  113.   size_type ret = 0;
  114.   while (p_nd != 0)
  115.     {
  116.       ret += 1 + size_from_node(p_nd->m_p_l_child);
  117.       p_nd = p_nd->m_p_next_sibling;
  118.     }
  119.   return ret;
  120. }
  121.  
  122. PB_DS_CLASS_T_DEC
  123. typename PB_DS_CLASS_C_DEC::size_type
  124. PB_DS_CLASS_C_DEC::
  125. degree(node_const_pointer p_nd)
  126. {
  127.   size_type ret = 0;
  128.   node_const_pointer p_child = p_nd->m_p_l_child;
  129.   while (p_child != 0)
  130.     {
  131.       ++ret;
  132.       p_child = p_child->m_p_next_sibling;
  133.     }
  134.   return ret;
  135. }
  136.  
  137. #endif
  138.