Skip to content

Commit ec2eadb

Browse files
mbostockmbostock
committed
Fix a bug in d3.merge optimization.
The d3.merge operator must always return a new array, but it wasn’t in the case where a one-element array was passed. This implementation is still quite fast but always returns a new array.
1 parent cc00e66 commit ec2eadb

4 files changed

Lines changed: 55 additions & 11 deletions

File tree

‎d3.js‎

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -186,8 +186,15 @@ d3 = function() {
186186
return entries;
187187
};
188188
d3.merge = function(arrays) {
189-
var n = arrays.length;
190-
return n ? n > 1 ? Array.prototype.concat.apply([], arrays) : arrays[0] : [];
189+
var n = arrays.length, m = 0, i, j, k = -1, merged, array;
190+
for (i = 0; i < n; ++i) m += arrays[i].length;
191+
merged = new Array(m);
192+
for (i = 0; i < n; ++i) {
193+
for (array = arrays[i], m = array.length, j = 0; j < m; ++j) {
194+
merged[++k] = array[j];
195+
}
196+
}
197+
return merged;
191198
};
192199
var abs = Math.abs;
193200
d3.range = function(start, stop, step) {

‎d3.min.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/arrays/merge.js‎

Lines changed: 18 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,20 @@
11
d3.merge = function(arrays) {
2-
var n = arrays.length;
3-
return n ? n > 1
4-
? Array.prototype.concat.apply([], arrays)
5-
: arrays[0]
6-
: [];
2+
var n = arrays.length,
3+
m = 0,
4+
i,
5+
j,
6+
k = -1,
7+
merged,
8+
array;
9+
10+
for (i = 0; i < n; ++i) m += arrays[i].length;
11+
merged = new Array(m);
12+
13+
for (i = 0; i < n; ++i) {
14+
for (array = arrays[i], m = array.length, j = 0; j < m; ++j) {
15+
merged[++k] = array[j];
16+
}
17+
}
18+
19+
return merged;
720
};

‎test/arrays/merge-test.js‎

Lines changed: 27 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,9 +11,33 @@ suite.addBatch({
1111
var a = {}, b = {}, c = {}, d = {}, e = {}, f = {};
1212
assert.deepEqual(merge([[a], [b, c], [d, e, f]]), [a, b, c, d, e, f]);
1313
},
14-
"returns a new array": function(merge) {
15-
var input = [[1, 2, 3], [4, 5], [6]];
16-
assert.isFalse(merge(input) === input);
14+
"returns a new array when zero arrays are passed": function(merge) {
15+
var input = [],
16+
output = merge(input);
17+
assert.deepEqual(output, []);
18+
input.push([0.1]);
19+
assert.deepEqual(input, [[0.1]]);
20+
assert.deepEqual(output, []);
21+
},
22+
"returns a new array when one array is passed": function(merge) {
23+
var input = [[1, 2, 3]],
24+
output = merge(input);
25+
assert.deepEqual(output, [1, 2, 3]);
26+
input.push([4.1]);
27+
input[0].push(3.1);
28+
assert.deepEqual(input, [[1, 2, 3, 3.1], [4.1]]);
29+
assert.deepEqual(output, [1, 2, 3]);
30+
},
31+
"returns a new array when two or more arrays are passed": function(merge) {
32+
var input = [[1, 2, 3], [4, 5], [6]],
33+
output = merge(input);
34+
assert.deepEqual(output, [1, 2, 3, 4, 5, 6]);
35+
input.push([7.1]);
36+
input[0].push(3.1);
37+
input[1].push(5.1);
38+
input[2].push(6.1);
39+
assert.deepEqual(input, [[1, 2, 3, 3.1], [4, 5, 5.1], [6, 6.1], [7.1]]);
40+
assert.deepEqual(output, [1, 2, 3, 4, 5, 6]);
1741
},
1842
"does not modify the input arrays": function(merge) {
1943
var input = [[1, 2, 3], [4, 5], [6]];

0 commit comments

Comments
 (0)