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 binary_heap_.hpp
44 * Contains an implementation class for a binary heap.
45 */
46
47#ifndef PB_DS_BINARY_HEAP_HPP
48#define PB_DS_BINARY_HEAP_HPP
49
50/*
51 * Based on CLRS.
52 */
53
54#include <queue>
55#include <algorithm>
56#include <ext/pb_ds/detail/cond_dealtor.hpp>
57#include <ext/pb_ds/detail/cond_dealtor.hpp>
58#include <ext/pb_ds/detail/type_utils.hpp>
59#include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp>
60#include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp>
61#include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp>
62#include <ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp>
63#include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp>
64#ifdef PB_DS_BINARY_HEAP_TRACE_
65#include <iostream>
66#endif
67#include <ext/pb_ds/detail/type_utils.hpp>
68#include <debug/debug.h>
69
70namespace pb_ds
71{
72  namespace detail
73  {
74#define PB_DS_CLASS_T_DEC \
75    template<typename Value_Type, class Cmp_Fn, class Allocator>
76
77#define PB_DS_CLASS_C_DEC \
78    binary_heap_<Value_Type, Cmp_Fn, Allocator>
79
80#define PB_DS_ENTRY_CMP_DEC \
81    entry_cmp<Value_Type, Cmp_Fn, is_simple<Value_Type>::value, Allocator>::type
82
83#define PB_DS_RESIZE_POLICY_DEC	\
84    resize_policy<typename Allocator::size_type>
85
86    /**
87     * class description = "Base class for some types of h3ap$">
88     **/
89    template<typename Value_Type, class Cmp_Fn, class Allocator>
90    class binary_heap_ : public PB_DS_ENTRY_CMP_DEC,
91			 public PB_DS_RESIZE_POLICY_DEC
92    {
93
94    private:
95      enum
96	{
97	  simple_value = is_simple<Value_Type>::value
98	};
99
100      typedef integral_constant<int, simple_value> no_throw_copies_t;
101
102      typedef
103      typename Allocator::template rebind<
104	Value_Type>::other
105      value_allocator;
106
107      typedef
108      typename __conditional_type<
109	simple_value,
110	Value_Type,
111	typename value_allocator::pointer>::__type
112      entry;
113
114      typedef
115      typename Allocator::template rebind<
116	entry>::other
117      entry_allocator;
118
119      typedef typename entry_allocator::pointer entry_pointer;
120
121      typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp;
122
123      typedef PB_DS_RESIZE_POLICY_DEC resize_policy;
124
125      typedef
126      cond_dealtor<
127	Value_Type,
128	Allocator>
129      cond_dealtor_t;
130
131    public:
132
133      typedef typename Allocator::size_type size_type;
134
135      typedef typename Allocator::difference_type difference_type;
136
137      typedef Value_Type value_type;
138
139      typedef
140      typename Allocator::template rebind<
141	value_type>::other::pointer
142      pointer;
143
144      typedef
145      typename Allocator::template rebind<
146	value_type>::other::const_pointer
147      const_pointer;
148
149      typedef
150      typename Allocator::template rebind<
151	value_type>::other::reference
152      reference;
153
154      typedef
155      typename Allocator::template rebind<
156	value_type>::other::const_reference
157      const_reference;
158
159      typedef
160      binary_heap_const_point_iterator_<
161	value_type,
162	entry,
163	simple_value,
164	Allocator>
165      const_point_iterator;
166
167      typedef const_point_iterator point_iterator;
168
169      typedef
170      binary_heap_const_iterator_<
171	value_type,
172	entry,
173	simple_value,
174	Allocator>
175      const_iterator;
176
177      typedef const_iterator iterator;
178
179      typedef Cmp_Fn cmp_fn;
180
181      typedef Allocator allocator;
182
183    public:
184
185      binary_heap_();
186
187      binary_heap_(const Cmp_Fn& r_cmp_fn);
188
189      binary_heap_(const PB_DS_CLASS_C_DEC& other);
190
191      void
192      swap(PB_DS_CLASS_C_DEC& other);
193
194      ~binary_heap_();
195
196      inline bool
197      empty() const;
198
199      inline size_type
200      size() const;
201
202      inline size_type
203      max_size() const;
204
205      Cmp_Fn&
206      get_cmp_fn();
207
208      const Cmp_Fn&
209      get_cmp_fn() const;
210
211      inline point_iterator
212      push(const_reference r_val);
213
214      void
215      modify(point_iterator it, const_reference r_new_val);
216
217      inline const_reference
218      top() const;
219
220      inline void
221      pop();
222
223      inline void
224      erase(point_iterator it);
225
226      template<typename Pred>
227      typename PB_DS_CLASS_C_DEC::size_type
228      erase_if(Pred pred);
229
230      inline static void
231      erase_at(entry_pointer a_entries, size_type size, false_type);
232
233      inline static void
234      erase_at(entry_pointer a_entries, size_type size, true_type);
235
236      inline iterator
237      begin();
238
239      inline const_iterator
240      begin() const;
241
242      inline iterator
243      end();
244
245      inline const_iterator
246      end() const;
247
248      void
249      clear();
250
251      template<typename Pred>
252      void
253      split(Pred pred, PB_DS_CLASS_C_DEC& other);
254
255      void
256      join(PB_DS_CLASS_C_DEC& other);
257
258#ifdef PB_DS_BINARY_HEAP_TRACE_
259      void
260      trace() const;
261#endif
262
263    protected:
264
265      template<typename It>
266      void
267      copy_from_range(It first_it, It last_it);
268
269    private:
270
271      void
272      value_swap(PB_DS_CLASS_C_DEC& other);
273
274      inline void
275      insert_value(const_reference r_val, false_type);
276
277      inline void
278      insert_value(value_type val, true_type);
279
280      inline void
281      insert_entry(entry e);
282
283      inline void
284      resize_for_insert_if_needed();
285
286      inline void
287      swap_value_imp(entry_pointer p_e, value_type new_val, true_type);
288
289      inline void
290      swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type);
291
292      void
293      fix(entry_pointer p_e);
294
295      inline const_reference
296      top_imp(true_type) const;
297
298      inline const_reference
299      top_imp(false_type) const;
300
301      inline static size_type
302      left_child(size_type i);
303
304      inline static size_type
305      right_child(size_type i);
306
307      inline static size_type
308      parent(size_type i);
309
310      inline void
311      resize_for_erase_if_needed();
312
313      template<typename Pred>
314      size_type
315      partition(Pred pred);
316
317#ifdef _GLIBCXX_DEBUG
318      void
319      assert_valid() const;
320#endif
321
322#ifdef PB_DS_BINARY_HEAP_TRACE_
323      void
324      trace_entry(const entry& r_e, false_type) const;
325
326      void
327      trace_entry(const entry& r_e, true_type) const;
328#endif
329
330    private:
331      static entry_allocator s_entry_allocator;
332
333      static value_allocator s_value_allocator;
334
335      static no_throw_copies_t s_no_throw_copies_ind;
336
337      size_type m_size;
338
339      size_type m_actual_size;
340
341      entry_pointer m_a_entries;
342    };
343
344#include <ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp>
345#include <ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp>
346#include <ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp>
347#include <ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp>
348#include <ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp>
349#include <ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp>
350#include <ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp>
351#include <ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp>
352#include <ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp>
353#include <ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp>
354
355#undef PB_DS_CLASS_C_DEC
356#undef PB_DS_CLASS_T_DEC
357#undef PB_DS_ENTRY_CMP_DEC
358#undef PB_DS_RESIZE_POLICY_DEC
359
360  } // namespace detail
361} // namespace pb_ds
362
363#endif
364