Disney Line Linked List

Introduction

In this assignment, you will add exceptions to a Linked-List class and then use a List to implement a program that simulates a lineup of people waiting to enter Disneyland. The focus of Part 1 is on throwing exceptions when methods are called incorrectly (or under incorrect circumstances). In Part 2, you will use the list (that you have updated so that it correctly works with exceptions) to model a lineup at Disneyland.

Although there is a tester provided for this assignment, it does not include a comprehensive set of sets for each method. You should add your own tests for any test cases not considered.

NOTE: The automated grading of your assignment will include some different and additional tests to those found in the A6Tester.java file. For all assignments, you are expected to write additional tests until you are convinced each method has full test coverage.

Objectives

Upon finishing this assignment, you should be able to:

  • Write methods that throw exceptions
  • Write code that handles exceptions (using try and catch)
  • Write code that uses an ADT to solve a problem

Instructions

Part 1:

  • Download all of the .java files found
  • Read through the tests provided in A6Tester.java.
  • Compile and run A6Tester.java. The first few tests should pass.
  • Eventually you will see some tests enclosed in try-catch blocks. In order for these tests to pass, you will need to throw exceptions in the corresponding methods. If you read through the List.java interface you will see the documentation has been updated so specify which methods throw exceptions.
  • In each of the methods that throw an exception, determine what input scenario triggers the exception, and then add the code to throw the exception under those circumstance(s).
  • Remember: After adding the exceptions in the correct places in LinkedList.java and saving it, compile and run A6Tester.java. All tests should pass. If any tests do not pass, it means you are either not detecting the correct circumstances that throw the exception, or you are not throwing the correct exception. Reminder: the List.java specifies which exception should be thrown in each method.

Part 2:

  • Read the documentation provided above each method in DisneylandList.java.
  • You will need to implement each method using only the fields provided for you in the DisneylandList class.
  • Compile and run A6Tester.java. Work through implementing each method one at a time. Debug the method until all of the tests pass for that method before proceeding to the next method.
  • Note: None of the methods in the DisneylandList class throw an exception. If they call a method that throws an exception, they will need to handle that exception (ie. the exception does not make it back so that it is instead caught in A6Tester).

Starter Code

List.java

public interface List< T > {

/*
* Purpose: add val to the front of the list
* Parameters: T val - the value to insert
* Returns: void - nothing
*/
void addFront (T val);

/*
* Purpose: add val to the back of the list
* Parameters: T val - the value to insert
* Returns: void - nothing
*/
void addBack (T val);

/*
* Purpose: remove and return the front element from the list
* Parameters: none
* Returns: T - the value of the element removed
* Throws: ListEmptyException - if there is nothing to remove
*/
T removeFront() throws ListEmptyException;

/*
* Purpose: remove and return the back element from the list
* Parameters: none
* Returns: T - the value of the element removed
* Throws: ListEmptyException - if there is nothing to remove
*/
T removeBack() throws ListEmptyException;

/*
* Purpose: get the number of elements in the list
* Parameters: none
* Returns: int - number of elements in list
*/
int size ();

/* Purpose: insert val into the specified position while
* maintaining the order of all other elements
* Parameters: int position - the 0-based position to insert
* T val - the value to insert
* Returns: void - nothing
* Throws: InvalidPositionException - if the given position
* is less than 0 or greater than the number of elements
*/
void insertAt (int position, T val) throws InvalidPositionException;

}

Node.java

public class Node< T >{

private T data;
protected Node< T > next;

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

/*
* Purpose: get the data value of this Node
* Parameters: nothing
* Returns: T - the data value
*/
public T getData() {
return data;
}

/*
* Purpose: get the next node
* Parameters: nothing
* Returns: Node< T > - the next node
*/
public Node< T > getNext() {
return next;
}

/*
* Purpose: update the next reference for this node
* Parameters: Node< T > next - the new next
* Returns: void - nothing
*/
public void setNext(Node< T > next) {
this.next = next;
}

}

A6Tester.java

public class A6Tester {
private static int testPassCount = 0;
private static int testCount = 0;

public static void main(String[] args) {
listTests();
disneyTests();

System.out.println("Passed " + testPassCount + " / " + testCount + " tests");
}

public static void listTests() {
System.out.println("nTesting linked list implementation");

LinkedList< Integer > list1 = new LinkedList< Integer >();
LinkedList< Integer > list2 = new LinkedList< Integer >();
LinkedList< Integer > list3 = new LinkedList< Integer >();
LinkedList< Integer > list4 = new LinkedList< Integer >();

String expected = "";
String result = "";

displayResults(list1.size()==0, "size of empty list");

list1.addFront(2);
list2.addFront(2);
displayResults(list1.size()==1, "size after inserting to front");

list3.addBack(3);
list4.addBack(3);
displayResults(list3.size()==1, "size after inserting to back");

list1.addFront(1);
result = list1.toString();
expected = "{1 2}";
displayResults(result.equals(expected), "elements in list correct");

list2.addBack(3);
result = list2.toString();
expected = "{2 3}";
displayResults(result.equals(expected), "elements in list correct");

list3.addFront(2);
result = list3.toString();
expected = "{2 3}";
displayResults(result.equals(expected), "elements in list correct");

list4.addBack(4);
result = list4.toString();
expected = "{3 4}";
displayResults(result.equals(expected), "elements in list correct");

try {
list1.insertAt(0, 8);
displayResults(list1.size()==3, "size after third insert");
result = list1.toString();
expected = "{8 1 2}";
displayResults(result.equals(expected), "contents after third insert");
} catch (InvalidPositionException e) {
System.out.println("exception thrown");
displayResults(false, "size after third insert");
displayResults(false, "contents after third insert");
}

try {
list2.insertAt(1, 8);
displayResults(list2.size()==3, "size after third insert");
result = list2.toString();
expected = "{2 8 3}";
displayResults(result.equals(expected), "contents after third insert");
} catch (InvalidPositionException e) {
System.out.println("exception thrown");
displayResults(false, "size after third insert");
displayResults(false, "contents after third insert");
}

try {
list3.insertAt(2, 8);
displayResults(list3.size()==3, "size after third insert");
result = list3.toString();
expected = "{2 3 8}";
displayResults(result.equals(expected), "contents after third insert");
} catch (InvalidPositionException e) {
System.out.println("exception thrown");
displayResults(false, "size after third insert");
displayResults(false, "contents after third insert");
}

try {
list4.insertAt(3, 8);
displayResults(false, "size after third insert");
displayResults(false, "contents after third insert");
} catch (InvalidPositionException e) {
System.out.println("exception thrown");
displayResults(list4.size()==2, "size after third insert");
result = list4.toString();
expected = "{3 4}";
displayResults(result.equals(expected), "contents after third insert");
}


Integer removed = null;

try {
removed = list1.removeFront();
removed = list1.removeFront();
removed = list1.removeFront();
displayResults(list1.size()==0, "size after removeFronts");
displayResults(removed.equals(2), "element returned after removeFronts");
} catch (ListEmptyException e) {
System.out.println("exception thrown");
displayResults(false, "size after removeFronts");
displayResults(false, "element returned after removeFronts");
}

try {
removed = list2.removeBack();
removed = list2.removeBack();
removed = list2.removeBack();
displayResults(list2.size()==0, "size after removeBacks");
displayResults(removed.equals(2), "element returned after removeBacks");
} catch (ListEmptyException e) {
System.out.println("exception thrown");
displayResults(false, "size after removeBacks");
displayResults(false, "element returned after removeBacks");
}

try {
removed = list3.removeBack();
removed = list3.removeFront();
removed = list3.removeBack();
displayResults(list3.size()==0, "size after removals");
displayResults(removed.equals(3), "element returned after removals");
} catch (ListEmptyException e) {
System.out.println("exception thrown");
displayResults(false, "size after removals");
displayResults(false, "element returned after removals");
}

try {
removed = list4.removeFront();
removed = list4.removeBack();
removed = list4.removeFront();
displayResults(false, "size after removals");
displayResults(false, "element returned after removals");
} catch (ListEmptyException e) {
System.out.println("exception thrown");
displayResults(list4.size()==0, "size after removals");
displayResults(removed.equals(4), "element returned after removals");
}

try {
list1.addBack(9);
displayResults(list1.size()==1, "size after insert at removeAll");
result = list1.toString();
expected = "{9}";
displayResults(expected.equals(result), "contents after insert at removeAll");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "size after insert at removeAll");
displayResults(false, "contents after insert at removeAll");
}

try {
list2.addBack(9);
displayResults(list2.size()==1, "size after insert at removeAll");
result = list2.toString();
expected = "{9}";
displayResults(expected.equals(result), "contents after insert at removeAll");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "size after insert at removeAll");
displayResults(false, "contents after insert at removeAll");
}

try {
list3.addFront(9);
displayResults(list3.size()==1, "size after insert at removeAll");
result = list3.toString();
expected = "{9}";
displayResults(expected.equals(result), "contents after insert at removeAll");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "size after insert at removeAll");
displayResults(false, "contents after insert at removeAll");
}

try {
list4.addFront(9);
displayResults(list4.size()==1, "size after insert at removeAll");
result = list4.toString();
expected = "{9}";
displayResults(expected.equals(result), "contents after insert at removeAll");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "size after insert at removeAll");
displayResults(false, "contents after insert at removeAll");
}

try {
list1.removeFront();
list1.removeFront();
displayResults(false, "correct exception thrown when removing from empty list");
} catch (ListEmptyException e) {
System.out.println("exception thrown");
displayResults(true, "correct exception thrown when removing from empty list");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "correct exception thrown when removing from empty list");
}

try {
list2.removeBack();
list2.removeBack();
displayResults(false, "correct exception thrown when removing from empty list");
} catch (ListEmptyException e) {
System.out.println("exception thrown");
displayResults(true, "correct exception thrown when removing from empty list");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "correct exception thrown when removing from empty list");
}

try {
list3.removeBack();
list3.removeFront();
displayResults(false, "correct exception thrown when removing from empty list");
} catch (ListEmptyException e) {
System.out.println("exception thrown");
displayResults(true, "correct exception thrown when removing from empty list");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "correct exception thrown when removing from empty list");
}

try {
list4.removeFront();
list4.removeBack();
displayResults(false, "correct exception thrown when removing from empty list");
} catch (ListEmptyException e) {
System.out.println("exception thrown");
displayResults(true, "correct exception thrown when removing from empty list");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "correct exception thrown when removing from empty list");
}

}

public static void disneyTests() {
System.out.println("nTesting Disney Lineup implementation");

Person p1 = new Person("Ali", 23);
Person p2 = new Person("Juan", 23);
Person p3 = new Person("Sam", 23);
Person p4 = new Person("Yiyi", 23);
Person p5 = new Person("Lee", 23);
Person p6 = new Person("Mika", 23);
Person p7 = new Person("Ola", 23);

DisneylandLine d = new DisneylandLine();
Person result = null;
Person expected = null;
boolean inserted = false;
int numRemoved = 0;

displayResults(d.peopleInLine()==0, "people in empty line");

try {
result = d.handleOne();
displayResults(result == null, "handled person in empty line");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled person in empty line");
}

d.enterLine(p1);
displayResults(d.peopleInLine()==1, "people in line 1");
d.enterLine(p2);
d.enterLine(p3);
d.enterLine(p4);
displayResults(d.peopleInLine()==4, "people in line 2");


try {
result = d.handleOne();
expected = p1;
if (result == null) {
displayResults(false, "handled first person in line 1");
} else {
displayResults(result.equals(expected), "handled first person in line 1");
}
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled first person in line 1");
}

displayResults(d.peopleInLine()==3, "people in line 3");
d.enterLine(p5);
d.enterLine(p6);
displayResults(d.peopleInLine()==5, "people in line 4");

try {
inserted = d.premiumEntry(p7, 2);
displayResults(inserted==true, "inserted into specific pos");
} catch (Exception e) {
displayResults(false, "inserted into specific pos");
}

try {
result = d.handleOne();
expected = p2;
if (result == null) {
displayResults(false, "handled first person in line 2");
} else {
displayResults(result.equals(expected), "handled first person in line 2");
}
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled first person in line 2");
}

try {
result = d.handleOne();
expected = p3;
if (result == null) {
displayResults(false, "handled first person in line 3");
} else {
displayResults(result.equals(expected), "handled first person in line 3");
}
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled first person in line 3");
}

try {
result = d.handleOne();
expected = p7;
if (result == null) {
displayResults(false, "handled first person in line 4");
} else {
displayResults(result.equals(expected), "handled first person in line 4");
}
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled first person in line 4");
}

displayResults(d.peopleInLine()==3, "people in line 4");
d.enterLine(p7);
d.enterLine(p1);
d.enterLine(p2);
d.enterLine(p3);
displayResults(d.peopleInLine()==7, "people in line 5");

try {
numRemoved = d.handleMultiple(5);
displayResults(numRemoved==5, "group of 5 enter disneyland");
} catch (Exception e) {
displayResults(false, "group of 5 enter disneyland");
}
displayResults(d.peopleInLine()==2, "people in line 6");

try {
numRemoved = d.handleMultiple(5); // buy 5 tickets, but only 2 in line
displayResults(numRemoved==2, "group of 2 enter disneyland");
} catch (Exception e) {
displayResults(false, "group of 2 enter disneyland");
}
displayResults(d.peopleInLine()==0, "people in line 7");

try {
numRemoved = d.handleMultiple(5); // buy 5 tickets, but no one in line
displayResults(numRemoved==0, "group of 0 enter disneyland");
} catch (Exception e) {
displayResults(false, "group of 0 enter disneyland");
}
displayResults(d.peopleInLine()==0, "people in line 8");

d.enterLine(p1);
displayResults(d.peopleInLine()==1, "people in line 9");

try {
inserted = d.premiumEntry(p2, 0);
displayResults(inserted==true, "inserted into specific pos");
} catch (Exception e) {
displayResults(false, "inserted into specific pos");
}
displayResults(d.peopleInLine()==2, "people in line 10");

try {
inserted = d.premiumEntry(p3, 2);
displayResults(inserted==true, "inserted into specific pos");
} catch (Exception e) {
displayResults(false, "inserted into specific pos");
}
displayResults(d.peopleInLine()==3, "people in line 11");

try {
inserted = d.premiumEntry(p4, -2);
displayResults(inserted==false, "inserted into specific pos");
} catch (Exception e) {
displayResults(false, "inserted into specific pos");
}
displayResults(d.peopleInLine()==3, "people in line 12");

try {
inserted = d.premiumEntry(p5, 4);
displayResults(inserted==false, "inserted into specific pos");
} catch (Exception e) {
displayResults(false, "inserted into specific pos");
}
displayResults(d.peopleInLine()==3, "people in line 13");

try {
result = d.handleOne();
expected = p2;
if (result == null) {
displayResults(false, "handled first person in line 5");
} else {
displayResults(result.equals(expected), "handled first person in line 5");
}
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled first person in line 5");
}

try {
result = d.handleOne();
expected = p1;
if (result == null) {
displayResults(false, "handled first person in line 6");
} else {
displayResults(result.equals(expected), "handled first person in line 6");
}
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled first person in line 6");
}

try {
result = d.handleOne();
expected = p3;
if (result == null) {
displayResults(false, "handled first person in line 7");
} else {
displayResults(result.equals(expected), "handled first person in line 7");
}
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled first person in line 7");
}

try {
result = d.handleOne();
displayResults(result == null, "handled first person in line 8");
} catch (Exception e) {
System.out.println("exception thrown");
displayResults(false, "handled first person in line 8");
}

}


public static void displayResults (boolean passed, String testName) {
testCount++;
if (passed) {
System.out.println ("Passed test: " + testCount);
testPassCount++;
} else {
System.out.println ("Failed test: " + testName + " at line "
+ Thread.currentThread().getStackTrace()[2].getLineNumber());
}
}
}

DisneyLandLine.java

/*
* DisneylandLine
*
* A class to simulate a lineup of people waiting to enter
* Disneyland. Some people come alone and go to the back of
* the line, others bribe their way to a certain position.
* Sometimes someone buys a bunch of tickets at once so
* multiple people can be removed from the line and enter
* Disneyland at the same time.
*/
public class DisneylandLine {
List< Person > list;
//Do not add any other fields

public DisneylandLine() {
//Do not change the constructor in any way
list = new LinkedList< Person >();
}

/*
* Purpose: add a person to line to enter Disneyland
* Parameter: Person p - the person to add
* Returns void - nothing
*/
public void enterLine(Person p) {
// TODO: implement this
}

/*
* Purpose: handle the first person in line
(allow them to purchase their ticket
and enter into Disneyland)
* Parameter: none
* Returns: Person - the person who gets their ticket
* and is no longer waiting in line
* or null if no one can be removed
* from the line
*/
public Person handleOne() {
// TODO: implement this
return null; // so it compiles
}

/*
* Purpose: handle a whole group of people waiting in line
* (allow a group to buy a number of tickets
* and all enter Disneyland)
* Parameters: int num - the number of people
* Returns int - the number of people who were successfully
* able to be removed from the line
*/
public int handleMultiple(int num) {
// TODO: implement this
return -1; // so it compiles
}

/*
* Purpose: accept a bribe to put someone into a specific
* position in the line to get into Disneyland
* Parameters: Person p - the person entering the line
* int pos - the position they are trying to get to
* Returns boolean - true if person added to line, false otherwise
*/
public boolean premiumEntry(Person p, int pos) {
// TODO: implement this
return false; // so it compiles
}

/*
* Purpose: gets the number of people in line
* Parameters: none
* Returns: int - number of people in line
*/
public int peopleInLine() {
// TODO: implement this
return -1; // so it compiles
}
}

LinkedList.java

class ListEmptyException extends Exception {}
class InvalidPositionException extends Exception {}

public class LinkedList< T > implements List< T > {
private int numElements;
private Node< T > head;
private Node< T > tail;

public LinkedList() {
head = null;
tail = null;
numElements = 0;
}

public void addFront (T val) {
Node< T > n = new Node< T >(val);
if (head != null) {
n.next = head;
} else {
tail = n;
}
head = n;
numElements++;
}

public void addBack (T val) {
Node< T > n = new Node< T >(val);
if (head == null) {
head = n;
} else {
tail.next = n;
}
tail = n;
numElements++;
}

public int size (){
return numElements;
}

public void insertAt(int position, T val) throws InvalidPositionException {
if (position == 0) {
addFront(val);
} else if (position == numElements) {
addBack(val);
} else {
Node< T > cur = head;
for (int i = 0; i < position-1; i++) {
cur = cur.next;
}
// Now cur is pointing the node in the position
// one before the place we want to insert.
Node< T > n = new Node< T >(val);
n.next = cur.next;
cur.next = n;
numElements++;
}
}

public T removeFront() throws ListEmptyException {
if (head == null) {
return null;
}
T toReturn = head.getData();
if (head.next == null) {
tail = null;
}
head = head.next;
numElements--;
return toReturn;
}

public T removeBack() throws ListEmptyException {
if (head == null) {
return null;
}
T toReturn = tail.getData();
if (head.next == null) {
head = null;
tail = null;
} else {
Node< T > cur = head;
while (cur.next != tail) {
cur = cur.next;
}
cur.next = null;
tail = cur;
}
numElements--;
return toReturn;
}

/* Parameters: nothing
* Purpose: create a string representation of list
* Returns: (String) the string representation
*/
public String toString() {
if (head == null) {
return "{}";
}
String s = "{"+head.getData().toString();
Node< T > cur = head.next;
while (cur != null) {
s += " " + cur.getData().toString();
cur = cur.next;
}
s += "}";
return s;
}

}

Person.java

public class Person {
String name;
int age;

public Person(String name, int age) {
this.name = name;
this.age = age;
}

public String toString() {
return name;
}
}
Academic Honesty!
It is not our intention to break the school's academic policy. Posted solutions are meant to be used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly complete the form. Please provide a valid email address and we will get back to you within 24 hours. Payment is through PayPal, Buy me a Coffee or Cryptocurrency. We are a nonprofit organization however we need funds to keep this organization operating and to be able to complete our research and development projects.