yui_link/link/
path.rs

1use std::{fmt::Display, cmp::min};
2
3use itertools::Itertools;
4
5use crate::{Edge, Link};
6
7#[derive(Debug, Clone, PartialEq, Eq)]
8pub struct Path { 
9    edges:Vec<Edge>,
10    closed:bool
11}
12
13impl Path { 
14    pub fn new<I>(edges: I, closed: bool) -> Self
15    where I: IntoIterator<Item = Edge> { 
16        let edges = edges.into_iter().collect_vec();
17        assert!(!edges.is_empty());
18        Self { edges, closed }
19    }
20
21    pub fn arc<I>(edges: I) -> Self
22    where I: IntoIterator<Item = Edge> { 
23        Self::new(edges, false)
24    }
25
26    pub fn circ<I>(edges: I) -> Self
27    where I: IntoIterator<Item = Edge> { 
28        Self::new(edges, true)
29    }
30
31    pub fn contains(&self, e: Edge) -> bool { 
32        self.edges.contains(&e)
33    }
34
35    pub fn len(&self) -> usize { 
36        self.edges.len()
37    }
38    
39    pub fn edges(&self) -> &Vec<Edge> { 
40        &self.edges
41    }
42
43    pub fn min_edge(&self) -> Edge { 
44        *self.edges.iter().min().unwrap()
45    }
46
47    pub fn ends(&self) -> Option<(Edge, Edge)> { 
48        if self.is_arc() { 
49            let &e0 = self.edges.first().unwrap();
50            let &e1 = self.edges.last().unwrap();
51            Some((e0, e1))
52        } else { 
53            None
54        }
55    }
56
57    pub fn is_arc(&self) -> bool { 
58        !self.closed
59    }
60
61    pub fn is_circle(&self) -> bool { 
62        self.closed
63    }
64
65    pub fn reduce(&mut self) { 
66        if self.is_arc() && self.len() > 2 { 
67            let e0 = self.edges.remove(0);
68            let e1 = self.edges.pop().unwrap();
69            let min = self.edges().iter().filter(|&e| e < min(&e0, &e1)).min();
70
71            self.edges = if let Some(&e2) = min {
72                vec![e0, e2, e1]
73            } else { 
74                vec![e0, e1]
75            };
76        } else if self.is_circle() && self.len() > 1 { 
77            let e0 = *self.edges.iter().min().unwrap();
78            self.edges = vec![e0];
79        }
80    }
81
82    pub fn is_connectable(&self, other: &Self) -> bool { 
83        let Some((e0, e1)) =  self.ends() else { return false };
84        let Some((f0, f1)) = other.ends() else { return false };
85        
86        e0 == f0 || e0 == f1 || e1 == f0 || e1 == f1
87    }
88
89    pub fn is_connectable_bothends(&self, other: &Self) -> bool { 
90        let Some((e0, e1)) =  self.ends() else { return false };
91        let Some((f0, f1)) = other.ends() else { return false };
92
93        (e0, e1) == (f0, f1) || (e0, e1) == (f1, f0)
94    }
95
96    pub fn connect(&mut self, other: Self) { 
97        assert!(self.is_connectable(&other), "{self} and {other} is not connectable.");
98
99        let (e0, e1) =  self.ends().unwrap();
100        let (f0, f1) = other.ends().unwrap();
101
102        let Path {mut edges, ..} = other.clone();
103
104        if e1 == f0 {        // [.., e1) + [f0, ..)
105            edges.remove(0);
106            self.edges.append(&mut edges);
107        } else if e1 == f1 { // [.., e1) + [.., f1)
108            edges.pop();
109            edges.reverse();
110            self.edges.append(&mut edges);
111        } else if e0 == f0 { // [e0, ..) + [f0, ..)
112            edges.remove(0);
113            edges.reverse();
114            edges.append(&mut self.edges);
115            self.edges = edges;
116        } else if e0 == f1 { // [e0, ..) + [.., f1)
117            edges.pop();
118            edges.append(&mut self.edges);
119            self.edges = edges;
120        } else {
121            panic!() // unreachable
122        }
123
124        let (e0, e1) = self.ends().unwrap();
125
126        if e0 == e1 { 
127            self.edges.pop();
128            self.closed = true;
129        }
130    }
131
132    pub fn is_adj(&self, other: &Path, link: &Link) -> bool { 
133        // 1) find crossings `x` that touche `self`. 
134        // 2) check if `x` also touches `other`.
135        
136        for x in link.nodes() { 
137            if !x.edges().iter().any(|e| 
138                self.edges.contains(e)
139            ) { 
140                continue
141            }
142
143            let Some(e) = x.edges().iter().find(|e| 
144                !self.edges.contains(e)
145            ) else { 
146                continue
147            };
148
149            if other.edges.contains(e) { 
150                return true
151            }
152        }
153
154        false
155    }
156
157    fn edge_sum(&self) -> usize { 
158        self.edges.iter().sum()
159    }
160
161    pub fn unori_eq(&self, other: &Self) -> bool {
162        // early failure
163        if self.closed != other.closed ||
164           self.edges.len() != other.edges.len() || 
165           self.edge_sum() != other.edge_sum()
166        { 
167            return false;
168        }
169
170        if self.edges == other.edges { 
171            return true
172        } 
173        
174        if self.closed { 
175            let n = self.edges.len();
176            let Some(p) = other.edges.iter().position(|e| e == &self.edges[0]) else { 
177                return false
178            };
179            (0 .. n).all(|i| self.edges[i] == other.edges[(p + i) % n]) || 
180            (0 .. n).all(|i| self.edges[i] == other.edges[(p + n - i) % n])
181        } else { 
182            Iterator::zip(
183                self.edges.iter(), 
184                other.edges.iter().rev()
185            ).all(|(e, f)| 
186                e == f
187            )
188        }
189    }
190}
191
192impl Display for Path {
193    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
194        let c = self.edges.iter().map(|e| e.to_string()).join("-");
195        if self.is_circle() { 
196            write!(f, "⚪︎({c})")
197        } else {
198            write!(f, "[{c}]")
199        }
200    }
201}
202
203#[cfg(test)]
204mod tests { 
205    use super::*;
206
207    #[test]
208    fn reduce() { 
209        let mut c = Path::new(vec![0], false);
210        c.reduce();
211        assert_eq!(c, Path::new(vec![0], false));
212        
213        let mut c = Path::new(vec![0,1,2,3], false);
214        c.reduce();
215        assert_eq!(c, Path::new(vec![0, 3], false));
216        
217        let mut c = Path::new(vec![0], true);
218        c.reduce();
219        assert_eq!(c, Path::new(vec![0], true));
220
221        let mut c = Path::new(vec![0,1,2,3], true);
222        c.reduce();
223        assert_eq!(c, Path::new(vec![0], true));
224    }
225
226    #[test]
227    fn is_connectable() { 
228        let c = Path::new(vec![1,2,3,4], false);
229
230        assert!( c.is_connectable(&Path::new(vec![4,5], false)));
231        assert!( c.is_connectable(&Path::new(vec![5,4], false)));
232        assert!( c.is_connectable(&Path::new(vec![1,5], false)));
233        assert!( c.is_connectable(&Path::new(vec![5,1], false)));
234        assert!(!c.is_connectable(&Path::new(vec![5,6], false)));
235        assert!(!c.is_connectable(&Path::new(vec![2,3], false)));
236        assert!(!c.is_connectable(&Path::new(vec![0],   true)));
237    }
238
239    #[test]
240    fn is_connectable_bothends() { 
241        let c = Path::new(vec![1,2,3,4], false);
242
243        assert!(!c.is_connectable_bothends(&Path::new(vec![4,5], false)));
244        assert!(!c.is_connectable_bothends(&Path::new(vec![5,4], false)));
245        assert!(!c.is_connectable_bothends(&Path::new(vec![1,5], false)));
246        assert!(!c.is_connectable_bothends(&Path::new(vec![5,1], false)));
247        assert!( c.is_connectable_bothends(&Path::new(vec![1,4], false)));
248        assert!( c.is_connectable_bothends(&Path::new(vec![4,1], false)));
249        assert!(!c.is_connectable_bothends(&Path::new(vec![0],   true)));
250    }
251
252    #[test]
253    fn connect() { 
254        let mut c = Path::new(vec![1,2,3,4], false);
255        c.connect(Path::new(vec![4,5], false));
256        assert_eq!(c, Path::new(vec![1,2,3,4,5], false));
257
258        let mut c = Path::new(vec![1,2,3,4], false);
259        c.connect(Path::new(vec![5,4], false));
260        assert_eq!(c, Path::new(vec![1,2,3,4,5], false));
261
262        let mut c = Path::new(vec![1,2,3,4], false);
263        c.connect(Path::new(vec![6,1], false));
264        assert_eq!(c, Path::new(vec![6,1,2,3,4], false));
265
266        let mut c = Path::new(vec![1,2,3,4], false);
267        c.connect(Path::new(vec![1,6], false));
268        assert_eq!(c, Path::new(vec![6,1,2,3,4], false));
269
270        let mut c = Path::new(vec![1,2,3,4], false);
271        c.connect(Path::new(vec![1], false));
272        assert_eq!(c, Path::new(vec![1,2,3,4], false));
273
274        let mut c = Path::new(vec![1,2,3,4], false);
275        c.connect(Path::new(vec![4], false));
276        assert_eq!(c, Path::new(vec![1,2,3,4], false));
277    }
278
279    #[test]
280    fn unori_eq_arc() { 
281        let c = Path::arc(vec![1,2,3]);
282
283        assert!(c.unori_eq(&Path::arc(vec![1,2,3])));
284        assert!(c.unori_eq(&Path::arc(vec![3,2,1])));
285
286        assert!(!c.unori_eq(&Path::arc(vec![1,2])));
287        assert!(!c.unori_eq(&Path::arc(vec![1,2,3,4])));
288        assert!(!c.unori_eq(&Path::circ(vec![1,2,3])));
289    }
290
291    #[test]
292    fn unori_eq_circ() { 
293        let c = Path::circ(vec![1,2,3,4]);
294
295        assert!(c.unori_eq(&Path::circ(vec![1,2,3,4])));
296        assert!(c.unori_eq(&Path::circ(vec![2,3,4,1])));
297        assert!(c.unori_eq(&Path::circ(vec![3,4,1,2])));
298        assert!(c.unori_eq(&Path::circ(vec![2,3,4,1])));
299        assert!(c.unori_eq(&Path::circ(vec![4,3,2,1])));
300        assert!(c.unori_eq(&Path::circ(vec![3,2,1,4])));
301        
302        assert!(!c.unori_eq(&Path::circ(vec![1,2,3])));
303        assert!(!c.unori_eq(&Path::circ(vec![1,2,3,4,5])));
304        assert!(!c.unori_eq(&Path::circ(vec![1,2,4,3])));
305    }
306}
yui_link/link/path.rs

yui_link/link/
path.rs
