¿Cómo evito la recursión infinita con un enumerador personalizado?

Question

Hice un método de extensión para encontrar el número de valores consecutivos en una colección. Debido a que es genérico, le permito a la persona que llama definir el "incrementor" que es un Func <> que se supone que incrementa el valor para verificar la existencia de un "próximo" valor.

Sin embargo, si la persona que llama pasa un incremento impropio (es decir, x => x), producirá un bucle recursivo infinito. ¿Alguna sugerencia sobre una forma limpia de prevenir esto?

public static int CountConsecutive<T>(this IEnumerable<T> values, T startValue, Func<T, T> incrementor) 
{ 
    if (values == null) 
    { 
     throw new ArgumentNullException("values"); 
    } 
    if (incrementor == null) 
    { 
     throw new ArgumentNullException("incrementor"); 
    } 
    var nextValue = incrementor(startValue); 
    return values.Contains(nextValue) 
     ? values.CountConsecutive(nextValue, incrementor) + 1 
     : 1; 
} 

Answer 1

En el sentido más puro, este es un intento en el Halting Problem y es indecidible. Para todos los casos menos simples, tendrá que confiar en los que llaman a su método.

Como han demostrado otros, puede hacer una simple comprobación de igualdad para mostrar que el siguiente valor es diferente. Almacenar cada visita T funcionará pero tendrá que preocuparse por la memoria eventualmente.

Como un lado, aquí hay una StackOverflowException fácilmente implementada por lo que debe tener cuidado con cualquier conjunto de datos que tendrá mucho en valores consecutivos.

var x = Enumerable.Range(1, 100000).CountConsecutive(1, x => x+1); 

Answer 2

Puede comparar nextValue to startValue (necesitará T para implementar IComparable).

Esto resolverá este error, no resolverá un desagradable error incrementor que devuelve un bucle - a1, a2, a3, ..., an, a1. Creo que no desea manejar este caso, sin embargo

Answer 3

Para tratar el caso más simple, se puede hacer esto:

var nextValue = incrementor(startValue); 
if (nextValue.Equals(startValue)) { 
    throw new ArgumentException("incrementor"); 
} 

Por caso general, hacer esto:

public static int CountConsecutive<T>(this IEnumerable<T> values, T startValue, Func<T, T> incrementor) { 
    if (values == null) { 
     throw new ArgumentNullException("values"); 
    } 
    if (incrementor == null) { 
     throw new ArgumentNullException("incrementor"); 
    } 
    ISet<T> seen = new HashSet<T>(); 
    return CountConsecutive(values, startValue, incrementor, seen); 
} 

private static int CountConsecutive<T>(IEnumerable<T> values, T startValue, Func<T, T> incrementor, ISet<T> seen) { 
    if (!seen.Add(startValue)) { 
     throw new ArgumentException("incrementor"); 
    } 
    var nextValue = incrementor(startValue); 
    return values.Contains(nextValue) 
     ? values.CountConsecutive(nextValue, incrementor) + 1 
     : 1; 
}