/* Author : Jenn-Dar Chang */

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <mpi.h>
#define N 75 /* 75 = 122 - 48 + 1 */
#define LEN 40320*1000 /* 40320=1*2*3*4*5*6*7*8 */

struct list1 {
char data;
char brod; /* bord = 'r' 表是兄弟在右邊, bord = 'l' 表是兄弟在左邊 */
int val;
int merged; /* merged = 1 表示合併過, merged =0 表示沒合併過*/
struct list1 *parent;
};

struct list1 *p[N];
char *lettercode[N];

void construct_tree(int *count, int *a, int n);
void calfreq(char *buf, int n, int *count);
void main(int argc, char *argv[])
{
char *buffer;
int me, ntag, size, i, j, num, bsize;
MPI_Status status;
time_t seed;
int count[N], tmpcount[N], temp[N];
double begin, end;

MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &me);
MPI_Comm_size(MPI_COMM_WORLD, &size);

time(&seed);
srand(seed*(me+1));

bsize = LEN / size;
begin = MPI_Wtime();
for (i=0; i<N; i++) { lettercode[i]=NULL; count[i] = 0; }


buffer =(char *) malloc(sizeof(char)*bsize);

for (i=0; i<bsize; i++)
buffer[i] = (char)((rand() % 75)+48); /* random 產生 LEN 各 symbol */

calfreq(buffer, bsize, count);

ntag = 100;
if (me != 0) MPI_Send(count, N, MPI_INT, 0, ntag, MPI_COMM_WORLD);
else {
for (i=1; i<size; i++) {
MPI_Recv(tmpcount, N, MPI_INT, i, ntag, MPI_COMM_WORLD, &status);
for (j=0; j<N; j++)
if (tmpcount != 0)
count[j]+=tmpcount[j];
}
}


if (me == 0) {
num = 0;
for (i=0; i < N; i++) {
if (count[i] != 0) {
temp[num] = count[i];
num++;
}
}

if (num>=2) construct_tree(count, temp, num);

end = MPI_Wtime();
printf("Total Computing time : %lf\n", (end-begin));
}

MPI_Finalize();
}

void calfreq(char *buf, int n, int *count)
{
int i, k;

for (i=0; i<n; i++) {
k =(int)buf[i]-48;
count[k]++;
} /* end of for loop */
}

void construct_tree(int *count, int *a, int n)
{
int i, j, flag, t, c1, findr, findl, c2, flag2;
int tmpa[2], init = 1;
char ch[2], tmpchar;
struct list1 *tmplistl, *tmplistr, *tmpp;

flag = 1; c2 = 0;
while (flag) {
for (i=0; i<2; i++) /* find two smallest element */
for (j=0; j<n-i-1; j++)
if (a[j]<a[j+1]) {
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}

tmpa[0] = a[n-1]; tmpa[1] = a[n-2];

if (init) { /* initial */
tmplistl = (struct list1 *)malloc(sizeof(struct list1));
tmplistr = (struct list1 *)malloc(sizeof(struct list1));
p[c2] = tmplistl;
c2++;
p[c2] = tmplistr;
c2++;
tmplistl->val = tmpa[0];
tmplistr->val = tmpa[1];
init = 0;
}
else {
findl = 0; findr = 0; flag2 = 1;
for (i=0; i<c2 && flag2; i++) {
tmpp = p[i];
while (tmpp) {
if ((tmpp->val == tmpa[0]) && (!tmpp->merged) && (!findl)) {
tmpp->merged = 1;
tmplistl = tmpp;
findl = 1;
}
else if ((tmpp->val == tmpa[1]) && (!tmpp->merged) && (!findr)) {
tmpp->merged = 1;
tmplistr = tmpp;
findr = 1;
}
tmpp=tmpp->parent;
} /* end of while loop */
if (findl && findr) flag2 = 0;
} /* end of for loop */

if (findl == 0) {
tmplistl = (struct list1 *)malloc(sizeof(struct list1));
p[c2] = tmplistl;
c2++;
tmplistl->val = tmpa[0];
}
if (findr == 0) {
tmplistr = (struct list1 *)malloc(sizeof(struct list1));
p[c2] = tmplistr;
c2++;
tmplistr->val = tmpa[1];
}
} /* end of not initial */

/* construct parent */
tmplistl->parent = (struct list1 *)malloc(sizeof(struct list1));
tmplistl->parent->parent = NULL;
tmplistl->parent->brod = 'r';
tmplistl->parent->val = tmpa[0] + tmpa[1];
tmplistl->parent->merged = 0; /* 表示還未和其他的合併過 */
tmplistl->merged = 1; /* 表示合併過 */
tmplistr->merged = 1; /* 表示合併過 */
tmplistl->brod = 'r';
tmplistr->brod = 'l';
tmplistr->parent = tmplistl->parent;

n=n-1;
a[n-1]=tmplistl->parent->val;

if (n==1) flag = 0; /* represent construct tree terminted */
} /* end of while (flag) loop ie. construct tree */

for (i=0; i<c2; i++) {
if (p[i]) {
lettercode[i] = (char *) malloc(sizeof(char)*N);
c1=0;
tmpp=p[i];
while (tmpp) {
if (tmpp->brod == 'r') lettercode[i][c1]='0';
else lettercode[i][c1]='1';
c1++;
tmpp=tmpp->parent;
}
lettercode[i][c1-1]='\0';

c1 = strlen(lettercode[i]);
for (j=0; j<(c1/2); j++) {
tmpchar=lettercode[i][j];
lettercode[i][j]=lettercode[i][c1-j-1];
lettercode[i][c1-j-1]=tmpchar;
}

} /* end of if (p[i]) */
} /* end of for loop */
}