Writing about Knuth's literate programming book reminded me about when I met him (at a conference) and asked why the following algorithm wasn't in TAOCP. He grasped the algorithm from a ten-second description, and said it wasn't there because he didn't know about it. Good reason.

My TA at university (when I invented it for an exercise) wasn't aware of it either, but unlike Knuth, my TA didn't understand it. And I hadn't commented the code at all. Sigh.

Here are some words in sorted order:

You may observe that the boldfaced digits look like a binary tree. This property can be used to build a binary tree in O(n) given sorted input. Making an empty tree and repeatedly calling its insert operation is already quite fast, probably O(n log2(n)), so you may or may not care about the improvement. If the input happens to be in sorted order, lookups on a regular binary tree will be slow, but a tree built by this algorithm behaves well.

The algorithm:

1. Make a zero-filled array a of node pointers, as big as the tree can be deep. log2(sizeof(void*)) is fine.
2. For each item of input:
   1. Make a node with that input. Set its left and right children to null.
   2. Compute the node's proper level, l, by counting the number of zero bits below the least significant one bit.
   3. If l>0, and a[l-1] is filled, make the left pointer of your new node point to a[l-1] and clear a[l-1].
   4. If a[l+1] is filled, make its right pointer point to your new node.
   5. Set a[l] to the new node.
3. Make a new variable, n, a pointer to a node. Set it to null.
4. For each node in a, a[l], starting with a[0]:
   1. If a[l] is non-null, set a[l]'s right pointer to n, and set n to a[l].

At the end, n is the root of the tree.

A slight variation of the algorithm can be used to make sure the root has an almost equal number of left and right children.

Another variation can be used to rebalance an existing tree.

Donald Knuth invented literate programming and published the TexBook as an example. The book is great, or so I've heard from many people who've read it. So why is literate programming is practically unused today, at least the kind Knuth invented? (more…)

The TeXbook employs something called literate programming: Knuth wrote code and text together, effectively writing a narrative about that code, with that code as part of the narrative.

Knuth could do that, he's a genius. He was able to write a sizable program practically without bugs, in a note-book. Mortals like myself could not. I'd have to go back and rewrite earlier bits, and before long the narrative would stink. (more…)

The origin of udoc goes a long way back, to when I still was a student at the University of Trondheim, the world's first and only Quasar Toolkit user, and about to start working at Trolltech, which at the time was called Quasar Technologies (Hi Haavard) and occupied a room and a half overlooking a busy street in a rather unfashionable part of Oslo.

I wasn't very happy with the Qt documentation, which was then written using LaTeX macros and already obsolete. I was also an opinionated asshole and far too sure of myself, and I'd just learned about Donald Knuth's literate programming techniques, but I hadn't read his book. Naturally I looked at the existing litprog tools (there were quite a few) before discarding them all to write something good. (more…)