Friday, 25 July 2008

Yet another wishlist for programming languages, part 2: Inverse enumeration

How do you enumerate an IEnumerable inversely, from the last to first? Sometimes I need it. Maybe there can be a MovePrevious() method in the IEnumerator interface...

Please drop a comment if anyone thinks it's not 'doable' or why it's a bad practice :)

3 comments:

özgür said...

Given the list,
List<string> list = new List<string>() { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten" };


Hmm having the following effect using a foreach instead of for would fulfill your wish, i guess.

for (int i=list.Count; i>=0; i--)
    someFunc(list[i]);


Certainly there exists no MovePrevious() method in IEnumerator interface, and you can't add it yourself.

Simplest way would be:

list.Reverse();
foreach(var item in list)
     someFunc(item);

Hehe, we don't want the list to be reversed physically, i know.
A better way would be defining a new class which implements IEnumerator. This way you should implement GetEnumerator() yourself.

public class ReverseList<T> : System.Collections.IEnumerable
{
     private List<T> list;

     public ReverseList(List<T> list)
     {
         this.list = list;
     }

     System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
     {
         for (int i = list.Count - 1; i >= 0; i--)
         {
             yield return list[i];
         }
     }
}

Now you can use the following code to iterate through your collection:

foreach (var item in new ReverseList<string>(list))
    someFunc(item);

I am not sure whether we are physically creating a reversed copy of the original list or not. I think not the values but the references are used this way.

Note: I tried to go all the way using lists but all of the proposed statements can be used by other IEnumerable descendant classes.
Note 2: It is really hard to write something in this little blogger comment box. Google, give a hand :)

Görkem PAÇACI said...

Well, it's ok to do it with a list, but the point is that I don't have a List<T> instance! I only have an IEnumerable<T>, god knows where it's coming from!

The good thing about c#'s enumerators is that you can implement lazy-fetching using the 'yield' keyword, which brings dramatic performance increase in some certain 'filtered lookup' loops. And this approach makes it --almost-- impossible to implement an inverse enumerator.

And another thing is, Enumerable<T> interface doesn't grant you anything about the order of items in the results you get, or any kind of consistency among multiple loops. So an 'inverse' operation is indeed nonsense in this context.

I know it's not doable in c#'s Enumerable concept. It was more a kind of 'my wish' from language inventors like anders hejlsberg. That's the reason they're managing those strategies :)

Weeble said...

Easiest way is:
IEnumerable<T> InReverse(IEnumerable<T> series)
{
List<T> list = new List<T>(series);
list.Reverse();
return list;
}

Since you only have an IEnumerable, there's no getting around the fact that you need to read and store all the items in the list before you can reverse it.

Of course, as you suggest, it would be handy to have bidirectional iterators like in C++. I think you could make these yourself, though!

interface IBidirectionalEnumerator<T> : IEnumerator<T>
{
// We inherit MoveNext() and Current from IEnumerator<T>.
bool MovePrevious();
}

Then you could use extension methods to add a "GetBidirectionalEnumerator" method to the built-in collection types.