Compiler Explorer

Source code

use std::ptr;

struct DListNode<T> {
    data: T,
    next: *mut DListNode<T>,
    prev: *mut DListNode<T>,
}

impl<T> DListNode<T> {
    fn new(data: T) -> Self {
        DListNode {
            data,
            next: ptr::null_mut(),
            prev: ptr::null_mut(),
        }
    }

// Initialize self-references after creation
    fn init_self_refs(&mut self) {
        let self_ptr = self as *mut DListNode<T>;
        self.next = self_ptr;
        self.prev = self_ptr;
    }

// Dancing Links delete
    unsafe fn delete(&mut self) {
        unsafe {
            (*self.prev).next = self.next;
            (*self.next).prev = self.prev;
        }
    }

// Dancing Links undelete
    unsafe fn undelete(&mut self) {
        unsafe {
            (*self.prev).next = self;
            (*self.next).prev = self;
        }
    }

// Insert new node after current one
    unsafe fn insert_after(&mut self, new_node: *mut DListNode<T>) {
        unsafe {
            (*new_node).next = self.next;
            (*new_node).prev = self;
            (*self.next).prev = new_node;
            self.next = new_node;
        }
    }

// Print list forward
    unsafe fn print_forward(&self) 
    where 
        T: std::fmt::Display 
    {
        unsafe {
            let start = self as *const DListNode<T>;
            let mut current = start;
            print!("List: ");
            loop {
                print!("{} ", (*current).data);
                current = (*current).next;
                if current == start {
                    break;
                }
            }
        }
        println!();
    }
}

pub fn main() {
    unsafe {
        // Create nodes
        let mut a = DListNode::new('A');
        let mut b = DListNode::new('B');
        let mut c = DListNode::new('C');

// Initialize self-references
        a.init_self_refs();
        b.init_self_refs();
        c.init_self_refs();

println!("Initial states (each node by itself):");
        a.print_forward();
        b.print_forward();
        c.print_forward();

// Build list: A -> B -> C -> A
        let ptr_b = &mut b as *mut DListNode<char>;
        let ptr_c = &mut c as *mut DListNode<char>;
        
        a.insert_after(ptr_b);
        (*ptr_b).insert_after(ptr_c);

println!("\nAfter linking:");
        a.print_forward();

// Some demo
        println!("\nDeleting B:");
        (*ptr_b).delete();
        a.print_forward();

println!("B still knows its neighbors:");
        println!("B.prev = {}, B.next = {}", 
                 (*(*ptr_b).prev).data, 
                 (*(*ptr_b).next).data);

println!("\nRestoring B:");
        (*ptr_b).undelete();
        a.print_forward();

// Backtracking example
        println!("\nBacktracking demonstration:");
        
        println!("1. Delete C");
        (*ptr_c).delete();
        a.print_forward();
        
        println!("2. Delete B"); 
        (*ptr_b).delete();
        a.print_forward();
        
        println!("3. Restore B (reverse order)");
        (*ptr_b).undelete();
        a.print_forward();
        
        println!("4. Restore C");
        (*ptr_c).undelete();
        a.print_forward();

println!("\nAll operations completed successfully!");
    }
}