Homework SourseArizona State University CSE205 Assignment 10 Due Date Thur
Arizona State University - CSE205
Assignment #10
Due Date
Thursday, November 10th, at 7pm.
Minimal Submitted Files
Important: This is an individual assignment. Please do not collaborate.
No late assignment will be accepted.
Make sure that you write every line of your code. Using code written by someone else will be considered a violation of the academic integrity and will result in a report to the Dean\'s office.
You are required, but not limited, to turn in the following source files:
Assignment10.java (This file does not need to be modified)
LinkedList.java (It needs to be modified)
ListIterator.java (This file does not need to be modified)
Requirements to get full credits in Documentation
The assignment number, your name, StudentID, Lecture number, and a class description need to be included at the top of each file/class.
A description of each method is also needed.
Some additional comments inside of long methods (such as a \"main\" method) to explain codes that are hard to follow should be written.
You can look at the Java programs in the text book to see how comments are added to programs.
New Skills to be Applied
In addition to what has been covered in previous assignments, the use of the following items, discussed in class, will probably be needed:
Linked Lists
Program Description
Class Diagram:
In the Assignment #10, you are given three files Assignment10.java, LinkedList.java, and ListIterator.java. You will need to add additional methods in the LinkedList class in the LinkedList.java file. The LinkedList will be tested using strings only.
Specifically, the following methods must be implemented in the LinkedList class:
(You should utilize listIterator() method already defined in the LinkedList class to obtain its LinkedListIterator object, and use the methods in the LinkedListIterator class to traverse from the first element to the last element of the linked list to define the following methods.)
1.
public String toString()
The toString method should concatenate strings in the linked list, and return a string of the following format:
{ Apple Banana Melon Orange }
Thus it starts with \"{\" and ends with \"}\", and there is a space between strings and \"{\" or \"}\". If the list is empty, it returns \"{ }\" with a space in between.
2.
public boolean isEmpty()
The isEmpty method returns true of the linked list is empty, false otherwise.
3.
public void addElement(Object element)
The addElement adds the parameter element at the parameter in the linked list in alphabetical order. For instance, if the linked list contains {Apple, Banana, Grape}, and a user tries to add \"Carrot\", then it should be added as:
{Apple, Banana, Carrot, Grape}.
4.
public Object removeElement(int index)
The removeElement removes the string (Object) at the parameter index and returns it. Note that this index starts with 0 just like array indices. For instance, if the linked list contains {Apple, Banana, Carrot, Grape} and the parameter index is 3, then \"Grape\" should be remove. If the parameter index is larger or smaller than the existing indices, it should throw an object of the IndexOutOfBoundsException class (and the content of the linked list should remain unchanged).
5.
public Object getElement(int index)
The getElement searches the string (Object) at the parameter index and returns it. Note that this index starts with 0 just like array indices. For instance, if the linked list contains {Apple, Banana, Carrot, Grape} and the parameter index is 3, then \"Grape\" will be returned. If the parameter index is larger or smaller than the existing indices, it should throw an object of the IndexOutOfBoundsException class (and the content of the linked list should remain unchanged).
6.
public void searchAndReplace(Object oldString, Object newString)
The searchAndReplace method searches all occurrences of the first parameter string (object) in the list, and replaces them with the second parameter string (object). If the parameter string does not exist in the linked list, then the linked list content will not change.
7.
public int indexOfLast(Object searchString)
The indexOfLast searches the parameter string (object) with the largest index, and returns its index. If the parameter string does not exist in the linked list, then it should return -1.
For instance, if the linked list contains { Apple Banana Banana Orange }, then after calling this method with the parameter \"Banana\", then it should return 2, which is the index of later Banana.
Test your LinkedList class with the given Assignment10.java file.
It is recommended to test boundary cases such as the cases when the linked list is empty, when it contains only one element, when adding/removing at the beginning or at the end of the linked list.
Code for Assignment 10 (Given)
Code given for LinkedList
Code given for ListIterator
Solution
Modified Code:
//Assignment10.java
import java.io.*;
public class Assignment10
{
public static void main(String[] args)
{
char input1;
String inputInfo = new String();
int operation2;
String line = new String();
//create a linked list to be used in this method.
LinkedList list1 = new LinkedList();
try
{
// print out the menu
printMenu();
// create a BufferedReader object to read input from a keyboard
InputStreamReader isr = new InputStreamReader (System.in);
BufferedReader stdin = new BufferedReader (isr);
do
{
System.out.print(\"What action would you like to perform?\ \");
line = stdin.readLine().trim(); //read a line
input1 = line.charAt(0);
input1 = Character.toUpperCase(input1);
if (line.length() == 1) //check if a user entered only one character
{
switch (input1)
{
case \'A\': //Add String
System.out.print(\"Please enter a string to add:\ \");
String str1 = stdin.readLine().trim();
list1.addElement(str1);
break;
case \'G\': //Get a String at a certain index
System.out.print(\"Please enter an index of a string to get:\ \");
inputInfo = stdin.readLine().trim();
int getIndex = Integer.parseInt(inputInfo);
try
{
String getString = list1.getElement(getIndex).toString();
System.out.print(\"The string at the index \" + getIndex + \" is \"
+ getString + \"\ \");
}
catch(IndexOutOfBoundsException ex)
{
System.out.print(\"The index is not valid\ \");
}
break;
case \'E\': //Check if the linked list is empty
boolean empty = list1.isEmpty();
if (empty)
System.out.print(\"The linked list is empty\ \");
else
System.out.print(\"The linked list is not empty\ \");
break;
case \'I\': //Get the last index of a given String
System.out.print(\"Please enter a string to search:\ \");
String str2 = stdin.readLine().trim();
int searchIndex = list1.indexOfLast(str2);
if (searchIndex != -1)
System.out.print(\"The index of the last \" + str2 + \" is \" + searchIndex
+ \"\ \");
else
System.out.print(\"The string \" + str2
+ \" does not exist in the linked list\ \");
break;
case \'L\': //List Strings
System.out.print(list1.toString());
break;
case \'Q\': //Quit
break;
case \'R\': //Remove a String
System.out.print(\"Please enter an index of a string to remove:\ \");
inputInfo = stdin.readLine().trim();
int removeIndex = Integer.parseInt(inputInfo);
try
{
String removeString = (String) list1.removeElement(removeIndex);
System.out.print(\"The string at the index \" + removeIndex + \" was \"
+ removeString + \" and was removed\ \");
}
catch(IndexOutOfBoundsException ex)
{
System.out.print(\"The index is not valid\ \");
}
break;
case \'S\': //Search and Replace
System.out.print(\"Please enter a string to replace:\ \");
String original = stdin.readLine().trim();
System.out.print(\"Please enter a string used to replace with:\ \");
String newStr = stdin.readLine().trim();
list1.searchAndReplace(original, newStr);
break;
case \'?\': //Display Menu
printMenu();
break;
default:
System.out.print(\"Unknown action\ \");
break;
}
}
else
{
System.out.print(\"Unknown action\ \");
}
} while (input1 != \'Q\' || line.length() != 1);
}
catch (IOException exception)
{
System.out.print(\"IO Exception\ \");
}
}
/** The method printMenu displays the menu to a user **/
public static void printMenu()
{
System.out.print(\"Choice\\t\\tAction\ \" +
\"------\\t\\t------\ \" +
\"A\\t\\tAdd String\ \" +
\"G\\t\\tGet String\ \" +
\"E\\t\\tCheck if Empty\ \" +
\"I\\t\\tIndex of Last String\ \" +
\"L\\t\\tList Strings\ \" +
\"Q\\t\\tQuit\ \" +
\"R\\t\\tRemove String\ \" +
\"S\\t\\tSearch and Replace\ \" +
\"?\\t\\tDisplay Help\ \ \");
} //end of printMenu()
}
//ListIterator.java
public interface ListIterator
{
//Move Moves the iterator past the next element.
Object next();
// Tests if there is an element after the iterator position.
boolean hasNext();
// Adds an element before the iterator position
// and moves the iterator past the inserted element.
void add(Object element);
// Removes the last traversed element. This method may
// only be called after a call to the next() method.
void remove();
// Sets the last traversed element to a different value.
void set(Object element);
}
//LinkedList.java
import java.util.NoSuchElementException;
import java.lang.IndexOutOfBoundsException;
public class LinkedList
{
//nested class to represent a node
private class Node
{
public Object data;
public Node next;
}
//only instance variable that points to the first node.
private Node first;
// Constructs an empty linked list.
public LinkedList()
{
first = null;
}
// Returns the first element in the linked list.
public Object getFirst()
{
if (first == null)
{
NoSuchElementException ex
= new NoSuchElementException();
throw ex;
}
else
return first.data;
}
// Removes the first element in the linked list.
public Object removeFirst()
{
if (first == null)
{
NoSuchElementException ex = new NoSuchElementException();
throw ex;
}
else
{
Object element = first.data;
first = first.next; //change the reference since it\'s removed.
return element;
}
}
// Adds an element to the front of the linked list.
public void addFirst(Object element)
{
//create a new node
Node newNode = new Node();
newNode.data = element;
newNode.next = first;
//change the first reference to the new node.
first = newNode;
}
public String toString()
{
String st=\"{ \";
if(first==null)
return \"{ }\";
Node pp=first;
while(pp!=null)
{
st += pp.data.toString()+ \" \";
pp=pp.next;
}
return st+\"}\";
}
public boolean isEmpty()
{
if(first==null)
return true;
return false;
}
public void addElement(Object element)
{
Node newNode=new Node();
newNode.data=element;
if(first==null)
{
newNode.next=null;
first=newNode;
return;
}
else if(element.toString().compareTo(first.data.toString() )<0)
{
newNode.next=first;
first=newNode;
}
else
{
Node pp=first.next;
Node prev=first;
while(pp!=null )
{
if((element.toString().compareTo( pp.data.toString())<0))
break;
prev=pp;
pp=pp.next;
}
newNode.next=prev.next;
prev.next=newNode;
}
}
public Object removeElement(int index)
{
if(index==0)
return removeFirst();
else
{
Node pp=first;
Node prev=pp;
int kk=0;
while((pp!=null) &&(kk<index))
{
prev=pp;
pp=pp.next;
kk++;
}
if(pp!=null)
{
Node tt=pp;
prev.next=pp.next;
pp=prev;
return tt.data;
}
else
throw new IndexOutOfBoundsException();
}
}
public Object getElement(int index)
{
if(index==0)
return first.data;
else
{
Node pp=first;
int kk=0;
while(pp!=null && kk<index)
{
kk++;
pp=pp.next;
}
if(pp!=null)
return pp.data;
else
throw new IndexOutOfBoundsException();
}
}
public void searchAndReplace(Object oldString, Object newString)
{
if(first==null)
return;
else
{
Node pp=first;
while(pp!=null)
{
String tt= pp.data.toString();
int cc=tt.compareTo(oldString.toString());
if(cc==0)
{
pp.data=newString;
return;
}
pp=pp.next;
}
}
}
public int indexOfLast(Object searchString)
{
int index=0;
int sind=-1;
if(first==null)
{
NoSuchElementException ex = new NoSuchElementException();
throw ex;
}
else
{
Node pp=first;
while(pp!=null)
{
String tt=pp.data.toString();
int cc=searchString.toString().compareTo(tt);
if(cc==0)
sind=index;
index++;
pp=pp.next;
}
return sind;
}
}
// Returns an iterator for iterating through this list.
public ListIterator listIterator()
{
return new LinkedListIterator();
}
//nested class to define its iterator
private class LinkedListIterator implements ListIterator
{
private Node position; //current position
private Node previous; //it is used for remove() method
// Constructs an iterator that points to the front
// of the linked list.
public LinkedListIterator()
{
position = null;
previous = null;
}
// Tests if there is an element after the iterator position.
public boolean hasNext()
{
if (position == null) //not traversed yet
{
if (first != null)
return true;
else
return false;
}
else
{
if (position.next != null)
return true;
else
return false;
}
}
// Moves the iterator past the next element, and returns
// the traversed element\'s data.
public Object next()
{
if (!hasNext())
{
NoSuchElementException ex = new NoSuchElementException();
throw ex;
}
else
{
previous = position; // Remember for remove
if (position == null)
position = first;
else
position = position.next;
return position.data;
}
}
// Adds an element before the iterator position
// and moves the iterator past the inserted element.
public void add(Object element)
{
if (position == null) //never traversed yet
{
addFirst(element);
position = first;
}
else
{
//making a new node to add
Node newNode = new Node();
newNode.data = element;
newNode.next = position.next;
//change the link to insert the new node
position.next = newNode;
//move the position forward to the new node
position = newNode;
}
//this means that we cannot call remove() right after add()
previous = position;
}
// Removes the last traversed element. This method may
// only be called after a call to the next() method.
public void remove()
{
if (previous == position) //not after next() is called
{
IllegalStateException ex = new IllegalStateException();
throw ex;
}
else
{
if (position == first)
{
removeFirst();
}
else
{
previous.next = position.next; //removing
}
//stepping back
//this also means that remove() cannot be called twice in a row.
position = previous;
}
}
// Sets the last traversed element to a different value.
public void set(Object element)
{
if (position == null)
{
NoSuchElementException ex = new NoSuchElementException();
throw ex;
}
else
position.data = element;
}
} //end of LinkedListIterator class
} //end of LinkedList class
Sample Output:
run:
Choice Action
------ ------
A Add String
G Get String
E Check if Empty
I Index of Last String
L List Strings
Q Quit
R Remove String
S Search and Replace
? Display Help
What action would you like to perform?
A
Please enter a string to add:
Banana
What action would you like to perform?
A
Please enter a string to add:
Carrot
What action would you like to perform?
A
Please enter a string to add:
Apple
What action would you like to perform?
L
{ Apple Banana Carrot }What action would you like to perform?
A
Please enter a string to add:
Orange
What action would you like to perform?
L
{ Apple Banana Carrot Orange }What action would you like to perform?
R
Please enter an index of a string to remove:
1
The string at the index 1 was Banana and was removed
What action would you like to perform?
L
{ Apple Carrot Orange }What action would you like to perform?
I
Please enter a string to search:
Orange
The index of the last Orange is 2
What action would you like to perform?
S
Please enter a string to replace:
Orange
Please enter a string used to replace with:
Olive
What action would you like to perform?
L
{ Apple Carrot Olive }What action would you like to perform?
G
Please enter an index of a string to get:
1
The string at the index 1 is Carrot
What action would you like to perform?
E
The linked list is not empty
What action would you like to perform?
Q
BUILD SUCCESSFUL (total time: 1 minute 50 seconds)
