dependent_sort/dependent_sort/
mod.rs

1use crate::TopologicalError;
2use std::{
3    cmp::Ordering,
4    collections::{BTreeMap, HashMap, VecDeque},
5    fmt::{Debug, Display},
6    hash::Hash,
7    ops::AddAssign,
8};
9
10mod arithmetic;
11mod display;
12// mod mermaid;
13
14/// A topological sort of tasks with dependencies.
15#[allow(dead_code)]
16#[derive(Debug)]
17pub struct DependentSort<'i, T, G> {
18    /// non-virtualized tasks
19    tasks: Vec<Task<'i, T, G>>,
20    // virtual_group_id: isize,
21    /// Should circular dependencies report an error immediately or declare them at the same time.
22    allow_circular: bool,
23}
24
25/// A task or type who has dependencies and optionally belongs to a group.
26#[derive(Debug)]
27pub struct Task<'i, T, G> {
28    /// The unique identifier of the task.
29    pub id: &'i T,
30    /// The group to which the task belongs.
31    pub group: Option<&'i G>,
32    /// The tasks that this task depends on.
33    pub dependent_tasks: Vec<&'i T>,
34}
35
36/// A group of tasks, if task is not in a group, it will be in a group of its own.
37#[derive(Debug)]
38pub struct Group<'i, T, G> {
39    /// The unique identifier of the group.
40    pub id: Option<&'i G>,
41    /// The tasks that this group contains.
42    pub tasks: Vec<&'i T>,
43}
44
45#[derive(Debug)]
46struct FinalizeDependencies<'i, T, G> {
47    /// maps for recovering the original tasks
48    task_map: Vec<&'i T>,
49    /// maps for recovering the original groups
50    group_map: Vec<&'i G>,
51    /// virtualized tasks
52    virtualized_groups: Vec<isize>,
53    virtualized_dependent_tasks: Vec<Vec<usize>>,
54}
55
56impl<'i, T, G> Task<'i, T, G> {
57    /// Create a new task without dependencies.
58    pub fn new(id: &'i T) -> Self {
59        Self { id, group: None, dependent_tasks: vec![] }
60    }
61    /// Create a new task with given dependencies.
62    pub fn new_with_dependent(id: &'i T, dependent_tasks: Vec<&'i T>) -> Self {
63        Self { id, group: None, dependent_tasks }
64    }
65    /// Set the group to which the task belongs.
66    pub fn with_group(self, group: &'i G) -> Self {
67        Self { group: Some(group), ..self }
68    }
69}
70
71impl<'i, T, G> DependentSort<'i, T, G>
72where
73    T: PartialEq,
74    G: PartialEq,
75{
76    fn finalize(&self) -> Result<FinalizeDependencies<'i, T, G>, TopologicalError<'i, T, G>> {
77        let mut sorter = FinalizeDependencies::default();
78        for task in &self.tasks {
79            sorter.task_map.push(task.id);
80            if let Some(group) = task.group {
81                if !sorter.group_map.contains(&group) {
82                    sorter.group_map.push(group);
83                }
84            }
85        }
86        for task in &self.tasks {
87            sorter.virtualize(task)?;
88        }
89        Ok(sorter)
90    }
91    /// Sort the tasks and return the sorted tasks.
92    pub fn sort(&mut self) -> Result<Vec<Task<'i, T, G>>, TopologicalError<'i, T, G>> {
93        let sorter = self.finalize()?;
94        let sorted = double_topological_sort(
95            sorter.virtualized_groups.clone(),
96            sorter.virtualized_groups.len(),
97            sorter.virtualized_dependent_tasks.clone(),
98        );
99        Ok(sorted.into_iter().map(|i| self.tasks[i as usize].clone()).collect())
100    }
101    /// Sort the tasks and return the sorted tasks grouped by their group.
102    pub fn sort_grouped(&mut self) -> Result<Vec<Group<'i, T, G>>, TopologicalError<'i, T, G>>
103    where
104        G: PartialEq,
105    {
106        let sorted = self.sort()?;
107        let mut group_index_map: Vec<(&G, usize)> = vec![];
108        let mut grouped: Vec<Group<T, G>> = vec![];
109        'outer: for task in sorted {
110            match task.group {
111                Some(s) => {
112                    for (key, position) in group_index_map.iter().map(|(k, v)| (*k, *v)) {
113                        // group has been defined
114                        if key == s {
115                            grouped[position].tasks.push(task.id);
116                            continue 'outer;
117                        }
118                    }
119                    // first appearance of group
120                    group_index_map.push((s, grouped.len()));
121                    grouped.push(Group { id: Some(s), tasks: vec![task.id] })
122                }
123                None => grouped.push(Group { id: None, tasks: vec![task.id] }),
124            }
125        }
126        Ok(grouped)
127    }
128    /// Sort the tasks and return the sorted tasks grouped by their group.
129    pub fn sort_grouped_hash_specialization(&mut self) -> Result<Vec<Group<'i, T, G>>, TopologicalError<'i, T, G>>
130    where
131        G: PartialEq + Eq + Hash,
132    {
133        let sorted = self.sort()?;
134        let mut group_index_map: HashMap<&G, usize> = HashMap::new();
135        let mut grouped: Vec<Group<T, G>> = vec![];
136        for task in sorted {
137            match task.group {
138                Some(s) => match group_index_map.get(s) {
139                    Some(position) => {
140                        grouped[*position].tasks.push(task.id);
141                    }
142                    None => {
143                        let position = grouped.len();
144                        group_index_map.insert(s, position);
145                        grouped.push(Group { id: Some(s), tasks: vec![task.id] })
146                    }
147                },
148                None => grouped.push(Group { id: None, tasks: vec![task.id] }),
149            }
150        }
151        Ok(grouped)
152    }
153}
154
155impl<'i, T, G> FinalizeDependencies<'i, T, G>
156where
157    T: PartialEq,
158    G: PartialEq,
159{
160    fn virtualize(&mut self, task: &Task<'i, T, G>) -> Result<(), TopologicalError<'i, T, G>> {
161        let dependent_tasks = self.virtualize_dependent_tasks(&task.dependent_tasks)?;
162        let group_id = match task.group {
163            Some(reals) => self.virtualize_group(reals)? as isize,
164            None => -1,
165        };
166        self.task_map.push(task.id);
167        self.virtualized_groups.push(group_id);
168        self.virtualized_dependent_tasks.push(dependent_tasks);
169        Ok(())
170    }
171    fn virtualize_group(&self, group: &'i G) -> Result<usize, TopologicalError<'i, T, G>> {
172        match self.group_map.iter().position(|x| *x == group) {
173            Some(index) => Ok(index),
174            None => Err(TopologicalError::MissingGroup { group })?,
175        }
176    }
177    fn virtualize_dependent_tasks(&self, input: &[&'i T]) -> Result<Vec<usize>, TopologicalError<'i, T, G>> {
178        let mut output = Vec::with_capacity(input.len());
179        for task in input {
180            match self.task_map.iter().position(|x| x == task) {
181                Some(index) => output.push(index),
182                None => return Err(TopologicalError::MissingTask { task }),
183            }
184        }
185        Ok(output)
186    }
187}
188
189pub fn double_topological_sort(mut group: Vec<isize>, unique_groups: usize, dependent: Vec<Vec<usize>>) -> Vec<isize> {
190    let n = group.len();
191    let mut in_degree = vec![0; n];
192    let mut adj = vec![vec![]; n];
193    for (item, deps) in dependent.iter().enumerate() {
194        for &dep in deps {
195            adj[dep].push(item);
196            in_degree[item] += 1;
197        }
198    }
199    let items_ids = topological_sort(adj, in_degree);
200    if items_ids.len() != n {
201        return vec![];
202    }
203
204    let mut groups = items_ids.into_iter().fold(vec![vec![]; unique_groups], |mut acc, i| {
205        if group[i] == -1 {
206            group[i] = acc.len() as isize;
207            acc.push(vec![]);
208        }
209        acc[group[i] as usize].push(i as isize);
210        acc
211    });
212
213    let mut group_in_degree = vec![0; groups.len()];
214    let mut group_adj = vec![vec![]; groups.len()];
215    for (item, deps) in dependent.into_iter().enumerate() {
216        for dep in deps {
217            let (src, dst) = (group[dep] as usize, group[item] as usize);
218            if src == dst {
219                continue;
220            }
221            group_adj[src].push(dst);
222            group_in_degree[dst] += 1;
223        }
224    }
225    let group_ids = topological_sort(group_adj, group_in_degree);
226    if group_ids.len() != groups.len() {
227        return vec![];
228    }
229
230    group_ids.into_iter().fold(Vec::new(), |mut acc, i| {
231        acc.append(&mut groups[i]);
232        acc
233    })
234}
235
236fn topological_sort(adj: Vec<Vec<usize>>, mut indeg: Vec<u32>) -> Vec<usize> {
237    let mut q = indeg.iter().enumerate().filter(|(_, &d)| d == 0).map(|(node, _)| node).collect::<VecDeque<_>>();
238    let mut ret = Vec::new();
239    while let Some(node) = q.pop_front() {
240        ret.push(node);
241        for &new_node in adj[node].iter() {
242            indeg[new_node] -= 1;
243            if indeg[new_node] == 0 {
244                q.push_back(new_node)
245            }
246        }
247    }
248    ret
249}
dependent_sort/dependent_sort/mod.rs

dependent_sort/dependent_sort/
mod.rs
