in-order-unique-union.js

const a = ['a', 'b', 'c', 'd', 'e'];
const b = ['b', 'f', 'a', 'g', 'e'];

const table = {};
const d = [];
var isEqual = (a, b) => {
  if (a.length === b.length) {
    let isEqual = true;
    for (let i = 0; isEqual && i < a.length; ++i) {
      isEqual = a[i] === b[i];
    }
    return isEqual;
  }
  return false;
};
var buildTable = (a, b) => {
  for (let j = 0, l = a.length; j < l; ++j) {
    table[a[j]] = -1;
  }
  for (let j = 0, l = b.length; j < l; ++j) {
    table[b[j]] = j;
  }
};
var isAll = (a, b) => {
  let all = true;
  for (let j = 0; all && j < a.length; ++j) {
    all = table[a[j]] !== -1;
  }
  return all;
};
const unionUnshift = (a, b) => {
  const f = d;
  f.length = 0;
  for (let i = 0; i < b.length; i++) {
    f.push(b[i]);
  }
  f.unshift(a[a.length - 1]);
  for (let i = a.length - 2; i > -1; --i) {
    if (table[a[i]] === -1) {
      f.unshift(a[i]);
    }
  }
  return f;
};
var unionInject = (a, b, lastMissingIndex) => {
  const f = d;
  f.length = 0;
  for (let i = 0; i < b.length; i++) {
    f.push(b[i]);
  }
  for (let i = a.length - 2; i > -1; --i) {
    if (table[a[i]] === -1) {
      f.splice(lastMissingIndex, 0, a[i]);
    }
  }
  return f;
};
var fix = (a, b) => {
  if (a.length === 0) {
    return b;
  }

  if (isEqual(a, b)) {
    return a;
  }

  buildTable(a, b);

  if (isAll(a, b)) {
    return b;
  }

  const lastMissingIndex = table[a[a.length - 1]];
  if (lastMissingIndex) {
    return unionUnshift(a, b);
  }

  return unionInject(a, b, lastMissingIndex);
}

const z = fix(a, b);

const rset=n=>Array.from(new Array(n), ()=>Math.random().toString(16).substring(2));
const randomize = set => {
  set.sort(()=>Math.random()*2-1);
  return set;
};

const e = rset(100);
const f = randomize(e.filter(()=>Math.random() > 0.5).concat(rset(50)));
const g = randomize(e.slice());

var bench=function(fn,n){var s=Date.now();for(var i=0;i<n;++i){fn();}return Date.now()-s;};

// Add noise to table
for (let i = 0; i < 100; ++i) {
  fix(rset(100), rset(100), z);
}

const et = {};
const ft = {};
const gt = {};
bench(()=>fix(e,e),10000);
bench(()=>fix(e,e),10000);
bench(()=>fix(e,e),10000);
bench(()=>fix(e,g),10000);
bench(()=>fix(e,g),10000);
bench(()=>fix(e,g),10000);
bench(()=>fix(e,f),10000);
bench(()=>fix(e,f),10000);
bench(()=>fix(e,f),10000);