Skip to content

Instantly share code, notes, and snippets.

@SchrodingerZhu

SchrodingerZhu/gist:bbc983eac54da18f0869b07a2d8c61a6

Created April 4, 2023 03:15
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save SchrodingerZhu/bbc983eac54da18f0869b07a2d8c61a6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save SchrodingerZhu/bbc983eac54da18f0869b07a2d8c61a6 to your computer and use it in GitHub Desktop.
Download ZIP
Pairing Heap
Raw
gistfile1.rs
#![feature(core_intrinsics)]
use std::intrinsics::likely;
use std::marker::PhantomData;
use std::ptr::NonNull;
use std::rc::{Rc, Weak};
struct Node<T> {
next: NonNull<Self>,
prev: NonNull<Self>,
children: Option<NonNull<Self>>,
parent: Option<NonNull<Self>>,
data: T,
alive: Rc<()>,
}
pub struct DecHeap<T> {
root: Option<NonNull<Node<T>>>,
}
impl<T> Node<T> {
unsafe fn destroy(node: NonNull<Self>) {
let mut cursor = node;
loop {
if let Some(child) = cursor.as_ref().children {
Self::destroy(child);
}
cursor = cursor.as_ref().next;
Self::deallocate(cursor);
if cursor == node {
break;
}
}
}
unsafe fn remove_from_list(&mut self) -> Option<NonNull<Self>> {
let result = self.next;
self.next.as_mut().prev = self.prev;
self.prev.as_mut().next = self.next;
self.prev = self.into();
self.next = self.into();
if result == self.next {
None
} else {
Some(result)
}
}
unsafe fn push_to_front(&mut self, list: Option<NonNull<Self>>) -> NonNull<Self> {
if let Some(head) = list {
self.next = head;
self.prev = head.as_ref().prev;
self.next.as_mut().prev = self.into();
self.prev.as_mut().next = self.into();
}
self.into()
}
unsafe fn deallocate(data: NonNull<Self>) -> T {
let memory = Box::from_raw(data.as_ptr());
memory.data
}
unsafe fn allocate(data: T) -> NonNull<Self> {
let mut result = NonNull::from(Box::leak(Box::new(Node {
next: NonNull::dangling(),
prev: NonNull::dangling(),
children: None,
parent: None,
alive: Rc::new(()),
data,
})));
result.as_mut().next = result;
result.as_mut().prev = result;
result
}
}
impl<T> Node<T> where T: Ord {
unsafe fn merge(h1: Option<NonNull<Self>>, mut h2: NonNull<Self>) -> NonNull<Self> {
match h1 {
None => h2,
Some(mut h1) => {
if h2.as_ref().data < h1.as_ref().data {
std::mem::swap(&mut h1, &mut h2);
}
h1.as_mut().children = Some(h2.as_mut().push_to_front(h1.as_ref().children));
h1.as_mut().next = h1;
h1.as_mut().prev = h1;
h2.as_mut().parent = Some(h1);
h1
}
}
}
// handle must be alive
unsafe fn decrease(root: Option<NonNull<Self>>, mut handle: NonNull<Self>, data: T) -> Option<NonNull<Self>> {
handle.as_mut().data = data;
// check if the node is already the root
match handle.as_ref().parent {
None => root,
Some(mut parent) => {
let res = handle.as_mut().remove_from_list();
if parent.as_ref().children == Some(handle) {
parent.as_mut().children = res;
}
handle.as_mut().parent = None;
Some(Self::merge(root, handle))
}
}
}
}
pub struct Handle<'a, T> {
handle: NonNull<Node<T>>,
alive: Weak<()>,
ownership: PhantomData<&'a mut ()>,
}
impl<'a, T> Handle<'a, T> {
pub fn get(&self) -> Option<&'a T> {
if self.alive.strong_count() > 0 {
Some(unsafe { &self.handle.as_ref().data })
} else {
None
}
}
}
impl<T> DecHeap<T> where T: Ord {
pub fn new() -> Self {
DecHeap {
root: None,
}
}
pub fn push<'a>(&mut self, data: T) -> Handle<'a, T> {
unsafe {
let handle = Node::allocate(data);
self.root.replace(Node::merge(self.root, handle));
Handle {
handle,
alive: Rc::downgrade(&handle.as_ref().alive),
ownership: PhantomData::default(),
}
}
}
pub fn decrease_to(&mut self, handle: &Handle<T>, data: T) -> bool {
let valid =
likely(handle.alive.strong_count() != 0);
if !valid || !unsafe { handle.handle.as_ref().data >= data } {
false
} else {
self.root = unsafe { Node::decrease(self.root, handle.handle, data) };
true
}
}
pub fn top(&self) -> Option<&T> {
unsafe {
self.root.map(|x| &x.as_ref().data)
}
}
pub fn pop(&mut self) -> Option<T> {
match self.root {
None => None,
Some(mut root) => unsafe {
let mut list = None;
while let Some(mut x) = root.as_ref().children {
root.as_mut().children = x.as_mut().remove_from_list();
match root.as_ref().children {
Some(mut y) => {
root.as_mut().children = y.as_mut().remove_from_list();
let mut merged = Node::merge(Some(x), y);
list = Some(merged.as_mut().push_to_front(list));
}
None => {
list = Some(x.as_mut().push_to_front(list));
}
}
}
let mut new_root = None;
while let Some(mut x) = list {
list = x.as_mut().remove_from_list();
new_root.replace(Node::merge(new_root, x));
}
self.root = new_root;
Some(Node::deallocate(root))
}
}
}
}
impl<T> Drop for DecHeap<T> {
fn drop(&mut self) {
if let Some(heap) = self.root.take() {
unsafe { Node::destroy(heap); }
}
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn sequential_heap_sort() {
let limit = 10000;
let mut heap = DecHeap::new();
for i in (0..limit).rev() {
heap.push(i);
}
let mut result : Vec<i32> = Vec::new();
let expect : Vec<i32> = (0..limit).collect();
while let Some(i) = heap.pop() {
result.push(i);
}
assert_eq!(result, expect)
}
#[test]
fn decrement() {
let limit = 10000;
let mut heap = DecHeap::new();
let mut handles = Vec::new();
for i in (0..limit).rev() {
handles.push(heap.push(i));
}
for i in handles.iter() {
heap.decrease_to(i, i.get().unwrap() - 50);
}
let mut result : Vec<i32> = Vec::new();
let expect : Vec<i32> = (-50..limit-50).collect();
while let Some(i) = heap.pop() {
result.push(i);
}
assert_eq!(result, expect)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment