Struct WorkQueue

pub struct WorkQueue<T: Idx + From<usize>> {
    pub deque: VecDeque<T>,
    pub set: BitSet<T>,
}

A work queue is a handy data structure for tracking work left to do. (For example, basic blocks left to process.) It is basically a de-duplicating queue; so attempting to insert X if X is already enqueued has no effect. This implementation assumes that the elements are dense indices, so it can allocate the queue to size and also use a bit set to track occupancy.

Fields

deque: VecDeque<T>

set: BitSet<T>

Implementations

impl<T: Idx + From<usize>> WorkQueue<T>

pub fn with_all(len_idx: T) -> Self

Creates a new work queue with all the elements from (0..len).

pub fn with_none(len_idx: T) -> Self

Creates a new work queue that starts empty, where elements range from (0..len).

pub fn insert(&mut self, element: T) -> bool

Attempt to enqueue element in the work queue. Returns false if it was already present.

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

Attempt to pop an element from the work queue.

pub fn take(&mut self) -> Option<T>

Attempt to take an element from from the work queue This function does not remove the item from the iternal set As such any element removed using take can never be inserted again. For must use cases [pop]should be used

This is useful when you want to write a worklist based algorithm that processes every element exactly one

pub fn is_empty(&self) -> bool

Returns true if nothing is enqueued.

Trait Implementations

impl<I: Idx + From<usize> + Debug> Debug for WorkQueue<I>

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

Formats the value using the given formatter.

impl<I: Idx + From<usize>> From<BitSet<I>> for WorkQueue<I>

fn from(set: BitSet<I>) -> Self

Converts to this type from the input type.