What Is an Outline?, part 1
As I hinted at in my previous post, this is not as easy to answer as you'd think. To give you a hint on how hard it is, I'm currently up to my fourth major version of my fundamental data structure. The best way to answer "What is an outline?" is probably to take you through the same development process I used to get to where I am now.
A word of warning: I'll try to keep this largely comprehensible to anyone who's willing to really try to read this, but (as some of the more technical of you are probably already guessing) we will have to dip a little bit into graph theory and some programming concepts.
Why Are Data Structures Important?
It's first worth justifying why a discussion of the root data structure of Iron Lute is important. The following is a miniature discussion of the concepts laid out in my Bowers' Law essay:
Bowers' Law: A program can not safely rise above its data structures.Discussion: A programmer can try to extend a program's data structure's capabilities with code, but the code will inevitably get out of sync, the kludges and compromises will proliferate, and the whole becomes difficult to extend, rapidly collapsing into something too complicated for a mere mortal to understand. This kind of complexity can only work with geometrically more effort for every new feature... and in the worst cases, every new bug fix!
If a program's behavior must get significantly more sophisticated, the sophistication must almost always come from more sophistication in the data structures, not the code.
Example: Witness the wide variety of web pages that try to implement something as simple as hierarchical menus with Javascript. It is a true challenge, so much so that the linked web page is attempting to sell a solution for that problem, something that seems so simple it should be of neglible price. The fundamental problem is that HTML has no support for "menus", compounded by the wild differences in browser capabilities. In this case, the only choice is to try to glue together support for menus with code, but it's still difficult, must be frequently updated, is effectively impossible to extend, and for all this effort is still painfully quirky. HTML, considered as a data serialization protocol, is simply not rich enough to represent menus, and the addition of Javascript to the mix only allows something "close" to work. Since browsers are out of most webmaster's control, extending the browser is not a valid option.
The outline data structure will be at the core of Iron Lute. It will define its theoretical limit of its capabilities. Weak outline data structures are the fundamental reason I had to write my own outliner rather then extend an existing one; a layer or two I could have added, but trying to make an existing outline structure have the sophistication of my current structure would be impossible.
To understand Iron Lute as a programmer, you must understand the outline data structure. Understanding the outline structure as a user is somewhat less useful, but might still aid in understanding how it behaves on screen.
So, with justification, let's delve into the outline data structure Iron Lute is using:
Outline Data Structure Version 1: A Tree
The obvious choice of data structures for an outline is a Tree, specifically an "ordered tree". (Please see that page if you don't know what a Tree data structure is; you don't need to be heavy into computer science to understand it and it explains it better then I can, with more links for more help.) How that applies should be immediately obvious; each node has some number of child nodes, possibly zero, and they may have children of their own, and so on.
In the outliners I've seen, they also use what I'm going to call "monolithic nodes" for reason that will become clear later. A "node" contains everything about the node, such as the data, the children list, etc., all in the one Node data structure. So the tree consists of Nodes, linking directly to other Nodes, and so on.
At the top of the tree is the root node, which you can can think of as being "the entire document". Typically, you do not see this root node, you only view its children. One example where you can see a root node is the Windows Explorer as shown above, where the "Desktop" functions as the root node; normally you'd just see the stuff under it.
Certainly I started out here because it comes very close to what most outlines are. And while I don't have access to the internals of the commercial outliners like Radio Userland, I suspect this is what most or all of them use internally. (I looked over JOE and I'm 99% sure that's what it is using; corrections welcome).
A tree is a special case of the more general graph structure. Graph structures are notoriously challenging to work with in the general case, spawning an entire discipline dedicated to studying them. The primary advantage of a tree is that it is much, much, much simpler to work with, and you can define many useful notions without ambiguity. These advantages all stem primarily from the fact that there are never cycles in a tree (a path from node to node that eventually returns to the original node).
Some of the notions you can define are
- descendent count: counting not just children of the node, but all grand-children, great-grandchildren, etc. for all total descendents, not directly useful to the user but very useful for internal bookkeeping by the outliner
- path to root: There is one and only one path to the root node. This also include the notion that there is one and only one "parent" for a given node, which also means one can meaningfully talk about the "index" of a node, which is "which child of the parent I am" (i.e., if I am my parent's second node, then my index is 2). Conversely, for a given node there is only one path from the root, so for instance, if you want to expand the outline so a given node is visible then jump the screen to it, there's a well-defined number of nodes you have to open and a specific place to jump to.
- traversals: You get totally unambiguous traversals. (A traversal, since the Wikipedia doesn't define it, is a way of visiting all the nodes once. It generates a tree inside a graph; since the outline is already a tree, there's only one tree the traversal can follow. I'm leaving stuff out of the graph like whether it's "fully connected", since it doesn't matter here.) What that means to the user, among other things, is that there is only one representation of the outline on screen, ever; each node has these children, with precisely one path to the top, etc.
- There's some other non-obvious stuff, too, like the way a lot of properties can be determine solely by looking at the parents, like "my index" as mentioned above, either non-recursively like the index, or recursively for things like "what document do I belong to?". (To answer that, you ask the parent of the node, then the parent of that node, and so on, until you get to the root, and that's your document. In a tree, there's never any ambiguity about this.)
In fact these things are so nice that it's not immediately obvious that it's even possible to create an outliner based on something more general then trees. As we'll see later, it can be done with very few sacrifices by the client programmers, but it takes some work on my part.
To my knowlege, the only way around this right now is through transclusion, which at least Radio Userland can do and I don't know if any others can. Document "A" can transclude document "B", which may then transclude "A" again. Navigate down and you can (at least in theory) keep opening the transclusion forever, because it's a cycle.
This points to the first feature I wanted my outliner to have: I want the outliner to know and understand that it has already opened "A" and make the second "A" the same "A", such that a change in the one would show as a change in the other, so they could never be out of sync. Unfortunately, if that's going to work, the only real way to do it is to step outside of the world of trees and enter the hurly-burly world of fully-fledged graphs. (I'm not certain if Radio Userland does this or not; I seem to remember it doesn't, that it opens a seperate instance of the document for each transclusion, but it's been a while since I played with it.)
I also wanted to allow more complex linking, including links inside the document itself, such that a child may show us under more then one parent, and editing it in one place would propogate to both.
Why allow this? Alone, this feature does not add much. but in conjunction with some of the other elaborations we'll be discussing, it turns the outliner into something that can do more then just simple documents, but also provide a powerful view onto potentially complicated data structures, including (for instance) multiple interlinked documents such as a web site. This may not get us much in the single document case, but I envision a tool that natively handles much more complicated interlinking structures without imposing a tree on the whole.
An outliner at the micro level will always work with trees; if you have a highly-connected graph an outliner will never be the right tool to deal with it. (It doesn't have to work on all graphs to be useful, after all.) But in the large, many systems of documents either can not be, or should not be, represented as a simple tree. More structure is needed. So one of the exploratory questions I've had to answer as I develop Iron Lute is, Is it even possible to create an outliner that works with things other then strict ordered trees? I now believe the answer is a firm "Yes", but I did not necessarily know that in advance.
Design Decision 1: Keep The Tree Or Develop Something Else?
Issue: We need to figure out how to represent outlines in memory.
Options:
- Keep the tree structure and kludge additional capabilities in with code.
- Develop something more sophisticated.
Pros of keeping the tree structure: It's a known structure. Many nice and simple algorithms exist.
Cons of keeping the tree structure: We know it's too weak to do what we want. By the time we're done kludging the new capabilities on top of the tree structure those simple algorithms may not be so simple anyhow. We already know this data structure is intrinsically incapable of meeting some of our requirements. (This isn't necessarily an immediate reason to discard this choice, though; sometimes requirements must be modified to reflect reality.)
Pros of developing something new: A better data structure may give us a lot more power with not much more complexity. We should be able to do things easily that may not even be possible in a strict tree structure.
Cons of developing something new: Since nobody else has even done this in an outliner context to my knowlege, I have no assurance this is necessarily possible with a reasonable amount of effort. Thus, there's a significant risk that time spent creating something new may be a waste of time because it may never work.
Discussion: Since this is a personal project at the moment, I can afford to discount the risk of wasting my time, in favor of the potential benefits afforded by a more capable data structure.
There is also the consideration of why am I bothering at all if I'm not going to improve on existing outliners?.
Finally, while keeping the tree structure may seem like the "safe bet", it really isn't. This is where design experience comes in; careful consideration says that keeping the tree structure would be a disasterous mistake. Explaining why in detail would take a long time, but it boils down to the practical effects of my oh-so-humbly-named Bowers' law earlier: The number of layers of kludges on top of that structure would just kill me right at the outset of my programming.
Therefore, after weighing the risks, I decided to go ahead and try to create a more sophisticated data structure.
The next design decisions we will examine stem from my attempts to create a data structure that handles transclusion in a way that meets my earlier requirements that the transclusion be "real".
Next up: Handling transclusion, and hitting a whole lot more birds with that one stone then I planned.