]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
99dee823 | 3 | // Copyright (C) 2005-2021 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 rc_binomial_heap_/rc.hpp |
4569a895 AT |
38 | * Contains a redundant (binary counter). |
39 | */ | |
40 | ||
41 | #ifndef PB_DS_RC_HPP | |
42 | #define PB_DS_RC_HPP | |
43 | ||
5e11f978 | 44 | namespace __gnu_pbds |
4569a895 AT |
45 | { |
46 | namespace detail | |
47 | { | |
a345e45d BK |
48 | /// Redundant binary counter. |
49 | template<typename _Node, typename _Alloc> | |
4569a895 AT |
50 | class rc |
51 | { | |
52 | private: | |
a345e45d BK |
53 | typedef _Alloc allocator_type; |
54 | typedef typename allocator_type::size_type size_type; | |
55 | typedef _Node node; | |
4569a895 | 56 | |
ec541f1b | 57 | typedef typename rebind_traits<_Alloc, node>::pointer node_pointer; |
4569a895 | 58 | |
4569a895 | 59 | |
ec541f1b JW |
60 | typedef typename rebind_traits<_Alloc, node_pointer>::pointer |
61 | entry_pointer; | |
62 | typedef typename rebind_traits<_Alloc, node_pointer>::const_pointer | |
63 | entry_const_pointer; | |
4569a895 AT |
64 | |
65 | enum | |
66 | { | |
67 | max_entries = sizeof(size_type) << 3 | |
68 | }; | |
69 | ||
70 | public: | |
a345e45d BK |
71 | typedef node_pointer entry; |
72 | typedef entry_const_pointer const_iterator; | |
4569a895 | 73 | |
4569a895 AT |
74 | rc(); |
75 | ||
a345e45d | 76 | rc(const rc&); |
4569a895 AT |
77 | |
78 | inline void | |
a345e45d | 79 | swap(rc&); |
4569a895 AT |
80 | |
81 | inline void | |
a345e45d | 82 | push(entry); |
4569a895 AT |
83 | |
84 | inline node_pointer | |
85 | top() const; | |
86 | ||
87 | inline void | |
88 | pop(); | |
89 | ||
d715f554 | 90 | _GLIBCXX_NODISCARD inline bool |
4569a895 AT |
91 | empty() const; |
92 | ||
93 | inline size_type | |
94 | size() const; | |
95 | ||
96 | void | |
97 | clear(); | |
98 | ||
99 | const const_iterator | |
100 | begin() const; | |
101 | ||
102 | const const_iterator | |
103 | end() const; | |
104 | ||
47bea7b8 | 105 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 106 | void |
a345e45d BK |
107 | assert_valid(const char*, int) const; |
108 | #endif | |
4569a895 AT |
109 | |
110 | #ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_ | |
4569a895 AT |
111 | void |
112 | trace() const; | |
a345e45d | 113 | #endif |
4569a895 AT |
114 | |
115 | private: | |
a345e45d BK |
116 | node_pointer m_a_entries[max_entries]; |
117 | size_type m_over_top; | |
4569a895 AT |
118 | }; |
119 | ||
a345e45d BK |
120 | template<typename _Node, typename _Alloc> |
121 | rc<_Node, _Alloc>:: | |
47bea7b8 | 122 | rc() : m_over_top(0) |
f5886803 | 123 | { PB_DS_ASSERT_VALID((*this)) } |
4569a895 | 124 | |
a345e45d BK |
125 | template<typename _Node, typename _Alloc> |
126 | rc<_Node, _Alloc>:: | |
127 | rc(const rc<_Node, _Alloc>& other) : m_over_top(0) | |
f5886803 | 128 | { PB_DS_ASSERT_VALID((*this)) } |
4569a895 | 129 | |
a345e45d | 130 | template<typename _Node, typename _Alloc> |
4569a895 | 131 | inline void |
a345e45d BK |
132 | rc<_Node, _Alloc>:: |
133 | swap(rc<_Node, _Alloc>& other) | |
4569a895 | 134 | { |
f5886803 FD |
135 | PB_DS_ASSERT_VALID((*this)) |
136 | PB_DS_ASSERT_VALID(other) | |
4569a895 | 137 | |
47bea7b8 | 138 | const size_type over_top = std::max(m_over_top, other.m_over_top); |
4569a895 AT |
139 | |
140 | for (size_type i = 0; i < over_top; ++i) | |
141 | std::swap(m_a_entries[i], other.m_a_entries[i]); | |
142 | ||
143 | std::swap(m_over_top, other.m_over_top); | |
f5886803 FD |
144 | PB_DS_ASSERT_VALID((*this)) |
145 | PB_DS_ASSERT_VALID(other) | |
47bea7b8 | 146 | } |
4569a895 | 147 | |
a345e45d | 148 | template<typename _Node, typename _Alloc> |
4569a895 | 149 | inline void |
a345e45d | 150 | rc<_Node, _Alloc>:: |
4569a895 AT |
151 | push(entry p_nd) |
152 | { | |
f5886803 | 153 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 154 | _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries); |
4569a895 | 155 | m_a_entries[m_over_top++] = p_nd; |
f5886803 | 156 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 157 | } |
4569a895 | 158 | |
a345e45d | 159 | template<typename _Node, typename _Alloc> |
4569a895 | 160 | inline void |
a345e45d | 161 | rc<_Node, _Alloc>:: |
4569a895 AT |
162 | pop() |
163 | { | |
f5886803 | 164 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 165 | _GLIBCXX_DEBUG_ASSERT(!empty()); |
4569a895 | 166 | --m_over_top; |
f5886803 | 167 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 168 | } |
4569a895 | 169 | |
a345e45d BK |
170 | template<typename _Node, typename _Alloc> |
171 | inline typename rc<_Node, _Alloc>::node_pointer | |
172 | rc<_Node, _Alloc>:: | |
4569a895 AT |
173 | top() const |
174 | { | |
f5886803 | 175 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 BK |
176 | _GLIBCXX_DEBUG_ASSERT(!empty()); |
177 | return *(m_a_entries + m_over_top - 1); | |
4569a895 AT |
178 | } |
179 | ||
a345e45d | 180 | template<typename _Node, typename _Alloc> |
d715f554 | 181 | _GLIBCXX_NODISCARD inline bool |
a345e45d | 182 | rc<_Node, _Alloc>:: |
4569a895 AT |
183 | empty() const |
184 | { | |
f5886803 | 185 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 186 | return m_over_top == 0; |
4569a895 AT |
187 | } |
188 | ||
a345e45d BK |
189 | template<typename _Node, typename _Alloc> |
190 | inline typename rc<_Node, _Alloc>::size_type | |
191 | rc<_Node, _Alloc>:: | |
4569a895 | 192 | size() const |
47bea7b8 | 193 | { return m_over_top; } |
4569a895 | 194 | |
a345e45d | 195 | template<typename _Node, typename _Alloc> |
4569a895 | 196 | void |
a345e45d | 197 | rc<_Node, _Alloc>:: |
4569a895 AT |
198 | clear() |
199 | { | |
f5886803 | 200 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 201 | m_over_top = 0; |
f5886803 | 202 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 203 | } |
4569a895 | 204 | |
a345e45d BK |
205 | template<typename _Node, typename _Alloc> |
206 | const typename rc<_Node, _Alloc>::const_iterator | |
207 | rc<_Node, _Alloc>:: | |
4569a895 | 208 | begin() const |
47bea7b8 | 209 | { return& m_a_entries[0]; } |
4569a895 | 210 | |
a345e45d BK |
211 | template<typename _Node, typename _Alloc> |
212 | const typename rc<_Node, _Alloc>::const_iterator | |
213 | rc<_Node, _Alloc>:: | |
4569a895 | 214 | end() const |
47bea7b8 | 215 | { return& m_a_entries[m_over_top]; } |
4569a895 | 216 | |
47bea7b8 | 217 | #ifdef _GLIBCXX_DEBUG |
a345e45d | 218 | template<typename _Node, typename _Alloc> |
4569a895 | 219 | void |
a345e45d | 220 | rc<_Node, _Alloc>:: |
f5886803 FD |
221 | assert_valid(const char* __file, int __line) const |
222 | { PB_DS_DEBUG_VERIFY(m_over_top < max_entries); } | |
a345e45d | 223 | #endif |
4569a895 AT |
224 | |
225 | #ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_ | |
a345e45d | 226 | template<typename _Node, typename _Alloc> |
4569a895 | 227 | void |
a345e45d | 228 | rc<_Node, _Alloc>:: |
4569a895 AT |
229 | trace() const |
230 | { | |
231 | std::cout << "rc" << std::endl; | |
4569a895 AT |
232 | for (size_type i = 0; i < m_over_top; ++i) |
233 | std::cerr << m_a_entries[i] << std::endl; | |
4569a895 AT |
234 | std::cout << std::endl; |
235 | } | |
a345e45d | 236 | #endif |
47bea7b8 | 237 | } // namespace detail |
5e11f978 | 238 | } // namespace __gnu_pbds |
4569a895 | 239 | |
a345e45d | 240 | #endif |