sublist.js

sublist.js

#!/usr/bin/env node

/**
 *
 * Utility function to not become the code more confuse
 *
 * Iterates over an array with a advantage of reset the
 * iterator and start again in the first element of the array 
 * increasing the initial index to one
 *
 * Ex:
 * var iterator = subsequentIterator([1,2,3,4]);
 *
 * while(iterator.canRetry()) {
 *   while(iterator.hasNext()) {
 *     var elem = iterator.next();
 *     console.log(elem);
 *   }
 *   iterator.retry();
 * }
 *
 * // outputs
 * 1
 * 2
 * 3
 * 4
 * 2
 * 3
 * 4
 * 3
 * 4
 *
 */

function subsequentIterator(array) {
  return {
    initialIndex: 0,
    index: 0,
    next: function() {
      return array[this.index++];
    },
    hasNext: function() {
      return this.index < array.length;
    },
    canRetry: function() {
      return this.initialIndex < array.length;
    },
    retry: function() {
      this.initialIndex++;
      this.index = this.initialIndex;
    }
  }
}

function compare(source, target) {
  // the simple scenario
  if(source.length === target.length) {
    if (arrayEquals(source, target)) {
      return "equal";
    } else {
      return "unequal";
    }
  }

  var mark = "sublist";
  // we always make the comparison from the lesser array to the greater
  // but we change the mark flag to _remember_ what array is inside of the other
  if(source.length > target.length) {
    mark = "superlist";
    var tmp = source;
    source = target;
    target = tmp;
  }

  return do_compare(source, target, mark);
}

function do_compare(source, target, mark) {
  // we enumerate each element from target and compare with each element of source
  // but if source doesn't match the range of elements in target, we need to reset
  // the target enumeration starting from the first element at index+1, to do a
  // properly comparison
  var iterator = subsequentIterator(target);
  while(iterator.hasNext()) {
    var allMatch = source.every(function(item) {
      return item === iterator.next();
    });
    if (allMatch) { return mark; }
    else { iterator.retry(); }
  }
  return "unequal";
}

// simple array equality with one depth level
function arrayEquals(a, b) {
  for (var i = 0, l = a.length; i < l; i ++) {
    for (var j = 0, l = b.length; j < l; j ++) {
      if(i === j && a[i] !== b[j]) { return false }
    }
  }
  return true;
}

// based on elixir sublist_test
console.log(compare([], []) === "equal");
console.log(compare([], [null]) === "sublist");
console.log(compare([null], []) === "superlist");
console.log(compare([1], [2]) === "unequal");
console.log(compare([1,2,3,4], [1,2,3,4]) === "equal");
console.log(compare([1,2,3], [1,2,3,4,5]) === "sublist");
console.log(compare([3,2,1],[5,4,3,2,1]) === "sublist");
console.log(compare([3,4,5],[1,2,3,4,5]) === "sublist");
console.log(compare([1,1,2], [1,1,1,2]) === "sublist");
console.log(compare([1,2,3,4], [3,4,5,6]) === "unequal");
console.log(compare([1,2,3,4,5],[1,2,3]) === "superlist");
console.log(compare([5,4,3,2,1],[3,2,1]) === "superlist");
console.log(compare([1,1,1,2], [1,1,2]) === "superlist");
// console.log(compare([1], [1.0, 2]) === "unequal"); The 1 === 1.0 is evaluated to true, and don't want to bother with it
console.log(compare([1,2,1,2,3], [1,2,3,1,2,1,2,3,2,1]) === "sublist");
console.log(compare([1,2,1,2,3], [1,2,3,1,2,3,2,3,2,1]) === "unequal");