solar_data_structures/
cycle.rs

1use crate::map::FxHashSet;
2use std::ops::ControlFlow;
3
4// NOTE: `Cx` + `fn` emulates a closure. We can't use a closure directly because it would error with
5// `closures cannot capture themselves or take themselves as argument`.
6
7type F<Cx, T, B> = fn(Cx, &mut CycleDetector<Cx, T, B>, T) -> CycleDetectorResult<B, T>;
8
9/// `?` for [`CycleDetectorResult`].
10#[macro_export]
11macro_rules! cdr_try {
12    ($e:expr) => {
13        match $e {
14            CycleDetectorResult::Continue => {}
15            e => return e,
16        }
17    };
18}
19pub use cdr_try;
20
21/// Detector for cycles in directed graphs.
22pub struct CycleDetector<Cx, T, B> {
23    cx: Cx,
24    first_cycle_vertex: Option<T>,
25    depth: u32,
26    processed: FxHashSet<T>,
27    processing: FxHashSet<T>,
28    f: F<Cx, T, B>,
29}
30
31/// Result of [`CycleDetector`].
32pub enum CycleDetectorResult<B, T> {
33    /// Processing continued.
34    Continue,
35    /// Processing stopped from a user-defined break.
36    Break(B),
37    /// A cycle was detected.
38    Cycle(T),
39}
40
41impl<B, T> CycleDetectorResult<B, T> {
42    /// Converts the result to a [`ControlFlow`].
43    pub fn to_controlflow(self) -> ControlFlow<Self> {
44        match self {
45            Self::Continue => ControlFlow::Continue(()),
46            _ => ControlFlow::Break(self),
47        }
48    }
49
50    /// Returns `true` if the result is `Continue`.
51    #[inline]
52    pub fn is_continue(&self) -> bool {
53        matches!(self, Self::Continue)
54    }
55
56    /// Returns `true` if the result is not `Continue`.
57    #[inline]
58    pub fn is_err(&self) -> bool {
59        !self.is_continue()
60    }
61
62    /// Returns the value if the result is `Break`, otherwise `None`.
63    #[inline]
64    pub fn break_value(self) -> Option<B> {
65        match self {
66            Self::Break(b) => Some(b),
67            _ => None,
68        }
69    }
70
71    /// Returns the value if the result is `Cycle`, otherwise `None`.
72    #[inline]
73    pub fn cycle_value(self) -> Option<T> {
74        match self {
75            Self::Cycle(t) => Some(t),
76            _ => None,
77        }
78    }
79}
80
81impl<Cx: Copy, T: Copy + Eq + std::hash::Hash, B> CycleDetector<Cx, T, B> {
82    /// Creates a new cycle detector and runs it on the given vertex.
83    ///
84    /// Returns `Err` if a cycle is detected, containing the first vertex in the cycle.
85    #[inline]
86    pub fn detect(cx: Cx, vertex: T, f: F<Cx, T, B>) -> CycleDetectorResult<B, T> {
87        Self::new(cx, f).run(vertex)
88    }
89
90    /// Creates a new cycle detector.
91    #[inline]
92    pub fn new(cx: Cx, f: F<Cx, T, B>) -> Self {
93        Self {
94            cx,
95            first_cycle_vertex: None,
96            depth: 0,
97            processed: FxHashSet::default(),
98            processing: FxHashSet::default(),
99            f,
100        }
101    }
102
103    /// Runs the cycle detector on the given vertex.
104    ///
105    /// Returns `Err` if a cycle is detected, containing the first vertex in the cycle.
106    #[inline]
107    pub fn run(&mut self, vertex: T) -> CycleDetectorResult<B, T> {
108        cdr_try!(self.cycle_result());
109        if self.processed.contains(&vertex) {
110            return CycleDetectorResult::Continue;
111        }
112        if !self.processing.insert(vertex) {
113            self.first_cycle_vertex = Some(vertex);
114            return CycleDetectorResult::Cycle(vertex);
115        }
116
117        self.depth += 1;
118        cdr_try!((self.f)(self.cx, self, vertex));
119        self.depth -= 1;
120
121        self.processing.remove(&vertex);
122        self.processed.insert(vertex);
123
124        self.cycle_result()
125    }
126
127    #[inline]
128    fn cycle_result(&self) -> CycleDetectorResult<B, T> {
129        match self.first_cycle_vertex {
130            Some(vx) => CycleDetectorResult::Cycle(vx),
131            None => CycleDetectorResult::Continue,
132        }
133    }
134
135    /// Returns the current depth.
136    #[inline]
137    pub fn depth(&self) -> usize {
138        self.depth as usize
139    }
140}
solar_data_structures/cycle.rs

solar_data_structures/
cycle.rs
