1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110

// See the LICENSE files at the top-level directory of this distribution.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! Printing-related traits and implementations.

use std::fmt;
use std::hash::Hash;
use std::io::{Result as IoRes, Write};

use crate::{Zdd, ZddTree, ZddTreeOps};

/// Printing and logging to graphviz.
pub trait ZddPrint<Label> {
    /// Pretty prints a ZDD with a prefix.
    fn print(&self, pref: String);
    /// Logs a ZDD as graphviz to a `Write`.
    fn write_as_gv(&self, w: &mut impl Write) -> IoRes<()>;
}

/// Prints a ZDD as a graphviz graph to a `Write`.
fn graph_print<Label: Hash + Clone + fmt::Display + Ord>(
    wrt: &mut impl Write,
    zdd: &Zdd<Label>,
    root: &'static str,
    zero: &'static str,
) -> IoRes<()> {
    use std::collections::HashSet;
    let mut mem = HashSet::new();

    let mut to_do = vec![(root.to_string(), "", false, zdd.clone())];
    let has_one_style = " arrowtail=odot  dir=both";

    loop {
        if let Some((parent, edge_lbl, has_one, zdd)) = to_do.pop() {
            let style = if has_one { has_one_style } else { "" };
            match zdd.get() {
                &ZddTree::Zero => {
                    write!(wrt, "  {} -> {} [{}{}] ;\n", parent, zero, edge_lbl, style)?
                }
                &ZddTree::HasOne(ref kid) => to_do.push((parent, edge_lbl, true, kid.clone())),
                &ZddTree::Node(ref lbl, ref left, ref right) => {
                    let name = zdd.uid().to_string();
                    write!(wrt, "  {} [label=\"{}\"] ; \n", name, lbl)?;
                    write!(wrt, "  {} -> {} [{}{}] ;\n", parent, name, edge_lbl, style)?;
                    if !mem.contains(&zdd) {
                        mem.insert(zdd.clone());
                        to_do.push((name.clone(), "arrowhead=empty", false, right.clone()));
                        to_do.push((name, "", false, left.clone()))
                    }
                }
            }
        } else {
            return Ok(());
        }
    }
}

impl<Label: fmt::Display + Ord + Clone + Hash> ZddPrint<Label> for Zdd<Label> {
    fn print(&self, pref: String) {
        println!("{}{{", pref);
        for vec in self.iter() {
            print!("{}  {{ ", pref);
            let mut first = true;
            for e in vec.into_iter() {
                print!(
                    "{}{}",
                    if first {
                        first = false;
                        ""
                    } else {
                        ", "
                    },
                    e
                )
            }
            println!(" }}");
        }
        println!("{}}}", pref)
    }

    fn write_as_gv(&self, wrt: &mut impl Write) -> IoRes<()> {
        let root = "root_of_the_zdd";
        let zero = "zero_of_the_zdd";
        write!(wrt, "digraph {{\n\n")?;
        write!(wrt, "    graph [bgcolor=black margin=0.0];\n")?;
        write!(wrt, "    node [style=invisible]; {};\n\n", root)?;
        write!(
            wrt,
            "    \
            node [ style=filled  fillcolor=black  fontcolor=\"#1e90ff\"  color=\"#666666\" ] ;\n"
        )?;
        write!(
            wrt,
            "  edge [color=\"#1e90ff\" fontcolor=\"#222222\"] ;\n\n"
        )?;
        write!(
            wrt,
            "  node [shape=doublecircle] ; {} [label=\"{{}}\"] ;\n",
            zero
        )?;
        write!(wrt, "  node [shape=circle] ;\n")?;
        graph_print(wrt, self, root, zero)?;
        write!(wrt, "}}\n")
    }
}