// THis program will output the huffman tree in graphics window and will show the huffman code in command window
// huff.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <stdlib.h> //Needed for "exit" function
#include "math.h"
//Include OpenGL header files, so that we can use OpenGL
#ifdef __APPLE__
#include <OpenGL/OpenGL.h>
#include <GLUT/glut.h>
#else
#include "glut.h"
#endif
typedef struct node {
char name[20]; // name of the node
float data;
struct node* right;
struct node* left;
struct node* parent;
struct node* next;
}NODE;
NODE* root = NULL;
using namespace std;
void display_list(NODE* head) {
if(head) {
cout<<"\nList contents:\n";
NODE* temp = head;
while(temp) {
cout<<"Node : "<<temp->name<<" probability:"<<temp->data<<endl;
temp = temp->next;
}
} else {
cout<<"\nEmpty List";
}
}
void find_smallest(NODE* head,NODE** smallest1, NODE** smallest2) {
*smallest1 = NULL;
*smallest2 = NULL;
NODE* t = head;
while(t) {
// Skip the nodes who has parent
if(t->parent) {
t = t->next;
continue;
}
if(!*smallest1) {
*smallest1 = t;
} else if(!*smallest2) {
*smallest2 = t;
} else if(t->data < (*smallest1)->data) {
if ((*smallest1)->data < (*smallest2)->data) {
*smallest2 = *smallest1;
}
*smallest1 = t;
} else if(t->data < (*smallest2)->data) {
*smallest2 = t;
} else {
// Do nothing
}
if(*smallest1 && *smallest2) {
if((*smallest1)->data > (*smallest2)->data) {
NODE* temp = *smallest1;
*smallest1 = *smallest2;
*smallest2 = temp;
}
}
t = t->next;
}
}
void add_element(NODE** head,NODE** e) {
if(!*head) {
*head = *e;
} else {
NODE* t = *head;
while(t->next!=NULL) {
t = t->next;
}
t->next = *e;
}
}
void tree_traversal(NODE* root,char code[20]) {
if(!root) {
return;
}
//cout<<"\n NODE : "<<root->name<<" prob: "<<root->data;
if(root->left==NULL && root->right==NULL) {
cout<<" \nNODE : "<<root->name<<" prob : "<<root->data<<" code: "<<code;
return;
}
int len = strlen(code);
if(root->left) {
code[len]='1';
code[len+1]='\0';
tree_traversal(root->left,code);
}
if(root->right) {
code[len]='0';
code[len+1]='\0';
tree_traversal(root->right,code);
}
}
void drawCircle(float segments, float radius, float sx, float sy)
{
float theta = 2 * 3.1415926 / segments;
float tan_factor = tanf(theta);
float radial_factor = cosf(theta);
float x = radius;
float y = 0;
int cache_pt = 0;
double cache_x;
double cache_y;
glBegin(GL_LINES);
for (int ii = 0; ii < segments; ii++) {
if(!cache_pt) {
cache_x = x+sx;
cache_y = y+sy;
cache_pt = 1;
} else {
//glVertex2f(cache_x,cache_y);
glVertex2f(x + sx, y + sy);
cache_x = x+sx;
cache_y = y+sy;
}
float tx = -y;
float ty = x;
x += tx * tan_factor;
y += ty * tan_factor;
x *= radial_factor;
y *= radial_factor;
}
glEnd();
}
void draw_line(float x1,float y1,float x2, float y2) {
glBegin(GL_LINES);
glVertex2f(x1,y1);
glVertex2f(x2,y2);
glEnd();
}
void draw_text(char* text,float x, float y) {
GLvoid *font_style = GLUT_BITMAP_TIMES_ROMAN_24;
glRasterPos3f(x, y, 0);
for (int i = 0; text[i] != '\0'; i++){
glutBitmapCharacter(font_style, text[i]);
}
}
void drawNode(NODE* t_root,float x1,float y1,int level) {
if (t_root==NULL) {
return;
}
float segments = 25;
float radius = 1.0;
float left_angle = 245;
float right_angle = 115;
float branch_length = 12 - level*2.5;
float angle_change = 20;
// Draw the current circle
drawCircle(segments,radius,x1,y1);
char buff[5];
//itoa(t_root->name,buff,10);
draw_text(t_root->name,x1,y1);
if(t_root->left) {
// Draw the Left circle
float angle = left_angle - level*angle_change;
double radian = angle*3.14/180;
float m = (double)tan((double)radian);
float x2 = x1 + branch_length * sin((double) radian);
float y2 = y1 + branch_length * cos((double) radian);
drawNode(t_root->left,x2,y2,level+1);
draw_line(x1,y1,x2,y2);
float x3 = (x1+x2) / 2;
float y3 = (y1+y2) / 2;
char label[2];
label[0]='1';
label[1]='\0';
draw_text(label,x3,y3);
}
if(t_root->right) {
// Draw the Right circle
float angle = right_angle + level*angle_change;
float radian = angle*3.14/180;
float m = (double)tan((double)radian);
float x2 = x1 + branch_length * sin((double) radian);
float y2 = y1 + branch_length * cos((double) radian);
drawNode(t_root->right,x2,y2,level+1);
draw_line(x1,y1,x2,y2);
float x3 = (x1+x2) / 2;
float y3 = (y1+y2) / 2;
char label[2];
label[0]='0';
label[1]='\0';
draw_text(label,x3,y3);
}
}
void display(void) {
glClearColor (0.0,0.0,0.0,1.0);
glClear (GL_COLOR_BUFFER_BIT);
glLoadIdentity();
glTranslatef(0,10,-30);
glColor3f(1,1,1);
drawNode(root,0,0,0);
glutSwapBuffers();
}
void reshape (int w, int h) {
glViewport (0, 0, (GLsizei)w, (GLsizei)h);
glMatrixMode (GL_PROJECTION);
glLoadIdentity ();
gluPerspective (60, (GLfloat)w / (GLfloat)h, 0.1, 100.0);
glMatrixMode (GL_MODELVIEW);
}
void keyboard(unsigned char key, int x, int y)
{
switch (key) {
case 27:
exit(0);
break;
}
}
int _tmain(int argc, char** argv)
{
NODE* list = NULL;
float arr[10];
int n;
cout<<"Enter n:";
cin>>n;
for(int i=0; i<n; i++) {
cin>>arr[i];
// Create a new node and append it to the list
NODE* current = new NODE;
current->data = arr[i];
current->next = NULL;
current->left = NULL;
current->right = NULL;
current->parent = NULL;
current->name[0] = 65+i; current->name[1] = '\0';
// Appending the node to the list
add_element(&list,¤t);
}
// Display the nodes entered by the user along with their probabilities
display_list(list);
while(1) {
// Find the 2 smallest elements from the list
NODE* smallest1 = NULL;
NODE* smallest2 = NULL;
find_smallest(list,&smallest1,&smallest2);
if(!smallest2) {
root = smallest1;
break;
}
float small1 = smallest1->data;
float small2 = smallest2->data;
NODE* current = new NODE;
current->data = small1 + small2;
current->left = smallest1;
current->right = smallest2;
current->parent = NULL;
current->next = NULL;
strcpy(current->name,smallest1->name);
strcat(current->name,smallest2->name);
smallest1->parent = current;
smallest2->parent = current;
add_element(&list,¤t);
}
cout<<"\n\nHuffman code :\n\n";
char code[20];
code[0]='\0';
tree_traversal(root,code);
// OPENGL Drawing functions
glutInit (&argc, argv);
glutInitDisplayMode (GLUT_DOUBLE);
glutInitWindowSize (1200, 800);
glutInitWindowPosition (0, 0);
glutCreateWindow ("A Binary search tree");
// Register function pointers to the drawing framework
glutDisplayFunc (display);
glutIdleFunc (display);
glutReshapeFunc (reshape);
glutKeyboardFunc (keyboard);
glutMainLoop ();
cout<<endl;
return 0;
}
