libstdc++
binomial_heap_base_/insert_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_/insert_fn_imps.hpp
00038  * Contains an implementation class for a base of binomial heaps.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 inline typename PB_DS_CLASS_C_DEC::point_iterator
00043 PB_DS_CLASS_C_DEC::
00044 push(const_reference r_val)
00045 {
00046   PB_DS_ASSERT_VALID_COND((*this),true)
00047   node_pointer p_nd = base_type::get_new_node_for_insert(r_val);
00048   insert_node(p_nd);
00049   m_p_max = 0;
00050   PB_DS_ASSERT_VALID_COND((*this),true)
00051   return point_iterator(p_nd);
00052 }
00053 
00054 PB_DS_CLASS_T_DEC
00055 inline void
00056 PB_DS_CLASS_C_DEC::
00057 insert_node(node_pointer p_nd)
00058 {
00059   if (base_type::m_p_root == 0)
00060     {
00061       p_nd->m_p_next_sibling = 0;
00062       p_nd->m_p_prev_or_parent = 0;
00063       p_nd->m_p_l_child = 0;
00064       p_nd->m_metadata = 0;
00065       base_type::m_p_root = p_nd;
00066       return;
00067     }
00068 
00069   if (base_type::m_p_root->m_metadata > 0)
00070     {
00071       p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0;
00072       p_nd->m_p_next_sibling = base_type::m_p_root;
00073       base_type::m_p_root->m_p_prev_or_parent = p_nd;
00074       base_type::m_p_root = p_nd;
00075       p_nd->m_metadata = 0;
00076       return;
00077     }
00078 
00079   if (Cmp_Fn::operator()(base_type::m_p_root->m_value, p_nd->m_value))
00080     {
00081       p_nd->m_p_next_sibling = base_type::m_p_root->m_p_next_sibling;
00082       p_nd->m_p_prev_or_parent = 0;
00083       p_nd->m_metadata = 1;
00084       p_nd->m_p_l_child = base_type::m_p_root;
00085       base_type::m_p_root->m_p_prev_or_parent = p_nd;
00086       base_type::m_p_root->m_p_next_sibling = 0;
00087       base_type::m_p_root = p_nd;
00088     }
00089   else
00090     {
00091       p_nd->m_p_next_sibling = 0;
00092       p_nd->m_p_l_child = 0;
00093       p_nd->m_p_prev_or_parent = base_type::m_p_root;
00094       p_nd->m_metadata = 0;
00095       _GLIBCXX_DEBUG_ASSERT(base_type::m_p_root->m_p_l_child == 0);
00096       base_type::m_p_root->m_p_l_child = p_nd;
00097       base_type::m_p_root->m_metadata = 1;
00098     }
00099 
00100   base_type::m_p_root = fix(base_type::m_p_root);
00101 }
00102 
00103 PB_DS_CLASS_T_DEC
00104 inline typename PB_DS_CLASS_C_DEC::node_pointer
00105 PB_DS_CLASS_C_DEC::
00106 fix(node_pointer p_nd) const
00107 {
00108   while (p_nd->m_p_next_sibling != 0 &&
00109      p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata)
00110     {
00111       node_pointer p_next = p_nd->m_p_next_sibling;
00112       if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value))
00113     {
00114       p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
00115 
00116       if (p_nd->m_p_prev_or_parent != 0)
00117         p_nd->m_p_prev_or_parent->m_p_next_sibling = p_next;
00118 
00119       base_type::make_child_of(p_nd, p_next);
00120       ++p_next->m_metadata;
00121       p_nd = p_next;
00122     }
00123       else
00124     {
00125       p_nd->m_p_next_sibling = p_next->m_p_next_sibling;
00126 
00127       if (p_nd->m_p_next_sibling != 0)
00128         p_next->m_p_next_sibling = 0;
00129 
00130       base_type::make_child_of(p_next, p_nd);
00131       ++p_nd->m_metadata;
00132     }
00133     }
00134 
00135   if (p_nd->m_p_next_sibling != 0)
00136     p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd;
00137 
00138   return p_nd;
00139 }
00140 
00141 PB_DS_CLASS_T_DEC
00142 void
00143 PB_DS_CLASS_C_DEC::
00144 modify(point_iterator it, const_reference r_new_val)
00145 {
00146   PB_DS_ASSERT_VALID_COND((*this),true)
00147   node_pointer p_nd = it.m_p_nd;
00148 
00149   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
00150   PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd, false)
00151 
00152   const bool bubble_up = Cmp_Fn::operator()(p_nd->m_value, r_new_val);
00153   p_nd->m_value = r_new_val;
00154 
00155   if (bubble_up)
00156     {
00157       node_pointer p_parent = base_type::parent(p_nd);
00158       while (p_parent != 0 &&
00159          Cmp_Fn::operator()(p_parent->m_value, p_nd->m_value))
00160     {
00161       base_type::swap_with_parent(p_nd, p_parent);
00162       p_parent = base_type::parent(p_nd);
00163     }
00164 
00165       if (p_nd->m_p_prev_or_parent == 0)
00166     base_type::m_p_root = p_nd;
00167 
00168       m_p_max = 0;
00169       PB_DS_ASSERT_VALID_COND((*this),true)
00170       return;
00171     }
00172 
00173   base_type::bubble_to_top(p_nd);
00174   remove_parentless_node(p_nd);
00175   insert_node(p_nd);
00176   m_p_max = 0;
00177   PB_DS_ASSERT_VALID_COND((*this),true)
00178 }