rshyper_algo/dijkstra/
queue_node.rs

1/*
2    appellation: queue_node <module>
3    authors: @FL03
4*/
5use core::cmp::Ordering;
6use rshyper::idx::{RawIndex, VertexId};
7
8/// A node in the priority queue for Dijkstra's algorithm
9#[derive(Copy, Clone, Debug, Default)]
10pub struct QueueNode<Idx, T>
11where
12    Idx: RawIndex,
13{
14    pub(crate) cost: T,
15    pub(crate) vertex: VertexId<Idx>,
16}
17
18impl<Idx, T> QueueNode<Idx, T>
19where
20    Idx: RawIndex,
21{
22    /// Creates a new [`QueueNode`] with the given cost and vertex.
23    pub const fn new(cost: T, vertex: VertexId<Idx>) -> Self {
24        Self { cost, vertex }
25    }
26    /// create a new node with the given cost and a default vertex
27    pub fn from_cost(cost: T) -> Self
28    where
29        Idx: Default,
30    {
31        Self::new(cost, Default::default())
32    }
33    /// create a new node with the given vertex and a default cost
34    pub fn from_vertex(vertex: VertexId<Idx>) -> Self
35    where
36        T: Default,
37    {
38        Self::new(Default::default(), vertex)
39    }
40    /// returns an immutable reference to the cost of the node
41    pub const fn cost(&self) -> &T {
42        &self.cost
43    }
44    /// returns a mutable reference to the cost of the node
45    pub const fn cost_mut(&mut self) -> &mut T {
46        &mut self.cost
47    }
48    /// returns an immutable reference to the vertex of the node
49    pub const fn vertex(&self) -> &VertexId<Idx> {
50        &self.vertex
51    }
52    /// returns a mutable reference to the vertex of the node
53    pub const fn vertex_mut(&mut self) -> &mut VertexId<Idx> {
54        &mut self.vertex
55    }
56    /// update the current cost and return a mutable reference to the node
57    pub fn set_cost(&mut self, cost: T) -> &mut Self {
58        *self.cost_mut() = cost;
59        self
60    }
61    /// update the current vertex and return a mutable reference to the node
62    pub fn set_vertex(&mut self, vertex: VertexId<Idx>) -> &mut Self {
63        *self.vertex_mut() = vertex;
64        self
65    }
66    /// consumes the current instance to create another with the given cost
67    pub fn with_cost(self, cost: T) -> Self {
68        Self { cost, ..self }
69    }
70    /// consumes the current instance to create another with the given vertex
71    pub fn with_vertex(self, vertex: VertexId<Idx>) -> Self {
72        Self { vertex, ..self }
73    }
74}
75
76impl<Idx, T> Eq for QueueNode<Idx, T>
77where
78    Idx: RawIndex + PartialEq,
79    T: PartialEq,
80{
81}
82
83impl<Idx, T> core::hash::Hash for QueueNode<Idx, T>
84where
85    Idx: RawIndex + Eq + core::hash::Hash,
86    T: Eq + core::hash::Hash,
87{
88    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
89        self.cost().hash(state);
90        self.vertex().hash(state);
91    }
92}
93
94impl<Idx, T> Ord for QueueNode<Idx, T>
95where
96    Idx: RawIndex + PartialEq,
97    T: PartialOrd + PartialEq,
98{
99    fn cmp(&self, other: &Self) -> Ordering {
100        // Reverse order for min-heap
101        other
102            .cost()
103            .partial_cmp(self.cost())
104            .unwrap_or(Ordering::Equal)
105    }
106}
107
108impl<Idx, T> PartialEq<QueueNode<Idx, T>> for QueueNode<Idx, T>
109where
110    Idx: RawIndex + PartialEq,
111    T: PartialEq,
112{
113    fn eq(&self, other: &QueueNode<Idx, T>) -> bool {
114        self.cost() == other.cost() && self.vertex() == other.vertex()
115    }
116}
117
118impl<'a, Idx, T> PartialEq<&'a QueueNode<Idx, T>> for QueueNode<Idx, T>
119where
120    Idx: RawIndex + PartialEq,
121    T: PartialEq,
122{
123    fn eq(&self, other: &&'a QueueNode<Idx, T>) -> bool {
124        self.cost() == other.cost() && self.vertex() == other.vertex()
125    }
126}
127
128impl<'a, Idx, T> PartialEq<&'a mut QueueNode<Idx, T>> for QueueNode<Idx, T>
129where
130    Idx: RawIndex + PartialEq,
131    T: PartialEq,
132{
133    fn eq(&self, other: &&'a mut QueueNode<Idx, T>) -> bool {
134        self.cost() == other.cost() && self.vertex() == other.vertex()
135    }
136}
137
138impl<Idx, T> PartialEq<QueueNode<Idx, T>> for &QueueNode<Idx, T>
139where
140    Idx: RawIndex + PartialEq,
141    T: PartialEq,
142{
143    fn eq(&self, other: &QueueNode<Idx, T>) -> bool {
144        self.cost() == other.cost() && self.vertex() == other.vertex()
145    }
146}
147
148impl<Idx, T> PartialEq<QueueNode<Idx, T>> for &mut QueueNode<Idx, T>
149where
150    Idx: RawIndex + PartialEq,
151    T: PartialEq,
152{
153    fn eq(&self, other: &QueueNode<Idx, T>) -> bool {
154        self.cost() == other.cost() && self.vertex() == other.vertex()
155    }
156}
157
158impl<Idx, T> PartialOrd<QueueNode<Idx, T>> for QueueNode<Idx, T>
159where
160    Idx: RawIndex + PartialEq,
161    T: PartialEq + PartialOrd,
162{
163    fn partial_cmp(&self, other: &QueueNode<Idx, T>) -> Option<Ordering> {
164        self.cost().partial_cmp(other.cost())
165    }
166}
167
168impl<'a, Idx, T> PartialOrd<&'a QueueNode<Idx, T>> for QueueNode<Idx, T>
169where
170    Idx: RawIndex + PartialEq,
171    T: PartialEq + PartialOrd,
172{
173    fn partial_cmp(&self, other: &&'a QueueNode<Idx, T>) -> Option<Ordering> {
174        self.cost().partial_cmp(other.cost())
175    }
176}
177
178impl<'a, Idx, T> PartialOrd<&'a mut QueueNode<Idx, T>> for QueueNode<Idx, T>
179where
180    Idx: RawIndex + PartialEq,
181    T: PartialEq + PartialOrd,
182{
183    fn partial_cmp(&self, other: &&'a mut QueueNode<Idx, T>) -> Option<Ordering> {
184        self.cost().partial_cmp(other.cost())
185    }
186}
187
188impl<Idx, T> PartialOrd<QueueNode<Idx, T>> for &QueueNode<Idx, T>
189where
190    Idx: RawIndex + PartialEq,
191    T: PartialEq + PartialOrd,
192{
193    fn partial_cmp(&self, other: &QueueNode<Idx, T>) -> Option<Ordering> {
194        self.cost().partial_cmp(other.cost())
195    }
196}
197
198impl<Idx, T> PartialOrd<QueueNode<Idx, T>> for &mut QueueNode<Idx, T>
199where
200    Idx: RawIndex + PartialEq,
201    T: PartialEq + PartialOrd,
202{
203    fn partial_cmp(&self, other: &QueueNode<Idx, T>) -> Option<Ordering> {
204        self.cost().partial_cmp(other.cost())
205    }
206}
rshyper_algo/dijkstra/queue_node.rs

rshyper_algo/dijkstra/
queue_node.rs
