libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2024 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 rebind_traits<_Alloc, node>::pointer node_pointer;
  58
  59
  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;
  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       _GLIBCXX_NODISCARD 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     _GLIBCXX_NODISCARD 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