orx_priority_queue/dary/
daryheap_index.rs

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

orx_priority_queue/dary/
daryheap_index.rs
