Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 3f54f45

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

File tree

Expand file treeCollapse file tree

3 files changed

+64
-27
lines changed
Filter options
Expand file treeCollapse file tree

3 files changed

+64
-27
lines changed

‎__tests__/Vector.ts

Copy file name to clipboardExpand all lines: __tests__/Vector.ts
+4-5Lines 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

Copy file name to clipboardExpand all lines: dist/Vector.js
+30-11Lines 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

Copy file name to clipboardExpand all lines: src/Vector.js
+30-11Lines 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)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.