Assignment #$5-$ Radix Sorting

Background:

The purpose of this assignment is to get familiar with the deque $($double$-$ended queue$)$ node$-$based structure along with generic data type. In this assignment, you will involve constructing Java functions that use linked nodes and head and tail references to operate the elements in the list. Moreover, to leverage the usefulness of the structure you designed, we use the deque to apply the radix sort to a list of integer numbers read from a input file.

A real$-$world application of the deque is to store the history of a web browser. The recently visited URLs are added to the front of the deque, and the URL at the back of the deque is removed after some specified number of insertions at the front. Another common application of the deque is to work like a list of undo operations in a software application.

Objectives:

This assignment will assess your mastery of the following objectives:

To construct double$-$end queue.

To understand how node references work in the linked lists.

To perform basic operations in the linked list.

To design interface, abstract class, and concrete classes. $($optional$)$

To design condition for the comparable class. $($optional$)$

Rules and Explanations:

Part $1$:

The original queue has a reference to the first element $($head$)$ of the queue. In this assignment, you are ask to construct a deque $($a double$-$ended queue$)$ that has an additional reference to the last element $($tail$)$ of the queue. Anyway, you are NOT allowed to use the tail reference in the LinkedDeque class. Deque is an ordered collection of items similar to the queue. It has two ends, a front and rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items. Deque allows adding new items at either the front or the rear. Furthermore, we can remove existing items from either end. In an insight, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.

We will develop a singly$-$linked implementation of a double$-$ended queue. There is an interface Deque that extends from the Queue interface with a new interface called Deque. The class LinkedQueue implements all prototypes in the interface Queue. You are not allowed to modify Queue, Deque, and LinkedQueue. You will develop a new class called LinkedDeque, and this class will extend the provided LinkedQueue class and implements all prototypes in the Deque interface. Please do not add any extra fields or methods. Write the code in the body of each required methods as following:

Method Description

public void addRear$($Type data$)$ The method adds element to the back

public void addFront$($Type data$)$ The method adds element to the front

public Type removeRear$()$ The method removes element from the back and return the removed element.

public Type removeFront$()$ The method removes element from the front and return the removed element.

public Type peekRear$()$ The method examines element from the back.

public Type peekFront$()$ The method examines element from the front.

In this assignment, you have to write JUnit tests for all public LinkedDeque operations $($including those inherited from LinkedQueue$).$ Your tests should provide complete code coverage $($including the toString$()$ method$).$ Think carefully about border cases and exceptional cases as you develop your code and your tests. You will need to take a screenshot that shows all test cases of LinkedDeque passed. Your unit tests should NOT produce any console output. Here is a list of examples of test cases you must have.

Method Description

public void testLinkedDeque$()$ Do nothing but check the size and if the queue is empty.

public void testAddRear$1()$ Add one element to the back and check size and queue in string format.

public void testAddRear$2()$ Add two elements to the back and check size and queue in string format.

public void testAddFront$1()$ Add one element to the front and check size and queue in string format.

public void testAddFront$2()$ Add two elements to the front and check size and queue in string format.

public void testAddFrontRear$1()$ Add three elements to the front and$/$or back then check size and queue in string format.

public void testAddFrontRear$2()$ Add three elements to the front and$/$or back then check size and queue in string format.

public void testRemoveRear$1()$ Remove the element from the back once then check size and queue in string format.

public void testRemoveRear$2()$ Remove the element from the back twice then check size and queue in string format.

public void testRemoveFront$1()$ Remove the element from the front once then check size and queue in string format.

public void testRemoveFront$2()$ Remove the element from the front twice then check size and queue in string format.

public void testPeekRear$()$ Examine the element from the back then check size and queue in string format.

public void testPeekFront$()$ Examine the element from the