How to structure temporary data so that you can find the latest point?

Question

It's pretty hard to put in a single line of questions, but I'm looking for some recommendations / best practices for structuring data and writing functions in Javascript.

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

I am looking for a function that will allow me to easily get the status of each object at a given time using the latest latest update. I am not sure if my data structure will allow this, or if this happens, how to write a function. (for this example, I'm going to reduce the 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 would like to have a function like this:

  getStatus(1260); 

and come back

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

Each identifier with the status in which it was at the time that passed in accordance with the most recent historical record before the requested time.

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

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

Thanks!

Answer 1

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

Not if you sorted the array, as you can directly access the most recent date. You can also use binary search to get state with a specific timestamp. With the object that you are currently using, you always need to list all the properties in order to find the best match.

 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 can 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 is found. It may be inefficient, but hey, it works :-)

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