orx_priority_queue/dary/
daryheap_map.rs

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

orx_priority_queue/dary/
daryheap_map.rs
