How to structure time specific data so that the most recent point can be found?

Question

This is kinda hard to phrase in a single line questions, but I'm looking for some advice/best practices for structuring data and writing a function in Javascript.

I have several items that change status regularly. My data contains an itemID, timestamp, and status. I am currently structuring it as an array of objects (for each item), with a history priority that contains the timestamps and status. (see below).

I'm looking for a function that will allow me to easily get the status of each object at a given time using the most recent past update. I'm not sure if my data structure will allow for this, or if it does, how to write the function. (for this example I'm going to shorten my timestamps to a 4 digit number)

 var items = [
      { id: 1,
        history: {1234: 'open', 1256: 'in-use', 1289: 'reset', 1293: 'open'},
      { id: 2,
        history: {1230: 'open', 1290: 'in-use'},
      { id: 3,
        history: {1238: 'open', 1241: 'in-use', 1251: 'reset'}
 ]

I'd like to be able to have a function like this:

 getStatus(1260);

and get back

 {1: 'in-use', 2: 'open', 3: 'reset'}

Each id, with the status it was in at the time passed in based on the most recent history record prior to the queried time.

I am not at all attached to this data structure. I also tried having the history an array of objects containing the time and the status, but that means I have to loop through the entire array every time. My biggest problem is that my head is pushing me to an SQL method for doing this, but I'm stuck in client-side Javascript...

My questions: What is the best data structure for this? and How would I go about writing my getStatus() function?

Thanks!

Answer 1

I also tried having the history an array of objects containing the time and the status, but that means I have to loop through the entire array every time.

Not if you had the array sorted, as you then can access the most recent date directly. Also you can use binary search for getting the state at a specific timestamp. With the object you currently have, you always have to enumerate all properties to find the best-matching.

var items = [
  { id: 1,
    history: [
      { timestamp: 1234, status: 'open'},
      { timestamp: 1256, status: 'in-use'},
      { timestamp: 1289, status: 'reset'},
      { timestamp: 1293, status: 'open'}
    ]
  },
  …
];
function index(arr, compare) { // binary search, with custom compare function
    var l = 0,
        r = arr.length - 1;
    while (l <= r) {
        var m = l + ((r - l) >> 1);
        var comp = compare(arr[m]);
        if (comp < 0) // arr[m] comes before the element
            l = m + 1;
        else if (comp > 0) // arr[m] comes after the element
            r = m - 1;
        else // this[m] equals the element
            return m;
    }
    return l-1; // return the index of the next left item
                // usually you would just return -1 in case nothing is found
}
// example:
function insertItem(history, timestamp, status) {
    var i = index(history, function(item) {
        return item.timestamp - timestamp;
    });
    history.splice(i+1, 0, {timestamp: timestamp, status: status});
}

function getStatus(time) {
    var result = {};
    function comparefn (item) {
        return item.timestamp - time;
    }
    for (var i=0; i<items.length; i++) {
        var pos = index(items[i].history, comparefn);
        result[items[i].id] = pos == -1
          ? undefined
          : items[i].history[pos].status;
    }
    return result;
}

Answer 2

You could use a loop:

// for each entry:
var n2 = n;
while (typeof items[n2] == "undefined" && n2 >= -1) {
    n2--;
}
if (n != -1) {returnedArray[idBeingProcessed] = items[n2];}
else {alert("Error handling here");}
// repeat for each item (id 1, id 2...)

This will stop if an answer has been found. It may be inefficient, but hey, it works :-)

Also, consider using an array for your history objects if applicable.