Several years have passed since my first attempt at implementing SkipList via TDD. I continue to do test-first development — for example, most of the Practical XML library was written in this manner. However, while I use tests to validate my design, and put me in the shoes of a person using the library, they don't drive that design.
For the SkipList, I tried very hard to take that next step, and let the tests show me where to go. I'm not sure that I was successful, and in some cases I didn't like the results. I won't blame you for skipping this post: it has a close resemblance to a fishing show (“yes, Billy-Bob, he's definitely got something on the hook, so lets watch him reel it in”). Not for everyone, but it does lay the groundwork for my next post.
In returning to the SkipList, I recognized that I would need a way to test the implementation separate from the public API. Java gave me a solution to the packaging issue: rather than using multiple top-level classes, or interface and implementation, I would use nested static classes. Everything lives in one source file. The choice of nested classes, rather than inner, was intentional: if TDD was going to drive me to independent collaborators, I wanted them to be truly independent.
The first question was where to draw the line between interface and implementation? I took what appeared to be the simplest: create a SkipListElement that knew only how to talk to its neighbors. The SkipList itself would know about the first element. Conceptually, this is how any linked list can be implemented, and it's very easy to test. In practice, of course, implementing a normal linked list with self-aware elements is a good way to blow up your stack from the recursive search operation (unless your language optimizes tail recursion). For SkipList, with its log2 access paths, it seemed like a workable idea.
As it turned out, while the tests remained simple, the implementation quickly became very complex. The find() method was particularly so: it had to work its way up through the tiers of links and then back down. After a lot of massaging, it turned into a half-dozen lines of code that still appeared to have O(log2) behavior. This exercise, however, was more test-first than test-driven: I made a lot of changes to the code, but only after pondering why the test was still failing; the test remained relatively unchanged.
Moreover, at this point my intuition was screaming “warning, Will Robinson!” but the tests remained silent. Looking at the tests, I realized that I wasn't actually validating that my search properly traversed the list, merely that it found the expected element. So I wrote a new test, one that recorded each invocation of the find() method, and discovered that I wasn't properly maintaining high-tier links. Even though I'd written a nice recursive method, I was doing a linear search.
Would a “pure” approach to TDD have made me write this test? On the one hand, I was validating core behavior; on the other, I already had a green bar, 100% coverage, and lots of tests that showed me what I expected to see.
As I looked at the code and thought about what would be required to make it work, I came to the conclusion that I had walked down a cul de sac. So, in good XP fashion, I deleted everything and started over.
In my next attempt I introduced another nested class, SkipListManager, and went having SkipListElement be a dumb data container. Well, almost a dumb data container: I made the decision that it should know about its neighbors.
This led to an interesting situation: to write my tests, I wanted to be able to connect two elements together at multiple tiers, so wrote an append() method to do so. As I moved forward with the implementation, I found that method leading me into a corner: because it existed, I wrote my manager to use it, and ended up with a findAndRemember() operation that was almost, but not quite the same as the find() operation. I couldn't find a good way out without a third object, a “find iterator.”
At this point, I debated whether or not I really needed the manager object. Its sole reason for existence was to provide a back door for testing; giving the list protected methods would do the same. This was a rehash of my original concerns about TDD: protected methods are part of the interface of a class, and can never be removed. I decided that I didn't want to pollute SkipList just to support testing.
As I was thinking about the manager-element interaction, I decided that the best way back was to delete a large chunk of code (unlike the former attempt, I wasn't willing to throw it all away). My tests certainly helped with this: I deleted the chunks of code that I didn't like, and my IDE told me what tests depended on them. The code that remained was still covered by tests, still worked, and still represented a design that I liked.
I dove back in, and again ran into trouble inserting elements. Once I had appended an element in a tier, it prevented me from properly traversing the lower tiers. Score one for the tests: they turned up this problem right away. I still needed to run in a debugger to figure out what was happening, but the tests gave me a controlled environment in which to walk the code.
The test for the manager's insert() function came in at nearly 100 lines of code, as I validated how different element values would work their way through the chains. Although I wrote this test one section at a time, I suspect a TDD purist would look at the length of the method and cringe (it was actually quite a bit longer, until I refactored the assertions). The TDD approach would be to break each of these scenarios into separate methods, but that seems like a lot of needless duplication to me: I would have to repeat code to configure the list for each test. By combining these tests I additionally validate that I'm not damaging other portions of the list. I will say, though, that my variable naming conventions left something to be desired.
The final hurdle came from remove(). After getting the manager to properly handle insertions, I started working through the public API in alphabetical order. When I hit removal, I realized belatedly that I just wasn't going to to get away with a singly-linked list. Should I have seen this coming? Probably yes, given that my element-only approach ran into a similar dead end. But it points out a very good point: with TDD, the order of tests matters. On the positive side, I was able to insert the backlinks by breaking one test at a time, and I was still testing the forward links.
Are you ready for “the codez”? You'll find the list class here, and the test class here. The name “SkipList1” should give you a hint that I'm still not happy with the implementation, but it's time to ship (ie, get this post up on the blog). Over the next few weeks I'll be tinkering with the implementation (I have an idea that will take me back to a forward-linked list), and once I'm happy with it (if ever), will post a link to the final code.
Next up: my thoughts about this experiment, and TDD in general.
No comments:
Post a Comment