]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2005-2022 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. | |
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/>. | |
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 pairing_heap_/pairing_heap_.hpp |
4569a895 AT |
38 | * Contains an implementation class for a pairing heap. |
39 | */ | |
40 | ||
41 | /* | |
42 | * Pairing heap: | |
43 | * Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, | |
44 | * and Robert Endre Tarjan, The Pairing Heap: | |
45 | * A New Form of Self-Adjusting Heap, Algorithmica, 1(1):111-129, 1986. | |
46 | */ | |
47 | ||
48 | #include <ext/pb_ds/detail/cond_dealtor.hpp> | |
49 | #include <ext/pb_ds/detail/type_utils.hpp> | |
50 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp> | |
47bea7b8 | 51 | #include <debug/debug.h> |
4569a895 | 52 | |
5e11f978 | 53 | namespace __gnu_pbds |
4569a895 AT |
54 | { |
55 | namespace detail | |
56 | { | |
47bea7b8 | 57 | #define PB_DS_CLASS_T_DEC \ |
a345e45d | 58 | template<typename Value_Type, typename Cmp_Fn, typename _Alloc> |
4569a895 | 59 | |
47bea7b8 | 60 | #define PB_DS_CLASS_C_DEC \ |
a345e45d | 61 | pairing_heap<Value_Type, Cmp_Fn, _Alloc> |
4569a895 | 62 | |
47bea7b8 | 63 | #ifdef _GLIBCXX_DEBUG |
a345e45d BK |
64 | #define PB_DS_P_HEAP_BASE \ |
65 | left_child_next_sibling_heap<Value_Type, Cmp_Fn, null_type, _Alloc, false> | |
66 | #else | |
67 | #define PB_DS_P_HEAP_BASE \ | |
68 | left_child_next_sibling_heap<Value_Type, Cmp_Fn, null_type, _Alloc> | |
69 | #endif | |
4569a895 | 70 | |
30a96b3b BK |
71 | /** |
72 | * Pairing heap. | |
73 | * | |
74 | * @ingroup heap-detail | |
75 | */ | |
a345e45d BK |
76 | template<typename Value_Type, typename Cmp_Fn, typename _Alloc> |
77 | class pairing_heap : public PB_DS_P_HEAP_BASE | |
78 | { | |
4569a895 | 79 | private: |
a345e45d BK |
80 | typedef PB_DS_P_HEAP_BASE base_type; |
81 | typedef typename base_type::node_pointer node_pointer; | |
4569a895 | 82 | |
ec541f1b | 83 | typedef rebind_traits<_Alloc, Value_Type> __rebind_a; |
4569a895 AT |
84 | |
85 | public: | |
a345e45d BK |
86 | typedef Value_Type value_type; |
87 | typedef Cmp_Fn cmp_fn; | |
88 | typedef _Alloc allocator_type; | |
89 | typedef typename _Alloc::size_type size_type; | |
90 | typedef typename _Alloc::difference_type difference_type; | |
4569a895 | 91 | |
a345e45d BK |
92 | typedef typename __rebind_a::pointer pointer; |
93 | typedef typename __rebind_a::const_pointer const_pointer; | |
94 | typedef typename __rebind_a::reference reference; | |
95 | typedef typename __rebind_a::const_reference const_reference; | |
4569a895 | 96 | |
a345e45d BK |
97 | typedef typename base_type::point_const_iterator point_const_iterator; |
98 | typedef typename base_type::point_iterator point_iterator; | |
99 | typedef typename base_type::const_iterator const_iterator; | |
100 | typedef typename base_type::iterator iterator; | |
4569a895 | 101 | |
a345e45d | 102 | pairing_heap(); |
4569a895 | 103 | |
a345e45d | 104 | pairing_heap(const Cmp_Fn&); |
4569a895 | 105 | |
a345e45d | 106 | pairing_heap(const pairing_heap&); |
4569a895 AT |
107 | |
108 | void | |
a345e45d | 109 | swap(pairing_heap&); |
4569a895 | 110 | |
a345e45d | 111 | ~pairing_heap(); |
4569a895 AT |
112 | |
113 | inline point_iterator | |
a345e45d | 114 | push(const_reference); |
4569a895 AT |
115 | |
116 | void | |
a345e45d | 117 | modify(point_iterator, const_reference); |
4569a895 AT |
118 | |
119 | inline const_reference | |
120 | top() const; | |
121 | ||
122 | void | |
123 | pop(); | |
124 | ||
125 | void | |
a345e45d | 126 | erase(point_iterator); |
4569a895 AT |
127 | |
128 | template<typename Pred> | |
129 | size_type | |
a345e45d | 130 | erase_if(Pred); |
4569a895 AT |
131 | |
132 | template<typename Pred> | |
133 | void | |
a345e45d | 134 | split(Pred, pairing_heap&); |
4569a895 AT |
135 | |
136 | void | |
a345e45d | 137 | join(pairing_heap&); |
4569a895 AT |
138 | |
139 | protected: | |
140 | ||
141 | template<typename It> | |
142 | void | |
a345e45d | 143 | copy_from_range(It, It); |
4569a895 | 144 | |
47bea7b8 | 145 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 146 | void |
a345e45d | 147 | assert_valid(const char*, int) const; |
4569a895 AT |
148 | #endif |
149 | ||
150 | private: | |
151 | ||
152 | inline void | |
a345e45d | 153 | push_imp(node_pointer); |
4569a895 AT |
154 | |
155 | node_pointer | |
a345e45d | 156 | join_node_children(node_pointer); |
4569a895 AT |
157 | |
158 | node_pointer | |
a345e45d | 159 | forward_join(node_pointer, node_pointer); |
4569a895 AT |
160 | |
161 | node_pointer | |
a345e45d | 162 | back_join(node_pointer, node_pointer); |
4569a895 AT |
163 | |
164 | void | |
a345e45d | 165 | remove_node(node_pointer); |
4569a895 AT |
166 | }; |
167 | ||
a345e45d BK |
168 | #define PB_DS_ASSERT_NODE_CONSISTENT(_Node, _Bool) \ |
169 | _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(_Node, _Bool, \ | |
170 | __FILE__, __LINE__);) | |
f5886803 | 171 | |
4569a895 AT |
172 | #include <ext/pb_ds/detail/pairing_heap_/constructors_destructor_fn_imps.hpp> |
173 | #include <ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp> | |
174 | #include <ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp> | |
175 | #include <ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp> | |
176 | #include <ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp> | |
177 | #include <ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp> | |
178 | ||
f5886803 | 179 | #undef PB_DS_ASSERT_NODE_CONSISTENT |
4569a895 AT |
180 | #undef PB_DS_CLASS_C_DEC |
181 | #undef PB_DS_CLASS_T_DEC | |
a345e45d | 182 | #undef PB_DS_P_HEAP_BASE |
4569a895 AT |
183 | |
184 | } // namespace detail | |
5e11f978 | 185 | } // namespace __gnu_pbds |