baktrak 0.1.0

A quick little library for super simple backtracking in Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

use std::collections::{BTreeMap, BTreeSet, VecDeque};

pub trait BackTrackable: Ord + Clone {
    fn next(&self) -> Vec<Self>
    where
        Self: Sized;
    fn is_final(&self) -> bool;

    fn backtrack(&self) -> Option<Vec<Self>>
    where
        Self: Sized,
    {
        let mut tracker = BackTracker::new(self.clone());
        tracker.run()
    }
}

pub struct BackTracker<T: BackTrackable + Ord + Clone> {
    queue: VecDeque<T>,
    seen: BTreeSet<T>,
    comes_from: BTreeMap<T, T>,
}

impl<T: BackTrackable + Ord + Clone> BackTracker<T> {
    pub fn new(start: T) -> Self {
        Self {
            queue: VecDeque::from_iter(vec![start]),
            seen: BTreeSet::new(),
            comes_from: BTreeMap::new(),
        }
    }

    pub fn run(&mut self) -> Option<Vec<T>> {
        while let Some(current) = self.queue.pop_front() {
            if self.seen.contains(&current) {
                continue;
            }

            if current.is_final() {
                let mut path = vec![current.clone()];
                let mut node = current.clone();
                while let Some(next) = self.comes_from.get(&node) {
                    path.push(next.clone());
                    node = next.clone();
                }
                path.reverse();
                return Some(path);
            }

            current.next().iter().for_each(|next| {
                if !self.seen.contains(next) && !self.queue.contains(next) {
                    self.queue.push_back(next.clone());
                    self.comes_from.insert(next.clone(), current.clone());
                }
            });
            self.seen.insert(current.clone());
        }
        None
    }
}

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

    #[derive(Debug, Clone, PartialEq, Eq, Ord, PartialOrd)]
    struct TestState {
        value: i32,
    }

    impl BackTrackable for TestState {
        fn next(&self) -> Vec<Self> {
            if self.value < 5 {
                vec![TestState {
                    value: self.value + 1,
                }]
            } else {
                vec![]
            }
        }

        fn is_final(&self) -> bool {
            self.value == 5
        }
    }

    #[test]
    fn test_back_tracker() {
        assert_eq!(
            TestState { value: 0 }.backtrack(),
            Some(vec![
                TestState { value: 0 },
                TestState { value: 1 },
                TestState { value: 2 },
                TestState { value: 3 },
                TestState { value: 4 },
                TestState { value: 5 },
            ])
        );
    }
}