contrib/libstdc++/include/ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file erase_fn_imps.hpp
  44  * Contains an implementation for thin_heap_.
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 void
  49 PB_DS_CLASS_C_DEC::
  50 pop()
  51 {
  52   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  53     _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
  54
  55   _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL);
  56
  57   node_pointer p_nd = m_p_max;
  58
  59   remove_max_node();
  60
  61   base_type::actual_erase_node(p_nd);
  62
  63   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  64     }
  65
  66 PB_DS_CLASS_T_DEC
  67 inline void
  68 PB_DS_CLASS_C_DEC::
  69 remove_max_node()
  70 {
  71   to_aux_except_max();
  72
  73   make_from_aux();
  74 }
  75
  76 PB_DS_CLASS_T_DEC
  77 void
  78 PB_DS_CLASS_C_DEC::
  79 to_aux_except_max()
  80 {
  81   node_pointer p_add = base_type::m_p_root;
  82
  83   while (p_add != m_p_max)
  84     {
  85       node_pointer p_next_add = p_add->m_p_next_sibling;
  86
  87       add_to_aux(p_add);
  88
  89       p_add = p_next_add;
  90     }
  91
  92   p_add = m_p_max->m_p_l_child;
  93
  94   while (p_add != NULL)
  95     {
  96       node_pointer p_next_add = p_add->m_p_next_sibling;
  97
  98       p_add->m_metadata = p_add->m_p_l_child == NULL?
  99         0 :
 100         p_add->m_p_l_child->m_metadata + 1;
 101
 102       add_to_aux(p_add);
 103
 104       p_add = p_next_add;
 105     }
 106
 107   p_add = m_p_max->m_p_next_sibling;
 108
 109   while (p_add != NULL)
 110     {
 111       node_pointer p_next_add = p_add->m_p_next_sibling;
 112
 113       add_to_aux(p_add);
 114
 115       p_add = p_next_add;
 116     }
 117 }
 118
 119 PB_DS_CLASS_T_DEC
 120 inline void
 121 PB_DS_CLASS_C_DEC::
 122 add_to_aux(node_pointer p_nd)
 123 {
 124   size_type r = p_nd->m_metadata;
 125
 126   while (m_a_aux[r] != NULL)
 127     {
 128       _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
 129
 130       if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value))
 131         make_child_of(m_a_aux[r], p_nd);
 132       else
 133         {
 134           make_child_of(p_nd, m_a_aux[r]);
 135
 136           p_nd = m_a_aux[r];
 137         }
 138
 139       m_a_aux[r] = NULL;
 140
 141       ++r;
 142     }
 143
 144   _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
 145
 146   m_a_aux[r] = p_nd;
 147 }
 148
 149 PB_DS_CLASS_T_DEC
 150 inline void
 151 PB_DS_CLASS_C_DEC::
 152 make_child_of(node_pointer p_nd, node_pointer p_new_parent)
 153 {
 154   _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata);
 155   _GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd ||
 156                    m_a_aux[p_nd->m_metadata] == p_new_parent);
 157
 158   ++p_new_parent->m_metadata;
 159
 160   base_type::make_child_of(p_nd, p_new_parent);
 161 }
 162
 163 PB_DS_CLASS_T_DEC
 164 inline void
 165 PB_DS_CLASS_C_DEC::
 166 make_from_aux()
 167 {
 168   base_type::m_p_root = m_p_max = NULL;
 169
 170   const size_type rnk_bnd = rank_bound();
 171
 172   size_type i = 0;
 173
 174   while (i < rnk_bnd)
 175     {
 176       if (m_a_aux[i] != NULL)
 177         {
 178           make_root_and_link(m_a_aux[i]);
 179
 180           m_a_aux[i] = NULL;
 181         }
 182
 183       ++i;
 184     }
 185
 186   _GLIBCXX_DEBUG_ONLY(assert_aux_null();)
 187     }
 188
 189 PB_DS_CLASS_T_DEC
 190 inline void
 191 PB_DS_CLASS_C_DEC::
 192 remove_node(node_pointer p_nd)
 193 {
 194   node_pointer p_parent = p_nd;
 195   while (base_type::parent(p_parent) != NULL)
 196     p_parent = base_type::parent(p_parent);
 197
 198   base_type::bubble_to_top(p_nd);
 199
 200   m_p_max = p_nd;
 201
 202   node_pointer p_fix = base_type::m_p_root;
 203   while (p_fix != NULL&&  p_fix->m_p_next_sibling != p_parent)
 204     p_fix = p_fix->m_p_next_sibling;
 205
 206   if (p_fix != NULL)
 207     p_fix->m_p_next_sibling = p_nd;
 208
 209   remove_max_node();
 210 }
 211
 212 PB_DS_CLASS_T_DEC
 213 inline void
 214 PB_DS_CLASS_C_DEC::
 215 clear()
 216 {
 217   base_type::clear();
 218
 219   m_p_max = NULL;
 220 }
 221
 222 PB_DS_CLASS_T_DEC
 223 void
 224 PB_DS_CLASS_C_DEC::
 225 erase(point_iterator it)
 226 {
 227   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 228     _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
 229
 230   node_pointer p_nd = it.m_p_nd;
 231
 232   remove_node(p_nd);
 233
 234   base_type::actual_erase_node(p_nd);
 235
 236   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 237     }
 238
 239 PB_DS_CLASS_T_DEC
 240 template<typename Pred>
 241 typename PB_DS_CLASS_C_DEC::size_type
 242 PB_DS_CLASS_C_DEC::
 243 erase_if(Pred pred)
 244 {
 245   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 246
 247     if (base_type::empty())
 248       {
 249         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 250
 251           return 0;
 252       }
 253
 254   base_type::to_linked_list();
 255
 256   node_pointer p_out = base_type::prune(pred);
 257
 258   size_type ersd = 0;
 259
 260   while (p_out != NULL)
 261     {
 262       ++ersd;
 263
 264       node_pointer p_next = p_out->m_p_next_sibling;
 265
 266       base_type::actual_erase_node(p_out);
 267
 268       p_out = p_next;
 269     }
 270
 271   node_pointer p_cur = base_type::m_p_root;
 272
 273   m_p_max = base_type::m_p_root = NULL;
 274
 275   while (p_cur != NULL)
 276     {
 277       node_pointer p_next = p_cur->m_p_next_sibling;
 278
 279       make_root_and_link(p_cur);
 280
 281       p_cur = p_next;
 282     }
 283
 284   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 285
 286     return ersd;
 287 }
 288
 289 PB_DS_CLASS_T_DEC
 290 inline typename PB_DS_CLASS_C_DEC::size_type
 291 PB_DS_CLASS_C_DEC::
 292 rank_bound()
 293 {
 294   const std::size_t* const p_upper =
 295     std::upper_bound(            g_a_rank_bounds, g_a_rank_bounds + num_distinct_rank_bounds, base_type::m_size);
 296
 297   if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds)
 298     return max_rank;
 299
 300   return (p_upper - g_a_rank_bounds);
 301 }
 302