7
\$\begingroup\$

This function divides a sequence into partitions, where a partition is a list of consecutive matching elements.

Example

Input: (A, A, B, B, B, A, C, C)

Output: ((A, A), (B, B, B), (A), (C, C))

I've tried to make this code "obviously correct", but it still doesn't look that way to me.

public static IEnumerable<List<T>> PartitionBy<T, PK>(this IEnumerable<T> sequence, Func<T, PK> partitionKey)
{
    return sequence.PartitionBy(partitionKey, EqualityComparer<PK>.Default);
}

public static IEnumerable<List<T>> PartitionBy<T>(this IEnumerable<T> sequence, IEqualityComparer<T> comparer)
{
    return sequence.PartitionBy(item => item, comparer);
}

public static IEnumerable<List<T>> PartitionBy<T, X>(this IEnumerable<T> sequence, Func<T, X> partitionKey, IEqualityComparer<X> comparer)
{
    var itr = sequence.GetEnumerator();
    if (!itr.MoveNext())
    {
        // empty sequence was passed in, so return empty sequence
        yield break;
    }

    // Start the first partition.
    var currentList = new List<T>(new[] { itr.Current });

    while (itr.MoveNext())
    {
        var key1 = partitionKey(currentList[0]);
        var key2 = partitionKey(itr.Current);

        if (comparer.Equals(key1, key2))
        {
            // continue current partition
            currentList.Add(itr.Current);
        }
        else
        {
            // yield current partition and start a new one
            yield return currentList;
            currentList = new List<T>(new[] { itr.Current });
        }
    }

    // We know it has at least 1 element here.
    yield return currentList;
}
\$\endgroup\$
  • \$\begingroup\$ A downvote less than 5 seconds after posting? \$\endgroup\$ – default.kramer May 31 '17 at 18:50
  • \$\begingroup\$ The close-voter picked "unclear what you're asking" for a close reason; I suppose your post could use an edit to clarify what your code is doing, how it's used and why there are 3 overloads. \$\endgroup\$ – Mathieu Guindon May 31 '17 at 19:01
  • \$\begingroup\$ And how you mean that the code doesn't look "obviously correct"? \$\endgroup\$ – Simon Forsberg May 31 '17 at 19:04
  • 3
    \$\begingroup\$ I think that the poster is saying that the code works correctly, but is too verbose to be intuitively understood. \$\endgroup\$ – 200_success May 31 '17 at 19:14
  • 1
    \$\begingroup\$ @BKSpurgeon - GroupBy doesn't work because non-consecutive items end up in the same group. See my example, how one of the partitions is (A, A) and another is (A) \$\endgroup\$ – default.kramer Jun 1 '17 at 14:16
5
\$\begingroup\$

Just a small point to start:

new List<T>(new[] { itr.Current });

You don't need the array too, you can just do:

new List<T> { itr.Current };

I'd suggest that you aim for consistency with your generic type names too. Why X vs PK? I'd suggest TKey for both.

You could do it just with a foreach:

public static IEnumerable<IEnumerable<T>> Partition<T, TKey>(
    this IEnumerable<T> items, 
    Func<T, TKey> keySelector, 
    IEqualityComparer<TKey> comparer)
{
    List<T> currentPartition = null;
    foreach (var item in items)
    {
        if (currentPartition != null 
            && comparer.Equals(keySelector(item), keySelector(currentPartition[0])))
        {
            currentPartition.Add(item);
        }
        else 
        {
            if (currentPartition != null)
            {
                yield return currentPartition;
            }
            currentPartition = new List<T> { item };
        }
    }
    if (currentPartition != null)
    {
        yield return currentPartition;
    }
}

Is it clearer than your code? I'm not convinced it is.

\$\endgroup\$
  • \$\begingroup\$ Despite the (relative) complexity inside the loop, I do think this will be clearer for most programmers, simply because it avoids the cumbersome enumerator code that foreach is meant to free us from. \$\endgroup\$ – VisualMelon May 31 '17 at 21:35
  • \$\begingroup\$ Yeah, I started with a foreach but it wasn't as clean as yours. I think I slightly prefer yours to my OP now. And naming it "currentPartition" is a big improvement over "currentList". \$\endgroup\$ – default.kramer May 31 '17 at 22:13

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.