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