nuprl / jankscripten Goto Github PK

use std::cell::Cell;

pub enum BinTree {
    Leaf,
    Node(Box<BinTree>, usize, Box<BinTree>)
}

pub struct Replaceable<'a, T> {
    value: &'a mut T,
    new_value: Cell<Option<T>>
}

impl<'a, T> Replaceable<'a, T> {
    fn new(value: &'a mut T) -> Replaceable<'a, T> {
        Replaceable {
            value: value,
            new_value: Cell::new(None)
        }
    }

    fn get(&self) -> &T {
        self.value
    }

    fn set(&self, value: T) { 
        self.new_value.set(Some(value));
    }

    fn update(&mut self)  {
        if let Some(x) = self.new_value.take() {
            *self.value = x;
        }
    }
}

pub enum Context1<'a> {
    Left(&'a Replaceable<'a, usize>, &'a Replaceable<'a, BinTree>),
    Right(&'a Replaceable<'a, BinTree>, &'a Replaceable<'a, usize>)
}

pub enum Context<'a> {
    Nil,
    Cons(Context1<'a>, &'a Context<'a>)
}

pub trait Visitor {
    fn enter(&mut self, _node: &mut BinTree, _context: &Context) {
        // Do nothing by default
    }

    fn exit(&mut self, _node: &mut BinTree, _context: &Context) {
        // Do nothing by default
    }
}

pub fn visit_rec<'a, 'b>(tree: &'a mut BinTree, cxt: &'a Context<'a>, visitor: &mut impl Visitor) {
    visitor.enter(tree, cxt);
    match tree {
        BinTree::Leaf => { },
        BinTree::Node(lhs, value, rhs) => {
                  
                let mut value_cell = Replaceable::new(value);
                let mut rhs_cell = Replaceable::new(rhs.as_mut());
                let lhs_cxt = Context::Cons(Context1::Left(&value_cell, &rhs_cell), cxt);
                visit_rec(lhs, &lhs_cxt, visitor);
                value_cell.update();
                rhs_cell.update();
                
                let mut value_cell = Replaceable::new(value);
                let mut lhs_cell = Replaceable::new(lhs.as_mut());
                let mut rhs_cxt = Context::Cons(Context1::Right(&lhs_cell, &value_cell), cxt);
                visit_rec(rhs, &mut rhs_cxt, visitor);
                value_cell.update();
                lhs_cell.update();
        }
    }
    visitor.exit(tree, cxt);
}


pub fn visit(tree: & mut BinTree, visitor: &mut impl Visitor) {
    let mut cxt = Context::Nil;
    visit_rec(tree, &mut cxt, visitor);
}