dfs_rs/
proto.rs

1
2pub struct DFS<
3    'a,
4    C,
5    O: Copy,
6    T: FnOnce(&mut C, O),
7    U: FnMut(&mut C, O),
8    V: FnOnce(&C) -> bool,
9    W: FnOnce(&C) -> X,
10    X: IntoIterator<Item = O>,
11> {
12    status: &'a mut C,
13    forward: T,
14    back_tracking: U,
15    check: V,
16    get_all_ops: W,
17    op: O,
18}
19impl<
20        'a,
21        C: std::fmt::Debug,
22        O: Copy,
23        T: Copy + FnOnce(&mut C, O),
24        U: Copy + FnMut(&mut C, O),
25        V: Copy + FnOnce(&C) -> bool,
26        // W: FnOnce(&C) -> X,
27        // move occurs because `self.get_all_ops` has type `W`, which does not implement the `Copy` trait
28        W: Copy + FnOnce(&C) -> X,
29        X: IntoIterator<Item = O>,
30    > DFS<'a, C, O, T, U, V, W, X>
31{
32    pub fn new(
33        status: &'a mut C,
34        forward: T,
35        back_tracking: U,
36        check: V,
37        get_all_ops: W,
38        op: O,
39    ) -> Self {
40        Self {
41            status,
42            forward,
43            back_tracking,
44            check,
45            get_all_ops,
46            op,
47        }
48    }
49    pub fn dfs<'b>(&'b mut self)
50    where
51        'a: 'b,
52    {
53        if (self.check)(self.status) {
54            return;
55        }
56        for op in (self.get_all_ops)(self.status) {
57            let mut next = self.forward(op);
58            next.op = op;
59            next.dfs();
60        }
61    }
62    pub fn dfs_early_stop<'b>(&'b mut self) -> bool
63    where
64        'a: 'b,
65    {
66        if (self.check)(self.status) {
67            return true;
68        }
69        for op in (self.get_all_ops)(self.status) {
70            let mut next = self.forward(op);
71            next.op = op;
72            if next.dfs_early_stop() {
73                return true;
74            }
75        }
76        false
77    }
78    pub fn forward<'b: 'c, 'c>(&'b mut self, op: O) -> DFS<'b, C, O, T, U, V, W, X>
79    where
80        'b: 'c,
81    {
82        (self.forward)(self.status, op);
83        DFS {
84            status: self.status,
85            forward: self.forward,
86            back_tracking: self.back_tracking,
87            check: self.check,
88            get_all_ops: self.get_all_ops,
89            op,
90        }
91    }
92}
93impl<
94        'a,
95        C,
96        O: Copy,
97        T: FnOnce(&mut C, O),
98        U: FnMut(&mut C, O),
99        V: FnOnce(&C) -> bool,
100        W: FnOnce(&C) -> X,
101        X: IntoIterator<Item = O>,
102    > Drop for DFS<'a, C, O, T, U, V, W, X>
103{
104    fn drop(&mut self) {
105        (self.back_tracking)(self.status, self.op)
106    }
107}
108#[cfg(test)]
109mod tests {
110    use super::*;
111
112    #[test]
113    fn it_works() {
114        const N: usize = 3;
115        {
116            let mut s = [0; 2 * N + 1];
117            s[0] = N as i32;
118            let mut a = DFS::new(
119                &mut s,
120                |s: &mut [i32; 2 * N + 1], op: (i32, i32)| {
121                    s[op.1 as usize] = op.0;
122                    s[(1 + op.0 + op.1) as usize] = op.0;
123                    s[0] -= 1;
124                },
125                |s: &mut [i32; 2 * N + 1], op: (i32, i32)| {
126                    s[op.1 as usize] = 0;
127                    s[(1 + op.0 + op.1) as usize] = 0;
128                    s[0] += 1
129                },
130                |s: &[i32; 2 * N + 1]| {
131                    if s[0] == 0 {
132                        eprintln!("{s:?}");
133                        true
134                    } else {
135                        false
136                    }
137                },
138                |s: &[i32; 2 * N + 1]| {
139                    let a = s[0];
140                    (1..2 * N as i32 - a)
141                        .filter_map(move |x| {
142                            if s[x as usize] + s[(1 + a + x) as usize] == 0 {
143                                Some((a, x))
144                            } else {
145                                None
146                            }
147                        })
148                        .collect::<Vec<_>>()
149                },
150                (1, 0),
151            );
152            a.dfs();
153            a.dfs_early_stop();
154        }
155    }
156}
dfs_rs/proto.rs

dfs_rs/
proto.rs
