__gnu_pbds::detail::resize_policy< _Tp > Class Template Reference

Resize policy for binary heap. More...

#include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp>

Public Types
typedef _Tp	size_type

Public Member Functions
	resize_policy ()
	resize_policy (const resize_policy &other)
void	swap (resize_policy< _Tp > &)
bool	resize_needed_for_grow (size_type) const
bool	resize_needed_for_shrink (size_type) const
bool	grow_needed (size_type) const
bool	shrink_needed (size_type) const
size_type	get_new_size_for_grow () const
size_type	get_new_size_for_shrink () const
size_type	get_new_size_for_arbitrary (size_type) const
void	notify_grow_resize ()
void	notify_shrink_resize ()
void	notify_arbitrary (size_type)

Static Public Attributes
static const _Tp	min_size = 16

Private Types
enum	{ ratio = 8, factor = 2 }

Private Attributes
_Tp	m_shrink_size
	Next shrink size. More...
_Tp	m_grow_size
	Next grow size. More...

Detailed Description

template<typename _Tp>
class __gnu_pbds::detail::resize_policy< _Tp >

Resize policy for binary heap.

Member Typedef Documentation

template<typename _Tp>

typedef _Tp __gnu_pbds::detail::resize_policy< _Tp >::size_type

Member Enumeration Documentation

template<typename _Tp>

anonymous enum

private

Enumerator
ratio
factor

    {
      ratio = 8,
      factor = 2
    };

Constructor & Destructor Documentation

template<typename _Tp>

__gnu_pbds::detail::resize_policy< _Tp >::resize_policy ( )

inline

                      : m_shrink_size(0), m_grow_size(min_size)
      { PB_DS_ASSERT_VALID((*this)) }

template<typename _Tp>

__gnu_pbds::detail::resize_policy< _Tp >::resize_policy ( const resize_policy< _Tp > &  other )

inline

      : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size)
      { PB_DS_ASSERT_VALID((*this)) }

Member Function Documentation

template<typename _Tp >

resize_policy< _Tp >::size_type __gnu_pbds::detail::resize_policy< _Tp >::get_new_size_for_arbitrary ( size_type  size ) const

inline

    {
      size_type ret = min_size;
      while (ret < size)
    ret *= factor;
      return ret;
    }

template<typename _Tp >

resize_policy< _Tp >::size_type __gnu_pbds::detail::resize_policy< _Tp >::get_new_size_for_grow ( ) const

inline

    { return m_grow_size * factor; }

template<typename _Tp >

resize_policy< _Tp >::size_type __gnu_pbds::detail::resize_policy< _Tp >::get_new_size_for_shrink ( ) const

inline

    {
      const size_type half_size = m_grow_size / factor;
      return std::max(min_size, half_size);
    }

template<typename _Tp>

bool __gnu_pbds::detail::resize_policy< _Tp >::grow_needed ( size_type  ) const

inline

template<typename _Tp >

void __gnu_pbds::detail::resize_policy< _Tp >::notify_arbitrary ( size_type  actual_size )

inline

    {
      m_grow_size = actual_size;
      m_shrink_size = m_grow_size / ratio;
      PB_DS_ASSERT_VALID((*this))
    }

template<typename _Tp >

void __gnu_pbds::detail::resize_policy< _Tp >::notify_grow_resize ( )

inline

    {
      PB_DS_ASSERT_VALID((*this))
      _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size);
      m_grow_size *= factor;
      m_shrink_size = m_grow_size / ratio;
      PB_DS_ASSERT_VALID((*this))
    }

template<typename _Tp >

void __gnu_pbds::detail::resize_policy< _Tp >::notify_shrink_resize ( )

inline

    {
      PB_DS_ASSERT_VALID((*this))
      m_shrink_size /= factor;
      if (m_shrink_size == 1)
    m_shrink_size = 0;
      m_grow_size = std::max(m_grow_size / factor, min_size);
      PB_DS_ASSERT_VALID((*this))
    }

template<typename _Tp >

bool __gnu_pbds::detail::resize_policy< _Tp >::resize_needed_for_grow ( size_type  size ) const

inline

    {
      _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
      return size == m_grow_size;
    }

template<typename _Tp >

bool __gnu_pbds::detail::resize_policy< _Tp >::resize_needed_for_shrink ( size_type  size ) const

inline

    {
      _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
      return size == m_shrink_size;
    }

template<typename _Tp>

bool __gnu_pbds::detail::resize_policy< _Tp >::shrink_needed ( size_type  ) const

inline

template<typename _Tp>

void __gnu_pbds::detail::resize_policy< _Tp >::swap ( resize_policy< _Tp > &  other )

inline

    {
      std::swap(m_shrink_size, other.m_shrink_size);
      std::swap(m_grow_size, other.m_grow_size);
    }

Member Data Documentation

template<typename _Tp>

_Tp __gnu_pbds::detail::resize_policy< _Tp >::m_grow_size

private

Next grow size.

template<typename _Tp>

_Tp __gnu_pbds::detail::resize_policy< _Tp >::m_shrink_size

private

Next shrink size.

template<typename _Tp>

const _Tp __gnu_pbds::detail::resize_policy< _Tp >::min_size = 16

static

---

The documentation for this class was generated from the following file:

• GCC4/inc/ext/pb_ds/detail/binary_heap_/resize_policy.hpp