uwMike » Archive » Avoiding Special Cases

I'm in Waterloo at the moment, and next available to work in September 2008.

Avoiding Special Cases

July 14th, 2005

Every programming problem has some corner case. Every loop has a first or last element that requires slightly modified processing.

Every time I create a special case in a program, I feel a little bit dirty. I’ve gone ahead and created redundant code. I’ve placed the same logic in two places. When one is changed, the other will break.

Example

There’s an assignment we’re working on in class that is the epitome of ugly cases. It’s a simple implementation of a Binary Search Tree. Most of the solutions I’ve seen for the add-node function involve three or more nested cases and if-blocks, cordoning off various chunks of almost-identical code from each other.

Anyone’s who’s worked with complicated pointer-based structures in C will tell you that this is par for the course.

Uglyness

But I came up with a really sweet solution. It eliminates special cases altogether. It’s a mere 15 lines long.

What’s the drawback? It uses a pointer to a pointer to a structure. Consider the following snippet:

if (compare leftChild);
else
  nodeLocation = &((*nodeLocation)->rightChild);

It makes perfect sense to me right now, which is all I need, with the assignment due in a week. But will I still understand this bizarre pointer operation a month from now?

Is it worth the readability tradeoff to have a function with zero redundancy? What if it’s 1/3 the length of the alternative?

For me, I’m pretty sure I’d rather see less code, even if it means reading through the comments to understand a clever hack. And besides, clever hacks give me the warm fuzzies.

Mike

← Earlier Later → Posted at 4:00 am to School.

Discussion

I’d go with your creative solution. They mark it on output and as long as you make comments and it is the right solution, they will give you the marks. I would greatly like to see the code (after mine is done, of course) and get an explaination. I’m going to stick to the cases, as it’s what I know. Safe.

Posted at 12:54 am on July 15th by Jeffrey Aho.
Basically, I guess it ends up being a discussion about abstraction. The more ‘levels’ something can be abstracted in, the more ‘bottom-uppy‘ the code is, and hence more reusable.

Posted at 1:50 pm on July 15th by Mike Purvis.
Well, personally, I can’t really picture programming without pointer-pointers (and crazier things once the data structures get more interesting).

I guess you engineers are probably working in C as opposed to C++? In C++, if you aren’t worried at all about performance, you can write some very tight binary tree code using classes and recursive calls (I seem to recall one that actually stored extra leaf nodes that contain no data, but simplified the cases, allowing very short methods.)

The only reason to be using C these days is if you’re really performance paranoid, in which case you ought to be pretty comfortable with strange pointer operations.

Posted at 3:18 pm on July 17th by Daniel Dresser.
Yeah, well my previous pointer experience had been with Pascal, which is pretty touchy about those weirder things. PHP doesn’t have pointers at all, in part, I expect, for stability, and simply because nested associative arrays are such a powerful structure.

This is supposed to be an introductory course for deer-in-the-headlight folks whose only prior experience is, you know, last year’s C++ course.

Anyhow, yeah, once I drew a little diagram and got the stars and ampersands in the right places, it worked like a charm. But still, it would depend who else was seeing the code. Me in six months would probably still get it. But would co-worker X get it?

BTW, if you’re even in Waterloo before September, Dan, you need to stop by for dinner so you can get USB mice working on my Gentoo…

Posted at 4:14 pm on July 17th by Mike Purvis.
Hey Mike, I’m done the assignment, but after Monday, would you mind showing me the explaination for this code? Looks like a great idea, if only I could get what you’re trying to say here..

Posted at 6:20 pm on July 22nd by Ryan Hildebrandt.
I ‘discovered’ exactly this same thing a few weeks ago. It’s a neat solution and I see no reason not to use it. If you are worried about not understanding your code in a few weeks, just make sure you write good comments.

Another trick useful for linked lists is to create dummy head and tail elements of exactly the same type as the real elements. This way you completely avoid any special cases when adding or removing items from the ends of the list because you are inserting between two existing elements (one of which is the dummy).

Posted at 6:18 pm on August 17th by Ian.

You can use Markdown for style. I love hearing from readers, but please don’t hijack the discussion, use offensive language, or try to sell anything.

Avoiding Special Cases

Example

Uglyness

Discussion

Leave a Reply