Complete the Compress.java file so that it computes the Huffman com$-$

pression code for WarAndPeace. Your program should use a level$-$order

traversal of the binary tree constructed by the Huffman algorithm to print

the codes in order of length $($shorter codes first$).$ War and Peace is the novel used, a snippet is attached. Send exactly what to put in the one code file.

HuffmanNode.java

$/**$ Node for constructing binary tree in Huffman algorithm. $*/$

public class HuffmanNode implements Comparable $\{$

private char c; $//$ The character,

$//$private double f; $//$ the character's frequency.

private int f; $//$ the character's frequency.

private HuffmanNode left;

private HuffmanNode right;

private String code; $//$ This will contain the optimal binary code.

HuffmanNode$($char ch$,$ int fr$,$ HuffmanNode l$,$ HuffmanNode r$)\{$

c $=$ ch;

f $=$ fr;

left $=$ l;

right $=$ r;

code $=""$;

$\}$

public char getCharacter$()\{$

return c;

$\}$

public int getFrequency$()\{$

return f;

$\}$

public HuffmanNode getLeft$()\{$

return left;

$\}$

public HuffmanNode getRight$()\{$

return right;

$\}$

public void setCharacter$($char ch$)\{$

c $=$ ch;

$\}$

public void setFrequency$($int fr$)\{$

f $=$ fr;

$\}$

public String getCode$()\{$

return code;

$\}$

public void setCode$($String c$)\{$

code $=$ c;

$\}$

public boolean isLeaf$()\{$

return$(($left$==$null$)$&&$($right$==$null$))$;

$\}$

public String toString$()\{$

String s $=$ Character.toString$($c$)+""+$

Integer.toString$($f$)$;

return s;

$\}$

public int compareTo$($HuffmanNode h$)\{$

if$($this$.$f $-$ h$.$f $<mtext></mtext><mn>0</mn><mi>)</mi>$

return $1$;

else if$($this$.$f $-$ h$.$f $>0)$

return $-1$;

else

return $0$;

$\}$

$\}$

Compress.java

$/**$

Implement Huffman code compression for example in notes. Create a

binary tree with nodes defined in HuffmanNode.java class. We need

a MinHeap; cheat by switching the comparator in HuffmanNode.java.

$*/$

import java.util.Queue;

import java.util.ArrayList;

import java.util.LinkedList;

import java.io$.$File;

import java.io$.$FileReader;

import java.io$.$IOException;

import java.io$.$FileInputStream;

public class Compress $\{$

public static void main$($String$[]$ args$)$ throws IOException $\{$

MaxHeap Q $=$ new MaxHeap$()$;

$//$ Enter data from example in class.

FileReader inputStream $=$ null;

ArrayList letters $=$ new ArrayList$()$;

ArrayList frequencies $=$ new ArrayList$()$;

try $\{$

inputStream $=$ new FileReader$("$WarAndPeace$")$;

int c;

while $(($c $=$ inputStream.read$())!=-1)\{$

Character ch $=($char$)$ c;

int i $=$ letters.indexOf$($ch$)$;

if$($i$>-1)$

frequencies.set$($i$,$ frequencies.get$($i$)+1)$;

else

$\{$

letters.add$($ch$)$;

frequencies.add$(1)$;

$\}$

$\}$

$\}$ finally $\{$

if $($inputStream $!=$ null$)\{$

inputStream.close$()$;

$\}$

$\}$

for$($int j$=0$; j elts $=$ levelorderElements$($r$)$;

System.out.println$("$Now do levels"$)$;

for$($HuffmanNode nd : elts$)$

if$($nd$.$isLeaf$())$ System.out.println$($nd$.$getCharacter$()+""+$nd$.$getCode$())$;

$\}$

$/*$ Recursively descend to leaves, constructing code as we go$.*/$

public static void printLeaves$($HuffmanNode r$)\{$

if$($r $==$ null$)$ return;

if$(($r$.$getLeft$()==$ null$)$ &&

$($r$.$getRight$()==$ null$))\{$

System.out.println$($r$.$getCode$()+""+$r$)$;

return;

$\}$

if$($r$.$getLeft$()!=$ null$)\{$

r$.$getLeft$().$setCode$($r$.$getCode$()+\text{'}0\text{'})$;

printLeaves$($r$.$getLeft$())$;

$\}$

if$($r$.$getRight$()!=$ null$)\{$

r$.$getRight$().$setCode$($r$.$getCode$()+\text{'}1\text{'})$;

printLeaves$($r$.$getRight$())$;

$\}$

$\}$

public static ArrayList levelorderElements$($HuffmanNode r$)\{$

$//$ return nodes in level order: root, then children of root, etc.

if$($r$==$null$)$

return null;

ArrayList elts $=$ new ArrayList$()$;

$//$ Fill in$.$

return elts;

$\}$

$\}$

$```$

The Project Gutenberg EBook of War and Peace, by Leo Tolstoy

This eBook is for the use of anyone anywhere at no cost and with

almost no restrictions whatsoever. You may copy it$,$ give it away or

re$-$use it under the terms of the Project Gutenberg License included

with this eBook or online at www$.$gutenberg.org

Title: War and Peace

Author: Leo Tolstoy

Posting Date: January $10,2009[$EBook #$2600]$

Release Date: April, $2001$

Language: English

Character set encoding: ASCII

$***$ START OF THIS PROJECT GUTENBERG EBOOK WAR AND PEACE $***$

$```$

An Anonymous Volunteer Complete the Compress.java file so that it computes the Huffman compression code for WarAndPeace. Your program should use a level$-$order traversal of the binary tree constructed by the Huffman algorithm to print the codes in order of length $($shorter codes first$).$

You can download the files Compress.java, HuffmanNode.java, and WarAndPeace from Canvas $($and MaxHeap.java if you have not downloaded it previously$).$

Suppose that you need to "approximately sort" arrays of length $\backslash ($ n $\backslash ),$ in the sense that if the $\backslash ($ i $\backslash )$ th smallest element of the input is at index $\backslash ($ j $\backslash )$ in the output, then $\backslash (|$i$-$j$|\backslash$leq k $\backslash ),$ for some fixed number $\backslash ($ k $\backslash )($small compared to $\backslash ($ n $\backslash )).$ Describe an efficient algorithm and characterize the asymptotic running time $($state whether your analysis is worst$-$case or average$-$case$).```$

The Project Gutenberg EBook of War and Peace, by Leo Tolstoy

This eBook is for the use of anyone anywhere at no cost and with

almost no restrictions whatsoever. You may copy it$,$ give it away or

re$-$use it under the terms of the Project Gutenberg License included

with this eBook or online at www$.$gutenberg.org

Title: War