4
\$\begingroup\$

Basically, what I mean by splice is to take an array of Enumerables, take the 1st element from the first one, then the 1st element from the second one, and so forth, until we come back to the 1st enumerable, and we then take the next element from it and each of the others.

Sort of like this: [A A] [B B] [C C] [D D] [E E] [F F] Splicing these together would produce [A B C D E F A B C D E F]

namespace xofz
{
    using System.Collections.Generic;

    public interface MaterializedEnumerable<out T> : IEnumerable<T>
    {
        long Count { get; }
    }
}

A MaterializedEnumerable is basically an enumerable which has been written to memory, so it can be iterated as many times as you want. It also gets a Count property.

Here is the actual splice code. Don't worry about what an OrderedMaterializedEnumerable is, just think of it for now as a wrapper for List<T>

namespace xofz.Transformation
{
    using System.Collections.Generic;
    using System.Linq;
    using xofz.Materialization;

    public class EnumerableSplicer
    {
        public MaterializedEnumerable<T> Splice<T>(IEnumerable<T>[] sources)
        {
            var lists = new List<T>[sources.Length];

            // first, enumerate all the items into separate lists
            for (var i = 0; i < sources.Length; ++i)
            {
                lists[i] = new List<T>(new LinkedList<T>(sources[i]));
            }

            // then, splice the lists together
            var list = new List<T>(lists.Sum(l => l.Count));
            var smallestCount = lists.Select(l => l.Count).Min();

            for (var i = 0; i < smallestCount; ++i)
            {
                list.AddRange(lists.Select(l => l[i]));
            }

            var remainingLists = new LinkedList<List<T>>();
            foreach (var l in lists)
            {
                l.RemoveRange(0, smallestCount);
                if (l.Count > 0)
                {
                    remainingLists.AddLast(l);
                }
            }

            if (remainingLists.Count == 0)
            {
                return new OrderedMaterializedEnumerable<T>(list);
            }

            IEnumerable<IEnumerable<T>> remainingEnumerables = remainingLists;
            list.AddRange(this.Splice(remainingEnumerables.ToArray()));

            return new OrderedMaterializedEnumerable<T>(list);
        }
    }
}

This method is slightly recursive, to handle enumerables of different sizes. I hope it is easy enough to read!

More transformations I wrote lately are available at xofz.Core on Github.

\$\endgroup\$
  • 1
    \$\begingroup\$ This operation is more commonly known as zip-join. LINQ ships with support for zipping two sequences together. \$\endgroup\$ – Eric Lippert Jul 5 '16 at 22:54
4
\$\begingroup\$

My comment is that you can write your desired method with far more generality, no recursion, and far less realization into lists. For example:

using System;
using System.Linq;
using System.Collections.Generic;   

public class Program
{
    public static IEnumerable<R> Zipper<A, R>(IEnumerable<IEnumerable<A>> sequences, Func<IEnumerable<A>, R> f)
    {
        var enumtors = sequences.Select(seq => seq.GetEnumerator()).ToList();
        while(true)
        {
            // Not quite kosher, as we are using Select to cause a side effect!
            var hasValues = enumtors.Select(e => e.MoveNext());
            if (hasValues.Any(v => !v)) 
                break;
            yield return f(enumtors.Select(e => e.Current));
        }
        foreach(var enumtor in enumtors)
          enumtor.Dispose();
    }

    public static void Main()
    {
        foreach(var s in Zipper(
            new[] { 
              new[] {1, 2}, 
              new[] {3, 4}, 
              new[] {5, 6, 7} }, 
            x => string.Join("-", x))) 
          Console.WriteLine(s);
    }
}

Produces output

1-3-5
2-4-6

Note that my version works on infinite lists provided that there are finitely many of them. Note also that my method is "lazy"; it only makes computations when the caller "pulls" something.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Probable typo enumtors -> enumerators \$\endgroup\$ – Caridorc Jul 7 '16 at 14:14
  • \$\begingroup\$ Note that this isn't disposing the enumerators. \$\endgroup\$ – Servy Jul 7 '16 at 21:38
  • \$\begingroup\$ I'd also be tempted to write the loop as while(enumtors.Select(e => e.MoveNext()).All(v => v)){ yield return [...] } rather than an infinite loop that breaks in the middle. If that was too much for you in the while predicate then my inclination would be to move that code to a MoveAll method, rather than creating an infinite loop with a break; in the middle. \$\endgroup\$ – Servy Jul 7 '16 at 21:44
  • \$\begingroup\$ @Servy: Good points all! \$\endgroup\$ – Eric Lippert Jul 8 '16 at 14:49

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.