dfs_rs/
indexable.rs

1use std::ops::{Index, IndexMut};
2pub trait Op<T> {
3    fn r#do(&mut self, status: &mut T);
4    fn undo(&mut self, status: &mut T);
5}
6impl<T> Op<T> for (){
7    fn r#do(&mut self, _: &mut T){}
8    fn undo(&mut self, _: &mut T){}
9}
10#[derive(Copy, Clone)]
11pub struct Add<I, V>(pub I, pub V);
12impl<T: IndexMut<I>, I: Copy, V: Copy> Op<T> for Add<I, V>
13where
14    <T as Index<I>>::Output: std::ops::SubAssign<V> + std::ops::AddAssign<V>,
15{
16    #[inline(always)]
17    fn r#do(&mut self, status: &mut T) {
18        status[self.0] += self.1
19    }
20    #[inline(always)]
21    fn undo(&mut self, status: &mut T) {
22        status[self.0] -= self.1
23    }
24}
25#[derive(Copy, Clone)]
26pub struct Assign<I, V>(pub I, pub V);
27impl<T:Index<I, Output = V>+IndexMut<I>, I: Copy, V: Copy+Sized> Op<T> for Assign<I, V> where  {
28    #[inline(always)]
29    fn r#do(&mut self, status: &mut T) {
30        std::mem::swap(&mut status[self.0] , &mut self.1)
31    }
32    #[inline(always)]
33    fn undo(&mut self, status: &mut T) {
34        std::mem::swap(&mut status[self.0] , &mut self.1)
35    }
36}
37
38
39
40#[derive(Copy, Clone)]
41pub struct Chain<I:Op<T>, V:Op<T>,T>(I, V,[T;0]);
42impl<T> Chain<(),(),T>{
43    pub fn new()->Chain<(),(),T>{
44        Chain((),(),[])
45    }
46}
47impl<I:Op<T>, V:Op<T>,T> Chain<I, V,T>{
48    pub fn chain<W:Op<T>>(self,op:W)->Chain<Chain<I, V,T>,W,T>{
49        Chain(self,op,[])
50    }
51}
52impl<I:Op<T>, V:Op<T>,T> Op<T> for Chain<I,V,T>{
53    #[inline(always)]
54    fn r#do(&mut self, status: &mut T){
55        self.0.r#do(status);
56        self.1.r#do(status);
57    }
58    #[inline(always)]
59    fn undo(&mut self, status: &mut T){
60        self.1.undo(status);
61        self.0.undo(status);
62    }
63}
64pub struct DFS<
65    'a,
66    I,
67    C: Index<I,Output:Sized> + IndexMut<I>,
68    O: Op<C>,
69    V: FnOnce(&C) -> bool,
70    W: FnOnce(&C) -> X,
71    X: IntoIterator<Item = O>,
72> where <C as Index<I>>::Output:Sized{
73    status: &'a mut C,
74    check: V,
75    get_all_ops: W,
76    op: O,
77    _i:[I;0],
78}
79impl<
80        'a,
81        I,
82        C: Index<I,Output:Sized> + IndexMut<I> + std::fmt::Debug,
83        O: Op<C>,
84        V: Copy + FnOnce(&C) -> bool, // check success
85        W: Copy + FnOnce(&C) -> X,
86        X: IntoIterator<Item = O>,
87    > DFS<'a,I, C, O, V, W, X>
88{
89    pub fn new(
90        status: &'a mut C,
91        check: V,
92        get_all_ops: W,
93        op: O,
94    ) -> Self {
95        Self {
96            status,
97            check,
98            get_all_ops,
99            op,_i:[]
100        }
101    }
102    pub fn dfs<'b>(&'b mut self)
103    where
104        'a: 'b,
105    {
106        if (self.check)(self.status) {
107            return;
108        }
109        for op in (self.get_all_ops)(self.status) {
110            let mut next = self.forward(op);
111            next.dfs();
112        }
113    }
114    pub fn dfs_early_stop<'b>(&'b mut self) -> bool
115    where
116        'a: 'b,
117    {
118        if (self.check)(self.status) {
119            return true;
120        }
121        for op in (self.get_all_ops)(self.status) {
122            let mut next = self.forward(op);
123            if next.dfs_early_stop() {
124                return true;
125            }
126        }
127        false
128    }
129    pub fn forward<'b: 'c, 'c>(&'b mut self, mut op: O) -> DFS<'b,I, C, O, V, W, X>
130    where
131        'b: 'c,
132    {
133        op.r#do(self.status);
134        DFS {
135            status: self.status,
136            check: self.check,
137            get_all_ops: self.get_all_ops,
138            op,_i:[]
139        }
140    }
141}
142impl<
143        'a,
144        I,
145        C: Index<I,Output:Sized> + IndexMut<I>,
146        O: Op<C>,
147        V: FnOnce(&C) -> bool,
148        W: FnOnce(&C) -> X,
149        X: IntoIterator<Item = O>,
150    > Drop for DFS<'a,I, C, O, V, W, X>
151{
152    fn drop(&mut self) {
153        self.op.undo(self.status)
154    }
155}
156
157#[cfg(test)]
158mod tests {
159    use super::*;
160
161    #[test]
162    fn it_works() {
163        const N: usize = 3;
164        {
165            let mut s = [0i32; 2 * N + 1];
166            s[0] = N as i32;
167            let mut a = DFS::<usize,_,_,_,_,_>::new(
168                &mut s,
169                |s: &[i32; 2 * N + 1]| {
170                    if s[0] == 0 {
171                        eprintln!("{s:?}");
172                        true
173                    } else {
174                        false
175                    }
176                },
177                |s: &[i32; 2 * N + 1]| {
178                    let a = s[0];
179                    (1..2 * N as i32 - a)
180                        .filter_map(move |x| {
181                            if s[x as usize] + s[(1 + a + x) as usize] == 0 {
182                                Some(Chain::new().chain(Add(x as usize,a)).chain(Add((1+a+x) as usize,a)).chain(Add(0,-1)))
183                            } else {
184                                None
185                            }
186                        })
187                        .collect::<Vec<_>>()
188                },
189                Chain::new().chain(Add(0,1)).chain(Add(0,1)).chain(Add(0,-2)),
190            );
191            a.dfs();
192            a.dfs_early_stop();
193        }
194    }
195
196    #[test]
197    fn op_works(){
198        let mut a=[0,1,2,3,4,5];
199        let mut b=Add(0,1);
200        b.r#do(&mut a);
201        assert!(a==[1,1,2,3,4,5]);
202        #[derive(Copy, Clone)]
203        struct Swap<I>(I, I);
204        impl Op<[i32;6]> for Swap<usize> {
205            #[inline(always)]
206            fn r#do(&mut self, status: &mut [i32;6]) {
207                status.swap(self.0,self.1)
208            }
209            #[inline(always)]
210            fn undo(&mut self, status: &mut [i32;6]) {
211                status.swap(self.0,self.1)
212            }
213        }
214        let mut c=Swap(4,5);
215        c.r#do(&mut a);
216        assert!(a==[1,1,2,3,5,4]);
217        let mut d=Assign(5,8);
218        d.r#do(&mut a);
219        assert!(a==[1,1,2,3,5,8]);
220        let mut chain=Chain::new().chain(b).chain(c).chain(d);
221        chain.undo(&mut a);
222        assert!(a==[0,1,2,3,4,5]);
223    }
224}
dfs_rs/indexable.rs

dfs_rs/
indexable.rs
