Alan’s Kiloblog

When you are in the psychological moment for a particular project, something will beacon you to leave your moment, and expend that certainty and conviction elsewhere.

It is amazing. Is amazing that there is an economy for that sort of thing, but it is true, there are those that sense this. It is amazing how efficient these markets are.

Which is why I’ve decided that these are the following questions to ask, the next time I’m faced with an opportunity that does tie in with my stated agenda.

• This hasn’t worked before, is the first thing to state.
• How exactly will I benefit? Exposure doesn’t count. I get better exposure working on my turf.
• Who pays for it? It had better be all expenses paid, and then some, because I don’t have time to entertain.
• How much of what I’m doing are you aware of? Because, you might have got it into your head that New Orleans needs to be a component of your master plan, but if you haven’t done the research, I’m not going to change my position on matters to suit you.

Hint: If you’re thinking opportunity, be informed that I’m thinking crisis. I checked the Chinese dictionary, the are not the same word.

I am considering moving the WordPress blog on ThinkNOLA so that it is the landing page and changing the URL structure. This is to create smaller URLs that are easier to cut and paste into email.

What has kept me from putting WordPress as the base is that I always imagined a different application there. An application that still exists primarily in my imagination. I’ll let that go. When the time comes, I can incorporate the existing URL structure into the new application. This is aligns with the attitude that content and archival is important, and that new code should respect the cumulative efforts of the user base.

Now, I am concerned that redirections will suck out some of my Google Juice, especially on the few articles that are rock stars in my mind. Articles about AmericaSpeaks are slipping anyway.

Ryan Vis said something about how by virtue of being a redirection, the landing page for ThinkNOLA.com is invisible to search engines.

Is is best to rework ThinkNOLA to accommodate the usage patterns of New Orleanians. They need URLs that won’t break in email. I don’t like using tinyurl.com with it’s mystery meat URLs. That can’t do much for my Google ranking.

People will copy and paste URLs into other forums, and if they don’t break, then incoming links to ThinkNOLA.com will increase.

Had to look and look to ask why this man was so familiar. He’s from Ann Arbor! The photographer has a very nice photoset of Ann Arbor places.

I’ve decided to return to the original idea for kiloblog, which was that is it is a stream of consciousness blog, where I wrote what I was thinking, and sorted it out later. It is a place where I can be personal.

If you were following this blog because I wrote about some programming project that piqued your interest, you can read more about it, and in more detail at Alan’s Blogometer.

You will find a lot of talk about software development in this blog. You may follow it for a while and think that it is a programmers journal. That is because I will go on a software binge, muddle my head with thoughts about software, and offload them constantly.

Then, without any warning, I’ll be writing about some deep personal failing and it’s repercussions. Don’t worry. I’ve not snapped. It was merely a context switch, one that wouldn’t seem so odd if you were not expecting another soliloquy on Java serialization.

There once was a time when I said that I couldn’t do social work. That it is not in my nature to be able to deal with people’s problems. That’s work for a different temperament than my own.

I am angry with that sentiment.

I will have to simply dismiss that world view that was shaped by a pointed isolation from social problems, to an extent that any sort of service, read to children, bring meals to the elderly, any sort of tangental intersection might reveal evidence of the pressures that people feel every day.

Switched TheBayouBoogaloo.com to a simple structure.

Used to do the long structure like http://kiloblog.com/2007/04/23/why-I-like-to-put-mustard-on-blueberry-pancakes, but who cares when I posted, really? It makes the URLs long and makes finding something via auto-complete in the browser pointless. I’m probably not going to write about my tangy, sweet breakfast taste sensation more than once. Certainly, I would not have to explain myself more than once.

My new structure is http://TheBayouBoogaloo.com/post/volunteer-2007. Because I’m able to edit the post slug, I choose one that would not be long, and not collide with a call for volunteers in 2008.

I’m all about Textile.

I’ve installed Textile 2.0 on every WordPress installation, and I regularly use Backpacks and Instiki in my work, in recovery, in New Orleans. I’ve created lesson plans around Textile, and taught neighborhood leaders to use Textile, instead of web-based WYSIWYG.

Why? Because Textile works. It’s easier to teach than a flakey JavaScript editor. Once they get it, they use it, and there is little followup.

I’m a fan.

Thus, I’m creating a Textile parse for Java, which is my language of choice. There are a few available already, I know. My needs are a tad different.

It follows that my implementation is a tad different as well. Rather than processing a string in place, I’m going line by line, building the paragraph blocks, and then processing the contents recursively.

I’m finding that there are some serious differences between the Perl and PHP implentations of Textile, and the Ruby Redcloth implementation.

Thus, I’m curious as to whether or not we can standardize on a definition of Textile.

I’m also finding that all of the implementations will produce invalid XML if fed the right sort of garbage. Because I’m emitting SAX events, that will not work for me. I’d like to have bad Textile, still produce valid XML.

I’m particularly interested, because I’d like to create a round trip implementation of Textile. One where, if you can go from Textile to XML, then you can go back to Textile, so that I can store the Textile as XML.

This would be a subset of XHTML, and it would be limited. Only that XHTML which could have been produced by Textile would be acceptable.

In order to do this though, it would be nice to start from a definition of the Textile languagae, a BNF Textile grammar.

Is there interest in creating a definition of the Textile language?

At the outset, Strata was developed for use with in memory and file backed implementations of tiers.

When in memory, branches and the objects can be stored in arrays. The default implementation uses ArrayList classes to store objects.

When file backed, their are two types of objects that can be stored, variable length objects and fixed length objects. Objects can be stored within the tiers or by reference.

When file backed, tiers are softly or weakly referenced, so that they can be collected. Thus, they can act as caches of the objects they reference.

Storing by refernece means storing an address. Whether or not the object is stored in the tier, or by reference outside the tier, the object needs to be in memory for comparisons, for traversal at both the leaf and the inner tier.

By reference storage can keep the object within the in memory tier, or it can perform a look up of the referenced object. The object is an simple object, like a string, it might be easier to keep it in the memory tier, as part of an address, object pair. If it is a complicated object, it can load the object through a caching mechanism.

These were once the objectives for Strata, reflecting an early understanding of the project. I’m about to rewrite them, so I thought I’d put them somewhere, besides the wiki history.

Thus, the short-term objectives for Strata are as follows.

• Leaf nodes only to store references to file positions, not store the data itself.
• Branches also store only references to file positions, and hold a list of objects read from those file positions to use as keys.
• Thread-safe.
• File backed, paged.
• Supports efficent insertion and deletion, while maintaining the balance of the B-Tree.
• Equality comparison query.
• Compares byte buffer ranges, not objects.

Crazy thoughts included storing partial in the inner tiers on pages, but this presents a strange case where a partial key might not fit on a page, if the length of a key is unbounded.

What changed? For the first two points, only the way I’d state them. Since it’s now a given, I don’t know if I’d state them. There are also a few more devils in those two details, only the fields of interest may be cached for example.

“Equality comparison query”, meant that the only operator supported is the equality operator, which is also given, but that’s all you need to implement between, less than, greater than, etc. Probably could not see that then.

“Compares byte buffer ranges, not objects”, the meaning of this has escaped my memory.

The crazy thoughts are reflections on how to store the objects referenced by the B+Tree. There was a time when I thought that the objects might be stored in the pages of the tree.

Authentic c-store Japanese bento by Ramil Sagum.

Malloc

The idea behind Bento it to take a file and divide it up using the malloc algorithm as described by Doug Lea.

Bento is written in Java for JDK 1.4.2 using NIO.

You can read more about Bento on my Wiki and you can paruse the source in my Subversion repsitory and you can use it under LGPL.

Design Goals

Bento is a file format for writing out discrete blocks of data. It is designed for the storage of objects. Bento is not supposed to be a database in itself.

Bento is a robust file format that provides

• storage of blocks of arbitrary size,
• random access to stored blocks,
• atomic writes of multiple blocks,
• thread-safe allocation and deallocation of blocks,
• and thread-safe reads and writes.

Funamentally, Bento strives to be a simple data structure that you can use to persist objects in your applications. You can use Bento as the basis for more complicated data structures or databases.

Usage

Bento can be used to serialize objects using Java serialization, to write out objects as Java primitives, or to store Java primitives.

A single Bento file can be organized into a database of different Java types. For desktop applications, this means that a single file can be the container for many different objects of many different classes.

Multiple Bento files can be organized into a database, spread across different file system, to reduce disk contention.

You can design resuable Bento based data structures and mix them into a single Bento file.

Quick Start

An example program that creates a Bento file with a static header and a single allocated block.

Bento.Creator creator = new Bento.Creator();
creator.addStaticBlock(URI.create("flag://agtrz.com/header"), 512);
Bento bento = creator.create(new File("data.bento"));

Bento.Mutator mutator = bento.mutate();
try {
    Bento.Block block = mutator.allocate(512);

    ByteBuffer bytes = block.toByteBuffer();
    for (int i = 0; i < 512 / 4; i++) {
        bytes.putInt(i);
    }
    block.write();

    Bento.Block header = mutator.load(URI.create("flag://agtrz.com/header"));

    ByteBuffer bytes = header.toByteBuffer();
    block.getAddress().write(bytes);
    header.write();

    mutator.commit();
}
finally {
    mutator.rollback();
}

bento.close();

Bento.Opener opener = new Bento.Opener();
bento = opener.open(new File("bento.data"));

ByteBuffer header = bento.read(URI.create("http://agtrz.com/header"));

ByteBuffer bytes = bento.read(new Bento.Address(header));
for (int i = 0; i < bytes.capacity() / 4; i++) {
    if (i != bytes.getInt()) {
        throw new IllegalStateException();
    }
}

bento.close();

Mutation

A Bento file is written using a Bento.Mutator. All of the changes performed by a mutator are atomic. The changes are not made perminent until the commit method of mutator is called. The changes can be discarded by calling the rollback method of the mutator.

After calling commit or rollback the mutator can be reused. Calling commit or rollback when there are no uncommited changes held by the mutator does nothing. Thus, we use a try/finally block to recover the state of a Bento file when a failure occurs.

public void storeObjects(Bento bento, Bento.Address address) {
    Bento.Mutator mutator = bento.mutate();
    try {
        Bento.Block block = mutator.load(address);
        block.toByteBuffer().putInt(this.magicNumber);
        block.write();

        mutator.commit();
    }
    finally {
        mutator.rollback();
    }
}

Concurrency

Bento synchronizes the list of free blocks, but does not synchronize the blocks themselves. Blocks can be allocated and freed in a thread-safe manner without further consideration by the application developer.

If you read and write blocks without some syncrhonization strategy, you’ll turn your Bento file into garbage in short order.

Multiple threads can read the same blocks, but blocks that are being written should not be written or read by other threads. Reads can be shared. Writes are exclusive.

A simple strategy is to use a read/write lock from the concurrency library to gaurd the file during updates.

Bento strives for liveness, however. It places as few locks as possible on the management of list of free blocks.

A more sophisticated strategy would place locks on the blocks themselves. A composite object, such as a tree, could lock a tree root element. Different threads can then operate on different trees in the same file. They would not run afoul of each other.

Atomic Writes

A Bento file is edited using a mutator the object. The mutator object keeps all block writes, allocations, and deallocations are kept in memory until the user commits or rolls back the changes made by the mutator.

Journaling

All reads, writes, allocations and frees are performed on buffers in memory. Only when a mutation is committed or rollback, is the underlying file written.

Journaling is implemented by writing out the list of operations into a journal prior to applying the changes to the file.

The journal can be implemented using blocks within the file, or it can be implemented using external temporary files. The former is good for desktop applications, where the user may move a corrupted Bento file out of reach of the external journals, or unwittingly delete the external journals. The latter is good for a server application, where multiple Bento files and journals can exist in a single directory, watched over by an administrator.

I do not like checked exceptions. I consider them harmful. They create a lot of noise. They insist on attention at every level of a program, when I’d prefer to decide for myself where I’d like to handle exceptional conditions.

To reduce the amount of noise in my Java programs, I created a class called UniversalException, and use it as the base class for all my exceptions. At the starting point of a program, I can catch UniversalException, and place my application wide error handling there.

A new trick is to add the ability to declare an exception and fill it full of useful information as a one liner.

if (!file.exsits())
    throw new StorageException("file.not.found")
             .info("file", file);

There is a method in UniversalException called info that adds exception information to a linked hash map of exception information. Thus, it’s pretty easy to throw an exception and have some meaningful reporting in the stack trace.

This only works because I’ve renounced checked exceptions. If it meant something to me to declare a method as one that throws StorageException, then I’d have a problem, because the info method would generalize the exception into a UniversalException.

How nice to not have to worry about that petty little language misfeature.

After a disappointing start with jQuery:

1. No clear strategy to preserve state of custom objects.
2. No response to questions in the jQuery discuss mailing list.

As a result, I fetched the Yahoo UI Library and Jack Slocum’s Yahoo UI Extension Library. That grid worked well in Internet Explorer 6 and in Firefox. In Safari, the column resize seemed to fail.

• Yahoo UI Extension Library Grid.

Nice. A bit heavy. There are a lot of dependencies. A lot of features that I don’t really need. I can turn them off, but the code and the complexity are still present. In essence, I wanted a table that had a sticky headers.

I found that state is stored in jQuery fancy-pants extensions by creating a hash and attaching it to the target element. I don’t know why that couldn’t have been said on jQuery discuss.

I’d imagined that there was some limitation, that not all browsers supported “expando” properties on document elements, but it must not be the case.

Here is the simple table that I’ve created in jQuery. No resizable columns.

• Grid One.

This works on IE 6, Firefox 1.5 and Safari 2.0.4.

It was only possible once I’d abandoned table markup, however. The table is rendered with div and span elements, rather than table, tbody, tr, td, etc.

Much easier. The implementation of tables has a lot of baggage attacted to it.

However, I’m not finding that it doesn’t scale. The rendering causes the “Unresponsive Script” warning in Firefox when the table is large.

• Grid Two.

In the course of creating this grid, I fixed the innerWidth and innerHeight methods of dimensions.js, which incorrectly named the border properites, “borderLeft” instead of “borderLeftWidth”, and neglected to deduct the padding width.

Update: I’ve addressed some of the performance issues of loading the table. The time that it takes to load this new revision is greatly reduced. Speed up is a factor of ten.

• Grid Three.

I build the cells as spans, so that I can measure the width of the text, when rendered as a span, an inline element, this is possible. A assign a class name for the span, based on it’s column position. Then I’d set the dispaly property of the span to block. In the end, I’ll define a CSS class for each column, with the width set to the maximum width for that span.

By removing the assignment of the display property of the span, I got my speed up.

I also speed up loading by measuring the border and padding for each column once, rather than calculating the inner width for each column, I keep track check the offset width, and calculate the innner width by dedcuting the total of all borders and padding of the first from form the offset width. The assumes that the styles for each column are identical in all rows (which is perfectly reasonable and all I need).

It still chokes on the large datasets that I’m using, 500+ rows. For my next trick, I’m going to load incrementally, so that the unresponsive script warning does not appear.

The grid will render much faster if I have a set width, of course. I can create an optimized rendering method that builds a large HTML string and injects it, 100 rows at a time, in the case of resorting, or in the case where I’ve assigned widths to all the columns.

Update: The grid now renders concurrently. Different browsers prefer different combinations of rows per timeout and time between timeout.

• Grid Six, 100 rows.
• Grid Six, 500 rows.

The important thing is that the page is responsive. The user can scroll the grid while it loads, the back button and other controls still work.

The key tradeoff is that the slower the grid loads, the more responsive it is.

Rendering is faster in this incarnation. Absolute positioning is much faster that relative layout. Much faster than laying out the grid as blocks that float left.

I’m implementing a B-Tree in Java. The project is called Strata. You can view the source, is is in the strata subdirectory of my subversion repository. There is a lot of cruft from an earlier attempt.

I’ve yet to choose a license.

This tree is the first indexing option in Momento, which is a large file XML database that I wrote last year, when I was in Ann Arbor.

Strata will index the normalized text of a specific node. The only query supported at the outset is equality.

Then I can use Lucene to do full text indexing. In order for Lucene to be effective, you see, it must be a simple matter to retrieve the document. Indexing unique atom identifers, would give a key to fetch the document resulting from a Lucene query.

My research B-Tree implemetnations can be tracked with my del.icio.us account, under the tag strata.

I’ve written a description of the tree structure at my user page on the New Orleans Wiki, under a Software Development page.

Set out to look for a ready made grid to import information from a spread sheet. The nicest one that I came across, via the Rails Spinoffs mailing list was A Grid Component for Yahoo! UI - Part 1, the work of a fella named Jack Slocum. This introduced me to the Yahoo! UI Library, or rather, made me take notice.

I’ve just completed a real deal Prototype/Script.aculo.us application, for the neighborhood boundary project at Think New Orleans.

Prototype and Script.aculo.us are well documented, and there is enough mention of quirks between the Google Maps API and Rails Spinoffs mailing lists, that I’ve been able to navigate the incompatibilites between Protoype and Google Maps.

The Yahoo! UI Library contains parallels to the Prototype library, such as effects and event handling structures. What caught my eye, was the Ajax implementation’s acceptance of a structure of event handlers, much like in Prototype, with the addition of a field for the target of the event handlers. Assuming that this pattern is repeated elsewhere, this is more economical than saying:

this.onMouseOver.bindAsEventListener(this)

When that is repeated for every mouse action, it seems tedious. This may have more to do with my preference for short lines than any rational complaint.

One nice concept, shows that people are somewhere thinking about the lessons learned from Prototype, and other libraries that I’m not as familiar with, like Dojo. The code Jack created for his grid is crisp.

The crisp code and straight creases makes me think of Borland’s Object Windows Library, which was where I entered the world of UI programming, many years ago.

It also makes me think of Second System Syndrome, first diagnosed by Fred Brooks in the Mythical Man Month. The Yahoo! UI Library adds more structure to Prototype and Script.aculo.us, creating a library with more rigor.

In Jack’s blog he references a Zebra Table Showdown over at a blog about jQuery. Although he goes on to show that with his extension library, the Yahoo! UI Library can be just as terse, I’m already drawn to the jQuery library.

jQuery has the feel of scripting, where the Yahoo! UI Library has the feel of the Object Windows Library.

The former uses the document itself as part of the model. In Prototype derived code, the trick where you bind the “this” object to an object of your choice, is used to create a controller. This is a step just far enough away from the Document Object Model to organize one’s thoughts, but not so far away that you interact with the browser’s document as if it were a sofa-surfing paradigm that stayed longer than the weekend it promised.

jQuery makes it easier to navigate the browser’s document, and therefore, makes applications a matter of knitting together document nodes with events. That’s a fresh new look for this generation of JavaScript programmers, or a return to the practices of the days of yore. Not a second system effect.

The task at hand is to create a polyline draw UI that people can use to edit their own neighborhood boundaries.

The tool that I’ve created uses the Google Geocoder to set the points. (Previously, I’d used a Geocoder based on the Perl module Geo::Coder::US.)

The UI builds a list of points. There is a box at the top where the next point is added when the goecoding resolves correctly.

There is the issue of how to resolve multiple geocode answers, when they occur. One option is to draw the possiblities, each in a different color and ask the person to choose which they want to use. If there are three addresses, say, each point can be displayed with different marker, and marker color, the Three addresses can appear at the top of the list in a style of some sort, something bulbous, that has the three addresses with color coded back grounds, the user can chose one of the three options.

Mousing over each coordinate and highlights them. An X will appear to the right, allowing you to delete the address.

I’m trying to decide how to insert.

I don’t want to reorder the list. I’d rather move the insertion point.

I’m imagining drawing a border, or moving a div to show the insertion point. Drawing a dark line above where the insert would take place.

What will I learn when this is done? I’ll have chosen a temporary icon set, or possibly it is the one to go with.

I might learn how to create the rounded edges that are found around Flicker photosets.

One of failure points is that once I get too familiar with something, I loose interest in it. I assume the because I have an understanding of something, that everyone else does. It must be time to move on. More likely, continue to have a perception that is uncommon, the difference is that I have explored beyond the point where it’s novel, to the point where I can act on it. Perhaps it is not as earth shattering as spaghetti you can eat with a spoon, but maybe it is. The implementation and marketing of idea make the difference. This is true of software programming especially, where an idea gets implemented, and it doesn’t seem so slick anymore. At that point it falls victim to refactoring, so it can be really truly elegant, and perhaps even read email. It doesn’t ever seem to make it over the wall, however.

I’ve reworked my build environment on the software that I abandoned last year, for a renewed life in post-Katrina New Orleans.

How do I feel? I feel pleased that I’ve hived off dozens of hideous Ant scripts for a single Groovy script that builds everything. Returning to the code base after a ten month hiatus, it struck me as fully OCD compliant, an attempt to create a build environment in Ant, that built multiple projects, with an awareness of their dependencies, without the benefit of Turing machine.

How I hate Ant. I hate it. It is horrible nonsense. It is wrong. I can’t believe that an industry attempts to develop software with a build environment that lacks the benefit of a Turing machine. You cannot loop. You cannot recurse. Why must I install extensions in order to add my own logic to my own build?

Software should not make a programmer seethe.

Now I like Groovy. The toy language. The language that was not invented here. It’s strangely European. An Anglo-Franco-Deutsche concoction. The EU’s take on an American VM and a Japanese syntax.

The last I looked at it, the hope was that perhaps, it was similar enough to Java, that Javans would adopt it do the things that they’d done with half-assed XML configuration abominations like Ant, Maven, or Jelly.

Why not adopt Ruby? Java is a keeper. Java is a keeper because of ANTLR and Saxon. (I’d like to play with Modern C++, because there lie concepts that are not available in Java or Ruby.) Those are two software packages that I find delightful.

Why adopt Ruby? They have an nice mailing list. It is very friendly and helpful. Like the Perl groups nice people. Javans have no place to congregate as central as Ruby. Javans tend to be annoying pedants and they bicker about stupid, boring things. A lot of dogma for the sake of dogma, so that they can sound as smart as C++ programmers.

Can’t stand to have someone talk about the Singleton pattern for yet another thread. Can’t get a straight answer on all the conceptual problems raised by checked exceptions. Then there is a lot of Socratic-retentive half-answers to questions. Familiar tone from comp.lang.c++, but there I suspect that someone really is telling you about a convention to follow so that your code will port to the most obscure hardware platforms, not simply because it’s more object oriented or some such.

Maybe if I program in Groovy I’ll finally get a change to practice my high-school German. More importantly, there is a community growing up around Grails that has a whip-it-up-a-tude approach to programming. If something is too slow in Groovy, I can implement it in Java, using Eclipse, which I also enjoy. I’ll gladly use a strongly typed language, for all the neat tricks that you get in the IDE. Tricks I miss when I don’t have them handy. But, you’ll excuse me if I pass Object instances around because too much typing kills reuse, and adds too much complexity. They only reason I want a Duck is because I want to type the letter “q” and have Eclipse make it quack. Reminding me what goes into a quack, and what comes out.

Why not JRuby? It’s not OCD compliant. The difference in naming conventions drives me bonkers.

Where have I landed? I’m going to take a peek at Groovy and Grails. Then I’m going to look for more ways to put Groovy in Saxon. It seems like a better way to mesh with XML. Maybe I get Groovy happy, creating Groovy options for libraries I create. Maybe Grails is part of every solution, giving me scaffolding to CRUD my objects while I work on creating more elaborate interfaces.

Relay still comes into play, because I’ve been wanting this XML dependency engine for a long, long time. What I’m prepared to consider, is that Groovy might make an ideal controller, an easier to type expression of program logic or flow, easier than the purist notion that XSLT is the one language to rule them all, pipelines are expressed as XML documents, XSLT creates those pipelines. XSLT is an XML document.

Where does this stream of conciousness lead me? Grails for the sake of the Groovy community. They seem like decent people with some sense. That they are not hamstrung by some adherence to object this or that, it seems like they are likely to be a helpful lot. Grails is nice, because it’s an application. Maybe Relay can be an application, one that is not too terribly parallel to a Ruby project.

Rails is a no go because I have a high resistance to hyperbole, and this burp of investement in browser based software is nothing less than what the W3C, Microsoft and the Mozilla project would have expected, once people realized how effective the browser is as a client. Ajax is one of those things where someone discovers something as it reaches completion, and must think they’ve invented it. I swear this was all at the MSDN web site in 1999. Go look it up yourself.

Anyway, I’d like to put a bow on this and move on with my life. My build environment gives me any more grief and I’ll redistribute with Eclipse and insist that users run my code in the debugger. Really, I don’t care if you can’t build it. I can. Finally. I hate Ant. Oh, how I hate it.

I’m not going to do this anymore, if it makes me unhappy. I used to program in Perl. It was fun.

The B-Tree has two different types of nodes, an inner node and a leaf node. Both have methods that are similiar, except they operate on different types of objects. The inner node has a branch object, which is a pairing of an object in the container to test, and a pointer to the next node to visit if the sought object is less than or equal to the test object. There is a method called isLeaf to determine if we are at a leaf.

If we are, there are different things that need to be done. How nice it would be to have that be the only indication in the code, that context, and to not have to create different interfaces for the inner node and leaf node. It is turning out to be a lot of thinking about class design, when I’d much rather focus on algorithm design. Is there a magical pattern out there, with an additional level of indirection, can I have one node be both inner and leaf?

Perhaps, but then you have many small functions, which is supposed to be a good thing. It isn’t. At any point I could write a test to assert that a node can be correctly inserted into a leaf, but that does not mean that is makes for a correct B-Tree. Unit testing these tiny functions, I’m not sure the value. In the end, there will be only on real implementation of the leaf node, so a fixture against which new implementations can be tested will cut the other way, requiring that the fixture get fixed, should details of the implementation of the tree change, rather than having it dictated the implementation of new node classes.