libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009 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 insert_fn_imps.hpp
  38  * Contains an implementation for thin_heap_.
  39  */
  40
  41 PB_DS_CLASS_T_DEC
  42 inline typename PB_DS_CLASS_C_DEC::point_iterator
  43 PB_DS_CLASS_C_DEC::
  44 push(const_reference r_val)
  45 {
  46   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  47
  48     node_pointer p_nd = base_type::get_new_node_for_insert(r_val);
  49
  50   p_nd->m_metadata = 0;
  51
  52   p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0;
  53
  54   if (base_type::m_p_root == 0)
  55     {
  56       p_nd->m_p_next_sibling = 0;
  57
  58       m_p_max = base_type::m_p_root = p_nd;
  59
  60       _GLIBCXX_DEBUG_ONLY(assert_valid();)
  61
  62         return point_iterator(p_nd);
  63     }
  64
  65   p_nd->m_p_next_sibling = base_type::m_p_root;
  66
  67   base_type::m_p_root->m_p_prev_or_parent = 0;
  68
  69   base_type::m_p_root = p_nd;
  70
  71   update_max(p_nd);
  72
  73   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  74
  75     return point_iterator(p_nd);
  76 }
  77
  78 PB_DS_CLASS_T_DEC
  79 inline void
  80 PB_DS_CLASS_C_DEC::
  81 make_root(node_pointer p_nd)
  82 {
  83   p_nd->m_metadata =
  84     p_nd->m_p_l_child == 0?
  85     0 :
  86     1 + p_nd->m_p_l_child->m_metadata;
  87 }
  88
  89 PB_DS_CLASS_T_DEC
  90 inline void
  91 PB_DS_CLASS_C_DEC::
  92 make_root_and_link(node_pointer p_nd)
  93 {
  94   make_root(p_nd);
  95
  96   p_nd->m_p_prev_or_parent = 0;
  97
  98   p_nd->m_p_next_sibling = base_type::m_p_root;
  99
 100   if (base_type::m_p_root != 0)
 101     base_type::m_p_root->m_p_prev_or_parent = 0;
 102
 103   base_type::m_p_root = p_nd;
 104
 105   update_max(p_nd);
 106 }
 107
 108 PB_DS_CLASS_T_DEC
 109 inline void
 110 PB_DS_CLASS_C_DEC::
 111 fix(node_pointer p_y)
 112 {
 113   while (true)
 114     {
 115       if (p_y->m_p_prev_or_parent == 0)
 116         {
 117           fix_root(p_y);
 118
 119           return;
 120         }
 121       else if (p_y->m_metadata == 1&&  p_y->m_p_next_sibling == 0)
 122         {
 123           if (p_y->m_p_l_child != 0)
 124             {
 125               fix_sibling_rank_1_unmarked(p_y);
 126
 127               return;
 128             }
 129
 130           fix_sibling_rank_1_marked(p_y);
 131
 132           p_y = p_y->m_p_prev_or_parent;
 133         }
 134       else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1)
 135         {
 136           _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != 0);
 137
 138           if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2)
 139             {
 140               fix_sibling_general_unmarked(p_y);
 141
 142               return;
 143             }
 144
 145           fix_sibling_general_marked(p_y);
 146
 147           p_y = p_y->m_p_prev_or_parent;
 148         }
 149       else if ((p_y->m_p_l_child == 0&&
 150                 p_y->m_metadata == 2) ||(p_y->m_p_l_child != 0&&
 151                                          p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3))
 152         {
 153           node_pointer p_z = p_y->m_p_prev_or_parent;
 154
 155           fix_child(p_y);
 156
 157           p_y = p_z;
 158         }
 159       else
 160         return;
 161     }
 162 }
 163
 164 PB_DS_CLASS_T_DEC
 165 inline void
 166 PB_DS_CLASS_C_DEC::
 167 fix_root(node_pointer p_y)
 168 {
 169   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == 0);
 170
 171   make_root(p_y);
 172
 173   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, true);)
 174     }
 175
 176 PB_DS_CLASS_T_DEC
 177 inline void
 178 PB_DS_CLASS_C_DEC::
 179 fix_sibling_rank_1_unmarked(node_pointer p_y)
 180 {
 181   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
 182
 183   _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;)
 184     _GLIBCXX_DEBUG_ASSERT(p_w != 0);
 185   _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == 0);
 186   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == 0);
 187
 188   p_y->m_p_next_sibling = p_y->m_p_l_child;
 189
 190   p_y->m_p_next_sibling->m_p_prev_or_parent = p_y;
 191
 192   p_y->m_p_l_child = 0;
 193
 194   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
 195     }
 196
 197 PB_DS_CLASS_T_DEC
 198 inline void
 199 PB_DS_CLASS_C_DEC::
 200 fix_sibling_rank_1_marked(node_pointer p_y)
 201 {
 202   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
 203   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == 0);
 204
 205   p_y->m_metadata = 0;
 206
 207   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
 208     }
 209
 210 PB_DS_CLASS_T_DEC
 211 inline void
 212 PB_DS_CLASS_C_DEC::
 213 fix_sibling_general_unmarked(node_pointer p_y)
 214 {
 215   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
 216
 217   node_pointer p_w = p_y->m_p_l_child;
 218   _GLIBCXX_DEBUG_ASSERT(p_w != 0);
 219   _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0);
 220
 221   p_y->m_p_l_child = p_w->m_p_next_sibling;
 222   p_w->m_p_next_sibling->m_p_prev_or_parent = p_y;
 223
 224   p_w->m_p_next_sibling = p_y->m_p_next_sibling;
 225   _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0);
 226   p_w->m_p_next_sibling->m_p_prev_or_parent = p_w;
 227
 228   p_y->m_p_next_sibling = p_w;
 229   p_w->m_p_prev_or_parent = p_y;
 230
 231   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
 232     }
 233
 234 PB_DS_CLASS_T_DEC
 235 inline void
 236 PB_DS_CLASS_C_DEC::
 237 fix_sibling_general_marked(node_pointer p_y)
 238 {
 239   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
 240
 241   --p_y->m_metadata;
 242
 243   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
 244     }
 245
 246 PB_DS_CLASS_T_DEC
 247 inline void
 248 PB_DS_CLASS_C_DEC::
 249 fix_child(node_pointer p_y)
 250 {
 251   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
 252
 253   if (p_y->m_p_next_sibling != 0)
 254     p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent;
 255
 256   if (p_y->m_p_prev_or_parent->m_p_l_child == p_y)
 257     p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling;
 258   else
 259     p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling;
 260
 261   make_root_and_link(p_y);
 262 }
 263
 264 PB_DS_CLASS_T_DEC
 265 void
 266 PB_DS_CLASS_C_DEC::
 267 modify(point_iterator it, const_reference r_new_val)
 268 {
 269   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 270     node_pointer p_nd = it.m_p_nd;
 271
 272   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
 273
 274   const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value);
 275
 276   p_nd->m_value = r_new_val;
 277
 278   if (smaller)
 279     {
 280       remove_node(p_nd);
 281
 282       p_nd->m_p_l_child = 0;
 283
 284       make_root_and_link(p_nd);
 285
 286       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 287
 288         return;
 289     }
 290
 291   if (p_nd->m_p_prev_or_parent == 0)
 292     {
 293       update_max(p_nd);
 294
 295       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 296
 297         return;
 298     }
 299
 300   node_pointer p_y = p_nd->m_p_prev_or_parent;
 301   _GLIBCXX_DEBUG_ASSERT(p_y != 0);
 302
 303   if (p_nd->m_p_next_sibling != 0)
 304     p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y;
 305
 306   if (p_y->m_p_l_child == p_nd)
 307     p_y->m_p_l_child = p_nd->m_p_next_sibling;
 308   else
 309     p_y->m_p_next_sibling = p_nd->m_p_next_sibling;
 310
 311   fix(p_y);
 312
 313   make_root_and_link(p_nd);
 314
 315   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 316     }
 317
 318 PB_DS_CLASS_T_DEC
 319 inline void
 320 PB_DS_CLASS_C_DEC::
 321 update_max(node_pointer p_nd)
 322 {
 323   if (m_p_max == 0 || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value))
 324     m_p_max = p_nd;
 325 }
 326