Implementing IEnumerable in the Data Structures

by ⋅ Leave a Comment

After finishing the series of articles about data structures (see here, here, here and here) I started to think about the GetItems method I had implemented in the Linked List and in the Tree. This method was iterating on the structure and retrieving the items as IEnumerable.

That was not what I was expecting of the class. I was expecting to replicate the .NET data structures, and they implemented IEnumerable<T>, instead of using a special method for getting the items. So I decided to implement IEnumerable<T> on the data structures.

In order to implement IEnumerable<T>, we must create two methods:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()

IEnumerator IEnumerable.GetEnumerator()
[/sourcecode]

In reality, we should create only one function:  the second one calls the first one and doesn’t need to be implemented. As the linked list already had the GetItems implemented, I only had to remove its code and add it to GetEnumerator:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()
{
    if (Count == 0)
        yield break;
    _currentItem = _top;
    while (_currentItem != null)
    {
        yield return _currentItem.Data;
        _currentItem = _currentItem.Next;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

That was simple, and caused no troubles. For the stack, I hadn’t implemented the GetItems method, so I needed to create the enumerator for it, but it was really simple, as it’s very similar to the one in the linked list:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()
{
    if (Count == 0)
        yield break;
    _currentItem = _top;
    while (_currentItem != null)
    {
        yield return _currentItem.Data;
        _currentItem = _currentItem.Next;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

When it came to add the IEnumerable in the stack implementation as a linked list, it was also easy:

[sourcecode language='csharp'  padlinenumbers='true']
public IEnumerator<T> GetEnumerator()
{
    return _linkedList.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

But then I wrote a unit test to test this feature:

[sourcecode language='csharp' ]
[TestMethod]
public void StackAddFiveItemsIterateInReverseOrder()
{
    var stack = new StackAsList<int>();
    for (int i = 0; i < 5; i++)
    {
        stack.Push(i);
    }
    var num = 4;
    foreach (var item in stack)
    {
        Assert.AreEqual(num, item);
        num--;
    }
}
[/sourcecode]

And it failed. The data was iterated in the normal order, and not in the reversed order (last pushed should be the first in the iteration). The problem was that I was inserting the data at the end and retrieving the last item. That worked fine, but it wasn’t a real stack: the items should be piled in the beginning of the list. So, the implementation should be changed:

[sourcecode language='csharp' ]
public void Push(T obj)
{
    _linkedList.InsertAt(0, obj);
}

public T Peek()
{
    if (_linkedList.Count == 0)
        throw (new InvalidOperationException("The stack is empty"));
    return _linkedList[0];
}

public T Pop()
{
    if (_linkedList.Count == 0)
        throw (new InvalidOperationException("The stack is empty"));
    var result = _linkedList[0];
    _linkedList.RemoveAt(0);
    return result;
}
[/sourcecode]

With these changes, the test passed. The code of GetEnumerator for the queue is the same as for the stack:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()
{
    if (Count == 0)
        yield break;
    _currentItem = _top;
    while (_currentItem != null)
    {
        yield return _currentItem.Data;
        _currentItem = _currentItem.Next;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

For the tree, implementing IEnumerable was also easy, as we already had the GetItems method:

[sourcecode language='csharp' ]
public IEnumerator<T> GetEnumerator()
{
    if (_root == null)
        yield break;
    foreach (var data in VisitNode(_root))
        yield return data;
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
[/sourcecode]

That way, we have implemented IEnumerable in all data structures we’ve developed. The source code for the data structures is in https://github.com/bsonnino/DataStructures