/*Cameron Dobbs - 11697123
**CS101 - Spring 2018
**Project 4 - This project reads a plain text file, computes a Huffman code tree for that text file, and writes out the encoded version of the text.
*/

#include <iostream>
#include <fstream>
#include <string>
using namespace std;


struct treenode {
        //leaf as a node
        char letter;
        int occurences;
        treenode *left;
        treenode *right;
};

void heapify(treenode *minheap, int passNum, int i, treenode move) {
        treenode temp;
        int left = (2*i)+1;
        int right = (2*i)+2;

        cout << "passNum = " << passNum << endl;

        //node you are inserting is bigger than left child, swap them. go again with the new move
        if (minheap[left].occurences <= minheap[right].occurences) {
                if ((left <= passNum) && (minheap[left].occurences < move.occurences)) {
                temp = move;
                minheap[i] = minheap[left];
                minheap[left] = temp;
                for (int m = 0; m < passNum + 1; m++) {
                        cout << "heapifyL: node: " << minheap[m].letter << " ...occur: " << minheap[m].occurences << endl;
                }
                cout << endl;
                heapify(minheap, passNum, left, minheap[left]);
                }
        }
        else if (minheap[right].occurences < minheap[left].occurences) {
                if ((right <= passNum) && (minheap[right].occurences < move.occurences)) {
                temp = move;
                minheap[i] = minheap[right];
                minheap[right] = temp;
                for (int m = 0; m < passNum + 1; m++) {
                        cout << "heapifyR: node: " << minheap[m].letter << " ...occur: " << minheap[m].occurences << endl;
                }
                cout << endl;
                heapify(minheap, passNum, right, minheap[right]);
                }
        }
}

//extracts the top node, replaces it with the last, then reorders
treenode *extractMin(treenode *minheap, int &passNum) {
        treenode *min = new treenode;
        *min = minheap[0];

        minheap[0] = minheap[passNum];


        passNum -= 1;

        //put in huffman tree...buble it down - the first one ...compare with two children, swap if out of order...go until it stops
        heapify(minheap, passNum, 0, minheap[0]);

        return min;
}


void insert(treenode *minheap, treenode newNode, int passNum) {
        treenode temp;
        int parent;
        parent = (passNum - 1)/2;

        //node you are inserting is bigger than left child, swap them. go again with the new move
        if ((parent >= 0) && (minheap[parent].occurences > newNode.occurences)) {
                temp = newNode;
                minheap[passNum].letter = minheap[parent].letter;
                minheap[passNum].occurences = minheap[parent].occurences;
                minheap[passNum].left = minheap[parent].left;
                minheap[passNum].right = minheap[parent].right;

                minheap[parent].letter = temp.letter;
                minheap[parent].occurences = temp.occurences;
                minheap[parent].left = temp.left;
                minheap[parent].right = temp.right;

                passNum = parent;
                insert(minheap, minheap[parent], passNum);
        }
}

//FIXME: not only does it not accept z, but idk how to print the "code"...
//OR if I'm not supposed to print the code, what AM I supposed to print?
void Preorder(treenode *z, ofstream &preorder) {
        if (z) {
                preorder << z->letter;
                cout<<"writing "<<z->letter << " ...occur = " << z->occurences << endl;
                Preorder(z->left, preorder);
                Preorder(z->right, preorder);
        }
}

//FIXME
void Inorder(treenode *z, ofstream &inorder) {
        if (z) {
                Inorder(z->left, inorder);
                cout << "writing " << z->letter << " ...occur = " << z->occurences << endl;
                inorder << z->letter;
                Inorder(z->right, inorder);
        }
}

//FIXME
void Encode(ofstream &encode) {

}


//You must create a binary heap data structure that uses an array and implements insert and extract-min that run in O(lg N) time.

int main(int argc, char *argv[]) {
        //read the text from the file given as a command line argument
        ifstream infile;
        infile.open(argv[1]);
        if (infile.fail()) return 0;

        //get each character, store number of occurences
        int asciiTable[128];
        char getChar;
        int numLetters = 0;
        while(infile.get(getChar)) {
                int ascii = (int) getChar;
                if (!asciiTable[ascii]) numLetters++;
                asciiTable[ascii]++;
        }

        cout << "num letters = " << numLetters << endl;
        cout << "Table: " << endl;
        for (int i = 0; i < 128; i++) {
                if (asciiTable[i]) {
                        cout << "i= " << i << "...char = " << (char)i << "...Occur=" << asciiTable[i] << endl;
                }
        }
        cout << endl;

        //build the unsorted array
        int j = 0;
        treenode unsorted[numLetters];
        treenode minheap[numLetters];
        for (int i = 0; i < 128; i++) {
                if (asciiTable[i]) {
                        unsorted[j].occurences = asciiTable[i];
                        unsorted[j].letter = char(i);
                        j++;
                }
        }

        //insert the unsorted array into a min order heap
        for (int i = 0; i < numLetters; i++) {
                if (i == 0) {                           //if head is empty
                        minheap[0] = unsorted[0];       //place item in root
                        //cout << "In i==0" << endl;
                }
                else {
                        minheap[i] = unsorted[i];
                        minheap[i].left = NULL;
                        minheap[i].right = NULL;
                        insert(minheap, unsorted[i], i);
                }
        }

        //delete this later...checks the order after min heap
        for (int i = 0; i< numLetters; i++) {
                cout << "Char = " << minheap[i].letter << "...num = " << minheap[i].occurences << endl;
        }

        //FIXME: build the Huffman code tree using the heap. as you create new internal nodes, give them a unique character label, using values >128
        //call extract-min twice...make the two lowest the new nodes
        //make a new node..adding those two old nodes together
        //add the new node to the list...repeat
        int passNum = numLetters -1;
        //FIXME: change 97 to 128
        int a = 97;
        treenode *root;
        while (passNum > 0) {
                treenode *z = new treenode;
                treenode *tleft = extractMin(minheap,passNum);
                cout << "t.left.occur = " << tleft->occurences << " ...char =" << tleft->letter << endl;
                z->left = tleft;

                treenode *tright = extractMin(minheap, passNum);
                cout << "t.right.occur = " << tright->occurences << " ...char =" << tright->letter << endl << endl;
                z->right = tright;

                z->occurences = z->left->occurences + z->right->occurences;
                z->letter = char(a++);

                passNum += 1;
                minheap[passNum] = *z;
                insert(minheap, minheap[passNum], passNum);

                cout << "passNum after insert = " << passNum << endl;
                for (int k = 0; k< passNum; k++) {
                        cout << "Char = " << minheap[k].letter << "...num = " << minheap[k].occurences << endl;
                }


                cout << endl;
                cout << "z->left->occurences = " << z->left->occurences << "....z->left->letter = " << z->left->letter << endl; cout << "z->right->occurences = " << z->right->occurences << "...z->right->letter = " << z->right->letter << endl << "z->occurences = " << z->occurences << ".........z->leter = " << z->letter << endl << "-------------"<< endl;
                root = z;
        }

        //FIXME: write the pre-order traversal to the file "preorder"
        ofstream myfile;
        myfile.open("preorder");
        cout << "1      " << endl;
        Preorder(root, myfile);
        myfile.close();
        cout << "past preorder" << endl;

        //FIXME: write the in-order traversal to the file "inorder"
        ofstream myfile2;
        myfile2.open("inorder");
        cout << "opened inorder" << endl;
        Inorder(root, myfile2);
        myfile2.close();
        cout << "past inorder" << endl;

        //FIXME: construct a table containing the encoding for each character, storing the encoding as a string
        string table[numLetters];

        //FIXME: encode the original text, writing the econded version to "code.txt". This file should be ASCII '0' and '1' characters
        ofstream myfile3;
        myfile3.open("code.txt");
        Encode(myfile3);
        myfile3.close();

        return 0;
}