CSE 274 Spring 2017

PROJECT #5: 60 points Due Saturday, March 25, by 11:59 p.m.

Outcomes:

Implement the Deque ADT using a circular doubly linked chain

Create a JUnit test that tests a class

Naming requirements (not following any of these results in a score of 0):

The Eclipse project name must be Project5.

You will have exactly four source code files to submit:

DequeInterface.java (an interface you are provided)

EmptyQueueException.java (a class you are provided)

CircularChainDeque.java (your implementation of DequeInterface)

DequeTest.java (a JUnit test for your deque implementation)

Use the default package (this means there should be no package statements in any of your files).

Preliminaries:

Read the following sections in chapters 10 and 11:

"The ADT Deque" section 10.14, which of a double-ended queue.

"Circular Linked Implementations of a Queue" section 11.17, focusing on the circular linked chain to understand how a circular chain works (focus on the version where the last node references the first node...not the two-part circular-linked chain).

"A Doubly-Linked Implementation of a Deque" sections 11.27 through 11.33, which focuses on modifying the Node class so that it has references to the next and the previous nodes.

The note after section 11.33 describing the basics of a circular doubly linked chain.

Assignment:

Project 11.9 from textbook:

Use a circular doubly linked chain to implement the ADT deque. Your implementation should have:

Only one instance variable: A reference to the first node in the chain.

A private inner class Node with links to the next and previous nodes. It is up to you whether you want to include getters and setters.

Implement JUnit tests to thoroughly test your methods. Include a comment at the beginning of each JUnit test to briefly describe what is being tested (such as "// Removing last item from the front of the deque"). Be sure to include special cases such as:

adding to the front and back when the deque is empty

removing the last node from the front and back

proper exceptions being thrown when removing from or peeking at an empty queue (see sample below for an example of test that will be green if an exception is thrown)

At the top of the comments of your Deque implementation, identify the aspects of your class that work and do not work. It is not enough to say "everything works". Indicate specifically what you have tested (such as "adding to the front and back an empty deque works").

Here is an example of a JUnit test that verifies that the correct exception is being thrown. Ordinarily, an exception would indicate that a test fails, but the test below says that we expect an EmptyQueueException. So, if the exception is thrown by the code, then the JUnit test will pass:

@Test (expected = EmptyQueueException.class)

public void testEmptyQueueException() {

QueueInterface queue = new ArrayQueue<>();

queue.dequeue();

}

Scoring:

Outcome	Max score
CircularChainDeque implemented correctly	40
JUnit tests thoroughly test all aspects of your deque	15
Comments in CircularChainDeque indicate what does and does not work	5
Code formatted according to generally accepted standards. Note that Javadoc comments are not required because you are implementing an already documented interface.	0 (deductions only)
Code follows good programming guidelines (avoid excessively long methods, use helper methods, name variables appropriately, and so on)	0 (deductions only)

CSE 274 Spring 2017

PROJECT #5: 60 points Due Saturday, March 25, by 11:59 p.m.

Outcomes:

Implement the Deque ADT using a circular doubly linked chain

Create a JUnit test that tests a class

Naming requirements (not following any of these results in a score of 0):

The Eclipse project name must be Project5.

You will have exactly four source code files to submit:

DequeInterface.java (an interface you are provided)

EmptyQueueException.java (a class you are provided)

CircularChainDeque.java (your implementation of DequeInterface)

DequeTest.java (a JUnit test for your deque implementation)

Use the default package (this means there should be no package statements in any of your files).

Preliminaries:

Read the following sections in chapters 10 and 11:

"The ADT Deque" section 10.14, which of a double-ended queue.

"Circular Linked Implementations of a Queue" section 11.17, focusing on the circular linked chain to understand how a circular chain works (focus on the version where the last node references the first node...not the two-part circular-linked chain).

"A Doubly-Linked Implementation of a Deque" sections 11.27 through 11.33, which focuses on modifying the Node class so that it has references to the next and the previous nodes.

The note after section 11.33 describing the basics of a circular doubly linked chain.

Assignment:

Project 11.9 from textbook:

Use a circular doubly linked chain to implement the ADT deque. Your implementation should have:

Only one instance variable: A reference to the first node in the chain.

A private inner class Node with links to the next and previous nodes. It is up to you whether you want to include getters and setters.

Implement JUnit tests to thoroughly test your methods. Include a comment at the beginning of each JUnit test to briefly describe what is being tested (such as "// Removing last item from the front of the deque"). Be sure to include special cases such as:

adding to the front and back when the deque is empty

removing the last node from the front and back

proper exceptions being thrown when removing from or peeking at an empty queue (see sample below for an example of test that will be green if an exception is thrown)

At the top of the comments of your Deque implementation, identify the aspects of your class that work and do not work. It is not enough to say "everything works". Indicate specifically what you have tested (such as "adding to the front and back an empty deque works").

Here is an example of a JUnit test that verifies that the correct exception is being thrown. Ordinarily, an exception would indicate that a test fails, but the test below says that we expect an EmptyQueueException. So, if the exception is thrown by the code, then the JUnit test will pass:

@Test (expected = EmptyQueueException.class)

public void testEmptyQueueException() {

QueueInterface queue = new ArrayQueue<>();

queue.dequeue();

}

Scoring:

Outcome	Max score
CircularChainDeque implemented correctly	40
JUnit tests thoroughly test all aspects of your deque	15
Comments in CircularChainDeque indicate what does and does not work	5
Code formatted according to generally accepted standards. Note that Javadoc comments are not required because you are implementing an already documented interface.	0 (deductions only)
Code follows good programming guidelines (avoid excessively long methods, use helper methods, name variables appropriately, and so on)	0 (deductions only)

these are 2 given .java file

/** A class of runtime exceptions thrown by methods to indicate that a queue is empty. @author Frank M. Carrano @author Timothy M. Henry */ public class EmptyQueueException extends RuntimeException { public EmptyQueueException() { this(null); } // end default constructor public EmptyQueueException(String message) { super(message); } // end constructor } // end EmptyQueueException

/** An interface for the ADT deque. @author Frank M. Carrano @author Timothy M. Henry @version 4.0 */ public interface DequeInterface { /** Adds a new entry to the front/back of this dequeue. @param newEntry An object to be added. */ public void addToFront(T newEntry); public void addToBack(T newEntry); /** Removes and returns the front/back entry of this dequeue. @return The object at the front/back of the dequeue. @throws EmptyQueueException if the dequeue is empty before the operation. */ public T removeFront(); public T removeBack(); /** Retrieves the front/back entry of this dequeue. @return The object at the front/back of the dequeue. @throws EmptyQueueException if the dequeue is empty before the operation. */ public T getFront(); public T getBack(); /* Detects whether this dequeue is empty. @return True if the queue is empty, or false otherwise. */ public boolean isEmpty(); /* Removes all entries from this dequeue. */ public void clear(); } // end DequeInterface