use std::io;
use std::fs;
use std::path::Path;
// This is a unique algorithm for compression that uses a combination of Huffman coding and run-length encoding.
use std::collections::HashMap;
use std::collections::BinaryHeap;
#[derive(Eq, Ord, PartialEq, PartialOrd)]
// This is the Huffman tree node.
struct Node {
    character: char,
    frequency: usize,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}
// This function takes a string and returns a HashMap of characters and their frequencies.
fn get_frequencies(input: &str) -> HashMap<char, usize> {
    let mut frequencies = HashMap::new();
    for c in input.chars() {
        let count = frequencies.entry(c).or_insert(0);
        *count += 1;
    }
    frequencies
}
// This function takes a HashMap of characters and their frequencies and returns a Huffman tree.
fn build_huffman_tree(frequencies: &HashMap<char, usize>) -> Node {
    let mut nodes: BinaryHeap<Node> = frequencies
        .iter()
        .map(|(&c, &f)| Node {
            character: c,
            frequency: f,
            left: None,
            right: None,
        })
        .collect();
    while nodes.len() > 1 {
        let min1 = nodes.pop().expect("Error: pop() method does not exist for BinaryHeap<Node>");
        let min2 = nodes.pop().expect("Error: pop() method does not exist for BinaryHeap<Node>");
        let frequency = min1.frequency + min2.frequency;
        let node = Node {
            left: Some(Box::new(min1)),
            right: Some(Box::new(min2)),
            frequency,
            character: '\0',
        };
        nodes.push(node);
    }
    nodes.into_iter().next().unwrap()
}
// This function takes a Huffman tree and returns a HashMap of characters and their codes.
fn get_codes(node: &Node) -> HashMap<char, String> {
    let mut codes = HashMap::new();
    let mut code = String::new();
    get_codes_recursive(node, &mut codes, &mut code);
    codes
}
fn get_codes_recursive(node: &Node, codes: &mut HashMap<char, String>, code: &mut String) {
    match node {
        Node {
            character,
            left: None,
            right: None,
            ..
        } => {
            codes.insert(*character, code.clone());
        }
        Node {
            left,
            right,
            ..
        } => {
            code.push('0');
            get_codes_recursive(left.as_ref().unwrap(), codes, code);
            code.pop();

            code.push('1');
            get_codes_recursive(right.as_ref().unwrap(), codes, code);
            code.pop();
        }
    }
}
// This function takes a string and returns a run-length encoded string.
fn run_length_encode(input: &str) -> String {
    let mut output = String::new();
    let mut current_char = '\0';
    let mut current_count = 0;
    for c in input.chars() {
        if c == current_char {
            current_count += 1;
        } else {
            if current_count > 0 {
                output.push_str(&format!("{}{}", current_count, current_char));
            }
            current_char = c;
            current_count = 1;
        }
    }
    if current_count > 0 {
        output.push_str(&format!("{}{}", current_count, current_char));
    }
    output
}
// This function takes a string and returns a compressed string using the LZW algorithm.
fn lzw_compress(input: &str) -> String {
    let mut output = String::new();
    let mut dictionary = HashMap::new();
    let mut current_string = String::new();
    let mut next_code = 0;
    for c in input.chars() {
        let mut string = current_string.clone();
        string.push(c);
        if dictionary.contains_key(&string) {
            current_string = string;
        } else {
            output.push_str(&format!("{}", dictionary.get(&current_string).unwrap()));
            dictionary.insert(string, next_code);
            next_code += 1;
            current_string = c.to_string();
        }
    }
    output.push_str(&format!("{}", dictionary.get(&current_string).unwrap()));
    output
}

// This function takes a string and returns a compressed string.
fn compress(input: &str) -> String {
    let frequencies = get_frequencies(input);
    let tree = build_huffman_tree(&frequencies);
    let codes = get_codes(&tree);
    let encoded = input
        .chars()
        .map(|c| codes.get(&c).unwrap().to_string())
        .collect::<Vec<String>>()
        .join("");
    let lzw_encoded = lzw_compress(&encoded);
    let run_length_encoded = run_length_encode(&lzw_encoded);
    run_length_encoded
}

fn main() {
    println!("Welcome to the Compression Program!");
    println!("Please enter the path of the file you would like to compress:");
    let mut input_path = String::new();
    io::stdin().read_line(&mut input_path).expect("Failed to read line");
    let input_path = input_path.trim();
    println!("Please enter the path of the output file:");
    let mut output_path = String::new();
    io::stdin().read_line(&mut output_path).expect("Failed to read line");
    let output_path = output_path.trim();
    let input_data = fs::read_to_string(input_path).expect("Failed to read file");
    let compressed_data = compress(&input_data);
    let output_file = Path::new(&output_path);
    fs::write(output_file, compressed_data).expect("Failed to write file");

    println!("Compression complete!");
}