Paige-Tarjan

main.rs

use std::collections::VecDeque;
use std::cell::RefCell;
use std::rc::Rc;
use std::cell::Ref;

pub mod vllsimple;
use vllsimple::*;

struct part_man{
    // pools
    points_pool : VllPool<point>,
    edges_pool : VllPool<edge>,
    count_pool : VllPool<u64>,
    point_ptr_pool : VllPool<VllPointer<point>>,
    qblock_pool : VllPool<qblock>,
    qblock_ptr_pool : VllPool<VllPointer<qblock>>,
    xblock_pool : VllPool<xblock>,
    xblock_ptr_pool : VllPool<VllPointer<xblock>>,
    // vlls
    points_vll : Vll<point>,
    counts_vll : Vll<u64>,
    qblocks_vll : Vll<qblock>,
    xblocks_vll : Vll<xblock>,
    compound_vll : Vll<VllPointer<xblock>>,
}

struct point {
    edges : Vll<edge>,
    // the block that this point is contained in
    qblock : VllPointer<qblock>,
}

impl point {
    fn add_edge(&mut self, pool: &mut VllPool<edge>, edge : edge){
        self.edges.push_front(pool, edge);
    }
}

struct edge {
    source : VllPointer<point>,
    count: VllPointer<u64>,
}

struct qblock {
    qblock_size : u64,
    points : Vll<VllPointer<point>>,
    xblock_containing : VllPointer<xblock>,
}

impl qblock{
    fn add_point(&mut self, pool: &mut VllPool<VllPointer<point>>, point : VllPointer<point>){
        self.points.push_front(pool, point);
    }
}

struct xblock {
    qblocks_contained : Vll<VllPointer<qblock>>,
}

fn init_part_manager(n : u64, m : u64, edges : Vec<Vec<u64>>, partition : Vec<Vec<u64>>) -> part_man{
    let mut points_pool : VllPool<point> = VllPool::new(n as usize);
    let mut edges_pool : VllPool<edge> = VllPool::new(m as usize);
    let mut count_pool : VllPool<u64> = VllPool::new(m as usize);
    let mut point_ptr_pool : VllPool<VllPointer<point>> = VllPool::new(n as usize);
    let mut qblock_pool : VllPool<qblock> = VllPool::new(n as usize);
    let mut qblock_ptr_pool : VllPool<VllPointer<qblock>> = VllPool::new(n as usize);
    let mut xblock_pool : VllPool<xblock> = VllPool::new(n as usize);
    let mut xblock_ptr_pool : VllPool<VllPointer<xblock>> = VllPool::new(n as usize);
    
    let mut points_vll : Vll<point> = points_pool.new_vll();
    let mut counts_vll : Vll<u64> = count_pool.new_vll();
    let mut qblocks_vll : Vll<qblock> = qblock_pool.new_vll();
    let mut xblocks_vll : Vll<xblock> = xblock_pool.new_vll();
    let mut compound_vll : Vll<VllPointer<xblock>> = xblock_ptr_pool.new_vll();

    let mut to_point_ptr : Vec<VllPointer<point>> = Vec::new();
    let mut to_qblock_ptr : Vec<VllPointer<qblock>> = Vec::new();
    
    // for every point i
    for i in 0..n {
        // create a new point with empty edge list
        let point = point {
            edges : edges_pool.new_vll(),
            qblock : VllPointer::null(),
        };
        // create a new count
        let count = counts_vll.push_front(&mut count_pool, 0);
        // add the pointer to the linked list of points
        let point_ptr = points_vll.push_front(&mut points_pool, point);
        // for every edge (i, j) in the input,
        // add the edge to the edge list of point i
        for j in &edges[i as usize]{
            let edge = edge {
                    source: point_ptr,
                      count: count
                    };
            let point = points_vll.get(&mut points_pool, point_ptr);
            point.add_edge(&mut edges_pool, edge);
            // increment the count associated with the edge
            let count = counts_vll.get(&mut count_pool, count);
            *count += 1;
        }
        // add the pointer to the vector of pointers
        to_point_ptr.push(point_ptr);
    }

    for q in 0..partition.len(){
        // set up a dummy qblock
        let qblock = qblock {
            qblock_size : partition[q].len() as u64,
            points : point_ptr_pool.new_vll(),
            xblock_containing : VllPointer::null(),
        };
        let qblock_ptr = qblocks_vll.push_front(&mut qblock_pool, qblock);
        // iterate through every partition and for each point in the partition,
        // add the point to the qblock and set the qblock of the point to the qblock
        for p in &partition[q]{
            let point = points_vll.get(&mut points_pool, to_point_ptr[*p as usize]);
            let qblock = qblocks_vll.get(&mut qblock_pool, qblock_ptr);
            qblock.add_point(&mut point_ptr_pool, to_point_ptr[*p as usize]);
            point.qblock = qblock_ptr;
        }
        // add the qblock to the vector of pointers
        to_qblock_ptr.push(qblock_ptr);
    }

    // set up a single xblock and put all the qblocks in it
    let xblock = xblock {
        qblocks_contained : qblock_ptr_pool.new_vll(),
    };
    let xblock_ptr = xblocks_vll.push_front(&mut xblock_pool, xblock);
    for qblock_ptr in &to_qblock_ptr{
        let xblock = xblocks_vll.get(&mut xblock_pool, xblock_ptr);
        xblock.qblocks_contained.push_front(&mut qblock_ptr_pool, *qblock_ptr);
        qblocks_vll.get(&mut qblock_pool, *qblock_ptr).xblock_containing = xblock_ptr;
    }

    // add this xblock to the list of compound xblocks
    compound_vll.push_front(&mut xblock_ptr_pool, xblock_ptr);

    part_man{
        points_pool,
        edges_pool,
        count_pool,
        point_ptr_pool,
        qblock_pool,
        qblock_ptr_pool,
        xblock_pool,
        xblock_ptr_pool,
        points_vll,
        counts_vll,
        qblocks_vll,
        xblocks_vll,
        compound_vll,
    }

}

fn paige_tarjan(mut partman : part_man){
    while !partman.compound_vll.is_empty(){
        // step 1: select refining block
        let blockS_ptr = partman.compound_vll.get_head(&partman.xblock_ptr_pool);
        //let blockS = partman.xblocks_vll.get(&mut partman.xblock_pool, blockS_ptr);
        partman.compound_vll.delete(&mut partman.xblock_ptr_pool, blockS_ptr);

    }

}

fn main() {
    init_part_manager(2, 
        4,
        vec![vec![0, 1]
        , vec![0, 1]],
        vec![vec![0, 1]]);
}

vllsimple.rs

use std::marker::PhantomData;

pub struct VllPool<T> {
    mem : Vec<T>,
    freehead : Option<usize>,
    next : Vec<Option<usize>>,
    prev : Vec<Option<usize>>,
}

pub struct Vll<T> {
    head : VllPointer<T>,
}

pub struct VllPointer<T> {
    ptr : Option<usize>,
    phantom : PhantomData<T>,
}

impl<T> Clone for VllPointer<T> {
    fn clone(&self) -> VllPointer<T> {
        VllPointer { ptr : self.ptr.clone(), phantom : PhantomData }
    }
}

impl<T> Copy for VllPointer<T> {}

impl<T> VllPool<T>{
    pub fn new(size : usize) -> VllPool<T> {
        assert!(size > 0);
        let mut mem : Vec<T> = Vec::with_capacity(size);
        unsafe {
            mem.set_len(size);
        }
        let freehead : Option<usize> = Some(0);
        // next = [Some(1), Some(2), ..., Some(size-1), None]
        let mut next : Vec<Option<usize>> = (0..size).map(|i| Some(i + 1)).collect();
        next.push(None);
        let prev : Vec<Option<usize>> = vec![None; size];
        VllPool { mem, freehead, next, prev }
    }
    pub fn new_vll(&self) -> Vll<T> {
        Vll { head : VllPointer::null()}
    }
    pub fn has_space(&self) -> bool {
        self.freehead.is_some()
    }
    // creates a new node with content x
    // which is positioned after after, and before before,
    // i.e, after -> new -> before
    fn insert_new(&mut self, x : T, after : Option<usize>, before : Option<usize>) -> usize {
        assert!(self.has_space());
        let tmp = self.freehead.unwrap();
        self.freehead = self.next[tmp];
        self.next[tmp] = before;
        self.prev[tmp] = after;
        if let Some(b) = before {
            self.prev[b] = Some(tmp);
        }
        if let Some(a) = after {
            self.next[a] = Some(tmp);
        }
        self.mem[tmp] = x;
        tmp
    }
    // deletes the node at position p
    // p is the new head of the free list
    // if we previously had after -> p -> before
    // now we have after -> before
    fn delete(&mut self, p : usize) {
        let after = self.prev[p];
        let before = self.next[p];
        if let Some(b) = before {
            self.prev[b] = after;
        }
        if let Some(a) = after {
            self.next[a] = before;
        }
        self.next[p] = self.freehead;
        self.freehead = Some(p);
    }
    // moves p to a new singleton list
    fn move_to_singleton(&mut self, p : usize){
        // previously we had after -> p -> before
        // now we have after -> before
        let after = self.prev[p];
        let before = self.next[p];
        if let Some(b) = before {
            self.prev[b] = after;
        }
        if let Some(a) = after {
            self.next[a] = before;
        }
        // now we have p -> None
        self.next[p] = None;
        self.prev[p] = None;
    }
    fn get<'b>(&'b mut self, p : usize) -> &'b mut T {
        &mut self.mem[p]
    }
}

impl<T> Vll<T> {
    pub fn is_empty(&self) -> bool {
        !self.head.is_some()
    }
    pub fn push_front(&mut self, pool : &mut VllPool<T>, x : T) -> VllPointer<T> {
        let p = pool.insert_new(x, None, self.head.ptr);
        self.head.ptr = Some(p);
        VllPointer { ptr : Some(p), phantom : PhantomData }
    }
    pub fn delete(&mut self, pool : &mut VllPool<T>, p : VllPointer<T>) {
        assert!(p.is_some());
        let p = p.ptr.unwrap();
        pool.delete(p);
        if self.head.ptr == Some(p) {
            self.head.ptr = pool.next[p];
        }
    }
    pub fn move_to_singleton(&mut self, pool : &mut VllPool<T>, p : VllPointer<T>) -> Vll<T> {
        assert!(p.is_some());
        let p = p.ptr.unwrap();
        pool.move_to_singleton(p);
        if self.head.ptr == Some(p) {
            self.head.ptr = pool.next[p];
        }
        Vll { head : VllPointer { ptr : Some(p), phantom : PhantomData } }
    }
    pub fn get<'b>(&'b mut self, pool : &'b mut VllPool<T>, p : VllPointer<T>) -> &'b mut T {
        assert!(p.is_some());
        let p = p.ptr.unwrap();
        pool.get(p)
    }
    pub fn get_head<'b>(&'b self, pool : &'b VllPool<T>) -> VllPointer<T> {
        VllPointer { ptr : self.head.ptr, phantom : PhantomData }
    }
    pub fn get_next<'b>(&'b self, pool : &'b VllPool<T>, p : VllPointer<T>) -> VllPointer<T> {
        assert!(p.is_some());
        let p = p.ptr.unwrap();
        VllPointer { ptr : pool.next[p], phantom : PhantomData }
    }
    pub fn get_prev<'b>(&'b self, pool : &'b VllPool<T>, p : VllPointer<T>) -> VllPointer<T> {
        assert!(p.is_some());
        let p = p.ptr.unwrap();
        VllPointer { ptr : pool.prev[p], phantom : PhantomData }
    }
}

impl<T> VllPointer<T> {
    fn point_to(p : usize) -> VllPointer<T> {
        VllPointer { ptr : Some(p), phantom : PhantomData }
    }
    pub fn null() -> VllPointer<T> {
        VllPointer { ptr : None, phantom : PhantomData }
    }
    pub fn is_some(&self) -> bool {
        self.ptr.is_some()
    }
}