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

struct tree
{
  int f;
  char id;
  int empty;

  struct tree *right;
  struct tree *left;
};

int findNode(struct tree *huffT,char id){
  int pos=0;
  while(huffT[pos].empty!=1){
    if(huffT[pos].id==id){
      return pos;
      printf("(%d,%c)",pos,id);
    }
    pos++;
  }
  return -1;
}

void printTable(struct tree *huffT){
  if(huffT[0].empty==0)
    {
      if(huffT[0].right!=NULL){
	printTable(huffT[0].right);
	printf("-%c-",huffT[0]->right->id);
      } else {
	printf("0");
      }
      if(huffT[0].left!=NULL){
	printTable(huffT[0].left);
      } else {
	printf("1");
      }
    } else {
      printf("test");
    }
  printf("\n");
}

void deleteNode(struct tree *huffT,int n){
  int pos=n;
  while(huffT[pos].empty!=1){
    huffT[pos].id=huffT[pos+1].id;
    huffT[pos].f=huffT[pos+1].f;
    huffT[pos].empty=huffT[pos+1].empty;
    pos++;
  }
}

void deleteChar(char *text,int pos){
  int i=pos;
  
  while(text[i]!='\0')
  {
    text[i]=text[i+1];
    i++;
  }
}

void printRoots(struct tree *huffT,int size){
  int i;
  for(i=0;i<size;i++){
    printf("i:%d-%c,%d\n",i,huffT[i].id,huffT[i].f);
  }
}

int findSmallest(struct tree *huffT){
  int pos=0;
  int smallest;
  smallest=0;
  while(huffT[pos].empty!=1){
    if(huffT[smallest].f>huffT[pos].f){
      smallest=pos;
    }
    pos++;
  }
  return smallest;
}

void mergeSmallest(struct tree *huffT){
  struct tree node1;
  struct tree node2;
  
  int smallest1;
  int smallest2;

  smallest1=findSmallest(huffT);
  node1.id=huffT[smallest1].id;
  node1.f=huffT[smallest1].f;
  node1.empty=huffT[smallest1].empty;
  deleteNode(huffT,smallest1);
  
  smallest2=findSmallest(huffT);
  node2.id=huffT[smallest2].id;
  node2.f=huffT[smallest2].f;
  node2.empty=huffT[smallest2].empty;

  huffT[smallest2].id='\0';
  huffT[smallest2].f=(node1.f + node2.f);
  huffT[smallest2].right=&node2;
  huffT[smallest2].left=&node1;
  huffT[smallest2].empty=0;
}

int deleteDuplicates(char *text, char s){
  int pos=0;
  int n=0;
  while(text[pos]!='\0'){
    if(text[pos]==s){
      deleteChar(text,pos);
      n++;
    }else{
      pos++;
    }
  }
  return n;
}

int makeTree(char *text, struct tree *huffT){
  int pos=0;
  while(text[0]!='\0'){
    huffT[pos].id=text[0];
    huffT[pos].f=deleteDuplicates(text,text[0]);
    pos++;
  }
  huffT[pos].empty=1;
  return pos;
}

int main(){
  struct tree huff[17];
  char text[] = "aabaabccdbdbabdbc";

  makeTree(text,huff);
  printf("\nFörsta printtree:\n");
  printRoots(huff,4);
  mergeSmallest(huff);
  printf("\nFörsta merge:\n");
  printRoots(huff,3);
  mergeSmallest(huff);
  printf("\nAndra merge:\n");
  printRoots(huff,2);
  mergeSmallest(huff);
  printf("\nTredje merge:\n");
  printRoots(huff,1);
  printTable(huff);
  return 0;
}