contrib/libstdc++/include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file rc.hpp
  44  * Contains a redundant (binary counter).
  45  */
  46
  47 #ifndef PB_DS_RC_HPP
  48 #define PB_DS_RC_HPP
  49
  50 namespace pb_ds
  51 {
  52   namespace detail
  53   {
  54
  55 #define PB_DS_CLASS_T_DEC \
  56     template<typename Node, class Allocator>
  57
  58 #define PB_DS_CLASS_C_DEC \
  59     rc<Node, Allocator>
  60
  61     template<typename Node, class Allocator>
  62     class rc
  63     {
  64     private:
  65       typedef Allocator allocator;
  66
  67       typedef typename allocator::size_type size_type;
  68
  69       typedef Node node;
  70
  71       typedef
  72       typename allocator::template rebind<
  73         node>::other::pointer
  74       node_pointer;
  75
  76       typedef
  77       typename allocator::template rebind<
  78         node_pointer>::other::pointer
  79       entry_pointer;
  80
  81       typedef
  82       typename allocator::template rebind<
  83         node_pointer>::other::const_pointer
  84       const_entry_pointer;
  85
  86       enum
  87         {
  88           max_entries = sizeof(size_type) << 3
  89         };
  90
  91     public:
  92       typedef node_pointer entry;
  93
  94       typedef const_entry_pointer const_iterator;
  95
  96     public:
  97       rc();
  98
  99       rc(const PB_DS_CLASS_C_DEC& other);
 100
 101       inline void
 102       swap(PB_DS_CLASS_C_DEC& other);
 103
 104       inline void
 105       push(entry p_nd);
 106
 107       inline node_pointer
 108       top() const;
 109
 110       inline void
 111       pop();
 112
 113       inline bool
 114       empty() const;
 115
 116       inline size_type
 117       size() const;
 118
 119       void
 120       clear();
 121
 122       const const_iterator
 123       begin() const;
 124
 125       const const_iterator
 126       end() const;
 127
 128 #ifdef _GLIBCXX_DEBUG
 129       void
 130       assert_valid() const;
 131 #endif
 132
 133 #ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
 134       void
 135       trace() const;
 136 #endif
 137
 138     private:
 139       node_pointer m_a_entries[max_entries];
 140
 141       size_type m_over_top;
 142     };
 143
 144     PB_DS_CLASS_T_DEC
 145     PB_DS_CLASS_C_DEC::
 146     rc() : m_over_top(0)
 147     { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
 148
 149     PB_DS_CLASS_T_DEC
 150     PB_DS_CLASS_C_DEC::
 151     rc(const PB_DS_CLASS_C_DEC& other) : m_over_top(0)
 152     { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
 153
 154     PB_DS_CLASS_T_DEC
 155     inline void
 156     PB_DS_CLASS_C_DEC::
 157     swap(PB_DS_CLASS_C_DEC& other)
 158     {
 159       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 160       _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
 161
 162       const size_type over_top = std::max(m_over_top, other.m_over_top);
 163
 164       for (size_type i = 0; i < over_top; ++i)
 165         std::swap(m_a_entries[i], other.m_a_entries[i]);
 166
 167       std::swap(m_over_top, other.m_over_top);
 168       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 169       _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
 170      }
 171
 172     PB_DS_CLASS_T_DEC
 173     inline void
 174     PB_DS_CLASS_C_DEC::
 175     push(entry p_nd)
 176     {
 177       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 178       _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries);
 179       m_a_entries[m_over_top++] = p_nd;
 180       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 181     }
 182
 183     PB_DS_CLASS_T_DEC
 184     inline void
 185     PB_DS_CLASS_C_DEC::
 186     pop()
 187     {
 188       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 189       _GLIBCXX_DEBUG_ASSERT(!empty());
 190       --m_over_top;
 191       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 192     }
 193
 194     PB_DS_CLASS_T_DEC
 195     inline typename PB_DS_CLASS_C_DEC::node_pointer
 196     PB_DS_CLASS_C_DEC::
 197     top() const
 198     {
 199       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 200       _GLIBCXX_DEBUG_ASSERT(!empty());
 201       return *(m_a_entries + m_over_top - 1);
 202     }
 203
 204     PB_DS_CLASS_T_DEC
 205     inline bool
 206     PB_DS_CLASS_C_DEC::
 207     empty() const
 208     {
 209       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 210       return m_over_top == 0;
 211     }
 212
 213     PB_DS_CLASS_T_DEC
 214     inline typename PB_DS_CLASS_C_DEC::size_type
 215     PB_DS_CLASS_C_DEC::
 216     size() const
 217     { return m_over_top; }
 218
 219     PB_DS_CLASS_T_DEC
 220     void
 221     PB_DS_CLASS_C_DEC::
 222     clear()
 223     {
 224       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 225       m_over_top = 0;
 226       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 227     }
 228
 229     PB_DS_CLASS_T_DEC
 230     const typename PB_DS_CLASS_C_DEC::const_iterator
 231     PB_DS_CLASS_C_DEC::
 232     begin() const
 233     { return& m_a_entries[0]; }
 234
 235     PB_DS_CLASS_T_DEC
 236     const typename PB_DS_CLASS_C_DEC::const_iterator
 237     PB_DS_CLASS_C_DEC::
 238     end() const
 239     { return& m_a_entries[m_over_top]; }
 240
 241 #ifdef _GLIBCXX_DEBUG
 242     PB_DS_CLASS_T_DEC
 243     void
 244     PB_DS_CLASS_C_DEC::
 245     assert_valid() const
 246     { _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries); }
 247 #endif
 248
 249 #ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
 250     PB_DS_CLASS_T_DEC
 251     void
 252     PB_DS_CLASS_C_DEC::
 253     trace() const
 254     {
 255       std::cout << "rc" << std::endl;
 256       for (size_type i = 0; i < m_over_top; ++i)
 257         std::cerr << m_a_entries[i] << std::endl;
 258       std::cout << std::endl;
 259     }
 260 #endif
 261
 262 #undef PB_DS_CLASS_T_DEC
 263 #undef PB_DS_CLASS_C_DEC
 264
 265 } // namespace detail
 266 } // namespace pb_ds
 267
 268 #endif