Skip to content

Instantly share code, notes, and snippets.

@Agnishom
Created September 29, 2022 14:34
Show Gist options
  • Save Agnishom/077a50679ff6750203a163a09f458687 to your computer and use it in GitHub Desktop.
Save Agnishom/077a50679ff6750203a163a09f458687 to your computer and use it in GitHub Desktop.
Paige-Tarjan
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]]);
}
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()
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment