In this part, we will build a test suite, trying to obtain “good coverage” that helps us find where the bug/s is/are.

chemistry-23400_640   Experiment:

  1. In Eclipse, create a new Java Project
  2. Copy (from here) Solution.java
  3. Create a new JUnit Test Case
  4. Create a new test:
     @Test
    public void testEmpty() {
     Solution.MaxHeap mh = new Solution.MaxHeap(5);
     assertNotNull(mh);
     assertEquals(0, mh.size());
    }
    
  5. Run the test (and check that it succeeds!)
  6. Run the test using EclEmma (notice that it only covers around 6% of the code – the heap constructor and size methods)
  7. We now add a new test in which we insert one element:
     @Test
    public void testInsert1() {
      Solution.MaxHeap mh = new Solution.MaxHeap(5);
      mh.insert(5);
      assertNotNull(mh);
      assertEquals(1, mh.size());
      assertEquals(5, mh.top());
    }
  8. The test succeeds, and the coverage percentage is now around 15%
  9. We now add a test to remove one element (calling pop)
     @Test
    public void testPop1() {
      Solution.MaxHeap mh = new Solution.MaxHeap(5);
      mh.insert(5);
      int result = mh.pop();
      assertEquals(5, result);
      assertEquals(0, mh.size());
    }
  10. The test fails! The current implementation of pop() is not updating the length when there is only one element in the heap:
     public int pop() {
      int result = elems[1];
      if (length > 1) {
        elems[1] = elems[length];
        length--;
        sink(1);
      }
      return result;
    } 
  11. Fix the implementation (where should length-- be?)
  12. After fixing this bug, the implementation is still not producing the correct output, and the coverage percentage is around 20%. Thus we continue adding some more test cases.
  13. We notice that we can easily build a test that pops an element from a heap with more than one element to have more coverage of that method: Screen Shot 2017-04-16 at 11.53.21 AM
  14. Add the following test:
     @Test
    public void testPop2() {
      Solution.MaxHeap mh = new Solution.MaxHeap(5);
      mh.insert(5);
      mh.insert(10);
      int result = mh.pop();
      assertEquals(10, result);
      assertEquals(1, mh.size());
    } 
  15. The test passes and we obtain around 40% coverage of Solution.java
  16. We notice that we have not tested sink() at all, that is the pop invocations were trivial. We build a more interesting case, and start removing the elements one by one: Screen Shot 2017-04-16 at 12.02.47 PM
     @Test
    public void testPopWithSink2Levels() {
      Solution.MaxHeap mh = new Solution.MaxHeap(20);
      mh.insert(11);
      mh.insert(10);
      mh.insert(9);
      mh.insert(8);
      mh.insert(7);
      mh.insert(6);
      mh.insert(5);
      int result = mh.pop();
      assertEquals(11, result);
      assertEquals(6, mh.size());
      result = mh.pop();
      assertEquals(10, result);
      assertEquals(5, mh.size());
      result = mh.pop();
      assertEquals(9, result);
      assertEquals(4, mh.size());
      result = mh.pop();
      assertEquals(8, result);
      assertEquals(3, mh.size());
      result = mh.pop();
      assertEquals(7, result);
      assertEquals(2, mh.size());
      result = mh.pop();
      assertEquals(6, result);
      assertEquals(1, mh.size());
      result = mh.pop();
      assertEquals(5, result);
      assertEquals(0, mh.size());
    }
  17. The test passes, and we notice that one of the branches within the sink() method was never executed (when !priority(moveToIndex,i)): Screen Shot 2017-04-16 at 12.06.31 PM
  18. To cause sink() to stop in the middle we have to build a different heap:Screen Shot 2017-04-16 at 12.19.00 PM output_5tBc4B
      @Test
    public void testPopWithSinkOnlyPart() {
      Solution.MaxHeap mh = new Solution.MaxHeap(20);
      mh.insert(11);
      mh.insert(8);
      mh.insert(10);
      mh.insert(6);
      mh.insert(5);
      mh.insert(7);
      mh.insert(9);
      int result = mh.pop();
      assertEquals(11, result);
      assertEquals(6, mh.size());
      result = mh.pop();
      assertEquals(10, result);
      assertEquals(5, mh.size());
      result = mh.pop();
      assertEquals(9, result);
      assertEquals(4, mh.size());
      result = mh.pop();
      assertEquals(8, result);
      assertEquals(3, mh.size());
      result = mh.pop();
      assertEquals(7, result);
      assertEquals(2, mh.size());
      result = mh.pop();
      assertEquals(6, result);
      assertEquals(1, mh.size());
      result = mh.pop();
      assertEquals(5, result);
      assertEquals(0, mh.size());
    } 
  19. This test fails. Debugging, we find that when the heap is [9,8,7,6,5], or given as a tree: Screen Shot 2017-04-16 at 12.39.34 PMThen, removing the 9 leaves a tree not representing a heap: Screen Shot 2017-04-16 at 12.41.03 PMThat is, the last comparison is missing!
  20. Correct the implementation of sink() from:
     private void sink(int i) {
      while (2*i < length) {
        int moveToIndex = 2*i;
        if (2*i+1 < length && priority(2*i+1, 2*i)) {
          moveToIndex = 2*i+1;
        }
        if (priority(moveToIndex, i)) {
          int tmp = elems[i];
          elems[i] = elems[moveToIndex];
          elems[moveToIndex] = tmp;
          i = moveToIndex;
        } else {
          break;
        }
      }
    } 

    to:

     private void sink(int i) {
      while (2*i <= length) {
        int moveToIndex = 2*i;
        if (2*i+1 <= length && priority(2*i+1, 2*i)) {
          moveToIndex = 2*i+1;
        }
        if (priority(moveToIndex, i)) {
          int tmp = elems[i];
          elems[i] = elems[moveToIndex];
          elems[moveToIndex] = tmp;
          i = moveToIndex;
        } else {
          break;
        }
      }
    } 

    Lines 2 and 4 should check with <= length instead of < length.

  21. Run the program with the previously problematic input, and now it works correctly!

We now have an initial set of tests and the program succeeding. We used code coverage to notice parts of the program not being covered by any tests.

student-41444_640.png What other things can I do with this example?

  • When having a bug in a complex program, try adding tests. Combine it with code coverage to notice which methods or conditions have not yet been covered!
Advertisements