use std::collections::HashSet;
use std::hash::Hash;
use std::iter::FusedIterator;
pub fn dfs<N, FN, IN, FS>(start: N, mut successors: FN, mut success: FS) -> Option<Vec<N>>
where
N: Eq,
FN: FnMut(&N) -> IN,
IN: IntoIterator<Item = N>,
FS: FnMut(&N) -> bool,
{
let mut path = vec![start];
step(&mut path, &mut successors, &mut success).then_some(path)
}
fn step<N, FN, IN, FS>(path: &mut Vec<N>, successors: &mut FN, success: &mut FS) -> bool
where
N: Eq,
FN: FnMut(&N) -> IN,
IN: IntoIterator<Item = N>,
FS: FnMut(&N) -> bool,
{
if success(path.last().unwrap()) {
true
} else {
let successors_it = successors(path.last().unwrap());
for n in successors_it {
if !path.contains(&n) {
path.push(n);
if step(path, successors, success) {
return true;
}
path.pop();
}
}
false
}
}
pub fn dfs_reach<N, FN, IN>(start: N, successors: FN) -> DfsReachable<N, FN>
where
N: Eq + Hash + Clone,
FN: FnMut(&N) -> IN,
IN: IntoIterator<Item = N>,
{
let (to_see, mut seen) = (vec![start.clone()], HashSet::new());
seen.insert(start);
DfsReachable {
to_see,
seen,
successors,
}
}
pub struct DfsReachable<N, FN> {
to_see: Vec<N>,
seen: HashSet<N>,
successors: FN,
}
impl<N, FN, IN> Iterator for DfsReachable<N, FN>
where
N: Eq + Hash + Clone,
FN: FnMut(&N) -> IN,
IN: IntoIterator<Item = N>,
{
type Item = N;
fn next(&mut self) -> Option<Self::Item> {
let n = self.to_see.pop()?;
let mut to_insert = Vec::new();
for s in (self.successors)(&n) {
if !self.seen.contains(&s) {
to_insert.push(s.clone());
self.seen.insert(s);
}
}
self.to_see.extend(to_insert.into_iter().rev());
Some(n)
}
}
impl<N, FN, IN> FusedIterator for DfsReachable<N, FN>
where
N: Eq + Hash + Clone,
FN: FnMut(&N) -> IN,
IN: IntoIterator<Item = N>,
{
}