libstdc++
binomial_heap_base_/erase_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file binomial_heap_base_/erase_fn_imps.hpp
00038  * Contains an implementation class for a base of binomial heaps.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 void
00043 PB_DS_CLASS_C_DEC::
00044 pop()
00045 {
00046   PB_DS_ASSERT_VALID_COND((*this),true)
00047   _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
00048 
00049   if (m_p_max == 0)
00050     find_max();
00051 
00052   _GLIBCXX_DEBUG_ASSERT(m_p_max != 0);
00053   node_pointer p_nd = m_p_max;
00054   remove_parentless_node(m_p_max);
00055   base_type::actual_erase_node(p_nd);
00056   m_p_max = 0;
00057   PB_DS_ASSERT_VALID_COND((*this),true)
00058 }
00059 
00060 PB_DS_CLASS_T_DEC
00061 void
00062 PB_DS_CLASS_C_DEC::
00063 remove_parentless_node(node_pointer p_nd)
00064 {
00065   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
00066   _GLIBCXX_DEBUG_ASSERT(base_type::parent(p_nd) == 0);
00067 
00068   node_pointer p_cur_root = p_nd == base_type::m_p_root?
00069     p_nd->m_p_next_sibling : base_type::m_p_root;
00070 
00071   if (p_cur_root != 0)
00072     p_cur_root->m_p_prev_or_parent = 0;
00073 
00074   if (p_nd->m_p_prev_or_parent != 0)
00075     p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd->m_p_next_sibling;
00076 
00077   if (p_nd->m_p_next_sibling != 0)
00078     p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
00079 
00080   node_pointer p_child = p_nd->m_p_l_child;
00081   if (p_child != 0)
00082     {
00083       p_child->m_p_prev_or_parent = 0;
00084       while (p_child->m_p_next_sibling != 0)
00085     p_child = p_child->m_p_next_sibling;
00086     }
00087 
00088   m_p_max = 0;
00089   base_type::m_p_root = join(p_cur_root, p_child);
00090 }
00091 
00092 PB_DS_CLASS_T_DEC
00093 inline void
00094 PB_DS_CLASS_C_DEC::
00095 clear()
00096 {
00097   base_type::clear();
00098   m_p_max = 0;
00099 }
00100 
00101 PB_DS_CLASS_T_DEC
00102 void
00103 PB_DS_CLASS_C_DEC::
00104 erase(point_iterator it)
00105 {
00106   PB_DS_ASSERT_VALID_COND((*this),true)
00107   _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
00108 
00109   base_type::bubble_to_top(it.m_p_nd);
00110   remove_parentless_node(it.m_p_nd);
00111   base_type::actual_erase_node(it.m_p_nd);
00112   m_p_max = 0;
00113   PB_DS_ASSERT_VALID_COND((*this),true)
00114 }
00115 
00116 PB_DS_CLASS_T_DEC
00117 template<typename Pred>
00118 typename PB_DS_CLASS_C_DEC::size_type
00119 PB_DS_CLASS_C_DEC::
00120 erase_if(Pred pred)
00121 {
00122   PB_DS_ASSERT_VALID_COND((*this),true)
00123 
00124   if (base_type::empty())
00125     {
00126       PB_DS_ASSERT_VALID_COND((*this),true)
00127       return 0;
00128     }
00129 
00130   base_type::to_linked_list();
00131   node_pointer p_out = base_type::prune(pred);
00132   size_type ersd = 0;
00133   while (p_out != 0)
00134     {
00135       ++ersd;
00136       node_pointer p_next = p_out->m_p_next_sibling;
00137       base_type::actual_erase_node(p_out);
00138       p_out = p_next;
00139     }
00140 
00141   node_pointer p_cur = base_type::m_p_root;
00142   base_type::m_p_root = 0;
00143   while (p_cur != 0)
00144     {
00145       node_pointer p_next = p_cur->m_p_next_sibling;
00146       p_cur->m_p_l_child = p_cur->m_p_prev_or_parent = 0;
00147       p_cur->m_metadata = 0;
00148       p_cur->m_p_next_sibling = base_type::m_p_root;
00149 
00150       if (base_type::m_p_root != 0)
00151     base_type::m_p_root->m_p_prev_or_parent = p_cur;
00152 
00153       base_type::m_p_root = p_cur;
00154       base_type::m_p_root = fix(base_type::m_p_root);
00155       p_cur = p_next;
00156     }
00157 
00158   m_p_max = 0;
00159   PB_DS_ASSERT_VALID_COND((*this),true)
00160   return ersd;
00161 }