TPIE

v1.1rc1-6-g0c97303
Public Types | Public Member Functions | Static Public Member Functions | List of all members
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, 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())
 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())
 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 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 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...
 
const T & top () const
 Return the minimum element. More...
 
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 stream_size_type memory_usage (stream_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() 
)
inline

Construct a priority queue.

Parameters
max_sizeMaximum size of queue.

Definition at line 45 of file internal_priority_queue.h.

45 : pq(max_size), 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() 
)
inline

Construct a priority queue with given elements.

Definition at line 51 of file internal_priority_queue.h.

52  : pq(max_size), sz(0), comp(c) {
53  insert(start, end);
54  }
tpie::internal_priority_queue::insert
void insert(const IT &start, const IT &end)
Insert some elements and run make_heap.
Definition: internal_priority_queue.h:60

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 160 of file internal_priority_queue.h.

160 {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 88 of file internal_priority_queue.h.

Referenced by tpie::internal_priority_queue< std::pair< T, size_t >, tpie::merger::predwrap >::pop(), and tpie::internal_priority_queue< std::pair< T, size_t >, tpie::merger::predwrap >::pop_and_push().

88 {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 153 of file internal_priority_queue.h.

153  {
154  return pq;
155  }
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 60 of file internal_priority_queue.h.

Referenced by tpie::internal_priority_queue< std::pair< T, size_t >, tpie::merger::predwrap >::internal_priority_queue().

60  {
61  std::copy(start, end, pq.find(sz));
62  sz += (end - start);
63  make_safe();
64  }
tpie::array::find
iterator find(size_t idx)
Return an iterator to the i'th element of the array.
Definition: array.h:166
tpie::internal_priority_queue::make_safe
void make_safe()
Make the priority queue safe after a sequence of calls to unsafe_push.
Definition: internal_priority_queue.h:80
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 80 of file internal_priority_queue.h.

Referenced by tpie::internal_priority_queue< std::pair< T, size_t >, tpie::merger::predwrap >::insert().

80  {
81  std::make_heap(pq.begin(), pq.find(sz), comp);
82  }
tpie::array::find
iterator find(size_t idx)
Return an iterator to the i'th element of the array.
Definition: array.h:166
tpie::array::begin
iterator begin()
Return an iterator to the beginning of the array.
Definition: array.h:274
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 136 of file internal_priority_queue.h.

136  {
137  return tpie::array<T>::memory_coefficient();
138  }
tpie::array::memory_coefficient
static double memory_coefficient()
Return the memory coefficient of the structure.
Definition: array.h:360
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
memoryThe 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.

93  {
94  return static_cast<memory_size_type>(
95  floor((memory - child_t::memory_overhead()) / child_t::memory_coefficient()));
96  }
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 144 of file internal_priority_queue.h.

144  {
145  return tpie::array<T>::memory_overhead() - sizeof(tpie::array<T>) + sizeof(internal_priority_queue);
146  }
tpie::array::memory_overhead
static double memory_overhead()
Return the memory overhead of the structure.
Definition: array.h:367
tpie::internal_priority_queue::internal_priority_queue
internal_priority_queue(size_type max_size, comp_t c=comp_t())
Construct a priority queue.
Definition: internal_priority_queue.h:45
static stream_size_type tpie::linear_memory_base< internal_priority_queue< T, comp_t > >::memory_usage ( stream_size_type  size)
inlinestaticinherited

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

Parameters
sizeThe number of elements to support
Returns
The amount of memory required in bytes

Definition at line 81 of file util.h.

81  {
82  return static_cast<stream_size_type>(
83  floor(static_cast<double>(size) * child_t::memory_coefficient() + child_t::memory_overhead()));
84  }
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 110 of file internal_priority_queue.h.

110  {
111  assert(!empty());
112  std::pop_heap(pq.begin(), pq.find(sz), comp);
113  --sz;
114  }
tpie::array::find
iterator find(size_t idx)
Return an iterator to the i'th element of the array.
Definition: array.h:166
tpie::internal_priority_queue::empty
bool empty() const
Is the queue empty?
Definition: internal_priority_queue.h:88
tpie::array::begin
iterator begin()
Return an iterator to the beginning of the array.
Definition: array.h:274
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 119 of file internal_priority_queue.h.

119  {
120  assert(!empty());
121  pq[0] = v;
122  pop_and_push_heap(pq.begin(), pq.find(sz), comp);
123  }
tpie::pop_and_push_heap
void pop_and_push_heap(T a, T b, C lt)
Restore heap invariants after the first element has been replaced by some other element.
Definition: util.h:119
tpie::array::find
iterator find(size_t idx)
Return an iterator to the i'th element of the array.
Definition: array.h:166
tpie::internal_priority_queue::empty
bool empty() const
Is the queue empty?
Definition: internal_priority_queue.h:88
tpie::array::begin
iterator begin()
Return an iterator to the beginning of the array.
Definition: array.h:274
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
vThe element that should be inserted.

Definition at line 101 of file internal_priority_queue.h.

101  {
102  assert(size() < pq.size());
103  pq[sz++] = v;
104  std::push_heap(pq.begin(), pq.find(sz), comp);
105  }
tpie::internal_priority_queue::size
size_type size() const
Returns the size of the queue.
Definition: internal_priority_queue.h:94
tpie::array::size
size_type size() const
Return the size of the array.
Definition: array.h:472
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
sNew size of priority queue.

Definition at line 166 of file internal_priority_queue.h.

166 {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:431
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 94 of file internal_priority_queue.h.

Referenced by tpie::internal_priority_queue< std::pair< T, size_t >, tpie::merger::predwrap >::push().

94 {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 130 of file internal_priority_queue.h.

130 {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
vThe element that should be inserted.

Definition at line 72 of file internal_priority_queue.h.

72  {
73  pq[sz++] = v;
74  }
The documentation for this class was generated from the following file:
  • from TPIE v1.1rc1-6-g0c97303 (browse source). Generated on Fri Mar 31 2017 00:00:12 by Doxygen 1.8.7