]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
f5886803 | 3 | // Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
4569a895 AT |
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 | /** | |
a345e45d | 37 | * @file left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp |
4569a895 AT |
38 | * Contains an implementation class for a basic heap. |
39 | */ | |
40 | ||
41 | #ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP | |
42 | #define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP | |
43 | ||
44 | /* | |
45 | * Based on CLRS. | |
46 | */ | |
47 | ||
48 | #include <iterator> | |
49 | #include <ext/pb_ds/detail/cond_dealtor.hpp> | |
50 | #include <ext/pb_ds/detail/type_utils.hpp> | |
51 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp> | |
a345e45d | 52 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp> |
4569a895 AT |
53 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp> |
54 | #ifdef PB_DS_LC_NS_HEAP_TRACE_ | |
55 | #include <iostream> | |
a345e45d | 56 | #endif |
47bea7b8 | 57 | #include <debug/debug.h> |
4569a895 | 58 | |
5e11f978 | 59 | namespace __gnu_pbds |
4569a895 AT |
60 | { |
61 | namespace detail | |
62 | { | |
47bea7b8 | 63 | #ifdef _GLIBCXX_DEBUG |
a345e45d BK |
64 | #define PB_DS_CLASS_T_DEC \ |
65 | template<typename Value_Type, typename Cmp_Fn, typename Node_Metadata, \ | |
66 | typename _Alloc, bool Single_Link_Roots> | |
67 | ||
68 | #define PB_DS_CLASS_C_DEC \ | |
69 | left_child_next_sibling_heap<Value_Type, Cmp_Fn, Node_Metadata, \ | |
70 | _Alloc, Single_Link_Roots> | |
71 | #else | |
72 | #define PB_DS_CLASS_T_DEC \ | |
73 | template<typename Value_Type, typename Cmp_Fn, typename Node_Metadata, \ | |
74 | typename _Alloc> | |
75 | ||
76 | #define PB_DS_CLASS_C_DEC \ | |
77 | left_child_next_sibling_heap<Value_Type, Cmp_Fn, Node_Metadata, _Alloc> | |
78 | #endif | |
79 | ||
80 | /// Base class for a basic heap. | |
4569a895 | 81 | template<typename Value_Type, |
a345e45d | 82 | typename Cmp_Fn, |
4569a895 | 83 | typename Node_Metadata, |
a345e45d BK |
84 | typename _Alloc |
85 | #ifdef _GLIBCXX_DEBUG | |
86 | ,bool Single_Link_Roots> | |
87 | #else | |
88 | > | |
89 | #endif | |
90 | class left_child_next_sibling_heap : public Cmp_Fn | |
4569a895 | 91 | { |
4569a895 AT |
92 | protected: |
93 | typedef | |
a345e45d | 94 | typename _Alloc::template rebind< |
30a96b3b | 95 | left_child_next_sibling_heap_node_<Value_Type, Node_Metadata, |
a345e45d | 96 | _Alloc> >::other |
4569a895 AT |
97 | node_allocator; |
98 | ||
a345e45d BK |
99 | typedef typename node_allocator::value_type node; |
100 | typedef typename node_allocator::pointer node_pointer; | |
101 | typedef typename node_allocator::const_pointer node_const_pointer; | |
4569a895 | 102 | typedef Node_Metadata node_metadata; |
a345e45d | 103 | typedef std::pair< node_pointer, node_pointer> node_pointer_pair; |
4569a895 AT |
104 | |
105 | private: | |
a345e45d | 106 | typedef cond_dealtor< node, _Alloc> cond_dealtor_t; |
4569a895 AT |
107 | |
108 | enum | |
109 | { | |
47bea7b8 | 110 | simple_value = is_simple<Value_Type>::value |
4569a895 AT |
111 | }; |
112 | ||
a345e45d BK |
113 | typedef integral_constant<int, simple_value> no_throw_copies_t; |
114 | typedef typename _Alloc::template rebind<Value_Type> __rebind_v; | |
4569a895 AT |
115 | |
116 | public: | |
a345e45d BK |
117 | typedef typename _Alloc::size_type size_type; |
118 | typedef typename _Alloc::difference_type difference_type; | |
119 | typedef Value_Type value_type; | |
4569a895 | 120 | |
a345e45d BK |
121 | typedef typename __rebind_v::other::pointer pointer; |
122 | typedef typename __rebind_v::other::const_pointer const_pointer; | |
123 | typedef typename __rebind_v::other::reference reference; | |
124 | typedef typename __rebind_v::other::const_reference const_reference; | |
4569a895 | 125 | |
a345e45d BK |
126 | typedef left_child_next_sibling_heap_node_point_const_iterator_<node, _Alloc> |
127 | point_const_iterator; | |
4569a895 | 128 | |
a345e45d | 129 | typedef point_const_iterator point_iterator; |
4569a895 | 130 | |
a345e45d | 131 | typedef left_child_next_sibling_heap_const_iterator_<node, _Alloc> |
4569a895 AT |
132 | const_iterator; |
133 | ||
a345e45d BK |
134 | typedef const_iterator iterator; |
135 | typedef Cmp_Fn cmp_fn; | |
136 | typedef _Alloc allocator_type; | |
4569a895 | 137 | |
a345e45d BK |
138 | left_child_next_sibling_heap(); |
139 | left_child_next_sibling_heap(const Cmp_Fn&); | |
140 | left_child_next_sibling_heap(const left_child_next_sibling_heap&); | |
4569a895 AT |
141 | |
142 | void | |
a345e45d | 143 | swap(PB_DS_CLASS_C_DEC&); |
4569a895 | 144 | |
a345e45d | 145 | ~left_child_next_sibling_heap(); |
4569a895 AT |
146 | |
147 | inline bool | |
148 | empty() const; | |
149 | ||
150 | inline size_type | |
151 | size() const; | |
152 | ||
153 | inline size_type | |
154 | max_size() const; | |
155 | ||
a345e45d | 156 | Cmp_Fn& |
4569a895 AT |
157 | get_cmp_fn(); |
158 | ||
a345e45d | 159 | const Cmp_Fn& |
4569a895 AT |
160 | get_cmp_fn() const; |
161 | ||
162 | inline iterator | |
163 | begin(); | |
164 | ||
165 | inline const_iterator | |
166 | begin() const; | |
167 | ||
168 | inline iterator | |
169 | end(); | |
170 | ||
171 | inline const_iterator | |
172 | end() const; | |
173 | ||
174 | void | |
175 | clear(); | |
176 | ||
177 | #ifdef PB_DS_LC_NS_HEAP_TRACE_ | |
4569a895 AT |
178 | void |
179 | trace() const; | |
a345e45d | 180 | #endif |
4569a895 AT |
181 | |
182 | protected: | |
4569a895 | 183 | inline node_pointer |
a345e45d | 184 | get_new_node_for_insert(const_reference); |
4569a895 AT |
185 | |
186 | inline static void | |
a345e45d | 187 | make_child_of(node_pointer, node_pointer); |
4569a895 AT |
188 | |
189 | void | |
a345e45d | 190 | value_swap(left_child_next_sibling_heap&); |
4569a895 AT |
191 | |
192 | inline static node_pointer | |
a345e45d | 193 | parent(node_pointer); |
4569a895 AT |
194 | |
195 | inline void | |
a345e45d | 196 | swap_with_parent(node_pointer, node_pointer); |
4569a895 AT |
197 | |
198 | void | |
a345e45d | 199 | bubble_to_top(node_pointer); |
4569a895 AT |
200 | |
201 | inline void | |
a345e45d | 202 | actual_erase_node(node_pointer); |
4569a895 AT |
203 | |
204 | void | |
a345e45d | 205 | clear_imp(node_pointer); |
4569a895 AT |
206 | |
207 | void | |
208 | to_linked_list(); | |
209 | ||
210 | template<typename Pred> | |
211 | node_pointer | |
a345e45d | 212 | prune(Pred); |
4569a895 | 213 | |
47bea7b8 | 214 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 215 | void |
a345e45d | 216 | assert_valid(const char*, int) const; |
4569a895 AT |
217 | |
218 | void | |
a345e45d | 219 | assert_node_consistent(node_const_pointer, bool, const char*, int) const; |
4569a895 AT |
220 | |
221 | static size_type | |
a345e45d | 222 | size_under_node(node_const_pointer); |
4569a895 AT |
223 | |
224 | static size_type | |
a345e45d BK |
225 | degree(node_const_pointer); |
226 | #endif | |
4569a895 AT |
227 | |
228 | #ifdef PB_DS_LC_NS_HEAP_TRACE_ | |
4569a895 | 229 | static void |
a345e45d BK |
230 | trace_node(node_const_pointer, size_type); |
231 | #endif | |
4569a895 AT |
232 | |
233 | private: | |
47bea7b8 | 234 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 235 | void |
a345e45d | 236 | assert_iterators(const char*, int) const; |
4569a895 AT |
237 | |
238 | void | |
a345e45d | 239 | assert_size(const char*, int) const; |
4569a895 AT |
240 | |
241 | static size_type | |
a345e45d BK |
242 | size_from_node(node_const_pointer); |
243 | #endif | |
4569a895 AT |
244 | |
245 | node_pointer | |
a345e45d | 246 | recursive_copy_node(node_const_pointer); |
4569a895 AT |
247 | |
248 | inline node_pointer | |
a345e45d | 249 | get_new_node_for_insert(const_reference, false_type); |
4569a895 AT |
250 | |
251 | inline node_pointer | |
a345e45d | 252 | get_new_node_for_insert(const_reference, true_type); |
4569a895 AT |
253 | |
254 | #ifdef PB_DS_LC_NS_HEAP_TRACE_ | |
4569a895 AT |
255 | template<typename Metadata_> |
256 | static void | |
a345e45d | 257 | trace_node_metadata(node_const_pointer, type_to_type<Metadata_>); |
4569a895 AT |
258 | |
259 | static void | |
30a96b3b | 260 | trace_node_metadata(node_const_pointer, type_to_type<null_type>); |
a345e45d | 261 | #endif |
4569a895 | 262 | |
a345e45d BK |
263 | static node_allocator s_node_allocator; |
264 | static no_throw_copies_t s_no_throw_copies_ind; | |
30a96b3b BK |
265 | |
266 | protected: | |
267 | node_pointer m_p_root; | |
268 | size_type m_size; | |
4569a895 AT |
269 | }; |
270 | ||
271 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp> | |
272 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp> | |
273 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp> | |
274 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp> | |
275 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp> | |
276 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp> | |
277 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp> | |
278 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp> | |
279 | ||
280 | #undef PB_DS_CLASS_C_DEC | |
4569a895 AT |
281 | #undef PB_DS_CLASS_T_DEC |
282 | ||
4569a895 | 283 | } // namespace detail |
5e11f978 | 284 | } // namespace __gnu_pbds |
4569a895 | 285 | |
a345e45d | 286 | #endif |