d3.interpolate = function(a, b) {

  var i = d3.interpolators.length, f;

  while (--i >= 0 && !(f = d3.interpolators[i](a, b)));

  return f;

};

d3.interpolateNumber = function(a, b) {

  b -= a;

  return function(t) { return a + b * t; };

};

d3.interpolateRound = function(a, b) {

  b -= a;

  return function(t) { return Math.round(a + b * t); };

};

d3.interpolateString = function(a, b) {

  var m, // current match

      i, // current index

      j, // current index (for coallescing)

      s0 = 0, // start index of current string prefix

      s1 = 0, // end index of current string prefix

      s = [], // string constants and placeholders

      q = [], // number interpolators

      n, // q.length

      o;

  // Reset our regular expression!

  d3_interpolate_number.lastIndex = 0;

  // Find all numbers in b.

  for (i = 0; m = d3_interpolate_number.exec(b); ++i) {

    if (m.index) s.push(b.substring(s0, s1 = m.index));

    q.push({i: s.length, x: m[0]});

    s.push(null);

    s0 = d3_interpolate_number.lastIndex;

  }

  if (s0 < b.length) s.push(b.substring(s0));

  // Find all numbers in a.

  for (i = 0, n = q.length; (m = d3_interpolate_number.exec(a)) && i < n; ++i) {

    o = q[i];

    if (o.x == m[0]) { // The numbers match, so coallesce.

      if (o.i) {

        if (s[o.i + 1] == null) { // This match is followed by another number.

          s[o.i - 1] += o.x;

          s.splice(o.i, 1);

          for (j = i + 1; j < n; ++j) q[j].i--;

        } else { // This match is followed by a string, so coallesce twice.

          s[o.i - 1] += o.x + s[o.i + 1];

          s.splice(o.i, 2);

          for (j = i + 1; j < n; ++j) q[j].i -= 2;

        }

      } else {

          if (s[o.i + 1] == null) { // This match is followed by another number.

          s[o.i] = o.x;

        } else { // This match is followed by a string, so coallesce twice.

          s[o.i] = o.x + s[o.i + 1];

          s.splice(o.i + 1, 1);

          for (j = i + 1; j < n; ++j) q[j].i--;

        }

      }

      q.splice(i, 1);

      n--;

      i--;

    } else {

      o.x = d3.interpolateNumber(parseFloat(m[0]), parseFloat(o.x));

    }

  }

  // Remove any numbers in b not found in a.

  while (i < n) {

    o = q.pop();

    if (s[o.i + 1] == null) { // This match is followed by another number.

      s[o.i] = o.x;

    } else { // This match is followed by a string, so coallesce twice.

      s[o.i] = o.x + s[o.i + 1];

      s.splice(o.i + 1, 1);

    }

    n--;

  }

  // Special optimization for only a single match.

  if (s.length === 1) {

    return s[0] == null ? q[0].x : function() { return b; };

  }

  // Otherwise, interpolate each of the numbers and rejoin the string.

  return function(t) {

    for (i = 0; i < n; ++i) s[(o = q[i]).i] = o.x(t);

    return s.join("");

  };

};

d3.interpolateTransform = function(a, b) {

  return d3.interpolateString(d3.transform(a) + "", d3.transform(b) + "");

};

d3.interpolateRgb = function(a, b) {

  a = d3.rgb(a);

  b = d3.rgb(b);

  var ar = a.r,

      ag = a.g,

      ab = a.b,

      br = b.r - ar,

      bg = b.g - ag,

      bb = b.b - ab;

  return function(t) {

    return "#"

        + d3_rgb_hex(Math.round(ar + br * t))

        + d3_rgb_hex(Math.round(ag + bg * t))

        + d3_rgb_hex(Math.round(ab + bb * t));

  };

};

// interpolates HSL space, but outputs RGB string (for compatibility)

d3.interpolateHsl = function(a, b) {

  a = d3.hsl(a);

  b = d3.hsl(b);

  var h0 = a.h,

      s0 = a.s,

      l0 = a.l,

      h1 = b.h - h0,

      s1 = b.s - s0,

      l1 = b.l - l0;

  return function(t) {

    return d3_hsl_rgb(h0 + h1 * t, s0 + s1 * t, l0 + l1 * t).toString();

  };

};

d3.interpolateArray = function(a, b) {

  var x = [],

      c = [],

      na = a.length,

      nb = b.length,

      n0 = Math.min(a.length, b.length),

      i;

  for (i = 0; i < n0; ++i) x.push(d3.interpolate(a[i], b[i]));

  for (; i < na; ++i) c[i] = a[i];

  for (; i < nb; ++i) c[i] = b[i];

  return function(t) {

    for (i = 0; i < n0; ++i) c[i] = x[i](t);

    return c;

  };

};

d3.interpolateObject = function(a, b) {

  var i = {},

      c = {},

      k;

  for (k in a) {

    if (k in b) {

      i[k] = d3_interpolateByName(k)(a[k], b[k]);

    } else {

      c[k] = a[k];

    }

  }

  for (k in b) {

    if (!(k in a)) {

      c[k] = b[k];

    }

  }

  return function(t) {

    for (k in i) c[k] = i[k](t);

    return c;

  };

}

var d3_interpolate_number = /[-+]?(?:\d*\.?\d+)(?:[eE][-+]?\d+)?/g;

function d3_interpolateByName(n) {

  return n == "transform"

      ? d3.interpolateTransform

      : d3.interpolate;

}

d3.interpolators = [

  d3.interpolateObject,

  function(a, b) { return (b instanceof Array) && d3.interpolateArray(a, b); },

  function(a, b) { return (typeof b === "string") && d3.interpolateString(a + "", b); },

  function(a, b) { return (typeof b === "string" ? b in d3_rgb_names || /^(#|rgb\(|hsl\()/.test(b) : b instanceof d3_Rgb || b instanceof d3_Hsl) && d3.interpolateRgb(a + "", b); },

  function(a, b) { return (typeof b === "number") && d3.interpolateNumber(+a, b); }

];