How does one even approach testing an abstract data type?I mean, besides the normal (supposed) way of doing unit tests, where you mock the collaborators, feed them in the class to test, together with sample data, and call the public methods, verifying that the output is the expected one, how do you ensure that the internals are what you want?Let's take an example : let's say I want to implement my own PriorityQueue, but I want to use a Heap as internal representation and even further, an array for the Heap part. The normal way to test would be to check the public methods in different scenarios, the methods being : push, pop, peek.This does not give any guarantees on the performance of the algorithm used internally. I could and should bother make some scenarios to check the performance, but these are useful after I have implemented my thing and they are mostly for collecting metrics.So, how do I test the internal parts? Or better said, how do I ensure that the internal representation uses the algorithm I want.I know that I will have several levels on internals if I go with the heap implementation (these are everywhere on the Internet for implementations of PriorityQueues) :1. calculating the left-child, right-child, parent for a node ; I could extract these in a separate class and test that. Or I could just make them protected and test them in the PriorityQueue class, but this break encapsulation because the tests look into the state of the class to test2. shiftUp and shiftDown ; same issues as for the one in point 1., except now I can make them receive the object that represents the internal state, or use the private field direct, in case of an Object-oriented language. So, protected or in another entity?3. the internal representation is a array, so I could have a toArray() method that is public and test that. Testing the output of this can even save me from testing the previous two points, but again, the internal state is exposed to the outside world. Do I really want to do that?The questions here are :do you separate the code into more pieces? when do you stop with the granularity?how much do I sacrifice from KISS in order to have some unit tests? I want the things simple and could have most of the things in the same class and even methods to use the internal fields directly (in case of OO)are there other suggestions, other ways to ensure both the functionality of the data structure and the algorithm used ?
How to test abstract data types that I implement myself?
algorithms;unit testing;data types