Remove gaps between non-overlapping segments of an array of time elements

Question

I have an array of elements, each with a start time and an end time.

These form a timeline, some of which overlap, and others that do not (and have a gap between groups of overlapping elements).

I written some code that removes the gaps between the non-overlapping elements (red lines as per the image below) however it is starting to get messy and not catching edge cases.

Does an algorithm exist already that will remove the red gaps and shift everything up neatly?

My code stab is below:

// sort by time, lowest to highest
entries.Sort((a, b) => a.TimeOffset.CompareTo(b.TimeOffset));

var lookingForFirstGap = true;
var storedOffset = 0.0;
var indexToTrimFrom = 0;

for (var i = 0; i < entries.Count -1; i++ )
{
    // var previous = entries[i-1];
    var current = entries[i];
    var next = entries[i+1];

    // var distanceBack = previous.TimingsAbsolute.End - current.TimingsAbsolute.Start;
    var distanceForward = next.TimingsAbsolute.Start - current.TimingsAbsolute.End;

    Console.WriteLine("Distance {0} -> {1} is {2}", i, i+1, distanceForward);

    if (!(distanceForward > 0))
        continue;

    if (lookingForFirstGap)
    {
        indexToTrimFrom = i + 1;
        Console.WriteLine("To trim from " + indexToTrimFrom);
        storedOffset = distanceForward; // we have found a gap, store the amount
        lookingForFirstGap = false; // now start looking for element where there is a gap after it
    }
    else
    {
        var indexToTrimTo = i;

        for (var x = indexToTrimFrom; x <= indexToTrimTo; x++)
        {
            // trim all
            Console.WriteLine("Adjust [" + x + "] by " + storedOffset);
        }

        if (distanceForward > 0)
        {
            indexToTrimFrom = i + 1;
            Console.WriteLine("To trim from " + indexToTrimFrom);
            storedOffset = distanceForward; // we have found a gap, store the amount
        }
        else
            lookingForFirstGap = true; // start looking for gap again
    }
}

Answer 1

You're trying to do too much in one loop. Subtracting the gaps is difficult because it's difficult to identify the gaps. Identifying the gaps is difficult because of all the weird ways the intervals overlap, so remove the overlapping interval problem first.

Make one pass to flatten the intervals, using an algorithm from this question. Then one pass to make a list of gaps, which should be very simple with the flattened list.

Now you're ready to loop through your original list of intervals. For each interval, see how many gaps occur before it, and subtract the cumulative time of each.

Answer 2

Posting this as the code, @Karl helped me realise splitting this up made it much easier! SOLID principles enables much easier code.

List<Tuple<int, int>> FindGaps(List<LogEntry> entries)
{
    var gaps = new List<Tuple<int, int>>();

    for (var i = 0; i < entries.Count - 1; i++)
    {
        var current = entries[i];
        var next = entries[i + 1];

        var distanceForward = next.TimingsAbsolute.Start - current.TimingsAbsolute.End;

        if (!(distanceForward > 0)) // there is no gap to the next element, continue
            continue;

        gaps.Add(new Tuple<int, int>(i, i+1)); // otherwise, we have found a gap...
    }

    return gaps;
}

List<Tuple<int, int>> FindContiguous(List<Tuple<int, int>> gaps, int totalLength)
{
    var previous = 0;
    var lastIndex = totalLength - 1;

    var contiguous = new List<Tuple<int, int>>();

    foreach (var gap in gaps)
    {
        contiguous.Add(new Tuple<int, int>(previous,gap.Item1));

        previous = gap.Item2;
    }

    if (previous != lastIndex)
    {
        contiguous.Add(new Tuple<int, int>(previous,lastIndex));
    }

    return contiguous;
}


List<LogEntry> RemoveGaps(List<LogEntry> entries, List<Tuple<int, int>> contiguous)
{
    var newList = new List<LogEntry>();

    var totalShift = 0.0;
    LogEntry previousLast = null;

    foreach (var seq in contiguous)
    {
        var startIndex = seq.Item1;
        var endIndex = seq.Item2;

        if (previousLast != null)
        {
            totalShift += entries[startIndex].TimingsAbsolute.Start - previousLast.TimingsAbsolute.End;
        }

        previousLast = entries[endIndex];

        for (var i = startIndex; i <= endIndex; i++)
        {
            var entry = entries[i];

            newList.Add(
                new LogEntry(
                    entry.Url,
                    entry.Status,
                    entry.HeaderSize,
                    entry.PayloadSize,
                    entry.TimeOffset-totalShift,
                    entry.Timings.Blocked,
                    entry.Timings.Dns,
                    entry.Timings.Connect,
                    entry.Timings.Ssl,
                    entry.Timings.Send,
                    entry.Timings.Wait,
                    entry.Timings.Receive,
                    entry.ConnectionId));    
        }
    }

    return newList;
}

public void Generate(List<LogEntry> entries, Guid testId)
{
    // sort by time, lowest to highest
    entries.Sort((a, b) => a.TimeOffset.CompareTo(b.TimeOffset));

    // get a list of contigous elements
    var contiguous = FindContiguous(FindGaps(entries), entries.Count);

    // now remove the gaps between the contiguous sequences of elements 
    var list = RemoveGaps(entries, contiguous);
}