前些日子为了练习使用泛型，作死写了一个带回溯的dfs。

带回溯的dfs需要保存当前状态，于是我们需要一个类似struct DFS<const N:usize>{state:[i32;N]}这样的结构。

为了保证搜索前后不改变状态，这里使用了Drop trait，在制作新状态的时候用op记录更改，在drop时候使用op把更改撤销。

因此DFS变成了这个样子：

struct DFS<const N:usize,Op>{
    state:[i32;N], // 目前每次新建都是复制，并不是修改/撤销
    op:Op
}
impl DFS{
    fn dfs(self){
        if condition_met {println!("found,{:?}",self.state)}
        for op in ops{
            DFS{state:op.r#do(state),op:op}.dfs()
        }
    }
}
impl drop for DFS{...}

这里涉及到对state的操作，不方便将state直接原样传递（因为Copy开销可能很大）

于是可以尝试使用&mut state

struct DFS<'a,const N:usize>{state:&'a mut [i32;N],op:Op}
...
    pub fn dfs<'b>(&'b mut self)
    where
        'a: 'b,
    {
        if (self.check)(self.status) {
            return;
        }
        for op in (self.get_all_ops)(self.status) {
            let mut next = self.forward(op);
            next.op = op;
            next.dfs();
        }
    }

这样做会产生额外开销：哪怕所有的&mut state都一样，我们也必须为每一个DFS分配一个&mut state的存储空间，因而产生额外的开销。

类似的算法可以做成零成本抽象吗？

附录：一个有额外开销的抽象。

pub struct DFS<
    'a,
    C,
    O: Copy,
    T: FnOnce(&mut C, O),
    U: FnMut(&mut C, O),
    V: FnOnce(&C) -> bool,
    W: FnOnce(&C) -> X,
    X: IntoIterator<Item = O>,
> {
    status: &'a mut C,
    forward: T,
    back_tracking: U,
    check: V,
    get_all_ops: W,
    op: O,
}
impl<
        'a,
        C: std::fmt::Debug,
        O: Copy,
        T: Copy + FnOnce(&mut C, O),
        U: Copy + FnMut(&mut C, O),
        V: Copy + FnOnce(&C) -> bool,
        // W: FnOnce(&C) -> X,
        // move occurs because `self.get_all_ops` has type `W`, which does not implement the `Copy` trait
        W: Copy + FnOnce(&C) -> X,
        X: IntoIterator<Item = O>,
    > DFS<'a, C, O, T, U, V, W, X>
{
    pub fn new(
        status: &'a mut C,
        forward: T,
        back_tracking: U,
        check: V,
        get_all_ops: W,
        op: O,
    ) -> Self {
        Self {
            status,
            forward,
            back_tracking,
            check,
            get_all_ops,
            op,
        }
    }
    pub fn dfs<'b>(&'b mut self)
    where
        'a: 'b,
    {
        if (self.check)(self.status) {
            return;
        }
        for op in (self.get_all_ops)(self.status) {
            let mut next = self.forward(op);
            next.op = op;
            next.dfs();
        }
    }
    pub fn dfs_early_stop<'b>(&'b mut self) -> bool
    where
        'a: 'b,
    {
        if (self.check)(self.status) {
            return true;
        }
        for op in (self.get_all_ops)(self.status) {
            let mut next = self.forward(op);
            next.op = op;
            if next.dfs_early_stop() {
                return true;
            }
        }
        false
    }
    pub fn forward<'b: 'c, 'c>(&'b mut self, op: O) -> DFS<'b, C, O, T, U, V, W, X>
    where
        'b: 'c,
    {
        (self.forward)(self.status, op);
        DFS {
            status: self.status,
            forward: self.forward,
            back_tracking: self.back_tracking,
            check: self.check,
            get_all_ops: self.get_all_ops,
            op,
        }
    }
}
impl<
        'a,
        C,
        O: Copy,
        T: FnOnce(&mut C, O),
        U: FnMut(&mut C, O),
        V: FnOnce(&C) -> bool,
        W: FnOnce(&C) -> X,
        X: IntoIterator<Item = O>,
    > Drop for DFS<'a, C, O, T, U, V, W, X>
{
    fn drop(&mut self) {
        (self.back_tracking)(self.status, self.op)
    }
}
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        const N: usize = 3;
        {
            let mut s = [0; 2 * N + 1];
            s[0] = N as i32;
            let mut a = DFS::new(
                &mut s,
                |s: &mut [i32; 2 * N + 1], op: (i32, i32)| {
                    s[op.1 as usize] = op.0;
                    s[(1 + op.0 + op.1) as usize] = op.0;
                    s[0] -= 1;
                },
                |s: &mut [i32; 2 * N + 1], op: (i32, i32)| {
                    s[op.1 as usize] = 0;
                    s[(1 + op.0 + op.1) as usize] = 0;
                    s[0] += 1
                },
                |s: &[i32; 2 * N + 1]| {
                    if s[0] == 0 {
                        eprintln!("{s:?}");
                        true
                    } else {
                        false
                    }
                },
                |s: &[i32; 2 * N + 1]| {
                    let a = s[0];
                    (1..2 * N as i32 - a)
                        .filter_map(move |x| {
                            if s[x as usize] + s[(1 + a + x) as usize] == 0 {
                                Some((a, x))
                            } else {
                                None
                            }
                        })
                        .collect::<Vec<_>>()
                },
                (1, 0),
            );
            a.dfs();
            a.dfs_early_stop();
        }
    }
}