#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define bytes 256

//Huffman tree node
struct treeNode{
    char data;  //Character
    int frequency;  // Frequency of the character
    struct treeNode *left, *right; // Left and right child of this node
};

//Huffman tree nodes !
struct MinHeap
{
    int currentSize;    //Current size of min heap
    int totalSize;   //Total Size of min heap
    struct treeNode **array;  // Array of minheap node pointers
};

//Allocate a new min heap node with given character and frequency of this character
struct treeNode* newNode(char data,int frequency)
{
    struct treeNode* temp = (struct treeNode*) malloc(sizeof(struct treeNode));
    temp->left = temp->right = NULL;
    temp->data = data;
    temp->frequency = frequency;
    return temp;
}

//Get each character and it's frequency
int get_frequency(char* str,int len,struct treeNode *chars)
{
    int i,no_chars;
    int freq[26];
    //Initialize frequency of each character to 0
    for(i=0; i<26; i++)
    {
        freq[i] = 0;
    }
     //Find total number of occurrences of each character
    for(i=0; i<len; i++)
    {
        //If the current character is lowercase
        if(str[i]>='a' && str[i]<='z')
        {
            freq[str[i] - 97]++;
        }
        //If the current character is uppercase
        else if(str[i]>='A' && str[i]<='Z')
        {
            freq[str[i] - 65]++;
        }
    }

    for(i=0; i<26; i++)
    {
        /* If current character exists in given string */
        if(freq[i] != 0)
        {
            chars[no_chars].frequency=freq[i];
            chars[no_chars].data= (i+97);
            no_chars++;
        }
    }
return no_chars;
}

//Create MinHeap of given Size(N)
struct MinHeap* createMinHeap(int totalSize)
{
    struct MinHeap* minHeap = (struct MinHeap*) malloc(sizeof(struct MinHeap));
    minHeap->currentSize = 0;  // current size is 0
    minHeap->totalSize = totalSize;
    minHeap->array =(struct treeNode**)malloc(minHeap->totalSize * sizeof(struct treeNode*));
    return minHeap;
}

//Swap two nodes with each others
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
    struct MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}

//MIN_HEAPIFY
void MIN_HEAPIFY(struct MinHeap* minHeap, int index)
{
    printf("Minheapify reached\n");
    int smallest = index; //Smallest index
    int left = 2 * index + 1; //Left Child of smallest
    int right = 2 * index + 2; //Right Child of smallest

    struct treeNode* temp = (struct treeNode*) malloc(sizeof(struct treeNode));

    //Frequency of left < frequency of samllest
    if (left < minHeap->currentSize && minHeap->array[left]->frequency < minHeap->array[smallest]->frequency)
      {smallest = left;}

    //Frequency of right < frequency of samllest
    if (right < minHeap->currentSize && minHeap->array[right]->frequency < minHeap->array[smallest]->frequency)
      {smallest = right;}

    //If index smallest != index then swap the samllest with it's right place in the heap
    if (smallest != index)
    {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[index]);
        //After swap call min heapify again to check every one is in it's right place after swapping
        MIN_HEAPIFY(minHeap, smallest);
    }
}

//Check if size is one
int isSizeOne(struct MinHeap* minHeap)
{
    return (minHeap->currentSize == 1);
}

//Check if this node is leaf
int isLeaf(struct treeNode* root)
{
    return !(root->left) && !(root->right) ;
}

//Extract minimum node
struct treeNode* extractMin(struct MinHeap* minHeap)
{
    //Assuming that the smallest element of the heap is always in the first place of the array of pointers of the heap
    struct treeNode* temp = minHeap->array[0];
    //Putting the last element in the array of heaps in the first place of the heap after getting the smallest element
    minHeap->array[0] = minHeap->array[minHeap->currentSize - 1];
    --minHeap->currentSize;
    MIN_HEAPIFY(minHeap, 0);
    printf("\nsize= %d\n",minHeap->currentSize);
    return temp;
}

//Insert minimum into heap after
void insertMinHeap(struct MinHeap* minHeap, struct treeNode* treeNode)
{
    ++minHeap->currentSize;
    int i = minHeap->currentSize - 1;
    while (i && treeNode->frequency < minHeap->array[(i - 1)/2]->frequency)
    {
        minHeap->array[i] = minHeap->array[(i - 1)/2];
        i = (i - 1)/2;
    }
    minHeap->array[i] = treeNode;
}

//Build the heap b2a :O :O
void buildMinHeap(struct MinHeap* minHeap)
{
    int n = minHeap->currentSizesize - 1;
    int i;
    /* for(i=0;i<=n;i++)
        printf("char: %s & frequency: %d\n",freq[i]->x,freq[i]->frequency);*/
    for (i = (n - 1) / 2; i >= 0; --i)
        MIN_HEAPIFY(minHeap,i);
}


int main()

{
    FILE *fp;
    int c;

    fp = fopen("t.txt", "r");
    char *code;
    size_t n = 0;

    if (fp == NULL) {
    printf("ERROR!");
    return NULL;
    } //could not open file
    fseek(fp, 0, SEEK_END);
    long f_size = ftell(fp);
    fseek(fp, 0, SEEK_SET);
    code = malloc(f_size);


    while((c = fgetc(fp)) != EOF) {
            printf("%c\n",(char)c); //Feh moshkela hena lw shelna el printf by7sal moshkela fl malloc try to check it.
            code[n] = (char)c;
            n++;
            //putchar(c);
    }
    fclose(fp);

    struct treeNode* temp = (struct treeNode*) malloc(sizeof(struct treeNode));
    //Construct structuraya
    int no_chars=0;
    no_chars = get_frequency(code,n,temp);
    //BUILD_MIN_HEAP(no_chars);
    return 0;
}


/* int i=0;
    while (no_chars>0)
    {
        printf("char: %c & freq: %d\n",temp[i].x,temp[i].frequency);
        no_chars--;
        i++;
    }
    */