Home | History | Annotate | Download | only in binary_heap_ 
      1 // -*- C++ -*-
      2 
      3 // Copyright (C) 2005-2013 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 binary_heap_/resize_policy.hpp
     38  * Contains an implementation class for a binary_heap.
     39  */
     40 
     41 #ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
     42 #define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
     43 
     44 #include <debug/debug.h>
     45 
     46 namespace __gnu_pbds
     47 {
     48   namespace detail
     49   {
     50     /// Resize policy for binary heap.
     51     template<typename _Tp>
     52     class resize_policy
     53     {
     54     private:
     55       enum
     56 	{
     57 	  ratio = 8,
     58 	  factor = 2
     59 	};
     60 
     61       /// Next shrink size.
     62       _Tp 		m_shrink_size;
     63 
     64       /// Next grow size.
     65       _Tp 		m_grow_size;
     66 
     67     public:
     68       typedef _Tp	size_type;
     69 
     70       static const _Tp	min_size = 16;
     71 
     72       resize_policy() : m_shrink_size(0), m_grow_size(min_size)
     73       { PB_DS_ASSERT_VALID((*this)) }
     74 
     75       resize_policy(const resize_policy& other)
     76       : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size)
     77       { PB_DS_ASSERT_VALID((*this)) }
     78 
     79       inline void
     80       swap(resize_policy<_Tp>&);
     81 
     82       inline bool
     83       resize_needed_for_grow(size_type) const;
     84 
     85       inline bool
     86       resize_needed_for_shrink(size_type) const;
     87 
     88       inline bool
     89       grow_needed(size_type) const;
     90 
     91       inline bool
     92       shrink_needed(size_type) const;
     93 
     94       inline size_type
     95       get_new_size_for_grow() const;
     96 
     97       inline size_type
     98       get_new_size_for_shrink() const;
     99 
    100       inline size_type
    101       get_new_size_for_arbitrary(size_type) const;
    102 
    103       inline void
    104       notify_grow_resize();
    105 
    106       inline void
    107       notify_shrink_resize();
    108 
    109       void
    110       notify_arbitrary(size_type);
    111 
    112 #ifdef _GLIBCXX_DEBUG
    113       void
    114       assert_valid(const char*, int) const;
    115 #endif
    116 
    117 #ifdef PB_DS_BINARY_HEAP_TRACE_
    118       void
    119       trace() const;
    120 #endif
    121     };
    122 
    123     template<typename _Tp>
    124       const _Tp resize_policy<_Tp>::min_size;
    125 
    126     template<typename _Tp>
    127     inline void
    128     resize_policy<_Tp>::
    129     swap(resize_policy<_Tp>& other)
    130     {
    131       std::swap(m_shrink_size, other.m_shrink_size);
    132       std::swap(m_grow_size, other.m_grow_size);
    133     }
    134 
    135     template<typename _Tp>
    136     inline bool
    137     resize_policy<_Tp>::
    138     resize_needed_for_grow(size_type size) const
    139     {
    140       _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
    141       return size == m_grow_size;
    142     }
    143 
    144     template<typename _Tp>
    145     inline bool
    146     resize_policy<_Tp>::
    147     resize_needed_for_shrink(size_type size) const
    148     {
    149       _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
    150       return size == m_shrink_size;
    151     }
    152 
    153     template<typename _Tp>
    154     inline typename resize_policy<_Tp>::size_type
    155     resize_policy<_Tp>::
    156     get_new_size_for_grow() const
    157     { return m_grow_size * factor; }
    158 
    159     template<typename _Tp>
    160     inline typename resize_policy<_Tp>::size_type
    161     resize_policy<_Tp>::
    162     get_new_size_for_shrink() const
    163     {
    164       const size_type half_size = m_grow_size / factor;
    165       return std::max(min_size, half_size);
    166     }
    167 
    168     template<typename _Tp>
    169     inline typename resize_policy<_Tp>::size_type
    170     resize_policy<_Tp>::
    171     get_new_size_for_arbitrary(size_type size) const
    172     {
    173       size_type ret = min_size;
    174       while (ret < size)
    175 	ret *= factor;
    176       return ret;
    177     }
    178 
    179     template<typename _Tp>
    180     inline void
    181     resize_policy<_Tp>::
    182     notify_grow_resize()
    183     {
    184       PB_DS_ASSERT_VALID((*this))
    185       _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size);
    186       m_grow_size *= factor;
    187       m_shrink_size = m_grow_size / ratio;
    188       PB_DS_ASSERT_VALID((*this))
    189     }
    190 
    191     template<typename _Tp>
    192     inline void
    193     resize_policy<_Tp>::
    194     notify_shrink_resize()
    195     {
    196       PB_DS_ASSERT_VALID((*this))
    197       m_shrink_size /= factor;
    198       if (m_shrink_size == 1)
    199 	m_shrink_size = 0;
    200       m_grow_size = std::max(m_grow_size / factor, min_size);
    201       PB_DS_ASSERT_VALID((*this))
    202     }
    203 
    204     template<typename _Tp>
    205     inline void
    206     resize_policy<_Tp>::
    207     notify_arbitrary(size_type actual_size)
    208     {
    209       m_grow_size = actual_size;
    210       m_shrink_size = m_grow_size / ratio;
    211       PB_DS_ASSERT_VALID((*this))
    212     }
    213 
    214 #ifdef _GLIBCXX_DEBUG
    215     template<typename _Tp>
    216     void
    217     resize_policy<_Tp>::
    218     assert_valid(const char* __file, int __line) const
    219     {
    220       PB_DS_DEBUG_VERIFY(m_shrink_size == 0
    221 			 || m_shrink_size * ratio == m_grow_size);
    222       PB_DS_DEBUG_VERIFY(m_grow_size >= min_size);
    223     }
    224 #endif
    225 
    226 #ifdef PB_DS_BINARY_HEAP_TRACE_
    227     template<typename _Tp>
    228     void
    229     resize_policy<_Tp>::
    230     trace() const
    231     {
    232       std::cerr << "shrink = " << m_shrink_size
    233 		<< " grow = " << m_grow_size << std::endl;
    234     }
    235 #endif
    236 
    237 } // namespace detail
    238 } // namespace __gnu_pbds
    239 
    240 #endif
    241