abstutil/
priority_queue.rs

1use std::cmp::Ordering;
2
3use serde::{Deserialize, Serialize};
4
5/// Use with `BinaryHeap`. Since it's a max-heap, reverse the comparison to get the smallest cost
6/// first.
7#[derive(Serialize, Deserialize, PartialEq, Eq, Clone)]
8pub struct PriorityQueueItem<K, V> {
9    pub cost: K,
10    pub value: V,
11}
12
13impl<K: Ord, V: Ord> PartialOrd for PriorityQueueItem<K, V> {
14    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
15        Some(self.cmp(other))
16    }
17}
18
19impl<K: Ord, V: Ord> Ord for PriorityQueueItem<K, V> {
20    fn cmp(&self, other: &Self) -> Ordering {
21        let ord = other.cost.cmp(&self.cost);
22        if ord != Ordering::Equal {
23            return ord;
24        }
25        // The tie-breaker is arbitrary, based on the value
26        self.value.cmp(&other.value)
27    }
28}
abstutil/priority_queue.rs

abstutil/
priority_queue.rs
