Implementing a bidirectional enumerator in C#

Question

Is there a way to use yield blocks to implement an IEnumerator<T> which can go backward (MoveLast()) as well as forward?

Bornie

I would expect a function named "MoveLast()" to move to the very end of the enumerator. I think you want something more like "MovePrev()" – Spilt

Also, you're gonna have to implement your own enumerator. Not that hard, imho. – Lymphosarcoma

Answer 1

Not directly from the iterator block, no.

However, the caller can always buffer the results, for example into a List<T>, or just call Reverse() - but this doesn't always apply.

Macri

Yes, that's the obvious solution. I was hoping there was an alternative I was missing. – Bornie

@alexey_r - not much else you can do, though - for all the reasons that Jon gives. – Macri

Answer 2

No, the state machine generated by the C# compiler is strictly forward.

It doesn't even make sense to go backwards in many cases. Imagine an iterator reading from a network stream - to go backwards, it would have to remember everything that it had ever read, because it couldn't rewind time and ask the network for the data again.

(Ditto anything that generated data in some lossy way. Imagine an iterator which returned a new board for Conway's Life on each iteration - there are multiple boards which could all have been the previous one, so to go backwards you again have to remember what you've already returned.)

Friedrick

Obviously in many cases it doesn't make sense, yes. It's just a pity that we don't get any help when it does. – Bornie

Well we don't have any language support for iterating backwards either. I have to say, I can't remember the last time I needed to do it. Do you find yourself regularly in such a situation? – Friedrick

Well, C++ has not only bidirectional, but also random access iterators. Tons of algorithms can benefit a lot from these extra access modes. I understand that language machinery only really needs forward iterators (IEnumerator) but it would be nice if we had IBidirectionalEnumerator inheriting from IEnumerator with MovePrevious() and IRandomAccessEnumerator inheriting from it with MoveTo(index) method. We could then pass these to collection agnostic algorithms that need a collection + position in it. – Astolat

@ZarShardan: I suspect "iterator" in this case has a different meaning in C# and C++. In C#, an iterator is a method or property implemented with an iterator block, i.e. something with yield return statements etc. How would you propose running that backwards? – Friedrick

@JonSkeet Yes, that's exactly my point. As far as I understand IEnumerator's main purpose is to support the foreach/yield return machinery. Whereas C++ iterators are mainly there to serve as a container agnostic collection access modes. C# does not seem to have such facility, but it is very useful hence all these questions from C++/C# devs that keep popping up. But this shouldn't be difficult to implement by devs themselves as a small utility library. – Astolat

@ZarShardan: But the question isn't about IEnumerator so much as C# iterators - generators in other languages. Even if .NET had IBidirectionalEnumerator how would you expect that to work with iterators? – Friedrick

@JonSkeet Not sure if I understand your question correctly. If IBidirectionalEnumerator implements IEnumerator you should be able to use it everywhere where you need an IEnumerator. My main point is that being able to pass around this "collection handle + position" object is very useful. C++ has all 3 (sequential,bidirectional,indexed) and uses them everywhere with great success. C# only has the forward one (for example IEnumerator instance). – Astolat

@ZarShardan: I think you've still missed the point of the question. It's not about the interfaces provided by the framework. It's about the language feature of iterator blocks - methods using yield return to implement sequences. If I write a method that generates the Fibonacci sequence using yield return, how would you expect that to run backwards at some point, unless you buffered all previous output? – Friedrick

@JonSkeet of course not all sources support bidirectional or random access. And it is perfectly understood that language features such as foreach loop and yield return (which we all love and use) - can only implement one mode of iteration and the most obvious and natural choice is sequential forward iteration. All I'm saying is it would be nice to have a set of interfaces and classes in C# that would enable similar functionality to C++ iterators. This would require no changes to the language or even the standard library. Iterators could be returned by extension methods. – Astolat

@ZarShardan: But that's got nothing to do with this question, which is about iterators in the C# sense, i.e. yield return etc. Why add an unrelated comment to this answer, just to say you like C++ bidirectional iterators? I'm still not quite sure whether you understand how different the C++ and C# iterator concepts are. – Friedrick

@JonSkeet generators with "yield return" returns an IEnumerator, it won't, can't, and shouldn't return the hypothetical IBidirectionalEnumerator, even if the latter one exists. But how does that prevent people asking for a IBidirectionalEnumerator in C#? – Ozieozkum

@LanYi: It doesn't - but the question being asked wasn't about that interface existing. It was about what iterator blocks can do. Zar Shardan's comments are really off-topic with respect to the question asked by Alexey Romanov. – Friedrick

Answer 3

I know this thread is super old but it is relevant to note that

foreach(var item in someCollection)
{
    // Do something
}

... is get compiled into:

var enumerator = someCollection.GetEnumerator()
while (enumerator.MoveNext())
{
    var item = enumerator.Current;
    // Do something
}

So if you don't mind the "MoveNext" syntax, you could easily implement IEnumerator and add a "MovePrevious". You wouldn't be able to reverse direction if you use "foreach" but you'd be able to reverse direction if using a while loop.

Or... if you want to "foreach" a list in reverse direction (not bidirectional) you could take advantage of the yield statement.

public static IEnumerable<TItem> Get<TItem>(IList<TItem> list)
{
    if (list == null)
        yield break;

    for (int i = list.Count - 1; i > -1; i--)
        yield return list[i];
}

Or... if you want to foreach in reverse by going the long route you can implement your own IEnumerable/IEnumerator

public static class ReverseEnumerable
{
    public static IEnumerable<TItem> Get<TItem>(IList<TItem> list)
    {
        return new ReverseEnumerable<TItem>(list);
    }
}

public struct ReverseEnumerable<TItem> : IEnumerable<TItem>
{
    private readonly IList<TItem> _list;

    public ReverseEnumerable(IList<TItem> list)
    {
        this._list = list;
    }

    public IEnumerator<TItem> GetEnumerator()
    {
        if (this._list == null)
            return Enumerable.Empty<TItem>().GetEnumerator();

        return new ReverseEnumator<TItem>(this._list);
    }

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

public struct ReverseEnumator<TItem> : IEnumerator<TItem>
{
    private readonly IList<TItem> _list;
    private int _currentIndex;

    public ReverseEnumator(IList<TItem> list)
    {
        this._currentIndex = list.Count;
        this._list = list;
    }

    public bool MoveNext()
    {
        if (--this._currentIndex > -1)
            return true;

        return false;
    }

    public void Reset()
    {
        this._currentIndex = -1;
    }

    public void Dispose() { }

    public TItem Current
    {
        get
        {
            if (this._currentIndex < 0)
                return default(TItem);

            if (this._currentIndex >= this._list.Count)
                return default(TItem);

            return this._list[this._currentIndex];
        }
    }

    object IEnumerator.Current
    {
        get { return this.Current; }
    }
}

Applewhite

The question isn't asking how to iterate a sequence backward, it's asking how to get the previously yielded item. That's completely different. You can use the LINQ Reverse operator to just reverse a sequence. – Labiovelar

Servy, my answer explicitly provides a sample on how to retrieve a previous item. It does not simply explain how to iterate backwards. I should also point out that "Reserve" buffers the entirety of the IEnumerable that you use it against. That's required if the enumerable has no real items in it. But for an IList(T) that is not optimal. My example of going in reverse order does not create an unnecessary copy. – Applewhite

No, it doesn't provide a way to get the previous item for a sequence. It doesn't provide a sequence that can move forward and backward from every position, which is what the question is asking. You just provide an IEnumerable that iterates a sequence in reverse. Yes, Reverse needs to buffer the whole sequence; the code in your answer requires the same thing, it just requires it to be eagerly buffered into an IList, rather than having it be deferred. – Labiovelar

Read the first full paragraph of my answer. No code sample, true. But it provides a way to go forward and backward. Thanks. – Applewhite

All you said was that you could create a type with a MovePrevious method. Of course you can create a type with that method, the question is asking if you can have an iterator block create an iterator that is bi-directional. You're not even attempting to address that in any way in this answer. – Labiovelar

I came here because I was looking for a solution for bidirectional iterators. The OP should have made his questions more precise because of the yield operator, but I don't think we should withhold votes to Brian's answer as it's addressing the gist of the OP's question. – Collimore

Answer 4

C5 Collections library (http://www.itu.dk/research/c5/) implements collections and linked list with backwards enumeration. The project is OpenSource so you should be able to find answer there.

Juridical

Answer 5

No. One of the limitations of IEnumerator is that it holds its current state, and it doesn't remember its prior state. As a result, IEnumerable is forward-only.

If you need to hold onto prior states, read the IEnumerable into a List or LinkedList and enumerate through those objects instead.

Backler

Answer 6

Actually, there seems to be an approach described in Accelerated C# 2008. Unfortunately, two pages are not visible in the preview, and it has to rely on reflection (the results of which can be cached, as usual) but you can get the gist.

Bornie

That makes a bidirectional iterator from a LinkedList. That is easy enough. The difficulty lies in implementing one from just an IEnumerable. – Tartu

Answer 7

No. Using yield results in an IEnumerable which is unidirectional.

Guaiacol

For completeness: or an IEnumerator[<T>] – Macri