runtasktic 1.2.1

pub mod dot;
mod iter;

use self::iter::*;

#[derive(Debug, PartialEq, Clone)]
pub struct TaskFst {
  states: Vec<TaskFstState>,
  start_states: Vec<usize>,
}

#[derive(Debug, PartialEq, Clone)]
pub struct TaskFstState {
  label: String,
  id: usize,
  next: Vec<usize>,
  prev: Vec<usize>,
}

impl TaskFst {
  pub fn new() -> TaskFst {
    TaskFst {
      states: vec![],
      start_states: vec![],
    }
  }

  pub fn len(&self) -> usize {
    self.states.len()
  }

  pub fn add_state<S: Into<String>>(&mut self, label: S) -> usize {
    self.states.push(TaskFstState {
      label: label.into(),
      id: self.states.len(),
      next: vec![],
      prev: vec![],
    });
    self.states.len() - 1
  }

  pub fn add_start_state(&mut self, id: usize) {
    self.start_states.push(id)
  }

  pub fn add_arc(&mut self, from: usize, to: usize) {
    self.states[from].next.push(to);
    self.states[to].prev.push(from);
  }

  pub fn get_state_from_id(&self, id: usize) -> &TaskFstState {
    &self.states[id]
  }

  pub fn is_cyclic(&self) -> bool {
    let visited: &mut Vec<usize> = &mut Vec::with_capacity(self.states.len());
    for s in &self.start_states {
      visited.push(*s);
      if self.is_cyclic_dfs(visited) {
        return true;
      }
      visited.pop();
    }
    false
  }

  fn is_cyclic_dfs(&self, visited: &mut Vec<usize>) -> bool {
    let cur = visited[visited.len() - 1];
    for s in &self.states[cur].next {
      if visited.contains(s) {
        return true;
      }
      visited.push(*s);
      if self.is_cyclic_dfs(visited) {
        return true;
      }
      visited.pop();
    }
    false
  }

  pub fn reachable_states(&self) -> Vec<bool> {
    let visited: &mut Vec<usize> = &mut Vec::with_capacity(self.states.len());
    let reachable: &mut Vec<bool> = &mut vec![false; self.states.len()];
    for s in &self.start_states {
      reachable[*s] = true;
      visited.push(*s);
      self.reachable_states_dfs(visited, reachable);
      visited.pop();
    }
    reachable.clone()
  }

  fn reachable_states_dfs(&self, visited: &mut Vec<usize>, reachable: &mut Vec<bool>) {
    let cur = visited[visited.len() - 1];
    for s in &self.states[cur].next {
      reachable[*s] = true;
      if visited.contains(s) {
        return;
      }
      visited.push(*s);
      self.reachable_states_dfs(visited, reachable);
      visited.pop();
    }
  }

  pub fn iter(&self) -> TaskIter {
    TaskIter::new(&self)
  }
}

impl TaskFstState {
  pub fn label(&self) -> &String {
    &self.label
  }

  pub fn id(&self) -> usize {
    self.id
  }
}

#[cfg(test)]
mod test {
  use super::*;

  #[test]
  pub fn create_task_fst() {
    assert_eq!(
      TaskFst::new(),
      TaskFst {
        states: vec![],
        start_states: vec![]
      }
    );
  }

  #[test]
  pub fn add_arc() {
    let mut fst = TaskFst::new();
    fst.add_state("a");
    fst.add_state("b");
    fst.add_arc(0, 1);

    assert_eq!(
      fst,
      TaskFst {
        states: vec![
          TaskFstState {
            label: "a".to_string(),
            id: 0,
            next: vec![1],
            prev: vec![]
          },
          TaskFstState {
            label: "b".to_string(),
            id: 1,
            next: vec![],
            prev: vec![0]
          }
        ],
        start_states: vec![]
      }
    )
  }

  #[test]
  pub fn is_cyclic_and_reachable() {
    let mut fst = TaskFst::new();
    fst.add_state("a");
    fst.add_state("b");

    fst.add_arc(0, 1);
    assert_eq!(fst.reachable_states(), vec![false, false]);
    fst.add_start_state(0);
    assert_eq!(fst.reachable_states(), vec![true, true]);

    assert!(!fst.is_cyclic());

    fst.add_state("c");

    assert_eq!(fst.reachable_states(), vec![true, true, false]);
    fst.add_arc(0, 2);
    assert_eq!(fst.reachable_states(), vec![true, true, true]);
    assert!(!fst.is_cyclic());
    fst.add_arc(1, 2);
    assert!(!fst.is_cyclic());

    fst.add_state("d");
    assert_eq!(fst.reachable_states(), vec![true, true, true, false]);
    fst.add_arc(2, 3);
    assert_eq!(fst.reachable_states(), vec![true, true, true, true]);
    assert!(!fst.is_cyclic());

    fst.add_state("e");
    assert_eq!(fst.reachable_states(), vec![true, true, true, true, false]);
    fst.add_start_state(4);
    assert_eq!(fst.reachable_states(), vec![true, true, true, true, true]);
    assert!(!fst.is_cyclic());

    fst.add_arc(4, 3);
    assert!(!fst.is_cyclic());

    fst.add_arc(3, 1);
    assert!(fst.is_cyclic());
  }
}