fibonacci_heap/
lib.rs

1use std::ptr::NonNull;
2
3type RootLink<T> = NonNull<RootNode<T>>;
4type Link<T> = NonNull<Node<T>>;
5
6pub struct FibonacciHeap<T> {
7    len: usize,
8    max: Option<RootLink<T>>,
9    ends: Option<(RootLink<T>, RootLink<T>)>,
10}
11
12struct RootNode<T> {
13    root: Link<T>,
14    next_root: Option<RootLink<T>>,
15}
16
17struct Node<T> {
18    val: T,
19    parent: Option<Link<T>>,
20    // (neighbor.0 == this) implies |sibling| == 1
21    // (neighbor.0 == neighbor.1) implies |sibling| <= 2
22    neighbor: (Link<T>, Link<T>),
23    any_child: Option<Link<T>>,
24    order: usize,
25    cut: bool,
26    root: Option<RootLink<T>>,
27}
28
29pub struct NodeRef<T> {
30    node: Link<T>,
31}
32
33struct Bucket<T> {
34    bucket: Vec<Option<RootLink<T>>>,
35}
36
37impl<T: Ord> FibonacciHeap<T> {
38    pub fn new() -> Self { Self { len: 0, max: None, ends: None } }
39
40    pub fn len(&self) -> usize { self.len }
41    pub fn is_empty(&self) -> bool { self.len == 0 }
42
43    pub fn push(&mut self, elt: T) -> NodeRef<T> {
44        self.len += 1;
45        let new = Node::new(elt);
46        self.push_root(RootNode::new(new));
47        NodeRef::new(new)
48    }
49
50    pub fn pop(&mut self) -> Option<T> {
51        let root = self.max.take()?;
52        self.len -= 1;
53        while let Some(child) =
54            unsafe { Node::pop_child((*root.as_ptr()).root) }
55        {
56            // we clean the parent-pointer of child later.
57            self.push_root(RootNode::new(child));
58        }
59        // if `root` has no child, `self.max.is_none() && self.ends.is_some()`
60        // may hold at this point.
61        self.coalesce();
62        Some(RootNode::take(root))
63    }
64
65    pub fn meld(&mut self, mut other: Self) {
66        self.len += other.len;
67        if let Some((other_first, other_last)) = other.ends.take() {
68            if let Some((first, last)) = self.ends {
69                RootNode::append(last, other_first);
70                self.ends = Some((first, other_last));
71            } else {
72                self.ends = other.ends;
73            }
74        }
75        if let Some(other_max) = other.max.take() {
76            self.push_root(other_max);
77        }
78    }
79
80    pub unsafe fn urge(&mut self, handle: NodeRef<T>, new: T) -> bool {
81        let node = handle.node;
82        unsafe {
83            if (*node.as_ptr()).val >= new {
84                return false;
85            }
86
87            (*node.as_ptr()).val = new;
88            if !Node::is_heapified(node) {
89                let mut node = Some(node);
90                while let Some(cur) = node {
91                    node = Node::orphan(cur);
92                    self.push_root(RootNode::new(cur));
93                }
94            }
95
96            if let (Some(old), Some(new)) = (self.max, (*node.as_ptr()).root) {
97                RootNode::challenge(old, new);
98            }
99        }
100        true
101    }
102
103    fn push_root(&mut self, new: RootLink<T>) {
104        if let Some(old) = self.max {
105            RootNode::challenge(old, new);
106            if let Some((first, last)) = self.ends {
107                RootNode::append(last, new);
108                self.ends = Some((first, new));
109            } else {
110                self.ends = Some((new, new));
111            }
112        } else {
113            self.max = Some(new);
114        }
115    }
116
117    fn coalesce(&mut self) {
118        let mut bucket = Bucket::new();
119
120        if let Some(max) = self.max.take() {
121            RootNode::isolate(max);
122            bucket.push(max);
123        }
124        if let Some((first, _)) = self.ends.take() {
125            let mut root = Some(first);
126            while let Some(cur) = root {
127                unsafe {
128                    let ptr = cur.as_ptr();
129                    root = (*ptr).next_root;
130                }
131                RootNode::isolate(cur);
132                bucket.push(cur);
133            }
134        }
135
136        for root in bucket.take() {
137            self.push_root(root);
138        }
139    }
140}
141
142impl<T> Drop for FibonacciHeap<T> {
143    fn drop(&mut self) {
144        if let Some(max) = self.max.take() {
145            RootNode::drop(max);
146        }
147        if let Some((first, _)) = self.ends.take() {
148            let mut cur = Some(first);
149            while let Some(root) = cur {
150                cur = unsafe { (*root.as_ptr()).next_root };
151                RootNode::drop(root);
152            }
153        }
154    }
155}
156
157impl<T> RootNode<T> {
158    pub fn new(node: Link<T>) -> RootLink<T> {
159        let root = Self { root: node, next_root: None };
160        let root = NonNull::from(Box::leak(Box::new(root)));
161        unsafe { (*node.as_ptr()).root = Some(root) };
162        root
163    }
164
165    pub fn append(fst: RootLink<T>, snd: RootLink<T>) {
166        unsafe {
167            debug_assert!((*fst.as_ptr()).next_root.is_none());
168            (*fst.as_ptr()).next_root = Some(snd);
169        }
170    }
171
172    pub fn challenge(old: RootLink<T>, new: RootLink<T>)
173    where
174        T: Ord,
175    {
176        if old == new {
177            return;
178        }
179        if Self::val(old) < Self::val(new) {
180            let old_ptr = old.as_ptr();
181            let new_ptr = new.as_ptr();
182            unsafe {
183                debug_assert!((*(*old_ptr).root.as_ptr()).parent.is_none());
184                debug_assert!((*(*new_ptr).root.as_ptr()).parent.is_none());
185                std::mem::swap(
186                    &mut (*(*old_ptr).root.as_ptr()).root,
187                    &mut (*(*new_ptr).root.as_ptr()).root,
188                );
189                std::mem::swap(&mut (*old_ptr).root, &mut (*new_ptr).root);
190            }
191        }
192    }
193
194    fn val<'a>(this: RootLink<T>) -> &'a T {
195        unsafe { &(*(*this.as_ptr()).root.as_ptr()).val }
196    }
197    fn order(this: RootLink<T>) -> usize {
198        unsafe { (*(*this.as_ptr()).root.as_ptr()).order }
199    }
200    fn is_isolated_root(this: RootLink<T>) -> bool {
201        let ptr = this.as_ptr();
202        unsafe {
203            (*ptr).next_root.is_none()
204                && (*(*ptr).root.as_ptr()).parent.is_none()
205                && (*ptr).root == (*(*ptr).root.as_ptr()).neighbor.0
206        }
207    }
208
209    fn isolate(this: RootLink<T>) {
210        let ptr = this.as_ptr();
211        unsafe {
212            (*ptr).next_root.take();
213            (*(*ptr).root.as_ptr()).parent.take();
214            Node::init_siblings((*ptr).root);
215        }
216    }
217
218    fn fuse(par: RootLink<T>, child: RootLink<T>) -> RootLink<T>
219    where
220        T: Ord,
221    {
222        Self::precheck_fuse(par, child);
223        let (greater, less) = if Self::val(par) > Self::val(child) {
224            (par, child)
225        } else {
226            (child, par)
227        };
228        unsafe {
229            Node::push_child((*greater.as_ptr()).root, (*less.as_ptr()).root);
230            drop(Box::from_raw(less.as_ptr()));
231            greater
232        }
233    }
234
235    fn precheck_fuse(par: RootLink<T>, child: RootLink<T>) {
236        debug_assert_eq!(Self::order(par), Self::order(child));
237        debug_assert!(Self::is_isolated_root(par));
238        debug_assert!(Self::is_isolated_root(child));
239    }
240
241    fn take(this: RootLink<T>) -> T {
242        let ptr = this.as_ptr();
243        let node = unsafe { Box::from_raw((*ptr).root.as_ptr()) };
244        let res = node.val;
245        unsafe { drop(Box::from_raw(ptr)) };
246        res
247    }
248}
249
250impl<T> RootNode<T> {
251    fn drop(this: RootLink<T>) {
252        unsafe {
253            Node::drop((*this.as_ptr()).root);
254            drop(Box::from_raw(this.as_ptr()));
255        }
256    }
257}
258
259impl<T> Node<T> {
260    pub fn new(elt: T) -> Link<T> {
261        let node = Self {
262            val: elt,
263            parent: None,
264            neighbor: (NonNull::dangling(), NonNull::dangling()),
265            any_child: None,
266            order: 0,
267            cut: false,
268            root: None,
269        };
270        let ptr = NonNull::from(Box::leak(Box::new(node)));
271        Node::init_siblings(ptr);
272        ptr
273    }
274
275    pub fn push_child(this: Link<T>, child: Link<T>) {
276        debug_assert!(Node::is_root(this));
277        let par = this.as_ptr();
278        unsafe {
279            (*par).order += 1;
280            if let Some(old_child) = (*par).any_child {
281                Node::push_sibling(old_child, child);
282            } else {
283                Node::init_siblings(child);
284                (*par).any_child = Some(child);
285            }
286            (*child.as_ptr()).parent = Some(this);
287            (*child.as_ptr()).root.take();
288        }
289    }
290
291    pub fn pop_child(this: Link<T>) -> Option<Link<T>> {
292        let par = this.as_ptr();
293        unsafe {
294            let child = (*par).any_child.take()?;
295            (*par).order -= 1;
296            if (*par).parent.is_some() {
297                // root nodes does not use this flag.
298                (*par).cut = true;
299            }
300            (*child.as_ptr()).parent.take();
301            let (prev, next) = (*child.as_ptr()).neighbor;
302            if child == prev {
303                // that is the last child; nothing is to be done.
304            } else {
305                // `next` may be equal to `prev`, but no special care is needed.
306                (*par).any_child = Some(next);
307                (*prev.as_ptr()).neighbor.1 = next;
308                (*next.as_ptr()).neighbor.0 = prev;
309            }
310            Node::init_siblings(child);
311            Some(child)
312        }
313    }
314
315    pub fn init_siblings(this: Link<T>) {
316        unsafe { (*this.as_ptr()).neighbor = (this, this) };
317    }
318    pub fn push_sibling(old: Link<T>, new: Link<T>) {
319        unsafe {
320            let neighbor = (*old.as_ptr()).neighbor;
321            if old == neighbor.0 {
322                // siblings == {old}
323                (*new.as_ptr()).neighbor = (old, old);
324                (*old.as_ptr()).neighbor = (new, new);
325            } else {
326                let next = neighbor.1;
327                (*old.as_ptr()).neighbor.1 = new;
328                (*next.as_ptr()).neighbor.0 = new;
329                (*new.as_ptr()).neighbor = (old, next);
330            }
331        }
332    }
333
334    fn is_root(this: Link<T>) -> bool {
335        unsafe {
336            debug_assert_eq!(
337                (*this.as_ptr()).root.is_some(),
338                (*this.as_ptr()).parent.is_none(),
339            );
340            (*this.as_ptr()).parent.is_none()
341        }
342    }
343
344    pub fn orphan(this: Link<T>) -> Option<Link<T>> {
345        let ptr = this.as_ptr();
346        unsafe {
347            (*ptr).cut = false;
348            let par = (*ptr).parent.take()?;
349
350            let (prev, next) = (*ptr).neighbor;
351            if this == prev {
352                // the parent has no child now.
353                (*par.as_ptr()).any_child.take();
354            } else {
355                (*prev.as_ptr()).neighbor.1 = next;
356                (*next.as_ptr()).neighbor.0 = prev;
357                if this == (*par.as_ptr()).any_child.unwrap() {
358                    // `next` is now the representative child.
359                    (*par.as_ptr()).any_child = Some(next);
360                }
361            }
362
363            (*par.as_ptr()).order -= 1;
364            if Node::is_root(par) {
365                None
366            } else if (*par.as_ptr()).cut {
367                // cascading orphan is occurred.
368                Some(par)
369            } else {
370                (*par.as_ptr()).cut = true;
371                None
372            }
373        }
374    }
375
376    fn is_heapified(child: Link<T>) -> bool
377    where
378        T: Ord,
379    {
380        unsafe {
381            match (*child.as_ptr()).parent {
382                Some(par) => (*par.as_ptr()).val >= (*child.as_ptr()).val,
383                _ => true,
384            }
385        }
386    }
387}
388
389impl<T> Node<T> {
390    fn drop(node: Link<T>) {
391        while let Some(child) = Node::pop_child(node) {
392            Self::drop(child);
393        }
394        unsafe { drop(Box::from_raw(node.as_ptr())) };
395    }
396}
397
398impl<T> NodeRef<T> {
399    fn new(node: Link<T>) -> Self { Self { node } }
400}
401
402impl<T> Copy for NodeRef<T> {}
403impl<T> Clone for NodeRef<T> {
404    fn clone(&self) -> Self { *self }
405}
406
407impl<T: Ord> Bucket<T> {
408    pub fn new() -> Self { Self { bucket: vec![] } }
409    pub fn push(&mut self, root: RootLink<T>) {
410        let order = RootNode::order(root);
411        if order >= self.bucket.len() {
412            self.bucket.resize(order + 1, None)
413        }
414        if let Some(old) = self.bucket[order].take() {
415            self.push(RootNode::fuse(root, old));
416        } else {
417            self.bucket[order] = Some(root);
418        }
419    }
420    pub fn take(self) -> impl Iterator<Item = RootLink<T>> {
421        self.bucket.into_iter().filter_map(std::convert::identity)
422    }
423}
424
425#[test]
426fn nonnull_eq() {
427    use std::ptr::NonNull;
428
429    #[allow(unused)]
430    struct A(i32);
431
432    let a1 = NonNull::from(Box::leak(Box::new(A(0))));
433    let a2 = a1;
434    let b = NonNull::from(Box::leak(Box::new(A(0))));
435    assert_ne!(a1, b);
436    assert_eq!(a1, a2);
437
438    unsafe { *a1.as_ptr() = A(1) };
439    assert_eq!(a1, a2);
440
441    unsafe { *a2.as_ptr() = A(2) };
442    assert_eq!(a1, a2);
443
444    unsafe {
445        drop(Box::from_raw(a1.as_ptr()));
446        drop(Box::from_raw(b.as_ptr()));
447    }
448}
449
450#[test]
451fn memleak() {
452    use std::ptr::NonNull;
453
454    #[allow(unused)]
455    struct A(i32);
456
457    let a = NonNull::from(Box::leak(Box::new(A(0))));
458    let a_box = unsafe { Box::from_raw(a.as_ptr()) };
459    assert_eq!(a_box.0, 0);
460}
461
462#[test]
463fn nested_leak() {
464    use std::ptr::NonNull;
465
466    struct A(i32);
467    #[allow(unused)]
468    struct B(NonNull<A>);
469    let a = NonNull::from(Box::leak(Box::new(A(100))));
470    let b = NonNull::from(Box::leak(Box::new(B(a))));
471    let a0 = unsafe {
472        drop(Box::from_raw(b.as_ptr()));
473        Box::from_raw(a.as_ptr()).0
474    };
475    assert_eq!(a0, 100);
476}
477
478#[test]
479fn mutual_ref() {
480    use std::ptr::NonNull;
481
482    struct A(NonNull<A>);
483    let a = NonNull::from(Box::leak(Box::new(A(NonNull::dangling()))));
484    let b = NonNull::from(Box::leak(Box::new(A(NonNull::dangling()))));
485    unsafe {
486        (*a.as_ptr()).0 = b;
487        (*b.as_ptr()).0 = a;
488        (*a.as_ptr()).0 = b;
489    };
490
491    unsafe {
492        drop(Box::from_raw(a.as_ptr()));
493        drop(Box::from_raw(b.as_ptr()));
494    }
495}
496
497#[cfg(test)]
498mod tests {
499    use super::*;
500
501    #[test]
502    fn single() {
503        let mut q = FibonacciHeap::new();
504        q.push(1);
505        q.push(2);
506        q.push(3);
507        q.pop();
508    }
509
510    #[test]
511    fn push_meld_pop() {
512        let mut q = FibonacciHeap::new();
513        assert!(q.is_empty());
514        q.push(1);
515        q.push(3);
516        q.push(4);
517        assert_eq!(q.len(), 3);
518
519        let mut r = FibonacciHeap::new();
520        r.push(0);
521        r.push(2);
522        q.meld(r);
523        assert_eq!(q.len(), 5);
524
525        let mut actual = vec![];
526        for i in (0..5).rev() {
527            actual.extend(q.pop());
528            assert_eq!(q.len(), i);
529        }
530        assert_eq!(actual, [4, 3, 2, 1, 0]);
531    }
532
533    #[test]
534    fn many_pushes() {
535        let mut q = FibonacciHeap::new();
536        let mut r = FibonacciHeap::new();
537        for i in 0..100 {
538            q.push(i);
539            r.push(i);
540            assert_eq!(q.len(), i + 1);
541        }
542        let mut res = vec![];
543        for i in (0..100).rev() {
544            res.extend(q.pop());
545            assert_eq!(q.len(), i);
546        }
547    }
548
549    #[test]
550    fn heap_sort() {
551        let n = 1 << 8;
552        let mut q = FibonacciHeap::new();
553        for i in (0..n).map(|i| (i >> 1) ^ i) {
554            q.push(i);
555        }
556        let actual = (0..n).map(|_| q.pop().unwrap());
557        assert!(actual.eq((0..n).rev()));
558    }
559
560    #[test]
561    fn urge() {
562        let mut q = FibonacciHeap::new();
563        q.push(1);
564        let x2 = q.push(2);
565        q.push(3);
566        unsafe { q.urge(x2, 20) };
567        let actual: Vec<_> = (0..q.len()).map(|_| q.pop().unwrap()).collect();
568        assert_eq!(actual, [20, 3, 1]);
569
570        let x2 = q.push(2);
571        let x1 = q.push(1);
572        let _x6 = q.push(6);
573        let x3 = q.push(3);
574        let x5 = q.push(5);
575        let _x4 = q.push(4);
576        let _x7 = q.push(7);
577        assert_eq!(q.pop(), Some(7));
578
579        unsafe { q.urge(x5, 500) };
580        assert_eq!(q.pop(), Some(500));
581
582        unsafe { q.urge(x1, 4) };
583        assert_eq!(q.pop(), Some(6));
584
585        unsafe { q.urge(x2, 1) };
586        assert_eq!(q.pop(), Some(4));
587
588        unsafe { q.urge(x3, 5) };
589        assert_eq!(q.pop(), Some(5));
590
591        unsafe { q.urge(x2, 10) };
592        assert_eq!(q.pop(), Some(10));
593
594        assert_eq!(q.pop(), Some(4));
595        assert!(q.is_empty());
596    }
597}
598
599// TODO: `heap.iter()` and `node.iter()` should be implemented.
fibonacci_heap/lib.rs

fibonacci_heap/
lib.rs
