Fill missing data in between available data with default value

Question

My raw data has values on some random times:

const rawData = [
  {hour: 3, value: 3} ,
  {hour: 5, value: 9} ,
  {hour: 10, value: 5} ,
] as const 

I would like to fill all missing hours as having value 0:

const processedData = [
  { hour: 3, value: 3 },
  { hour: 4, value: 0 },
  { hour: 5, value: 9 },
  { hour: 6, value: 0 },
  { hour: 7, value: 0 },
  { hour: 8, value: 0 },
  { hour: 9, value: 0 },
  { hour: 10, value: 5 }
]

Here is my code:

function fillEmptyData(data: typeof rawData) {
  const processedData = [] 
  for (const iString in data) {
    const i = parseInt(iString)
    processedData.push(data[i])
    
    if (data[i+1]===undefined || data[i].hour + 1 === data[i+1].hour) {
      continue
    } else {
      const currentHour = data[i].hour
      const nextAvailableHour = data[i+1].hour
      const gap = nextAvailableHour - currentHour
      const emptyHours = Array(gap-1).fill().map((_, i) => i+currentHour+1)
      for (const emptyHour of emptyHours) {
        processedData.push({
          hour: emptyHour,
          value: 0
        })
      } 
    } 
  } 
  return processedData
} 
console.log(fillEmptyData(rawData))

Is there anything in this code that may be improved?

Answer 1

sorted input

function fillEmptyData(data: typeof rawData) {

I don't believe typeof rawData makes any sorting guarantees.

Apparently there's a pre-condition where caller promises to only offer sorted data. But this is not made explicit anywhere, not in the type, not in the function name, not in its (missing!) documentation, not in code which sorts or verifies a monotonic order. It really needs to be made explicit.

nit: I would find this guard

    if (data[i+1]===undefined || data[i].hour + 1 === data[i+1].hour) {

slightly easier to read if expressed like this

    if (data[i+1]===undefined || data[i+1].hour === data[i].hour + 1) {

or this

    if (data[i+1]===undefined
     || data[i+1].hour === data[i].hour + 1) {

I confess I am more accustomed to loops that pay attention to length of data so they avoid running off the end. Here, type safety saves us since it would be Bad if caller managed to pass in an undefined element.

algorithm

I find coping with multiple gaps more complex than necessary. Consider adopting the following approach.

Find the minimum and maximum, a start and end hour. Point an index at element zero. Now it's just a matter of looping over the start .. end closed interval, producing another processedData entry per hour.

• If the current indexed entry matches hour emit the entry and bump the index.
• Else synthesize a zero-valued entry.

Having a single outer for loop iterate through each required output hour makes it easy to reason about the returned datastructure and its expected length.

test suite

Consider adding an automated test which "knows the right answer" so it can display a Green bar. You might for example begin with $ npm install jest

Answer 2

The first thing that you'll want to do is to define a type for the elements in your array. Using as const here is an odd choice.

type Datum = { hour: number, value: number }
const rawData: Datum[] = [
  {hour: 3, value: 3} ,
  {hour: 5, value: 9} ,
  {hour: 10, value: 5} ,
]

Not using semi-colons isn't my preference but at least you're consistent with it.

It looks like you're trying to avoid for loops, possibly due to the as const on your input giving you a different type than you're expecting.

I'd like to propose an alternate implementation for you to think about. It looks backwards rather than forwards which makes bounds checking easier.

function fillEmptyData(data: typeof rawData) {
  const processedData: Datum[] = []
  if (!data || data.length === 0) {
     return processedData
  }
  processedData.push(data[0])
  for (let i = 1; i < data.length; i++) {
    const datum = data[i]
    const previousHour = processedData[processedData.length - 1].hour
    const delta = datum.hour - previousHour
    if (delta > 1) {
        for (let j = 1; j < delta; j++) {
            processedData.push({
                hour: previousHour + j,
                value: 0
            })
        }
    }
    processedData.push(datum)
  }
  
  return processedData;
} 

Answer 3

Your approach seems a bit overcomplicated. I'd choose either Array() or a loop, but not both. In this case, Array feels a little too clever, so a classic for loop seems sufficient.

JS isn't a pure language like Haskell, so you can mutate state. This is one of those times where it's a nice simplification, avoiding awkward indexing, slicing and "zipping" (joining parallel arrays) as would be done in a functional, immutable approach. Specifically, you can keep track of the last hour for comparison against the current one. Here's how that might look:

/**
 * @typedef {Object} HoursData - Represents an entry containing hour-value data.
 * @property {number} hour - The hour of the entry.
 * @property {number} value - The value associated with the hour.
 */

/**
 * Fills missing hours in a series of hour-value entries.
 * @param {HoursData[]} hours - A series of hour-value entries sorted ascending by hour.
 * @returns {HoursData[]} - A copy of the hours with gaps filled.
 */
const fillMissingHours = hours => {
  const result = [];
  let last;

  for (const entry of hours) {
    for (let i = last + 1; i < entry.hour; i++) {
      result.push({hour: i, value: 0});
    }

    result.push({...entry});
    last = entry.hour;
  }

  return result;
};

const rawData = [
  {hour: 3, value: 3},
  {hour: 5, value: 9},
  {hour: 10, value: 5},
];
console.log(fillMissingHours(rawData));

I used JSDoc instead of TS so this is runnable in the browser, but I assume you have the TS types handled already.

I'll admit, this is a wee bit clever because I'm relying on the fact that undefined + 1 is NaN which is greater than all other numbers. This means I don't need to use if (last !== undefined) {} around the C-style for loop. Feel free to add that if you prefer.

Other tips:

• Use standard formatting with Prettier (avoid smushed together expressions like i+currentHour+1 and extra spacing like {hour: 10, value: 5} ,).

• Avoid using the type in the variable name, so iString should be named what it is only. i generally means "index" so I'd avoid that in the name too.

• Your code only works when the input is pre-sorted. That's fine but needs to be documented as an invariant.

• Don't use in to iterate arrays because it has gotchas you can read about in the docs. Prefer for ... of.

• Compute the final value once when possible. Consider these lines:

  const gap = nextAvailableHour - currentHour
  const emptyHours = Array(gap-1)
  

  It's great that you've broken out a variable gap, but since it's only used this one time, I'd compute its final value up front:

  const gap = nextAvailableHour - currentHour - 1
  const emptyHours = Array(gap)
  

  This is a subtle distinction, but it's good practice to keep things in one place and be transparent about variables. Otherwise, the code reads like "The gap is nextAvailableHour - currentHour. Just kidding, it's actually - 1 that thing I just wrote on the previous line.".

• Write a test suite to validate the logic thoroughly. This is the sort of function that can have a lot of edge cases. I was lazy and didn't test this, so if there's a bug, that only proves my point.

Good points:

• You're using ===.
• You have a clear function name.
• Your code passes ESLint.

Note that your input doesn't quite match your code, which is doing some parsing that doesn't appear necessary since you've shown a pre-parsed array/object data structure. I'm going to assume that's the right input. If you need to parse strings, you can do that as a preliminary step. Use JSON.parse() if the input is JSON rather than rolling your own parser.

As a final item, here's my solution with Array() for comparison. Note that I'm using .push(...[]) to avoid the explicit inner loop.

const fillMissingHours = hours => {
  const result = [];
  let last;

  for (const entry of hours) {
    if (last !== undefined) {
      const fill = [...Array(entry.hour - last - 1)]
        .map((_, i) => ({hour: last + i + 1, value: 0}));
      result.push(...fill);
    }

    result.push({...entry});
    last = entry.hour;
  }

  return result;
};

const rawData = [
  {hour: 3, value: 3},
  {hour: 5, value: 9},
  {hour: 10, value: 5},
];
console.log(fillMissingHours(rawData));

This actually isn't too bad, but you can probably see why I went with the simpler syntax in my recommendation.

Answer 4

Here is my final code, which:

• applies J_H's advice on finding the min and max time value and iterate them
• accepts data with any time unit
• be able to work with unsorted input data

type Data = {date: Date, value: number}[]
type Unit = 'hour'|'day'|'week'|'month'|'year'

const input: Data = [
  { date: new Date(), hit: 3 },
  { date: new Date((new Date()).getTime() + 18000000), hit: 45 },
  { date: new Date((new Date()).getTime() + 36000000), hit: 534 },
],

function addTime(startDate: Date|string|number, quantity: number, unit: Unit) {
  let date: Date
  typeof startDate === 'string' || typeof startDate === 'number' ? date = new Date(startDate) : date = startDate
  switch (unit) {
    case "hour":
      return new Date(date.setHours(date.getHours() + quantity));
    case "day":
      return new Date(date.setDate(date.getDate() + quantity));
    case "week":
      return new Date(date.setDate(date.getDate() + 7 * quantity));
    case "month":
      return new Date(date.setMonth(date.getMonth() + quantity));
    case "year":
      return new Date(date.setFullYear(date.getFullYear() + quantity));
  }
}

function addMissingData(data: Data, unit: Unit ) {
  const result = [];
  const dates = data.map((i) => i.date.getTime());
  const minDate = Math.min(...dates)
  const maxDate = Math.max(...dates)

  let i = minDate
  while (i <= maxDate) {
    if (dates.includes(i)) {
      const a = data.filter((j) => j.date.getTime() === i);
      console.assert(a.length === 1) 
      result.push(a[0])
    } else {
      result.push({
        date: new Date(i),
        hit: 0,
      });
    }
    i = addTime(i, 1, unit).getTime()
  }
  return result;
}

I have to convert the dates to numbers with getTime() because comparing 2 date objects compares their references and not their values.

Answer 5

Utility functions

These types of problems help you build your set of useful functions.

In this case mapBy will create a Map or extend an existing Map, by a given field name.

    const mapBy = (data, fieldName, map = new Map()) => {
        for (const item of data) { map.set(item[fieldName], item); }
        return map;
    }

And getMinMax. Rather than sort the input data we need only the min and max values of a given field. Another function that is very reusable.

    const getMinMax = (data, fieldName) => {
        const vals = data.map(item => item[fieldName]);
        return [Math.min(...vals), Math.max(...vals)];
    }

Simplified the problem

With the above two functions padding the array of objects is easy. Rather than hard code the field names and the data to pad you can pass this to the function. Eg padBetween(rawData, "hour", {value: 0})

Though overall the source code is a little more complex (more lines), its complexity remains linear \$O(n)\$ (because we don`t need to sort) where \$n\$ is the number of items from min to max sequentially inclusive.

const data = [
  {hour: 3, value: 3} ,
  {hour: 5, value: 9} ,
  {hour: 10, value: 5} ,
];
const mapBy = (data, fieldName, map = new Map()) => {
    for (const item of data) { map.set(item[fieldName], item); }
    return map;
}
const getMinMax = (data, fieldName) => {
    const vals = data.map(item => item[fieldName]);
    return [Math.min(...vals), Math.max(...vals)];
}

const padBetween = (data, fieldName, padding = {}) => {
    const byField = mapBy(data, fieldName), res = [];
    var [min, max] = getMinMax(data, fieldName);
    while (min <= max) {
        res.push(byField.get(min) ?? {[fieldName]: min, ...padding});
        min ++;
    }
    return res;
}
console.log(padBetween(data, "hour", {value: 0}));