orx_priority_queue/dary/
daryheap_map.rs

1use super::heap::Heap;
2use crate::positions::map::{HeapPositionsMap, Index};
3use crate::{PriorityQueue, PriorityQueueDecKey, ResUpdateKey};
4
5/// Type alias for `DaryHeapWithMap<N, K, 2>`; see [`DaryHeapWithMap`] for details.
6pub type BinaryHeapWithMap<N, K> = DaryHeapWithMap<N, K, 2>;
7/// Type alias for `DaryHeapWithMap<N, K, 4>`; see [`DaryHeapWithMap`] for details.
8pub type QuaternaryHeapWithMap<N, K> = DaryHeapWithMap<N, K, 4>;
9
10/// A d-ary heap which implements both `PriorityQueue` and `PriorityQueueDecKey`.
11///
12/// See [`PriorityQueueDecKey`] for additional functionalities.
13///
14/// `DaryHeapWithMap` achieves the additional features by making use of a map of nodes to positions on the heap.
15///
16/// # Flexibility (`DaryHeapWithMap`) vs Performance (`DaryHeapOfIndices`)
17///
18/// [`DaryHeapWithMap`] (hence its variants such as [`BinaryHeapWithMap`]) does not require to know
19/// the absolute size of the closed set.
20/// Furthermore, the node type needs to implement `Hash + Eq` rather than `HasIndex` trait defined in this crate.
21/// Due to these, `DaryHeapWithMap` might be considered as the more flexible [`PriorityQueueDecKey`] variant.
22///
23/// On the other hand, `DaryHeapOfIndices` (hence its variants such as `BinaryHeapOfIndices`),
24/// provides significantly faster accesses to positions of nodes on the heap.
25/// This is important for [`PriorityQueueDecKey`] operations such as `decrease_key` or `contains`.
26/// Furthermore, in many algorithms such as certain network algorithms where nodes enter and exit the queue,
27/// `index_bound` can often trivially be set to number of nodes.
28///
29/// # Examples
30///
31/// ## Heap as a `PriorityQueue`
32///
33/// Usage of d-ary heap as a basic priority queue.
34///
35/// ```
36/// use orx_priority_queue::*;
37///
38/// fn test_priority_queue<P>(mut pq: P)
39/// where
40///     P: PriorityQueue<usize, f64>
41/// {
42///     pq.clear();
43///
44///     pq.push(0, 42.0);
45///     assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
46///     assert_eq!(Some(&42.0), pq.peek().map(|x| x.key()));
47///
48///     pq.push(1, 7.0);
49///     assert_eq!(Some(&1), pq.peek().map(|x| x.node()));
50///     assert_eq!(Some(&7.0), pq.peek().map(|x| x.key()));
51///
52///     let popped = pq.pop();
53///     assert_eq!(Some((1, 7.0)), popped);
54///
55///     let popped = pq.pop();
56///     assert_eq!(Some((0, 42.0)), popped);
57///
58///     assert!(pq.is_empty());
59/// }
60///
61/// // d-ary heap using a hash map to locate existing nodes (although decrease-key is not used here)
62/// test_priority_queue(DaryHeapWithMap::<_, _, 3>::default());
63/// test_priority_queue(DaryHeapWithMap::<_, _, 4>::with_capacity(16));
64/// // using type aliases to simplify signatures
65/// test_priority_queue(BinaryHeapWithMap::default());
66/// test_priority_queue(BinaryHeapWithMap::with_capacity(16));
67/// test_priority_queue(QuaternaryHeapWithMap::default());
68/// test_priority_queue(QuaternaryHeapWithMap::with_capacity(16));
69/// test_priority_queue(QuaternaryHeapWithMap::default());
70/// test_priority_queue(QuaternaryHeapWithMap::with_capacity(16));
71/// ```
72///
73/// ## Heap as a `PriorityQueueDecKey`
74///
75/// Usage of a d-ary heap as a priority queue with decrease key operation and its variants.
76///
77/// ```
78/// use orx_priority_queue::*;
79///
80/// fn test_priority_queue_deckey<P>(mut pq: P)
81/// where
82///     P: PriorityQueueDecKey<usize, f64>
83/// {
84///     pq.clear();
85///
86///     pq.push(0, 42.0);
87///     assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
88///     assert_eq!(Some(&42.0), pq.peek().map(|x| x.key()));
89///
90///     pq.push(1, 17.0);
91///     assert_eq!(Some(&1), pq.peek().map(|x| x.node()));
92///     assert_eq!(Some(&17.0), pq.peek().map(|x| x.key()));
93///
94///     pq.decrease_key(&0, 7.0);
95///     assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
96///     assert_eq!(Some(&7.0), pq.peek().map(|x| x.key()));
97///
98///     let res_try_deckey = pq.try_decrease_key(&1, 20.0);
99///     assert_eq!(res_try_deckey, ResTryDecreaseKey::Unchanged);
100///
101///     let popped = pq.pop();
102///     assert_eq!(Some((0, 7.0)), popped);
103///
104///     let popped = pq.pop();
105///     assert_eq!(Some((1, 17.0)), popped);
106///
107///     assert!(pq.is_empty());
108/// }
109/// // d-ary heap using a hash map to locate existing nodes
110/// test_priority_queue_deckey(DaryHeapWithMap::<_, _, 3>::default());
111/// test_priority_queue_deckey(DaryHeapWithMap::<_, _, 4>::with_capacity(16));
112/// // using type aliases to simplify signatures
113/// test_priority_queue_deckey(BinaryHeapWithMap::default());
114/// test_priority_queue_deckey(BinaryHeapWithMap::with_capacity(16));
115/// test_priority_queue_deckey(QuaternaryHeapWithMap::default());
116/// test_priority_queue_deckey(QuaternaryHeapWithMap::with_capacity(16));
117/// test_priority_queue_deckey(QuaternaryHeapWithMap::default());
118/// test_priority_queue_deckey(QuaternaryHeapWithMap::with_capacity(16));
119/// ```
120#[derive(Debug, Clone)]
121pub struct DaryHeapWithMap<N, K, const D: usize = 2>
122where
123    N: Index,
124    K: PartialOrd + Clone,
125{
126    heap: Heap<N, K, HeapPositionsMap<N>, D>,
127}
128
129impl<N, K, const D: usize> Default for DaryHeapWithMap<N, K, D>
130where
131    N: Index,
132    K: PartialOrd + Clone,
133{
134    fn default() -> Self {
135        Self {
136            heap: Heap::new(None, HeapPositionsMap::default()),
137        }
138    }
139}
140
141/// Creates a d-ary heap from an iterator in linear time.
142///
143/// The iterator must not contain the same node more than once.
144impl<N, K, const D: usize> FromIterator<(N, K)> for DaryHeapWithMap<N, K, D>
145where
146    N: Index,
147    K: PartialOrd + Clone,
148{
149    fn from_iter<I: IntoIterator<Item = (N, K)>>(iter: I) -> Self {
150        Self {
151            heap: Heap::from_iter(iter, HeapPositionsMap::default()),
152        }
153    }
154}
155
156/// The iterator must not contain the same node more than once.
157impl<N, K, const D: usize> DaryHeapWithMap<N, K, D>
158where
159    N: Index,
160    K: PartialOrd + Clone,
161{
162    /// Creates a new empty d-ary heap.
163    ///
164    ///  # Examples
165    ///
166    /// ```
167    /// use orx_priority_queue::*;
168    ///
169    /// let mut heap = BinaryHeapWithMap::new();
170    ///
171    /// heap.push('a', 4);
172    /// heap.push('b', 42);
173    ///
174    /// assert_eq!(Some('a'), heap.pop_node());
175    /// assert_eq!(Some('b'), heap.pop_node());
176    /// assert!(heap.is_empty());
177    /// ```
178    pub fn new() -> Self {
179        Self::default()
180    }
181
182    /// Creates a new d-ary heap with the given initial `capacity` on the number of nodes to simultaneously exist on the heap.
183    pub fn with_capacity(capacity: usize) -> Self {
184        Self {
185            heap: Heap::new(Some(capacity), HeapPositionsMap::with_capacity(capacity)),
186        }
187    }
188    /// Returns the 'd' of the d-ary heap.
189    /// In other words, it represents the maximum number of children that each node on the heap can have.
190    pub const fn d() -> usize {
191        D
192    }
193
194    // additional functionalities
195    /// Returns the nodes and keys currently in the queue as a slice;
196    /// not necessarily sorted.
197    ///
198    /// # Examples
199    ///
200    /// ```
201    /// use orx_priority_queue::*;
202    ///
203    /// let mut queue = QuaternaryHeapWithMap::default();
204    /// queue.push("x", 42);
205    /// queue.push("y", 7);
206    /// queue.push("z", 99);
207    ///
208    /// let slice = queue.as_slice();
209    ///
210    /// assert_eq!(3, slice.len());
211    /// assert!(slice.contains(&("x", 42)));
212    /// assert!(slice.contains(&("y", 7)));
213    /// assert!(slice.contains(&("z", 99)));
214    /// ```
215    pub fn as_slice(&self) -> &[(N, K)] {
216        self.heap.as_slice()
217    }
218}
219
220impl<N, K, const D: usize> PriorityQueue<N, K> for DaryHeapWithMap<N, K, D>
221where
222    N: Index,
223    K: PartialOrd + Clone,
224{
225    type NodeKey<'a>
226        = &'a (N, K)
227    where
228        Self: 'a,
229        N: 'a,
230        K: 'a;
231    type Iter<'a>
232        = core::slice::Iter<'a, (N, K)>
233    where
234        Self: 'a,
235        N: 'a,
236        K: 'a;
237
238    #[inline(always)]
239    fn len(&self) -> usize {
240        self.heap.len()
241    }
242
243    #[inline(always)]
244    fn capacity(&self) -> usize {
245        self.heap.capacity()
246    }
247
248    fn peek(&self) -> Option<&(N, K)> {
249        self.heap.peek()
250    }
251
252    fn clear(&mut self) {
253        self.heap.clear()
254    }
255
256    #[inline(always)]
257    fn pop(&mut self) -> Option<(N, K)> {
258        self.heap.pop()
259    }
260
261    #[inline(always)]
262    fn pop_node(&mut self) -> Option<N> {
263        self.heap.pop_node()
264    }
265
266    #[inline(always)]
267    fn pop_key(&mut self) -> Option<K> {
268        self.heap.pop_key()
269    }
270
271    #[inline(always)]
272    fn push(&mut self, node: N, key: K) {
273        self.heap.push(node, key)
274    }
275
276    #[inline(always)]
277    fn push_then_pop(&mut self, node: N, key: K) -> (N, K) {
278        self.heap.push_then_pop(node, key)
279    }
280
281    fn iter(&self) -> Self::Iter<'_> {
282        self.as_slice().iter()
283    }
284}
285impl<N, K, const D: usize> PriorityQueueDecKey<N, K> for DaryHeapWithMap<N, K, D>
286where
287    N: Index,
288    K: PartialOrd + Clone,
289{
290    #[inline(always)]
291    fn contains(&self, node: &N) -> bool {
292        self.heap.contains(node)
293    }
294
295    #[inline(always)]
296    fn key_of(&self, node: &N) -> Option<K> {
297        self.heap.key_of(node)
298    }
299
300    #[inline(always)]
301    fn decrease_key(&mut self, node: &N, decreased_key: K) {
302        self.heap.decrease_key(node, decreased_key)
303    }
304
305    #[inline(always)]
306    fn update_key(&mut self, node: &N, new_key: K) -> ResUpdateKey {
307        self.heap.update_key(node, new_key)
308    }
309
310    #[inline(always)]
311    fn remove(&mut self, node: &N) -> K {
312        self.heap.remove(node)
313    }
314}
orx_priority_queue/dary/daryheap_map.rs

orx_priority_queue/dary/
daryheap_map.rs
