Turi Create
4.0
|
#include <core/util/mutable_queue.hpp>
Public Types | |
typedef std::pair< T, Priority > | heap_element |
An element of the heap. | |
Public Member Functions | |
mutable_queue () | |
Default constructor. | |
size_t | size () const |
Returns the number of elements in the heap. | |
bool | empty () const |
Returns true iff the queue is empty. | |
bool | contains (const T &item) const |
Returns true if the queue contains the given value. | |
void | push (T item, Priority priority) |
Enqueues a new item in the queue. | |
const std::pair< T, Priority > & | top () const |
Accesses the item with maximum priority in the queue. | |
std::pair< T, Priority > | pop () |
Priority | get (T item) const |
Returns the weight associated with a key. | |
Priority | operator[] (T item) const |
Returns the priority associated with a key. | |
void | update (T item, Priority priority) |
void | push_or_update (T item, Priority priority) |
bool | insert_max (T item, Priority priority) |
bool | insert_cumulative (T item, Priority priority) |
const std::vector< heap_element > & | values () const |
Returns the values (key-priority pairs) in the priority queue. | |
void | clear () |
Clears all the values (equivalent to stl clear) | |
bool | remove (T item) |
Remove an item from the queue. | |
Protected Types | |
typedef boost::unordered_map< T, size_t > | index_map_type |
The storage type of the index map. | |
Protected Member Functions | |
size_t | left (size_t i) const |
Returns the index of the left child of the supplied index. | |
size_t | right (size_t i) const |
Returns the index of the right child of the supplied index. | |
size_t | parent (size_t i) const |
Returns the index of the parent of the supplied index. | |
Priority | priority_at (size_t i) |
Extracts the priority at a heap location. | |
bool | less (size_t i, size_t j) |
Compares the priorities at two heap locations. | |
void | swap (size_t i, size_t j) |
Swaps the heap locations of two elements. | |
void | heapify (size_t i) |
The traditional heapify function. | |
Protected Attributes | |
std::vector< heap_element > | heap |
The heap used to store the elements. The first element is unused. | |
index_map_type | index_map |
The map used to map from items to indexes in the heap. | |
A heap implementation of a priority queue that supports external priorities and priority updates. Both template arguments must be Assignable, EqualityComparable, and LessThanComparable.
T | the type of items stored in the priority queue. |
Priority | the type used to prioritize items. |
Definition at line 65 of file mutable_queue.hpp.
|
inline |
If item is already in the queue, sets its priority to the sum of the old priority and the new one. If the item is not in the queue, adds it to the queue.
returns true if the item was already present
Definition at line 284 of file mutable_queue.hpp.
|
inline |
If item is already in the queue, sets its priority to the maximum of the old priority and the new one. If the item is not in the queue, adds it to the queue.
returns true if the items was not already
Definition at line 255 of file mutable_queue.hpp.
|
inline |
Removes the item with maximum priority from the queue, and returns it with its priority.
Definition at line 185 of file mutable_queue.hpp.
|
inline |
Updates the priority associated with a item in the queue. If the item is not already present, insert it.
Definition at line 230 of file mutable_queue.hpp.
|
inline |
Updates the priority associated with a item in the queue. This function fails if the item is not already present.
Definition at line 212 of file mutable_queue.hpp.