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 = None;
185 while let Some(mut first) = head {
186 first.propagate();
187 let next = first.next_sibling.take();
188 let mut pair = if let Some(mut second) = next {
189 second.propagate();
190 head = second.next_sibling.take();
191 self.merge_option(Some(first), Some(second)).unwrap()
192 } else {
193 head = None;
194 first
195 };
196 pair.next_sibling = pairs;
197 pairs = Some(pair);
198 }
199
200 let mut result = None;
201 while let Some(mut node) = pairs {
202 pairs = node.next_sibling.take();
203 result = self.merge_option(Some(node), result);
204 }
205 result
206 }
207}
208
209impl<T, C, A> Default for PairingHeap<T, C, A>
210where
211 C: Comparator<T> + Default,
212 A: MonoidAct<Key = T, Act: PartialEq>,
213{
214 fn default() -> Self {
215 Self::with_comparator(C::default())
216 }
217}
218
219impl<T, A> PairingHeap<T, Less, A>
220where
221 T: Ord,
222 A: MonoidAct<Key = T, Act: PartialEq>,
223{
224 pub fn new() -> Self {
225 Self::default()
226 }
227}
228
229impl<T, C, A> Debug for PairingHeap<T, C, A>
230where
231 T: Debug,
232 C: Debug + Comparator<T>,
233 A: MonoidAct<Key = T, Act: PartialEq + Debug>,
234{
235 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
236 f.debug_struct("PairingHeap")
237 .field("len", &self.len)
238 .field("root", &self.root)
239 .field("cmp", &self.cmp)
240 .finish()
241 }
242}
243
244impl<T, C, A> Extend<T> for PairingHeap<T, C, A>
245where
246 C: Comparator<T>,
247 A: MonoidAct<Key = T, Act: PartialEq>,
248{
249 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
250 for value in iter {
251 self.push(value);
252 }
253 }
254}
255
256impl<T, C, A> FromIterator<T> for PairingHeap<T, C, A>
257where
258 C: Comparator<T> + Default,
259 A: MonoidAct<Key = T, Act: PartialEq>,
260{
261 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
262 let mut heap = Self::default();
263 heap.extend(iter);
264 heap
265 }
266}
267
268pub struct PeekMut<'a, T, C = Less, A = EmptyAct<T>>
269where
270 C: Comparator<T>,
271 A: MonoidAct<Key = T, Act: PartialEq>,
272{
273 heap: &'a mut PairingHeap<T, C, A>,
274 node: Option<Box<Node<T, A>>>,
275}
276
277impl<'a, T, C, A> PeekMut<'a, T, C, A>
278where
279 C: Comparator<T>,
280 A: MonoidAct<Key = T, Act: PartialEq>,
281{
282 pub fn pop(mut this: Self) -> T {
283 this.heap.len -= 1;
284 let node = this.node.take().expect("PeekMut already consumed");
285 let Node { value, .. } = *node;
286 value
287 }
288}
289
290impl<'a, T, C, A> Deref for PeekMut<'a, T, C, A>
291where
292 C: Comparator<T>,
293 A: MonoidAct<Key = T, Act: PartialEq>,
294{
295 type Target = T;
296
297 fn deref(&self) -> &Self::Target {
298 &self.node.as_ref().expect("PeekMut already consumed").value
299 }
300}
301
302impl<'a, T, C, A> DerefMut for PeekMut<'a, T, C, A>
303where
304 C: Comparator<T>,
305 A: MonoidAct<Key = T, Act: PartialEq>,
306{
307 fn deref_mut(&mut self) -> &mut Self::Target {
308 &mut self.node.as_mut().expect("PeekMut already consumed").value
309 }
310}
311
312impl<'a, T, C, A> Drop for PeekMut<'a, T, C, A>
313where
314 C: Comparator<T>,
315 A: MonoidAct<Key = T, Act: PartialEq>,
316{
317 fn drop(&mut self) {
318 if let Some(mut node) = self.node.take() {
319 debug_assert!(node.next_sibling.is_none());
320 let root = self.heap.root.take();
321 node.first_child = None;
322 self.heap.root = self.heap.merge_option(root, Some(node));
323 }
324 }
325}
326
327pub struct IntoIter<T, C = Less, A = EmptyAct<T>>
328where
329 C: Comparator<T>,
330 A: MonoidAct<Key = T, Act: PartialEq>,
331{
332 heap: PairingHeap<T, C, A>,
333}
334
335impl<T, C, A> IntoIter<T, C, A>
336where
337 C: Comparator<T>,
338 A: MonoidAct<Key = T, Act: PartialEq>,
339{
340 fn new(heap: PairingHeap<T, C, A>) -> Self {
341 Self { heap }
342 }
343}
344
345impl<T, C, A> Iterator for IntoIter<T, C, A>
346where
347 C: Comparator<T>,
348 A: MonoidAct<Key = T, Act: PartialEq>,
349{
350 type Item = T;
351
352 fn next(&mut self) -> Option<Self::Item> {
353 self.heap.pop()
354 }
355
356 fn size_hint(&self) -> (usize, Option<usize>) {
357 let len = self.heap.len();
358 (len, Some(len))
359 }
360}
361
362impl<T, C, A> ExactSizeIterator for IntoIter<T, C, A>
363where
364 C: Comparator<T>,
365 A: MonoidAct<Key = T, Act: PartialEq>,
366{
367 fn len(&self) -> usize {
368 self.heap.len()
369 }
370}
371
372impl<T, C, A> FusedIterator for IntoIter<T, C, A>
373where
374 C: Comparator<T>,
375 A: MonoidAct<Key = T, Act: PartialEq>,
376{
377}
378
379impl<T, C, A> IntoIterator for PairingHeap<T, C, A>
380where
381 C: Comparator<T>,
382 A: MonoidAct<Key = T, Act: PartialEq>,
383{
384 type Item = T;
385 type IntoIter = IntoIter<T, C, A>;
386
387 fn into_iter(self) -> Self::IntoIter {
388 IntoIter::new(self)
389 }
390}
391
392#[cfg(test)]
393mod tests {
394 use super::*;
395 use crate::{
396 algebra::{AdditiveOperation, FlattenAct},
397 tools::{Xorshift, comparator::Greater},
398 };
399 use std::{cmp::Reverse, collections::BinaryHeap};
400
401 #[test]
402 fn test_heap_order() {
403 let mut rng = Xorshift::default();
404 for _ in 0..100 {
405 let mut min_heap = PairingHeap::<i32>::default();
406 let mut max_heap: PairingHeap<i32, Greater> = PairingHeap::with_comparator(Greater);
407 let mut min_model = BinaryHeap::new();
408 let mut max_model = BinaryHeap::new();
409 for _ in 0..1000 {
410 if rng.random(0..3) == 0 {
411 assert_eq!(min_heap.pop(), min_model.pop().map(|Reverse(x)| x));
412 assert_eq!(max_heap.pop(), max_model.pop());
413 } else {
414 let x = rng.random(-100..=100);
415 min_heap.push(x);
416 max_heap.push(x);
417 min_model.push(Reverse(x));
418 max_model.push(x);
419 }
420 assert_eq!(min_heap.len(), min_model.len());
421 assert_eq!(max_heap.len(), max_model.len());
422 assert_eq!(min_heap.peek(), min_model.peek().map(|Reverse(x)| x));
423 assert_eq!(max_heap.peek(), max_model.peek());
424 }
425 assert_eq!(
426 min_heap.into_iter().collect::<Vec<_>>(),
427 min_model
428 .into_sorted_vec()
429 .into_iter()
430 .rev()
431 .map(|Reverse(x)| x)
432 .collect::<Vec<_>>()
433 );
434 assert_eq!(
435 max_heap.into_iter().collect::<Vec<_>>(),
436 max_model
437 .into_sorted_vec()
438 .into_iter()
439 .rev()
440 .collect::<Vec<_>>()
441 );
442 }
443 }
444
445 #[test]
446 fn test_against_binary_heap() {
447 let mut rng = Xorshift::default();
448 for _ in 0..200 {
449 type Heap = PairingHeap<i64, Less, FlattenAct<AdditiveOperation<i64>>>;
450 let mut heap = Heap::default();
451 let mut reference = BinaryHeap::new();
452 let mut heap_offset = 0i64;
453 let mut other = Heap::default();
454 let mut reference_other = BinaryHeap::new();
455 let mut other_offset = 0i64;
456 for _ in 0..2000 {
457 match rng.rand(9) {
458 0 => {
459 let value: i64 = rng.random(-1_000_000..=1_000_000);
460 heap.push(value);
461 reference.push(Reverse(value - heap_offset));
462 }
463 1 => {
464 assert_eq!(
465 heap.pop(),
466 reference.pop().map(|Reverse(x)| x + heap_offset)
467 );
468 }
469 2 => {
470 let value: i64 = rng.random(-1_000_000..=1_000_000);
471 other.push(value);
472 reference_other.push(Reverse(value - other_offset));
473 }
474 3 => {
475 heap.append(&mut other);
476 while let Some(Reverse(value)) = reference_other.pop() {
477 reference.push(Reverse(value + other_offset - heap_offset));
478 }
479 }
480 4 => {
481 if let Some(mut guard) = heap.peek_mut() {
482 let new_value: i64 = rng.random(-1_000_000..=1_000_000);
483 {
484 let mut reference_guard = reference
485 .peek_mut()
486 .expect("reference heap empty while pairing heap not");
487 reference_guard.0 = new_value - heap_offset;
488 }
489 *guard = new_value;
490 } else {
491 assert!(reference.is_empty());
492 }
493 }
494 5 => {
495 if let Some(mut guard) = other.peek_mut() {
496 let new_value: i64 = rng.random(-1_000_000..=1_000_000);
497 {
498 let mut reference_guard = reference_other
499 .peek_mut()
500 .expect("reference heap empty while pairing heap not");
501 reference_guard.0 = new_value - other_offset;
502 }
503 *guard = new_value;
504 } else {
505 assert!(reference_other.is_empty());
506 }
507 }
508 6 => {
509 let add: i64 = rng.random(-1_000..=1_000);
510 heap.apply_all(add);
511 if !reference.is_empty() {
512 heap_offset += add;
513 }
514 }
515 7 => {
516 let add: i64 = rng.random(-1_000..=1_000);
517 other.apply_all(add);
518 if !reference_other.is_empty() {
519 other_offset += add;
520 }
521 }
522 _ => {
523 assert_eq!(
524 other.pop(),
525 reference_other.pop().map(|Reverse(x)| x + other_offset)
526 );
527 }
528 }
529 assert_eq!(
530 heap.peek().copied(),
531 reference.peek().map(|x| x.0 + heap_offset)
532 );
533 assert_eq!(
534 other.peek().copied(),
535 reference_other.peek().map(|x| x.0 + other_offset)
536 );
537 assert_eq!(heap.len(), reference.len());
538 assert_eq!(other.len(), reference_other.len());
539 }
540 heap.append(&mut other);
541 while let Some(Reverse(value)) = reference_other.pop() {
542 reference.push(Reverse(value + other_offset - heap_offset));
543 }
544 while let Some(Reverse(value)) = reference.pop() {
545 assert_eq!(heap.pop(), Some(value + heap_offset));
546 }
547 assert!(heap.is_empty());
548 assert!(other.is_empty());
549 assert!(reference.is_empty());
550 assert!(reference_other.is_empty());
551 }
552 }
553}