algorithms_fourth 0.1.10

use std::{
    fmt::Display,
    ops::{Deref, DerefMut},
};

use crate::search::ST;

use super::{Node, RedBlackBST};

#[derive(Clone)]
struct Element<'a, K: PartialOrd + Display, V> {
    p_id: usize,
    id: usize,
    level: usize,
    label: String,
    node: &'a Node<K, V>,
    is_left: bool,
}
pub struct TraceRedBlackBST<K: PartialOrd + Display, V>(RedBlackBST<K, V>, Vec<String>);

pub fn new<K: PartialOrd + Display, V>(
    red_black_bst: RedBlackBST<K, V>,
    graph: Vec<String>,
) -> TraceRedBlackBST<K, V> {
    TraceRedBlackBST(red_black_bst, graph)
}
impl<K: PartialOrd + Display, V: Display> Deref for TraceRedBlackBST<K, V> {
    type Target = RedBlackBST<K, V>;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl<K: PartialOrd + Display, V: Display> DerefMut for TraceRedBlackBST<K, V> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}
fn generate_element<K: PartialOrd + Display, V: Display>(
    node: &Node<K, V>,
    p_id: usize,
    id: usize,
    level: usize,
    is_left: bool,
) -> Element<K, V> {
    // let label = format!( r#" <l>|{{key:{}|val:{}|n:{}}}|<r> "#, node.key, node.val, node.n);
    let label = format!(
        r#"<<table border="0" cellspacing="10" cellpadding="10" style="rounded" bgcolor="/rdylgn11/1:/rdylgn11/11"> <tr>
        <td port="l"></td>
        <td>key:{}<br/>val:{}<br/>n:{}<br/>level:{}</td>
        <td port="r"></td>
        </tr> </table>>
     "#,
        node.key, node.val, node.n, level
    );
    Element {
        p_id,
        id,
        level,
        node,
        is_left,
        label,
    }
}
impl<K,V> TraceRedBlackBST<K, V> where K: PartialOrd + Display, V: Display {
    pub fn trace(&mut self, title: String) {
        let graph_id = self.1.len();
        let mut sub_graph = format!("subgraph cluster_{}{{\n", self.1.len());
        sub_graph.push_str(&format!("label=\"{}\"\n", title));
        if let Some(root) = self.0.root.as_deref() {
            let mut id = 0;
            let mut current_list = vec![generate_element(root, 0, 0, 1, true)];
            while !current_list.is_empty() {
                let mut next_list = Vec::with_capacity(current_list.len() * 2);
                for item in current_list {
                    sub_graph.push_str(&format!(
                        " {}.{}[label={}] \n",
                        graph_id, item.id, item.label
                    ));
                    if item.id != item.p_id {
                        let port = if item.is_left { "l" } else { "r" };
                        if item.node.is_red() {
                            sub_graph.push_str(&format!(
                                "{{ rank=same; {}.{};{}.{} }}\n",
                                graph_id, item.p_id, graph_id, item.id
                            ));
                            sub_graph.push_str(&format!(
                                "{}.{} -> {}.{}:{} [color=red;dir=back]\n",
                                graph_id, item.id, graph_id, item.p_id, port
                            ));
                            // sub_graph.push_str(&format!(
                            //     "{}.{}:{} -> {}.{}[color=red]\n",
                            //     graph_id, item.p_id, port, graph_id, item.id
                            // ));
                        } else {
                            sub_graph.push_str(&format!(
                                "{}.{}:{} -> {}.{}\n",
                                graph_id, item.p_id, port, graph_id, item.id
                            ));
                        }
                    }
                    if let Some(next_node) = &item.node.left {
                        id += 1;
                        let level = if next_node.is_red() {
                            item.level
                        } else {
                            item.level + 1
                        };
                        next_list.push(generate_element(next_node, item.id, id, level, true));
                    }
                    if let Some(next_node) = &item.node.right {
                        id += 1;
                        let level = if next_node.is_red() {
                            item.level
                        } else {
                            item.level + 1
                        };
                        next_list.push(generate_element(next_node, item.id, id, level, false));
                    }
                }
                current_list = next_list;
            }
        }

        sub_graph.push_str("\n}");
        self.1.push(sub_graph);
    }
    pub fn get_graph(&self) -> String {
        let mut graph = "#@startdot trace red black tree\ndigraph red_black_tree{\nbgcolor=gray\nnode[shape=none]\n".to_string();
        graph.push_str(&self.1.join("\n"));
        graph.push_str("}\n#@enddot");
        graph
    }
}
impl<K: PartialOrd + Display, V: Display> ST<K, V> for TraceRedBlackBST<K, V> {
    fn put(&mut self, key: K, value: V) {
        let title = format!("put {}:{}", key, value);
        self.0.put(key, value);
        self.trace(title);
    }

    fn get(&self, key: &K) -> Option<&V> {
        self.0.get(key)
    }

    fn delete(&mut self, key: &K) {
        let title = format!("delete key:{}", key);
        self.0.delete(key);
        self.trace(title)
    }

    fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    fn size(&self) -> usize {
        self.0.size()
    }

    fn min(&self) -> Option<&K> {
        self.0.min()
    }

    fn max(&self) -> Option<&K> {
        self.0.max()
    }

    fn floor(&self, key: &K) -> Option<&K> {
        self.0.floor(key)
    }

    fn ceiling(&self, key: &K) -> Option<&K> {
        self.0.ceiling(key)
    }

    fn rank(&self, key: &K) -> usize {
        self.0.rank(key)
    }

    fn select(&self, k: usize) -> Option<&K> {
        self.0.select(k)
    }
}