3

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.

red gaps

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
    }
}
  • Are you ordering by start or end time? – Ewan Sep 24 '16 at 20:13
  • 1
    Do you want to add the time of the gap to the previous element? Why not just set the end-time of the previous element to the start time of the next element unless there's overlap? – Pieter B Sep 24 '16 at 22:40
  • You are not telling what you want to do with the gaps. Don't make us reverse engineer your code to find out. – Jan Doggen Sep 25 '16 at 14:37
  • each orange block is an array element (ordered by start time) which has a start and end time... some blocks overlap (in time) whereas others do not and there is a gap in time (the red line which indicates the duration), I would like to remove all the gaps (red lines) so that they butt up neatly together (but only the closest elements to the gap should align). – morleyc Sep 25 '16 at 19:42
2

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.

| improve this answer | |
  • Thanks @Karl splitting this up for sure made it easier to tackle, have posted the code i used below. – morleyc Sep 29 '16 at 22:55
1

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);
}
| improve this answer | |

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.