Struct IndexedPriorityQueue

pub struct IndexedPriorityQueue<Index, Priorities, Positions>
where
    Index: Copy,
    Priorities: Indexed<Index = Index, Output: Ord + Clone>,
    Positions: Indexed<Index = Index, Output = usize>,
{ /* private fields */ }

Indexed Priority Queue.

Implementations

impl<Index, Priorities, Positions> IndexedPriorityQueue<Index, Priorities, Positions>

where Index: Copy, Priorities: Indexed<Index = Index, Output: Ord + Clone>, Positions: Indexed<Index = Index, Output = usize>,

pub fn new( priorities: impl Into<Priorities>, positions: impl Into<Positions>, ) -> Self

Constructs a new, empty IndexedPriorityQueue.

pub fn with_capacity( priorities: impl Into<Priorities>, positions: impl Into<Positions>, capacity: usize, ) -> Self

Constructs a new, empty IndexedPriorityQueue with at least the specified capacity.

pub fn len(&self) -> usize

Returns the number of indices in the indexed priority queue.

Time complexity: O(1)

pub fn is_empty(&self) -> bool

Returns true if the priority queue contains no indices.

Time complexity: O(1)

pub fn contains(&self, index: Index) -> bool

Returns true if the priority queue contains the specified index.

Time complexity: O(1)

pub fn min_priority(&self) -> Option<&Priorities::Output>

Returns the smallest priority in the queue, or None, if it is empty.

Time complexity: O(1)

pub fn get_priority(&self, index: Index) -> Option<&Priorities::Output>

Returns the priority associated with the specified index, or None, if the index is not in the queue.

Time complexity: O(1)

pub fn restore_index(&mut self, index: Index)

Reinserts a previously removed index into the queue with its last associated value.

Time complexity: O(log n)

pub fn remove(&mut self, index: Index) -> Priorities::Output

Removes the specified index and its associated priority from the queue. This method should not be called with indices that are not present in the queue. Returns the removed priority.

Time complexity: O(log n)

pub fn remove_index(&mut self, index: Index)

Removes the specified index from the queue, retaining its associated priority.

Time complexity: O(log n)

pub fn clear(&mut self)

Clears all indices and their priorities from the queue.

pub fn clear_indices(&mut self)

Clears all indices from the queue.

pub fn push( &mut self, index: Index, value: Priorities::Output, ) -> Option<Priorities::Output>

Inserts an index-priority pair into the priority queue. Returns the previous priority associated with the index, if it existed.

Time complexity: O(log n)

pub fn min(&self) -> Option<&Index>

Returns the index associated with the smallest priority in the queue, or None if it is empty.

Time complexity: O(1)

pub fn pop(&mut self) -> Option<Index>

Removes and returns the index associated with the smallest priority in the queue, or None if it is empty.

Time complexity: O(log n)

pub fn update_priorities_order_preserving( &mut self, f: impl Fn(&mut Priorities::Output), )

Update the priorities of the values in the heap using a function The function must not change the relative order of any elements in the heap

impl<Index, Priorities, Positions> IndexedPriorityQueue<Index, Priorities, Positions>

where Index: Copy, Priorities: Indexed<Index = Index, Output: Ord + Clone>, Positions: Indexed<Index = Index, Output = usize>,

pub fn update_up( &mut self, index: Index, ) -> IPQMutRefUp<'_, Index, Priorities, Positions>

impl<Index, Priorities, Positions> IndexedPriorityQueue<Index, Priorities, Positions>

where Index: Copy, Priorities: Indexed<Index = Index, Output: Ord + Clone>, Positions: Indexed<Index = Index, Output = usize>,

pub fn update_down( &mut self, index: Index, ) -> IPQMutRefDown<'_, Index, Priorities, Positions>

impl<Index, Priorities, Positions> IndexedPriorityQueue<Index, Priorities, Positions>

where Index: Copy, Priorities: Indexed<Index = Index, Output: Ord + Clone>, Positions: Indexed<Index = Index, Output = usize>,

pub fn update_dyn( &mut self, index: Index, ) -> IPQMutRefDyn<'_, Index, Priorities, Positions>

Trait Implementations

impl<Index, Priorities, Positions> Debug for IndexedPriorityQueue<Index, Priorities, Positions>

where Index: Copy + Debug, Priorities: Indexed<Index = Index, Output: Ord + Clone> + Debug, Positions: Indexed<Index = Index, Output = usize> + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Index, Priorities, Positions> Default for IndexedPriorityQueue<Index, Priorities, Positions>

where Index: Copy, Priorities: Indexed<Index = Index, Output: Ord + Clone> + Default, Positions: Indexed<Index = Index, Output = usize> + Default,

fn default() -> Self

Returns the “default value” for a type.