0

I have MaxHeap class which provides all usual properties that one heap will do (ExtractMax, Add, Build). Now I want to test it, but in order to test it I need to work with the structure I am using it internally (array) in order to verify that heap property is not violated.

Heap property is each node of the heap to be larger(in context of integers) than its children and this can be done easily with this function for example

/// <summary>
///  Determines if given array is max maxHeap.
/// </summary>
/// <typeparam name="T">Type of the elements contained in the maxHeap.</typeparam>
/// <param name="maxHeap"> The maxHeap.</param>
/// <param name="index"> Index from which to start.</param>
/// <returns>Whether the heap is max heap or not.</returns>
private static bool IsMaxHeap<T>(MaxHeap<T> maxHeap, int index = 0)
{
    // if it is a leaf it is max maxHeap.
    if (index >= (maxHeap.Count - 1)/2)
    {
        return true;
    }

    return Comparer<T>.Default.Compare(maxHeap[index], maxHeap[2 * index + 1]) > 0
           && Comparer<T>.Default.Compare(maxHeap[index], maxHeap[2 * index + 2]) > 0
           && IsMaxHeap(maxHeap, 2 * index + 1)
           && IsMaxHeap(maxHeap, 2 * index + 2);
}

But this requires your heap class to have public indexer. If I have access to the internal representation to the heap this function gets easier by passing array rather than MaxHeap or access it via the MaxHeap object directly, but I don't think this is how it should be done since internal representation of a structure should not be exposed.

What is the correct way of doing this without messing with the Heap class API?

  • Should I duplicate code and copy the MaxHeap class in my testing project with all needed information exposed?
  • Or perhaps add some protected indexer in MaxHeap class and test it with stub?(don't like this approach much since it leaves door to inherit my class and get access to that indexer which basically defeats the logic of not changing the API of the MaxHeap)
kuskmen
  • 3,648
  • 4
  • 27
  • 54
  • 1
    What can't you test with testing the API (the use case) ? You can check other MaxHeap implementation and look at the test they have ;). Ex: https://codereview.stackexchange.com/questions/162311/min-max-heap-implementation – rad Dec 15 '17 at 16:20
  • Wow, sorry, editing my answer. – kuskmen Dec 15 '17 at 16:20
  • @rad , tests in the reference doesn't cover the heap property. Only certain operations of heap if they are correct. – kuskmen Dec 15 '17 at 17:11
  • 1
    Possible duplicate of [How do I test a private function or a class that has private methods, fields or inner classes?](https://stackoverflow.com/questions/34571/how-do-i-test-a-private-function-or-a-class-that-has-private-methods-fields-or) – Raedwald Dec 15 '17 at 18:15
  • @Raedwald this is not about testing specific internal method, but how to use this internal data to verify functionality of the class. There is a difference. – kuskmen Dec 15 '17 at 18:16
  • The internal structure of an abstract data type is private data, so it is the same. You can use your knowledge of the actual internal structure to choose good test cases, which are likely to fail if the internal structure is manipulated incorrectly. – Raedwald Dec 15 '17 at 18:21

0 Answers0