tdd with non-trivial algorithms

In these days I'm coding some data structures in Java. Many of them (if not all) offer a very simple interface (add, contains, delete) but under the hood there are non-trivial algorithms.

How can I use the tdd technique in such a situation?

I think that the problem is that tdd (and in general unit testing) is about testing the interfaces and not the implementations. Am I right? How can I deal with this?

If you know any technique to handle this cases please let me 开发者_如何学编程know it.

Thank you for your help.

---

You're correct that TDD is about testing the interfaces, and not the implementation. That said, why do you care to test the actual implementation? The point is that if you sufficiently test the interface, the implementation does not matter.

When you find a bug in the implementation, that means that somewhere it violates the interface that you are exposing to the outside world. You need to track it down to where it violates the interface. That's where you write your test case.

---

If your implementation is complex, then it would be a good idea to break it down in smaller modules. These smaller modules would then have their own interface, which you would unit test. For instance, if you're solving Sudoku by doing a depth-first search, then it would pay to develop separately a depth-first search algorithm, and a Sudoku position enumeration algorithm. I blogged about this a while ago: http://matteo.vaccari.name/blog/archives/416

---

Testing the interface is greatly superior to testing the implementation. Later, when you refactor the implementation, your tests will still be valid.

If you feel that your methods are too complex to adequately unit test, perhaps that is an indication that you need to refactor your code and break it down into several smaller (potentially private) methods which can be tested seperately.

---

To test if a implementation contains some restrictions (i.e: number of comparations, performance, etc.) you can TDD those constraints by using tests.

I found this twitter conversation very insightful: http://twitoaster.com/kentbeck/brunopedroso-i-think-you-could-tdd-quicksort-youd-need-assertions-about-the-of-comparisons-ways-to-incrementally-improve-the-count/

It talks about this idea: TDDing a quick sort. We know that a quicksort is faster than a bubble sort. Both algorithms will give the same output (a sorted collection), but they have different constraints.

So you explicitly add the constraints of your algorithm in your tests (you obviously need to test if your algorithm is doing what you expect it to do).

I agree that in this example you're tdding something that you already know the answer. However, if you must find a complex algorithm, you're probably not going to TDD it all the way. But the tests and constraints tests will help you know if you found the answer or not.

---

I have found the example TDD/BDD in RSpec book very useful -http://www.pragprog.com/titles/achbd/the-rspec-book this could be some what rails oriented but in the book the author goes from defining the problem, to identifying the simple test cases to complex cases in an intuitive manner. The example in that book is about developing a game and its progress towards towards passing all the tests.

Also this could be useful for you because you are talking about interfaces and the BDD is about testing behavior of the application(in your case algorithm).