Ensuring Sequence of Events in an Array

By Posted on

Problem

The Problem

I’m asking to see if there are methodically better solutions to this problem. The situation is as follows, I am receiving an array of events, they are marked by timestamp and there is a designated order of events. That is, that after every event of type a, there should always be a corresponding event b.

Due to how the server batches events, there is a chance that other event types with the same timestamp can corrupt this sequence. I would like to restore it.

The data structure is as follows,

[ { type: string, timestamp: number }, ]

As mentioned beforehand, I would like to ensure that every event of type ‘a’ is followed immediately by a type ‘b’ event. 

const events = [
  { type: 'a', timestamp: 1 },
  { type: 'c', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'c', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'b', timestamp: 2 },
];

The target sequence would be as follows:

const sortedEvents = [
  { type: 'a', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'c', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'c', timestamp: 2 },
];

My Solution

My immediate approach to this is the following: 

// Check if the next event for this item is of correct type
const nextIsCorrect = (arr, idx) => (arr[idx].type === 'a') && (arr[idx+1] && arr[idx+1].type === 'b');

// Build list of partnered events
const indices = events.reduce((prev, event, idx, arr) => {
  if (nextIsCorrect(arr, idx)) {
    return prev;
  }

  if (event.type === 'a') {
    prev.push([() => arr.indexOf(event)]);
  }

  if (event.type === 'b') {
    const precedingEvent = prev.find(el => {
      return (el[0] && !el[1]);
    });

    precedingEvent && precedingEvent.push(() => arr.indexOf(event));
  }

  return prev;
}, []);

// Rearrange
indices.forEach(set => {
  const from = set[1]();
  const target = set[0]() + 1;

  events.splice(target, 0, events.splice(from, 1)[0]);
});

I think this is an okay solution, but I can’t help feel there is a much better approach eluding me.

Solution

Hard coding

Is too easy…

The first problem I see is that the sorting has the event type hard coded into the function.

I feel that hard coding any type of data into code is bad practice. At minimum if hard coding values is unavoidable the values should be defined as a constant and placed in a common location in the source file.

The problem with hard coding is the inevitable need to change or add to the hard coded items. This is a difficult process when the values are scattered in the code, and usually not easy to find as they are not unique.

For a simple fix I would add

const eventTypes = { a : "a", b : "b" };  // at the top of the source file
                               // or in a common file, and as close
                               // to the required scope as possible
                               // as to not be in global

Then in the code

if(event.type === eventTypes.a){  ...
if(event.type === eventTypes.b){  ...

Thus if you want to change you do so where you define the const and if you need to change the code you can us refactor tools to locate the unique types in your code base.

Using data given.

Better yet is to avoid the constants all together and use the data in the array items. You can compare strings with "stringA" < "stringB" is true. Javascript uses the strings char codes to evaluate the condition, that means that "stringa" < "stringB" is false as lowercase characters have a higher character code than capitals.

So assuming that event types are all lowercase you can sort the events with a standard sort function.

Thus the steps would be

  1. Sort all events by time.
  2. Reduce the events array to event type, adding an array of times to each type.
  3. Sort the reduced events by type.
  4. Empty events array and reconstruct events using the following method.
  5. From the lowest time search the reduced array for matching times. Add to the events array matching time and associated type. Removing time from type if more than one time, and or remove type if only one time for type, until reduced array is empty.

Testing

The data set you have given, is very limited and thus the problem is a little ambiguous. To ensure that the function works you should provide data with at least every combination of possible data combinations (Not all combinations “abc” is the same as “gef” but different than “aac” and “abca” ) that will affect the ordered result.

Sometimes testing can not test all possible input possibilities as the number of tests is so large to be impractical. The best way to deal with such is to create randomised data and do a statistical test. You can not prove the function will not fail, you can prove it will.

in other words…

You can then say your function has only a small statistical chance of failure if you don’t get a fail. If you get any fail then your function is known to fail and should be fixed.

I used a random test (as I am can’t be bothered doing a complete test, and i Imagine it most matches the expected input) to test the function. Your function failed on the very first random test with a typeError (I did not examine the details)

The other answer given by GerritO also failed incorrectly ordering most test inputs.

An example of test data that fails

const events = [
  { type: 'a', timestamp: 1 },
  { type: 'a', timestamp: 4 },
  { type: 'a', timestamp: 3 },
  { type: 'c', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'c', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'b', timestamp: 2 },
];


//or
  [{ type: 'a', timestamp: 1 },
  { type: 'g', timestamp: 4 },
  { type: 'a', timestamp: 3 },
  { type: 'b', timestamp: 2 },]

A more robust function.

The rewrite has made a few assumptions, and has been tested on a huge set of random inputs without failing (no fail in over 10 million random input tests). That does not mean it does what you want, it does what I guessed you want. Order events by time, in same time groups, order events in alphabetical groups

Rather than modify the existing array I have created a new array to hold the results.

// test data example
const events = [
  { type: 'a', timestamp: 1 },
  { type: 'g', timestamp: 4 },
  { type: 'a', timestamp: 3 },
  { type: 'h', timestamp: 5 },
  { type: 'c', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'c', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'g', timestamp: 3 },
  { type: 'b', timestamp: 2 },
  { type: 'e', timestamp: 3 },
  { type: 'f', timestamp: 1 },
  { type: 'f', timestamp: 3 },
  { type: 'h', timestamp: 5 },
  { type: 'f', timestamp: 3 },
  { type: 'f', timestamp: 3 },
];

/* Please note this uses compact style. Single block statements are followed
   by `{ code }` when under 80 chars (tab 2). No `;` is added to comply with 
   JSLint rule Semicoloans must be followed by newline. */
   
function reorderEvents(events){
    /* global to this function variables */
    // timeClear is flag to indicate that there are no events at the current event time
    // eventTime is the current event time to add to result
    var timeClear, eventTime, eIdx = 0; // index into ev arrray

    /* Functions global to this function */
    const typeSort = (a, b) => a.type < b.type ? -1 : a.type > b.type ? 1 : 0;
    const getEvent = () => {                        // gets event matching eventTime from reduced events
        if (ev[eIdx].times[0] === eventTime){       // does the event match the event time 
            timeClear = false;                      // flag that it is unknown if there are more times at eventTime
            if (ev[eIdx].times.length === 1) {      // is this the only time for event
                const event = ev.splice(eIdx,1)[0]; // remove from array
                return { type : event.type, timestamp : event.times[0] }; // return the event
            }
            return { type : ev[eIdx].type, timestamp : ev[eIdx++].times.shift() }; // remove the time
        } else { eIdx ++ } // skip the event as not at the event time
    }    
    
    const orderedEvents = [];   // Will hold the results and is returned by this function
    const reduced = new Map();  // holds events type as key and array of event times per key
    
    // We dont want to mess with the original array and as sorts are in place we need to copy the array
    events = [...events];
    events.sort((a,b) => a.timestamp - b.timestamp );  // Order events by time
    
    // reduce events to type
    events.forEach((event) => {
        const existing = reduced.get(event.type);
        if (existing === undefined) {
            reduced.set( event.type, { type : event.type, times : [event.timestamp] });
        } else { existing.times.push(event.timestamp) }
    });
    
    // get the reduced events from the Map and sort by type 
    const ev = [...reduced.values()].sort(typeSort);
    timeClear = true;    // first pass the abstract previouse pass is clear
    
    // remove all events in order of time
    while (ev.length > 0) {
        if (eIdx === 0) { // if this the first item
            if (timeClear) { eventTime = ev[0].times[0] }  // get next time
            else { timeClear = true }  // clear flag and do another pass
        }
        const event = getEvent();
        if (event !== undefined) { orderedEvents.push(event) }
        eIdx = eIdx === ev.length ? 0 : eIdx ; // goto start when past end
    }
    return orderedEvents;
}
// To avoid console log function
function log(data) {
    const d = document.createElement("div");
    d.textContent = data.toString();
    document.body.appendChild(d);
}
const ordered = reorderEvents(events);
ordered.forEach(i => log(i.type + " : " + i.timestamp));

Expand snippet

Assuming that b events cannot be encountered before the a event that they must be matched too, here is an alternative implementation that requires only one pass through the array.

I am not completely happy with this, but I believe it is simpler than the original solution. It will fail if the events array contains an event of type a without an event of type b following it (The original function will as well, so this may not be an issue).

const events = [
  { type: 'a', timestamp: 1 },
  { type: 'c', timestamp: 1 },
  { type: 'b', timestamp: 1 },
  { type: 'a', timestamp: 2 },
  { type: 'a', timestamp: 2 },
  { type: 'c', timestamp: 2 },
  { type: 'b', timestamp: 2 },
  { type: 'b', timestamp: 2 },
];

function sortEvents(events) {
  // Since events will be modified, copy it
  events = events.slice()
  let sorted = []
  
  // While there are still events which have not been sorted
  while(events.length) {
    // Get the first event and add it to the sorted list
    let event  = events.shift()
    sorted.push(event)
    // If the event requires an event to occur after it
    if (event.type === 'a') {
      // Find the event that should be next
      let index = events.findIndex(e => e.type === 'b')
      // Add the event, removing it from the current queue
      sorted.push(...events.splice(index, 1))
    }
  }

  return sorted;
}

console.log(sortEvents(events));

Expand snippet

Leave a Reply

Your email address will not be published. Required fields are marked *