JAVA |-- lib |__ |-- checkstyle-6.5-all.jar |__ |-- hamcrest-core-1.3.jar |__ \\
ID: 666523 • Letter: J
Question
JAVA
|-- lib
|__ |-- checkstyle-6.5-all.jar
|__ |-- hamcrest-core-1.3.jar
|__ -- junit-4.12.jar
|-- Makefile
|-- src
|__ -- ArrayDeque.java
-- tests
|-- ArrayDequeTest.java
-- MyTestRunner.java
import org.junit.runner.JUnitCore;
import org.junit.runner.Result;
import org.junit.runner.notification.Failure;
public class MyTestRunner {
/** Runs all my unit tests.
* @param args command line arguments, this is ignored.
*/
public static void main(String[] args) {
boolean failed = false;
Result result = JUnitCore.runClasses(ArrayDequeTest.class);
for (Failure failure : result.getFailures()) {
System.out.println(failure.toString());
failed = true;
}
if (failed) {
System.exit(1);
}
}
}
We started to implement a deque using a doubly-linked list. In this assignment you will implement an array-based deque.
Your deque must be generic and be able to store any reference type. So as not to waste space in the underlying array, you are to use the array underlying your deque as a circular buffer. Your array-based deque should not throw an exception when an item is added and the underlying array is full. Instead you should resize the underlying array by:
1. Creating a new array double the size of the current array; and
2. Copy the contents of your current array across to the new array.
Since we are using the array as a circular buffer, you must be careful with how you copy the elements over to this new array. The initial capacity of the underlying array should be set at 10.
You are to follow test driven development, you should write your tests in tests/ArrayDequeTest.java (using JUnit4 idiomatically to test cases), to develop the following methods in src/ArrayDeque.java: public class ArrayDeque {}
•public boolean empty() // Returns whether the deque is empty.
•public int size() // Returns the number of elements currently in the deque.
•public void addFront(E e1) // Add el to the front of the deque.
•public void addRear(E e1) // Add el to the rear of the deque.
•public E peekFront() // Return the element at the front of the deque, but does not remove this element from the deque.
•public E peekRear() // Return the element at the rear of the deque, but does not remove thiselement from the deque.
•public E removeFront() // Return and remove the element at the front of the deque.
•public E removeRear() // Return and remove the element at the rear of the deque.
Your methods peekFront(), peekRear(), removeFront(), and removeRear()should throw a NoSucElementException, when they are called on an empty deque. You should write test cases which is used JUnit4 idiomatically to see whether the exception is correctly thrown in these cases.
/** tests/ArrayDequeTest.java (using JUnit4 idiomatically to test cases).*/
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import org.junit.Test;
public class ArrayDequeTest {
Your code here …..
}
/** src/ArrayDeque.java:*/
public class ArrayDeque {
Your code here ….
}
Explanation / Answer
working java code
public class CircularExtendedArrayDeque
{
public static final int INIT_CAPACITY = 4; // initial array capacity
protected int capacity; // current capacity of the array
protected int front; // index of the front element
protected int rear; // index of the rear element
protected int[] A; // array deque
public CircularExtendedArrayDeque( ) // constructor method
{
A = new int[ INIT_CAPACITY ];
capacity = INIT_CAPACITY;
front = rear = 0;
}
/**
* Print the content of the deque
*
*/
public void printDeque( )
{
for ( int i = front; i != rear; i = (i+1) % capacity )
System.out.print( A[i] + " " );
System.out.println();
}
/**
* Print the content of the whole array
*
*/
public void printArray( )
{
for ( int i = 0; i < capacity; i++ )
System.out.print( A[i] + " " );
System.out.println();
}
// ***************************************
// DO NOT MODIFY THE CODE ABOVE THIS LINE.
// ADD YOUR CODE BELOW THIS LINE.
//
// ***************************************
/**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size()
{
// COMPLETE THIS METHOD
return (capacity - front + rear) % capacity;
}
/**
* Returns true if this collection is empty.
* @return true if this collection is empty.
*/
public boolean isEmpty()
{
// COMPLETE THIS METHOD
return front == rear;
}
/**
* Returns the first element of the deque
*
*/
public int getFirst() throws EmptyDequeException
{
// COMPLETE THIS METHOD
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
return A[front % capacity];
}
/**
* Returns the last element of the deque
*
*/
public int getLast() throws EmptyDequeException
{
// COMPLETE THIS METHOD
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
return A[(front + rear - 1) % capacity];
}
/**
* Inserts e at the beginning (as the first element) of the deque
*
*/
public void insertFirst( int e )
{
// COMPLETE THIS METHOD
rear++;
if(size() == capacity - 1){
capacity *= 2;
}
int[] B = new int[capacity];
for(int i = 0; i < size(); i++){
B[i] = A[i];
}
A = B;
for(int i = size(); i >= front; i--){
A[i+1] = A[i];
}
A[front] = e;
front = front % capacity;
System.out.println("Front: " + front + " & Rear:" + rear);
}
/**
* Inserts e at the end (as the last element) of the deque
*
*/
public void insertLast( int e )
{
// COMPLETE THIS METHOD
if(size() == capacity - 1){
capacity *= 2;
int[] B = new int[capacity];
for ( int i = front; i != rear; i = (i+1) % capacity )
B[i] = A[i];
/*
for(int i = 0; i < size(); i++){
B[i] = A[i];
}
*/
A = B;
A[rear++] = e;
}
else{
//System.out.println("Array Size = " + A.length);
A[rear++] = e;
}
System.out.println("Front: " + front + " & Rear:" + rear);
System.out.println("msg...size=" + size());
}
/**
* Removes and returns the first element of the deque
*
*/
public int removeFirst( ) throws EmptyDequeException
{
// COMPLETE THIS METHOD
int result = A[front];
A[front] = 0;
front = (front+1)%capacity;
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
else if(capacity >= 4){
if(size() < capacity/2){
//System.out.println("msg...size = " + size());
capacity /= 2;
int[] B = new int[capacity];
int counter=0;
for(int i = front; i < front+size(); i++){
B[counter] = A[i%(capacity*2)];
counter++;
}
A = B;
front = 0;
rear = size()-1;
}
}
return result;
}
/**
* Removes and returns the last element of the deque
*
*/
public void insertLast(int e) {
if(size() == capacity - 1) {
capacity= capacity*2;
}
int[] B = new int[capacity];
for(int i = 0; i < size(); i++) {
B[i] = A[i];
}
A = B;
A[rear] = e;
rear = (rear + 1) % capacity;
}
public static void main(String[] args) {
CircularExtendedArrayDeque q = new CircularExtendedArrayDeque();
q.insertFirst(112);
q.insertFirst(105);
q.printDeque();
System.out.println("last element is = " + q.getLast());
System.out.println("first element is = " + q.getFirst());
q.insertLast(5501);
q.printDeque();
q.insertLast(778);
q.insertLast(37);
q.printDeque();
System.out.println("first element is = " + q.getFirst());
System.out.println("last element is = " + q.getLast());
System.out.println("remove last = " + q.removeLast());
q.printDeque();
System.out.println("remove last = " + q.removeLast());
System.out.println("remove first = " + q.removeFirst());
q.printDeque();
System.out.println("remove first = " + q.removeFirst());
System.out.println("remove first = " + q.removeFirst());
// q is now empty.
int i, k;
for( i = 1; i <= 60; i ++ )
q.insertLast(i*i);
q.printDeque(); // 60 elements in q
for( i = 1; i <= 58; i++ )
k = q.removeFirst();
q.printDeque(); // two elements are left
}
} // end class
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.