Standard binary internal heap. More...

#include <tpie/internal_priority_queue.h>

Inherits tpie::linear_memory_base< internal_priority_queue< T, comp_t > >.

Public Types
typedef memory_size_type	size_type

Public Member Functions
	internal_priority_queue (size_type max_size, comp_t c=comp_t(), memory_bucket_ref bucket=memory_bucket_ref())
	Construct a priority queue. More...

template<typename IT >
	internal_priority_queue (size_type max_size, const IT &start, const IT &end, comp_t c=comp_t(), memory_bucket_ref bucket=memory_bucket_ref())
	Construct a priority queue with given elements. More...

template<typename IT >
void	insert (const IT &start, const IT &end)
	Insert some elements and run make_heap. More...

void	unsafe_push (const T &v)
	Insert an element into the priority queue, possibly destroying ordering information. More...

void	unsafe_push (T &&v)

void	make_safe ()
	Make the priority queue safe after a sequence of calls to unsafe_push. More...

bool	empty () const
	Is the queue empty? More...

size_type	size () const
	Returns the size of the queue. More...

void	push (const T &v)
	Insert an element into the priority queue. More...

void	push (T &&v)

void	pop ()
	Remove the minimum element from heap. More...

void	pop_and_push (const T &v)
	Remove the minimum element and insert a new element. More...

void	pop_and_push (T &&v)

const T &	top () const
	Return the minimum element. More...

T &	top ()

tpie::array< T > &	get_array ()
	Return the underlying array. More...

void	clear ()
	Clear the structure of all elements. More...

void	resize (size_t s)
	Resize priority queue to given size. More...

Static Public Member Functions
static double	memory_coefficient ()
	Return the memory coefficient of the structure. More...

static double	memory_overhead ()
	Return the memory overhead of the structure. More...

static memory_size_type	memory_usage (memory_size_type size)
	Return the number of bytes required to create a data structure supporting a given number of elements. More...

static memory_size_type	memory_fits (memory_size_type memory)
	Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes. More...

Detailed Description

template<typename T, typename comp_t = std::less<T>>
class tpie::internal_priority_queue< T, comp_t >

Standard binary internal heap.

Author: Lars Hvam Petersen, Jakob Truelsen

Definition at line 37 of file internal_priority_queue.h.

Constructor & Destructor Documentation

template<typename T, typename comp_t = std::less<T>>

tpie::internal_priority_queue< T, comp_t >::internal_priority_queue	(	size_type	max_size,
		comp_t	c = `comp_t()`,
		memory_bucket_ref	bucket = `memory_bucket_ref()`
	)

inline

Construct a priority queue.

Parameters

max_size Maximum size of queue.

Definition at line 45 of file internal_priority_queue.h.

47 : pq(max_size, bucket), sz(0), comp(c) {}

template<typename T, typename comp_t = std::less<T>>

template<typename IT >

tpie::internal_priority_queue< T, comp_t >::internal_priority_queue	(	size_type	max_size,
		const IT &	start,
		const IT &	end,
		comp_t	c = `comp_t()`,
		memory_bucket_ref	bucket = `memory_bucket_ref()`
	)

inline

Construct a priority queue with given elements.

Definition at line 53 of file internal_priority_queue.h.

         : pq(max_size, bucket), sz(0), comp(c) {
         insert(start, end);
     }

Member Function Documentation

template<typename T, typename comp_t = std::less<T>>

void tpie::internal_priority_queue< T, comp_t >::clear ( )

inline

Clear the structure of all elements.

Definition at line 182 of file internal_priority_queue.h.

182 {sz=0;}

template<typename T, typename comp_t = std::less<T>>

bool tpie::internal_priority_queue< T, comp_t >::empty ( ) const

inline

Is the queue empty?

Returns: True if the queue is empty.

Definition at line 96 of file internal_priority_queue.h.

Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::pop(), and tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::pop_and_push().

96 {return sz == 0;}

template<typename T, typename comp_t = std::less<T>>

tpie::array<T>& tpie::internal_priority_queue< T, comp_t >::get_array ( )

inline

Return the underlying array.

Make sure you know what you are doing.

Returns: The underlying array.

Definition at line 175 of file internal_priority_queue.h.

                                {
         return pq;
     }

template<typename T, typename comp_t = std::less<T>>

template<typename IT >

void tpie::internal_priority_queue< T, comp_t >::insert	(	const IT &	start,
		const IT &	end
	)

inline

Insert some elements and run make_heap.

Definition at line 64 of file internal_priority_queue.h.

Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::internal_priority_queue().

                                                   {
         std::copy(start, end, pq.find(sz));
         sz += (end - start);
         make_safe();
     }

template<typename T, typename comp_t = std::less<T>>

void tpie::internal_priority_queue< T, comp_t >::make_safe ( )

inline

Make the priority queue safe after a sequence of calls to unsafe_push.

Definition at line 88 of file internal_priority_queue.h.

Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::insert().

                      {
         std::make_heap(pq.begin(), pq.find(sz), comp);
     }

template<typename T, typename comp_t = std::less<T>>

static double tpie::internal_priority_queue< T, comp_t >::memory_coefficient ( )

inlinestatic

Return the memory coefficient of the structure.

Allocating a structure with n elements will use at most $\lfloor \mathrm{memory\_coefficient} \cdot n + \mathrm{memory\_overhead} \rfloor$ bytes. This does not include memory overhead incurred if the structure is allocated using new.

Returns: The memory coefficient of the structure.

Definition at line 158 of file internal_priority_queue.h.

                                        {
         return tpie::array<T>::memory_coefficient();
     }

static memory_size_type tpie::linear_memory_base< internal_priority_queue< T, comp_t > >::memory_fits ( memory_size_type memory )

inlinestaticinherited

Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes.

Parameters

memory The number of bytes the structure is allowed to occupy

Returns: The number of elements that will fit in the structure

Definition at line 93 of file util.h.

                                                                         {
         return static_cast<memory_size_type>(
             floor((memory - child_t::memory_overhead()) / child_t::memory_coefficient()));
     }

template<typename T, typename comp_t = std::less<T>>

static double tpie::internal_priority_queue< T, comp_t >::memory_overhead ( )

inlinestatic

Return the memory overhead of the structure.

See also: memory_coefficient()

Returns: The memory overhead.

Definition at line 166 of file internal_priority_queue.h.

                                     {
         return tpie::array<T>::memory_overhead() - sizeof(tpie::array<T>) + sizeof(internal_priority_queue);
     }

static memory_size_type tpie::linear_memory_base< internal_priority_queue< T, comp_t > >::memory_usage ( memory_size_type size )

inlinestaticinherited

Return the number of bytes required to create a data structure supporting a given number of elements.

Parameters

size	The number of elements to support

Returns: The amount of memory required in bytes

Definition at line 81 of file util.h.

                                                                 {
         return static_cast<memory_size_type>(
             floor(static_cast<double>(size) * child_t::memory_coefficient() + child_t::memory_overhead()));
     }

template<typename T, typename comp_t = std::less<T>>

void tpie::internal_priority_queue< T, comp_t >::pop ( )

inline

Remove the minimum element from heap.

Definition at line 124 of file internal_priority_queue.h.

                { 
         assert(!empty());
         std::pop_heap(pq.begin(), pq.find(sz), comp);
         --sz;
     }

template<typename T, typename comp_t = std::less<T>>

void tpie::internal_priority_queue< T, comp_t >::pop_and_push ( const T & v )

inline

Remove the minimum element and insert a new element.

Definition at line 133 of file internal_priority_queue.h.

                                    {
         assert(!empty());
         pq[0] = v;
         pop_and_push_heap(pq.begin(), pq.find(sz), comp);
     }

template<typename T, typename comp_t = std::less<T>>

void tpie::internal_priority_queue< T, comp_t >::push ( const T & v )

inline

Insert an element into the priority queue.

Parameters

v	The element that should be inserted.

Definition at line 109 of file internal_priority_queue.h.

                            { 
         assert(size() < pq.size());
         pq[sz++] = v; 
         std::push_heap(pq.begin(), pq.find(sz), comp);
     }

template<typename T, typename comp_t = std::less<T>>

void tpie::internal_priority_queue< T, comp_t >::resize ( size_t s )

inline

Resize priority queue to given size.

Parameters

s	New size of priority queue.

Definition at line 188 of file internal_priority_queue.h.

188 {sz=0; pq.resize(s);}

tpie::array::resize

void resize(size_t size, const T &elm)

Change the size of the array.

Definition: array.h:485

template<typename T, typename comp_t = std::less<T>>

size_type tpie::internal_priority_queue< T, comp_t >::size ( ) const

inline

Returns the size of the queue.

Returns: Queue size.

Definition at line 102 of file internal_priority_queue.h.

Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::push().

102 {return sz;}

template<typename T, typename comp_t = std::less<T>>

const T& tpie::internal_priority_queue< T, comp_t >::top ( ) const

inline

Return the minimum element.

Returns: The minimum element.

Definition at line 150 of file internal_priority_queue.h.

150 {return pq[0];}

template<typename T, typename comp_t = std::less<T>>

void tpie::internal_priority_queue< T, comp_t >::unsafe_push ( const T & v )

inline

Insert an element into the priority queue, possibly destroying ordering information.

Parameters

v	The element that should be inserted.

Definition at line 76 of file internal_priority_queue.h.

                                   { 
         pq[sz++] = v;
     }

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

internal_priority_queue.h

TPIE

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

template<typename T, typename comp_t = std::less<T>> class tpie::internal_priority_queue< T, comp_t >

Constructor & Destructor Documentation

Member Function Documentation

template<typename T, typename comp_t = std::less<T>>
class tpie::internal_priority_queue< T, comp_t >