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