IEnumerable is an interface that allows us to iterate over a collection; it does so by exposing  a single GetEnumerator() method, which in turn returns an IEnumerator: a simple interface that provides methods to access the current element in the collection, move to the next item, and reset back to the beginning of the collection.

Why do we need IEnumerable

Let´s see a simple example to understand why we may want to implement IEnumerable.  Take this Stack implementation – you can check here this post on how to implement a Stack in C# – and see if you notice some functionality lacking:

public class BasicStack
    {
        private T[] arrayData;
        private const int defaultSize = 30;
        private int index;

        public BasicStack() {/*implementation*/}
        public T Pop() {/*implementation*/}
        public T Peek(){/*implementation*/}
        public void Push(T obj){/*implementation*/}

We can add, and remove elements to/from the stack, and we can peek the element at the top, but what if we wanted to iterate over all the elements of the stack? How could we do that? Well, only in a very ugly manner: with a while loop, and surrounding the code with a try/catch to iterate till we run into an exception when trying to do a pop on an empty stack. Yes, yucks.

If we want to iterate the stack in a sane manner, we need to improve our BasickStack class implementation. We could do that by adding functions that check if the Stack is empty, or by exposing the number of elements. But if we implement the IEnumerable interface, we will be able to use a foreach like this:

 foreach (var item in myBasicStack)
    {
      doSomething();
    }

Brief, when implementing a custom Data Structure we can implement the IEnumerable interface to add iteration functionality.

Implementing IEnumerable

We implement the IEnumerable interface:

public class BasicStack:IEnumerable
{
        private T[] arrayData;
        private const int defaultSize = 30;
        private int index;

        public BasicStack() {/*implementation*/}
        public T Pop() {/*implementation*/}
        public T Peek(){/*implementation*/}
        public void Push(T obj){/*implementation*/}

        public IEnumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }
}

When adding the interface we see we need to implement two methods that return an IEnumerator:

  • IEnumerator GetEnumerator()
  • IEnumerator IEnumerable.GetEnumerator()

Since our stack implementation uses generics, we want to implement IEnumerable. But IEnumerable extends from IEnumerable. Therefore we have methods for both the generic, and non generic enumerator.

Implementing IEnumerator

Having implemented IEnumerable, we need now to move on to implementing our Enumerator.

public class Enumerator : IEnumerator
        {
            public T Current => throw new NotImplementedException();

            object IEnumerator.Current => throw new NotImplementedException();

            public void Dispose()
            {
                throw new NotImplementedException();
            }

            public bool MoveNext()
            {
                throw new NotImplementedException();
            }

            public void Reset()
            {
                throw new NotImplementedException();
            }
        }

IEnumerator extends from IEnumerator, and IDisposable so we have to implement all the methods of those interfaces:

  • IEnumerator: Reset, MoveNext, object IEnumerator.Current
  • IEnumerator: Current
  • IDisposable: Dispose

Let´s start by implementing the the constructor: we need the stack, and an index to point to the last element of the stack:

public class Enumerator : IEnumerator
        {
            private BasicStack _stack;
            private int _index;

            internal Enumerator(BasicStack stack)
            {

                _stack = stack;
                _index = stack.index;
            }
        }

As we have not started to iterate our index is pointing just beyond the last element of the stack, ready to position to the first element to iterate.

When we want to reset the enumerator, we have to set the enumerator to its initial position: once again, this is before the first element of the collection.

public void Reset()
            {
                _index = _stack.index;
            }

Next we have to implement the MoveNext function: according the IEnumerator specification it must advance the enumerator to the next element of the collection, and returns true when it succeeds, and false if it moves beyond the end of the collection:

public bool MoveNext()
            {
                _index = _index - 1;
                // End of enumeration.
                if (_index < 0)
                {
                    return false;
                }
                else
                    return true;
            }

Getting the current element of the collection it is as simple as returning the element of the stack array at the current enumerator _index:

            public T Current
            {
                get
                {
                    if (_index < 0) throw new InvalidOperationException("Enumerator Ended");

                    return _stack.arrayData[_index];
                }
            }

            object IEnumerator.Current {
                get
                {
                    if (_index < 0) throw new InvalidOperationException("Enumerator Ended");
                    return _stack.arrayData[_index];
                }
            }

And if the user calls on dispose in our enumerator, we will position the index at a negative position to terminate the iteration:

public void Dispose()
{
_index = -1;
}

The collection was modified after the enumerator was created

We are almost there, but not quite yet. According to the IEnumerator especification, Reset and MoveNext must throw an InvalidOperationException if the collection is modified after the Enumerator has been created:

        // Summary:
        //     Sets the enumerator to its initial position, which is before the first element
        //     in the collection.
        //
        // Exceptions:
        //   T:System.InvalidOperationException:
        //     The collection was modified after the enumerator was created.
        void Reset();

So the enumerator needs to know if the collection has been modified, so that it can throw an InvalidOperationException when necessary. We can achieve that easily enough, if we add a property version to our stack implementation. Every time the collection changes we will increase the version. Also we will add a property _version to the Enumerator too: we will initialise it to the version value of the stack. And when calling MoveNext, and Reset we will check that both version properties are in sync; if that´s not the case we will know that the collection has been modified since the creation of the Enumerator.

When we put it all together, our stack class that implements the IEnumerable interface looks like this:

namespace CustomDataStructure
{
    public class BasicStack<T>:IEnumerable<T>
    {
        private T[] arrayData;
        private int version;
        private const int defaultSize = 2;
        private int index;

        public BasicStack()
        {
            arrayData = new T[defaultSize];
            index = 0;
            version = 0;
        }

        public BasicStack(int size)
        {
            if (size < 0)
                throw new ArgumentOutOfRangeException("size", "Size must be a positive number");

            arrayData = new T[size];
            index = 0;
            version = 0;
        }

        public T Pop()
        {
            if (index == 0)
                throw new InvalidOperationException("Exception: Empty stack");

            version++;
            return arrayData[--index];

        }

        public T Peek()
        {
            if (index == 0)
                throw new InvalidOperationException("Exception: Empty stack");

            return arrayData[index - 1];

        }

        public void Push(T obj)
        {
            if (index == arrayData.Length)
            {
                T[] newArray = new T[2 * arrayData.Length];
                Array.Copy(arrayData, 0, newArray, 0, index);
                arrayData = newArray;
            }
            arrayData[index] = obj;
            version++;
            index++;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        public class Enumerator : IEnumerator<T>
        {
            private BasicStack _stack;
            private int _index;
            private int _version;
            internal Enumerator(BasicStack stack)
            {

                _stack = stack;
                _index = stack.index;
                _version = stack.version;
            }

            public T Current
            {
                get
                {
                    if (_index < 0) throw new InvalidOperationException("Enumerator Ended");

                    return _stack.arrayData[_index];
                }
            }

            object IEnumerator.Current {
                get
                {
                    if (_index < 0) throw new InvalidOperationException("Enumerator Ended");
                    return _stack.arrayData[_index];
                }
            }

            public void Dispose()
            {
                _index = -1;
            }

            public bool MoveNext()
            {
                if (_version != _stack.version) throw new InvalidOperationException("Collection modified");
                _index = _index - 1;
                // End of enumeration.
                if (_index < 0)
                {
                    return false;
                }
                else
                    return true;
            }

            public void Reset()
            {
                if (_version != _stack.version) new InvalidOperationException("Collection modified");
                _index = _stack.index;
            }
        }
    }

}

Advertisements