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

   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.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
  49 #define PB_DS_CLASS_T_DEC \
  50     template<typename Node, class Allocator>
  51
  52 #define PB_DS_CLASS_C_DEC \
  53     rc<Node, Allocator>
  54
  55     template<typename Node, class Allocator>
  56     class rc
  57     {
  58     private:
  59       typedef Allocator allocator_type;
  60
  61       typedef typename allocator_type::size_type size_type;
  62
  63       typedef Node node;
  64
  65       typedef
  66       typename allocator_type::template rebind<
  67         node>::other::pointer
  68       node_pointer;
  69
  70       typedef
  71       typename allocator_type::template rebind<
  72         node_pointer>::other::pointer
  73       entry_pointer;
  74
  75       typedef
  76       typename allocator_type::template rebind<
  77         node_pointer>::other::const_pointer
  78       const_entry_pointer;
  79
  80       enum
  81         {
  82           max_entries = sizeof(size_type) << 3
  83         };
  84
  85     public:
  86       typedef node_pointer entry;
  87
  88       typedef const_entry_pointer const_iterator;
  89
  90     public:
  91       rc();
  92
  93       rc(const PB_DS_CLASS_C_DEC& other);
  94
  95       inline void
  96       swap(PB_DS_CLASS_C_DEC& other);
  97
  98       inline void
  99       push(entry p_nd);
 100
 101       inline node_pointer
 102       top() const;
 103
 104       inline void
 105       pop();
 106
 107       inline bool
 108       empty() const;
 109
 110       inline size_type
 111       size() const;
 112
 113       void
 114       clear();
 115
 116       const const_iterator
 117       begin() const;
 118
 119       const const_iterator
 120       end() const;
 121
 122 #ifdef _GLIBCXX_DEBUG
 123       void
 124       assert_valid(const char* file, int line) const;
 125 #endif
 126
 127 #ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
 128       void
 129       trace() const;
 130 #endif
 131
 132     private:
 133       node_pointer m_a_entries[max_entries];
 134
 135       size_type m_over_top;
 136     };
 137
 138     PB_DS_CLASS_T_DEC
 139     PB_DS_CLASS_C_DEC::
 140     rc() : m_over_top(0)
 141     { PB_DS_ASSERT_VALID((*this)) }
 142
 143     PB_DS_CLASS_T_DEC
 144     PB_DS_CLASS_C_DEC::
 145     rc(const PB_DS_CLASS_C_DEC& other) : m_over_top(0)
 146     { PB_DS_ASSERT_VALID((*this)) }
 147
 148     PB_DS_CLASS_T_DEC
 149     inline void
 150     PB_DS_CLASS_C_DEC::
 151     swap(PB_DS_CLASS_C_DEC& other)
 152     {
 153       PB_DS_ASSERT_VALID((*this))
 154       PB_DS_ASSERT_VALID(other)
 155
 156       const size_type over_top = std::max(m_over_top, other.m_over_top);
 157
 158       for (size_type i = 0; i < over_top; ++i)
 159         std::swap(m_a_entries[i], other.m_a_entries[i]);
 160
 161       std::swap(m_over_top, other.m_over_top);
 162       PB_DS_ASSERT_VALID((*this))
 163       PB_DS_ASSERT_VALID(other)
 164      }
 165
 166     PB_DS_CLASS_T_DEC
 167     inline void
 168     PB_DS_CLASS_C_DEC::
 169     push(entry p_nd)
 170     {
 171       PB_DS_ASSERT_VALID((*this))
 172       _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries);
 173       m_a_entries[m_over_top++] = p_nd;
 174       PB_DS_ASSERT_VALID((*this))
 175     }
 176
 177     PB_DS_CLASS_T_DEC
 178     inline void
 179     PB_DS_CLASS_C_DEC::
 180     pop()
 181     {
 182       PB_DS_ASSERT_VALID((*this))
 183       _GLIBCXX_DEBUG_ASSERT(!empty());
 184       --m_over_top;
 185       PB_DS_ASSERT_VALID((*this))
 186     }
 187
 188     PB_DS_CLASS_T_DEC
 189     inline typename PB_DS_CLASS_C_DEC::node_pointer
 190     PB_DS_CLASS_C_DEC::
 191     top() const
 192     {
 193       PB_DS_ASSERT_VALID((*this))
 194       _GLIBCXX_DEBUG_ASSERT(!empty());
 195       return *(m_a_entries + m_over_top - 1);
 196     }
 197
 198     PB_DS_CLASS_T_DEC
 199     inline bool
 200     PB_DS_CLASS_C_DEC::
 201     empty() const
 202     {
 203       PB_DS_ASSERT_VALID((*this))
 204       return m_over_top == 0;
 205     }
 206
 207     PB_DS_CLASS_T_DEC
 208     inline typename PB_DS_CLASS_C_DEC::size_type
 209     PB_DS_CLASS_C_DEC::
 210     size() const
 211     { return m_over_top; }
 212
 213     PB_DS_CLASS_T_DEC
 214     void
 215     PB_DS_CLASS_C_DEC::
 216     clear()
 217     {
 218       PB_DS_ASSERT_VALID((*this))
 219       m_over_top = 0;
 220       PB_DS_ASSERT_VALID((*this))
 221     }
 222
 223     PB_DS_CLASS_T_DEC
 224     const typename PB_DS_CLASS_C_DEC::const_iterator
 225     PB_DS_CLASS_C_DEC::
 226     begin() const
 227     { return& m_a_entries[0]; }
 228
 229     PB_DS_CLASS_T_DEC
 230     const typename PB_DS_CLASS_C_DEC::const_iterator
 231     PB_DS_CLASS_C_DEC::
 232     end() const
 233     { return& m_a_entries[m_over_top]; }
 234
 235 #ifdef _GLIBCXX_DEBUG
 236     PB_DS_CLASS_T_DEC
 237     void
 238     PB_DS_CLASS_C_DEC::
 239     assert_valid(const char* __file, int __line) const
 240     { PB_DS_DEBUG_VERIFY(m_over_top < max_entries); }
 241 #endif
 242
 243 #ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
 244     PB_DS_CLASS_T_DEC
 245     void
 246     PB_DS_CLASS_C_DEC::
 247     trace() const
 248     {
 249       std::cout << "rc" << std::endl;
 250       for (size_type i = 0; i < m_over_top; ++i)
 251         std::cerr << m_a_entries[i] << std::endl;
 252       std::cout << std::endl;
 253     }
 254 #endif
 255
 256 #undef PB_DS_CLASS_T_DEC
 257 #undef PB_DS_CLASS_C_DEC
 258
 259 } // namespace detail
 260 } // namespace __gnu_pbds
 261
 262 #endif