libstdc++
thin_heap_/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 thin_heap_/insert_fn_imps.hpp
00038  * Contains an implementation for thin_heap_.
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((*this))
00047   node_pointer p_nd = base_type::get_new_node_for_insert(r_val);
00048   p_nd->m_metadata = 0;
00049   p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0;
00050   if (base_type::m_p_root == 0)
00051     {
00052       p_nd->m_p_next_sibling = 0;
00053       m_p_max = base_type::m_p_root = p_nd;
00054       PB_DS_ASSERT_VALID((*this))
00055       return point_iterator(p_nd);
00056     }
00057 
00058   p_nd->m_p_next_sibling = base_type::m_p_root;
00059   base_type::m_p_root->m_p_prev_or_parent = 0;
00060   base_type::m_p_root = p_nd;
00061   update_max(p_nd);
00062   PB_DS_ASSERT_VALID((*this))
00063   return point_iterator(p_nd);
00064 }
00065 
00066 PB_DS_CLASS_T_DEC
00067 inline void
00068 PB_DS_CLASS_C_DEC::
00069 make_root(node_pointer p_nd)
00070 {
00071   p_nd->m_metadata = p_nd->m_p_l_child == 0 
00072                      ? 0 : 1 + p_nd->m_p_l_child->m_metadata;
00073 }
00074 
00075 PB_DS_CLASS_T_DEC
00076 inline void
00077 PB_DS_CLASS_C_DEC::
00078 make_root_and_link(node_pointer p_nd)
00079 {
00080   make_root(p_nd);
00081   p_nd->m_p_prev_or_parent = 0;
00082   p_nd->m_p_next_sibling = base_type::m_p_root;
00083   if (base_type::m_p_root != 0)
00084     base_type::m_p_root->m_p_prev_or_parent = 0;
00085 
00086   base_type::m_p_root = p_nd;
00087   update_max(p_nd);
00088 }
00089 
00090 PB_DS_CLASS_T_DEC
00091 inline void
00092 PB_DS_CLASS_C_DEC::
00093 fix(node_pointer p_y)
00094 {
00095   while (true)
00096     {
00097       if (p_y->m_p_prev_or_parent == 0)
00098         {
00099       fix_root(p_y);
00100       return;
00101         }
00102       else if (p_y->m_metadata == 1&&  p_y->m_p_next_sibling == 0)
00103         {
00104       if (p_y->m_p_l_child != 0)
00105             {
00106           fix_sibling_rank_1_unmarked(p_y);
00107           return;
00108             }
00109 
00110       fix_sibling_rank_1_marked(p_y);
00111       p_y = p_y->m_p_prev_or_parent;
00112         }
00113       else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1)
00114         {
00115       _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != 0);
00116       if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2)
00117             {
00118           fix_sibling_general_unmarked(p_y);
00119           return;
00120             }
00121 
00122       fix_sibling_general_marked(p_y);
00123       p_y = p_y->m_p_prev_or_parent;
00124         }
00125       else if ((p_y->m_p_l_child == 0&& 
00126                 p_y->m_metadata == 2) ||(p_y->m_p_l_child != 0&& 
00127                      p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3))
00128         {
00129       node_pointer p_z = p_y->m_p_prev_or_parent;
00130       fix_child(p_y);
00131       p_y = p_z;
00132         }
00133       else
00134     return;
00135     }
00136 }
00137 
00138 PB_DS_CLASS_T_DEC
00139 inline void
00140 PB_DS_CLASS_C_DEC::
00141 fix_root(node_pointer p_y)
00142 {
00143   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == 0);
00144   make_root(p_y);
00145   PB_DS_ASSERT_NODE_CONSISTENT(p_y, true)
00146 }
00147 
00148 PB_DS_CLASS_T_DEC
00149 inline void
00150 PB_DS_CLASS_C_DEC::
00151 fix_sibling_rank_1_unmarked(node_pointer p_y)
00152 {
00153   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
00154 
00155   _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;)
00156   _GLIBCXX_DEBUG_ASSERT(p_w != 0);
00157   _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == 0);
00158   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == 0);
00159 
00160   p_y->m_p_next_sibling = p_y->m_p_l_child;
00161   p_y->m_p_next_sibling->m_p_prev_or_parent = p_y;
00162   p_y->m_p_l_child = 0;
00163   PB_DS_ASSERT_NODE_CONSISTENT(p_y, false)
00164 }
00165 
00166 PB_DS_CLASS_T_DEC
00167 inline void
00168 PB_DS_CLASS_C_DEC::
00169 fix_sibling_rank_1_marked(node_pointer p_y)
00170 {
00171   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
00172   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == 0);
00173   p_y->m_metadata = 0;
00174   PB_DS_ASSERT_NODE_CONSISTENT(p_y, false)
00175 }
00176 
00177 PB_DS_CLASS_T_DEC
00178 inline void
00179 PB_DS_CLASS_C_DEC::
00180 fix_sibling_general_unmarked(node_pointer p_y)
00181 {
00182   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
00183 
00184   node_pointer p_w = p_y->m_p_l_child;
00185   _GLIBCXX_DEBUG_ASSERT(p_w != 0);
00186   _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0);
00187 
00188   p_y->m_p_l_child = p_w->m_p_next_sibling;
00189   p_w->m_p_next_sibling->m_p_prev_or_parent = p_y;
00190 
00191   p_w->m_p_next_sibling = p_y->m_p_next_sibling;
00192   _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0);
00193   p_w->m_p_next_sibling->m_p_prev_or_parent = p_w;
00194 
00195   p_y->m_p_next_sibling = p_w;
00196   p_w->m_p_prev_or_parent = p_y;
00197 
00198   PB_DS_ASSERT_NODE_CONSISTENT(p_y, false)
00199 }
00200 
00201 PB_DS_CLASS_T_DEC
00202 inline void
00203 PB_DS_CLASS_C_DEC::
00204 fix_sibling_general_marked(node_pointer p_y)
00205 {
00206   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
00207   --p_y->m_metadata;
00208   PB_DS_ASSERT_NODE_CONSISTENT(p_y, false)
00209 }
00210 
00211 PB_DS_CLASS_T_DEC
00212 inline void
00213 PB_DS_CLASS_C_DEC::
00214 fix_child(node_pointer p_y)
00215 {
00216   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
00217 
00218   if (p_y->m_p_next_sibling != 0)
00219     p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent;
00220 
00221   if (p_y->m_p_prev_or_parent->m_p_l_child == p_y)
00222     p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling;
00223   else
00224     p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling;
00225 
00226   make_root_and_link(p_y);
00227 }
00228 
00229 PB_DS_CLASS_T_DEC
00230 void
00231 PB_DS_CLASS_C_DEC::
00232 modify(point_iterator it, const_reference r_new_val)
00233 {
00234   PB_DS_ASSERT_VALID((*this))
00235   node_pointer p_nd = it.m_p_nd;
00236   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
00237 
00238   const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value);
00239   p_nd->m_value = r_new_val;
00240   if (smaller)
00241     {
00242       remove_node(p_nd);
00243       p_nd->m_p_l_child = 0;
00244       make_root_and_link(p_nd);
00245       PB_DS_ASSERT_VALID((*this))
00246       return;
00247     }
00248 
00249   if (p_nd->m_p_prev_or_parent == 0)
00250     {
00251       update_max(p_nd);
00252       PB_DS_ASSERT_VALID((*this))
00253       return;
00254     }
00255 
00256   node_pointer p_y = p_nd->m_p_prev_or_parent;
00257   _GLIBCXX_DEBUG_ASSERT(p_y != 0);
00258 
00259   if (p_nd->m_p_next_sibling != 0)
00260     p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y;
00261 
00262   if (p_y->m_p_l_child == p_nd)
00263     p_y->m_p_l_child = p_nd->m_p_next_sibling;
00264   else
00265     p_y->m_p_next_sibling = p_nd->m_p_next_sibling;
00266 
00267   fix(p_y);
00268   make_root_and_link(p_nd);
00269   PB_DS_ASSERT_VALID((*this))
00270 }
00271 
00272 PB_DS_CLASS_T_DEC
00273 inline void
00274 PB_DS_CLASS_C_DEC::
00275 update_max(node_pointer p_nd)
00276 {
00277   if (m_p_max == 0 || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value))
00278     m_p_max = p_nd;
00279 }
00280