1// -*- C++ -*-
2
3// Copyright (C) 2005-2022 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 thin_heap_/thin_heap_.hpp
38 * Contains an implementation class for a thin heap.
39 */
40
41#ifndef PB_DS_THIN_HEAP_HPP
42#define PB_DS_THIN_HEAP_HPP
43
44#include <algorithm>
45#include <ext/pb_ds/detail/cond_dealtor.hpp>
46#include <ext/pb_ds/detail/type_utils.hpp>
47#include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
48#include <debug/debug.h>
49
50namespace __gnu_pbds
51{
52  namespace detail
53  {
54#define PB_DS_CLASS_T_DEC \
55    template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
56
57#define PB_DS_CLASS_C_DEC \
58    thin_heap<Value_Type, Cmp_Fn, _Alloc>
59
60#ifdef _GLIBCXX_DEBUG
61#define PB_DS_BASE_T_P \
62    <Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc, true>
63#else
64#define PB_DS_BASE_T_P \
65    <Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc>
66#endif
67
68
69    /**
70     *  Thin heap.
71     *
72     *  @ingroup heap-detail
73     *
74     *  See Tarjan and Kaplan.
75     */
76    template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
77    class thin_heap
78    : public left_child_next_sibling_heap PB_DS_BASE_T_P
79    {
80    private:
81      typedef rebind_traits<_Alloc, Value_Type>		  __rebind_a;
82      typedef left_child_next_sibling_heap PB_DS_BASE_T_P base_type;
83
84    protected:
85      typedef typename base_type::node 			node;
86      typedef typename base_type::node_pointer 		node_pointer;
87      typedef typename base_type::node_const_pointer 	node_const_pointer;
88
89    public:
90      typedef Value_Type 				value_type;
91      typedef Cmp_Fn 					cmp_fn;
92      typedef _Alloc 					allocator_type;
93      typedef typename _Alloc::size_type 		size_type;
94      typedef typename _Alloc::difference_type 		difference_type;
95
96      typedef typename __rebind_a::pointer		pointer;
97      typedef typename __rebind_a::const_pointer	const_pointer;
98      typedef typename __rebind_a::reference		reference;
99      typedef typename __rebind_a::const_reference     	const_reference;
100
101      typedef typename base_type::point_iterator 	point_iterator;
102      typedef typename base_type::point_const_iterator 	point_const_iterator;
103      typedef typename base_type::iterator 		iterator;
104      typedef typename base_type::const_iterator 	const_iterator;
105
106
107      inline point_iterator
108      push(const_reference);
109
110      void
111      modify(point_iterator, const_reference);
112
113      inline const_reference
114      top() const;
115
116      void
117      pop();
118
119      void
120      erase(point_iterator);
121
122      inline void
123      clear();
124
125      template<typename Pred>
126      size_type
127      erase_if(Pred);
128
129      template<typename Pred>
130      void
131      split(Pred, PB_DS_CLASS_C_DEC&);
132
133      void
134      join(PB_DS_CLASS_C_DEC&);
135
136    protected:
137      thin_heap();
138
139      thin_heap(const Cmp_Fn&);
140
141      thin_heap(const PB_DS_CLASS_C_DEC&);
142
143      void
144      swap(PB_DS_CLASS_C_DEC&);
145
146      ~thin_heap();
147
148      template<typename It>
149      void
150      copy_from_range(It, It);
151
152#ifdef _GLIBCXX_DEBUG
153      void
154      assert_valid(const char*, int) const;
155
156      void
157      assert_max(const char*, int) const;
158#endif
159
160#ifdef PB_DS_THIN_HEAP_TRACE_
161      void
162      trace() const;
163#endif
164
165    private:
166      enum
167	{
168	  max_rank = (sizeof(size_type) << 4) + 2
169	};
170
171      void
172      initialize();
173
174      inline void
175      update_max(node_pointer);
176
177      inline void
178      fix(node_pointer);
179
180      inline void
181      fix_root(node_pointer);
182
183      inline void
184      fix_sibling_rank_1_unmarked(node_pointer);
185
186      inline void
187      fix_sibling_rank_1_marked(node_pointer);
188
189      inline void
190      fix_sibling_general_unmarked(node_pointer);
191
192      inline void
193      fix_sibling_general_marked(node_pointer);
194
195      inline void
196      fix_child(node_pointer);
197
198      inline static void
199      make_root(node_pointer);
200
201      inline void
202      make_root_and_link(node_pointer);
203
204      inline void
205      remove_max_node();
206
207      void
208      to_aux_except_max();
209
210      inline void
211      add_to_aux(node_pointer);
212
213      inline void
214      make_from_aux();
215
216      inline size_type
217      rank_bound();
218
219      inline void
220      make_child_of(node_pointer, node_pointer);
221
222      inline void
223      remove_node(node_pointer);
224
225      inline node_pointer
226      join(node_pointer, node_pointer) const;
227
228#ifdef _GLIBCXX_DEBUG
229      void
230      assert_node_consistent(node_const_pointer, bool, const char*, int) const;
231
232      void
233      assert_aux_null(const char*, int) const;
234#endif
235
236      node_pointer 	m_p_max;
237      node_pointer 	m_a_aux[max_rank];
238    };
239
240    enum
241      {
242	num_distinct_rank_bounds = 48
243      };
244
245    // Taken from the SGI implementation; acknowledged in the docs.
246    static const std::size_t g_a_rank_bounds[num_distinct_rank_bounds] =
247      {
248	/* Dealing cards... */
249	/* 0     */ 0ul,
250	/* 1     */ 1ul,
251	/* 2     */ 1ul,
252	/* 3     */ 2ul,
253	/* 4     */ 4ul,
254	/* 5     */ 6ul,
255	/* 6     */ 11ul,
256	/* 7     */ 17ul,
257	/* 8     */ 29ul,
258	/* 9     */ 46ul,
259	/* 10    */ 76ul,
260	/* 11    */ 122ul,
261	/* 12    */ 199ul,
262	/* 13    */ 321ul,
263	/* 14    */ 521ul,
264	/* 15    */ 842ul,
265	/* 16    */ 1364ul,
266	/* 17    */ 2206ul,
267	/* 18    */ 3571ul,
268	/* 19    */ 5777ul,
269	/* 20    */ 9349ul,
270	/* 21    */ 15126ul,
271	/* 22    */ 24476ul,
272	/* 23    */ 39602ul,
273	/* 24    */ 64079ul
274#if __SIZE_MAX__ > 0xfffful
275	,
276	/* 25    */ 103681ul,
277	/* 26    */ 167761ul,
278	/* 27    */ 271442ul,
279	/* 28    */ 439204ul,
280	/* 29    */ 710646ul
281#if __SIZE_MAX__ > 0xffffful
282	,
283	/* 30    */ 1149851ul,
284	/* 31    */ 1860497ul,
285	/* 32    */ 3010349ul,
286	/* 33    */ 4870846ul,
287	/* 34    */ 7881196ul,
288	/* 35    */ 12752042ul
289#if __SIZE_MAX__ > 0xfffffful
290	,
291	/* 36    */ 20633239ul,
292	/* 37    */ 33385282ul,
293	/* 38    */ 54018521ul,
294	/* 39    */ 87403803ul,
295	/* 40    */ 141422324ul,
296	/* 41    */ 228826127ul,
297	/* 42    */ 370248451ul,
298	/* 43    */ 599074578ul,
299	/* 44    */ 969323029ul,
300	/* 45    */ 1568397607ul,
301	/* 46    */ 2537720636ul,
302	/* 47    */ 4106118243ul
303#endif
304#endif
305#endif
306	/* Pot's good, let's play */
307      };
308
309#define PB_DS_ASSERT_NODE_CONSISTENT(_Node, _Bool)			\
310  _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, _Bool,		\
311					     __FILE__, __LINE__);)
312
313#define PB_DS_ASSERT_AUX_NULL(X)					\
314  _GLIBCXX_DEBUG_ONLY(X.assert_aux_null(__FILE__, __LINE__);)
315
316#include <ext/pb_ds/detail/thin_heap_/constructors_destructor_fn_imps.hpp>
317#include <ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp>
318#include <ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp>
319#include <ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp>
320#include <ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp>
321#include <ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp>
322#include <ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp>
323
324#undef PB_DS_ASSERT_AUX_NULL
325#undef PB_DS_ASSERT_NODE_CONSISTENT
326#undef PB_DS_CLASS_C_DEC
327#undef PB_DS_CLASS_T_DEC
328#undef PB_DS_BASE_T_P
329
330  } // namespace detail
331} // namespace __gnu_pbds
332
333#endif
334