Trait PriorityQueue 

pub unsafe trait PriorityQueue<P: Priority>: Default {
    type Handle: PriorityQueueHandle<P>;
    type SharedHandle: AsRef<Self::Handle>;

    // Required methods
    fn enqueue(&mut self, data: P) -> Self::Handle;
    fn dequeue(
        &mut self,
        handle: Self::Handle,
    ) -> (Option<&P>, Option<Self::SharedHandle>);
    fn get_by_handle(&self, handle: &Self::Handle) -> &P;
    fn iter_at<'a>(
        &'a self,
        handle: Option<&Self::Handle>,
    ) -> impl Iterator<Item = &'a P>
       where P: 'a;
    fn update_node(
        &mut self,
        handle: &Self::Handle,
        update: impl FnOnce(&mut P) -> bool,
    );
    fn head_handle(&self) -> Option<Self::SharedHandle>;
    fn get_next_handle(
        &self,
        handle: &Self::Handle,
    ) -> Option<Self::SharedHandle>;

    // Provided methods
    fn iter<'a>(&'a self) -> impl Iterator<Item = &'a P>
       where P: 'a { ... }
    fn is_empty(&self) -> bool { ... }
    fn head(&self) -> Option<&P> { ... }
}

A PriorityQueue is a queue which orders entries by priority - higher priority first.

This is marked as unsafe as some associated types exist which must behave correctly, in particular:

• An enqueued node will return a Self::Handle
• Until that handle is dequeued via self.dequeue, we must be able to lookup the node - even if that node is repositioned.
• “shared” handles - these allow us to lookup nodes without owning them or retaining a reference to the queue (allowing us to update them, but not remove them)

Any lookups via a handle which was not returned from enqueue or other functions is UB. Implementers can choose to panic or simply assume that all handles provided will be valid.

Additionally, it is required that all nodes be dequeued before the queue is dropped - so the queue should not have any entries when it is dropped.

Required Associated Types

type Handle: PriorityQueueHandle<P>

type SharedHandle: AsRef<Self::Handle>

Required Methods

fn enqueue(&mut self, data: P) -> Self::Handle

Enqueue an entry with provided data. This must return a unique handle for this node.

fn dequeue( &mut self, handle: Self::Handle, ) -> (Option<&P>, Option<Self::SharedHandle>)

Dequeue an entry by its handle

fn get_by_handle(&self, handle: &Self::Handle) -> &P

Get an entry’s data by its handle

fn iter_at<'a>( &'a self, handle: Option<&Self::Handle>, ) -> impl Iterator<Item = &'a P>

where P: 'a,

Iterate through the queue starting at a provided handle (or None to start with the head node) (including the provided value)

fn update_node( &mut self, handle: &Self::Handle, update: impl FnOnce(&mut P) -> bool, )

Update a node via handle ref. update is a fn that should return true if the node’s priority changed. i.e. if update returns false, the queue does not need to consider repositioning the changed node.

fn head_handle(&self) -> Option<Self::SharedHandle>

Get a SharedHandle for the first node in the queue

fn get_next_handle(&self, handle: &Self::Handle) -> Option<Self::SharedHandle>

Get the handle for the next node after an input handle (or None if the provided handle is the tail node)

Provided Methods

fn iter<'a>(&'a self) -> impl Iterator<Item = &'a P>

where P: 'a,

Iterate through the queue from the start.

fn is_empty(&self) -> bool

Returns true if the queue is empty

fn head(&self) -> Option<&P>

Get the first node in the queue

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<N: ArenaQueueNode> PriorityQueue<<N as ArenaQueueNode>::Data> for ArenaQueue<N>

type Handle = ArenaQueueHandle<N>

type SharedHandle = SharedArenaQueueHandle<N>

impl<N: BoxQueueNode> PriorityQueue<<N as BoxQueueNode>::Data> for BoxQueue<N>

type Handle = BoxQueueHandle<N>

type SharedHandle = SharedBoxQueueHandle<N>