orx_priority_queue/dary/
daryheap_index.rs

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

orx_priority_queue/dary/
daryheap_index.rs
