The requsite source code is attatched: public class LinearNode<Item>{ private Li
ID: 3863492 • Letter: T
Question
The requsite source code is attatched:
public class LinearNode<Item>{
private LinearNode<Item> next;
private Item element;
/**
* Creates a node storing the specified element.
* @param elem element to be stored
*/
public LinearNode(Item elem) {
next = null;
element = elem;
}
/**
* Returns the node that follows this one.
* @return reference to next node
*/
public LinearNode<Item> getNext() {
return next;
}
/**
* Sets the node that follows this one.
* @param node node to follow this one
*/
public void setNext(LinearNode<Item> node) {
next = node;
}
/**
* Returns the element stored in this node.
* @return element stored at the node
*/
public Item getElement() {
return element;
}
/**
* Sets the element stored in this node.
* @param elem element to be stored at this node
*/
public void setElement(Item elem) {
element = elem;
}
}
public class ListQueue<Item> implements Queue<Item>, Comparable<Item>{
LinearNode<Item> tail; //back
LinearNode<Item> head; //front
private int count;
private int modCount;
public ListQueue() {
tail = null;
count = 0;
}
@Override
public boolean isEmpty() {
return count == 0;
}
@Override
public void enqueue(Item item) {
LinearNode newNode = new LinearNode(item);
if(isEmpty())
head = newNode;
else
tail.setNext(newNode);
tail = newNode;
count++;
modCount++;
}
@Override
public Item dequeue() {
if(isEmpty())
throw new NoSuchElementException();
Item result = head.getElement();
head = head.getNext();
count--;
modCount++;
if(isEmpty())
tail = null;
return result;
}
@Override
public Item front() {
if(isEmpty())
throw new NoSuchElementException();
return head.getElement();
}
@Override
public String toString()
{
LinearNode iter = head;
String result = "";
while(iter != null) {
result = iter.getElement() + " " + result;
iter = iter.getNext();
}
return result + "(front)";
}
@Override
public int size() {
return count;
}
@Override
public int compareTo(Item i){
return ((Comparable<Item>)this.front()).compareTo(i);
}
@Override
public Iterator<Item> iterator(){
return new LinkedListIterator(this);
}
/**
* LinkedIterator represents an iterator for a linked list of linear nodes.
*/
private class LinkedListIterator implements Iterator<Item>
{
private final int iteratorModCount; // the number of elements in the collection
private LinearNode current; // the current position
/**
* Sets up this iterator using the specified items.
*
* @param collection the collection the iterator will move over
* @param size the integer size of the collection
*/
public LinkedListIterator(ListQueue<Item> o)
{
current = head;
iteratorModCount = modCount;
}
/**
* Returns true if this iterator has at least one more element
* to deliver in the iteration.
*
* @return true if this iterator has at least one more element to deliver
* in the iteration
* @throws ConcurrentModificationException if the collection has changed
* while the iterator is in use
*/
@Override
public boolean hasNext() throws ConcurrentModificationException
{
if (iteratorModCount != modCount)
throw new ConcurrentModificationException();
return (current != null);
}
/**
* Returns the next element in the iteration. If there are no
* more elements in this iteration, a NoSuchElementException is
* thrown.
*
* @return the next element in the iteration
* @throws NoSuchElementException if the iterator is empty
*/
@Override
public Item next() throws ConcurrentModificationException
{
LinearNode previous = null;
if (!hasNext())
throw new NoSuchElementException();
Item result = (Item)current.getElement();
previous = current;
current = current.getNext();
return result;
}
}
}
public interface Queue<Item> extends Iterable<Item>{
/**
* Add an item.
* @param item an item
*/
public void enqueue(Item item);
/**
* Remove the least recently added item.
* @return an item
*/
public Item dequeue() throws NoSuchElementException;
/**
* Return, but do not remove, the most least added item.
* @return an item
*/
public Item front() throws NoSuchElementException;
/**
* Is the queue empty?
* @return if empty
*/
public boolean isEmpty();
/**
* Number of items in the queue.
* @return number of items
*/
public int size();
public Iterator<Item> iterator();
}
public class BaseMerging {
/**
* Entry point for sample output.
*
* @param args the command line arguments
*/
public static void main(String[] args) {
Queue q1 = new ListQueue(); q1.enqueue("T"); q1.enqueue("R"); q1.enqueue("O"); q1.enqueue("L"); q1.enqueue("E");
Queue q2 = new ListQueue(); q2.enqueue("X"); q2.enqueue("S"); q2.enqueue("P"); q2.enqueue("M"); q2.enqueue("E"); q2.enqueue("A");
System.out.println(q1.toString());
System.out.println(q2.toString());
//Q1
Queue merged = mergeQueues(q1, q2);
System.out.println(merged.toString());
//Q2
String[] a = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
sort(a);//Java is pass by value only. Can't be
Comparable[] a1 = mergeSort(a);
System.out.println(isSorted(a1));
System.out.println(isSorted(a));
show(a1);
//Q3
String[] b = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
shuffle(b);
show(b);
shuffle(b);
show(b);
}
public static Queue mergeQueues(Queue q1, Queue q2) {
Queue aux = new ListQueue();
while((!q2.isEmpty()) || (!q1.isEmpty())) {
if (q1.isEmpty())
while(!q2.isEmpty())
aux.enqueue(q2.dequeue());
else if(q2.isEmpty())
while(!q1.isEmpty())
aux.enqueue(q1.dequeue());
else if(((Comparable)q1.front()).compareTo(q2.front()) < 0){
aux.enqueue(q2.front());
q2.dequeue();
}
else if(((Comparable)q1.front()).compareTo(q2.front()) > 0){
aux.enqueue(q1.front());
q1.dequeue();
}
else
{
aux.enqueue(q1.front());
aux.enqueue(q2.front());
q1.dequeue();
q2.dequeue();
}
}
//TODO: implement this.
return aux;
}
public static void sort(Comparable[] a){
Comparable[] b = a;
b = mergeSort(a);
}
//helper
public static Comparable[] mergeSort(Comparable[] a) {
//base case
if(a.length <= 1)
return a;
int mid = a.length/2;
Comparable[] left = new Comparable[mid];
Comparable[] right = new Comparable[a.length - mid];
Comparable[] aux = new Comparable[a.length];
for(int i = 0; i < mid; i++)
left[i] = a[i];
int x = 0;
for(int i = mid; i < a.length; i++){
if(x < right.length){
right[x] = a[i];
x++;
}
}
left = mergeSort(left);
right = mergeSort(right);
aux = merge(left, right);
return aux;
}
//merge method
public static Comparable[] merge(Comparable[] a, Comparable[] b){
Comparable[] aux = new Comparable[a.length + b.length];
int indexL = 0;
int indexR = 0;
int indexAux = 0;
while(indexL < a.length || indexR < b.length){
if(indexL < a.length && indexR < b.length){
if(((Comparable)a[indexL]).compareTo(b[indexR]) < 0){
aux[indexAux] = a[indexL];
indexL++;
indexAux++;
}
else if(((Comparable)a[indexL]).compareTo(b[indexR]) > 0){
aux[indexAux] = b[indexR];
indexR++;
indexAux++;
}
//The two values in the array are equal
else{
aux[indexAux] = a[indexL];
indexAux++;
aux[indexAux] = b[indexR];
indexAux++;
indexL++;
indexR++;
}
}
else if(indexL < a.length && indexR >= b.length){
aux[indexAux] = a[indexL];
indexAux++;
indexL++;
}
else if(indexR < b.length && indexL >= a.length){
aux[indexAux] = b[indexR];
indexAux++;
indexR++;
}
}
return aux;
}
public static void shuffle(Object[] a) {
//TODO: implement this.
}
//sorting helper from text
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
//sorting helper from text
private static void show(Comparable[] a) {
for (Comparable a1 : a)
System.out.print(a1 + " ");
System.out.println();
}
//sorting helper from text
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i-1]))
return false;
return true;
}
}
Explanation / Answer
A. The method to merge two queues in the sorted order is given by :
B. The program to implement merge sort algorithm by passing only array as parameter is given by :
#include <iostream>
using namespace std;
//The merge function
void merge(int a[], int begin, int end)
{
int size = (end - begin) + 1;
int *b = new int [size]();
int i = begin;
int mid = (begin + end)/2;
int k = 0;
int j = mid + 1;
while (k < size)
{
if((i<=mid) && (a[i] < a[j]))
{
b[k++] = a[i++];
}
else
{
b[k++] = a[j++];
}
}
for(k=0; k < size; k++)
{
a[begin+k] = b[k];
}
delete []b;
}
void merge_sort(int Array[], int begin, int end)
{
int midIndex;
if (begin >= end)
{
return;
}
midIndex = (begin + end)/2;
merge_sort(Array, begin, midIndex);
merge_sort(Array, midIndex+1, end);
merge(Array, begin, end);
}
int main(int argc, char *argv[])
{
int Array[10] = {1,5,6,4,7,2,8,3,9,10};
merge_sort(Array, 0, 9);
for(int i=0; i < 10; i++)
{
cout << Array[i] << endl;
}
return 0;
}
Output:
C. The program to implement the shuffle function to an array is given by :
import java.util.ArrayList;
import static java.util.Collections.swap;
import java.util.List;
import java.util.Random;
public class Shuffle {
public static void shuffle(List<Integer> a) {
int n = a.size();
Random random = new Random();
random.nextInt();
int i = 0;
for (int begin = 0; i < n; i++) {
int end = begin + random.nextInt(n - i);
swap(a, begin, end);
}
}
private static void merge_sort(List<Integer> a, int begin, int end) {
int midIndex;
midIndex = (begin + end)/2;
merge_sort(a, begin, midIndex);
merge_sort(a, midIndex+1, end);
swap(a, begin, end);
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
shuffle(list);
for (int i : list) {
System.out.println(i);
}
}
}
Output:
4
6
2
3
1
7
5