use std::collections::BTreeMap;
use std::ops::Range;
use bitflags::bitflags;
#[cfg(feature = "serialize")]
use serde::Serialize;
use super::column::Column;
use super::column::ColumnsExt;
use super::output::OutputRendererBuilder;
pub trait Renderer<N> {
type Output;
fn width(&self, new_node: Option<&N>, new_parents: Option<&Vec<Ancestor<N>>>) -> u64;
fn reserve(&mut self, node: N);
fn next_row(
&mut self,
node: N,
parents: Vec<Ancestor<N>>,
glyph: String,
message: String,
) -> Self::Output;
}
pub struct GraphRowRenderer<N> {
columns: Vec<Column<N>>,
}
pub enum Ancestor<N> {
Ancestor(N),
Parent(N),
Anonymous,
}
impl<N> Ancestor<N> {
fn to_column(&self) -> Column<N>
where
N: Clone,
{
match self {
Ancestor::Ancestor(n) => Column::Ancestor(n.clone()),
Ancestor::Parent(n) => Column::Parent(n.clone()),
Ancestor::Anonymous => Column::Blocked,
}
}
fn id(&self) -> Option<&N> {
match self {
Ancestor::Ancestor(n) => Some(&n),
Ancestor::Parent(n) => Some(&n),
Ancestor::Anonymous => None,
}
}
fn is_direct(&self) -> bool {
match self {
Ancestor::Ancestor(_) => false,
Ancestor::Parent(_) => true,
Ancestor::Anonymous => true,
}
}
fn to_link_line(&self, direct: LinkLine, indirect: LinkLine) -> LinkLine {
if self.is_direct() { direct } else { indirect }
}
}
struct AncestorColumnBounds {
target: usize,
min_ancestor: usize,
min_parent: usize,
max_parent: usize,
max_ancestor: usize,
}
impl AncestorColumnBounds {
fn new<N>(columns: &BTreeMap<usize, &Ancestor<N>>, target: usize) -> Option<Self> {
if columns.is_empty() {
return None;
}
let min_ancestor = columns
.iter()
.next()
.map_or(target, |(index, _)| *index)
.min(target);
let max_ancestor = columns
.iter()
.next_back()
.map_or(target, |(index, _)| *index)
.max(target);
let min_parent = columns
.iter()
.find(|(_, ancestor)| ancestor.is_direct())
.map_or(target, |(index, _)| *index)
.min(target);
let max_parent = columns
.iter()
.rev()
.find(|(_, ancestor)| ancestor.is_direct())
.map_or(target, |(index, _)| *index)
.max(target);
Some(Self {
target,
min_ancestor,
min_parent,
max_parent,
max_ancestor,
})
}
fn range(&self) -> Range<usize> {
if self.min_ancestor < self.max_ancestor {
self.min_ancestor + 1..self.max_ancestor
} else {
Default::default()
}
}
fn horizontal_line(&self, index: usize) -> LinkLine {
if index == self.target {
LinkLine::empty()
} else if index > self.min_parent && index < self.max_parent {
LinkLine::HORIZ_PARENT
} else if index > self.min_ancestor && index < self.max_ancestor {
LinkLine::HORIZ_ANCESTOR
} else {
LinkLine::empty()
}
}
}
impl<N> Column<N> {
fn to_node_line(&self) -> NodeLine {
match self {
Column::Ancestor(_) => NodeLine::Ancestor,
Column::Parent(_) => NodeLine::Parent,
_ => NodeLine::Blank,
}
}
fn to_link_line(&self) -> LinkLine {
match self {
Column::Ancestor(_) => LinkLine::VERT_ANCESTOR,
Column::Parent(_) => LinkLine::VERT_PARENT,
_ => LinkLine::empty(),
}
}
fn to_pad_line(&self) -> PadLine {
match self {
Column::Ancestor(_) => PadLine::Ancestor,
Column::Parent(_) => PadLine::Parent,
_ => PadLine::Blank,
}
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(Serialize))]
pub enum NodeLine {
Blank,
Ancestor,
Parent,
Node,
}
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(Serialize))]
pub enum PadLine {
Blank,
Ancestor,
Parent,
}
bitflags! {
#[derive(Default)]
#[cfg_attr(feature = "serialize", derive(Serialize))]
pub struct LinkLine: u16 {
const HORIZ_PARENT = 0b0_0000_0000_0001;
const HORIZ_ANCESTOR = 0b0_0000_0000_0010;
const VERT_PARENT = 0b0_0000_0000_0100;
const VERT_ANCESTOR = 0b0_0000_0000_1000;
const LEFT_FORK_PARENT = 0b0_0000_0001_0000;
const LEFT_FORK_ANCESTOR = 0b0_0000_0010_0000;
const RIGHT_FORK_PARENT = 0b0_0000_0100_0000;
const RIGHT_FORK_ANCESTOR = 0b0_0000_1000_0000;
const LEFT_MERGE_PARENT = 0b0_0001_0000_0000;
const LEFT_MERGE_ANCESTOR = 0b0_0010_0000_0000;
const RIGHT_MERGE_PARENT = 0b0_0100_0000_0000;
const RIGHT_MERGE_ANCESTOR = 0b0_1000_0000_0000;
const CHILD = 0b1_0000_0000_0000;
const HORIZONTAL = Self::HORIZ_PARENT.bits | Self::HORIZ_ANCESTOR.bits;
const VERTICAL = Self::VERT_PARENT.bits | Self::VERT_ANCESTOR.bits;
const LEFT_FORK = Self::LEFT_FORK_PARENT.bits | Self::LEFT_FORK_ANCESTOR.bits;
const RIGHT_FORK = Self::RIGHT_FORK_PARENT.bits | Self::RIGHT_FORK_ANCESTOR.bits;
const LEFT_MERGE = Self::LEFT_MERGE_PARENT.bits | Self::LEFT_MERGE_ANCESTOR.bits;
const RIGHT_MERGE = Self::RIGHT_MERGE_PARENT.bits | Self::RIGHT_MERGE_ANCESTOR.bits;
const ANY_MERGE = Self::LEFT_MERGE.bits | Self::RIGHT_MERGE.bits;
const ANY_FORK = Self::LEFT_FORK.bits | Self::RIGHT_FORK.bits;
const ANY_FORK_OR_MERGE = Self::ANY_MERGE.bits | Self::ANY_FORK.bits;
}
}
#[derive(Debug)]
#[cfg_attr(feature = "serialize", derive(Serialize))]
pub struct GraphRow<N> {
pub node: N,
pub glyph: String,
pub message: String,
pub merge: bool,
pub node_line: Vec<NodeLine>,
pub link_line: Option<Vec<LinkLine>>,
pub term_line: Option<Vec<bool>>,
pub pad_lines: Vec<PadLine>,
}
impl<N> GraphRowRenderer<N>
where
N: Clone + Eq,
{
pub fn new() -> Self {
GraphRowRenderer {
columns: Vec::new(),
}
}
pub fn output(self) -> OutputRendererBuilder<N, Self> {
OutputRendererBuilder::new(self)
}
}
impl<N> Renderer<N> for GraphRowRenderer<N>
where
N: Clone + Eq,
{
type Output = GraphRow<N>;
fn width(&self, node: Option<&N>, parents: Option<&Vec<Ancestor<N>>>) -> u64 {
let mut width = self.columns.len();
let mut empty_columns = self
.columns
.iter()
.filter(|&column| column == &Column::Empty)
.count();
if let Some(node) = node {
if self.columns.find(&node).is_none() {
if empty_columns == 0 {
width += 1;
} else {
empty_columns = empty_columns.saturating_sub(1);
}
}
}
if let Some(parents) = parents {
let unallocated_parents = parents
.iter()
.filter(|parent| {
parent
.id()
.map_or(true, |parent| self.columns.find(&parent).is_none())
})
.count()
.saturating_sub(empty_columns);
width += unallocated_parents.saturating_sub(1);
}
width as u64
}
fn reserve(&mut self, node: N) {
if self.columns.find(&node).is_none() {
if let Some(index) = self.columns.first_empty() {
self.columns[index] = Column::Reserved(node);
} else {
self.columns.push(Column::Reserved(node));
}
}
}
fn next_row(
&mut self,
node: N,
parents: Vec<Ancestor<N>>,
glyph: String,
message: String,
) -> GraphRow<N> {
let column = self.columns.find(&node).unwrap_or_else(|| {
self.columns
.first_empty()
.unwrap_or_else(|| self.columns.new_empty())
});
self.columns[column] = Column::Empty;
let merge = parents.len() > 1;
let mut node_line: Vec<_> = self.columns.iter().map(|c| c.to_node_line()).collect();
node_line[column] = NodeLine::Node;
let mut link_line: Vec<_> = self.columns.iter().map(|c| c.to_link_line()).collect();
let mut need_link_line = false;
let mut term_line: Vec<_> = self.columns.iter().map(|_| false).collect();
let mut need_term_line = false;
let mut pad_lines: Vec<_> = self.columns.iter().map(|c| c.to_pad_line()).collect();
let mut parent_columns = BTreeMap::new();
for p in parents.iter() {
if let Some(parent_id) = p.id() {
if let Some(index) = self.columns.find(parent_id) {
self.columns[index].merge(&p.to_column());
parent_columns.insert(index, p);
continue;
}
}
if let Some(index) = self.columns.find_empty(column) {
self.columns[index].merge(&p.to_column());
parent_columns.insert(index, p);
continue;
}
parent_columns.insert(self.columns.len(), p);
node_line.push(NodeLine::Blank);
pad_lines.push(PadLine::Blank);
link_line.push(LinkLine::default());
term_line.push(false);
self.columns.push(p.to_column());
}
for (i, p) in parent_columns.iter() {
if p.id().is_none() {
term_line[*i] = true;
need_term_line = true;
}
}
if parents.len() == 1 {
if let Some((&parent_column, _)) = parent_columns.iter().next() {
if parent_column > column {
self.columns.swap(column, parent_column);
let parent = parent_columns
.remove(&parent_column)
.expect("parent should exist");
parent_columns.insert(column, parent);
let was_direct = link_line[parent_column].contains(LinkLine::VERT_PARENT);
link_line[column] |= if was_direct {
LinkLine::RIGHT_FORK_PARENT
} else {
LinkLine::RIGHT_FORK_ANCESTOR
};
#[allow(clippy::needless_range_loop)]
for i in column + 1..parent_column {
link_line[i] |= if was_direct {
LinkLine::HORIZ_PARENT
} else {
LinkLine::HORIZ_ANCESTOR
};
}
link_line[parent_column] = if was_direct {
LinkLine::LEFT_MERGE_PARENT
} else {
LinkLine::LEFT_MERGE_ANCESTOR
};
need_link_line = true;
pad_lines[parent_column] = PadLine::Blank;
}
}
}
if let Some(bounds) = AncestorColumnBounds::new(&parent_columns, column) {
for i in bounds.range() {
link_line[i] |= bounds.horizontal_line(i);
need_link_line = true;
}
if bounds.max_parent > column {
link_line[column] |= LinkLine::RIGHT_MERGE_PARENT;
need_link_line = true;
} else if bounds.max_ancestor > column {
link_line[column] |= LinkLine::RIGHT_MERGE_ANCESTOR;
need_link_line = true;
}
if bounds.min_parent < column {
link_line[column] |= LinkLine::LEFT_MERGE_PARENT;
need_link_line = true;
} else if bounds.min_ancestor < column {
link_line[column] |= LinkLine::LEFT_MERGE_ANCESTOR;
need_link_line = true;
}
#[allow(clippy::comparison_chain)]
for (&i, p) in parent_columns.iter() {
pad_lines[i] = self.columns[i].to_pad_line();
if i < column {
link_line[i] |=
p.to_link_line(LinkLine::RIGHT_FORK_PARENT, LinkLine::RIGHT_FORK_ANCESTOR);
} else if i == column {
link_line[i] |= LinkLine::CHILD
| p.to_link_line(LinkLine::VERT_PARENT, LinkLine::VERT_ANCESTOR);
} else {
link_line[i] |=
p.to_link_line(LinkLine::LEFT_FORK_PARENT, LinkLine::LEFT_FORK_ANCESTOR);
}
}
}
self.columns.reset();
let link_line = Some(link_line).filter(|_| need_link_line);
let term_line = Some(term_line).filter(|_| need_term_line);
GraphRow {
node,
glyph,
message,
merge,
node_line,
link_line,
term_line,
pad_lines,
}
}
}