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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 2008, 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 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 binary_heap.
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 void
  49 PB_DS_CLASS_C_DEC::
  50 clear()
  51 {
  52   for (size_type i = 0; i < m_size; ++i)
  53     erase_at(m_a_entries, i, s_no_throw_copies_ind);
  54
  55   __try
  56     {
  57       const size_type actual_size = resize_policy::get_new_size_for_arbitrary(0);
  58
  59       entry_pointer a_entries = s_entry_allocator.allocate(actual_size);
  60
  61       resize_policy::notify_arbitrary(actual_size);
  62
  63       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
  64
  65       m_actual_size = actual_size;
  66
  67       m_a_entries = a_entries;
  68     }
  69   __catch(...)
  70     { }
  71
  72   m_size = 0;
  73
  74   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  75     }
  76
  77 PB_DS_CLASS_T_DEC
  78 void
  79 PB_DS_CLASS_C_DEC::
  80 erase_at(entry_pointer a_entries, size_type i, false_type)
  81 {
  82   a_entries[i]->~value_type();
  83
  84   s_value_allocator.deallocate(a_entries[i], 1);
  85 }
  86
  87 PB_DS_CLASS_T_DEC
  88 void
  89 PB_DS_CLASS_C_DEC::
  90 erase_at(entry_pointer, size_type, true_type)
  91 { }
  92
  93 PB_DS_CLASS_T_DEC
  94 inline void
  95 PB_DS_CLASS_C_DEC::
  96 pop()
  97 {
  98   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  99     _GLIBCXX_DEBUG_ASSERT(!empty());
 100
 101   erase_at(m_a_entries, 0, s_no_throw_copies_ind);
 102
 103   std::pop_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));
 104
 105   resize_for_erase_if_needed();
 106
 107   _GLIBCXX_DEBUG_ASSERT(m_size > 0);
 108   --m_size;
 109
 110   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 111     }
 112
 113 PB_DS_CLASS_T_DEC
 114 template<typename Pred>
 115 typename PB_DS_CLASS_C_DEC::size_type
 116 PB_DS_CLASS_C_DEC::
 117 erase_if(Pred pred)
 118 {
 119   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 120
 121     typedef
 122     typename entry_pred<
 123     value_type,
 124     Pred,
 125     simple_value,
 126     Allocator>::type
 127     pred_t;
 128
 129   const size_type left = partition(pred_t(pred));
 130
 131   _GLIBCXX_DEBUG_ASSERT(m_size >= left);
 132
 133   const size_type ersd = m_size - left;
 134
 135   for (size_type i = left; i < m_size; ++i)
 136     erase_at(m_a_entries, i, s_no_throw_copies_ind);
 137
 138   __try
 139     {
 140       const size_type actual_size =
 141         resize_policy::get_new_size_for_arbitrary(left);
 142
 143       entry_pointer a_entries = s_entry_allocator.allocate(actual_size);
 144
 145       std::copy(m_a_entries, m_a_entries + left, a_entries);
 146
 147       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
 148
 149       m_actual_size = actual_size;
 150
 151       resize_policy::notify_arbitrary(m_actual_size);
 152     }
 153   __catch(...)
 154     { };
 155
 156   m_size = left;
 157
 158   std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));
 159
 160   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 161
 162     return ersd;
 163 }
 164
 165 PB_DS_CLASS_T_DEC
 166 inline void
 167 PB_DS_CLASS_C_DEC::
 168 erase(point_iterator it)
 169 {
 170   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 171     _GLIBCXX_DEBUG_ASSERT(!empty());
 172
 173   const size_type fix_pos = it.m_p_e - m_a_entries;
 174
 175   std::swap(*it.m_p_e, m_a_entries[m_size - 1]);
 176
 177   erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);
 178
 179   resize_for_erase_if_needed();
 180
 181   _GLIBCXX_DEBUG_ASSERT(m_size > 0);
 182   --m_size;
 183
 184   _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size);
 185
 186   if (fix_pos != m_size)
 187     fix(m_a_entries + fix_pos);
 188
 189   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 190     }
 191
 192 PB_DS_CLASS_T_DEC
 193 inline void
 194 PB_DS_CLASS_C_DEC::
 195 resize_for_erase_if_needed()
 196 {
 197   if (!resize_policy::resize_needed_for_shrink(m_size))
 198     return;
 199
 200   __try
 201     {
 202       const size_type new_actual_size =
 203         resize_policy::get_new_size_for_shrink();
 204
 205       entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size);
 206
 207       resize_policy::notify_shrink_resize();
 208
 209       _GLIBCXX_DEBUG_ASSERT(m_size > 0);
 210       std::copy(m_a_entries, m_a_entries + m_size - 1, a_new_entries);
 211
 212       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
 213
 214       m_actual_size = new_actual_size;
 215
 216       m_a_entries = a_new_entries;
 217     }
 218   __catch(...)
 219     { }
 220 }
 221
 222 PB_DS_CLASS_T_DEC
 223 template<typename Pred>
 224 typename PB_DS_CLASS_C_DEC::size_type
 225 PB_DS_CLASS_C_DEC::
 226 partition(Pred pred)
 227 {
 228   size_type left = 0;
 229   size_type right = m_size - 1;
 230
 231   while (right + 1 != left)
 232     {
 233       _GLIBCXX_DEBUG_ASSERT(left <= m_size);
 234
 235       if (!pred(m_a_entries[left]))
 236         ++left;
 237       else if (pred(m_a_entries[right]))
 238         --right;
 239       else
 240         {
 241           _GLIBCXX_DEBUG_ASSERT(left < right);
 242
 243           std::swap(m_a_entries[left], m_a_entries[right]);
 244
 245           ++left;
 246           --right;
 247         }
 248     }
 249
 250   return left;
 251 }
 252