All my four classes are working correctly except the test class. if someone coul
ID: 3777604 • Letter: A
Question
All my four classes are working correctly except the test class. if someone could help i will appreciate.
In Java
I'm writing a program to test the merge sort algorithm for linked lists.
I need to Print the list before being sorted and the list after sorting the elements
here is my code
TEST CLASS
import java.io.*;
import java.util.*;
public class Test {
Scanner input = new Scanner(System.in);
public static void main(String[] args) throws IOException {
OrderedLinkedList list
= new OrderedLinkedList(); //Line 1
IntElement num = new IntElement(); //Line 2
// Prompt the user to enter some integers
System.out.println("Enter integers numbers ");
String temp = input.hasnextLine();
String[] split = temp.split(" ");
for (int i = 0; i < split.length; i++) {
Integer a = Integer.parseInt(split[i]);
// insert the intgers into the list you created above
num.setNum(a);
list.insertNode(num);
}
System.out.println();
// Print the list before being sorted
// call the mergesort method
System.out.println();
// print the list after sorting the elements
}
}
ORDEREDLICKEDLIST CLASS
public class OrderedLinkedList extends LinkedListClass
{
//default constructor
public OrderedLinkedList()
{
super();
}
//copy constructor
public OrderedLinkedList(OrderedLinkedList otherList)
{
super(otherList);
}
public void linkedInsertionSort()
{
LinkedListNode lastInOrder;
LinkedListNode firstOutOfOrder;
LinkedListNode current;
LinkedListNode trailCurrent;
lastInOrder = first;
if(first == null)
System.out.println("Cannot sort an empty list");
else
if(first.link == null)
System.out.println("The list is of length 1. "
+ "Already in order");
else
while(lastInOrder.link != null)
{
firstOutOfOrder = lastInOrder.link;
if(firstOutOfOrder.info.compareTo(first.info) < 0)
{
lastInOrder.link = firstOutOfOrder.link;
firstOutOfOrder.link = first;
first = firstOutOfOrder;
}
else
{
trailCurrent = first;
current = first.link;
while(current.info.compareTo(firstOutOfOrder.info) < 0)
{
trailCurrent = current;
current = current.link;
}
if(current != firstOutOfOrder)
{
lastInOrder.link = firstOutOfOrder.link;
firstOutOfOrder.link = current;
trailCurrent.link = firstOutOfOrder;
}
else
lastInOrder = lastInOrder.link;
}
}
}//end linkedInsertionSort
//Method to determine whether searchItem is in
//the list.
//Postcondition: Returns true if searchItem is found
// in the list; otherwise, it returns
// false.
public boolean search(DataElement searchItem)
{
LinkedListNode current; //variable to traverse the list
boolean found;
current = first; //set current to point to the first
//node in the list
found = false; //set found to false
while(current != null && !found ) //search the list
if(current.info.compareTo(searchItem) >= 0)
found = true;
else
current = current.link; //make current point to
//the next node
if(found)
found = current.info.equals(searchItem);
return found;
}
//Method to insert insertItem in the list
//Postcondition: first points to the new list,
// newItem is inserted at the proper place
// in the list, and count is incremented by 1.
public void insertNode(DataElement insertItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
LinkedListNode newNode; //variable to create a node
boolean found;
newNode = new LinkedListNode(); //create the node
newNode.info = insertItem.getCopy(); //store newItem
//in the node
newNode.link = null; //set the link field of the node
//to null
if(first == null) //Case 1
{
first = newNode;
count++;
}
else
{
trailCurrent = first;
current = first;
found = false;
while(current != null && !found) //search the list
if(current.info.compareTo(insertItem) >= 0)
found = true;
else
{
trailCurrent = current;
current = current.link;
}
if(current == first) //Case 2
{
newNode.link = first;
first = newNode;
count++;
}
else //Case 3
{
trailCurrent.link = newNode;
newNode.link = current;
count++;
}
}//end else
}//end insertNode
//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list. Also, first points to the first
// node, last points to the last
// node of the updated list, and count
// is decremented by 1.
public void deleteNode(DataElement deleteItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
boolean found;
if(first == null) //Case 1; list is empty.
System.err.println("Can not delete from an "
+ "empty list.");
else
{
if(first.info.equals(deleteItem)) //Case 2
{
first = first.link;
count--;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point to
//the first node
current = first.link; //set current to point to the
//second node
while(current != null && !found)
{
if(current.info.compareTo(deleteItem) >= 0)
found = true;
else
{
trailCurrent = current;
current = current. link;
}
} //end while
if(current == null) //Case 4
System.out.println("Item to be deleted is "
+ "not in the list.");
else
if(current.info.equals(deleteItem)) //item to be
//deleted is in the list
{
if(first == current) //Case 2
{
first = first.link;
count--;
}
else //Case 3
{
trailCurrent.link = current.link;
count--;
}
}
else //Case 4
System.out.println("Item to be deleted is "
+ " not in the list.");
}
} //end else
} //end deleteNode
}
LINKEDLIST CLASS
public abstract class LinkedListClass
{
protected class LinkedListNode
{
DataElement info;
LinkedListNode link;
}
protected LinkedListNode first; //variable to store the
//address of the first
//node of the list
protected LinkedListNode last; //variable to store the
//address of the last
//node of the list
protected int count; //variable to store the number of nodes
//in the list
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0
public LinkedListClass()
{
first = null;
last = null;
count = 0;
}
//Method to determine whether the list is empty.
//Postcondition: Returns true if the list is empty;
// false otherwise.
public boolean isEmptyList()
{
return (first == null);
}
//Method to initialize the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0
public void initializeList()
{
first = null;
last = null;
count = 0;
}
//Method to output the data contained in each node.
public void print()
{
LinkedListNode current; //variable to traverse the list
current = first; //set current so that it points to
//the first node
while(current != null) //while more data to print
{
System.out.print(current.info + " ");
current = current.link;
}
}//end print
//Method to return the number of nodes in the list.
//Postcondition: The value of count is returned.
public int length()
{
return count;
}
//Method to return a reference of the object containing
//the data of the first node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the first node
// is returned.
public DataElement front()
{
DataElement temp = first.info.getCopy();
return temp;
}
//Method to return a reference of object containing
//the data of the last node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the last node
// is returned.
public DataElement back()
{
DataElement temp = last.info.getCopy();
return temp;
}
//Method to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found
// in the list; false otherwise.
public abstract boolean search(DataElement searchItem);
//Method to insert newItem in the list.
//Postcondition: first points to the new list
// and newItem is inserted at the
// beginning of the list. Also,
// last points to the last node and
// count is incremented by 1.
public void insertFirst(DataElement newItem)
{
LinkedListNode newNode; //variable to create the
//new node
newNode = new LinkedListNode(); //create the new node
newNode.info = newItem.getCopy(); //assign a copy of
//newItem to the node
newNode.link = first; //insert newNode before first
first = newNode; //make first point to the
//actual first node
if(last == null) //if the list was empty, newNode is
//also the last node in the list
last = newNode;
count++;
}
//Method to insert newItem at the end of the list.
//Postcondition: first points to the new list and
// newItem is inserted at the end
// of the list. Also, last points to
// the last node and
// count is incremented by 1.
public void insertLast(DataElement newItem)
{
LinkedListNode newNode; //variable to create the new node
newNode = new LinkedListNode(); //create the new node
newNode.info = newItem.getCopy(); //assign a copy of
//newItem to the node
newNode.link = null; //set the link field of
//newNode to null
if(first == null) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
}
else //if the list is not empty, insert newNode after last
{
last.link = newNode; //insert newNode after last
last = newNode; //set last to point to the actual last node
}
count++;
}//end insertLast
//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list. Also first points to the first
// node, last points to the last
// node of the updated list, and count
// is decremented by 1.
public abstract void deleteNode(DataElement deleteItem);
//Method to return a reference of the copy of otherList.
private void copy(LinkedListClass otherList)
{
LinkedListNode newNode; //variable to create a node
LinkedListNode current; //variable to traverse the list
first = null; //make this list empty
if(otherList.first == null) //otherList is empty
{
first = null;
last = null;
count = 0;
}
else
{
count = otherList.count;
current = otherList.first; //current points to the
//list to be copied
//copy the first element
first = new LinkedListNode(); //create the node
first.info = current.info.getCopy(); //copy the info
first.link = null; //set the link field of
//the node to null
last = first; //make last point to the first node
current = current.link; //make current point to the next
//node of the list being copied
//copy the remaining list
while(current != null)
{
newNode = new LinkedListNode();
newNode.info = current.info.getCopy();
newNode.link = null;
last.link = newNode;
last = newNode;
current = current.link;
}//end while
}//end else
}//end copy
//Method to return a reference of the copy of otherList.
public void copyList(LinkedListClass otherList)
{
if(this != otherList) //avoid self-copy
copy(otherList);
}
//copy constructor
public LinkedListClass(LinkedListClass otherList)
{
copy(otherList);
}//end copy constructor
}
public class IntElement extends DataElement
{
protected int num;
//default constructor
public IntElement()
{
num = 0;
}
//constructor with parameters
public IntElement(int x)
{
num = x;
}
//copy constructor
public IntElement(IntElement otherElement)
{
num = otherElement.num;
}
//Method to set the value of the instance variable num
//Postcondition: num = x;
public void setNum(int x)
{
num = x;
}
//Method to return the value of the instance variable num
//Postcondition: The value of num is returned
public int getNum()
{
return num;
}
public boolean equals(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
return (num == temp.num);
}
public int compareTo(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
return (num - temp.num);
}
public void makeCopy(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
num = temp.num;
}
public DataElement getCopy()
{
IntElement temp = new IntElement(num);
return temp;
}
public String toString()
{
return String.valueOf(num);
}
}
DATAELEMENT CLASS
public abstract class DataElement
{
public abstract boolean equals(DataElement otherElement);
//Method to determine if two objects contains the same data
//Postcondition: Returns true if this object contains the
// data is the object otherElement; otherwise it
// returns false otherwise
public abstract int compareTo(DataElement otherElement);
//Method to compare two objects.
//Postcondition: Returns a value < 0 if this element is
// less than otherElement;
// Returns 0 if this element is same as
// otherElement;
// Returns a value > 0 if this element is
// greater than otherElement;
public abstract void makeCopy(DataElement otherElement);
//Method to copy otherElement into this element
//Postcondition: data of otherElement is copied into
// this object
public abstract DataElement getCopy();
//Method to return a copy of this object.
//Postcondition: A copy of this object is created and
// a reference of the copy is returned
}
Explanation / Answer
//Remove getCopy method on info of DataElement object in OrderedLinkedList and LinkedListClass
//DataElement.java
public abstract class DataElement
{
public abstract boolean equals(DataElement otherElement);
//Method to determine if two objects contains the same data
//Postcondition: Returns true if this object contains the
// data is the object otherElement; otherwise it
// returns false otherwise
public abstract int compareTo(DataElement otherElement);
//Method to compare two objects.
//Postcondition: Returns a value < 0 if this element is
// less than otherElement;
// Returns 0 if this element is same as
// otherElement;
// Returns a value > 0 if this element is
// greater than otherElement;
public abstract void makeCopy(DataElement otherElement);
//Method to copy otherElement into this element
//Postcondition: data of otherElement is copied into
// this object
public abstract DataElement getCopy();
//Method to return a copy of this object.
//Postcondition: A copy of this object is created and
// a reference of the copy is returned
}
----------------------------------------
public class IntElement extends DataElement
{
protected int num;
//default constructor
public IntElement()
{
num = 0;
}
//constructor with parameters
public IntElement(int x)
{
num = x;
}
//copy constructor
public IntElement(IntElement otherElement)
{
num = otherElement.num;
}
//Method to set the value of the instance variable num
//Postcondition: num = x;
public void setNum(int x)
{
num = x;
}
//Method to return the value of the instance variable num
//Postcondition: The value of num is returned
public int getNum()
{
return num;
}
public boolean equals(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
return (num == temp.num);
}
public int compareTo(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
return (num - temp.num);
}
public void makeCopy(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
num = temp.num;
}
public DataElement getCopy()
{
IntElement temp = new IntElement(num);
return temp;
}
public String toString()
{
return String.valueOf(num);
}
}
----------------------------------------
public abstract class LinkedListClass
{
protected class LinkedListNode
{
DataElement info;
LinkedListNode link;
}
protected LinkedListNode first; //variable to store the
//address of the first
//node of the list
protected LinkedListNode last; //variable to store the
//address of the last
//node of the list
protected int count; //variable to store the number of nodes
//in the list
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0
public LinkedListClass()
{
first = null;
last = null;
count = 0;
}
//Method to determine whether the list is empty.
//Postcondition: Returns true if the list is empty;
// false otherwise.
public boolean isEmptyList()
{
return (first == null);
}
//Method to initialize the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0
public void initializeList()
{
first = null;
last = null;
count = 0;
}
//Method to output the data contained in each node.
public void print()
{
LinkedListNode current; //variable to traverse the list
current = first; //set current so that it points to
//the first node
while(current != null) //while more data to print
{
System.out.print(current.info + " ");
current = current.link;
}
}//end print
//Method to return the number of nodes in the list.
//Postcondition: The value of count is returned.
public int length()
{
return count;
}
//Method to return a reference of the object containing
//the data of the first node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the first node
// is returned.
public DataElement front()
{
DataElement temp = first.info;
return temp;
}
//Method to return a reference of object containing
//the data of the last node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the last node
// is returned.
public DataElement back()
{
DataElement temp = last.info;
return temp;
}
//Method to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found
// in the list; false otherwise.
public abstract boolean search(DataElement searchItem);
//Method to insert newItem in the list.
//Postcondition: first points to the new list
// and newItem is inserted at the
// beginning of the list. Also,
// last points to the last node and
// count is incremented by 1.
public void insertFirst(DataElement newItem)
{
LinkedListNode newNode; //variable to create the
//new node
newNode = new LinkedListNode(); //create the new node
newNode.info = newItem; //assign a copy of
//newItem to the node
newNode.link = first; //insert newNode before first
first = newNode; //make first point to the
//actual first node
if(last == null) //if the list was empty, newNode is
//also the last node in the list
last = newNode;
count++;
}
//Method to insert newItem at the end of the list.
//Postcondition: first points to the new list and
// newItem is inserted at the end
// of the list. Also, last points to
// the last node and
// count is incremented by 1.
public void insertLast(DataElement newItem)
{
LinkedListNode newNode; //variable to create the new node
newNode = new LinkedListNode(); //create the new node
newNode.info = newItem; //assign a copy of
//newItem to the node
newNode.link = null; //set the link field of
//newNode to null
if(first == null) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
}
else //if the list is not empty, insert newNode after last
{
last.link = newNode; //insert newNode after last
last = newNode; //set last to point to the actual last node
}
count++;
}//end insertLast
//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list. Also first points to the first
// node, last points to the last
// node of the updated list, and count
// is decremented by 1.
public abstract void deleteNode(DataElement deleteItem);
//Method to return a reference of the copy of otherList.
private void copy(LinkedListClass otherList)
{
LinkedListNode newNode; //variable to create a node
LinkedListNode current; //variable to traverse the list
first = null; //make this list empty
if(otherList.first == null) //otherList is empty
{
first = null;
last = null;
count = 0;
}
else
{
count = otherList.count;
current = otherList.first; //current points to the
//list to be copied
//copy the first element
first = new LinkedListNode(); //create the node
first.info = current.info; //copy the info
first.link = null; //set the link field of
//the node to null
last = first; //make last point to the first node
current = current.link; //make current point to the next
//node of the list being copied
//copy the remaining list
while(current != null)
{
newNode = new LinkedListNode();
newNode.info = current.info;
newNode.link = null;
last.link = newNode;
last = newNode;
current = current.link;
}//end while
}//end else
}//end copy
//Method to return a reference of the copy of otherList.
public void copyList(LinkedListClass otherList)
{
if(this != otherList) //avoid self-copy
copy(otherList);
}
//copy constructor
public LinkedListClass(LinkedListClass otherList)
{
copy(otherList);
}//end copy constructor
}
----------------------------------------
public class OrderedLinkedList extends LinkedListClass
{
//default constructor
public OrderedLinkedList()
{
super();
}
//copy constructor
public OrderedLinkedList(OrderedLinkedList otherList)
{
super(otherList);
}
public void linkedInsertionSort()
{
LinkedListNode lastInOrder;
LinkedListNode firstOutOfOrder;
LinkedListNode current;
LinkedListNode trailCurrent;
lastInOrder = first;
if(first == null)
System.out.println("Cannot sort an empty list");
else
if(first.link == null)
System.out.println("The list is of length 1. "+ "Already in order");
else
while(lastInOrder.link != null)
{
firstOutOfOrder = lastInOrder.link;
if(firstOutOfOrder.info.compareTo(first.info)<0)
{
lastInOrder.link = firstOutOfOrder.link;
firstOutOfOrder.link = first;
first = firstOutOfOrder;
}
else
{
trailCurrent = first;
current = first.link;
while(current.info.compareTo(firstOutOfOrder.info) < 0)
{
trailCurrent = current;
current = current.link;
}
if(current != firstOutOfOrder)
{
lastInOrder.link = firstOutOfOrder.link;
firstOutOfOrder.link = current;
trailCurrent.link = firstOutOfOrder;
}
else
lastInOrder = lastInOrder.link;
}
}
}//end linkedInsertionSort
//Method to determine whether searchItem is in
//the list.
//Postcondition: Returns true if searchItem is found
// in the list; otherwise, it returns
// false.
public boolean search(DataElement searchItem)
{
LinkedListNode current; //variable to traverse the list
boolean found;
current = first; //set current to point to the first
//node in the list
found = false; //set found to false
while(current != null && !found ) //search the list
if(current.info.compareTo(searchItem) >= 0)
found = true;
else
current = current.link; //make current point to
//the next node
if(found)
found = current.info.equals(searchItem);
return found;
}
//Method to insert insertItem in the list
//Postcondition: first points to the new list,
// newItem is inserted at the proper place
// in the list, and count is incremented by 1.
public void insertNode(DataElement insertItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
LinkedListNode newNode; //variable to create a node
boolean found;
newNode = new LinkedListNode(); //create the node
newNode.info = insertItem.getCopy(); //store newItem
//in the node
newNode.link = null; //set the link field of the node
//to null
if(first == null) //Case 1
{
first = newNode;
count++;
}
else
{
trailCurrent = first;
current = first;
found = false;
while(current != null && !found) //search the list
if(current.info.compareTo(insertItem) >= 0)
found = true;
else
{
trailCurrent = current;
current = current.link;
}
if(current == first) //Case 2
{
newNode.link = first;
first = newNode;
count++;
}
else //Case 3
{
trailCurrent.link = newNode;
newNode.link = current;
count++;
}
}//end else
}//end insertNode
//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list. Also, first points to the first
// node, last points to the last
// node of the updated list, and count
// is decremented by 1.
public void deleteNode(DataElement deleteItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
boolean found;
if(first == null) //Case 1; list is empty.
System.err.println("Can not delete from an "
+ "empty list.");
else
{
if(first.info.equals(deleteItem)) //Case 2
{
first = first.link;
count--;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point to
//the first node
current = first.link; //set current to point to the
//second node
while(current != null && !found)
{
if(current.info.compareTo(deleteItem) >= 0)
found = true;
else
{
trailCurrent = current;
current = current. link;
}
} //end while
if(current == null) //Case 4
System.out.println("Item to be deleted is "+ "not in the list.");
else
if(current.info.equals(deleteItem)) //item to be
//deleted is in the list
{
if(first == current) //Case 2
{
first = first.link;
count--;
}
else //Case 3
{
trailCurrent.link = current.link;
count--;
}
}
else //Case 4
System.out.println("Item to be deleted is "
+ " not in the list.");
}
} //end else
} //end deleteNode
}
----------------------------------------
import java.io.*;
import java.util.*;
public class Test {
//Create an instance of the Scanner class of static type
private static Scanner input = new Scanner(System.in);
public static void main(String[] args) throws IOException {
OrderedLinkedList list= new OrderedLinkedList(); //Line 1
IntElement num = new IntElement(); //Line 2
// Prompt the user to enter some integers
System.out.println("Enter integers numbers ");
//Call nextLIne method
String temp = input.nextLine();
String[] split = temp.split(" ");
for (int i = 0; i < split.length; i++)
{
Integer a = Integer.parseInt(split[i]);
// insert the intgers into the list you created above
num.setNum(a);
list.insertNode(num);
}
System.out.println("Before sorting:");
System.out.println(temp);
// Print the list before being sorted
// call the mergesort method
System.out.println(" After sorting:");
list.print();
System.out.println();
// print the list after sorting the elements
}
}
----------------------------------------
Output:
Enter integers numbers
7 8 9 5 4 3
Before sorting:
7 8 9 5 4 3
After sorting:
3 4 5 7 8 9