<commit_before>//! module for finite automation.

use std::collections::HashSet;
use std::hash::Hash;


/// The rule that moves state from one to another.
///
/// `S` - the type parameter of state.
///
/// `T` - the type parameter of input symbol.
#[deriving(PartialEq, Eq, Hash)]
pub struct Rule<S, T> {
  pub state: S,
  pub symbol: Option<T>,
  pub next_state: S
}

impl<S: PartialEq, T: PartialEq> Rule<S, T> {
  /// determine whether the rule applies to the given state and symbol
  pub fn apply_to(&self, state: &S, symbol: &Option<T>) -> bool {
    self.state == *state && self.symbol == *symbol
  }
}

/// The transition relation in DFA,
/// containing all the rules needed by the DFA.
pub struct DFATransitions<S, T> {
  pub rules: HashSet<Rule<S, T>>
}

impl<S: Eq + Hash, T: Eq + Hash> DFATransitions<S, T> {
  /// get the next state for the given state and symbol
  pub fn next_state(&self, state: &S, symbol: &Option<T>) -> Option<&S> {
    self.rule_for(state, symbol).map(|rule| &rule.next_state)
  }

  fn rule_for(&self, state: &S, symbol: &Option<T>) -> Option<&Rule<S, T>> {
    self.rules.iter().find(|rule| { rule.apply_to(state, symbol) })
  }
}

/// A running dfa instance, constructed from a DFA model
pub struct DFA<'a, S: 'a, T: 'a> {
  state: S, // current state
  accept_states: &'a HashSet<S>, // set of accept states
  transitions: &'a DFATransitions<S, T>
}

impl<'a, S: Eq + Hash + Clone, T: Eq + Hash> DFA<'a, S, T> {
  pub fn accepted(&self) -> bool {
    self.accept_states.contains(&self.state)
  }

  pub fn read_symbol(&mut self, sym: &Option<T>) {
    self.state = self.transitions.next_state(&self.state, sym)
                                 .expect("unknown input symbol")
                                 .clone()
  }
}


/// DFA template that can generates dfa instance
pub struct DFAModel<S, T> {
  pub start_state: S,
  pub accept_states: HashSet<S>,
  pub transitions: DFATransitions<S, T>
}

impl<S: Clone + Eq + Hash, T: Eq + Hash> DFAModel<S, T> {
  /// determine whether the given symbols can be accepted by the model
  pub fn accept<I: Iterator<T>>(&self, mut iter: I) -> bool {
    let mut dfa = self.gen_dfa();
    for sym in iter {
      dfa.read_symbol(&Some(sym));
    }

    dfa.accepted()
  }

  /// generate a dfa instance
  fn gen_dfa(&self) -> DFA<S, T> {
    DFA {
      state: self.start_state.clone(),
      accept_states: &self.accept_states,
      transitions: &self.transitions
    }
  }
}


/// The transition relation in NFA,
/// containing all the rules needed by the NFA.
pub struct NFATransitions<S, T> {
  pub rules: HashSet<Rule<S, T>>
}

impl<S: Eq + Hash + Clone, T: Eq + Hash> NFATransitions<S, T> {

  pub fn next_states(&self, states: &HashSet<S>, symbol: &Option<T>) -> HashSet<S> {

    // TODO: find out why the flat_map thing cannot work.
    // states.iter().flat_map(|state| {
    //   // error goes here: borrowed value does not live long enough
    //   self.next_states_for(state, symbol).iter().map(|s| s.clone())
    // }).collect()

    let mut result = HashSet::new();
    for state in states.iter() {
      result.extend(self.next_states_for(state, symbol).iter().map(|s| s.clone()));
    }

    result
  }

  /// get the next state for the given state and symbol
  fn next_states_for(&self, state: &S, symbol: &Option<T>) -> HashSet<S> {
    self.rules.iter().filter_map(|rule| {
      if rule.apply_to(state, symbol) { Some(rule.next_state.clone()) } else { None }
    }).collect()
  }

  fn rules_for<'a>(&'a self, state: &S, symbol: &Option<T>) -> HashSet<&'a Rule<S, T>> {
    self.rules.iter()
              .filter(|rule| { rule.apply_to(state, symbol) })
              .collect()
  }
}


struct NFA<'a, S: 'a, T: 'a> {
  states: HashSet<S>,
  accept_states: &'a HashSet<S>,
  transitions: &'a NFATransitions<S, T>
}
<commit_msg>improve the flat_map things<commit_after>//! module for finite automation.

use std::collections::HashSet;
use std::hash::Hash;


/// The rule that moves state from one to another.
///
/// `S` - the type parameter of state.
///
/// `T` - the type parameter of input symbol.
#[deriving(PartialEq, Eq, Hash)]
pub struct Rule<S, T> {
  pub state: S,
  pub symbol: Option<T>,
  pub next_state: S
}

impl<S: PartialEq, T: PartialEq> Rule<S, T> {
  /// determine whether the rule applies to the given state and symbol
  pub fn apply_to(&self, state: &S, symbol: &Option<T>) -> bool {
    self.state == *state && self.symbol == *symbol
  }
}

/// The transition relation in DFA,
/// containing all the rules needed by the DFA.
pub struct DFATransitions<S, T> {
  pub rules: HashSet<Rule<S, T>>
}

impl<S: Eq + Hash, T: Eq + Hash> DFATransitions<S, T> {
  /// get the next state for the given state and symbol
  pub fn next_state(&self, state: &S, symbol: &Option<T>) -> Option<&S> {
    self.rule_for(state, symbol).map(|rule| &rule.next_state)
  }

  fn rule_for(&self, state: &S, symbol: &Option<T>) -> Option<&Rule<S, T>> {
    self.rules.iter().find(|rule| { rule.apply_to(state, symbol) })
  }
}

/// A running dfa instance, constructed from a DFA model
pub struct DFA<'a, S: 'a, T: 'a> {
  state: S, // current state
  accept_states: &'a HashSet<S>, // set of accept states
  transitions: &'a DFATransitions<S, T>
}

impl<'a, S: Eq + Hash + Clone, T: Eq + Hash> DFA<'a, S, T> {
  pub fn accepted(&self) -> bool {
    self.accept_states.contains(&self.state)
  }

  pub fn read_symbol(&mut self, sym: &Option<T>) {
    self.state = self.transitions.next_state(&self.state, sym)
                                 .expect("unknown input symbol")
                                 .clone()
  }
}


/// DFA template that can generates dfa instance
pub struct DFAModel<S, T> {
  pub start_state: S,
  pub accept_states: HashSet<S>,
  pub transitions: DFATransitions<S, T>
}

impl<S: Clone + Eq + Hash, T: Eq + Hash> DFAModel<S, T> {
  /// determine whether the given symbols can be accepted by the model
  pub fn accept<I: Iterator<T>>(&self, mut iter: I) -> bool {
    let mut dfa = self.gen_dfa();
    for sym in iter {
      dfa.read_symbol(&Some(sym));
    }

    dfa.accepted()
  }

  /// generate a dfa instance
  fn gen_dfa(&self) -> DFA<S, T> {
    DFA {
      state: self.start_state.clone(),
      accept_states: &self.accept_states,
      transitions: &self.transitions
    }
  }
}


/// The transition relation in NFA,
/// containing all the rules needed by the NFA.
pub struct NFATransitions<S, T> {
  pub rules: HashSet<Rule<S, T>>
}

impl<S: Eq + Hash + Clone, T: Eq + Hash> NFATransitions<S, T> {

  pub fn next_states(&self, states: &HashSet<S>, symbol: &Option<T>) -> HashSet<S> {
    states.iter().flat_map(|state| {
      // NOTE: use `move_iter` instead of `iter`
      self.next_states_for(state, symbol).move_iter()
    }).collect()
  }

  /// get the next state for the given state and symbol
  fn next_states_for(&self, state: &S, symbol: &Option<T>) -> HashSet<S> {
    self.rules.iter().filter_map(|rule| {
      if rule.apply_to(state, symbol) { Some(rule.next_state.clone()) } else { None }
    }).collect()
  }

  fn rules_for<'a>(&'a self, state: &S, symbol: &Option<T>) -> HashSet<&'a Rule<S, T>> {
    self.rules.iter()
              .filter(|rule| { rule.apply_to(state, symbol) })
              .collect()
  }
}


struct NFA<'a, S: 'a, T: 'a> {
  states: HashSet<S>,
  accept_states: &'a HashSet<S>,
  transitions: &'a NFATransitions<S, T>
}

{'fraction_non_alphanumeric': 0.16220600162206, 'fraction_numerical': 0.0, 'mean_word_length': 2.9566844919786095, 'pattern_counts': {'":': 0, '<': 97, '<?xml version=': 0, '>': 115, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6170820', 'n_tokens_mistral': 2663, 'n_tokens_neox': 2620, 'n_words': 778}