Find 'holes' (gaps) in array of date ranges

Question

Given you have an array of date ranges

var arr = [
  {
    "from": 'unix 1st of august',
    "until": 'unix 5th of august'
  },
  {
    "from": 'unix 15th of august',
    "until": 'unix 20th of august'
  },
  {
    "from": 'unix 25th of august',
    "until": 'unix 31th of august'
  }
];

What would be the easiest way to find 'holes' in the time ranges? in this case the 5th until the 15th and the 20th until the 25th is missing.

function findDateRangeHoles() {
  let chunks = [];

  arr.forEach(range => {
     // ??
     chunks.push({from: '?', until: '?'});
  });

  // Return value example, array of object, each holding a missing date range chunk
  [
    {
        from: 'unix 5th of august',
        until: 'unix 15th of august'
    },
    {
        from: 'unix 20th of august',
        until: 'unix 25th of august'
    }
  ]

  return chunks;
}

let missingChunks = findDateRangeHoles(1st of August, 31 of August); // Array of objects

Wonder if momentjs has something for it??

Answer 1

So, after spending many hours.. (Im sorry guys, the given answers didn't give a chunk when no ranges exists for example, so had to keep trying).

But anyway, this what I ended up using.

function getGapsFromRangesArray(from, until, ranges) {
    let chunks = [],
        i = 0, len = ranges.length, range;

    let _from = from;

    // If there are no ranges cached, create one big chunk for entire range.
    if (!len) {
        chunks.push({from: from, until: until});
    } else {

        for (; i < len; i++) {
            range = ranges[i];

            // Cache is complete or from is higher then until, we can stop looping
            if (range.from >= until || (range.from <= from && range.until >= until)) {
                _from = until;
                break;
            }

            // Range hasn't gotten to from date yet, so continue
            if (range.until < from)
                continue;

            // This range is lower then the current _from time, so we can go ahead to its until time
            if (range.from <= _from) {
                _from = range.until;
            }
            // This range is higher then the current _from time, so we are missing a piece
            else {
                console.log('missing piece', new Date(_from), new Date(range.from));
                chunks.push({
                    from: _from,
                    until: range.from
                });
                _from = range.until;
            }
        }

        // Final piece (if required)
        if (_from < until) {
            chunks.push({
                from: _from,
                until: until
            });
        }
    }

    return chunks
}

A data var to use

var testData = [
  {
    "from": 1470002400000, // 1st of August
    "until": 1470780000000 // 10th of August
  },
  {
    "from": 1471212000000, // 15th of August
    "until": 1471644000000 // 20th of August
  },
  {
    "from": 1472076000000, // 25th of August
    "until": 1472594400000 // 31t of August
  }]

And then you can call

getGapsFromRangesArray(1470002400000, 1472594400000, testData);
// missing piece 2016-08-09T22:00:00.000Z 2016-08-14T22:00:00.000Z
// missing piece 2016-08-19T22:00:00.000Z 2016-08-24T22:00:00.000Z

Timezones are screwed indeed and (like @George Jempty also mentioned) I have to take in account if start / end date is included or not .. Bat anyway it works..

Special thanks to @Xotic750 and @Juan Mendes for patience and thinking with me.

p.s. and if anybody needs this for the same reason as I do (lazy loading caching system). Here is a function dat can glue the dates together of the range list, whenever new data is loaded.. This way you keep an efficient record of the data loaded, by time.. You only have to load chunks in the missing date ranges, add the from/until to the ranges list at the right spot, or re-order the range list every time you add a range..

function glueMapDates(list) {
    let prevUntil = null,
        i = 0, len = list.length,
        date;

    for (; i < len; i++) {
        date = list[i];

        // From date matches, glue 2 dates together
        if (date.from === prevUntil) {
            // Set previous until to current until
            list[i-1].until = date.until;

            // Remove current date from the list
            list.splice(i, 1);

            // Set the loop back 1 counter
            i--;
            len--;
        }

        prevUntil = date.until;
    }

    fs.writeFileSync(PATH_MAP_FILE, JSON.stringify(map, null, 2));
}

Answer 2

Here is another example in ES6, hopefully you will be able to see why it is so important to have some test data and know the expected outcome, and always show what you have tried.

The output doesn't match your human readable ranges, you need to think about that and adjust your expectations or adjust the code to match your expectation, I'll leave that exercise to you.

// Unix time is in seconds since the Epoch, Javascript is milliseconds
// Date input UTC
// Month is zero indexed 0-11
// Time is 00:00:00.000
function getUnixTime(year, month, day) {
  return Date.UTC(year, month, day) / 1000;
}
// Your example data for 2016
// You state that your data is sorted by `from`
const ranges = [{
  from: getUnixTime(2016, 7, 1),
  until: getUnixTime(2016, 7, 5)
}, {
  from: getUnixTime(2016, 7, 15),
  until: getUnixTime(2016, 7, 20)
}, {
  from: getUnixTime(2016, 7, 25),
  until: getUnixTime(2016, 7, 31)
}];

// Calculate `holes`
let previousRange;
const holes = [];
for (let range of ranges) {
  if (previousRange && previousRange.until < range.from) {
    // Add and substract 1 second to get `hole` and store
    holes.push({
      from: previousRange.until + 1,
      until: range.from - 1
    });
  }
  previousRange = range;
}
console.log('holes object: ', holes);

// Convert `holes` into human readable UTC string
function unixTimeToJavascriptUTC(seconds) {
  return new Date(seconds * 1000).toUTCString();
}
for (let hole of holes) {
  const from = unixTimeToJavascriptUTC(hole.from);
  const until = unixTimeToJavascriptUTC(hole.until);
  console.log(`From: ${from}, Until: ${until}`);
}

Answer 3

Here's an example, but in the future, you should post a real attempt, what you have posted does not show that you have tried it.

Sort them and compare the end of range a with the beginning of range b, as numbers. After you do that, convert the from and untils that you have created into date ranges

// Assuming they are sorted
var ranges = [{
  from: 946702800, // +new Date(2000, 0, 1) / 1000
  until: 949381200 // +new Date(2000, 1, 1)
},{
  from: 954565200,
  until: 957153600
},{
  from: 962424000,
  until: 965102400
}];

var holes = [];

for (var i=1; i < ranges.length; i++) {
  var beginningOfHole = ranges[i-1].until;
  var endOfHole = ranges[i].from;
  if (beginningOfHole < endOfHole) {
    holes.push({from: beginningOfHole + 1, until: endOfHole - 1});
  }
}

console.log('holes in ranges', holes.map(hole => ({
    from: new Date(hole.from * 1000), // Convert unix timestamp into JS timestamp
    until: new Date(hole.until * 1000)
})));