Struct cjdns_snode::pathsearch::frontier::Frontier

pub(super) struct Frontier<T, W> {
    queue: Vec<(T, W)>,
    index: HashMap<T, usize>,
}

Frontier for the Dijkstra algorithm. Internally uses binary search to maintain priority queue and hashmap-based index.

Fields

queue: Vec<(T, W)>

Stores items in cost-descending order, so the item with the lowest cost is placed at the end of the array.

index: HashMap<T, usize>

Links node tag <T> to the index in the queue.

Implementations

impl<T, W> Frontier<T, W> where
    T: Clone + Ord + Eq + Hash,
    W: Clone + PartialOrd + IntoOrd, 

pub fn new() -> Frontier<T, W>

Create new empty instance.

fn key_fn(item: &(T, W)) -> impl Ord

Sorts by cost in descending order, then by tag.

fn insertion_pos(&self, item: &(T, W)) -> usize

Find position in the queue where to insert a new item.

pub fn push(&mut self, tag: T, weight: W)

Insert a node with associated cost into the priority queue.

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

Extract node with the least cost from the queue.

pub fn try_insert_or_decrease_cost(&mut self, tag: &T, new_cost: W) -> bool

Insert a node if it is not in the queue yet, otherwise update associated cost if the new cost is less that existing. Returns true if the node was either inserted or updated, otherwise (node existed and current cost is less that the new one) false.