1use super::{Comparator, EmptyAct, MonoidAct, Unital, comparator::Less};
2use std::{
3 cmp::Ordering,
4 fmt::{self, Debug, Formatter},
5 iter::FusedIterator,
6 mem::{replace, swap},
7 ops::{Deref, DerefMut},
8};
9
10#[derive(Clone)]
11struct Node<T, A>
12where
13 A: MonoidAct<Key = T, Act: PartialEq>,
14{
15 value: T,
16 first_child: Option<Box<Node<T, A>>>,
17 next_sibling: Option<Box<Node<T, A>>>,
18 lazy: A::Act,
19}
20
21impl<T, A> Node<T, A>
22where
23 A: MonoidAct<Key = T, Act: PartialEq>,
24{
25 fn new(value: T) -> Self {
26 Self {
27 value,
28 first_child: None,
29 next_sibling: None,
30 lazy: A::unit(),
31 }
32 }
33
34 fn apply(&mut self, act: &A::Act) {
35 A::act_assign(&mut self.value, act);
36 A::operate_assign(&mut self.lazy, act);
37 }
38
39 fn propagate(&mut self) {
40 if !<A::ActMonoid as Unital>::is_unit(&self.lazy) {
41 let act = replace(&mut self.lazy, A::unit());
42 if let Some(node) = self.first_child.as_mut() {
43 node.apply(&act);
44 }
45 if let Some(node) = self.next_sibling.as_mut() {
46 node.apply(&act);
47 }
48 }
49 }
50}
51
52impl<T, A> Debug for Node<T, A>
53where
54 T: Debug,
55 A: MonoidAct<Key = T, Act: PartialEq + Debug>,
56{
57 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
58 f.debug_struct("Node")
59 .field("value", &self.value)
60 .field("first_child", &self.first_child)
61 .field("next_sibling", &self.next_sibling)
62 .field("lazy", &self.lazy)
63 .finish()
64 }
65}
66
67#[derive(Clone)]
68pub struct PairingHeap<T, C = Less, A = EmptyAct<T>>
69where
70 A: MonoidAct<Key = T, Act: PartialEq>,
71{
72 root: Option<Box<Node<T, A>>>,
73 len: usize,
74 cmp: C,
75}
76
77impl<T, C, A> PairingHeap<T, C, A>
78where
79 C: Comparator<T>,
80 A: MonoidAct<Key = T, Act: PartialEq>,
81{
82 pub fn with_comparator(cmp: C) -> Self {
83 Self {
84 root: None,
85 len: 0,
86 cmp,
87 }
88 }
89
90 pub fn len(&self) -> usize {
91 self.len
92 }
93
94 pub fn is_empty(&self) -> bool {
95 self.len == 0
96 }
97
98 pub fn peek(&self) -> Option<&T> {
99 self.root.as_ref().map(|node| &node.value)
100 }
101
102 pub fn push(&mut self, value: T) {
103 let node = Box::new(Node::new(value));
104 let root = self.root.take();
105 self.root = self.merge_option(root, Some(node));
106 self.len += 1;
107 }
108
109 pub fn append(&mut self, other: &mut Self) {
110 if other.is_empty() {
111 return;
112 }
113
114 let left = self.root.take();
115 self.root = self.merge_option(left, other.root.take());
116 self.len += other.len;
117 other.len = 0;
118 }
119
120 pub fn pop(&mut self) -> Option<T> {
121 self.root.take().map(|mut root| {
122 self.len -= 1;
123 root.propagate();
124 let children = root.first_child.take();
125 self.root = self.merge_pairs(children);
126 root.value
127 })
128 }
129
130 pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, C, A>> {
131 let mut root = self.root.take()?;
132 root.propagate();
133 let children = root.first_child.take();
134 debug_assert!(root.next_sibling.is_none());
135 root.next_sibling = None;
136 self.root = self.merge_pairs(children);
137 Some(PeekMut {
138 heap: self,
139 node: Some(root),
140 })
141 }
142
143 pub fn clear(&mut self) {
144 self.root = None;
145 self.len = 0;
146 }
147
148 pub fn apply_all(&mut self, act: A::Act) {
149 if let Some(root) = self.root.as_mut() {
150 root.apply(&act);
151 }
152 }
153
154 pub fn into_sorted_vec(mut self) -> Vec<T> {
155 let mut result = Vec::with_capacity(self.len);
156 while let Some(value) = self.pop() {
157 result.push(value);
158 }
159 result
160 }
161
162 fn merge_option(
163 &mut self,
164 a: Option<Box<Node<T, A>>>,
165 b: Option<Box<Node<T, A>>>,
166 ) -> Option<Box<Node<T, A>>> {
167 match (a, b) {
168 (None, None) => None,
169 (Some(node), None) | (None, Some(node)) => Some(node),
170 (Some(mut a), Some(mut b)) => {
171 a.propagate();
172 b.propagate();
173 if self.cmp.compare(&a.value, &b.value) == Ordering::Greater {
174 swap(&mut a, &mut b);
175 }
176 b.next_sibling = a.first_child.take();
177 a.first_child = Some(b);
178 Some(a)
179 }
180 }
181 }
182
183 fn merge_pairs(&mut self, mut head: Option<Box<Node<T, A>>>) -> Option<Box<Node<T, A>>> {
184 let mut pairs: Vec<Box<Node<T, A>>> = Vec::new();
185 while let Some(mut first) = head {
186 first.propagate();
187 let next = first.next_sibling.take();
188 if let Some(mut second) = next {
189 second.propagate();
190 head = second.next_sibling.take();
191 pairs.push(self.merge_option(Some(first), Some(second)).unwrap());
192 } else {
193 pairs.push(first);
194 break;
195 }
196 }
197
198 let mut result = None;
199 while let Some(node) = pairs.pop() {
200 result = self.merge_option(Some(node), result);
201 }
202 result
203 }
204}
205
206impl<T, C, A> Default for PairingHeap<T, C, A>
207where
208 C: Comparator<T> + Default,
209 A: MonoidAct<Key = T, Act: PartialEq>,
210{
211 fn default() -> Self {
212 Self::with_comparator(C::default())
213 }
214}
215
216impl<T, A> PairingHeap<T, Less, A>
217where
218 T: Ord,
219 A: MonoidAct<Key = T, Act: PartialEq>,
220{
221 pub fn new() -> Self {
222 Self::default()
223 }
224}
225
226impl<T, C, A> Debug for PairingHeap<T, C, A>
227where
228 T: Debug,
229 C: Debug + Comparator<T>,
230 A: MonoidAct<Key = T, Act: PartialEq + Debug>,
231{
232 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
233 f.debug_struct("PairingHeap")
234 .field("len", &self.len)
235 .field("root", &self.root)
236 .field("cmp", &self.cmp)
237 .finish()
238 }
239}
240
241impl<T, C, A> Extend<T> for PairingHeap<T, C, A>
242where
243 C: Comparator<T>,
244 A: MonoidAct<Key = T, Act: PartialEq>,
245{
246 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
247 for value in iter {
248 self.push(value);
249 }
250 }
251}
252
253impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>
254where
255 C: Comparator<T> + Default,
256 A: MonoidAct<Key = T, Act: PartialEq>,
257{
258 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
259 let mut heap = Self::default();
260 heap.extend(iter);
261 heap
262 }
263}
264
265pub struct PeekMut<'a, T, C = Less, A = EmptyAct<T>>
266where
267 C: Comparator<T>,
268 A: MonoidAct<Key = T, Act: PartialEq>,
269{
270 heap: &'a mut PairingHeap<T, C, A>,
271 node: Option<Box<Node<T, A>>>,
272}
273
274impl<'a, T, C, A> PeekMut<'a, T, C, A>
275where
276 C: Comparator<T>,
277 A: MonoidAct<Key = T, Act: PartialEq>,
278{
279 pub fn pop(mut this: Self) -> T {
280 this.heap.len -= 1;
281 let node = this.node.take().expect("PeekMut already consumed");
282 let Node { value, .. } = *node;
283 value
284 }
285}
286
287impl<'a, T, C, A> Deref for PeekMut<'a, T, C, A>
288where
289 C: Comparator<T>,
290 A: MonoidAct<Key = T, Act: PartialEq>,
291{
292 type Target = T;
293
294 fn deref(&self) -> &Self::Target {
295 &self.node.as_ref().expect("PeekMut already consumed").value
296 }
297}
298
299impl<'a, T, C, A> DerefMut for PeekMut<'a, T, C, A>
300where
301 C: Comparator<T>,
302 A: MonoidAct<Key = T, Act: PartialEq>,
303{
304 fn deref_mut(&mut self) -> &mut Self::Target {
305 &mut self.node.as_mut().expect("PeekMut already consumed").value
306 }
307}
308
309impl<'a, T, C, A> Drop for PeekMut<'a, T, C, A>
310where
311 C: Comparator<T>,
312 A: MonoidAct<Key = T, Act: PartialEq>,
313{
314 fn drop(&mut self) {
315 if let Some(mut node) = self.node.take() {
316 debug_assert!(node.next_sibling.is_none());
317 let root = self.heap.root.take();
318 node.first_child = None;
319 self.heap.root = self.heap.merge_option(root, Some(node));
320 }
321 }
322}
323
324pub struct IntoIter<T, C = Less, A = EmptyAct<T>>
325where
326 C: Comparator<T>,
327 A: MonoidAct<Key = T, Act: PartialEq>,
328{
329 heap: PairingHeap<T, C, A>,
330}
331
332impl<T, C, A> IntoIter<T, C, A>
333where
334 C: Comparator<T>,
335 A: MonoidAct<Key = T, Act: PartialEq>,
336{
337 fn new(heap: PairingHeap<T, C, A>) -> Self {
338 Self { heap }
339 }
340}
341
342impl<T, C, A> Iterator for IntoIter<T, C, A>
343where
344 C: Comparator<T>,
345 A: MonoidAct<Key = T, Act: PartialEq>,
346{
347 type Item = T;
348
349 fn next(&mut self) -> Option<Self::Item> {
350 self.heap.pop()
351 }
352
353 fn size_hint(&self) -> (usize, Option<usize>) {
354 let len = self.heap.len();
355 (len, Some(len))
356 }
357}
358
359impl<T, C, A> ExactSizeIterator for IntoIter<T, C, A>
360where
361 C: Comparator<T>,
362 A: MonoidAct<Key = T, Act: PartialEq>,
363{
364 fn len(&self) -> usize {
365 self.heap.len()
366 }
367}
368
369impl<T, C, A> FusedIterator for IntoIter<T, C, A>
370where
371 C: Comparator<T>,
372 A: MonoidAct<Key = T, Act: PartialEq>,
373{
374}
375
376impl<T, C, A> IntoIterator for PairingHeap<T, C, A>
377where
378 C: Comparator<T>,
379 A: MonoidAct<Key = T, Act: PartialEq>,
380{
381 type Item = T;
382 type IntoIter = IntoIter<T, C, A>;
383
384 fn into_iter(self) -> Self::IntoIter {
385 IntoIter::new(self)
386 }
387}
388
389#[cfg(test)]
390mod tests {
391 use super::*;
392 use crate::{
393 algebra::{AdditiveOperation, FlattenAct},
394 tools::{Xorshift, comparator::Greater},
395 };
396 use std::{cmp::Reverse, collections::BinaryHeap};
397
398 #[test]
399 fn test_min_heap() {
400 let mut heap = PairingHeap::<i32>::default();
401 assert!(heap.is_empty());
402 heap.push(3);
403 heap.push(1);
404 heap.push(4);
405 heap.push(2);
406 assert_eq!(heap.len(), 4);
407 assert_eq!(heap.peek(), Some(&1));
408 assert_eq!(heap.pop(), Some(1));
409 assert_eq!(heap.pop(), Some(2));
410 assert_eq!(heap.pop(), Some(3));
411 assert_eq!(heap.pop(), Some(4));
412 assert!(heap.is_empty());
413 }
414
415 #[test]
416 fn test_max_heap() {
417 let mut heap = PairingHeap::<i32, Greater>::with_comparator(Greater);
418 heap.extend([3, 1, 4, 2]);
419 assert_eq!(heap.peek(), Some(&4));
420 assert_eq!(heap.pop(), Some(4));
421 assert_eq!(heap.pop(), Some(3));
422 assert_eq!(heap.pop(), Some(2));
423 assert_eq!(heap.pop(), Some(1));
424 assert!(heap.is_empty());
425 }
426
427 #[test]
428 fn test_against_binary_heap() {
429 let mut rng = Xorshift::default();
430 for _ in 0..200 {
431 type Heap = PairingHeap<i64, Less, FlattenAct<AdditiveOperation<i64>>>;
432 let mut heap = Heap::default();
433 let mut reference = BinaryHeap::new();
434 let mut heap_offset = 0i64;
435 let mut other = Heap::default();
436 let mut reference_other = BinaryHeap::new();
437 let mut other_offset = 0i64;
438 for _ in 0..2000 {
439 match rng.rand(9) {
440 0 => {
441 let value: i64 = rng.random(-1_000_000..=1_000_000);
442 heap.push(value);
443 reference.push(Reverse(value - heap_offset));
444 }
445 1 => {
446 assert_eq!(
447 heap.pop(),
448 reference.pop().map(|Reverse(x)| x + heap_offset)
449 );
450 }
451 2 => {
452 let value: i64 = rng.random(-1_000_000..=1_000_000);
453 other.push(value);
454 reference_other.push(Reverse(value - other_offset));
455 }
456 3 => {
457 heap.append(&mut other);
458 while let Some(Reverse(value)) = reference_other.pop() {
459 reference.push(Reverse(value + other_offset - heap_offset));
460 }
461 }
462 4 => {
463 if let Some(mut guard) = heap.peek_mut() {
464 let new_value: i64 = rng.random(-1_000_000..=1_000_000);
465 {
466 let mut reference_guard = reference
467 .peek_mut()
468 .expect("reference heap empty while pairing heap not");
469 reference_guard.0 = new_value - heap_offset;
470 }
471 *guard = new_value;
472 } else {
473 assert!(reference.is_empty());
474 }
475 }
476 5 => {
477 if let Some(mut guard) = other.peek_mut() {
478 let new_value: i64 = rng.random(-1_000_000..=1_000_000);
479 {
480 let mut reference_guard = reference_other
481 .peek_mut()
482 .expect("reference heap empty while pairing heap not");
483 reference_guard.0 = new_value - other_offset;
484 }
485 *guard = new_value;
486 } else {
487 assert!(reference_other.is_empty());
488 }
489 }
490 6 => {
491 let add: i64 = rng.random(-1_000..=1_000);
492 heap.apply_all(add);
493 if !reference.is_empty() {
494 heap_offset += add;
495 }
496 }
497 7 => {
498 let add: i64 = rng.random(-1_000..=1_000);
499 other.apply_all(add);
500 if !reference_other.is_empty() {
501 other_offset += add;
502 }
503 }
504 _ => {
505 assert_eq!(
506 other.pop(),
507 reference_other.pop().map(|Reverse(x)| x + other_offset)
508 );
509 }
510 }
511 assert_eq!(
512 heap.peek().copied(),
513 reference.peek().map(|x| x.0 + heap_offset)
514 );
515 assert_eq!(
516 other.peek().copied(),
517 reference_other.peek().map(|x| x.0 + other_offset)
518 );
519 assert_eq!(heap.len(), reference.len());
520 assert_eq!(other.len(), reference_other.len());
521 }
522 heap.append(&mut other);
523 while let Some(Reverse(value)) = reference_other.pop() {
524 reference.push(Reverse(value + other_offset - heap_offset));
525 }
526 while let Some(Reverse(value)) = reference.pop() {
527 assert_eq!(heap.pop(), Some(value + heap_offset));
528 }
529 assert!(heap.is_empty());
530 assert!(other.is_empty());
531 assert!(reference.is_empty());
532 assert!(reference_other.is_empty());
533 }
534 }
535}