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