libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2019 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 pairing_heap_/erase_fn_imps.hpp
  38  * Contains an implementation class for a pairing heap.
  39  */
  40
  41 #ifdef PB_DS_CLASS_C_DEC
  42
  43 PB_DS_CLASS_T_DEC
  44 void
  45 PB_DS_CLASS_C_DEC::
  46 pop()
  47 {
  48   PB_DS_ASSERT_VALID((*this))
  49   _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
  50
  51   node_pointer p_new_root = join_node_children(base_type::m_p_root);
  52   PB_DS_ASSERT_NODE_CONSISTENT(p_new_root, false)
  53   if (p_new_root != 0)
  54     p_new_root->m_p_prev_or_parent = 0;
  55
  56   base_type::actual_erase_node(base_type::m_p_root);
  57   base_type::m_p_root = p_new_root;
  58   PB_DS_ASSERT_VALID((*this))
  59 }
  60
  61 PB_DS_CLASS_T_DEC
  62 void
  63 PB_DS_CLASS_C_DEC::
  64 erase(point_iterator it)
  65 {
  66   PB_DS_ASSERT_VALID((*this))
  67   _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
  68   remove_node(it.m_p_nd);
  69   base_type::actual_erase_node(it.m_p_nd);
  70   PB_DS_ASSERT_VALID((*this))
  71 }
  72
  73 PB_DS_CLASS_T_DEC
  74 void
  75 PB_DS_CLASS_C_DEC::
  76 remove_node(node_pointer p_nd)
  77 {
  78   PB_DS_ASSERT_VALID((*this))
  79   _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
  80   node_pointer p_new_child = join_node_children(p_nd);
  81
  82   PB_DS_ASSERT_NODE_CONSISTENT(p_new_child, false)
  83
  84   if (p_nd == base_type::m_p_root)
  85     {
  86       if (p_new_child != 0)
  87         p_new_child->m_p_prev_or_parent = 0;
  88       base_type::m_p_root = p_new_child;
  89       PB_DS_ASSERT_NODE_CONSISTENT(base_type::m_p_root, false)
  90       return;
  91     }
  92
  93   _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_prev_or_parent != 0);
  94   if (p_nd->m_p_prev_or_parent->m_p_l_child == p_nd)
  95     {
  96       if (p_new_child != 0)
  97         {
  98           p_new_child->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
  99           p_new_child->m_p_next_sibling = p_nd->m_p_next_sibling;
 100           if (p_new_child->m_p_next_sibling != 0)
 101             p_new_child->m_p_next_sibling->m_p_prev_or_parent = p_new_child;
 102           p_nd->m_p_prev_or_parent->m_p_l_child = p_new_child;
 103           PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false)
 104           return;
 105         }
 106
 107       p_nd->m_p_prev_or_parent->m_p_l_child = p_nd->m_p_next_sibling;
 108       if (p_nd->m_p_next_sibling != 0)
 109         p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
 110       PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false)
 111       return;
 112     }
 113
 114   if (p_new_child != 0)
 115     {
 116       p_new_child->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
 117       p_new_child->m_p_next_sibling = p_nd->m_p_next_sibling;
 118       if (p_new_child->m_p_next_sibling != 0)
 119         p_new_child->m_p_next_sibling->m_p_prev_or_parent = p_new_child;
 120       p_new_child->m_p_prev_or_parent->m_p_next_sibling = p_new_child;
 121       PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false)
 122       return;
 123     }
 124
 125   p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd->m_p_next_sibling;
 126   if (p_nd->m_p_next_sibling != 0)
 127     p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
 128   PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false)
 129 }
 130
 131 PB_DS_CLASS_T_DEC
 132 typename PB_DS_CLASS_C_DEC::node_pointer
 133 PB_DS_CLASS_C_DEC::
 134 join_node_children(node_pointer p_nd)
 135 {
 136   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
 137   node_pointer p_ret = p_nd->m_p_l_child;
 138   if (p_ret == 0)
 139     return 0;
 140   while (p_ret->m_p_next_sibling != 0)
 141     p_ret = forward_join(p_ret, p_ret->m_p_next_sibling);
 142   while (p_ret->m_p_prev_or_parent != p_nd)
 143     p_ret = back_join(p_ret->m_p_prev_or_parent, p_ret);
 144   PB_DS_ASSERT_NODE_CONSISTENT(p_ret, false)
 145   return p_ret;
 146 }
 147
 148 PB_DS_CLASS_T_DEC
 149 typename PB_DS_CLASS_C_DEC::node_pointer
 150 PB_DS_CLASS_C_DEC::
 151 forward_join(node_pointer p_nd, node_pointer p_next)
 152 {
 153   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
 154   _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling == p_next);
 155   if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value))
 156     {
 157       p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
 158       base_type::make_child_of(p_nd, p_next);
 159       return p_next->m_p_next_sibling == 0
 160         ? p_next : p_next->m_p_next_sibling;
 161     }
 162
 163   if (p_next->m_p_next_sibling != 0)
 164     {
 165       p_next->m_p_next_sibling->m_p_prev_or_parent = p_nd;
 166       p_nd->m_p_next_sibling = p_next->m_p_next_sibling;
 167       base_type::make_child_of(p_next, p_nd);
 168       return p_nd->m_p_next_sibling;
 169     }
 170
 171   p_nd->m_p_next_sibling = 0;
 172   base_type::make_child_of(p_next, p_nd);
 173   PB_DS_ASSERT_NODE_CONSISTENT(p_nd, false)
 174   return p_nd;
 175 }
 176
 177 PB_DS_CLASS_T_DEC
 178 typename PB_DS_CLASS_C_DEC::node_pointer
 179 PB_DS_CLASS_C_DEC::
 180 back_join(node_pointer p_nd, node_pointer p_next)
 181 {
 182   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
 183   _GLIBCXX_DEBUG_ASSERT(p_next->m_p_next_sibling == 0);
 184
 185   if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value))
 186     {
 187       p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
 188       base_type::make_child_of(p_nd, p_next);
 189       PB_DS_ASSERT_NODE_CONSISTENT(p_next, false)
 190       return p_next;
 191     }
 192
 193   p_nd->m_p_next_sibling = 0;
 194   base_type::make_child_of(p_next, p_nd);
 195   PB_DS_ASSERT_NODE_CONSISTENT(p_nd, false)
 196   return p_nd;
 197 }
 198
 199 PB_DS_CLASS_T_DEC
 200 template<typename Pred>
 201 typename PB_DS_CLASS_C_DEC::size_type
 202 PB_DS_CLASS_C_DEC::
 203 erase_if(Pred pred)
 204 {
 205   PB_DS_ASSERT_VALID((*this))
 206     if (base_type::empty())
 207       {
 208         PB_DS_ASSERT_VALID((*this))
 209         return 0;
 210       }
 211   base_type::to_linked_list();
 212   node_pointer p_out = base_type::prune(pred);
 213   size_type ersd = 0;
 214   while (p_out != 0)
 215     {
 216       ++ersd;
 217       node_pointer p_next = p_out->m_p_next_sibling;
 218       base_type::actual_erase_node(p_out);
 219       p_out = p_next;
 220     }
 221
 222   node_pointer p_cur = base_type::m_p_root;
 223   base_type::m_p_root = 0;
 224   while (p_cur != 0)
 225     {
 226       node_pointer p_next = p_cur->m_p_next_sibling;
 227       p_cur->m_p_l_child = p_cur->m_p_next_sibling = p_cur->m_p_prev_or_parent = 0;
 228
 229       push_imp(p_cur);
 230       p_cur = p_next;
 231     }
 232   PB_DS_ASSERT_VALID((*this))
 233   return ersd;
 234 }
 235
 236 #endif