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 binomial_heap_base_.hpp
44 * Contains an implementation class for a base of binomial heaps.
47 #ifndef PB_DS_BINOMIAL_HEAP_BASE_HPP
48 #define PB_DS_BINOMIAL_HEAP_BASE_HPP
52 * Vuillemin J is the mastah.
56 #include <debug/debug.h>
57 #include <ext/pb_ds/detail/cond_dealtor.hpp>
58 #include <ext/pb_ds/detail/type_utils.hpp>
59 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
60 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>
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 binomial_heap_base_<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, \
79 #define PB_DS_BASE_C_DEC \
80 left_child_next_sibling_heap_<Value_Type, Cmp_Fn, \
81 typename Allocator::size_type, Allocator>
85 * class description = "8y|\|0|\/|i41 h34p 74813">
87 template<typename Value_Type, class Cmp_Fn, class Allocator>
88 class binomial_heap_base_ : public PB_DS_BASE_C_DEC
92 typedef PB_DS_BASE_C_DEC base_type;
95 typedef typename base_type::node node;
97 typedef typename base_type::node_pointer node_pointer;
99 typedef typename base_type::const_node_pointer const_node_pointer;
103 typedef typename Allocator::size_type size_type;
105 typedef typename Allocator::difference_type difference_type;
107 typedef Value_Type value_type;
110 typename Allocator::template rebind<
111 value_type>::other::pointer
115 typename Allocator::template rebind<
116 value_type>::other::const_pointer
120 typename Allocator::template rebind<
121 value_type>::other::reference
125 typename Allocator::template rebind<
126 value_type>::other::const_reference
130 typename PB_DS_BASE_C_DEC::const_point_iterator
131 const_point_iterator;
133 typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator;
135 typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
137 typedef typename PB_DS_BASE_C_DEC::iterator iterator;
139 typedef Cmp_Fn cmp_fn;
141 typedef Allocator allocator;
145 inline point_iterator
146 push(const_reference r_val);
149 modify(point_iterator it, const_reference r_new_val);
151 inline const_reference
158 erase(point_iterator it);
163 template<typename Pred>
167 template<typename Pred>
169 split(Pred pred, PB_DS_CLASS_C_DEC& other);
172 join(PB_DS_CLASS_C_DEC& other);
176 binomial_heap_base_();
178 binomial_heap_base_(const Cmp_Fn& r_cmp_fn);
180 binomial_heap_base_(const PB_DS_CLASS_C_DEC& other);
183 swap(PB_DS_CLASS_C_DEC& other);
185 ~binomial_heap_base_();
187 template<typename It>
189 copy_from_range(It first_it, It last_it);
194 #ifdef _GLIBCXX_DEBUG
196 assert_valid(bool strictly_binomial) const;
205 fix(node_pointer p_nd) const;
208 insert_node(node_pointer p_nd);
211 remove_parentless_node(node_pointer p_nd);
214 join(node_pointer p_lhs, node_pointer p_rhs) const;
216 #ifdef _GLIBCXX_DEBUG
218 assert_node_consistent(const_node_pointer, bool, bool) const;
222 node_pointer m_p_max;
225 #include <ext/pb_ds/detail/binomial_heap_base_/constructors_destructor_fn_imps.hpp>
226 #include <ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp>
227 #include <ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp>
228 #include <ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp>
229 #include <ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp>
230 #include <ext/pb_ds/detail/binomial_heap_base_/split_join_fn_imps.hpp>
232 #undef PB_DS_CLASS_C_DEC
233 #undef PB_DS_CLASS_T_DEC
234 #undef PB_DS_BASE_C_DEC
237 } // namespace detail