libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.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 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