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