Lab09

// Matthew Felix
// CSE-100
// Lab 09
// Spring 2020
// 4.16.2020

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

// A Huffman tree node struct

struct Node {

    char data;
    unsigned freq;
    Node* left;
    Node* right;

    Node(char data, unsigned freq) {

        left = NULL;
        right = NULL;
        this->data = data;
        this->freq = freq;

    }

};

string* s = new string[1000];

// Comparing two heap nodes

struct compare {

    bool operator()(Node* l, Node* r) {
        return (l->freq > r->freq);
    }
};

void printCode(struct Node* root, string str, char arr[], int n) {

    if (root == NULL) {
        return;
    }

    if (root->data != ' ') {
        for (int i = 0; i < n; i++) {
            if (root->data == arr[i]) {
                s[i] = str;
            }
        }
        //cout << root->data << ":" << str << endl;

    }

    printCode(root->left, str + "0", arr, n);
    printCode(root->right, str + "1", arr, n);

}

void huffman(char arr[], int freq[], int n, priority_queue<Node*, vector<Node*>, compare> Q) {

    struct Node* left;
    struct Node* right;
    struct Node* z;

    // "min-priority queue, Q, keyed on the freq atributes"

    for (int i = 0; i < n; i++) {

        Q.push(new Node(arr[i], freq[i]));
    }

    for (int i = n; i > 1; i--) {

        //Extract Min Q
        left = Q.top();
        Q.pop(); //remove from queue

        //Extract Min Q
        right = Q.top();
        Q.pop(); //remove from queue

        z = new Node(' ', left->freq + right->freq);

        z->left = left;
        z->right = right;
        Q.push(z); //insert the added values into the queue

    }

    printCode(Q.top(), "", arr, n);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << ":" << s[i] << endl;
    }

}

int main() {

    // "input consists of 6 integers"
    int n = 6;
    char arr[] = { 'A', 'B', 'C', 'D', 'E', 'F' };

    //created an array with the given outputs for easy testing
    //int freq[] = { 34787, 28342, 39894, 28982, 19899, 12998 };

    int* freq = new int[6];

    for (int i = 0; i < n; i++) {
        cin >> freq[i];
    }

    //page 431 mentions using a priority queue
    priority_queue<Node*, vector<Node*>, compare> Q;

    huffman(arr, freq, n, Q);

    return 0;

}