function identity(x) { return x; }

function map(arr, f) {
  var out = [];
  for (var i = arr.length; --i >= 0;) { out[i] = f(arr[i]); }
  return out;
}

function reduce(arr, f, opt_initial) {
  var value = opt_initial;
  for (var i = 0, n = arr.length; i < n; ++i) {
    value = f(arr[i], value);
  }
  return value;
}

function filter(arr, pred) {
  var out = [];
  for (var i = 0, k = -1, n = arr.length; i < n; ++i) {
    var x = arr[i];
    if (pred(x)) { out[++k] = x; }
  }
  return out;
}

function range(minIncl, maxExcl) {
  var arr = new Array(maxExcl - minIncl);
  for (var i = maxExcl - minIncl; --i >= 0;) { arr[i] = i + minIncl; }
  return arr;
}

function assert(cond) {
  if (!cond) { throw new Error('assertion failed'); }
}

function reverse(s) { return s.split('').reverse().join(''); }

function commonPrefix(a, b) {
  var n = Math.min(a.length, b.length);
  for (var i = 0; i < n; ++i) {
    if (a.charCodeAt(i) !== b.charCodeAt(i)) { return i; }
  }
  return n;
}

function diff(a, b) {
  var start = commonPrefix(a, b);
  var end = commonPrefix(
      reverse(a.substring(start)), reverse(b.substring(start)));
  return { start: start, end: end, diff: a.substring(start, a.length - end),
           endA: a.length - end, endB: b.length - end,
           match: start === a.length && start === b.length };
}

function js(s) {
  s = '' + s;
  return '\'' + s.replace(/[\r\n\u2028\2029\\\"\']/g, function (ch) { 
      switch (ch) {
        case '\r': return '\\r';
        case '\n': return '\\n';
        case '\u2028': return '\\u2028';
        case '\u2029': return '\\u2029';
        default: return '\\' + ch;
      }
    }) + '\'';
}

function jsArray(strs) {
  return '[' + map(strs, js).join(', ') + ']';
}

function runWhen(action, condition) {
  function attempt() {
    if (condition()) {
      action();
    } else {
      setTimeout(attempt, 100);
    }
  }
  attempt();
}