$($Java$)$ implement the radix sort that can sort a file contains either all positive integers or a file

contains mixture of positive and negative integers.

$1.$ Input: one input txt file. $//-1$ for hard code file name.

inFile $($use args $[0])$: a text file contains a list of integers $($may contain negative numbers$)$

$2.$ Outputs:

a$)$ outFile$1($args $[1])$:

$-$ The input data, one data per text$-$line.

$-$ The entire hash table after each iteration $($move from one hash table to the other hash table.

$-$ Print the result of the sorted data, one data per text$-$line.

b$)$ deBugFile $($use args $[2])$: For all debugging prints.

$3.$ Data Structures

$-$ listNode class

$-($int$)$ data

$-($listNode$)$ next

Methods:

$-$ constructor $($data$)//$create a listNode node for data and make sure assign node$$s next $$ null

$-$ LLQueue class

$-($listNode$)$ head

$-($listNode$)$ tail

Methods:

$-$ constructor$(...)$

$-$ insertQ $($table$,$ index, newNode$)//$ insert the newNode after the tail of hashTable$[$table$][$index$].$

$//$ hashTable$[$table$][$index$].$tail.next $$ newNode

$//$ hashTable$[2][$tableSize$].$tail $$ newNode

$-($listNode $*)$ deleteQ $(...)//$ if Q is not empty, deletes and returns the node after the dummy

$-($bool$)$ isEmpty $(...)//$ Returns true if tail $==$ head, returns false otherwise.

$-$ printQueue $($whichTable$,$ index, File$)//$ File can be outFile$1$ or deBugFile.

$//$ Print to File the entire linked list in hashTable$[$whichTable$][$index$].$

$//$ For example, if whichTable is $1$ and index is $6,$ then print

Table $[1][6]$: $(-999,33)(33,36)(36,18)............(13,$ NULL$)$ NULL

$-$ A RadixSort class:

$-($int$)$ tableSize $//$ set to $10.$

$-($LLQueue$)$ hashTable$[2][$tableSize$]//21$D arrays $($size of $10)$ of linked listqueues with dummy nodes.

$//$ Initially, create a new listNode for each hashTable$[$i$][$j$]$ to point to and set hashTable$[$i$][$j$]\text{'}$s head and

$//$ tail point to the dummy node.

$-($int$)$ data

$-($int$)$ currentTable $//$ either $0$ or $1$

$-($int$)$ previousTable $//$ either $0$ or $1$

$-($int$)$ maxLength $//$ the number of digits of the largest integer to control the number of iterations of Radix sort

$-($int$)$ offSet $//$ if there is no negative integer in the data, offSet will be zero; otherwise, the offset is the absolute

$//$value of the smallest negative integer in the data;

$//$ the offSet will add to each data before radix sort and subtract off afterward.

$-($int$)$ digitPosition $//$ The digit position of data that is currently processing, initialize to $0.$

$-($int$)$ currentDigit $//$ the digit which is currently used for sorting.

Methods:

$-$ constructor $()//$ Creates hashTable$[2][$tableSize$].$

$//$ Use loops to create LLQueue for each hashTable$[$i$][$j$],$ i $=0$ to $1$ and j $=0$ to $9,$ where

$//$ make a new listNode $($as dummy node$)$ for each hashTable$[$i$][$j$]$ point to and initially, head and tail are

$//$ also point to dummy node.

$-$ preProcessing $(...)//$ Read from input file; determine the largest and smallest integers in the file

$//$ and establishes offset. See algorithm below. You may include this method in constructor!

$-$ RSort $(...)//$ Performs Radix sort; sorts data dogot from right$-$to$-$left. See algorithm below.

$//$ The algorithm is exactly the same as taught in class.

$-($int$)$ getLength $($data$)//$ Determines and returns the length of data.

$//**$ suggestion: convert data to string, then returns string length.

$-($int$)$ getIndex $($data$,$ position$)//$This method is the hash function that determines and returns the digit at the

$//$ position of data, which is the index of the hash table for insertion. For example,

$//$ if data is $31456,$ length is $5$; data position $0$ is $6$; $1$ is $5$; $2$ is $4$; $3$ is $1$ and $4$ is $3$

$-$ printTable $($whichTable$,$ File$)//$ On your own!

$//$ Call printQueue $(...)$ to print each none empty queue in hashTable$[$whichTable$]$ out to File.

$-$ printSortedData $($whichTable$,$ outFile$1)//$ Output the final result of sorted data.

$//$ Print node$$s data in none empty queue in hashTable$[$whichTable$][$index$],$ index $=0$ to tableSize

$//10$ numbers per text$-$line with space in between two numbers.

$//***$ make sure to subtract offSet before printing the data.

$4.$ main$()$

Step $0$: inFile $$ open via args $[0]$

outFile$1$ open via args $[1]$

deBugFile $$ open via args $[2]$

hashTable$[2][$tableSize$]$ create by RadixSort constructor

Step $1$: preProcessing $($inFile$,$ deBugFile$)$

Step $2$: close inFile

reopen inFile.

Step $3$: RSort $($inFile$,$ outFile$1,$ deBugFile$)$

Step $4$: close all files

$5.$ preProcessing $($inFile$,$ deBugFile$)$

Step $0$: deBugFile $"**$ Entering preProcessing $()"$

negativeNum $0$

positiveNum $0$

Step $1$: data $$ read one integer from inFile

if data $<$ negativeNum

negativeNum $$ data

if data $>$ positiveNum

positiveNum $$ data

Step $2$: repeat step $1$ until inFile is empty

Step $3$: if negativeNum $<0$

offSet $$ abs $($negativeNum$)$

else

offSet $0$

Step $4$: positiveNum $$ positiveNum $+$ offset

maxLength $$ getLength $($positiveNum$)$

Step $5$: deBugFile $$ In preProcessing $()$: negativeNum$=,$ offSet$=,$ positiveNum$=,$ maxDigits $=$ print values

Step $6$: deBugFile $$Leaving preProcessing $()$