libstdc++
thin_heap_.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2019 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>
48 #include <debug/debug.h>
49 
50 namespace __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 typename _Alloc::template rebind<Value_Type>::other __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;
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 
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
GNU extensions for policy-based data structures for public use.