contrib/libstdc++/include/ext/pb_ds/detail/binomial_heap_base_/split_join_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 split_join_fn_imps.hpp
  44  * Contains an implementation class for a base of binomial heaps.
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 template<typename Pred>
  49 void
  50 PB_DS_CLASS_C_DEC::
  51 split(Pred pred, PB_DS_CLASS_C_DEC& other)
  52 {
  53   _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
  54     _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)
  55
  56     other.clear();
  57
  58   if (base_type::empty())
  59     {
  60       _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
  61         _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)
  62
  63         return;
  64     }
  65
  66   base_type::to_linked_list();
  67
  68   node_pointer p_out = base_type::prune(pred);
  69
  70   while (p_out != NULL)
  71     {
  72       _GLIBCXX_DEBUG_ASSERT(base_type::m_size > 0);
  73       --base_type::m_size;
  74
  75       ++other.m_size;
  76
  77       node_pointer p_next = p_out->m_p_next_sibling;
  78
  79       p_out->m_p_l_child = p_out->m_p_prev_or_parent = NULL;
  80
  81       p_out->m_metadata = 0;
  82
  83       p_out->m_p_next_sibling = other.m_p_root;
  84
  85       if (other.m_p_root != NULL)
  86         other.m_p_root->m_p_prev_or_parent = p_out;
  87
  88       other.m_p_root = p_out;
  89
  90       other.m_p_root = other.fix(other.m_p_root);
  91
  92       p_out = p_next;
  93     }
  94
  95   _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)
  96
  97     node_pointer p_cur = base_type::m_p_root;
  98
  99   base_type::m_p_root = NULL;
 100
 101   while (p_cur != NULL)
 102     {
 103       node_pointer p_next = p_cur->m_p_next_sibling;
 104
 105       p_cur->m_p_l_child = p_cur->m_p_prev_or_parent = NULL;
 106
 107       p_cur->m_metadata = 0;
 108
 109       p_cur->m_p_next_sibling = base_type::m_p_root;
 110
 111       if (base_type::m_p_root != NULL)
 112         base_type::m_p_root->m_p_prev_or_parent = p_cur;
 113
 114       base_type::m_p_root = p_cur;
 115
 116       base_type::m_p_root = fix(base_type::m_p_root);
 117
 118       p_cur = p_next;
 119     }
 120
 121   m_p_max = NULL;
 122
 123   _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
 124     _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)
 125     }
 126
 127 PB_DS_CLASS_T_DEC
 128 inline void
 129 PB_DS_CLASS_C_DEC::
 130 join(PB_DS_CLASS_C_DEC& other)
 131 {
 132   _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
 133     _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)
 134
 135     node_pointer p_other = other.m_p_root;
 136
 137   if (p_other != NULL)
 138     do
 139       {
 140         node_pointer p_next = p_other->m_p_next_sibling;
 141
 142         std::swap(p_other->m_p_next_sibling, p_other->m_p_prev_or_parent);
 143
 144         p_other = p_next;
 145       }
 146     while (p_other != NULL);
 147
 148   base_type::m_p_root = join(base_type::m_p_root, other.m_p_root);
 149   base_type::m_size += other.m_size;
 150   m_p_max = NULL;
 151
 152   other.m_p_root = NULL;
 153   other.m_size = 0;
 154   other.m_p_max = NULL;
 155
 156   _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
 157     _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)
 158     }
 159
 160 PB_DS_CLASS_T_DEC
 161 inline typename PB_DS_CLASS_C_DEC::node_pointer
 162 PB_DS_CLASS_C_DEC::
 163 join(node_pointer p_lhs, node_pointer p_rhs) const
 164 {
 165   node_pointer p_ret = NULL;
 166
 167   node_pointer p_cur = NULL;
 168
 169   while (p_lhs != NULL || p_rhs != NULL)
 170     {
 171       if (p_rhs == NULL)
 172         {
 173           if (p_cur == NULL)
 174             p_ret = p_cur = p_lhs;
 175           else
 176             {
 177               p_cur->m_p_next_sibling = p_lhs;
 178
 179               p_lhs->m_p_prev_or_parent = p_cur;
 180             }
 181
 182           p_cur = p_lhs = NULL;
 183         }
 184       else if (p_lhs == NULL || p_rhs->m_metadata < p_lhs->m_metadata)
 185         {
 186           if (p_cur == NULL)
 187             {
 188               p_ret = p_cur = p_rhs;
 189
 190               p_rhs = p_rhs->m_p_prev_or_parent;
 191             }
 192           else
 193             {
 194               p_cur->m_p_next_sibling = p_rhs;
 195
 196               p_rhs = p_rhs->m_p_prev_or_parent;
 197
 198               p_cur->m_p_next_sibling->m_p_prev_or_parent = p_cur;
 199
 200               p_cur = p_cur->m_p_next_sibling;
 201             }
 202         }
 203       else if (p_lhs->m_metadata < p_rhs->m_metadata)
 204         {
 205           if (p_cur == NULL)
 206             p_ret = p_cur = p_lhs;
 207           else
 208             {
 209               p_cur->m_p_next_sibling = p_lhs;
 210
 211               p_lhs->m_p_prev_or_parent = p_cur;
 212
 213               p_cur = p_cur->m_p_next_sibling;
 214             }
 215
 216           p_lhs = p_cur->m_p_next_sibling;
 217         }
 218       else
 219         {
 220           node_pointer p_next_rhs = p_rhs->m_p_prev_or_parent;
 221
 222           p_rhs->m_p_next_sibling = p_lhs;
 223
 224           p_lhs = fix(p_rhs);
 225
 226           p_rhs = p_next_rhs;
 227         }
 228     }
 229
 230   if (p_cur != NULL)
 231     p_cur->m_p_next_sibling = NULL;
 232
 233   if (p_ret != NULL)
 234     p_ret->m_p_prev_or_parent = NULL;
 235
 236   return p_ret;
 237 }
 238