SalehBinMohammed

package Test;

class Node {
    public char ch;
    public int freq;
    public Node left;
    public Node right;

    public Node(char ch) {
        this.ch = ch;
        freq = 1;
    }
    
    public boolean isLeaf() {
        return left == null && right == null;
    }
    
    public void freqIncrease() {
        freq++;
    }
    
    public String toString() {
        return String.format("Char: %c, frequency: %d", ch, freq);
    }
    
}

public class Huffman {
    public Node[] arr;
    private int loc;

    private Huffman() {
        arr = new Node[26];
        loc = 0;
    }
    
    public Huffman(String str) {
        this();
        countFrequency(str);
        BuildTree();
    }
    
    public void insert(Node e) {
        arr[loc++] = e;
    }
    
    public void delete(int index) {
        arr[index] = null;
        for(int i = index; i < loc - 1; i++) {
            arr[i] = arr[i + 1];
            arr[i + 1] = null;
        }
        loc--;
    }
    
    public int getIndex(char ch) {
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] != null && ch == arr[i].ch) {
                return i;
            }
        }
        return -1;
    }

    public void countFrequency(String str) {
        str = str.toUpperCase();
        for(char ch: str.toCharArray()) {
            int index = getIndex(ch);
            if(index != -1) {
                arr[index].freqIncrease();
            } else {
               insert(new Node(ch));
            }
        }
        insertionSort();
    }
    
    private void swap(int index1, int index2) {
        Node temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    
    public void insertionSort() {
        for(int i = 1; i < loc; i++) {
            for(int j = i; j > 0 && arr[j - 1].ch > arr[j].ch; j--) {
                swap(j , j - 1);
            }
        }
    }

    public boolean isArrayReady() {
        int count = 0;
       for(int i = 0; i < arr.length; i++) {
           if(arr[i] != null) {
               count++;
           }
       }
       return count == 1;
    }
    
    public Node getTheMinimum() {
        int min = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != null && arr[min] != null && arr[min].freq > arr[i].freq) {
                min = i;
            }
        }
        Node temp = arr[min];
        delete(min);
        return temp;
    }
    
    public void BuildTree() {
        while (!isArrayReady()) {
            Node min1 = getTheMinimum();
            Node min2 = getTheMinimum();
            Node left = null, right = null;
            if(min1 == null && min2 == null)    break;
            if(min2 != null) {
            if(min1.freq >= min2.freq) {
                right = min1;
                left = min2; 
            } else {
                right = min2;
                left = min1;
            }
            insert(new Node('*'));
            arr[loc - 1].freq = min1.freq + min2.freq;
            } else {
                insert(new Node(min1.ch));
                arr[loc - 1].freq = min1.freq;
            }
            arr[loc - 1].left = left;
            arr[loc - 1].right = right;
        }
    }
    
    public void printArray() {
        for (Node chars : arr) {
            if (chars != null) {
                System.out.println(chars);
            }
        }
    }
    
    public void printTree() {
        printTree(arr[getIndex('*')]);
    }
    
    private void printTree(Node root) {
        if(root == null) return;
        System.out.println(root);
        printTree(root.left);
        printTree(root.right);
    }
    
    public void printTable() {
        printTable(arr[getIndex('*')], "");
    }
    
    private void printTable(Node root, String str) {
        if(root.isLeaf()) {
            System.out.println(root.ch + ": " + str);
        } else {
            printTable(root.left, str + 0);
            printTable(root.right, str + 1);
        }
    }
}

class Test {
    public static void main(String[] args) {
        Huffman h = new Huffman("This is his message");
        h.printTree();
        h.printTable();
    }
}