yui_link/link/
node.rs

1//! [`Node`]: one vertex of a diagram — a crossing (`XL`/`XR`) or a smoothing
2//! (`V`/`H`) — its four incident edges, and the orientation given by the pair of
3//! [`Slot`]s the two strands enter by.
4//!
5//! The four [`NodeType`]s, with the incident edges numbered counter-clockwise
6//! from the lower left (`0 = SW`, `1 = SE`, `2 = NE`, `3 = NW`):
7//!
8//! ```text
9//!     3   2         3   2         3   2         3   2
10//!      \ /           \ /           \ /           \_/
11//!       \    = XL,    /    = XR,   | |   = V,     _    = H
12//!      / \           / \           / \           / \
13//!     0   1         0   1         0   1         0   1
14//! ```
15
16use std::fmt::Display;
17
18use yui_core::bitseq::Bit;
19use yui_core::num::Sign;
20use yui_core::ext::CloneAnd;
21
22use crate::Path;
23use super::Edge;
24
25use NodeType::{XL, XR, V, H};
26
27/// One of a node's four ends, counter-clockwise from the lower left
28/// (see the module diagram).
29#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, derive_more::Display, Debug)]
30pub enum Slot {
31    SW, SE, NE, NW
32}
33
34impl Slot {
35    pub const ALL: [Slot; 4] = [Slot::SW, Slot::SE, Slot::NE, Slot::NW];
36
37    pub fn index(&self) -> usize {
38        *self as usize
39    }
40
41    // the slot `k` steps counter-clockwise from this one.
42    pub fn shift(&self, k: usize) -> Self {
43        Self::from((self.index() + k) % 4)
44    }
45}
46
47impl From<usize> for Slot {
48    fn from(i: usize) -> Self {
49        Self::ALL.get(i).copied().unwrap_or_else(|| panic!("slot {i} out of range"))
50    }
51}
52
53#[derive(Clone, Copy, PartialEq, Eq, Hash, derive_more::Display, Debug)]
54pub enum NodeType {
55    XL, XR, V, H
56}
57
58impl NodeType {
59    // The slot at the other end of the strand passing through `slot` — the strand pairing.
60    pub fn paired_slot(&self, slot: Slot) -> Slot {
61        let i = slot.index();
62        Slot::from(match self {
63            XL | XR => (i + 2) % 4,   // SW<->NE, SE<->NW
64            V => 3 - i,               // SW<->NW, SE<->NE
65            H => i ^ 1,               // SW<->SE, NE<->NW
66        })
67    }
68
69    pub fn mirror(&self) -> Self {
70        match self {
71            XL => XR,
72            XR => XL,
73            _  => *self
74        }
75    }
76}
77
78#[derive(Debug, Clone, PartialEq, Eq, Hash)]
79pub struct Node {
80    node_type: NodeType,
81    // the two slots where the strands enter, sorted; `None` when the node is not coherently
82    // oriented. The two must lie on different strands — see `Node::orientable`.
83    incoming: Option<(Slot, Slot)>,
84    edges: [Edge; 4],
85}
86
87impl Node {
88    pub fn new(node_type: NodeType, incoming: Option<(Slot, Slot)>, edges: [Edge; 4]) -> Self {
89        let incoming = incoming.map(|(p, q)| (p.min(q), p.max(q)));
90        assert!(
91            incoming.is_none_or(|(p, q)| Self::orientable(node_type, p, q)),
92            "the two incoming slots must lie on different strands of {node_type}: {incoming:?}"
93        );
94        Node { node_type, edges, incoming }
95    }
96
97    pub fn from_pd_code(edges: [Edge; 4]) -> Self {
98        Node::new(NodeType::XL, None, edges)
99    }
100
101    // A node is coherently oriented only when its two incoming slots sit on different strands;
102    // `paired_slot` is the strand pairing.
103    pub fn orientable(node_type: NodeType, p: Slot, q: Slot) -> bool {
104        p != q && node_type.paired_slot(p) != q
105    }
106
107    pub fn node_type(&self) -> NodeType {
108        self.node_type
109    }
110
111    pub fn edge(&self, s: Slot) -> Edge {
112        self.edges[s.index()]
113    }
114
115    pub fn edges(&self) -> &[Edge; 4] {
116        &self.edges
117    }
118
119    pub fn min_edge(&self) -> Edge {
120        *self.edges.iter().min().unwrap()
121    }
122
123    pub fn is_crossing(&self) -> bool {
124        matches!(self.node_type, XL | XR)
125    }
126
127    pub fn is_resolved(&self) -> bool {
128        matches!(self.node_type, V | H)
129    }
130
131    pub fn resolve(&self, r: Bit) -> Self {
132        use Bit::{Bit0, Bit1};
133
134        self.clone_and(|x| {
135            x.node_type = match (x.node_type, r) {
136                (XL, Bit0) | (XR, Bit1) => H,
137                (XL, Bit1) | (XR, Bit0) => V,
138                _ => panic!("cannot resolve node-type: {}", x.node_type)
139            };
140
141            // the smoothing re-pairs the strands, so an orientation survives only one of the two:
142            // incoming {0,1}/{2,3} survives V, incoming {1,2}/{0,3} survives H.
143            if x.incoming.is_some_and(|(p, q)| !Self::orientable(x.node_type, p, q)) {
144                x.incoming = None
145            }
146        })
147    }
148
149    pub fn is_oriented(&self) -> bool {
150        self.incoming.is_some()
151    }
152
153    // The two slots where the strands enter, sorted.
154    pub fn incoming(&self) -> Option<(Slot, Slot)> {
155        self.incoming
156    }
157
158    // False on an unoriented node, where no slot is claimed either way.
159    pub fn is_incoming(&self, s: Slot) -> bool {
160        self.incoming.is_some_and(|(p, q)| p == s || q == s)
161    }
162
163    // Goes through `new`, so the pair is sorted and validated however the caller passes it.
164    pub(crate) fn set_incoming(&mut self, incoming: Option<(Slot, Slot)>) {
165        *self = Self::new(self.node_type, incoming, self.edges);
166    }
167
168    pub fn is_pos(&self) -> bool {
169        self.sign().map(|x| x.is_positive()).unwrap_or(false)
170    }
171
172    pub fn is_neg(&self) -> bool {
173        self.sign().map(|x| x.is_negative()).unwrap_or(false)
174    }
175
176    // Only a crossing has a sign, read off the type and which pair of slots the strands enter by.
177    pub fn sign(&self) -> Option<Sign> {
178        use Slot::{SW, SE, NE, NW};
179        match (self.node_type, self.incoming?) {
180            (XL, (SE, NE)) | (XL, (SW, NW)) | (XR, (SW, SE)) | (XR, (NE, NW)) => Some(Sign::Pos),
181            (XL, (SW, SE)) | (XL, (NE, NW)) | (XR, (SE, NE)) | (XR, (SW, NW)) => Some(Sign::Neg),
182            _ => None,
183        }
184    }
185
186    pub fn mirror(&self) -> Self {
187        self.clone_and(|x|
188            x.node_type = self.node_type.mirror()
189        )
190    }
191
192    // Reverse both strands: each now enters by the slot it used to leave. The two incoming slots
193    // stay on different strands, so orientability — and the sign — survive.
194    pub fn reversed(&self) -> Self {
195        self.clone_and(|x|
196            x.incoming = self.incoming.map(|(p, q)| {
197                let (p, q) = (self.paired_slot(p), self.paired_slot(q));
198                (p.min(q), p.max(q))
199            })
200        )
201    }
202
203    pub fn is_adj_to(&self, x: &Node) -> bool {
204        self.edges.iter().any(|e| x.edges.contains(e))
205    }
206
207    pub fn arcs(&self) -> (Path, Path) {
208        let comp = |i: usize, j: usize| {
209            let (ei, ej) = (self.edges[i], self.edges[j]);
210            if ei == ej {
211                Path::circ([ei])
212            } else {
213                Path::arc([ei, ej])
214            }
215        };
216        match self.node_type {
217            XL |
218            XR => (comp(0, 2), comp(1, 3)),
219            V  => (comp(0, 3), comp(1, 2)),
220            H  => (comp(0, 1), comp(2, 3))
221        }
222    }
223
224    pub fn convert_edges<F>(&self, f: F) -> Self
225    where F: Fn(Edge) -> Edge {
226        Self {
227            node_type: self.node_type,
228            incoming: self.incoming,
229            edges: self.edges.map(f)
230        }
231    }
232
233    pub fn paired_slot(&self, s: Slot) -> Slot {
234        self.node_type.paired_slot(s)
235    }
236}
237
238impl Display for Node {
239    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
240        write!(f, "{}{:?}", self.node_type, self.edges)
241    }
242}
243
244#[cfg(test)]
245mod tests {
246    use super::*;
247
248    // the four orientations a crossing can carry, by the direction the strands run.
249    const UP:    Option<(Slot, Slot)> = Some((Slot::SW, Slot::SE));
250    const LEFT:  Option<(Slot, Slot)> = Some((Slot::SE, Slot::NE));
251    const DOWN:  Option<(Slot, Slot)> = Some((Slot::NE, Slot::NW));
252    const RIGHT: Option<(Slot, Slot)> = Some((Slot::SW, Slot::NW));
253
254    fn node(ntype: NodeType, incoming: Option<(Slot, Slot)>) -> Node {
255        Node::new(ntype, incoming, [0, 1, 2, 3])
256    }
257
258    #[test]
259    fn test_is_resolved() {
260        for ntype in [XL, XR] {
261            let c = node(ntype, None);
262            assert!(c.is_crossing());
263            assert!(!c.is_resolved());
264        }
265        for ntype in [V, H] {
266            let c = node(ntype, None);
267            assert!(!c.is_crossing());
268            assert!(c.is_resolved());
269        }
270    }
271
272    #[test]
273    fn test_resolve() {
274        use Bit::{Bit0, Bit1};
275
276        // (ntype, incoming, bit, expected_ntype, expected_incoming)
277        let cases = [
278            (XL, None, Bit0, H, None),
279            (XL, None, Bit1, V, None),
280            (XR, None, Bit0, V, None),
281            (XR, None, Bit1, H, None),
282            // an orientation survives exactly one of the two smoothings: the one that leaves the
283            // two incoming slots on different strands.
284            (XL, UP,   Bit1, V, UP),
285            (XL, LEFT, Bit0, H, LEFT),
286            (XL, UP,   Bit0, H, None),
287            (XL, LEFT, Bit1, V, None),
288            (XR, LEFT, Bit0, V, None),
289            (XR, UP,   Bit1, H, None),
290        ];
291
292        for (ntype, incoming, bit, expected_ntype, expected) in cases {
293            let c = node(ntype, incoming).resolve(bit);
294            assert!(c.is_resolved());
295            assert_eq!(c.node_type(), expected_ntype);
296            assert_eq!(c.incoming(), expected);
297        }
298    }
299
300    #[test]
301    fn test_anti_parallel() {
302        // A resolved node may have its two strands running opposite ways — the diagonal slot pairs,
303        // which no crossing can carry. `resolve` never produces them, but a V/H diagram oriented in
304        // its own right does (e.g. orienting the circles of a resolution).
305        for ntype in [V, H] {
306            for (a, b) in [(Slot::SW, Slot::NE), (Slot::SE, Slot::NW)] {
307                let pair = (a, b);
308                assert!(Node::orientable(ntype, pair.0, pair.1));
309                assert_eq!(node(ntype, Some(pair)).incoming(), Some(pair));
310            }
311        }
312        for ntype in [XL, XR] {
313            assert!(!Node::orientable(ntype, Slot::SW, Slot::NE), "a crossing's diagonal is one strand");
314            assert!(!Node::orientable(ntype, Slot::SE, Slot::NW));
315        }
316    }
317
318    #[test]
319    fn test_mirror() {
320        // mirror flips XL <-> XR and preserves the orientation.
321        let cases = [
322            (XL, None,  XR, None),
323            (XR, None,  XL, None),
324            (H,  None,  H,  None),
325            (V,  None,  V,  None),
326            (XL, UP,    XR, UP),
327            (XR, LEFT,  XL, LEFT),
328            (V,  DOWN,  V,  DOWN),
329            (H,  RIGHT, H,  RIGHT),
330        ];
331
332        for (ntype, incoming, expected_ntype, expected) in cases {
333            let c = node(ntype, incoming).mirror();
334            assert_eq!(c.node_type(), expected_ntype);
335            assert_eq!(c.incoming(), expected);
336        }
337    }
338
339    #[test]
340    fn test_sign() {
341        let cases = [
342            (XL, LEFT,  Some(Sign::Pos)),
343            (XL, RIGHT, Some(Sign::Pos)),
344            (XR, UP,    Some(Sign::Pos)),
345            (XR, DOWN,  Some(Sign::Pos)),
346            (XL, UP,    Some(Sign::Neg)),
347            (XL, DOWN,  Some(Sign::Neg)),
348            (XR, LEFT,  Some(Sign::Neg)),
349            (XR, RIGHT, Some(Sign::Neg)),
350            // unsigned: no orientation, or a resolved node.
351            (XL, None,  Option::None),
352            (XR, None,  Option::None),
353            (V,  UP,    Option::None),
354            (V,  DOWN,  Option::None),
355            (H,  LEFT,  Option::None),
356            (H,  RIGHT, Option::None),
357            (V,  None,  Option::None),
358            (H,  None,  Option::None),
359        ];
360
361        for (ntype, incoming, expected) in cases {
362            assert_eq!(node(ntype, incoming).sign(), expected);
363        }
364    }
365
366    #[test]
367    fn test_traverse() {
368        let cases = [
369            (XL, [2, 3, 0, 1]),
370            (XR, [2, 3, 0, 1]),
371            (V,  [3, 2, 1, 0]),
372            (H,  [1, 0, 3, 2]),
373        ];
374        for (ntype, expected) in cases {
375            let c = node(ntype, None);
376            for s in Slot::ALL {
377                assert_eq!(c.paired_slot(s), Slot::from(expected[s.index()]));
378            }
379        }
380    }
381}
yui_link/link/node.rs

yui_link/link/
node.rs
