Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C# Class is IEnumerable AND an IEnumerator at the same time. What are the issues with this?

I have a class called GenericPermutations that is both enumerable and an enumerator. Its job is to take an ordered list of objects and iterate through each permutation of them in order.

Example, an integer implemenation of this class could iterate through the following:

GenericPermutations<int> p = new GenericPermutations<int>({ 1, 2, 3 });
p.nextPermutation(); // 123
p.nextPermutation(); // 132
p.nextPermutation(); // 213
// etc.

So its enumerable in the sense that it contains a 'list' of things you can enumerate over. It's also an enumerator, because its job involves finding the next permutation.

THE ISSUE: I am currently trying to integrate IEnumerator and IEnumerable with this class, and it seems to me like it should be both (rather than using a sub class as the IEnumerable). Thus far I have avoided the issue with trying to get two enumerators from it by passing a new GenericPermutation object in the GetEnumerator method.

Is this a bad idea? Anything else I should consider?

like image 218
jtfairbank Avatar asked Nov 08 '11 22:11

jtfairbank


2 Answers

Reduce your confusion (?) by using the generic versions of IEnumerable and IEnumerator.

A permutation enumerable is IEnumerable<IEnumerable<T>>. So you might have something like

IEnumerable<IEnumerable<T>> GetPermutations(IEnumerable<T> sequence)
{
    return new Permuter<T>(sequence);
}

and

public class Permuter<T> : IEnumerable<IEnumerable<T>> { ... }

Furthermore, I've seen more than one case where a single type implemented both IEnumerable<T> and IEnumerator<T>; its GetEnumerator method was simply return this;.

I think such a type would need to be a struct, though, because if it were a class you'd have all sorts of problems if you called GetEnumerator() a second time before the first enumeration was completed.

EDIT: Consuming the permuter

var permuter = GetPermutations(sequence);
foreach (var permutation in permuter)
{
    foreach (var item in permutation)
        Console.Write(item + "; ");
    Console.WriteLine();
}

Assuming the input sequence is { 1, 2, 3 }, the output is

1; 2; 3; 
1; 3; 2; 
2; 1; 3; 
2; 3; 1; 
3; 1; 2; 
3; 2; 1; 

EDIT:

Here's a super-inefficient implementation to illustrate the suggestion:

public class Permuter<T> : IEnumerable<IEnumerable<T>>
{
    private readonly IEnumerable<T> _sequence;

    public Permuter(IEnumerable<T> sequence)
    {
        _sequence = sequence;
    }

    public IEnumerator<IEnumerable<T>> GetEnumerator()
    {
        foreach(var item in _sequence)
        {
            var remaining = _sequence.Except(Enumerable.Repeat(item, 1));
            foreach (var permutation in new Permuter<T>(remaining))
                yield return Enumerable.Repeat(item, 1).Concat(permutation);
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}
like image 96
phoog Avatar answered Nov 03 '22 13:11

phoog


It is possible for one object to behave as both an IEnumerator<T> and IEnumerable<T>, but it is generally difficult for an object to do so in such fashion as to avoid quirky semantics; unless the IEnumerator<T> is going to be stateless (e.g. an empty enumerator, where MoveNext() always returns false, or an endless-repeat enumerator, where MoveNext() does nothing but always returns true, and Current always returns the same value), every call to GetEnumerator() must return a distinct object instance, and there's likely to be little value in having that instance implement IEnumerable<T>.

Having a value type implement IEnumerable<T> and IEnumerator<T>, and having its GetEnumerator() method return this, would satisfy the requirement that each call to GetEnumerator return a distinct object instance, but having value types implement mutable interfaces is generally dangerous. If a value type is boxed to IEnuerator<T> and never unboxed, it will behave as a class-type object, but there's no real reason why it shouldn't have simply been a class-type object.

Iterators in C# are implemented as class objects which implement both IEnumerable<T> and IEnumerator<T>, but they include a fair bit of fancy logic to ensure semantic correctness. The net effect is that having one object implement both interfaces offers a slight improvement in performance, in exchange for a fair bit of complexity in the generated code, and some semantic quirkiness in their IDisposable behavior. I would not recommend this approach in any code that needs to be human-readable; since the IEnumerator<T> and IEnumerable<T> aspects of the class mostly use different fields, and since a combined class needs to have a "thread-id" field which wouldn't be needed if using separate classes, the performance improvement one can achieve by using the same object to implement for both interfaces is limited. Worth doing perhaps if adding the complexity to the compiler will provide that slight performance improvement to millions of iterator routines, but not worth doing to improve the performance of one routine.

like image 37
supercat Avatar answered Nov 03 '22 13:11

supercat