libstdc++
rc.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009, 2011 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 
44 namespace __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>
122  rc() : m_over_top(0)
123  { PB_DS_ASSERT_VALID((*this)) }
124 
125  template<typename _Node, typename _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
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
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
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
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
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
192  size() const
193  { return m_over_top; }
194 
195  template<typename _Node, typename _Alloc>
196  void
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
208  begin() const
209  { return& m_a_entries[0]; }
210 
211  template<typename _Node, typename _Alloc>
212  const typename rc<_Node, _Alloc>::const_iterator
214  end() const
215  { return& m_a_entries[m_over_top]; }
216 
217 #ifdef _GLIBCXX_DEBUG
218  template<typename _Node, typename _Alloc>
219  void
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
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