use std::collections::{BTreeMap, BTreeSet, HashSet};
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum Direction {
BottomTop,
LeftRight,
}
pub fn parse(text: impl AsRef<str>) -> BTreeMap<String, BTreeSet<String>> {
use Direction::{BottomTop, LeftRight};
let direction = if text.as_ref().contains('|') {
BottomTop
} else {
LeftRight
};
let lines: Vec<Vec<char>> = text
.as_ref()
.lines()
.map(|line| line.chars().collect())
.collect();
let get = |y: isize, x: isize| -> char {
if y < 0 || x < 0 {
' '
} else {
lines
.get(y as usize)
.cloned()
.map(|line| line.get(x as usize).cloned().unwrap_or(' '))
.unwrap_or(' ')
}
};
let get_name = |y: isize, x: isize| -> String {
(0..x)
.rev()
.map(|x| get(y, x))
.take_while(|&ch| is_name(ch))
.collect::<Vec<_>>()
.into_iter()
.rev()
.chain((x..).map(|x| get(y, x)).take_while(|&ch| is_name(ch)))
.collect()
};
let get_parents = |y: isize, x: isize| -> Vec<String> {
let mut parents = Vec::new();
let mut visited = HashSet::new();
let mut visit = |y, x, expected: &'static str, to_visit: &mut Vec<(isize, isize, &str)>| {
if !visited.contains(&(y, x, expected)) {
visited.insert((y, x, expected));
let ch = get(y, x);
if is_name(ch) && expected.contains('t') {
parents.push(get_name(y, x));
return;
}
if !expected.contains(ch) {
return;
}
match (ch, direction) {
(' ', _) => (),
('|', BottomTop) => {
to_visit.push((y + 1, x - 1, "/"));
to_visit.push((y + 1, x, "|/\\t"));
to_visit.push((y + 1, x + 1, "\\"));
}
('\\', BottomTop) => {
to_visit.push((y + 1, x + 1, "|\\t"));
to_visit.push((y + 1, x, "|t"));
}
('/', BottomTop) => {
to_visit.push((y + 1, x - 1, "|/t"));
to_visit.push((y + 1, x, "|t"));
}
('-', LeftRight) => {
to_visit.push((y - 1, x - 1, "\\"));
to_visit.push((y, x - 1, "-/\\t"));
to_visit.push((y + 1, x - 1, "/"));
}
('\\', LeftRight) => {
to_visit.push((y - 1, x - 1, "-\\t"));
to_visit.push((y, x - 1, "-t"));
}
('/', LeftRight) => {
to_visit.push((y + 1, x - 1, "-/t"));
to_visit.push((y, x - 1, "-t"));
}
_ => unreachable!(),
}
}
};
let mut to_visit: Vec<(isize, isize, &str)> = match direction {
BottomTop => [(y + 1, x - 1, "/"), (y + 1, x, "|"), (y + 1, x + 1, "\\")],
LeftRight => [(y - 1, x - 1, "\\"), (y, x - 1, "-"), (y + 1, x - 1, "/")],
}
.iter()
.cloned()
.filter(|(y, x, expected)| expected.contains(get(*y, *x)))
.collect();
while let Some((y, x, expected)) = to_visit.pop() {
visit(y, x, expected, &mut to_visit);
}
parents
};
let mut edges: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();
for y in 0..lines.len() as isize {
for x in 0..lines[y as usize].len() as isize {
let ch = get(y, x);
if is_name(ch) {
let name = get_name(y, x);
edges.entry(name.clone()).or_default();
for parent in get_parents(y, x) {
edges.get_mut(&name).unwrap().insert(parent);
}
}
match (ch, direction) {
('-', BottomTop) => panic!("'-' is incompatible with BottomTop direction"),
('|', LeftRight) => panic!("'|' is incompatible with LeftRight direction"),
_ => (),
}
}
}
edges
}
pub fn commit(
dag: &BTreeMap<String, BTreeSet<String>>,
mut commit_func: impl FnMut(String, Vec<Box<[u8]>>) -> Box<[u8]>,
) {
let mut committed: BTreeMap<String, Box<[u8]>> = BTreeMap::new();
while committed.len() < dag.len() {
let mut made_progress = false;
for (name, parents) in dag.iter() {
if !committed.contains_key(name)
&& parents.iter().all(|name| committed.contains_key(name))
{
let parent_ids = parents.iter().map(|name| committed[name].clone()).collect();
let new_id = commit_func(name.clone(), parent_ids);
committed.insert(name.to_string(), new_id);
made_progress = true;
}
}
assert!(made_progress, "graph contains cycles");
}
}
pub fn drawdag(
text: impl AsRef<str>,
commit_func: impl FnMut(String, Vec<Box<[u8]>>) -> Box<[u8]>,
) {
commit(&parse(text), commit_func)
}
fn is_name(ch: char) -> bool {
ch.is_alphanumeric()
}
#[cfg(test)]
mod tests {
use super::*;
struct CommitLog {
log: String,
}
impl CommitLog {
fn new() -> Self {
Self { log: String::new() }
}
fn commit(&mut self, name: String, parents: Vec<Box<[u8]>>) -> Box<[u8]> {
let new_id = self.log.chars().filter(|&ch| ch == '\n').count();
let parents_str: Vec<String> = parents
.into_iter()
.map(|p| String::from_utf8(p.into_vec()).unwrap())
.collect();
self.log += &format!(
"{}: {{ parents: {:?}, name: {} }}\n",
new_id, parents_str, name
);
format!("{}", new_id).as_bytes().to_vec().into_boxed_slice()
}
}
fn assert_drawdag(text: &str, expected: &str) {
let mut log = CommitLog::new();
drawdag(text, |n, p| log.commit(n, p));
assert_eq!(log.log, expected);
}
#[test]
#[should_panic]
fn test_drawdag_cycle1() {
let mut log = CommitLog::new();
drawdag("A-B B-A", |n, p| log.commit(n, p));
}
#[test]
#[should_panic]
fn test_drawdag_cycle2() {
let mut log = CommitLog::new();
drawdag("A-B-C-A", |n, p| log.commit(n, p));
}
#[test]
fn test_drawdag() {
assert_drawdag(
"A-C-B",
r#"0: { parents: [], name: A }
1: { parents: ["0"], name: C }
2: { parents: ["1"], name: B }
"#,
);
assert_drawdag(
r#"
C-D-\ /--I--J--\
A-B------E-F-G-H--------K--L"#,
r#"0: { parents: [], name: A }
1: { parents: ["0"], name: B }
2: { parents: [], name: C }
3: { parents: ["2"], name: D }
4: { parents: ["1", "3"], name: E }
5: { parents: ["4"], name: F }
6: { parents: ["5"], name: G }
7: { parents: ["6"], name: H }
8: { parents: ["6"], name: I }
9: { parents: ["8"], name: J }
10: { parents: ["7", "9"], name: K }
11: { parents: ["10"], name: L }
"#,
);
assert_drawdag(
r#"
G
|
I D C F
\ \| |
H B E
\|/
A
"#,
r#"0: { parents: [], name: A }
1: { parents: ["0"], name: B }
2: { parents: ["1"], name: C }
3: { parents: ["1"], name: D }
4: { parents: ["0"], name: E }
5: { parents: ["4"], name: F }
6: { parents: ["5"], name: G }
7: { parents: ["0"], name: H }
8: { parents: ["7"], name: I }
"#,
);
assert_drawdag(
r#"
A
/|\
H B E
/ /| |
I D C F
|
G
"#,
r#"0: { parents: [], name: C }
1: { parents: [], name: D }
2: { parents: [], name: G }
3: { parents: [], name: I }
4: { parents: ["0", "1"], name: B }
5: { parents: ["2"], name: F }
6: { parents: ["3"], name: H }
7: { parents: ["5"], name: E }
8: { parents: ["4", "7", "6"], name: A }
"#,
);
}
}