Home | History | Annotate | Download | only in rc_binomial_heap_ 
      1 // -*- C++ -*-
      2 
      3 // Copyright (C) 2005, 2006, 2009 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;
    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     { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
    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     { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
    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       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    154       _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
    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       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    163       _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
    164      }
    165 
    166     PB_DS_CLASS_T_DEC
    167     inline void
    168     PB_DS_CLASS_C_DEC::
    169     push(entry p_nd)
    170     {
    171       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    172       _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries);
    173       m_a_entries[m_over_top++] = p_nd;
    174       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    175     }
    176 
    177     PB_DS_CLASS_T_DEC
    178     inline void
    179     PB_DS_CLASS_C_DEC::
    180     pop()
    181     {
    182       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    183       _GLIBCXX_DEBUG_ASSERT(!empty());
    184       --m_over_top;
    185       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    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       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    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       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    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       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    219       m_over_top = 0;
    220       _GLIBCXX_DEBUG_ONLY(assert_valid();)
    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
    240     { _GLIBCXX_DEBUG_ASSERT(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
    263