Trait orx_priority_queue::PriorityQueueDecKey

pub trait PriorityQueueDecKey<N, K>: PriorityQueue<N, K>where
    N: Clone,
    K: PartialOrd + Clone,{
    // Required methods
    fn contains(&self, node: &N) -> bool;
    fn key_of(&self, node: &N) -> Option<K>;
    fn decrease_key(&mut self, node: &N, decreased_key: &K);
    fn update_key(&mut self, node: &N, new_key: &K) -> bool;
    fn remove(&mut self, node: &N) -> K;

    // Provided methods
    fn try_decrease_key(&mut self, node: &N, new_key: &K) -> bool { ... }
    fn decrease_key_or_push(&mut self, node: &N, key: &K) -> bool { ... }
    fn update_key_or_push(&mut self, node: &N, key: &K) -> bool { ... }
    fn try_decrease_key_or_push(&mut self, node: &N, key: &K) -> bool { ... }
}

A PriorityQueueDecKey is a more advanced PriorityQueue with additional features mainly related to accessing or modifying already pushed nodes such as:

• checking if a node is present in the queue,
• getting the key of an alrady pushed node,
• decreasing or updating the key of an already pushed node.

This is often achieved by additional memory requirement; hence, it is separated from the PriorityQueue.

Another fundamental difference of PriorityQueueDecKey from PriorityQueue is that it behaves as a set enabled by the contains method. In other words,

• the same node can be pushed to a PriorityQueue an arbitrary number of times with same or different keys;
• on the other hand, a node can only be pushed to the PriorityQueueDecKey only once; however, the node in the queue can be mutated.

The PriorityQueue requires more space to handle a problem with lots of decrease key operations; PriorityQueueDecKey aims to be memory efficient in such situations. On the other hand, PriorityQueue could be preferable where number of such upadtes is limited due to its lack of additional checks and tracking.

Required Methods

fn contains(&self, node: &N) -> bool

Returns whether the given node is in the queue or not.

fn key_of(&self, node: &N) -> Option<K>

Returns the key of the given node if it is in the queue; returns None otherwise.

fn decrease_key(&mut self, node: &N, decreased_key: &K)

Decreases key of the node which is already in the queue to the given decreased_key. This method is commonly use to increase priority of a node; rather than to re-insert it to keep the size of the queue smaller.

Panics

This method panics if:

• the node is not in the queue; or
• decreased_key is strictly larget than key of the node in the queue.

See also

Note that the following methods have minor but important differences making them suitable for different cases/algorithms: decrease_key, update_key, try_decrease_key, decrease_key_or_push, update_key_or_push and try_decrease_key_or_push.

fn update_key(&mut self, node: &N, new_key: &K) -> bool

Updates key of the node which is already in the queue as the given new_key; and returns whether the node’s key is strictly decreased or not.

Panics

This method panics if:

• the node is not in the queue.

See also

Note that the following methods have minor but important differences making them suitable for different cases/algorithms: decrease_key, update_key, try_decrease_key, decrease_key_or_push, update_key_or_push and try_decrease_key_or_push.

fn remove(&mut self, node: &N) -> K

Removes the node from the queue; and returns its current key.

Panics

This method panics if:

• the node is not in the queue.

Provided Methods

fn try_decrease_key(&mut self, node: &N, new_key: &K) -> bool

This method:

• when new_key is strictly less than the node’s current key:
  • decreases the key of the node to the given new_key, and
  • returns true;
• otherwise:
  • does not change the queue, and
  • returns false.

In brief, the method returns whether the key of the node is decreased or not.

Panics

This method panics if:

• the node is not in the queue.

See also

Note that the following methods have minor but important differences making them suitable for different cases/algorithms: decrease_key, update_key, try_decrease_key, decrease_key_or_push, update_key_or_push and try_decrease_key_or_push.

fn decrease_key_or_push(&mut self, node: &N, key: &K) -> bool

This method

• when the node is present in the queue:
  • decreases its key to the given new key which is expected to be less than or equal to the current key, and
  • returns true;
• otherwise:
  • pushes the node with the given key to the queue, and
  • returns false.

In brief, the method returns whether the key of the node is decreased or not.

Panics

This method panics if:

• the node is in the queue; however, its current key is strictly less than the provided key.

See also

Note that the following methods have minor but important differences making them suitable for different cases/algorithms: decrease_key, update_key, try_decrease_key, decrease_key_or_push, update_key_or_push and try_decrease_key_or_push.

fn update_key_or_push(&mut self, node: &N, key: &K) -> bool

This method

• when the node is present in the queue:
  • updates its key to the given new key, and
  • returns whether the update operation strictly decreased the node’s key or not;
• otherwise:
  • pushes the node with the given key to the queue, and
  • returns false.

In brief, the method returns whether the key of the node is decreased or not.

See also

Note that the following methods have minor but important differences making them suitable for different cases/algorithms: decrease_key, update_key, try_decrease_key, decrease_key_or_push, update_key_or_push and try_decrease_key_or_push.

fn try_decrease_key_or_push(&mut self, node: &N, key: &K) -> bool

This method

• when the node is present in the queue:
  • when the new key is strictly less than the node’s current key:
    • decreases the key of the node to the given key, and
    • returns true;
  • otherwise:
    • does not change the queue, and
    • returns false;
• otherwise:
  • pushes the node with the given key to the queue, and
  • returns false.

In brief, the method returns whether the key of the node is decreased or not.

See also

Note that the following methods have minor but important differences making them suitable for different cases/algorithms: decrease_key, update_key, try_decrease_key, decrease_key_or_push, update_key_or_push and try_decrease_key_or_push.

Implementors

impl<N, K, const D: usize> PriorityQueueDecKey<N, K> for DaryHeapOfIndices<N, K, D>where N: HasIndex, K: PartialOrd + Clone,

impl<N, K, const D: usize> PriorityQueueDecKey<N, K> for DaryHeapWithMap<N, K, D>where N: Eq + Hash + Clone, K: PartialOrd + Clone,