6
\$\begingroup\$

my requirement is to implement a way to filter a collection of elements based on a value of previous one. For example to only select a number that is larger than the previous one. I don't currently know of any LINQ method that would allow me to do such a thing, so I decided to create one.

This is a code I have so far:

        public static IEnumerable<T> WherePrevious<T>(this IEnumerable<T> collection, Func<T, T, bool> predicate)
    {
        if (collection == null) throw new ArgumentNullException(nameof(collection));
        if (predicate == null) throw new ArgumentNullException(nameof(predicate));

        T previous = default(T);
        bool firstIteration = true;

        foreach (var item in collection)
        {
            if (firstIteration)
            {
                previous = item;
                firstIteration = false;
                yield return item;
            }
            else
            {
                if (predicate(previous, item))
                {
                    yield return item;
                }

                previous = item;
            }
        }
    }

Are there any ways to improve my code in terms of performance, readability or more generalization to make?

For example I'm not sure if it's clear to the caller of the method what the predicate inputs actually are

\$\endgroup\$
0
4
\$\begingroup\$

Linq Zip came to mind in order to map the items in pairs and then apply the predicate.

public static IEnumerable<T> WherePrevious<T>(this IEnumerable<T> collection, Func<T, T, bool> predicate) {
    if (collection == null) throw new ArgumentNullException(nameof(collection));
    if (predicate == null) throw new ArgumentNullException(nameof(predicate));
    if(!collection.Any()) yield break;

    yield return collection.First();

    var items = collection
        .Zip(collection.Skip(1), (previous, item) => (previous, item))
        .Where(zip => predicate(zip.previous, zip.item))
        .Select(zip => zip.item);

    foreach(var item in items)
        yield return item;
}

The following test was used to demonstrate the example given in the original question.

[TestClass]
public class FilterTest {
    [TestMethod]
    public void WherePreviousTest() {
        //Arrange
        var numbers = new[] { 1, 5, 8, 7, 12, 8, 5 };
        var expected = new[] { 1, 5, 8, 12 };

        //Act
        var actual = numbers.WherePrevious((first, second) => second > first).ToArray();

        //Assert
        actual.ShouldAllBeEquivalentTo(expected);
    }
}

The body of the created extension method could have been done on its own, but creating the extension method allowed for a cleaner approach.

While I would say it is easier to read IMO, technically you will be enumerating the list more than once, which makes this not as efficient as your one pass through.

That then lead me to rethink my approach. After reviewing the source code for Enumerable.Zip and realizing your approach had the right idea I refactored the code to use the enumerator of the collection.

public static IEnumerable<T> WherePrevious<T>(this IEnumerable<T> collection, Func<T, T, bool> predicate) {
    if (collection == null) throw new ArgumentNullException(nameof(collection));
    if (predicate == null) throw new ArgumentNullException(nameof(predicate));
    return WherePreviousIterator(collection, predicate);
}

private static IEnumerable<T> WherePreviousIterator<T>(IEnumerable<T> collection, Func<T, T, bool> predicate) {
    using (var e = collection.GetEnumerator()) {
        if (e.MoveNext()) {
            var previous = e.Current;
            yield return previous;
            while (e.MoveNext()) {
                var item = e.Current;
                if (predicate(previous, item))
                    yield return item;
                previous = item;
            }
        }
        yield break;
    }
}

Which actually performed not that much better than the previous suggestion using Zip when run against the same test above.

\$\endgroup\$
9
  • \$\begingroup\$ I like the Zip version better and I think you should put the predicate where it belongs, this is, inside Where instead of using a blank marker. \$\endgroup\$
    – t3chb0t
    Feb 9 '18 at 5:18
  • \$\begingroup\$ @t3chb0t I preferred the Zip myself, but when testing i noticed the iterator version performed 10 times better. As for the second part of your statement, how would the predicate work inside Where. It takes two arguments while Where's predicate expects only one. \$\endgroup\$
    – Nkosi
    Feb 9 '18 at 5:25
  • \$\begingroup\$ I'd do it like this - let me post it as a gist because otherwise it'll look terrible here as a single long line ;-] \$\endgroup\$
    – t3chb0t
    Feb 9 '18 at 5:30
  • 1
    \$\begingroup\$ @t3chb0t thanks. The updated zip version now performs almost as well as the enumerator, which actual would make the Zip the better choice. \$\endgroup\$
    – Nkosi
    Feb 9 '18 at 5:42
  • 1
    \$\begingroup\$ For my scenario returning the first element is correct but I agree that my description of the problem is different and should not return the first item. However I like this solution as it doesn't rely on indexed collection types and is readable by making it using existing LINQ methods. \$\endgroup\$ Feb 9 '18 at 11:43
2
\$\begingroup\$

First I've tried to make your extension a little clearer by avoiding the firstIteration flag:

public static IEnumerable<T> WherePreviousReview<T>(this IEnumerable<T> collection, Func<T, T, bool> predicate)
{
  if (collection == null) throw new ArgumentNullException(nameof(collection));
  if (predicate == null) throw new ArgumentNullException(nameof(predicate));
  if (!collection.Any())
    yield break;

  T previous = collection.First();

  yield return previous;

  foreach (var item in collection.Skip(1))
  {
    if (predicate(previous, item))
    {
      yield return item;
    }

    previous = item;
  }
}

This is a version that uses the power of the Where extension:

public static IEnumerable<T> WherePrevious<T>(this IEnumerable<T> collection, Func<T, T, bool> predicate)
{
  if (collection == null) throw new ArgumentNullException(nameof(collection));
  if (predicate == null) throw new ArgumentNullException(nameof(predicate));
  T previous = default(T);
  return collection.Where((current, i) =>
  {
    bool result = i == 0 || predicate(previous, current);
    previous = current;
    return result;
  });
}

This is a version that uses the Aggregate extension:

public static IEnumerable<T> NewWherePrevious<T>(this IEnumerable<T> collection, Func<T, T, bool> predicate)
{
  if (collection == null) throw new ArgumentNullException(nameof(collection));
  if (predicate == null) throw new ArgumentNullException(nameof(predicate));
  if (!collection.Any())
    return new List<T>();

  return collection.Aggregate((0, default(T), new List<T>()), (acc, cur) =>
  {
    if (acc.Item1 == 0 || acc.Item1 > 0 && predicate(acc.Item2, cur))
    {
      acc.Item3.Add(cur);
    }

    acc.Item1++;
    acc.Item2 = cur;

    return acc;
  }).Item3;
}

The latter is not meant as a better choice, just an example of another approach. The caveat is the inner list object.


Update

Aggregate version with named tuples:

public static IEnumerable<T> NewWherePrevious<T>(this IEnumerable<T> collection, Func<T, T, bool> predicate)
{
  if (collection == null) throw new ArgumentNullException(nameof(collection));
  if (predicate == null) throw new ArgumentNullException(nameof(predicate));
  if (!collection.Any())
    return new T[0];

  (int index, T prev, List<T> list) seed = (0, default(T), new List<T>());

  return collection.Aggregate(seed, ((int index, T prev, List<T> list) acc, T cur) =>
  {
    if (acc.index == 0 || acc.index > 0 && predicate(acc.prev, cur))
    {
      acc.list.Add(cur);
    }

    acc.index++;
    acc.prev = cur;

    return acc;
  }).list;
}
\$\endgroup\$
4
  • \$\begingroup\$ You should name the tuple properties because the aggregate approach is not necessarily a good advice with all these ItemXs; in fact it's the least readable version of all :-] \$\endgroup\$
    – t3chb0t
    Feb 9 '18 at 8:09
  • 1
    \$\begingroup\$ @t3chb0t: I totally agree - and updated my answer. \$\endgroup\$
    – user73941
    Feb 9 '18 at 8:35
  • \$\begingroup\$ The first approach that omits firstIteration flag is very nice. The second approach has one flaw, thats actually a problem for my case and that is that you are iterating the whole collection to filter it. Other solutions rely on yield keyword that should only enumerate it when its actually needed. For large collections it might be a problem. \$\endgroup\$ Feb 9 '18 at 11:47
  • 1
    \$\begingroup\$ @LadislavBohm: I agree. It is not the best or even a good implementation. As written above - just another way. \$\endgroup\$
    – user73941
    Feb 9 '18 at 14:24
1
\$\begingroup\$

For example to only select a number that is larger than the previous one. I don't currently know of any LINQ method that would allow me to do such a thing

Actually there is a LINQ extension which allows you to do that. the Where extension has an overload that uses the item value and the item's index:

List<int> test1 = new List<int>()
{
    23,
    45,
    16,
    8,
    90,
    25
};
var test2 = test1.Where((x, i) => (i > 0)?x > test1[i - 1]:false);

One caveat to this is, it will only work for indexed collections of types that support comparison operators.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.