Red, Black & Blue
One of my neglected hobbies involves enliterating programs for the literate programming wiki. Donald Knuth originally described a literate program as one that has explanation of the code to humans as its primary goal. (Structured nicely, it even can be torn apart to assemble a real program with the right software.) Javadocs are nice, but focus on describing the public functions independently. That's fine if I'm only after the api, but a new programmer - so the reasoning goes - should study how great programs work the way english majors deconstruct Shakespeare.
However, most of the gaps in the literate programming wiki are either code dumps I can't easily enlitarate (language I don't know or algorithm I don't understand) or have no code at all. One page that I thought threaded that line was a python implementation of a red black tree. So, I began describing the tree node and so on, before I noticed that the implementation lacked deletion code.
Understand, I can do this as I have seen the algorithms before. But, they are tedious to implement and I have other coding projects I want to pursue. This was undertaken in a different spirit. So I let it languish. I dumped in some pseudocode and went back to working on Simpletron (which I will https://github.com/Nzen/Simpletron/wikieventually submit to the wiki). A month and one half passed and no one else has touched it. So, I thought, why not check for something I can shoehorn in from github.
Big mistake of course. Little choices are stock and trade of writing a program. I call the values stored values, so & so calls them keys. (Only found one worth a damn, by headius.) I use tabs, he uses spaces and the compiler/interpreter expects consistent depth whichever is used. Suffice to say, I wasted half an hour correcting those things in the copypasta inserted in the established code. Then, I spent another half hour getting his native code to print nicely. Headius appearantly doesn't care about color or whether it looks vaguely treelike. Rather than leave you doubting me, here is an example. I had to add the periods so blogger wouldn't trim the spaces.
20
. . 10
. . . . . 3
. . . . . 15
. . 70
. . . . . 55
. . . . . . . . 30
. . . . . . . . 62
. . . . . 80
. . . . . . . . 98
The point here isn't that I'm wiser than headius. I am faced with three choices.
A) Throw out everything, get some reliable pseudocode, and build it myself. While I may relish the finished product more, it is a waste of time and concession of failure on my part. ie, I couldn't understand what was going on so I spent good money after bad when something workable was at hand. Not likely.
B) Throw out everything I've enliterated on the wiki so far and enliterate this version that works totally. (After refactoring it, so I don't cringe looking at the one letter variables and so on.) This is a blow to my pride since I've essentially wasted effort so far. However, - after refactoring - this is the decision closest to my actual goal: just describing how the code is working.
C) Keep what I have and translate a deletion algorithm to work with the code (and explanation) already present. One path involves translating headius' algorithm. The other involves translating pseudocode to python. The problem with each involves rectifying various assumptions we've made even more fundamental than calling the stored integer value or key. Headius uses shells rather than nulls as the leaves, which means he can query the null's parents & so on whereas the current code has to check whether it was just handed a null. I haven't checked Cormen's pseudocode in a while but it may feature the same, or a different, disjoint assumption.
The trick in deciding between the latter two choices stems from how much perceived work comes from the translation and debugging it against reenliterating and refactoring a code base that won't fight me. To be fair, I haven't enliterated much as I left the insertion code unrefactored and uncommented. Printing is the same, thanks to that last half hour. Intro and some of the normal node are the same or trivially retargetable. And yet, I shouldn't take it's uncomplaining operation on faith. I need to test that this indeed deletes like a red black tree should.
While I began this post thinking that I would argue myself into patching the deletion hole with translated pseudocode, I will take on headius' legacy. Make it better, readable, literate. This just won't show up instantly on the wiki. Honestly, I can't complain about this. In similar realization last time, I will restrict simpletron to describing its operation (filling its wiki). Besides learning clojure, that means for coding practice I would have turned to Java and either finish the game portion of Conway's trees or Edwin's game. (Conway's trees is an implementation of his game with different types of trees underlying the map.)