Struct BPQueue 

pub struct BPQueue<T> {
    pub bucket: Vec<Dllist<(usize, T)>>,
    /* private fields */
}

The BPQueue struct is a bounded priority queue implemented using an array of doubly-linked lists, with integer keys in a specified range.

Bounded Priority Queue with integer keys in [a..b]. Implemented by an array (bucket) of doubly-linked lists. Efficient if the keys are bounded by a small integer value.

Note that this class does not own PQ nodes. This feature allows these nodes sharable in both doubly linked list class and this class. In the FM algorithm, nodes are either attached to the gain buckets (PQ) or to the waitinglist (doubly-linked list), but cannot be in both at the same time.

Another improvement is to increase the size of the array by one element, i.e. (b - a + 2). The extra dummy array element (called sentinel) is used to reduce the boundary checking during updates.

All the member functions assume that the keys are inside the bounds.

Properties:

• max: The maximum number of elements that can be stored in the bounded priority queue.
• offset: The offset property represents the lower bound of the integer keys in the bounded priority queue. It is of type i32, which means it can hold both positive and negative values. The offset is used to calculate the index of the bucket in the bucket array for a given key.
• high: The high property represents the highest priority level in the bounded priority queue. It indicates the index of the last bucket in the bucket array.
• sentinel: A doubly linked list node that serves as a sentinel or dummy node. It is used to reduce boundary checking during updates.
• bucket: The bucket property is a vector of doubly-linked lists. Each doubly-linked list represents a priority level, with the index of the vector representing the priority value. The elements in the doubly-linked lists are tuples containing a priority value and a value of type T.

Fields

bucket: Vec<Dllist<(usize, T)>>

Implementations

impl<T: Default + Clone> BPQueue<T>

pub fn new(a: i32, b: i32) -> Self

Construct a new BPQueue object

Examples

use mywheel_rs::bpqueue::BPQueue;
let bpq = BPQueue::<i32>::new(-3, 3);

assert!(bpq.is_empty());

pub fn is_empty(&self) -> bool

Whether the %BPQueue is empty.

Examples

use mywheel_rs::bpqueue::BPQueue;
let bpq = BPQueue::<i32>::new(-3, 3);

assert!(bpq.is_empty());

pub fn get_max(&self) -> i32

Get the max value

Examples

use mywheel_rs::bpqueue::BPQueue;
let bpq = BPQueue::<i32>::new(-3, 3);

assert_eq!(bpq.get_max(), -4);

pub fn clear(&mut self)

Clear reset the PQ

Examples

use mywheel_rs::bpqueue::BPQueue;
let mut bpq = BPQueue::<i32>::new(-3, 3);
bpq.clear();

assert!(bpq.is_empty());

pub fn set_key(&mut self, it: &mut Dllink<(usize, T)>, gain: i32)

Set the key object

Examples

use mywheel_rs::bpqueue::BPQueue;
let mut bpq = BPQueue::<i32>::new(-3, 3);

assert!(bpq.is_empty());

pub fn append(&mut self, it: &mut Dllink<(usize, T)>, k: i32)

Append item with external key

Examples

use mywheel_rs::bpqueue::BPQueue;
use mywheel_rs::dllist::Dllink;

let mut bpq = BPQueue::<i32>::new(-3, 3);
let mut a = Dllink::<(usize, i32)>::new((0, 3));
bpq.append(&mut a, 0);

assert!(!bpq.is_empty());

pub fn appendleft(&mut self, it: &mut Dllink<(usize, T)>, k: i32)

Append item with external key

Examples

use mywheel_rs::bpqueue::BPQueue;
use mywheel_rs::dllist::Dllink;

let mut bpq = BPQueue::<i32>::new(-3, 3);
let mut a = Dllink::<(usize, i32)>::new((0, 3));
bpq.appendleft(&mut a, 0);

assert!(!bpq.is_empty());

pub fn appendleft_direct(&mut self, it: &mut Dllink<(usize, T)>)

Append item with internal key

Examples

use mywheel_rs::bpqueue::BPQueue;
use mywheel_rs::dllist::Dllink;

let mut bpq = BPQueue::<i32>::new(-3, 3);
let mut a = Dllink::<(usize, i32)>::new((0, 3));
bpq.appendleft_direct(&mut a);

assert!(!bpq.is_empty());

pub fn popleft(&mut self) -> *mut Dllink<(usize, T)>

Pop node with the highest key

Examples

use mywheel_rs::bpqueue::BPQueue;
use mywheel_rs::dllist::Dllink;

let mut bpq = BPQueue::<i32>::new(-3, 3);
let mut a = Dllink::<(usize, i32)>::new((0, 3));
bpq.append(&mut a, 0);
let d = bpq.popleft();
let (key, v) = unsafe { (*d).data.clone() };

assert_eq!(key, 4);
assert_eq!(v, 3);

pub fn detach(&mut self, it: &mut Dllink<(usize, T)>)

Detach the item from BPQueue

Examples

use mywheel_rs::bpqueue::BPQueue;
use mywheel_rs::dllist::Dllink;

let mut bpq = BPQueue::<i32>::new(-3, 3);
let mut a = Dllink::<(usize, i32)>::new((0, 3));
bpq.append(&mut a, 0);
bpq.detach(&mut a);

assert!(bpq.is_empty());

pub fn decrease_key(&mut self, it: &mut Dllink<(usize, T)>, delta: usize)

Decrease key by delta

Note that the order of items with same key will not be preserved. For the FM algorithm, this is a desired behavior.

Examples

use mywheel_rs::bpqueue::BPQueue;
use mywheel_rs::dllist::Dllink;

let mut bpq = BPQueue::<i32>::new(-3, 3);
let mut a = Dllink::<(usize, i32)>::new((0, 3));
bpq.append(&mut a, 0);
bpq.decrease_key(&mut a, 1);

assert_eq!(bpq.get_max(), -1);

pub fn increase_key(&mut self, it: &mut Dllink<(usize, T)>, delta: usize)

Increase key by delta

Note that the order of items with same key will not be preserved. For the FM algorithm, this is a desired behavior.

Examples

use mywheel_rs::bpqueue::BPQueue;
use mywheel_rs::dllist::Dllink;

let mut bpq = BPQueue::<i32>::new(-3, 3);
let mut a = Dllink::<(usize, i32)>::new((0, 3));
bpq.append(&mut a, 0);
bpq.increase_key(&mut a, 1);

assert_eq!(bpq.get_max(), 1);

pub fn modify_key(&mut self, it: &mut Dllink<(usize, T)>, delta: i32)

Modify key by delta

Note that the order of items with same key will not be preserved. For the FM algorithm, this is a desired behavior.

Examples

use mywheel_rs::bpqueue::BPQueue;
use mywheel_rs::dllist::Dllink;

let mut bpq = BPQueue::<i32>::new(-3, 3);
let mut a = Dllink::<(usize, i32)>::new((0, 3));
bpq.append(&mut a, 0);
bpq.modify_key(&mut a, -1);

assert_eq!(bpq.get_max(), -1);

impl<T: Default> BPQueue<T>

pub fn iter_mut(&mut self) -> BPQueueIterator<'_, T>

Return a new DllIterator object

Trait Implementations

impl<T: Debug> Debug for BPQueue<T>

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

Formats the value using the given formatter.