Linq - lookahead Iteration

Question

I am iterating thru a collection using a visitor-type pattern and need to access the current and next item in the list. At the moment I am doing it via an extension method like this

public void Visit<TItem>(this IEnumerable<TItem> theList, Action<TItem, TItem> visitor)
{
    for (i = 0; i <= theList.Count - 1; i++) {
        if (i == theList.Count - 1) {
            visitor(theList(i), null);
        } else {
            visitor(theList(i), theList(i + 1));
        }    
    }    
}

I was wondering whether there are other/better/more elegant ways to achieve this? At the moment I think I only need to have access to the current and next items in the list, but I'm wondering whether I may encounter situations where I may need to lookahead the next 'n' items, for example.

Answer 1

Assuming you're using .NET 4, you can use Zip to accomplish the same thing:

var query = original.Zip(original.Skip(1),
                         (current, next) => new { current, next });

This will iterate over the sequence twice though. A nicer alternative to your current extension method (which I don't believe will work, btw, as IEnumerable doesn't have a Count property, and you're trying to call theList as a method as well...) would be something like:

public static void Visit<TItem>(this IEnumerable<TItem> theList,
                         Action<TItem, TItem> visitor)
{
    TItem prev = default(TItem);
    using (var iterator = theList.GetEnumerator())
    {
        if (!iterator.MoveNext())
        {
            return;
        }
        prev = iterator.Current;
        while (iterator.MoveNext())
        {
            TItem current = iterator.Current;
            visitor(prev, current);
            prev = current;
        }
    }
    visitor(prev, default(TItem)); // Are you sure you want this?
}

A more general lookahead is trickier, to be honest... you'd want some sort of circular buffer, I suspect... probably a custom collection.

Answer 2

When we run into a similar task we have defined an extension methods:

/// <summary>
/// Projects a window of source elements in a source sequence into target sequence.
/// Thus
///   target[i] = 
///     selector(source[i], source[i - 1], ... source[i - window + 1])
/// </summary>
/// <typeparam name="T">A type of elements of source sequence.</typeparam>
/// <typeparam name="R">A type of elements of target sequence.</typeparam>
/// <param name="source">A source sequence.</param>
/// <param name="window">A size of window.</param>
/// <param name="lookbehind">
/// Indicate whether to produce target if the number of source elements 
/// preceeding the current is less than the window size.
/// </param>
/// <param name="lookahead">
/// Indicate whether to produce target if the number of source elements 
/// following current is less than the window size.
/// </param>
/// <param name="selector">
/// A selector that derives target element.
/// On input it receives:
///   an array of source elements stored in round-robing fashon;
///   an index of the first element;
///   a number of elements in the array to count.
/// </param>
/// <returns>Returns a sequence of target elements.</returns>
public static IEnumerable<R> Window<T, R>(
  this IEnumerable<T> source,
  int window,
  bool lookbehind,
  bool lookahead,
  Func<T[], int, int, R> selector)
{
  var buffer = new T[window];
  var index = 0;
  var count = 0;

  foreach(var value in source)
  {
    if (count < window)
    {
      buffer[count++] = value;

      if (lookbehind || (count == window))
      {
        yield return selector(buffer, 0, count);
      }
    }
    else
    {
      buffer[index] = value;
      index = index + 1 == window ? 0 : index + 1;

      yield return selector(buffer, index, count);
    }
  }

  if (lookahead)
  {
    while(--count > 0)
    {
      index = index + 1 == window ? 0 : index + 1;

      yield return selector(buffer, index, count);
    }
  }
}

/// <summary>
/// Projects a window of source elements in a source sequence into a 
/// sequence of window arrays.
/// </summary>
/// <typeparam name="T">A type of elements of source sequence.</typeparam>
/// <typeparam name="R">A type of elements of target sequence.</typeparam>
/// <param name="source">A source sequence.</param>
/// <param name="window">A size of window.</param>
/// <param name="lookbehind">
/// Indicate whether to produce target if the number of source elements 
/// preceeding the current is less than the window size.
/// </param>
/// <param name="lookahead">
/// Indicate whether to produce target if the number of source elements 
/// following current is less than the window size.
/// </param>
/// <returns>Returns a sequence of windows.</returns>
public static IEnumerable<T[]> Window<T>(
  this IEnumerable<T> source,
  int window,
  bool lookbehind,
  bool lookahead)
{
  return source.Window(
    window,
    lookbehind,
    lookahead,
    (buffer, index, count) =>
    {
      var result = new T[count];

      for(var i = 0; i < count; ++i)
      {
        result[i] = buffer[index];
        index = index + 1 == buffer.Length ? 0 : index + 1;
      }

      return result;
    });
}

These functions help to produce output elements from a window of input elements.

See also LINQ extensions.

Answer 3

It seems like you are using the wrong type. The act of indexing an sequence will iterate it until it reaches the specified index every single time. Why not use IList<T> or ReadOnlyCollection<T>?

Answer 4

Not tested, but I think this works? When the visit would exceed the bounds it loops to the front of the list.

public class FriendlyEnumerable<T> : IEnumerable<T>
{
    private IEnumerable<T> _enum;

    public FriendlyEnumerable(IEnumerable<T> enumerable) 
    {            
        _enum = enumerable;
    }

    public void VisitAll(Action<T, T> visitFunc)
    {
        VisitAll(visitFunc, 1);
    }

    public void VisitAll(Action<T, T> visitFunc, int lookahead)
    {
        int index = 0;
        int length = _enum.Count();
        _enum.ToList().ForEach(t =>
        {
            for (int i = 1; i <= lookahead; i++)
                visitFunc(t, _enum.ElementAt((index + i) % length));
            index++;
        });
    }

    #region IEnumerable<T> Members
    public IEnumerator<T> GetEnumerator()
    {
        return _enum.GetEnumerator();
    }
    #endregion
}

You could use it like:

List<string> results = new List<string>();
List<string> strings = new List<string>() 
    { "a", "b", "c", "d", "a", "b", "c", "d" };
FriendlyEnumerable<string> fe = new FriendlyEnumerable<string>(strings);
Action<string, string> compareString = 
    new Action<string,string>((s1, s2) =>
        {
            if (s1 == s2)
                results.Add(s1 + " == " + s2);
        });
fe.VisitAll(compareString);
//no results
fe.VisitAll(compareString, 4);
//8 results