6
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Your nextIsCorrect has hard-coded types. Won't this lead to problems with scalability? \$\endgroup\$
    – Mast
    Sep 19 '17 at 18:12
  • \$\begingroup\$ Is it possible for b events that should happen after a events to be received before the a event? \$\endgroup\$
    – Gerrit0
    Sep 19 '17 at 23:21
  • \$\begingroup\$ How big are the batches from the server, generally? Will timestamps ever be split across batches? \$\endgroup\$
    – BenC
    Sep 20 '17 at 0:18
3
\$\begingroup\$

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)); 

\$\endgroup\$
2
  • \$\begingroup\$ Thanks, this is an excellent answer, I've learned quite a bit from reading over it. It doesn't quite do what I had tried to explain, but that is mostly down to me, I've marked this as the best regardless. The data I have given was very poor in retrospect, 'abc' was not the best choice for example events. If you were to imagine the events as receive_data, parse_data, and post_datait would give a better idea of what has to be done. receive_data should always be immediately followed by parse_data. \$\endgroup\$
    – Ryan Park
    Sep 20 '17 at 13:10
  • \$\begingroup\$ Since the OP states "ensure that every event of type a is followed immediately by a type b event" In this case I think it's safe to assume that this will be true in this case. That said, your answer is a better solution if this is not always the case. I would avoid hard coding the event structure besides what is necessary. (If events also have a property message this will clear it.) \$\endgroup\$
    – Gerrit0
    Sep 20 '17 at 13:11
1
\$\begingroup\$

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));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.