HuffmanTree.java

HuffmanTree.java

import java.util.Arrays;


/**
 * class HuffmanTree
 */
public class HuffmanTree {
    
    static int non_zero_element_count;
    
    private static int[] frequencies;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) 
    {               
        //example characters array
        //char characters[] = new char[] {'m','s','a','i','d','o','z','c'};
        //char characters[] = new char[] {'m','s','a','i','d'};
        char characters[] = new char[] {'a','b','c','d','e','f'};
        
        //example frequencies array number 1        
        //int frequencies[] = new int[] {10,13,16,30,50};      
        int frequencies[] = new int[] {45,13,12,16,9,5};      
        //example frequencies array number 2
        //int frequencies[] = new int[] {10,14,20,40,55,70,75,90};  //it's just another example vector.
        
        //expanded array
        int expanded_array[] = new int[50];
        
        //huffman array
        int huffman_tree[] = new int[50];
        
        //for loop variable
        int i;
        
        int min;
        
        int temp_for_frequency;
        
        char temp_for_character;
        
        
        for (i = 0; i < frequencies.length; i++) {
            // Assume first element is min
            min = i;
            for (int j = i + 1; j < frequencies.length; j++) {
                if (frequencies[j] < frequencies[min]) {
                    min = j;

                }
            }
            if (min != i) {
                
                temp_for_frequency = frequencies[i];
                frequencies[i] = frequencies[min];
                frequencies[min] = temp_for_frequency;
                
                temp_for_character = characters[i];
                characters[i] = characters[min];
                characters[min] = temp_for_character;
                
            }
           
        }
        
        //HuffmanTree.print_array(frequencies, 0, 1);
        
        //for(i = 0; i<characters.length; i++){
        //    System.out.print(characters[i]+" ");
        //}
        
        // This for loop written below copies all the elements of frequencies array to expanded array
        // Because in expanded array i will calculate new numbers
        for(i=0; i< frequencies.length ; i++){ 
            
            expanded_array[i] = frequencies[i];
            
        }
        
        System.out.println("Character array is: ");
        
        for(i=0;i<characters.length;i++){
            System.out.print(" '"+characters[i]+"' ");
        }
        
        System.out.println("\n\nFrequencies array is:");
        
        HuffmanTree.print_array(frequencies, 1, 0);
             
        // expand_array method takes expanded_array and returns new expanded array
        // for frequencies array 2, expanded_array before this function: [10, 13, 16, 30, 50]
        // after this function it will be like this: [10, 13, 16, -23, 30, -39, 50, -69, -119]
        // addition of two numbers will be negative in expanded_array        
        expanded_array = HuffmanTree.expand_array(expanded_array,frequencies.length);
        
        System.out.println("\n\nExpanded array is:");
        
        HuffmanTree.print_array(expanded_array, 1, 0);             
           
        huffman_tree = HuffmanTree.create_huffman_tree(expanded_array,huffman_tree);
        
        System.out.println("\nHuffman Tree is:");
        
        HuffmanTree.print_array(huffman_tree, 0, 0);
        
        System.out.println("\nCodes of characters:");
        
        HuffmanTree.print_codes_of_characters_according_to_huffman(huffman_tree,expanded_array,characters,frequencies);
        
    }
    
    
    
    
    /*
     * function expand_array
     * @param int expanded_array[]
     * @param int length_of_frequencies
     * @return expanded_array
     */
    public static int[] expand_array(int expanded_array[],int length_of_frequencies)
    {
        //int length = expanded_array.length;
        int total;
        int k;
        int j;
        
        for(int i=0; i< length_of_frequencies-1 ; i+=2 ){
            
            total = Math.abs(expanded_array[i]) + Math.abs(expanded_array[i+1]);
            
            k=0;
            
            while(total >= expanded_array[k] && k < length_of_frequencies){
                
                k++;
                
            }
            
            for(j=length_of_frequencies; j>k; j--){
                
                expanded_array[j] = expanded_array[j-1];
                
            }
            
            expanded_array[k] = total*-1; 
            
            length_of_frequencies ++;
        }
        
        return expanded_array;
    }
    
    
    
    
    /*
     * function create_huffman_tree
     * @param int expanded_array[]
     * @param int huffman_tree[]
     * @return int[] huffman_tree
     */   
    public static int[] create_huffman_tree(int expanded_array[],int huffman_tree[])
    {
        //for loop variable
        int i=0;
        
        //this will hold non zero element count of expanded_array
        int non_zero_element_count=0;
        
        //this will hold the node will written in loop
        int indice;
        
        //this will be used when searching the elements of addition 
        int indice_of_left;
        
        //this will be used when searching the elements of addition 
        int indice_of_right;
        
        //this is temporary variable, to short long calculations
        int total;
        
        
        while(expanded_array[i] != 0){
            
            //calculating the non-zero element count in expanded_array
            non_zero_element_count ++;
            
            i++;
        }
        
        HuffmanTree.non_zero_element_count = non_zero_element_count; 
        
        System.out.println("\n\nCreating the Huffman Tree...");
        
        //root of huffman tree
        huffman_tree[0] = Math.abs(expanded_array[non_zero_element_count-1]);
        
        System.out.println("The root is joined to Huffman Tree:\t" + huffman_tree[0] );
        
        //end of this loop huffman tree will be ready
        for(i=non_zero_element_count-1;i>=0;i--){
            
            
            if(expanded_array[i] < 0){
                
                indice=0;
                
            
                while(huffman_tree[indice] != Math.abs(expanded_array[i])){
                    
                    indice ++;
                    
                }
            
                indice_of_left = 0;
            
                indice_of_right = i-1;
            
                total = Math.abs(expanded_array[indice_of_left]) + Math.abs(expanded_array[indice_of_right]);
                
                while( Math.abs(expanded_array[i]) != total || (indice_of_left +1 != indice_of_right) ){
                    
                    if(Math.abs(expanded_array[i]) > total ){
                        
                        indice_of_left ++;
                        
                    }else{
                        
                        indice_of_right --;
                        
                    }
                    
                    total = Math.abs(expanded_array[indice_of_left]) + Math.abs(expanded_array[indice_of_right]);
                    
                }
            
                System.out.println("Now these nodes added:\t\t\t" + Math.abs(expanded_array[indice_of_left]) + ", " + Math.abs(expanded_array[indice_of_right]));
                
                huffman_tree[indice*2+1] = Math.abs(expanded_array[indice_of_left]);
            
                huffman_tree[indice*2+2] = Math.abs(expanded_array[indice_of_right]);                              
            }
            
        }
        
        return huffman_tree;
        
    }
    
    
    
    
    /*
     * function print_array
     * @param int print[] will be printed array
     * @param int vertical indicates that will be printed horizontal or vertical
     * @return void
     */
    public static void print_array(int print[], int vertical, int print_zeros)
    {
        
        //for loop variable
        int i;        
        
        //if vertical is 0, then it will be printed horizontally
        if( 0 == vertical ){            
            
            //printing vertically
            for(i=0; i<print.length; i++){
                
                if( 1 == print_zeros){
                    System.out.println(i+"\t:"+print[i]);
                }else{
                    if(0 != print[i]){
                        System.out.println(i+"\t:"+print[i]);
                    }
                }
                
            }
            
        }else{
            
            //printin horizontally
            for(i=0; i<print.length; i++){
                
                if( 1 == print_zeros){
                    System.out.print(print[i]+"\t");
                }else{
                    if(0 != print[i]){
                        System.out.print(print[i]+"\t");
                    }
                }
            
            }
            
        }
        
    }
    
    
    
    
    
    
    /*
     * function print_codes_of_characters_according_to_huffman
     * @param int huffman_tree[]
     * @param int expanded_array[]
     * @return void
     */
    public static void print_codes_of_characters_according_to_huffman(int huffman_tree[], int expanded_array[],char characters[],int frequencies[]){
        //if 'd' is at huffman_tree[5] then it's indice will be 5.
        //in binary code 5 will be 110. if you delete first bit, you got it!
        int i;
        int indice;
        int indice_of_character;
        int decimal;       
        int search_element;
        String binary;
        binary = "";
        
        for( i=0; i<HuffmanTree.non_zero_element_count ; i++){
            
            if(expanded_array[i] > 0){
                
                search_element = Math.abs(expanded_array[i]);
                
                indice = HuffmanTree.search_for_value( huffman_tree, search_element );
                
                indice_of_character = HuffmanTree.search_for_value(frequencies, search_element);               
                
                indice = indice /2;
                
                binary =Integer.toBinaryString(indice);                                               
                               
                System.out.println("The code for character '"+characters[indice_of_character]+"' is this: "+binary);
                
            }            
        }
    }
    
    
    /*
     * function search_for_value
     * @param int arr[]
     * @param int s
     * @return int index
     */
    public static int search_for_value(int arr[], int s)
    {
                
        int i = 0;
        
        while(arr[i]!=s && i<arr.length) {
            i++;
        }
        
        if(i == arr.length) {
            return -1;
        }
        else {
            return i;
        }                   
        
    }    
}