Last time we saw that producing all the subsequences of a given size k from a given sequence of size n is essentially the same problem as computing all the sequences of n Booleans where exactly k of them are true. How do we do that?
An approach that I often see is “enumerate all sequences of n Booleans, count the number of on bits, and discard those which have too many or too few”. Though that works, it’s not ideal. Suppose we are seeking to enumerate the combinations of 16 items chosen from a set of 32. There are over four billion possible combinations of 32 bits, and of those over three billion of them have more or fewer than 16 true bits, so that’s a lot of counting and discarding to do. We can do better! To do so, we’ll use a combination of all my favourite techniques:
- Immutable data structures
- Abstract classes with derived nested classes
- Recursion
Long-time readers of this blog will have seen me use these techniques before, but for new readers, a quick introduction is in order.
The idea of an immutable collection is that the collection does not change when you add or remove something from it. That seems contradictory, but really it makes a lot of sense. The number 3 does not change into 7 when you add 4 to it; the number 3 is eternal and unchanging. Rather, adding 4 to it produces a new, entirely different number called 7. Similarly, adding an item to a collection does not change the original collection; it produces a new collection.
That might sound inefficient, but actually it is very efficient: because the original collection is immutable, we can use all or some of the original collection data structure in the new data structure.
The data structure I need to solve this problem is an immutable stack of Booleans, so let’s whip one of those up. (Of course we could use data structures in the BCL immutable collections, but for pedagogic and amusement purposes, let’s just make our own.) The operations I’m going to need are just pushing and enumerating, but for completeness let’s add public members for popping and emptiness checking as well. I’ll use one of my favourite techniques of an abstract base class whose derived classes are nested within it:
using System;
using System.Collections;
using System.Collections.Generic;
abstract class ImmutableStack<T>: IEnumerable<T>
{
public static readonly ImmutableStack<T> Empty = new EmptyStack();
private ImmutableStack() {}
public abstract ImmutableStack<T> Pop();
public abstract T Top { get; }
public abstract bool IsEmpty { get; }
public IEnumerator<T> GetEnumerator()
{
var current = this;
while(!current.IsEmpty)
{
yield return current.Top;
current = current.Pop();
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public ImmutableStack<T> Push(T value)
{
return new NonEmptyStack(value, this);
}
private class EmptyStack: ImmutableStack<T>
{
public override ImmutableStack<T> Pop()
{
throw new InvalidOperationException();
}
public override T Top
{
get { throw new InvalidOperationException(); }
}
public override bool IsEmpty { get { return true; } }
}
private class NonEmptyStack : ImmutableStack<T>
{
private readonly T head;
private readonly ImmutableStack<T> tail;
public NonEmptyStack(T head, ImmutableStack<T> tail)
{
this.head = head;
this.tail = tail;
}
public override ImmutableStack<T> Pop() { return this.tail; }
public override T Top { get { return this.head; } }
public override bool IsEmpty { get { return false; } }
}
}
We can create one of these like this:
ImmutableStack<bool> myStack =
ImmutableStack<bool>.Empty
.Push(true)
.Push(false)
.Push(false);
And hey, now we’ve got the stack false, false, true. Again, remember, pushing on Empty did not change Empty at all. It’s the same as it ever was.
Our technique is going to be to recursively build longer bit sequences out of shorter bit sequences. Since pushing onto an immutable stack is cheap, and we don’t ever have to worry about the stack being changed by someone else, we’ll see that the algorithm is pretty straightforward.
Next time: Now that we have our helper class, we’ll actually enumerate the combinations.
Fabulous adventures in coding 
Two derived private classes within an abstract public class that returns instances of the private classes cast as the public class? Mind = blown. (The lack of needing any reflection is just icing on top of the cake.) This code is poetry.
Thanks! It is a lovely technique that I wish more people used.
This pattern is also really useful for emulating Java’s enums – you create a fixed set of instances of private derived classes, and expose those via the public base class.
You can prevent *other* code from subclassing by giving the public class a private constructor (and no other constructors). That way the *only* derived classes can be the nested ones.
(And of course Eric’s code has a private constructor, presumably for this reason. It’s easy to miss that out, but it’s a really important part of the pattern.)
While a good principle in general, making the constructor private is less important in this case, because in this case there’s no public method on the abstract class that takes an ImmutableStack, so even if you created your own class derived from ImmutableStack you couldn’t “inject” it.
Does this pattern have a name?
It’s a variation of the factory pattern.
Unless you can override `Finalize` with a sealed method–something C# won’t allow (and which would be ugly in any case), I don’t think there’s any way to prevent an evil class from inheriting from an unsealed concrete class, defining two constructors which chain to each other while passing a parameter whose evaluation will throw an exception, and overriding `Finalize` to resurrect the object whose construction failed.
It is possible to protect an abstract class from outside inheritance with a technique I think I first saw from you, i.e. including an internal abstract method. Whereas a callable base constructor is only needed if one wishes to “properly” construct an object instance, one can’t even *define* a derived type–must less create any instances–without overriding all abstract methods. I don’t know any way to use this trick with concrete types, but I think it might be usable here.
That’s correct, and it is an unfortunate flaw in the design of .NET. I’ve been meaning to blog about this for some time; thanks for the reminder.
I look forward to it. I often find myself thinking that what’s really “needed” is a means by which a class can separate their “public-facing”, “parent-facing”, and “descendant-facing” faces. The question of who should be allowed to use one of Foo’s constructor to make an instance of Foo should be separate from the question of who should be allowed to use it to construct derived-class instances. Likewise the fact that a class overrides a public method does not mean that the override should be usable by derived-class instances.
In most cases, if a class overrides base method Foo(), it would be proper for the class to expose Foo() as part of its public face, and allow derived classes to use the inherited method without having to override it themselves. In the case of something like your Pop() method, however, there’s really no reason it should be exposed as a member of EmptyStack. If ImmutableStack were an interface, then EmptyStack could implement ImmutableStack.Pop without having to include Pop in its public face. Conceptually, it would seem like such usage should be no less reasonable when overriding an abstract method.
@John Payson
Properly considered, the public/private boundary is completely orthogonal to parent/child class relationships. I’m glad to see that some modern languages such as Nimrod and Ceylon (http://ceylon-lang.org/documentation/faq/language-design/#no_protected_modifier) recognize this.
Oh good heavens. I hadn’t thought of that. I’ll race Eric to blog about it – though no doubt in a less thoughtful way 😉 It’s a shame that the internal abstract method approach won’t work inside the same assembly… really, you want a private abstract method, but that’s not allowed (even though it does just about make sense).
Why wouldn’t a private abstract method make sense, given that it would be accessible to, and could be overridden by, nested classes?
(I can’t reply to supercat’s message, presumably due to a nesting limit.)
It *does* make sense – but only in this very limited situation. That’s my point – it would be useful, but the language disallows it.
When you said “just about [makes sense]” I interpreted that as “doesn’t quite”. There are a number of places where C# seems to go out of its way to disallow things which would be legal in CIL because the implementers of C# didn’t see a particular usage case; an example you’ve written about IIRC about is the rule against using `System.Enum` as a generic constraint. It would be interesting to know which inheritance-related rules are imposed by the Runtime, and C# enforces them because failure to do so would yield types that can’t be loaded, or would otherwise be broken, and which rules are imposed purely by the C# compiler and, if waived, would result in code that worked exactly as normal semantics would suggest that it should.but for the existence of the rule.
Trying to use language features to prevent “evil” classes is misdirected effort resulting in a false sense of security. Access restrictions are a tool for detecting encapsulation errors, nothing more.
Nothing is cast … they’re derived classes. I can’t see anything mindblowing … the derived classes are simply made private and stuck inside the base class because there’s no need to instantiate them elsewhere and they’re simply implementation details.
I really like your abstract base class with private constructor. I see the parallels with functional programming data types. Except one thing stands out to me as different: in functional programming the type cases are normally publicly accessible, and can be used for pattern matching (I guess the C# equivalent would be something like `if (mystack is EmptyStack)`). I understand making the derived classes private (and instead exposing an `IsEmpty` method) if you think of the classes as an implementation detail, but I can’t immediately see the advantage of calling them implementation details and not public surface area. Would you mind sharing your thoughts about how you decided to do it this way?
Good question. On the one hand I agree that in languages with pattern matching it can be nice to do matching as you describe. On the other hand, doing so then limits the ability of the author of the class to change the implementation details while preserving the abstract data type. Suppose for performance reasons I decided to use bit twiddling on an int to represent my stack of bits instead of a linked list as I am doing here. Code which depends on the implementation details is then broken; code which depends only on the public surface area is not.
A linked list exposes its node types. A stack implemented as a linked list should not. This is true in functional programming too. There is absolutely no reason do pattern matching on the nodes of a stack (unless you’re the implementer).
The nested classes remind me of what we called “variant records” in a programming language class I once took. In C-speak, a variant record is a union of structs. That is, you have one container-like union that can take the form of different struct types. Actually, we used Scheme with some custom data structure libraries, but the effect was the same.
They’re pretty directly parallel, which is pretty satisfying to me. I’m almost sad that I didn’t think to use a more functional-style approach in my previous solution!
It also reflects a very interesting OOP concept: the type of an object is useful for more than just polymorphism, because the type itself is meaningful independently of its members. I’m not sure I can quite put my wonder into words; it’s just a very intriguing idea to me.
Indeed, it is possible to use variant records — often also called “discriminated unions” — as an implementation detail of functional languages to obtain this effect.
Doesnt the emptystack violate Liskov substitution Principle?
But yea, i dont know, since its private and you are the only user of it…but still I would like expert’s opinion 🙂
Thank you
Suppose I have a base class Integer, and a derived class ColoredInteger. It has all the magnitude of an integer, but also tracks its color, whatever that is. The LSP suggests that I ought to be able to use a blue ColoredInteger in any context in which an Integer is required without changing the correctness of the program. So does that mean that if the program creates an Integer of value 123, I should be able to change the program to instead create a blue ColoredInteger of value 456 without changing the meaning of the program? I cannot imagine that this is what Liskov had in mind when she proposed her principle. You can substitute an empty stack for any context that takes *any stack*, but you can’t substitute an empty stack *for any particular stack*.
Here’s another way to look at it: the LSP can be stated as “if a theorem can be proved about objects of base type B then the theorem should be provable about objects of derived type D”. If you believe that the LSP has been violated then please prove a theorem about objects of type ImmutableStack that cannot be proved about objects of type EmptyStack.
I can prove the following theorems about ImmutableStack: (1) you can always push on any stack, (2) if IsEmpty is false then you can always pop, (3) if IsEmpty is true then popping an empty stack throws, (4) Suppose pushing item X onto immutable stack Y produces immutable stack Z. Z is not empty, the top of Z is X and popping Z produces Y. I could go on stating theorems all day. All those theorems can be proven about both the derived classes. So why would either be a violation of the LSP?
In code that you have you are of course right.
But let’s say I have method that takes ImmutableStack. It promises to work correctly with instances of that type. But thanks to parameter contravariance you can pass into it instances of EmpyStack, which would throw once the method tries to do something. So what’s the solution ? Do you test inside method if you have correct instance of this or that and then do logic based on that ? Doesn’t that break the whole concept of polymorphism? The instance of EmptyStack doesn’t deliver what it promises…
I know we can try/catch and all…but according to wikipedia:
– No new exceptions should be thrown by methods of the subtype, except where those exceptions are themselves subtypes of exceptions thrown by the methods of the supertype.
Let’s say you have no control over what comes into your method call, and if there were 5 subtypes, each with own exception, you would have to know internals of them and think of it…
I understand, that in your piece of code, there is no violation, but to me, this instantly popped into my mind…what if…? I am trying to understand it all, so thank you for this article and for reply.
I may be wrong, but don’t believe it’s a form of contravariance if a function accepts a parameter of type `ImmutableStack` and is given an argument of type `EmptyStack`. I would just call that “polymorphism” (or “subtype polymorphism”). The contravariance would come into play when you consider the type of the function itself, for example a value of type `Action` can be assigned to a variable of type `Action`.
But regarding substitution, if a function accepts a parameter of type `ImmutableStack` then nothing is violated by giving it an `EmptyStack`. The implicit contract of any `ImmutableStack` is that it can only be “popped” if `IsEmpty` returns false. The `EmptyStack` fulfills this perfectly because it returns true for `IsEmpty` and so can do whatever it wants when it’s popped – because the caller was never meant to call pop on it in the first place. It’s helpful to not have it do “whatever it wants” but instead throw a helpful exception to say “you aren’t supposed to pop *any* ImmutableStack that claims to be empty – no matter how it’s implemented”.
To put it another way, it’s a property of any `ImmutableStack` that it can be popped if it returns false for `IsEmpty`. Both `EmptyStack` and `NonEmptyStack` fullfil this property (and the other 2 properties Eric mentioned) and so they can be substituted safely wherever an `ImmutableStack` is required. I believe this is what Eric was saying in the previous comment, and so LSP is upheld this case.
Your scenario contradicts itself. The method cannot *both* “promise to work correctly with instances of that type” and throw when the method tries to pop an empty stack. The contract of the ImmutableStack is “thou shalt not pop an empty stack”, and the method violates that. The contract of the ImmutableStack is “I will throw if you pop an empty stack”, and EmptyStack fulfills that contract. There’s no violation.
“which would throw once the method tries to do something”
Only if you did something that violated the semantics of ImmutableStack, which says that you can’t pop an empty stack.
“No new exceptions should be thrown by methods of the subtype, except where those exceptions are themselves subtypes of exceptions thrown by the methods of the supertype.”
And these exceptions ARE thrown by the methods of UmmutableStack, under the exact same circumstances … an empty stack.
I think your intuitions are not well formed. It *should* be intuitively obvious that an EmptyStack is simply an ImmutableStack that is empty, and that it has exactly the same semantics.
“But thanks to parameter contravariance you can pass into it instances of EmpyStack”
No, that has nothing to do with contravariance. Contravariance applies to type parameters, such as the T in ImmutableStack. If a method can return an ImmutableStack, then an override that returns an ImmutableStack would be contravariant.
Arggh! How can a C# guy have a blog where < (less-than) and >( greater-than) are eaten in comments? And there’s no preview and no other help for commenters? Hopefully this will work but I won’t try again if it doesn’t:
Contravariance applies to type parameters, such as the T in ImmutableStack<T>. If a method can return an ImmutableStack<object>, then an override that returns an ImmutableStack<string> would be contravariant.
[Sorry to come so late to the party. I’m bingereading 3 years of fabulousness.]
I think your comment was on the right track but not exact. IIRC, contravariance applies to type parameters, as you say, but it involves the substitution of _less_ derived types. So suppose ImmutableStack had a method
static void NoOp(ImmutableStack < T > source){ }0
Then this is legal b/c Action < > is contravariant:
Action < EmptyStack > actor = NoOp;
It’s safe because actor will only ever invoke with an EmptyStack, and every EmptyStack is an ImmutableStack < T >.
“If a method can return an ImmutableStack…”
Return types are the province of covariance, not contravariance. Covariant methods can have more-derived return types, so a covariant override of your method could specify that it will return only EmptyStack. (Er, well, it could if your method were an interface, but that’s even farther into the weeds.)
My mnemonic: “co” rhymes with O for “out” and with “low” for more-derived [I think of base classes as higher, as in “high-level abstraction”, though I know some people think the opposite]; “contra” is its opposite.
It took me some time to figure out how to create and use one of these things:
ImmutableStack stack = ImmutableStack.Empty;
As opposed to:
ImmutableStack stack = new ImmutableStack();
Which of course doesn’t compile. If I had seen this thing in the wild, I would have balked at that bug-a-boo.
That’s a good point. Though it is a nice property that an empty immutable stack is a singleton; they’re all the same, so why bother ever making more than one?
Are you saying that your first stack should be created with ImmutableStack.Empty.Push()? How does one obtain an initial stack otherwise?
“How does one obtain an initial stack otherwise?”
That’s a good question. How does one create a stack without putting objects on that stack? Of course, if you already have a stack, you can use some or all of that. I suppose you could write a convenience method that accepts an IEnumerable and pushes them all onto a stack, but that’s not really something the stack needs to worry about.
If one wishes to have a variable that behaves as a mutable stack of Thing [the normal scenario] one would start by saying: ImmutableStack<Thing:> myStack = ImmutableStack<Thing:>.Empty; and would push each thing onto it via myStack=myStack.Push(newThing); without having to worry about whether the stack was empty or not.
Note that the whole idea being ImmutableStack is that references to it can be stored in mutable variables, and those variables themselves will then behave as mutable stacks. Copying a variable will effectively copy the state of the stack encapsulated thereby to a another variable which would behave as an independent mutable stack, whereas copying a variable of a MutableStack type would merely create another “live view” of the same stack. It might perhaps help to think of the type as really being “ImmutableStackState”.
No, your first stack is obtained with ImmutableStack.Empty. An empty stack is a stack.
“Are you saying that your first stack should be created with ImmutableStack.Empty.Push()? How does one obtain an initial stack otherwise?”
Of course not … Push() takes an argument. You already got it right:
ImmutableStack stack = ImmutableStack.Empty;
As for
ImmutableStack stack = new ImmutableStack();
the availability of new is part of a class’s contract. I actually think that publicly exposing new is a bad idea, as it’s an implementation detail that can’t be later changed. All construction should be through factories, and that’s how it works in some well-designed languages.
Haskell called. It wants you to stop beating around the bush, and propose already. 🙂
Shouldn’t a pop operation return the head (a single element) instead of the tail, according to “standard” stack semantics? Is there a way to build an immutable stack which complies with this (perhaps an out parameter)?
Yuck. There are logically two operations: look at the top of a stack, and produce a popped stack. I see no reason why those ought to be combined into one operation.
I agree they shouldn’t be combined into a single method, but the other point stands. The Pop operation normally returns T, not a collection of T. It’s not that it’s incorrect to do so, but just it goes against the general usage of a stack. I’m sure you’re solution will be complete and concise, but this is definitely an unusual implementation of Pop().
The usual stack has a Pop function that returns the top element and modifies the stack it’s called on. Since this is an immutable stack, the stack it’s called on cannot be modified. It would be possible to create a T Pop(out ImmutableStack s) function that simultaneously returns the top element and the resulting stack, but I’m not at all convinced that it would be a better adaptation to an immutable stack than having separate methods.
I just think the Pop method should have a different name. Top in this case is equivalent to Peek, but Pop is not equivalent to Stack.Pop. I think Pop should be called something else. GetTail() but that’s not a great name either.
@briantobin
A naming convention I’ve seen, that I quite like, is to use past-tense for operations that return a new instance rather than mutating an existing one. For example, if I see the code `myList.Append(x)` I would assume that `myList` is mutated, but if I see `myList.AppendedTo(x)` I would assume that `myList` is not mutated and that the result is a new list with x at the end of it. If that convention were used here, then the method would be called “Popped”. The word “pop” could be seen as an imperative command, as in “[You must] pop [now]!”, but the word “popped” could be seen as an *adjective*, as in “[the] popped [stack]” (I think the term may be “deverbal adjective”). In other words, they *describe* the result (in terms of the subject) rather than dictating an action.
Another example that comes to mind is Python’s “sort” command, which sorts a list by mutating it, vs its “sorted” function, which returns a “sorted list” based on the original list.
In the case of an immutable stack there is no ambiguity, so calling it “pop” seems fine, but it may illuminate some confusion if it were named in the imperative form.
@coder-mike
Ooh, I rather like that naming convention! I think I’ll adopt it.
Think of it this way, in a mutable stack the Pop() method will mutate the stack to be the equivalent of the tail. So it makes sense that the Pop() method of the immutable stack should return the tail.
Why does the Pop operation normally return the element on top? It’s because the stack itself mutates to be “popped”; instead of returning void, it’s much more C-style (stuff as much into one line as possible) to return something. The purpose of Pop is not to return an element; Peek/Top already does that! The purpose of Pop is to remove an item from the top of the stack. The only way the user can get to the resulting stack is to return it. In other words, the popped stack is truly the result of the pop operation, and should be the return value.
” I’m sure you’re solution will be complete and concise, but this is definitely an unusual implementation of Pop().”
It’s not at all an unusual implementation of an immutable stack … it’s the usual way.
Functional programming and its idioms have been around since at least 1958 … it’s about time that the programming population at large became familiar with them and didn’t think of them as “unusual”.
Push and Pop methods which took a storage location of type ImmutableStack as a ref parameter could be written to provide lock-free thread-safety when used simultaneously by any number of “pushing” threads and one “popping” thread, but for Pop to be thread-safe in the presence of other threads pushing, it must in one operation update the stack reference and return either the old reference or the item contained therein. Having to use static members and pass `ref` parameters is a bit syntactically ugly (I wish there were a syntax which would allow something like myStack.:Pop() to be shorthand for ImmutableStack.Pop(ref myStack); the use of “.:” rather than “.” should serve as an adequate clue that the method is acting upon the *reference* itself, rather than upon the object identified thereby.)
Immutable containers are thread-safe … that’s one of the big motivators for them. If you want to act on a stack in multiple threads, put the stack behind a thread-safe accessor.
” Is there a way to build an immutable stack which complies with this (perhaps an out parameter)?”
What a horrid idea, just to try to get an immutable stack to return what a mutable stack typically does. How could you possibly prefer
ImmutableStack<Thing> tempStack;
var thing = stack.Pop(out tempStack);
stack = tempStack;
over
var thing = stack.Top();
stack = stack.Pop();
?
I didn’t say I preferred it. I just wanted to see what other people thought about Pop; and got a couple of nice answers.
You asked “Is there a way to build an immutable stack which complies with this (perhaps an out parameter)?” … My question is, why would you *want* that, given how horrid the interface is? If is of course possible … how could it not be?
And as for “nice answers” … Eric said “Yuck” but I bothered to show you just how awful the usage would be.
Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1718
Pingback: Dew Drop – October 17, 2014 (#1879) | Morning Dew
Would it simplify or complicate matters if popping an EmptyStack (without checking .IsEmpty) returned the same instance of EmptyStack rather than throwing an exception? Likewise, calling EmptyStack.Top could return Default(T)?
My hunch is that while it would remove the implicit contract that you cannot pop an EmptyStack, it would only lead to sloppy recursion code that could open the door to a stack overflow in the case of Pop, and a potential Null Reference exception in the case of Top. The exceptions as they are would properly inform the developer that they’re not using the class in the way it was designed to be used, but I’m curious if you had other reasons to throw those exceptions (such as a design principle).
If you had to walk up to some programmer and ask them what it means to pop a stack, most people might say something like “removes the top item off the stack”, rather than “removes the top item off a stack, unless it’s empty – then no item would be removed”. If you had to further inquire, “What about when the stack is empty?” they might say something like “well then there are no items which can be removed, so it doesn’t make sense to remove the top item”. The same is true of getting the `Top` – if the stack is empty then there is no top to get, so it’s not valid to get the top of an empty stack. Getting the top of an empty stack is like getting the 5th element of a 4-element array – it’s simply not valid.
Apart from that, it just seems more helpful to the caller to “fail-fast” if they mistakenly attempt to do something stupid like removing an item from something that was already empty, since it’s best you’re alerted to the likelihood of there being a mistake in the caller’s algorithm as soon as possible rather than being left wondering where exactly that “null” value originated from somewhere else in the program.
Good question. My opinion is that good reusable code has the property that it complains early and loudly when it is misused. Popping an empty stack is simply wrong; it indicates a fundamental bug in the program. A program which pops an empty stack is arbitrarily badly broken, and the right thing to do when you find yourself in a hole is *stop digging*. A program that is so broken that it pops an empty stack is so broken that it could be doing arbitrary harm to the user, so stop the program immediately before it does something really bad.
Pingback: Producing combinations, part one | Fabulous adventures in coding
i don’t get something
when I was a CS student we learned that referencing objects is the basic of OOD, and what is the point of referencing something that can’t be changed (beyond performance)?
I do realize that changing an object state can cause unexpected results, and even if not it might point SRP violation. but we always use cloning instead of referencing (again, ignoring the performance) and then enjoy both worlds.
so my question is why to use a class if it is immutable. why not just use structs (even without immutability as every change will affect only a single instance copy).
Well, you do arithmetic, probably. What’s the point of using the number 12 if the number 12 never changes?
And cloning makes the problem worse, not better. Cloning is expensive, cloning can be deep or shallow and getting it wrong makes bugs, and cloning wastes memory. In an immutable world, cloning is just copying a reference.
The reason not to use structs is because structs cannot be recursively defined in C#.
Thanks!
Generic structs can be recursively defined, actually, but the only way to use them without boxing would be to have a method that receives a generic struct give make a method call which passes a bigger struct that contains the first. Not terribly useful.
Pingback: Producing combinations, part three | Fabulous adventures in coding
Pingback: Violating the “smart enum” pattern in C# | Jon Skeet's coding blog
Pingback: Graph traversal, part three | Fabulous adventures in coding