libstdc++
rb_tree_map_/split_join_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 rb_tree_map_/split_join_fn_imps.hpp
00038  * Contains an implementation for rb_tree_.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 inline void
00043 PB_DS_CLASS_C_DEC::
00044 join(PB_DS_CLASS_C_DEC& other)
00045 {
00046   PB_DS_ASSERT_VALID((*this))
00047   PB_DS_ASSERT_VALID(other)
00048   if (base_type::join_prep(other) == false)
00049     {
00050       PB_DS_ASSERT_VALID((*this))
00051       PB_DS_ASSERT_VALID(other)
00052       return;
00053     }
00054 
00055   const node_pointer p_x = other.split_min();
00056   join_imp(p_x, other.m_p_head->m_p_parent);
00057   base_type::join_finish(other);
00058   PB_DS_ASSERT_VALID((*this))
00059   PB_DS_ASSERT_VALID(other)
00060  }
00061 
00062 PB_DS_CLASS_T_DEC
00063 void
00064 PB_DS_CLASS_C_DEC::
00065 join_imp(node_pointer p_x, node_pointer p_r)
00066 {
00067   _GLIBCXX_DEBUG_ASSERT(p_x != 0);
00068   if (p_r != 0)
00069     p_r->m_red = false;
00070 
00071   const size_type h = black_height(base_type::m_p_head->m_p_parent);
00072   const size_type other_h = black_height(p_r);
00073   node_pointer p_x_l;
00074   node_pointer p_x_r;
00075   std::pair<node_pointer, node_pointer> join_pos;
00076   const bool right_join = h >= other_h;
00077   if (right_join)
00078     {
00079       join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent, 
00080                      h, other_h);
00081       p_x_l = join_pos.first;
00082       p_x_r = p_r;
00083     }
00084   else
00085     {
00086       p_x_l = base_type::m_p_head->m_p_parent;
00087       base_type::m_p_head->m_p_parent = p_r;
00088       if (p_r != 0)
00089     p_r->m_p_parent = base_type::m_p_head;
00090 
00091       join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent, 
00092                     h, other_h);
00093       p_x_r = join_pos.first;
00094     }
00095 
00096   node_pointer p_parent = join_pos.second;
00097   if (p_parent == base_type::m_p_head)
00098     {
00099       base_type::m_p_head->m_p_parent = p_x;
00100       p_x->m_p_parent = base_type::m_p_head;
00101     }
00102   else
00103     {
00104       p_x->m_p_parent = p_parent;
00105       if (right_join)
00106     p_x->m_p_parent->m_p_right = p_x;
00107       else
00108     p_x->m_p_parent->m_p_left = p_x;
00109     }
00110 
00111   p_x->m_p_left = p_x_l;
00112   if (p_x_l != 0)
00113     p_x_l->m_p_parent = p_x;
00114 
00115   p_x->m_p_right = p_x_r;
00116   if (p_x_r != 0)
00117     p_x_r->m_p_parent = p_x;
00118 
00119   p_x->m_red = true;
00120 
00121   base_type::initialize_min_max();
00122   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
00123   base_type::update_to_top(p_x, (node_update* )this);
00124   insert_fixup(p_x);
00125   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
00126 }
00127 
00128 PB_DS_CLASS_T_DEC
00129 inline typename PB_DS_CLASS_C_DEC::node_pointer
00130 PB_DS_CLASS_C_DEC::
00131 split_min()
00132 {
00133   node_pointer p_min = base_type::m_p_head->m_p_left;
00134 
00135 #ifdef _GLIBCXX_DEBUG
00136   const node_pointer p_head = base_type::m_p_head;
00137   _GLIBCXX_DEBUG_ASSERT(p_min != p_head);
00138 #endif 
00139 
00140   remove_node(p_min);
00141   return p_min;
00142 }
00143 
00144 PB_DS_CLASS_T_DEC
00145 std::pair<
00146   typename PB_DS_CLASS_C_DEC::node_pointer,
00147   typename PB_DS_CLASS_C_DEC::node_pointer>
00148 PB_DS_CLASS_C_DEC::
00149 find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r)
00150 {
00151   _GLIBCXX_DEBUG_ASSERT(h_l >= h_r);
00152 
00153   if (base_type::m_p_head->m_p_parent == 0)
00154     return (std::make_pair((node_pointer)0, base_type::m_p_head));
00155 
00156   node_pointer p_l_parent = base_type::m_p_head;
00157   while (h_l > h_r)
00158     {
00159       if (p_l->m_red == false)
00160         {
00161       _GLIBCXX_DEBUG_ASSERT(h_l > 0);
00162       --h_l;
00163         }
00164 
00165       p_l_parent = p_l;
00166       p_l = p_l->m_p_right;
00167     }
00168 
00169   if (!is_effectively_black(p_l))
00170     {
00171       p_l_parent = p_l;
00172       p_l = p_l->m_p_right;
00173     }
00174 
00175   _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l));
00176   _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r);
00177   _GLIBCXX_DEBUG_ASSERT(p_l == 0 || p_l->m_p_parent == p_l_parent);
00178   return std::make_pair(p_l, p_l_parent);
00179 }
00180 
00181 PB_DS_CLASS_T_DEC
00182 std::pair<
00183   typename PB_DS_CLASS_C_DEC::node_pointer,
00184   typename PB_DS_CLASS_C_DEC::node_pointer>
00185 PB_DS_CLASS_C_DEC::
00186 find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r)
00187 {
00188   _GLIBCXX_DEBUG_ASSERT(h_r > h_l);
00189   if (base_type::m_p_head->m_p_parent == 0)
00190     return (std::make_pair((node_pointer)0,
00191                base_type::m_p_head));
00192   node_pointer p_r_parent = base_type::m_p_head;
00193   while (h_r > h_l)
00194     {
00195       if (p_r->m_red == false)
00196         {
00197       _GLIBCXX_DEBUG_ASSERT(h_r > 0);
00198       --h_r;
00199         }
00200 
00201       p_r_parent = p_r;
00202       p_r = p_r->m_p_left;
00203     }
00204 
00205   if (!is_effectively_black(p_r))
00206     {
00207       p_r_parent = p_r;
00208       p_r = p_r->m_p_left;
00209     }
00210 
00211   _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r));
00212   _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l);
00213   _GLIBCXX_DEBUG_ASSERT(p_r == 0 || p_r->m_p_parent == p_r_parent);
00214   return std::make_pair(p_r, p_r_parent);
00215 }
00216 
00217 PB_DS_CLASS_T_DEC
00218 inline typename PB_DS_CLASS_C_DEC::size_type
00219 PB_DS_CLASS_C_DEC::
00220 black_height(node_pointer p_nd)
00221 {
00222   size_type h = 1;
00223   while (p_nd != 0)
00224     {
00225       if (p_nd->m_red == false)
00226     ++h;
00227       p_nd = p_nd->m_p_left;
00228     }
00229   return h;
00230 }
00231 
00232 PB_DS_CLASS_T_DEC
00233 void
00234 PB_DS_CLASS_C_DEC::
00235 split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other)
00236 {
00237   PB_DS_ASSERT_VALID((*this))
00238   PB_DS_ASSERT_VALID(other)
00239 
00240   if (base_type::split_prep(r_key, other) == false)
00241     {
00242       PB_DS_ASSERT_VALID((*this))
00243       PB_DS_ASSERT_VALID(other)
00244       return;
00245     }
00246 
00247   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
00248   PB_DS_STRUCT_ONLY_ASSERT_VALID(other)
00249   node_pointer p_nd = this->upper_bound(r_key).m_p_nd;
00250   do
00251     {
00252       node_pointer p_next_nd = p_nd->m_p_parent;
00253       if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
00254     split_at_node(p_nd, other);
00255 
00256       PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
00257       PB_DS_STRUCT_ONLY_ASSERT_VALID(other)
00258       p_nd = p_next_nd;
00259     }
00260   while (p_nd != base_type::m_p_head);
00261 
00262   base_type::split_finish(other);
00263   PB_DS_ASSERT_VALID((*this))
00264 }
00265 
00266 PB_DS_CLASS_T_DEC
00267 void
00268 PB_DS_CLASS_C_DEC::
00269 split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other)
00270 {
00271   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
00272 
00273   node_pointer p_l = p_nd->m_p_left;
00274   node_pointer p_r = p_nd->m_p_right;
00275   node_pointer p_parent = p_nd->m_p_parent;
00276   if (p_parent == base_type::m_p_head)
00277     {
00278       base_type::m_p_head->m_p_parent = p_l;
00279       if (p_l != 0)
00280         {
00281       p_l->m_p_parent = base_type::m_p_head;
00282       p_l->m_red = false;
00283         }
00284     }
00285   else
00286     {
00287       if (p_parent->m_p_left == p_nd)
00288     p_parent->m_p_left = p_l;
00289       else
00290     p_parent->m_p_right = p_l;
00291 
00292       if (p_l != 0)
00293     p_l->m_p_parent = p_parent;
00294 
00295       this->update_to_top(p_parent, (node_update* )this);
00296 
00297       if (!p_nd->m_red)
00298     remove_fixup(p_l, p_parent);
00299     }
00300 
00301   base_type::initialize_min_max();
00302   other.join_imp(p_nd, p_r);
00303   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
00304   PB_DS_STRUCT_ONLY_ASSERT_VALID(other)
00305 }
00306