The Untouchables (part III) – Adding iterators to our immutable stack

Joacim Andersson — Mon, 07 Sep 2009 13:39:00 GMT

Introduction

In my last post I showed you a VB translation of Eric Lippert’s immutable stack class. There was however one thing that was lost in translation. In Eric’s original code he made the class enumerable (added support for a For Each loop). Because C# has support for iterators with its yield keyword, that was very easy to do… in C#. VB currently doesn’t have this feature so to add the same support we need to implement both the IEnumerable(Of T) and the IEnumerator(Of T), which in turn requires the implementation of the non-generic IEnumarable and IEnumerator and also the IDisposable interfaces.

The Interfaces

As you can see from the above image, that is 7 members that we have to implement. That might sound like a lot, but fortunately it’s mainly boiler-plate code. Firstly, the Reset() method of the IEnumerator interface is rarely used and in our case we will simply throw an NotImplementedException in that method. Secondly, we will end up with two GetEnumerator() methods and two Current() properties. But in our case we will simply make the non-generic versions of these members private and call the generic versions from them. Thirdly, in our case we will not change the code that the designer adds to the Dispose() method of the IDisposable interface, except for one little detail. The designer will mark the Dispose() method as Overridable, but since our Stack() class is sealed (NotInheritable) we only need to remove that keyword.

That leaves us with only 3 members to which we need to add our logic, the IEnumarable(Of T).GetEnumerator() method, the IEnumerator(Of T).Current() property, and the IEnumerator.MoveNext() method.

The implementation

To add support for all of this we first have to make a change to our IStack(Of T) interface.

Public Interface IStack(Of T)
  Inherits IEnumerable(Of T), IEnumerator(Of T)


  Function Push(ByVal value As T) As IStack(Of T)
  Function Pop() As IStack(Of T)
  Function Peek() As T
  ReadOnly Property IsEmpty() As Boolean
End Interface

If you add this to your existing code, you will get the following in our class implementation:

To fix that simply put the text caret at the end of the Implements line and press the enter key. That will allow the designer to add the empty method and property procedures that we need to implement.

Since there will be two Current() properties and two GetEnumerator() methods, I simply rename the non-generic versions of these and make them private. From them we simply call the generic versions. In the Reset() method we simply throw an NotImplementedException.

Private Function IEnumerator_GetEnumerator() As System.Collections.IEnumerator _
    Implements System.Collections.IEnumerable.GetEnumerator
  Return GetEnumerator()
End Function

Private ReadOnly Property IEnumerator_Current() As Object _
    Implements System.Collections.IEnumerator.Current
  Get
    Return Current
  End Get
End Property

Public Sub Reset() Implements System.Collections.IEnumerator.Reset
  Throw New NotImplementedException()
End Sub

The important members to implement is the GetEnumertor() and the MoveNext() methods plus the Current() read-only property. In a regular class that implements these interfaces we would simply return Me in the GetEnumertor() method. However since our stack is immutable we can’t do that since we don’t change the current instance when we Pop a value from the stack. So instead we add a private instance of the object that we will change when needed. We also need a private field to hold the current value.

Private _enumerator As IStack(Of T) = Me
Private _currentValue As T

As you can see we initialize the _enumertor to be a reference to the current object, Me. This is what we return from the GetEnumerator() method.

Public Function GetEnumerator() As  _
    System.Collections.Generic.IEnumerator(Of T) _
    Implements System.Collections.Generic.IEnumerable(Of T).GetEnumerator
  Return _enumerator
End Function

In the MoveNext() method we are supposed to return a boolean value if we can move to the next object. In our case we simply need to check our IsEmpty() property, if that is false then we can return another item. We also set the _currentValue field to the current value and Pop it from the stack.

Public Function MoveNext() As Boolean _
    Implements System.Collections.IEnumerator.MoveNext
  If Not _enumerator.IsEmpty Then
    _currentValue = _enumerator.Peek()
    _enumerator = _enumerator.Pop()
    Return True
  Else
    Return False
  End If
End Function

In the Current() property we simply return the _currentValue field that was set in the previous method.

Public ReadOnly Property Current() As T _
    Implements System.Collections.Generic.IEnumerator(Of T).Current
  Get
    Return _currentValue
  End Get
End Property

That’s pretty much it. We can now iterate throw our Stack using code similar to this:

Public Sub Main()
  Dim myStack As IStack(Of String) = Stack(Of String).Empty
  'init the stack
  For i As Integer = 0 To 25
    myStack = myStack.Push(ChrW(Asc("A") + i).ToString)
  Next
  'Use a For Each loop on the stack
  'Note, since a stack is last in-first out,
  'the alphabet will be written in reversed order here
  For Each s As String In myStack
    Console.Write(s)
  Next
End Sub

Conclusion

As you’ve seen, since VB currently doesn’t support iterators in the same manner as C# does, we need to add a lot more code to our class to support it. Most of it are boiler-plate code though so it’s not as hard as it might look at a first glance. If you’re interested in learning more about how to use iterators in VB I highly recommend that you read this Visual Studio Magazine article written by Bill McCarthy.

You can download the code for this article here.

Have fun!

Joacim's view on stuff : IEnumerable, visual basic

The Untouchables (part III) – Adding iterators to our immutable stack