#include <stdlib.h>
#include <stdio.h>

#include "list.h"
#include "bit_code.h"

// from here shannon helper

// recursivly divides an array in halfs according to strengths
// sets code and bit width
// first half gets bit set
// second half gets bit cleared
void shannon(int from_index, int to_index, int bit_count, int coder, int set_count, int *bytes_used_array, int *map, _code_ *code)
{
  if (from_index == to_index)
  {
   code[map[from_index]].bit_count = bit_count + 1;
   code[map[from_index]].code = (coder<<1) + 1;
   return;
  }

  if (from_index+1 == to_index)
  {
   code[map[from_index]].bit_count = bit_count + 1;
   code[map[from_index]].code = (coder<<1)+1;
   code[map[to_index]].bit_count = bit_count + 1;
   code[map[to_index]].code = (coder<<1);
   return;
  }
  int start1 = from_index;
  int end1   = start1;
  int start2 = end1+1;
  int end2   = to_index;
  int set_count1 = bytes_used_array[map[end1]];
  int set_count2;
  while (set_count1 < set_count/2)
  {
    end1++;
    start2++;
    set_count1 += bytes_used_array[map[end1]];
  }
//  set_count2 = set_count-set_count1; -> gives negative numbers!
  set_count2 = 0;
  for (int i=start2; i<=end2; i++)
  {
    set_count2+=bytes_used_array[map[i]];
  }
//printf("S1 = %i, S2 = %i \n", set_count1, set_count2);

  if (start1 == end1)
  {
   code[map[start1]].bit_count = bit_count + 1;
   code[map[start1]].code = (coder<<1)+1;
  }
  else
  {
   shannon(start1, end1, bit_count+1, (coder<<1)+1, set_count1, bytes_used_array, map, code);
  }

  if (start2 == end2)
  {
   code[map[start2]].bit_count = bit_count + 1;
   code[map[start2]].code = (coder<<1);
  }
  else
  {
   shannon(start2, end2, bit_count+1, (coder<<1), set_count2, bytes_used_array, map, code);
  }
}

// from here huffman helper
typedef struct
{
 int count;
 int index;
 void *parent;
 void *left;
 void *right;
 int bit_count;
 int coder;
} TREE;

T_LISTE *list_head = NULL;
T_LISTE *list_tail = NULL;

// search smalles tree element in list and
// remove it give it back
TREE *get_and_remove_from_list_smallest()
{
 T_LISTE *liste = list_head;
 TREE *found=NULL;
 while (liste != NULL)
 {
  TREE *current = (TREE *) liste->objekt;
  if (found == NULL)
  {
   found = current;
  }
  else
  {
   if (found->count > current->count)
   {
    found = current;
   }
  }
  liste = (T_LISTE *) liste->naechstes;
 }
 d_entferne_aus_liste(found, &list_head,&list_tail, DL_CLEAN_UP );
 return found;
}

// set codes to coder from huffman tree information
// recursive
// free()'s tree node processed
void code_tree(TREE *htree, int *map, _code_ *code)
{
  if (htree->index != -1)
  {
   code[map[htree->index]].bit_count = htree->bit_count;
   code[map[htree->index]].code = htree->coder;

//printf("Byte %02X mapped (with %i bits) to: %02X \n", map[htree->index], htree->bit_count, htree->coder);
  }
  else
  {
   TREE *left = (TREE *) htree->left;
   left->bit_count = htree->bit_count+1;
   left->coder= ((htree->coder)<<1);

   TREE *right = (TREE *) htree->right;
   right->bit_count = htree->bit_count+1;
   right->coder=((htree->coder)<<1)+1;

   code_tree(left, map, code);
   code_tree(right, map, code);
  }
  free(htree);
}

// codes into a huffman tree from map[from] to map[to]
void hstart(int from_index, int to_index, int *bytes_used_array, int *map, _code_ *code)
{
 // generate list with lose tree nodes
 // one node for each 'set'
 int i;
 for (i=from_index; i<to_index; i++)
 {
  TREE *htree;
  htree = (TREE *) malloc(sizeof(TREE));
  htree->index = i;
  htree->count = bytes_used_array[map[i]];
  htree->parent = NULL;
  htree->left = NULL;
  htree->right = NULL;
  htree->bit_count = 0;
  htree->coder = 0;
  d_fuege_in_liste_ein((T_PVOID )htree,&list_head,&list_tail,DL_HINTEN);
 }
 while (d_anzahl_liste(list_head) != 1)
 {
  // look for the two smallest elements of the set
  TREE *small1 = get_and_remove_from_list_smallest();
  TREE *small2 = get_and_remove_from_list_smallest();

  TREE *htree;
  htree = (TREE *) malloc(sizeof(TREE));
  htree->index = -1;
  htree->count = small1->count+small2->count;
  htree->parent = NULL;
  htree->left = small1;
  htree->right = small2;
  htree->bit_count = 0;
  htree->coder = 0;
  small1->parent = htree;
  small2->parent = htree;
  d_fuege_in_liste_ein((T_PVOID )htree,&list_head,&list_tail,DL_HINTEN);
 }
 // now we have a tree, whose root is the single
 // element of the list!

 // now we code it -> recursively
 code_tree(get_and_remove_from_list_smallest(), map, code);
}