3
\$\begingroup\$

Can anyone help me prettify this code? The idea is to combine adjacent time spans so

[0:00-1:00, 1:00-2:00, 3:00-4:00] becomes [0:00-2:00, 3:00-4:00]

private static IEnumerable<Span> CombineAdjacentSpans(IEnumerable<Span> spans)
{
    var combined = new List<Span>();
    var list = spans.OrderBy(s => s.Start).ToList();

    var candidate = list.FirstOrDefault();
    foreach (var span in list.Skip(1))
    {
        if (span.Start == candidate.End)
        {
            candidate.End = span.End;
            continue;
        }

        combined.Add(candidate);
        candidate = span;
    }

    if (candidate != null)
        combined.Add(candidate);

    return combined;
}
\$\endgroup\$
4
\$\begingroup\$

You can shorten this and get lazy evalution using yield:

private static IEnumerable<Span> CombineAdjacentSpans(this IEnumerable<Span> spans)
{
    Span current = null;
    foreach (var span in spans.OrderBy(s => s.Start)) {
        if (current == null) { current == span; }
        // I made this handle overlaps, but if you don't care about those
        // you can change the comparison to just ==
        else if (span.Start <= current.End && span.End > current.End) {
            // current.End = span.End
            // it's probably better to make a new span rather than modifying the
            // current one here since that way this method doesn't modify elements
            // in the original list. If span is a struct, then modification would be
            // fine but we'd have to rely on a bool rather than checking against null
            current = new Span { Start = current.Start, End = span.End };
        } else {
            yield return current;
            current = span;
        }              
    }

    if (current != null) { yield return current; }
}

This way, something like mySpans.CombineAdjacentSpans().Take(3) will only do the work of combining the first 3 spans (although OrderBy will still have to look at all elements in the input sequence).

In response to Chris's comment, if you really want the last if statement inside the loop here's one way I can think of to do it:

private static IEnumerable<Span> CombineAdjacentSpans(this IEnumerable<Span> spans)
{
    Span current = null;
    // could also use Enumerable.Repeat() instead of new[] { ... }
    foreach (var span in spans.OrderBy(s => s.Start).Concat(new[] { default(Span) })) {
        if (current == null) { current == span; }
        // I made this handle overlaps, but if you don't care about those
        // you can change the comparison to just ==
        else if (span.Start <= current.End && span.End > current.End) {
            // current.End = span.End
            // it's probably better to make a new span rather than modifying the
            // current one here since that way this method doesn't modify elements
            // in the original list. If span is a struct, then modification would be
            // fine but we'd have to rely on a bool rather than checking against null
            current = new Span { Start = current.Start, End = span.End };
        } else {
            yield return current;
            current = span;
        }              
    }
}
\$\endgroup\$
  • \$\begingroup\$ Excellent idea, thanks. There is one more thing that is bothering me though, and to be honest I don't know if it's doable or not and if so if it will improve or degrade the readability - it's the final call after the loop ends - the if (current != null) { ... } I wanted to drag that somehow into the loop. Any ideas on that? \$\endgroup\$ – Chris Sep 1 '12 at 20:17
  • \$\begingroup\$ @Chris: I've added a second version that does just that. Not sure it's really more readable though. \$\endgroup\$ – Chase medallion Sep 1 '12 at 21:13
  • \$\begingroup\$ I was going in a similar direction with that ;) and am also not sure if that's more readable or not - but it is shorter, so I'll go for it. Thanks for your help. I like the refactorings. \$\endgroup\$ – Chris Sep 3 '12 at 8:13
0
\$\begingroup\$

I would make three changes

  1. Drop the ToList() as you are working on IEnumerable<Span> anyway and are not making use of list indexes.

  2. Take in account overlapping spans by testing for span.Start <= candidate.End instead of just span.Start == candidate.End.

  3. Use an else-clause instead of a continue. People are more used to else. It's a matter of personal preference, but I think that an else makes the control flow more obvious. continue remainds me a bit of goto.

private static IEnumerable<Span> CombineAdjacentSpans(IEnumerable<Span> spans)
{
    var combined = new List<Span>();
    var list = spans.OrderBy(s => s.Start); // Drop the ToList(), its not necessary.

    var candidate = list.FirstOrDefault();
    foreach (var span in list.Skip(1))
    {
        if (span.Start <= candidate.End) { // Consider overlapping spans
            candidate.End = span.End;
        } else { // Use an else-clause instead of continue.
            combined.Add(candidate);
            candidate = span;
        }
    }

    if (candidate != null)
        combined.Add(candidate);

    return combined;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback. Regarding the ToList() I used it to avoid potential multiple enumeration, not to use the indexes. Regarding point 2 -> good call. Although I will not encounter overlapping spans, this is far more 'correct' - thanks. Regarding 3) also a valid point, though I can's say that I agree on the 'goto' thing ;) \$\endgroup\$ – Chris Sep 1 '12 at 20:19
  • \$\begingroup\$ Except if you don't use ToList(), sorting the sequence will be done twice (once for FirstOrDefault() and once for the foreach). With a large list, that could make a big difference. \$\endgroup\$ – svick Sep 1 '12 at 20:48

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.