This lab exercise will have you finish implementing a partially implemented IntA

ID: 3884784 • Letter: T

Question

This lab exercise will have you finish implementing a partially implemented IntArrayBag class which

uses a dynamically sized array as its underlying data structure. You will also write a test case for the add

method and use invariants to test and nd bugs in the add and remove methods.

1 Implement the IntArrayBag Class

1). Implement the ensureCapacity method for the IntArrayBag class. A stub for this method exists at

the bottom of the provided file.

2). Within TestIntArrayBag.java , we have already provided a test case for the ensureCapacity method.

Ensure your implementation passes this test case.

2 Find the Error with JUnit

1). Within TestIntArrayBag.java , you need to add assertions to testAdd until you have a failed test

that uncovers the error in the method.

Note 1: Do NOT correct the bug in the IntArrayBag.java though you must be able to explain what

is wrong.

Note 2: JUnit Asserts

assertTrue( condition ) , when you expect the condition to return true

assertFalse( condition ) , when you expect the condition to return false

assertEquals( result , expression) , when you expect the expression to evalute to the result.

Since the integer array data is a private field, you cannot access them directly in the assertions.

We provide the countOccurrences(Integer) method in IntArrayBag . It returns the number of

occurrences of the argument, refer to testEnsureCapacity for how to use it in assertions.

3 Find the Error with Invariant

1). Within IntArrayBag.java , you need to add the 2nd invariant checker to wellFormed . This will also

help point out bugs in your program.

2. After writing the 2nd invariant, run assertions by right-click on the project, and click Run Configurations .

This will open the Run Dialog. Displayed in Figure 1 on the following page.

3. Click the Arguments tab, and in the VM Arguments box, enter

-ea

Similar to the Figure 2 on the following page.

4. Click Run

Note: Do not correct the bug in IntArrayBag.java though you must be able to explain what is

wrong.

IntArrayBag.java

import java.util.ArrayList;
import java.util.List;

public class IntArrayBag implements Cloneable {
private Integer[] data;
private int manyItems;

   public IntArrayBag() {
       final int INITIAL_CAPACITY = 10;
       manyItems = 0;
       data = new Integer[INITIAL_CAPACITY];
   }

   public IntArrayBag(int initialCapacity) {
       if (initialCapacity < 0) {
           throw new IllegalArgumentException("initialCapacity is negative: "
                   + initialCapacity);
       }
       manyItems = 0;
       data = new Integer[initialCapacity];
   }

   public void add(Integer element) {
       if (manyItems == data.length) {
           ensureCapacity(manyItems * 2 + 1);
       }
       data[manyItems] = manyItems + 1;
       manyItems++;
   }

   private boolean _report(String message) {
       System.out.println(message);
       return false;
   }

   private boolean wellFormed() {
       // Make assertions about the invariant, returning false
       // if the invariant false. Taken from pg 123 (3rd ed.)

       // #1. manyItems should never be greater than data.length
       if (manyItems > data.length)
           return _report("manyItems is greater than data.length");

       // #2. When the bag isn't empty, then items data[0] to data[manyItems-1]
       // should contain data (or not be null)
       // TODO Implement the 2nd Invariant

       // All invariant assertions passed so return true
       return true;
   }

public boolean remove(Integer target) {
assert wellFormed() : "Failed at the start of remove";

       int index = 0;
       while ((index < manyItems) && (target != data[index])) {
           index++;
       }

       if (index == manyItems) {
           return false;
       } else {
           data[index] = null;
           --manyItems;
           assert wellFormed() : "Failed at the end of remove";
           return true;
       }
   }

   public int size() {
       return manyItems;
   }

   public int getCapacity() {
       return data.length;
   }

   public int countOccurrences(int target) {
       int answer = 0;
       int index = 0;

       for (index = 0; index < manyItems; index++) {
           if (target == data[index]) {
               answer++;
           }
       }
       return answer;
   }

TestIntArrayBag.java

import java.util.ArrayList;
import java.util.List;

import junit.framework.TestCase;

public class TestIntArrayBag extends TestCase {

   @Override
   public void setUp() {
       try {
           assert 1/(5^5) == 42 : "OK";
           System.err.println("Assertions must be enabled to use this test suite.");
           System.err.println("In Eclipse: add -ea in the VM Arguments box under Run>Run Configurations>Arguments");
           assertFalse("Assertions must be -ea enabled in the Run Configuration>Arguments>VM Arguments",true);
       } catch (ArithmeticException ex) {
           return;
       }
   }
   /*
   * This has been provided for you to test your implementation of the
   * ensureCapacity.
   */
   public void testEnsureCapacity() {
       IntArrayBag bag = new IntArrayBag();
       bag.add(1);
       bag.add(2);
       bag.add(3);

       // checking below current capacity
       bag.ensureCapacity(3);
       assertFalse(bag.getCapacity() == 3);
       assertTrue(bag.size() == 3);
       assertEquals(1, bag.countOccurrences(1));
       assertEquals(1, bag.countOccurrences(2));
       assertEquals(1, bag.countOccurrences(3));
       assertEquals(0, bag.countOccurrences(4));

       // checking above current capacity
       bag.ensureCapacity(20);
       assertTrue(bag.getCapacity() == 20);
       assertTrue(bag.size() == 3);
       assertEquals(1, bag.countOccurrences(1));
       assertEquals(1, bag.countOccurrences(2));
       assertEquals(1, bag.countOccurrences(3));
       assertEquals(0, bag.countOccurrences(4));
   }

   public void testRemove() {
       IntArrayBag bag = new IntArrayBag();
       bag.add(1);
       bag.add(2);
       bag.add(3);
       assertEquals(3, bag.size());
       bag.remove(1);
       assertEquals(2, bag.size());
   }

   /*
   * TODO For the below test case, you are to insert asserts until you have it
   * fails and you are able to find the bug.
   *
   * Some possible asserts you can use are: assertTrue( condition )
   * assertFalse( condition ) assertEquals( expect, actual )
   *
   * You do not have direct access to the private array data in IntArrayBag.
   * We provide the countOccurrences(Integer) method to help you test if
   * the add(Integer) method correctly adds elements to data.
   *
   * There are examples of above methods in testEnsureCapacity
   */
   public void testAdd() {

   }
}

Explanation / Answer

import java.util.ArrayList;
import java.util.List;

public class IntArrayBag implements Cloneable {
private Integer[] data;
private int manyItems;

   public IntArrayBag() {
       final int INITIAL_CAPACITY = 10;
       manyItems = 0;
       data = new Integer[INITIAL_CAPACITY];
   }

   public void add(Integer element) {
       if (manyItems >= data.length) {
           ensureCapacity(manyItems * 2 + 1);
       }
       data[manyItems] =element;
       manyItems++;
   }

   public Object get(int index){
       if(index>=manyItems||index<0) throw new IndexOutOfBoundsException();
       return data[index];
   }
   private boolean _report(String message) {
       System.out.println(message);
       return false;
   }

   private boolean wellFormed() {
       // Make assertions about the invariant, returning false
       // if the invariant false. Taken from pg 123 (3rd ed.)

       // #1. manyItems should never be greater than data.length
       if (manyItems > data.length)
           return _report("manyItems is greater than data.length");

       // #2. When the bag isn't empty, then items data[0] to data[manyItems-1]
       // should contain data (or not be null)
       // TODO Implement the 2nd Invariant

       // All invariant assertions passed so return true
       return true;
   }

public boolean remove(Integer target) {
assert wellFormed() : "Failed at the start of remove";

       int index = 0;
       while ((index < manyItems) && (target != data[index])) {
           index++;
       }

   public int size() {
       return manyItems;
   }

   public int getCapacity() {
       return data.length;
   }

   public int countOccurrences(int target) {
       int answer = 0;
       int index = 0;

       for (index = 0; index < manyItems; index++) {
           if (target == data[index]) {
               answer++;
           }
       }
       return answer;
   }

   public void ensureCapacity(int minimumCapacity) {
       Integer[] biggerArray;
       if (data.length < minimumCapacity) {
           biggerArray = new Integer[minimumCapacity];
           System.arraycopy(data, 0, biggerArray, 0, manyItems);
           data = biggerArray;
       }

       // Do nothing if the current capacity is at least minimumCapacity
       // Otherwise make a bigger array of size minimumCapacity then copy elements over
    }

   public String toString(){

       if(size()==0) return "[]";

       StringBuilder sb=new StringBuilder("["+get(0));

       for(int i=1;i<size();i++)
       {
           sb.append(","+get(i));
       }
       sb.append("]");

   return sb.toString();
   }

}

// main class

public class MyArrayBagDemo {

   public static void main(String[] args) {

       IntArrayBag bag=new IntArrayBag();
       bag.add(2);
       bag.add(4);
       bag.add(6);
       System.out.println(bag.toString());
       System.out.println(bag.get(0));
       System.out.println(bag.size());
       bag.remove(6);

       System.out.println(bag.toString());
       bag.add(2);
       System.out.println(bag.size());
       bag.add(2);
       System.out.println(bag.countOccurrences(2));

   }

}

// test class
import java.util.ArrayList;
import java.util.List;
import junit.framework.TestCase;

public class TestIntArrayBag extends TestCase {

Navigate

This lab examines the various ways of working with arrays by uriting pseudocode.

This lab exercise will have you finish implementing a partially implemented IntA

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

This lab exercise will have you finish implementing a partially implemented IntA

Question

Explanation / Answer

Related Questions

Navigate