8000 fix a vector bounds bug, and improve performance of merge · rvrobotics/immutable-js@3f54f45 · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit 3f54f45

Browse files
leebyronleebyron
committed
fix a vector bounds bug, and improve performance of merge
1 parent f0d2061 commit 3f54f45

File tree

3 files changed

+64
-27
lines changed

3 files changed

+64
-27
line 8000 s changed

‎__tests__/Vector.ts

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -263,17 +263,16 @@ describe('Vector', () => {
263263
var v3 = v2.setLength(1500);
264264
expect(v1.length).toBe(2000);
265265
expect(v2.length).toBe(1000);
266-
// TODO: failing test!
267-
//expect(v3.length).toBe(1500);
266+
expect(v3.length).toBe(1500);
268267
expect(v1.get(900)).toBe(900);
269268
expect(v1.get(1300)).toBe(1300);
270269
expect(v1.get(1800)).toBe(1800);
271270
expect(v2.get(900)).toBe(900);
272271
expect(v2.get(1300)).toBe(undefined);
273272
expect(v2.get(1800)).toBe(undefined);
274-
//expect(v3.get(900)).toBe(900);
275-
//expect(v3.get(1300)).toBe(undefined);
276-
//expect(v3.get(1800)).toBe(undefined);
273+
expect(v3.get(900)).toBe(900);
274+
expect(v3.get(1300)).toBe(undefined);
275+
expect(v3.get(1800)).toBe(undefined);
277276
});
278277

279278
it('can be efficiently sliced', () => {

‎dist/Vector.js

Lines changed: 30 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,7 @@ for(var IndexedSequence____Key in IndexedSequence){if(IndexedSequence.hasOwnProp
5858
Vector.prototype.set=function(index, value) {"use strict";
5959
var tailOffset = getTailOffset(this.$Vector_size);
6060

61-
if (index + this.$Vector_origin >= tailOffset + SIZE) {
61+
if (index >= this.length) {
6262
return this.withMutations(function(vect)
6363
{return vect.$Vector_setBounds(0, index + 1).set(index, value);}
6464
);
@@ -176,10 +176,24 @@ for(var IndexedSequence____Key in IndexedSequence){if(IndexedSequence.hasOwnProp
176176

177177
// @pragma Composition
178178

179+
Vector.prototype.merge=function() {"use strict";var seqs=Array.prototype.slice.call(arguments,0);
180+
return ImmutableMap.prototype.merge.apply(
181+
vectorWithLengthOfLongestSeq(this, seqs), arguments);
182+
};
183+
179184
Vector.prototype.mergeWith=function(fn) {"use strict";var seqs=Array.prototype.slice.call(arguments,1);
180-
var merged = ImmutableMap.prototype.mergeWith.apply(this, arguments);
181-
var maxLength = Math.max.apply(null, seqs.map(function(seq) {return seq.length || 0;}));
182-
return maxLength > merged.length ? merged.$Vector_setBounds(0, maxLength) : merged;
185+
return ImmutableMap.prototype.mergeWith.apply(
186+
vectorWithLengthOfLongestSeq(this, seqs), arguments);
187+
};
188+
189+
Vector.prototype.mergeDeep=function() {"use strict";var seqs=Array.prototype.slice.call(arguments,0);
190+
return ImmutableMap.prototype.mergeDeep.apply(
191+
vectorWithLengthOfLongestSeq(this, seqs), arguments);
192+
};
193+
194+
Vector.prototype.mergeDeepWith=function(fn) {"use strict";var seqs=Array.prototype.slice.call(arguments,1);
195+
return ImmutableMap.prototype.mergeDeepWith.apply(
196+
vectorWithLengthOfLongestSeq(this, seqs), arguments);
183197
};
184198

185199
Vector.prototype.setLength=function(length) {"use strict";
@@ -206,15 +220,16 @@ for(var IndexedSequence____Key in IndexedSequence){if(IndexedSequence.hasOwnProp
206220

207221
// New origin might require creating a higher root.
208222
var offsetShift = 0;
209-
while (newOrigin < 0) {
223+
while (newOrigin + offsetShift < 0) {
224+
// TODO: why only ever shifting over by 1?
210225
newRoot = new VNode(newRoot.array.length ? [,newRoot] : [], owner);
211226
offsetShift += 1 << newLevel;
212-
newOrigin += offsetShift;
213227
newLevel += SHIFT;
214228
}
215229
if (offsetShift) {
216-
newSize += offsetShift;
230+
newOrigin += offsetShift;
217231
oldOrigin += offsetShift;
232+
newSize += offsetShift;
218233
oldSize += offsetShift;
219234
}
220235

@@ -267,7 +282,9 @@ for(var IndexedSequence____Key in IndexedSequence){if(IndexedSequence.hasOwnProp
267282
beginIndex = ((newOrigin) >>> newLevel) & MASK;
268283
endIndex = ((newTailOffset - 1) >>> newLevel) & MASK;
269284
if (beginIndex === endIndex) {
270-
offsetShift += 1 << newLevel;
285+
if (beginIndex) {
286+
offsetShift += (1 << newLevel) * beginIndex;
287+
}
271288
newLevel -= SHIFT;
272289
newRoot = newRoot && newRoot.array[beginIndex];
273290
}
@@ -405,9 +422,6 @@ for(var IndexedSequence____Key in IndexedSequence){if(IndexedSequence.hasOwnProp
405422
};
406423

407424

408-
Vector.prototype.merge = ImmutableMap.prototype.merge;
409-
Vector.prototype.mergeDeep = ImmutableMap.prototype.mergeDeep;
410-
Vector.prototype.mergeDeepWith = ImmutableMap.prototype.mergeDeepWith;
411425
Vector.prototype.withMutations = ImmutableMap.prototype.withMutations;
412426
Vector.prototype.updateIn = ImmutableMap.prototype.updateIn;
413427

@@ -600,6 +614,11 @@ Vector.prototype.updateIn = ImmutableMap.prototype.updateIn;
600614

601615

602616

617+
function vectorWithLengthOfLongestSeq(vector, seqs) {
618+
var maxLength = Math.max.apply(null, seqs.map(function(seq) {return seq.length || 0;}));
619+
return maxLength > vector.length ? vector.setLength(maxLength) : vector;
620+
}
621+
603622
function rawIndex(index, origin) {
604623
if (index < 0) throw new Error('Index out of bounds');
605624
return index + origin;

‎src/Vector.js

Lines changed: 30 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,7 @@ class Vector extends IndexedSequence {
5858
set(index, value) {
5959
var tailOffset = getTailOffset(this._size);
6060

61-
if (index + this._origin >= tailOffset + SIZE) {
61+
if (index >= this.length) {
6262
return this.withMutations(vect =>
6363
vect._setBounds(0, index + 1).set(index, value)
6464
);
@@ -176,10 +176,24 @@ class Vector extends IndexedSequence {
176176

177177
// @pragma Composition
178178

179+
merge(...seqs) {
180+
return ImmutableMap.prototype.merge.apply(
181+
vectorWithLengthOfLongestSeq(this, seqs), arguments);
182+
}
183+
179184
mergeWith(fn, ...seqs) {
180-
var merged = ImmutableMap.prototype.mergeWith.apply(this, arguments);
181-
var maxLength = Math.max.apply(null, seqs.map(seq => seq.length || 0));
182-
return maxLength > merged.length ? merged._setBounds(0, maxLength) : merged;
185+
return ImmutableMap.prototype.mergeWith.apply(
186+
vectorWithLengthOfLongestSeq(this, seqs), arguments);
187+
}
188+
189+
mergeDeep(...seqs) {
190+
return ImmutableMap.prototype.mergeDeep.apply(
191+
vectorWithLengthOfLongestSeq(this, seqs), arguments);
192+
}
193+
194+
mergeDeepWith(fn, ...seqs) {
195+
return ImmutableMap.prototype.mergeDeepWith.apply(
196+
vectorWithLengthOfLongestSeq(this, seqs), arguments);
183197
}
184198

185199
setLength(length) {
@@ -206,15 +220,16 @@ class Vector extends IndexedSequence {
206220

207221
// New origin might require creating a higher root.
208222
var offsetShift = 0;
209-
while (newOrigin < 0) {
223+
while (newOrigin + offsetShift < 0) {
224+
// TODO: why only ever shifting over by 1?
210225
newRoot = new VNode(newRoot.array.length ? [,newRoot] : [], owner);
211226
offsetShift += 1 << newLevel;
212-
newOrigin += offsetShift;
213227
newLevel += SHIFT;
214228
}
215229
if (offsetShift) {
216-
newSize += offsetShift;
230+
newOrigin += offsetShift;
217231
oldOrigin += offsetShift;
232+
newSize += offsetShift;
218233
oldSize += offsetShift;
219234
}
220235

@@ -267,7 +282,9 @@ class Vector extends IndexedSequence {
267282
beginIndex = ((newOrigin) >>> newLevel) & MASK;
268283
endIndex = ((newTailOffset - 1) >>> newLevel) & MASK;
269284
if (beginIndex === endIndex) {
270-
offsetShift += 1 << newLevel;
285+
if (beginIndex) {
286+
offsetShift += (1 << newLevel) * beginIndex;
287+
}
271288
newLevel -= SHIFT;
272289
newRoot = newRoot && newRoot.array[beginIndex];
273290
}
@@ -405,9 +422,6 @@ class Vector extends IndexedSequence {
405422
}
406423
}
407424

408-
Vector.prototype.merge = ImmutableMap.prototype.merge;
409-
Vector.prototype.mergeDeep = ImmutableMap.prototype.mergeDeep;
410-
Vector.prototype.mergeDeepWith = ImmutableMap.prototype.mergeDeepWith;
411425
Vector.prototype.withMutations = ImmutableMap.prototype.withMutations;
412426
Vector.prototype.updateIn = ImmutableMap.prototype.updateIn;
413427

@@ -600,6 +614,11 @@ class VectorIterator {
600614
}
601615

602616

617+
function vectorWithLengthOfLongestSeq(vector, seqs) {
618+
var maxLength = Math.max.apply(null, seqs.map(seq => seq.length || 0));
619+
return maxLength > vector.length ? vector.setLength(maxLength) : vector;
620+
}
621+
603622
function rawIndex(index, origin) {
604623
if (index < 0) throw new Error('Index out of bounds');
605624
return index + origin;

0 commit comments

Comments
 (0)
0