JAVA |-- lib |__ |-- checkstyle-6.5-all.jar |__ |-- hamcrest-core-1.3.jar |__ \\

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);

    }

}

}

(Do not modify the code above. this code is used for runing the Test in JUnit)

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 ….

}

* All of your file, class, and method names, if specified in this assignment, must have the exact names specified.

Explanation / Answer

public class ArrayDequeTest <E>{
   E[] l;
   int front, rear, max_size;
   public ArrayDequeTest(int n){
       l = new E[n];
       front = 0;
       rear = 0;
       max_size = n;
   }
   public ArrayDequeTest(){
       l = new E[10];
       front = 0;
       rear = 0;
       max_size = 10;
   }
   public boolean empty(){
       if (front == rear) return true;
       return false;
   }
   public int size(){
       return rear - front;
   }
   public void addFront(E e1){
       rear = rear + 1;
       int deque_size = size();
       if (deque_size + 1 == max_size) max_size = max_size*2;
       E[] temp = new E[max_size];
       for (int i = 0; i < deque_size; i++)
           temp[i] = l[i];
       l = temp;
       for (int i = deque_size; i >= front; i--){
           l[i+1] = l[i];
       }
       l[front] = e1;
       front = front % max_size;
   }
   public void addRear(E e1){
       int deque_size = size();
       if (deque_size + 1 == max_size){
           max_size = max_size*2;
           l[rear] = e1;
           rear = rear + 2;
       }
       else{
           l[rear] = e1;
           rear = rear+2;
       }
   }
   public E peekFront(){
       if (front == rear) {
           System.out.println("Deque is Empty");
           return null;
       }  
       return l[0];
   }
   public E peekRear(){
       if (front == rear) {
           System.out.println("Deque is Empty");
           return null;
       }  
       int index = (front + rear - 1);
       return l[index % max_size];
   }
   public E removeFront(){
       if (front == rear){
           System.out.println("Deque is empty");
           return null;
       }
       E[] temp = new E[max_size];
       for (int i = 1; i < deque_size; i++)
           temp[i-1] = l[i];
       l = temp;
       return l[front];
   }
   public E removeRear(){
       if (front == rear){
           System.out.println("Deque is empty");
           return null;
       }
       rear--;
       return A[rear];
   }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.