I need to finish a class about sort queues and merge sorted queues in java.

Please help me on this one and I will rate if your code passes all JUnit tests I provided in the JUnit test file.

I have three java files:

First is MergeSorter.java, which I have to work on.

Second is Queue.java which I already finished. This java file is needed to complete to code MergeSorter.java.

Third is the JUnite test file, PublicMergeSorterTest.java.

Here is MergeSorter.java:

package sorting;

import structures.Queue;

/**

* A class containing methods to sort queues and merge sorted queues.

* "Sorted" means in ascending order: the front of the queue is the smallest

* element, and the rear of the queue is the largest.

* e1 is less than or equal to e2 if and only if (e1.compareTo(e2) <= 0)

*/

public class MergeSorter> {

/**

* Returns a new queue containing the elements from the input queue

* in sorted order.

* Implement this method recursively:

* In the base case, return the queue with no further work.

* Otherwise:

* First, call divide to split the input queue into two smaller output queues.

* Then, recursively mergeSort each of these two smaller queues.

* Finally, return the result of merging these two queues.

*

* @param queue an input queue

* @return a sorted copy of the input queue

*/

public Queue mergeSort(Queue queue) {

Queue input = new Queue(queue);

Queue output1 = new Queue(); // output queue 1

Queue output2 = new Queue(); // output queue 2

// TODO 1

return null;

}

/**

* Split elements from the input queue into the output queues, roughly

* half and half.

*

* @param input a queue

* @param output1 a queue into which about half of the elements in input should go

* @param output2 a queue into which the other half of the elements in input should go

*/

void divide(Queue input, Queue output1, Queue output2) {

// TODO 2

}

/**

* Merge sorted input queues into an output queue in sorted order,

* and returns that queue. To do so: while there are still elements

* in at least one of the input queues, compare the front elements

* and pick the smaller among the two, dequeue it, and enqueue it

* to the output queue. Remember, the Queue class has a peek method

* which allows you to check the front element without removing it.

*

* @param input1 a sorted queue

* @param input2 a sorted queue

* @return a sorted queue consisting of all elements from input1 and input2

*/

Queue merge(Queue input1, Queue input2) {

Queue output = new Queue();

// TODO 3

return null;

}

}

Here is Queue.java:

package structures;

import java.util.NoSuchElementException;

/**************************************************************************************

* NOTE: before starting to code, check support/structures/UnboundedQueueInterface.java

* for detailed explanation of each interface method, including the parameters, return

* values, assumptions, and requirements

***************************************************************************************/

public class Queue implements UnboundedQueueInterface {

private Node front;

private Node rear;

private int num;

public Queue() {

// TODO 1

front = null;

rear = null;

num = 0;

}

public Queue(Queue other) {

// TODO 2

front = null;

rear = null;

num = 0;

Node curr = other.front;

while(curr!=null) {

enqueue(curr.data);

curr = curr.next;

}

}

@Override

public boolean isEmpty() {

// TODO 3

return front==null;

}

@Override

public int size() {

// TODO 4

return num;

}

@Override

public void enqueue(T element) {

// TODO 5

if(front == null) {

front = new Node(element);

rear = front;

}

else {

Node node = new Node(element);

rear.next = node;

rear = node;

}

num++;

}

@Override

public T dequeue() throws NoSuchElementException {

// TODO 6

T data = front.data;

if(front.next == null) {

front = null;

rear = null;

}

else

front = front.next;

num--;

return data;

}

@Override

public T peek() throws NoSuchElementException {

// TODO 7

return front.data;

}

@Override

public UnboundedQueueInterface reversed() {

// TODO 8

if(isEmpty()) {

return new Queue();

}

T arr[] = (T[]) new Object[size()];

Node curr = front;

int i=0;

while(curr != null) {

arr[i] = curr.data;

i++;

curr = curr.next;

}

Queue reverse = new Queue();

for(i=arr.length-1;i>=0;i--) {

reverse.enqueue(arr[i]);

}

return reverse;

}

}

class Node {

public T data;

public Node next;

public Node(T data) { this.data=data;}

public Node(T data, Node next) {

this.data = data; this.next=next;

}

}

Here is PublicMergeSorterTest.java:

package sorting;

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Before;

import org.junit.Test;

import structures.Queue;

public class PublicMergeSorterTest {

private MergeSorter ms = new MergeSorter();

private Queue empty;

private Queue one;

private Queue unsorted;

private Queue output1;

private Queue output2;

@Before

public void before() {

empty = new Queue();

one = new Queue();

output1 = new Queue();

output2 = new Queue();

one.enqueue(1);

unsorted = new Queue();

for (int i : new int[] {8, 4, 0, 3, 6, 1, 7, 9, 5, 2}) {

unsorted.enqueue(i);

}

}

@Test

public void testDivideEmpty() throws Exception {

ms.divide(empty, output1, output2);

assertTrue(empty.isEmpty());

assertTrue(output1.isEmpty());

assertTrue(output2.isEmpty());

}

@Test

public void testDivideOne() throws Exception {

ms.divide(one, output1, output2);

assertTrue(one.isEmpty());

assertTrue(output1.isEmpty() || output2.isEmpty());

assertFalse(output1.isEmpty() && output2.isEmpty());

}

@Test

public void testDivideNSplitsEvenly() throws Exception {

Queue q = new Queue();

for (int i = 0; i < 11; i++) {

q.enqueue(i);

}

ms.divide(q, output1, output2);

assertTrue(((output1.size() == 5) && (output2.size() == 6)) ||

((output1.size() == 6) && (output2.size() == 5)));;

}

@Test

public void testDivideNContainsAll() throws Exception {

Queue q = new Queue();

for (int i = 0; i < 11; i++) {

q.enqueue(i);

}

ms.divide(q, output1, output2);

int[] t = new int[11];

int i = 0;

while (!output1.isEmpty()) {

t[i] = output1.dequeue();

i++;

}

while (!output2.isEmpty()) {

t[i] = output2.dequeue();

i++;

}

Arrays.sort(t);

for (int j = 0; j < 11; j++) {

assertEquals(j, t[j]);

}

}

@Test

public void testMergeTwoEmpty() throws Exception {

Queue result = ms.merge(empty, empty);

assertTrue(result.isEmpty());

}

@Test

public void testMergeOneAndEmpty() throws Exception {

Queue result = ms.merge(one, empty);

assertEquals(1, result.size());

assertEquals(1, (int)result.dequeue());

}

@Test

public void testMergeEmptyAndOne() throws Exception {

Queue result = ms.merge(empty, one);

assertEquals(1, result.size());

assertEquals(1, (int)result.dequeue());

}

@Test

public void testMergeOneAndOne() throws Exception {

Queue two = new Queue();

two.enqueue(2);

Queue result = ms.merge(two, one);

assertEquals(2, result.size());

assertEquals(1, (int)result.dequeue());

assertEquals(2, (int)result.dequeue());

}

@Test

public void testMergeThreeAndOne() throws Exception {

Queue three = new Queue();

three.enqueue(-1);

three.enqueue(1);

three.enqueue(2);

Queue result = ms.merge(three, one);

assertEquals(4, result.size());

assertEquals(-1, (int)result.dequeue());

assertEquals(1, (int)result.dequeue());

assertEquals(1, (int)result.dequeue());

assertEquals(2, (int)result.dequeue());

}

@Test

public void testMergeOneAndThree() throws Exception {

Queue three = new Queue();

three.enqueue(-1);

three.enqueue(1);

three.enqueue(2);

Queue result = ms.merge(one, three);

assertEquals(4, result.size());

assertEquals(-1, (int)result.dequeue());

assertEquals(1, (int)result.dequeue());

assertEquals(1, (int)result.dequeue());

assertEquals(2, (int)result.dequeue());

}

@Test

public void testMergeSortEmpty() throws Exception {

Queue result = ms.mergeSort(empty);

assertTrue(result.isEmpty());

}

@Test

public void testMergeSortEmptyUnaliased() throws Exception {

Queue result = ms.mergeSort(empty);

assertTrue(result.isEmpty());

empty.enqueue(1);

assertTrue(result.isEmpty());

}

@Test

public void testMergeSort() throws Exception {

Queue sorted = ms.mergeSort(unsorted);

assertEquals(10, sorted.size());

for (int i = 0; i < 10; i++) {

assertEquals(i, (int)sorted.dequeue());

}

}

@Test

public void testMergeSortUnaliased() throws Exception {

Queue sorted = ms.mergeSort(unsorted);

sorted.dequeue();

unsorted.enqueue(10);

assertEquals(9, sorted.size());

assertEquals(11, unsorted.size());

}

}