3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
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
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.
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.
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
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
43 * @file thin_heap_.hpp
44 * Contains an implementation class for a thin heap.
47 #ifndef PB_DS_THIN_HEAP_HPP
48 #define PB_DS_THIN_HEAP_HPP
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>
67 #define PB_DS_CLASS_T_DEC \
68 template<typename Value_Type, class Cmp_Fn, class Allocator>
70 #define PB_DS_CLASS_C_DEC \
71 thin_heap_<Value_Type, Cmp_Fn, Allocator>
74 #define PB_DS_BASE_C_DEC \
75 left_child_next_sibling_heap_<Value_Type, Cmp_Fn, \
76 typename Allocator::size_type, Allocator, true>
78 #define PB_DS_BASE_C_DEC \
79 left_child_next_sibling_heap_<Value_Type, Cmp_Fn, \
80 typename Allocator::size_type, Allocator>
84 * class description = "t|-|i|\| h34p">
86 template<typename Value_Type, class Cmp_Fn, class Allocator>
87 class thin_heap_ : public PB_DS_BASE_C_DEC
91 typedef PB_DS_BASE_C_DEC base_type;
94 typedef typename base_type::node node;
96 typedef typename base_type::node_pointer node_pointer;
98 typedef typename base_type::const_node_pointer const_node_pointer;
102 typedef typename Allocator::size_type size_type;
104 typedef typename Allocator::difference_type difference_type;
106 typedef Value_Type value_type;
109 typename Allocator::template rebind<
110 value_type>::other::pointer
114 typename Allocator::template rebind<
115 value_type>::other::const_pointer
119 typename Allocator::template rebind<
120 value_type>::other::reference
124 typename Allocator::template rebind<
125 value_type>::other::const_reference
129 typename PB_DS_BASE_C_DEC::const_point_iterator
130 const_point_iterator;
132 typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator;
134 typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
136 typedef typename PB_DS_BASE_C_DEC::iterator iterator;
138 typedef Cmp_Fn cmp_fn;
140 typedef Allocator allocator;
144 inline point_iterator
145 push(const_reference r_val);
148 modify(point_iterator it, const_reference r_new_val);
150 inline const_reference
157 erase(point_iterator it);
162 template<typename Pred>
166 template<typename Pred>
168 split(Pred pred, PB_DS_CLASS_C_DEC& other);
171 join(PB_DS_CLASS_C_DEC& other);
177 thin_heap_(const Cmp_Fn& r_cmp_fn);
179 thin_heap_(const PB_DS_CLASS_C_DEC& other);
182 swap(PB_DS_CLASS_C_DEC& other);
186 template<typename It>
188 copy_from_range(It first_it, It last_it);
190 #ifdef _GLIBCXX_DEBUG
192 assert_valid() const;
198 #ifdef PB_DS_THIN_HEAP_TRACE_
206 max_rank = (sizeof(size_type) << 4) + 2
215 update_max(node_pointer p_nd);
218 fix(node_pointer p_nd);
221 fix_root(node_pointer p_y);
224 fix_sibling_rank_1_unmarked(node_pointer p_y);
227 fix_sibling_rank_1_marked(node_pointer p_y);
230 fix_sibling_general_unmarked(node_pointer p_y);
233 fix_sibling_general_marked(node_pointer p_y);
236 fix_child(node_pointer p_y);
239 make_root(node_pointer p_nd);
242 make_root_and_link(node_pointer p_nd);
251 add_to_aux(node_pointer p_nd);
260 make_child_of(node_pointer p_nd, node_pointer p_new_parent);
263 remove_node(node_pointer p_nd);
266 join(node_pointer p_lhs, node_pointer p_rhs) const;
268 #ifdef _GLIBCXX_DEBUG
270 assert_node_consistent(const_node_pointer p_nd, bool root) const;
273 assert_aux_null() const;
277 node_pointer m_p_max;
279 node_pointer m_a_aux[max_rank];
284 num_distinct_rank_bounds = 48
287 // Taken from the SGI implementation; acknowledged in the docs.
288 static const std::size_t g_a_rank_bounds[num_distinct_rank_bounds] =
290 /* Dealing cards... */
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 */
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>
350 #undef PB_DS_CLASS_C_DEC
351 #undef PB_DS_CLASS_T_DEC
352 #undef PB_DS_BASE_C_DEC
354 } // namespace detail