As a developers, sometimes our end user is going to be other developers. When this happens, it's prudent for us to use all the tools available to us to protect our users from encountering an error when calling our code. Ideally, the user should not experience an exception. What follows is an example of this idea taken to it's full potential, an easy to use, and 100% exception free Stack.
What do I mean by exception free? Not only will the object never throw an exception, but it will not allow you to try and remove an item from top of it when none exists. This is due to not only it's design, but also that the stack is itself, an extremly simple data type (we will see in a later post how much harder this is with the Stack's opposite, a Queue)
The Status Quo
First, let's look at the promises made by the System.Collections.Generic.Stack<T>, specifically the Pop() method
Returns
T
The object removed from the top of the Stack<T>
Exceptions
InvalidOperationException The Stack<T> is empty.
This object places the burden on the client code to check whether or not the stack has items in it, in order to ensure that they do not experience an exception. Of course, no stack can Pop() an item which does not exist, but is it possible to do better than a runtime exception? We could return null, but can we do better yet still? As it so happens, we can.
The method does not exist
If the stack is empty, the method (Pop()) does not exist. Let's see how we can achieve this with an abstract base class, and two inherited sub classes
public abstract class Stack<Data> { }
public class EmptyStack<Data> : Stack<Data>
{
internal EmptyStack() { }
}
public class NonEmptyStack<T>
{
public Top Data { get; }
private readonly Stack _rest;
internal NonEmptyStack(Data top, Stack rest)
{
Top = top;
_rest = rest;
}
public Stack Pop() => _rest;
}
First, let's note that this Stack is immutable. Which is to say that when you Pop() you are not removing the top item from this stack, but rather getting back a stack that has all the items except for the top of this one.
This is how we achieve an exception free Top and Pop(), we hide the method behind a type which is guaranteed to have at least one item, and therefore can return the Top, and execute a Pop() without exception.
We only need to add a little bit more code to complete this Stack, namely the Push() method, since currently there is no way of getting data into the Stack. Let's do that now.
public abstract class Stack<Data>
{
public static readonly Stack<Data> Empty = new EmptyStack<Data>();
public Stack<Data> Push(Data data) => new NonEmptyStack(data, rest: this);
}
public class EmptyStack<Data> : Stack<Data>
{
internal EmptyStack() { }
}
public class NonEmptyStack<T>
{
public Top Data { get; }
private readonly Stack _rest;
internal NonEmptyStack(Data top, Stack rest)
{
Top = top;
_rest = rest;
}
public Stack Pop() => _rest;
}
As before our Push() method respects the fact that our stack is immutable. It returns a new Stack, which has all the items before, except with the new data as the Top of the Stack
Putting it to work
Let's use this stack to execute a simple string reverse. We try to pattern match the abstract Stack to the concrete NonEmptyStack and as long as we can successfully do so, we add the Top character to the reversed string. We then execute a Pop() and assign the returned Stack to our stack variable so as to move toward the EmptyStack, which will break the loop.
string hello = "Hello World";
Stack<char> stack = Stack<char>.Empty;
string olleh = string.Empty;
foreach(char c in hello)
{
stack = stack.Push(c);
}
while(stack is NonEmptyStack<char> nonEmpty)
{
olleh += nonEmpty.Top;
stack = nonEmpty.Pop();
}
Console.WriteLine(olleh)
Conclusion
By taking advantage of immutability, a small amount of inheritance, and pattern matching, we've designed a type that will catch any attempt to read an empty stack not in Prod, QA or even in automated tests, but at the time of compilation.