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 binary_heap.
45 */
46
47PB_DS_CLASS_T_DEC
48void
49PB_DS_CLASS_C_DEC::
50clear()
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
77PB_DS_CLASS_T_DEC
78void
79PB_DS_CLASS_C_DEC::
80erase_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
87PB_DS_CLASS_T_DEC
88void
89PB_DS_CLASS_C_DEC::
90erase_at(entry_pointer, size_type, true_type)
91{ }
92
93PB_DS_CLASS_T_DEC
94inline void
95PB_DS_CLASS_C_DEC::
96pop()
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
113PB_DS_CLASS_T_DEC
114template<typename Pred>
115typename PB_DS_CLASS_C_DEC::size_type
116PB_DS_CLASS_C_DEC::
117erase_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
165PB_DS_CLASS_T_DEC
166inline void
167PB_DS_CLASS_C_DEC::
168erase(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
192PB_DS_CLASS_T_DEC
193inline void
194PB_DS_CLASS_C_DEC::
195resize_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
222PB_DS_CLASS_T_DEC
223template<typename Pred>
224typename PB_DS_CLASS_C_DEC::size_type
225PB_DS_CLASS_C_DEC::
226partition(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
253