#![warn(missing_docs)]
use std::cell::RefCell;
use std::fmt;
use std::rc::{Rc, Weak};
#[derive(Clone)]
struct Node<Alphabet> {
prev: Option<Rc<Node<Alphabet>>>,
next: RefCell<Option<Weak<Node<Alphabet>>>>,
data: RefCell<Alphabet>,
}
impl<Alphabet: Clone> Node<Alphabet> {
fn new(data: Alphabet, prev: Option<Rc<Node<Alphabet>>>) -> Node<Alphabet> {
Node {
prev,
next: RefCell::new(None),
data: RefCell::new(data),
}
}
fn prev(&self) -> Option<Rc<Node<Alphabet>>> {
self.prev.clone()
}
fn next(&self) -> Option<Weak<Node<Alphabet>>> {
self.next.borrow().clone()
}
fn replace_next(
&self,
new_value: Option<Weak<Node<Alphabet>>>,
) -> Option<Weak<Node<Alphabet>>> {
self.next.replace(new_value)
}
fn get(&self) -> Alphabet {
self.data.borrow().clone()
}
fn replace(&self, new_value: Alphabet) -> Alphabet {
self.data.replace(new_value)
}
}
pub struct TuringTape<Alphabet> {
empty: Alphabet,
last: RefCell<Rc<Node<Alphabet>>>,
cursor: RefCell<Rc<Node<Alphabet>>>,
}
impl<Alphabet: fmt::Display + Clone> fmt::Display for TuringTape<Alphabet> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "|")?;
let mut s = String::new();
let mut head: Rc<Node<Alphabet>> = self.last.borrow().clone();
loop {
let backup = s.clone();
if Rc::ptr_eq(&self.cursor.borrow(), &head) {
s = format!("> {} <|", head.get());
} else {
s = format!(" {} |", head.get());
}
s.push_str(&backup);
if let Some(new_head) = head.prev.clone() {
head = new_head;
} else {
break;
}
}
write!(f, "{}", s)
}
}
impl<Alphabet: Clone> TuringTape<Alphabet> {
pub fn new(empty: Alphabet, start: Alphabet, initial: Vec<Alphabet>) -> TuringTape<Alphabet> {
let fst_node = Rc::new(Node::new(start, None));
let tape = TuringTape {
empty,
last: RefCell::new(fst_node.clone()),
cursor: RefCell::new(fst_node),
};
initial.into_iter().for_each(|token| {
tape.append(token);
});
tape
}
fn append(&self, token: Alphabet) -> Rc<Node<Alphabet>> {
let new_node = Rc::new(Node::new(token, Some(self.last.borrow().clone())));
self.last
.borrow()
.replace_next(Some(Rc::downgrade(&new_node)));
self.last.replace(new_node.clone());
new_node
}
pub fn get_cursor(&self) -> Alphabet {
self.cursor.borrow().clone().get()
}
pub fn set_cursor(&self, value: Alphabet) -> Alphabet {
self.cursor.borrow().clone().replace(value)
}
pub fn step_right(&self) -> Alphabet {
let new_cursor = match self.cursor.borrow().clone().next() {
Some(next) => next.clone().upgrade().expect("Unable to upgrade"),
None => self.append(self.empty.clone()),
};
self.cursor.replace(new_cursor);
self.get_cursor()
}
pub fn step_left(&self) -> Alphabet {
let new_cursor = match self.cursor.borrow().clone().prev() {
Some(prev) => prev.clone(),
None => panic!("Went left side of the tape!"),
};
self.cursor.replace(new_cursor);
self.get_cursor()
}
pub fn run_states<S: TuringStates<Alphabet> + PartialEq>(
&self,
mut start_state: S,
end_states: Vec<S>,
) -> S {
while !end_states.contains(&start_state) {
start_state.internal_step(self);
}
start_state
}
}
impl<Alphabet: Clone> From<TuringTape<Alphabet>> for Vec<Alphabet> {
fn from(tape: TuringTape<Alphabet>) -> Vec<Alphabet> {
let cursor_initial = tape.cursor.borrow().clone();
let mut v = Vec::new();
while tape.cursor.borrow().clone().prev().is_some() {
tape.step_left();
}
while tape.cursor.borrow().clone().next().is_some() {
v.push(tape.get_cursor());
tape.step_right();
}
v.push(tape.get_cursor());
let mut cursor = tape.cursor.borrow_mut();
*cursor = cursor_initial;
v
}
}
pub enum Move {
Left,
Stay,
Right,
}
pub trait TuringStates<Alphabet: Clone>: Sized + PartialEq {
fn step(&self, current_token: Alphabet) -> (Self, Alphabet, Move);
fn internal_step(&mut self, tape: &TuringTape<Alphabet>) {
let (state, replace, mv) = self.step(tape.get_cursor());
*self = state;
tape.set_cursor(replace);
match mv {
Move::Left => {
tape.step_left();
}
Move::Stay => {}
Move::Right => {
tape.step_right();
}
};
}
fn run_until_end(
start_state: Self,
end_states: Vec<Self>,
empty_token: Alphabet,
start_token: Alphabet,
initial_state: Vec<Alphabet>,
) -> (Self, Vec<Alphabet>) {
let tape = TuringTape::new(empty_token, start_token, initial_state);
let end_state = tape.run_states(start_state, end_states);
(end_state, tape.into())
}
}
#[cfg(test)]
mod tests {
#[derive(PartialEq, Clone, Debug)]
pub enum Bit {
Delta,
Zero,
One,
}
impl fmt::Display for Bit {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
use Bit::*;
match self {
Delta => write!(f, "_"),
Zero => write!(f, "0"),
One => write!(f, "1"),
}
}
}
use super::*;
#[test]
fn fetch_cursor() {
use Bit::*;
assert_eq!(TuringTape::new(Delta, Zero, vec![]).get_cursor(), Zero);
assert_eq!(TuringTape::new(Delta, One, vec![]).get_cursor(), One);
assert_eq!(TuringTape::new(Delta, Delta, vec![]).get_cursor(), Delta);
assert_eq!(TuringTape::new(Delta, Zero, vec![Delta]).get_cursor(), Zero);
assert_eq!(TuringTape::new(Delta, One, vec![Delta]).get_cursor(), One);
assert_eq!(
TuringTape::new(Delta, Delta, vec![Delta]).get_cursor(),
Delta
);
}
#[test]
fn set_cursor() {
use Bit::*;
let tape = TuringTape::new(Delta, Delta, vec![Zero, One, Zero]);
assert_eq!(tape.get_cursor(), Delta);
tape.set_cursor(One);
assert_eq!(tape.get_cursor(), One);
tape.set_cursor(Zero);
assert_eq!(tape.get_cursor(), Zero);
}
#[test]
fn turing_tape_new() {
use Bit::*;
TuringTape::new(
Delta,
Delta,
vec![Zero, One, One, One, Zero, One, One, One, Zero],
);
}
#[test]
fn turing_into_vec() {
use Bit::*;
let tape = TuringTape::new(
Delta,
Delta,
vec![Zero, One, One, One, Zero, One, One, One, Zero],
);
assert_eq!(
<Vec<Bit>>::from(tape),
vec![Delta, Zero, One, One, One, Zero, One, One, One, Zero]
);
}
#[test]
fn turing_stepping() {
use Bit::*;
let tape = TuringTape::new(
Delta,
Delta,
vec![Zero, One, One, One, Zero, One, One, One, Zero],
);
assert_eq!(tape.get_cursor(), Delta);
tape.step_right();
assert_eq!(tape.get_cursor(), Zero);
tape.step_left();
assert_eq!(tape.get_cursor(), Delta);
tape.step_right();
tape.step_right();
assert_eq!(tape.get_cursor(), One);
tape.step_right();
assert_eq!(tape.get_cursor(), One);
tape.step_right();
assert_eq!(tape.get_cursor(), One);
tape.step_right();
assert_eq!(tape.get_cursor(), Zero);
assert_eq!(tape.step_right(), tape.get_cursor());
assert_eq!(tape.step_right(), tape.get_cursor());
assert_eq!(tape.step_right(), tape.get_cursor());
assert_eq!(tape.step_right(), tape.get_cursor());
}
}