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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2011
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the terms
   8 // of the GNU General Public License as published by the Free Software
   9 // Foundation; either version 3, or (at your option) any later
  10 // version.
  11
  12 // This library is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 // General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  27
  28 // Permission to use, copy, modify, sell, and distribute this software
  29 // is hereby granted without fee, provided that the above copyright
  30 // notice appears in all copies, and that both that copyright notice
  31 // and this permission notice appear in supporting documentation. None
  32 // of the above authors, nor IBM Haifa Research Laboratories, make any
  33 // representation about the suitability of this software for any
  34 // purpose. It is provided "as is" without express or implied
  35 // warranty.
  36
  37 /**
  38  * @file erase_fn_imps.hpp
  39  * Contains an implementation class for a binary_heap.
  40  */
  41
  42 PB_DS_CLASS_T_DEC
  43 void
  44 PB_DS_CLASS_C_DEC::
  45 clear()
  46 {
  47   for (size_type i = 0; i < m_size; ++i)
  48     erase_at(m_a_entries, i, s_no_throw_copies_ind);
  49
  50   __try
  51     {
  52       const size_type actual_size = resize_policy::get_new_size_for_arbitrary(0);
  53
  54       entry_pointer a_entries = s_entry_allocator.allocate(actual_size);
  55
  56       resize_policy::notify_arbitrary(actual_size);
  57
  58       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
  59
  60       m_actual_size = actual_size;
  61
  62       m_a_entries = a_entries;
  63     }
  64   __catch(...)
  65     { }
  66
  67   m_size = 0;
  68
  69   PB_DS_ASSERT_VALID((*this))
  70 }
  71
  72 PB_DS_CLASS_T_DEC
  73 void
  74 PB_DS_CLASS_C_DEC::
  75 erase_at(entry_pointer a_entries, size_type i, false_type)
  76 {
  77   a_entries[i]->~value_type();
  78   s_value_allocator.deallocate(a_entries[i], 1);
  79 }
  80
  81 PB_DS_CLASS_T_DEC
  82 void
  83 PB_DS_CLASS_C_DEC::
  84 erase_at(entry_pointer, size_type, true_type)
  85 { }
  86
  87 PB_DS_CLASS_T_DEC
  88 inline void
  89 PB_DS_CLASS_C_DEC::
  90 pop()
  91 {
  92   PB_DS_ASSERT_VALID((*this))
  93   _GLIBCXX_DEBUG_ASSERT(!empty());
  94
  95   erase_at(m_a_entries, 0, s_no_throw_copies_ind);
  96
  97   std::pop_heap(m_a_entries, m_a_entries + m_size,
  98                 static_cast<entry_cmp& >(*this));
  99
 100   resize_for_erase_if_needed();
 101
 102   _GLIBCXX_DEBUG_ASSERT(m_size > 0);
 103   --m_size;
 104
 105   PB_DS_ASSERT_VALID((*this))
 106 }
 107
 108 PB_DS_CLASS_T_DEC
 109 template<typename Pred>
 110 typename PB_DS_CLASS_C_DEC::size_type
 111 PB_DS_CLASS_C_DEC::
 112 erase_if(Pred pred)
 113 {
 114   PB_DS_ASSERT_VALID((*this))
 115
 116   typedef typename entry_pred<value_type, Pred, simple_value, Allocator>::type
 117     pred_t;
 118
 119   const size_type left = partition(pred_t(pred));
 120
 121   _GLIBCXX_DEBUG_ASSERT(m_size >= left);
 122
 123   const size_type ersd = m_size - left;
 124
 125   for (size_type i = left; i < m_size; ++i)
 126     erase_at(m_a_entries, i, s_no_throw_copies_ind);
 127
 128   __try
 129     {
 130       const size_type actual_size =
 131         resize_policy::get_new_size_for_arbitrary(left);
 132
 133       entry_pointer a_entries = s_entry_allocator.allocate(actual_size);
 134
 135       std::copy(m_a_entries, m_a_entries + left, a_entries);
 136
 137       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
 138
 139       m_actual_size = actual_size;
 140
 141       resize_policy::notify_arbitrary(m_actual_size);
 142     }
 143   __catch(...)
 144     { };
 145
 146   m_size = left;
 147
 148   std::make_heap(m_a_entries, m_a_entries + m_size,
 149                  static_cast<entry_cmp& >(*this));
 150
 151   PB_DS_ASSERT_VALID((*this))
 152
 153   return ersd;
 154 }
 155
 156 PB_DS_CLASS_T_DEC
 157 inline void
 158 PB_DS_CLASS_C_DEC::
 159 erase(point_iterator it)
 160 {
 161   PB_DS_ASSERT_VALID((*this))
 162   _GLIBCXX_DEBUG_ASSERT(!empty());
 163
 164   const size_type fix_pos = it.m_p_e - m_a_entries;
 165
 166   std::swap(*it.m_p_e, m_a_entries[m_size - 1]);
 167
 168   erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);
 169
 170   resize_for_erase_if_needed();
 171
 172   _GLIBCXX_DEBUG_ASSERT(m_size > 0);
 173   --m_size;
 174
 175   _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size);
 176
 177   if (fix_pos != m_size)
 178     fix(m_a_entries + fix_pos);
 179
 180   PB_DS_ASSERT_VALID((*this))
 181 }
 182
 183 PB_DS_CLASS_T_DEC
 184 inline void
 185 PB_DS_CLASS_C_DEC::
 186 resize_for_erase_if_needed()
 187 {
 188   if (!resize_policy::resize_needed_for_shrink(m_size))
 189     return;
 190
 191   __try
 192     {
 193       const size_type new_actual_size =
 194         resize_policy::get_new_size_for_shrink();
 195
 196       entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size);
 197
 198       resize_policy::notify_shrink_resize();
 199
 200       _GLIBCXX_DEBUG_ASSERT(m_size > 0);
 201       std::copy(m_a_entries, m_a_entries + m_size - 1, a_new_entries);
 202
 203       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
 204
 205       m_actual_size = new_actual_size;
 206
 207       m_a_entries = a_new_entries;
 208     }
 209   __catch(...)
 210     { }
 211 }
 212
 213 PB_DS_CLASS_T_DEC
 214 template<typename Pred>
 215 typename PB_DS_CLASS_C_DEC::size_type
 216 PB_DS_CLASS_C_DEC::
 217 partition(Pred pred)
 218 {
 219   size_type left = 0;
 220   size_type right = m_size - 1;
 221
 222   while (right + 1 != left)
 223     {
 224       _GLIBCXX_DEBUG_ASSERT(left <= m_size);
 225
 226       if (!pred(m_a_entries[left]))
 227         ++left;
 228       else if (pred(m_a_entries[right]))
 229         --right;
 230       else
 231         {
 232           _GLIBCXX_DEBUG_ASSERT(left < right);
 233
 234           std::swap(m_a_entries[left], m_a_entries[right]);
 235
 236           ++left;
 237           --right;
 238         }
 239     }
 240
 241   return left;
 242 }