import “number”;

d3.interpolateString = d3_interpolateString;

function d3_interpolateString(a, b) {

var m, // current match
    i, // current index
    j, // current index (for coalescing)
    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;

// Coerce inputs to strings.
a = a + "", b = b + "";

// 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 coalesce.
    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 coalesce 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 coalesce 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 coalesce 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
      ? (o = q[0].x, function(t) { return o(t) + ""; })
      : 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("");
};

}

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