Skip to content

Commit 4adb0c2

Browse files
mbostockmbostock
committed
Optimize interpolateString.
1 parent fa55eea commit 4adb0c2

4 files changed

Lines changed: 73 additions & 131 deletions

File tree

‎d3.js‎

Lines changed: 24 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -5617,71 +5617,38 @@
56175617
}
56185618
d3.interpolateString = d3_interpolateString;
56195619
function d3_interpolateString(a, b) {
5620-
var m, i, j, s0 = 0, s1 = 0, s = [], q = [], n, o;
5620+
var bi = d3_interpolate_numberA.lastIndex = d3_interpolate_numberB.lastIndex = 0, am, bm, bs, i = -1, s = [], q = [];
56215621
a = a + "", b = b + "";
5622-
d3_interpolate_number.lastIndex = 0;
5623-
for (i = 0; m = d3_interpolate_number.exec(b); ++i) {
5624-
if (m.index) s.push(b.substring(s0, s1 = m.index));
5625-
q.push({
5626-
i: s.length,
5627-
x: m[0]
5628-
});
5629-
s.push(null);
5630-
s0 = d3_interpolate_number.lastIndex;
5631-
}
5632-
if (s0 < b.length) s.push(b.substring(s0));
5633-
for (i = 0, n = q.length; (m = d3_interpolate_number.exec(a)) && i < n; ++i) {
5634-
o = q[i];
5635-
if (o.x == m[0]) {
5636-
if (o.i) {
5637-
if (s[o.i + 1] == null) {
5638-
s[o.i - 1] += o.x;
5639-
s.splice(o.i, 1);
5640-
for (j = i + 1; j < n; ++j) q[j].i--;
5641-
} else {
5642-
s[o.i - 1] += o.x + s[o.i + 1];
5643-
s.splice(o.i, 2);
5644-
for (j = i + 1; j < n; ++j) q[j].i -= 2;
5645-
}
5646-
} else {
5647-
if (s[o.i + 1] == null) {
5648-
s[o.i] = o.x;
5649-
} else {
5650-
s[o.i] = o.x + s[o.i + 1];
5651-
s.splice(o.i + 1, 1);
5652-
for (j = i + 1; j < n; ++j) q[j].i--;
5653-
}
5654-
}
5655-
q.splice(i, 1);
5656-
n--;
5657-
i--;
5658-
} else {
5659-
o.x = d3_interpolateNumber(parseFloat(m[0]), parseFloat(o.x));
5622+
while ((am = d3_interpolate_numberA.exec(a)) && (bm = d3_interpolate_numberB.exec(b))) {
5623+
if ((bs = bm.index) > bi) {
5624+
bs = b.substring(bi, bs);
5625+
if (s[i]) s[i] += bs; else s[++i] = bs;
56605626
}
5661-
}
5662-
while (i < n) {
5663-
o = q.pop();
5664-
if (s[o.i + 1] == null) {
5665-
s[o.i] = o.x;
5627+
if ((am = +am[0]) === (bm = +(bs = bm[0]))) {
5628+
if (s[i]) s[i] += bs; else s[++i] = bs;
56665629
} else {
5667-
s[o.i] = o.x + s[o.i + 1];
5668-
s.splice(o.i + 1, 1);
5630+
s[++i] = null;
5631+
q.push({
5632+
i: i,
5633+
x: d3_interpolateNumber(am, bm)
5634+
});
56695635
}
5670-
n--;
5636+
bi = d3_interpolate_numberB.lastIndex;
56715637
}
5672-
if (s.length === 1) {
5673-
return s[0] == null ? (o = q[0].x, function(t) {
5674-
return o(t) + "";
5675-
}) : function() {
5676-
return b;
5677-
};
5638+
if (bi < b.length) {
5639+
bs = b.substring(bi);
5640+
if (s[i]) s[i] += bs; else s[++i] = bs;
56785641
}
5679-
return function(t) {
5680-
for (i = 0; i < n; ++i) s[(o = q[i]).i] = o.x(t);
5642+
return s.length < 2 ? q[0] ? (b = q[0].x, function(t) {
5643+
return b(t) + "";
5644+
}) : function() {
5645+
return b;
5646+
} : (b = q.length, function(t) {
5647+
for (var i = 0, o; i < b; ++i) s[(o = q[i]).i] = o.x(t);
56815648
return s.join("");
5682-
};
5649+
});
56835650
}
5684-
var d3_interpolate_number = /[-+]?(?:\d+\.?\d*|\.?\d+)(?:[eE][-+]?\d+)?/g;
5651+
var d3_interpolate_numberA = /[-+]?(?:\d+\.?\d*|\.?\d+)(?:[eE][-+]?\d+)?/g, d3_interpolate_numberB = new RegExp(d3_interpolate_numberA.source, "g");
56855652
d3.interpolate = d3_interpolate;
56865653
function d3_interpolate(a, b) {
56875654
var i = d3.interpolators.length, f;

‎d3.min.js‎

Lines changed: 5 additions & 5 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/interpolate/string.js‎

Lines changed: 35 additions & 69 deletions
Original file line numberDiff line numberDiff line change
@@ -3,86 +3,52 @@ import "number";
33
d3.interpolateString = d3_interpolateString;
44

55
function d3_interpolateString(a, b) {
6-
var m, // current match
7-
i, // current index
8-
j, // current index (for coalescing)
9-
s0 = 0, // start index of current string prefix
10-
s1 = 0, // end index of current string prefix
6+
var bi = d3_interpolate_numberA.lastIndex = d3_interpolate_numberB.lastIndex = 0, // scan index for next number in b
7+
am, // current match in a
8+
bm, // current match in b
9+
bs, // string preceding current number in b, if any
10+
i = -1, // index in s
1111
s = [], // string constants and placeholders
12-
q = [], // number interpolators
13-
n, // q.length
14-
o;
12+
q = []; // number interpolators
1513

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

19-
// Reset our regular expression!
20-
d3_interpolate_number.lastIndex = 0;
21-
22-
// Find all numbers in b.
23-
for (i = 0; m = d3_interpolate_number.exec(b); ++i) {
24-
if (m.index) s.push(b.substring(s0, s1 = m.index));
25-
q.push({i: s.length, x: m[0]});
26-
s.push(null);
27-
s0 = d3_interpolate_number.lastIndex;
28-
}
29-
if (s0 < b.length) s.push(b.substring(s0));
30-
31-
// Find all numbers in a.
32-
for (i = 0, n = q.length; (m = d3_interpolate_number.exec(a)) && i < n; ++i) {
33-
o = q[i];
34-
if (o.x == m[0]) { // The numbers match, so coalesce.
35-
if (o.i) {
36-
if (s[o.i + 1] == null) { // This match is followed by another number.
37-
s[o.i - 1] += o.x;
38-
s.splice(o.i, 1);
39-
for (j = i + 1; j < n; ++j) q[j].i--;
40-
} else { // This match is followed by a string, so coalesce twice.
41-
s[o.i - 1] += o.x + s[o.i + 1];
42-
s.splice(o.i, 2);
43-
for (j = i + 1; j < n; ++j) q[j].i -= 2;
44-
}
45-
} else {
46-
if (s[o.i + 1] == null) { // This match is followed by another number.
47-
s[o.i] = o.x;
48-
} else { // This match is followed by a string, so coalesce twice.
49-
s[o.i] = o.x + s[o.i + 1];
50-
s.splice(o.i + 1, 1);
51-
for (j = i + 1; j < n; ++j) q[j].i--;
52-
}
53-
}
54-
q.splice(i, 1);
55-
n--;
56-
i--;
57-
} else {
58-
o.x = d3_interpolateNumber(parseFloat(m[0]), parseFloat(o.x));
17+
// Interpolate pairs of numbers in a & b.
18+
while ((am = d3_interpolate_numberA.exec(a))
19+
&& (bm = d3_interpolate_numberB.exec(b))) {
20+
if ((bs = bm.index) > bi) { // a string precedes the next number in b
21+
bs = b.substring(bi, bs);
22+
if (s[i]) s[i] += bs; // coalesce with previous string
23+
else s[++i] = bs;
5924
}
60-
}
61-
62-
// Remove any numbers in b not found in a.
63-
while (i < n) {
64-
o = q.pop();
65-
if (s[o.i + 1] == null) { // This match is followed by another number.
66-
s[o.i] = o.x;
67-
} else { // This match is followed by a string, so coalesce twice.
68-
s[o.i] = o.x + s[o.i + 1];
69-
s.splice(o.i + 1, 1);
25+
if ((am = +am[0]) === (bm = +(bs = bm[0]))) { // coalesce matching numbers
26+
if (s[i]) s[i] += bs; // coalesce with previous string
27+
else s[++i] = bs;
28+
} else { // interpolate non-matching numbers
29+
s[++i] = null;
30+
q.push({i: i, x: d3_interpolateNumber(am, bm)});
7031
}
71-
n--;
32+
bi = d3_interpolate_numberB.lastIndex;
7233
}
7334

74-
// Special optimization for only a single match.
75-
if (s.length === 1) {
76-
return s[0] == null
77-
? (o = q[0].x, function(t) { return o(t) + ""; })
78-
: function() { return b; };
35+
// Add remains of b.
36+
if (bi < b.length) {
37+
bs = b.substring(bi);
38+
if (s[i]) s[i] += bs; // coalesce with previous string
39+
else s[++i] = bs;
7940
}
8041

42+
// Special optimization for only a single match.
8143
// Otherwise, interpolate each of the numbers and rejoin the string.
82-
return function(t) {
83-
for (i = 0; i < n; ++i) s[(o = q[i]).i] = o.x(t);
84-
return s.join("");
85-
};
44+
return s.length < 2
45+
? (q[0] ? (b = q[0].x, function(t) { return b(t) + ""; })
46+
: function() { return b; })
47+
: (b = q.length, function(t) {
48+
for (var i = 0, o; i < b; ++i) s[(o = q[i]).i] = o.x(t);
49+
return s.join("");
50+
});
8651
}
8752

88-
var d3_interpolate_number = /[-+]?(?:\d+\.?\d*|\.?\d+)(?:[eE][-+]?\d+)?/g;
53+
var d3_interpolate_numberA = /[-+]?(?:\d+\.?\d*|\.?\d+)(?:[eE][-+]?\d+)?/g,
54+
d3_interpolate_numberB = new RegExp(d3_interpolate_numberA.source, "g");

‎test/interpolate/string-test.js‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,15 @@ suite.addBatch({
3636
assert.strictEqual(interpolate("-1.e-3", "-1.e-4")(.5), "-0.00055");
3737
assert.strictEqual(interpolate("+1.e-3", "+1.e-4")(.5), "0.00055");
3838
assert.strictEqual(interpolate(".1e-2", ".1e-3")(.5), "0.00055");
39+
},
40+
"with no numbers, returns the target string": function(interpolate) {
41+
assert.strictEqual(interpolate("foo", "bar")(.5), "bar");
42+
assert.strictEqual(interpolate("foo", "")(.5), "");
43+
assert.strictEqual(interpolate("", "bar")(.5), "bar");
44+
assert.strictEqual(interpolate("", "")(.5), "");
45+
},
46+
"with two numerically-equivalent numbers, returns the target format": function(interpolate) {
47+
assert.strictEqual(interpolate("top: 1000px;", "top: 1e3px;")(.5), "top: 1e3px;");
3948
}
4049
}
4150
});

0 commit comments

Comments
 (0)