5
\$\begingroup\$

I've come with a solution super tricky for a simple requirement. I think I could solve the problem using LinQ, but I'm not seeing it so clearly at all. What's sure, I'm not comfortable with my code.

The requirement is the following:

Given a list of lists of string (IEnumerable>), take the first N elements from each but one by one. So given this list of list and N=10:

{aaa, bb, ccc, ddd}
{eee, fff}
{ggg, hhhhh, iii, jjj, kkk}
{lll}
{1111, 22, 333, 444, 55555, 66666}

This is the output:

{aaa, eee, ggg, lll, 111, bb, fff, hhhhh, 22, ccc}

And here is the code:

private IEnumerable<string> Extract(
    IEnumerable<IEnumerable<string>> listOfList,
    int N
)
{
    var result = new List<string>();

    for (int i = 0; i < N; i++)
    {
        foreach (IEnumerable<string> list in listOfList)
        {
            if (list.Count() > i)
            {
                result.Add(list.ElementAt(i));

                if (result.Count >= N)
                    return result;
            }
        }
    }

    return result;
}

The code works, but I don't think this is maintainable nor easy to read. Thanks.

\$\endgroup\$
  • \$\begingroup\$ Would you mind clarifying the spec a little? Are you meant to take the first N elements of each list, but taking the first of each, then the second of each, etc. or are you meant to take the first N of the sequences defined by taking the first, then the second, etc. Your code (and the example and all the answers) currently do the second, but the spec sounds like it wants the first. \$\endgroup\$ – VisualMelon May 16 at 18:09
7
\$\begingroup\$

Calling ElementAt inside a loop will cause the IEnumerable to be called multiple times. This code isn't deffering execution either.

Now if you think the pervious code wasn't readable then hold on to your hats. I'm going to post some code in hopes someone can build on it and maybe come up with something better.

public static class IEnumerableExtensions
{
    public static IEnumerable<TSource> Interweave<TSource>(this IEnumerable<TSource> source, params IEnumerable<TSource>[] weavers)
    {
        // Create a list of Enumerators but need to reverse it as will be removing from list and don't want o mess up indexer
        var enumerators = new[] { source }.Concat(weavers).Select(x => x.GetEnumerator()).Reverse().ToList();
        try
        {
            while (enumerators.Count > 0)
            {
                //  index backwards so we can remove from list and not mess up index
                for (var i = enumerators.Count - 1; i >= 0; i--)
                {
                    var currentEnumerator = enumerators[i];
                    if (currentEnumerator.MoveNext())
                    {
                        yield return currentEnumerator.Current;
                    }
                    else
                    {
                        currentEnumerator.Dispose();
                        enumerators.Remove(currentEnumerator);
                    }
                }
            }
        }
        finally
        {
            // finally block as we can't use "using" as have multiple disposables and don't know count ahead of time
            if (enumerators != null)
            {
                enumerators.ForEach(x => x.Dispose());
            }
        }
    }
}

This doesn't do Take but you can just chain on the Take method.

Example of it in use

static void Main(string[] args)
{
    var one = new[] { "aaa", "bb", "ccc", "ddd" };
    var two = new[] { "eee", "fff" };
    var threee = new[] { "ggg", "hhhhh", "iii", "jjj", "kkk" };
    var four = new[] { "lll" };
    var five = new[] { "1111", "22", "333", "444", "55555", "66666" };

    foreach (var item in one.Interweave(two, threee, four, five).Take(6))
    {
        Console.WriteLine(item);
    }
    Console.ReadLine();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You can avoid the fiddly stuff with the list indices by using a queue instead. \$\endgroup\$ – Peter Taylor May 15 at 8:10
  • \$\begingroup\$ This code isn't just more efficient, it will handle infinite and non-resuable IEnumerables, which the OP's code won't. I like the lists personally (though not-so-much the reverse order, and it would probably be tidier with a Queue); you might consider using RemoteAt(i) rather than Remove(currentEnumerator) to avoid a linear scan. There is also no utility in the null check in the finally. \$\endgroup\$ – VisualMelon May 15 at 9:14
  • \$\begingroup\$ @VisualMelon RemoveAt would be better. The null check was from docs.microsoft.com/en-us/dotnet/csharp/language-reference/… where they have code of what using boils down to. I was wondering about it as well but put it in based on their example. \$\endgroup\$ – CharlesNRice May 15 at 13:21
  • 1
    \$\begingroup\$ I think this is a great approach. Here's a fiddle of what it might look like with Dequeue + maybe re-Enque in place of Remove or RemoveAt. dotnetfiddle.net/sOYUn4 \$\endgroup\$ – benj2240 May 15 at 23:20
  • 1
    \$\begingroup\$ @benj2240 the queue's constructor is eager and will enumerate the main collection entirely. \$\endgroup\$ – t3chb0t May 16 at 16:55
3
\$\begingroup\$

A few comments about the API which completely ignore the spec:

  • I would rename N to count, which is descriptive and follows typical naming conventions. Your method would benefit from inline documentation (///), which could clarify the behaviour (what does Extract mean?!?) and describe the parameters precisely.

  • It's good that you've used the general-purpose IEnumerable as the return type (gives you freedom to use lazy implementations like those provided by the other answers). I would consider removing the count parameter: the consumer can use LINQ's Take if they want. Currently the API means you can't just keep consuming stuff until you get bored (e.g. with TakeWhile or something), and lacks a specification as to what the method should do if it runs out of stuff to return, what to do with invalid inputs (e.g. -1) ,and all that fun stuff that comes with providing a nontrivial API.

  • Note that t3chb0t has provided a generic implementation, so it works with lists of anything, and not just strings. There is basically no reason not to do this, and it means you will have a nice reusable piece of code that works with any type.

  • Again, t3chb0t has made the method a static extension method: there is no need for your method to be an instance method unless it is swappable behaviour, which is not implied by the spec. An extension method means it will fit in nicely with the other LINQ methods that most of us use daily.

\$\endgroup\$
3
\$\begingroup\$

CharlesNRice's solution has still one flaw. It eagerly enumerates the main collection and since we don't know its length, we better avoid it. Since the other answer already mentions flaws in your code, let me just add this lazy alternative.


It's a little bit tricky to make it deferred because you first need to enumerate the main collection and create enumerators for each sub-collection, this is what I use the isQueuePopulated flag for. Then you need to collect them in the queue for as long as you're enumerating the main collection. When this is done, you need to switch to the queue, then you Dequeue the first enumerator, try to MoveNext and if it succeeded, you return Current and Enqueue the enumerator for later.

public static IEnumerable<T> TakeEach<T>(this IEnumerable<IEnumerable<T>> source, int count)
{
    var counter = 0;
    var queue = new Queue<IEnumerator<T>>();
    var mainEnumerator = source.GetEnumerator();
    var isQueuePopulated = false;
    try
    {
        var e = default(IEnumerator<T>);
        while (!isQueuePopulated || queue.Any())
        {
            if (!isQueuePopulated && mainEnumerator.MoveNext())
            {
                e = mainEnumerator.Current.GetEnumerator();
            }
            else
            {
                isQueuePopulated = true;
            }

            e = isQueuePopulated ? queue.Dequeue() : e;

            if (e.MoveNext())
            {
                queue.Enqueue(e);
                yield return e.Current;

                if (++counter == count)
                {
                    yield break;
                }
            }
            else
            {
                e.Dispose();
            }
        }
    }
    finally
    {
        mainEnumerator.Dispose();
        foreach (var e in queue)
        {
            e.Dispose();
        }

    }
}
\$\endgroup\$
3
\$\begingroup\$

Another opportunity to solve this problem is to use Transpose() in MoreLinq with Linq itself:

var listoflists = new List<List<string>>() { one, two, three, four, five };
var res = listoflists.Transpose()
    .SelectMany(x => x)
    .Take(10);

Result: { "aaa", "eee", "ggg", "lll", "1111", "bb", "fff", "hhhhh", "22", "ccc" }

\$\endgroup\$
  • \$\begingroup\$ The Transpose extension is implemented virtually exactly as we did it here ;) \$\endgroup\$ – t3chb0t May 17 at 9:28
  • \$\begingroup\$ yep ;) As opportunity to not implement it by yourself \$\endgroup\$ – HelloWorld May 17 at 9:30
  • \$\begingroup\$ And I find their _() hillarious. This should have never been accepted LOL \$\endgroup\$ – t3chb0t May 17 at 9:30
  • 1
    \$\begingroup\$ Although, now I think my solution is better because it's deferred on every collection. Theirs is using Acquire which is eager and enumerates the main collection completely. \$\endgroup\$ – t3chb0t May 17 at 9:32
  • 2
    \$\begingroup\$ @t3chb0t it doesn't have much choice, since it yields columns at a time ;) (good point non-the-less) (I also don't like that transpose method's API... transpose ought to be reversible in my book) \$\endgroup\$ – VisualMelon May 17 at 9:37

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.