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