tpie::internal_priority_queue< T, comp_t > Class Template Reference

Standard binary internal heap. More...

#include <tpie/internal_priority_queue.h>

Inherits tpie::linear_memory_base< internal_priority_queue< T, std::less< 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 constexpr double	memory_coefficient () noexcept
	Return the memory coefficient of the structure. More...
static constexpr double	memory_overhead () noexcept
	Return the memory overhead of the structure. More...
static constexpr memory_size_type	memory_usage (memory_size_type size) noexcept
	Return the number of bytes required to create a data structure supporting a given number of elements. More...
static constexpr linear_memory_usage	memory_usage () noexcept
static constexpr memory_size_type	memory_fits (memory_size_type memory) noexcept
	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

internal_priority_queue() [1/2]

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.

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

internal_priority_queue() [2/2]

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

clear()

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.

{sz=0;}

empty()

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.

{return sz == 0;}

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().

get_array()

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;
    }

insert()

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.

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

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

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.

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

Referenced by tpie::ami::merge_heap_ptr_op< REC, CMPR >::initialize(), tpie::ami::merge_heap_op< REC, Compare >::initialize(), and tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::insert().

memory_coefficient()

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

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

inlinestaticconstexprnoexcept

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();
    }

Referenced by tpie::ami::merge_heap_ptr_op< REC, CMPR >::space_per_item(), and tpie::ami::merge_heap_op< REC, Compare >::space_per_item().

memory_fits()

static constexpr memory_size_type tpie::linear_memory_base< internal_priority_queue< T, std::less< T > > >::memory_fits ( memory_size_type  memory )

inlinestaticconstexprnoexceptinherited

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 118 of file util.h.

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

memory_overhead()

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

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

inlinestaticconstexprnoexcept

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);
    }

Referenced by tpie::ami::merge_heap_ptr_op< REC, CMPR >::space_overhead(), and tpie::ami::merge_heap_op< REC, Compare >::space_overhead().

memory_usage()

static constexpr memory_size_type tpie::linear_memory_base< internal_priority_queue< T, std::less< T > > >::memory_usage ( memory_size_type  size )

inlinestaticconstexprnoexceptinherited

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 106 of file util.h.

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

pop()

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;
    }

Referenced by tpie::ami::merge_heap_ptr_op< REC, CMPR >::extract_min(), and tpie::ami::merge_heap_op< REC, Compare >::extract_min().

pop_and_push()

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);
    }

push()

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);
    }

resize()

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.

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

Referenced by tpie::ami::merge_heap_ptr_op< REC, CMPR >::allocate(), tpie::ami::merge_heap_op< REC, Compare >::allocate(), tpie::ami::merge_heap_ptr_op< REC, CMPR >::deallocate(), and tpie::ami::merge_heap_op< REC, Compare >::deallocate().

size()

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.

{return sz;}

Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::push(), tpie::ami::merge_heap_ptr_op< REC, CMPR >::sizeofheap(), and tpie::ami::merge_heap_op< REC, Compare >::sizeofheap().

top()

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.

{return pq[0];}

Referenced by tpie::ami::merge_heap_ptr_op< REC, CMPR >::extract_min(), tpie::ami::merge_heap_op< REC, Compare >::extract_min(), tpie::ami::merge_heap_ptr_op< REC, CMPR >::get_min_run_id(), and tpie::ami::merge_heap_op< REC, Compare >::get_min_run_id().

unsafe_push()

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;
    }

Referenced by tpie::ami::merge_heap_ptr_op< REC, CMPR >::insert(), and tpie::ami::merge_heap_op< REC, Compare >::insert().

---

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

• internal_priority_queue.h