use crate::Node::*;
use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd, Reverse};
use std::collections::{BinaryHeap, BTreeMap};
use std::convert::From;

#[derive(Debug, Clone)]
enum Node {
    Leaf(usize, char),
    Branch(usize, Box<Node>, Box<Node>),
}

impl Node {
    fn frequency(&self) -> usize {
        match self {
            Leaf(f, ..) => *f,
            Branch(f, ..) => *f,
        }
    }

    fn merge(lhs: Node, rhs: Node) -> Node {
        match (lhs, rhs) {
            (Leaf(f1, c1), Leaf(f2, c2)) => {
                Branch(f1 + f2, Box::new(Leaf(f1, c1)), Box::new(Leaf(f2, c2)))
            }
            (Leaf(f1, c1), Branch(f2, l, r)) => {
                Branch(f1 + f2, Box::new(Leaf(f1, c1)), Box::new(Branch(f2, l, r)))
            }
            (Branch(f1, l, r), Leaf(f2, c2)) => {
                Branch(f1 + f2, Box::new(Branch(f1, l, r)), Box::new(Leaf(f2, c2)))
            }
            (Branch(f1, l1, r1), Branch(f2, l2, r2)) => Branch(
                f1 + f2,
                Box::new(Branch(f1, l1, r1)),
                Box::new(Branch(f2, l2, r2)),
            ),
        }
    }

    fn build_code(self) -> BTreeMap<char, String> {
        let mut code = BTreeMap::new();
        let mut s = String::new();
        self.add_char(&mut s, &mut code, '0');
        code
    }

    fn add_char(self, s: &mut String, code: &mut BTreeMap<char, String>, a: char) {
        s.push(a);
        match self {
            Leaf(_, c) => {
                code.insert(c, s.clone());
            }
            Branch(_, l, r) => {
                l.add_char(s, code, '0');
                r.add_char(s, code, '1');
            }
        }
        s.pop();
    }
}

impl From<(char, usize)> for Node {
    fn from((c, count): (char, usize)) -> Node {
        Leaf(count, c)
    }
}

impl PartialEq for Node {
    fn eq(&self, other: &Node) -> bool {
        self.frequency() == other.frequency()
    }
}

impl Eq for Node {}

impl Ord for Node {
    fn cmp(&self, other: &Node) -> Ordering {
        Reverse(self.frequency()).cmp(&Reverse(other.frequency()))
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Node) -> Option<Ordering> {
        Some(Reverse(self.frequency()).cmp(&Reverse(other.frequency())))
    }
}

fn build_queue(message: &str) -> BinaryHeap<Node> {
    let mut map = BTreeMap::new();
    for c in message.chars() {
        map.entry(c).and_modify(|count| *count += 1).or_insert(1);
    }
    map.into_iter().map(Node::from).collect()
}

fn main() {
    let mut queue = build_queue(
        "the quick brown 🦊fox🦊 jumps over the sleazy 🐶dog🐶. 🦊🦊🐶🦊🦊"
    );
    while queue.len() > 1 {
        let lhs = queue.pop().unwrap();
        let rhs = queue.pop().unwrap();
        queue.push(Node::merge(lhs, rhs));
    }
    let huffman_tree = queue.pop().unwrap();
    let huffman_code = huffman_tree.build_code();
    dbg!(&huffman_code);
}