Struct PriorityQueue

Source

pub struct PriorityQueue<K, P>where
    K: Clone + Hash,
    P: Clone + Ord + PartialEq,
{ /* private fields */ }

Expand description

§About

See the module-level documentation for more information.

Implementations§

Source §

impl<K, P> PriorityQueue<K, P>
where K: Debug + Clone + Hash, P: Clone + Debug + Ord + PartialEq,

Source

pub fn new() -> Self

Creates a new, zero-sized PriorityQueue. Warning: Unimplemented

Source

pub fn new_with_capacity(capacity: usize) -> Self

Creates a new PriorityQueue that pre-allocates to the given capacity.

Source

pub fn len(&self) -> usize

Returns the number of live elements in the queue.

Source

pub fn is_empty(&self) -> bool

Returns true if the queue is empty.

Source

pub fn contains(&self, key: K) -> bool

Returns true if the provided key exists within the priority queue.

Source

pub fn put(&mut self, key: K, priority: P)

Adds an element to the heap in O(log(n)) time. It is the caller’s responsibility to ensure key uniqueness; this function overwrites priority values for duplicate keys.

Source

pub fn try_put(&mut self, key: K, priority: P) -> Result<(), &str>

Attempts to add an element to the heap in O(log(n)) time. Returns an error if the key already exists in the queue.

Source

pub fn peek(&self) -> Option<(&K, &P)>

Returns a tuple containing an immutable reference to the data at the top of the front of the queue in O(1) time, if the queue is not empty. Otherwise, returns None.

Source

pub fn mutate_priority(&mut self, key: K, new_priority: P) -> Result<P, &str>

Operates like put(K, P) but returns a Result that contains the old priority, if it exists. Operation requires O(log(n)) time.

Source

pub fn mutate_key(&mut self, old_key: K, new_key: K) -> Result<K, &str>

Attempts to replace the key in a key:value pair in the queue in O(1) time, if it exists. If the key does not exist, the operation returns an error.

Source

pub fn clean(&mut self)

A manual tool to rehash and shrink the structure’s map down to a load factor <= 0.5. The structure automatically rehashes the underlying map for remove and key mutation operations to reduce spatial bloat in long-lived queues with many such mutations. This operation provides a manual way to actually shrink the underlying map down to a load factor of 0.5 over live entries only. This operation uses the map’s shrink_to_fit() operation to clean up the backing structure for long-lived queues in O(n) time where n is the number of live entries in the queue.

Source

pub fn pop(&mut self) -> Option<(K, P)>

Removes and returns the highest priority pair in the queue. This operation automatically checks for spatial bloat and rehashes the underlying map when tombstones outnumber live entries. Amortized cost is O(log n), but a rehash may occasionally incur O(n) time where n is the number of live entries in the queue.

Source

pub fn remove(&mut self, key: K) -> Option<(K, P)>

Removes and returns an arbitrarily-located entry for the given key. This operation automatically checks for spatial bloat and rehashes the underlying map when tombstones outnumber live entries. Amortized cost is O(log n), but a rehash may occasionally incur O(n) time where n is the number of live entries in the queue.