wapshop/node_modules/combine-lists/index.js

var _ = require('lodash');

/** Merge two lists, removing duplicates, and doing everything possible to
 *  maintain the order of the two lists.
 *
 *  This function guarantees that the order of list1 is preserved (that is, if x
 *  comes before y in list1, x comes before y in the returned list) and tries
 *  not to undo the order of list2, though sometimes it is unavoidable.
 *
 *  For example, if we have list1 = [1, 2, 4] and list2 = [2, 1, 3, 4], then the
 *  merged list would be [1, 2, 3, 4], since that preserves the order of list1
 *  while doing the best job possible of preserving the order of list2.
 *
 *  A case like list1 = [1, 3], list2 = [3, 2, 1] is more complicated.  It's not
 *  clear what the best merged list is, but it's probably either [2, 1, 3] or
 *  [1, 3, 2].
 *
 *  In general, it's not totally clear what the "best" merged list is, but there
 *  are some basic properties that anyone would expect:
 *    - Since the order of list1 is preserved, the merged list will look like
 *      list1 with the elements exclusive to list2 inserted in betweeen
 *    - If list2[i] is not in list1, and it is possible to insert list2[i] into
 *      list1 without contradicting the order of list2, then it should be
 *      inserted in such a way
 *
 *  This is very slow, crossing the 100ms mark with lists around 150 in length,
 *  and growing at a rate of
 *  O(list2.length*list2.length*(list1.length + list2.length)) from there.
 *
 *  @param {Array<*>} list1
 *  @param {Array<*>} list2
 *  @return {Array<*>} A list containing all the elements of list1 and list2,
 *      with duplicates removed, the order of list1 preserved, and the order of
 *      list2 partially preserved
 */
module.exports = function(list1, list2) {
  /* This is going to get mathematical.  As noted above, the merged list will be
   * a copy of list1 with the items exclusive to list2 inserted in between.  But
   * additionally, we want to preserve the order of list2 as much as possible.
   * In more formal terms, for all x and y from list2, we want to minimize the
   * number of times that x is before y in the merged list but after y in list2.
   * We call each such time an "inversion", after the term in discrete math.
   *
   * We are going to take a greedy approach to this:
   *
   * merged_list = a copy of list1
   * for(i = 0; i < list2.length; i++)
   *   if(list2[i] is not in list1)
   *     insert list2[i] into merged_list in the earliest place that creates the
   *     minimum number of inversions
   * return merged_list
   *
   * It can be proven that this gives you the two properties mentioned in the
   * header comment above
   */
  var merged = list1.slice(); // The merged list to return
  var mergedIndexes = _.invert(merged);
  for (var i = 0; i < list2.length; i++) {
    var elem = list2[i];
    if (mergedIndexes[elem] === undefined) {
      // Count the inversions for every possible insertion position
      var inversionCnts = typeof Int32Array !== 'undefined' ?
          new Int32Array(merged.length + 1) :
          _.fill(new Array(merged.length + 1), 0);
      for (var j = 0; j < list2.length; j++) {
        var jMergedIndex = mergedIndexes[list2[j]];
        if (j < i) {
          for (var k = 0; k <= jMergedIndex; k++) {
            inversionCnts[k]++;
          }
        } else if (jMergedIndex !== undefined) { // j > i
          for (var k = jMergedIndex + 1; k < inversionCnts.length; k++) {
            inversionCnts[k]++;
          }
        }
      }

      // Pick the earliest place that creates the minimum number of inversions
      var minInversionIndex = 0;
      for (var j = 1; j < inversionCnts.length; j++) {
        if (inversionCnts[j] < inversionCnts[minInversionIndex]) {
          minInversionIndex = j;
        }
      }
      merged.splice(minInversionIndex, 0, elem);
      mergedIndexes = _.invert(merged);
    }
  }
  return merged;
};