Lightspeed Blog

Disclaimer: non-Computer Scientists may want to avoid reading this; it contains opinions of a geek-oriented nature, and pedantic discussion of data structures. You have been warned.

This Tuesday I return to college from a 2 week break. Things had been pretty much non-stop since I got back in January (hence the lack of updates) and since I don’t expect it to be any less frantic from when I’m back (what with me having 5 weeks to code a Real-Time Strategy Game), I decided I’d try to get as many of my assignments done over the break as possible. Despite making that commitment, I managed to spend the first 2 days of it furiously coding in Java, despite the fact that I’m not even using Java in any classes this semester.

I had read about Skip Lists a while ago, and thought the break was a perfect time to implement one. Skip Lists maintain several sorted lists of data; the lowest level has a link to every item, like a normal Linked List, and each higher layer has progressively fewer, allowing you to “skip” a number of elements in a traversal. If you’ve passed the object you’re looking for, you go back one link and drop down to a finer-grained list (The original paper on the subject explains things much more clearly than I can). Because of the need to maintain several lists, Skip Lists use more memory to provide faster access; but as any NASCAR driver or amphetamine junkie will tell you, it’s all about the speed.

I wanted to make sure my code was neat, so I downloaded and ran both Checkstyle and FindBugs on it (FindBugs is actually developed by the same guy who invented Skip Lists, Bill Pugh). Sure enough, FindBugs found several situations where crashes could potentially occur, such as not checking if method arguments were null. It also found a few glaring errors, which would have taken much humming, hawing, pondering and noggin-scratching to fix. In short, it saved me a LOT of time, and that was just in writing one class. I’ll certainly be coming back to that plugin…

While using Checkstyle definitely improved the quality of my code, it certainly wasn’t as pleasant an experience. Straight from the start it gave me dozens of misleading warnings, because it wasn’t set up to work with generics. it was asking me to insert a space before and after every occurrence of ‘<’ and ‘>’, which is fine if they’re being used as arithmetic less-than and greater-than; not so helpful when they’re specifying a generic parameter. I came across this bug filed in the Checkstyle bug tracker, which contains fixes.

So, where’s the finished product, you ask? Right here. It implements the Collection interface, so it can be used in place of any other Collection. I’m pretty proud of it; it’s clearly written and well documented. It’s also probably the only code I’ve ever written that’s immediately useful to someone else

(To anyone who waded through this post without knowing what I was talking about: first, why? and second, here’s something a little more entertaining)