1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2018 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 left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp
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>
52 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp>
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>
56 #endif
57 #include <debug/debug.h>
58 
59 namespace __gnu_pbds
60 {
61   namespace detail
62   {
63 #ifdef _GLIBCXX_DEBUG
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.
81     template<typename Value_Type,
82 	     typename Cmp_Fn,
83 	     typename Node_Metadata,
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
91     {
92     protected:
93       typedef
94       typename _Alloc::template rebind<
95       left_child_next_sibling_heap_node_<Value_Type, Node_Metadata,
96 					 _Alloc> >::other
97       node_allocator;
98 
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;
102       typedef Node_Metadata node_metadata;
103       typedef std::pair< node_pointer, node_pointer> 	node_pointer_pair;
104 
105     private:
106       typedef cond_dealtor< node, _Alloc> 		cond_dealtor_t;
107 
108       enum
109 	{
110 	  simple_value = is_simple<Value_Type>::value
111 	};
112 
113       typedef integral_constant<int, simple_value> 	no_throw_copies_t;
114       typedef typename _Alloc::template rebind<Value_Type>	__rebind_v;
115 
116     public:
117       typedef typename _Alloc::size_type 		size_type;
118       typedef typename _Alloc::difference_type 	difference_type;
119       typedef Value_Type 				value_type;
120 
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;
125 
126       typedef left_child_next_sibling_heap_node_point_const_iterator_<node, _Alloc>
127       point_const_iterator;
128 
129       typedef point_const_iterator 			point_iterator;
130 
131       typedef left_child_next_sibling_heap_const_iterator_<node, _Alloc>
132       const_iterator;
133 
134       typedef const_iterator 				iterator;
135       typedef Cmp_Fn 					cmp_fn;
136       typedef _Alloc 					allocator_type;
137 
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&);
141 
142       void
143       swap(PB_DS_CLASS_C_DEC&);
144 
145       ~left_child_next_sibling_heap();
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 
156       Cmp_Fn&
157       get_cmp_fn();
158 
159       const Cmp_Fn&
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_
178       void
179       trace() const;
180 #endif
181 
182     protected:
183       inline node_pointer
184       get_new_node_for_insert(const_reference);
185 
186       inline static void
187       make_child_of(node_pointer, node_pointer);
188 
189       void
190       value_swap(left_child_next_sibling_heap&);
191 
192       inline static node_pointer
193       parent(node_pointer);
194 
195       inline void
196       swap_with_parent(node_pointer, node_pointer);
197 
198       void
199       bubble_to_top(node_pointer);
200 
201       inline void
202       actual_erase_node(node_pointer);
203 
204       void
205       clear_imp(node_pointer);
206 
207       void
208       to_linked_list();
209 
210       template<typename Pred>
211       node_pointer
212       prune(Pred);
213 
214 #ifdef _GLIBCXX_DEBUG
215       void
216       assert_valid(const char*, int) const;
217 
218       void
219       assert_node_consistent(node_const_pointer, bool, const char*, int) const;
220 
221       static size_type
222       size_under_node(node_const_pointer);
223 
224       static size_type
225       degree(node_const_pointer);
226 #endif
227 
228 #ifdef PB_DS_LC_NS_HEAP_TRACE_
229       static void
230       trace_node(node_const_pointer, size_type);
231 #endif
232 
233     private:
234 #ifdef _GLIBCXX_DEBUG
235       void
236       assert_iterators(const char*, int) const;
237 
238       void
239       assert_size(const char*, int) const;
240 
241       static size_type
242       size_from_node(node_const_pointer);
243 #endif
244 
245       node_pointer
246       recursive_copy_node(node_const_pointer);
247 
248       inline node_pointer
249       get_new_node_for_insert(const_reference, false_type);
250 
251       inline node_pointer
252       get_new_node_for_insert(const_reference, true_type);
253 
254 #ifdef PB_DS_LC_NS_HEAP_TRACE_
255       template<typename Metadata_>
256       static void
257       trace_node_metadata(node_const_pointer, type_to_type<Metadata_>);
258 
259       static void
260       trace_node_metadata(node_const_pointer, type_to_type<null_type>);
261 #endif
262 
263       static node_allocator 	s_node_allocator;
264       static no_throw_copies_t 	s_no_throw_copies_ind;
265 
266     protected:
267       node_pointer 		m_p_root;
268       size_type 		m_size;
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
281 #undef PB_DS_CLASS_T_DEC
282 
283   } // namespace detail
284 } // namespace __gnu_pbds
285 
286 #endif
287