Skip to content

Commit 99bde3a

Browse files
MaxGraeydcodeIO
MaxGraey
authored and
dcodeIO
committed
Use insertion sort for references in Array#sort (AssemblyScript#90)
This fixes that Weak Heap Sort isn't stable and thus might swap equal values, which sometimes results in not deep equal arrays of strings, for example. Insertion sort is stable, so it is used for references instead.
1 parent 8b5d1d7 commit 99bde3a

File tree

5 files changed

+1105
-2766
lines changed

5 files changed

+1105
-2766
lines changed

‎std/assembly/array.ts‎

Lines changed: 10 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -314,9 +314,15 @@ export class Array<T> {
314314
}
315315
return this;
316316
}
317-
return changetype<this>(length < 256
318-
? insertionSort<T,T>(this, comparator)
319-
: weakHeapSort<T,T>(this, comparator)
320-
);
317+
318+
if (isReference<T>()) {
319+
// TODO replace this to stable sort when it implemented
320+
return changetype<this>(insertionSort<T>(this, comparator));
321+
} else {
322+
return changetype<this>(length < 256
323+
? insertionSort<T>(this, comparator)
324+
: weakHeapSort<T>(this, comparator)
325+
);
326+
}
321327
}
322328
}

‎std/assembly/internal/array.ts‎

Lines changed: 27 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -14,25 +14,25 @@ export function defaultComparator<T>(): (a: T, b: T) => i32 {
1414
}
1515

1616
/** Sorts an Array with the 'Insertion Sort' algorithm. */
17-
export function insertionSort<T,V>(arr: Array<T>, comparator: (a: V, b: V) => i32): Array<T> {
17+
export function insertionSort<T>(arr: Array<T>, comparator: (a: T, b: T) => i32): Array<T> {
1818
var buffer = arr.buffer_;
1919
for (let i: i32 = 0, length: i32 = arr.length; i < length; i++) {
20-
let a = loadUnsafe<T,V>(buffer, i); // a = arr[i]
20+
let a = loadUnsafe<T,T>(buffer, i); // a = arr[i]
2121
let j = i - 1;
2222
while (j >= 0) {
23-
let b = loadUnsafe<T,V>(buffer, j); // b = arr[j]
23+
let b = loadUnsafe<T,T>(buffer, j); // b = arr[j]
2424
if (comparator(a, b) < 0) {
25-
storeUnsafe<T,V>(buffer, j-- + 1, b); // arr[j + 1] = b
25+
storeUnsafe<T,T>(buffer, j-- + 1, b); // arr[j + 1] = b
2626
} else break;
2727
}
28-
storeUnsafe<T,V>(buffer, j + 1, a); // arr[j + 1] = a
28+
storeUnsafe<T,T>(buffer, j + 1, a); // arr[j + 1] = a
2929
}
3030
return arr;
3131
}
3232

3333
/** Sorts an Array with the 'Weak Heap Sort' algorithm. */
34-
export function weakHeapSort<T,V>(arr: Array<T>, comparator: (a: V, b: V) => i32): Array<T> {
35-
const shift32 = alignof<i32>();
34+
export function weakHeapSort<T>(arr: Array<T>, comparator: (a: T, b: T) => i32): Array<T> {
35+
const shift32 = alignof<u32>();
3636

3737
var length = arr.length;
3838
var bitsetSize = (length + 31) >> 5 << shift32;
@@ -44,49 +44,49 @@ export function weakHeapSort<T,V>(arr: Array<T>, comparator: (a: V, b: V) => i32
4444
var buffer = arr.buffer_;
4545
for (let i = length - 1; i > 0; i--) {
4646
let j = i;
47-
while ((j & 1) == (load<i32>(bitset + (j >> 6 << shift32)) >> (j >> 1 & 31) & 1)) j >>= 1;
47+
while ((j & 1) == (load<u32>(bitset + (j >> 6 << shift32)) >> (j >> 1 & 31) & 1)) j >>= 1;
4848

4949
let p = j >> 1;
50-
let a = loadUnsafe<T,V>(buffer, p); // a = arr[p]
51-
let b = loadUnsafe<T,V>(buffer, i); // b = arr[i]
50+
let a = loadUnsafe<T,T>(buffer, p); // a = arr[p]
51+
let b = loadUnsafe<T,T>(buffer, i); // b = arr[i]
5252
if (comparator(a, b) < 0) {
53-
store<i32>(
53+
store<u32>(
5454
bitset + (i >> 5 << shift32),
55-
load<i32>(bitset + (i >> 5 << shift32)) ^ (1 << (i & 31))
55+
load<u32>(bitset + (i >> 5 << shift32)) ^ (1 << (i & 31))
5656
);
57-
storeUnsafe<T,V>(buffer, i, a); // arr[i] = a
58-
storeUnsafe<T,V>(buffer, p, b); // arr[p] = b
57+
storeUnsafe<T,T>(buffer, i, a); // arr[i] = a
58+
storeUnsafe<T,T>(buffer, p, b); // arr[p] = b
5959
}
6060
}
6161

6262
for (let i = length - 1; i >= 2; i--) {
63-
let a = loadUnsafe<T,V>(buffer, 0); // a = arr[0]
64-
storeUnsafe<T,V>(buffer, 0, loadUnsafe<T,V>(buffer, i)); // arr[0] = arr[i]
65-
storeUnsafe<T,V>(buffer, i, a); // arr[i] = a
63+
let a = loadUnsafe<T,T>(buffer, 0); // a = arr[0]
64+
storeUnsafe<T,T>(buffer, 0, loadUnsafe<T,T>(buffer, i)); // arr[0] = arr[i]
65+
storeUnsafe<T,T>(buffer, i, a); // arr[i] = a
6666

6767
let x = 1, y: i32;
68-
while ((y = (x << 1) + ((load<i32>(bitset + (x >> 5 << shift32)) >> (x & 31)) & 1)) < i) x = y;
68+
while ((y = (x << 1) + ((load<u32>(bitset + (x >> 5 << shift32)) >> (x & 31)) & 1)) < i) x = y;
6969

7070
while (x > 0) {
71-
a = loadUnsafe<T,V>(buffer, 0); // a = arr[0]
72-
let b = loadUnsafe<T,V>(buffer, x); // b = arr[x]
71+
a = loadUnsafe<T,T>(buffer, 0); // a = arr[0]
72+
let b = loadUnsafe<T,T>(buffer, x); // b = arr[x]
7373

7474
if (comparator(a, b) < 0) {
75-
store<i32>(
75+
store<u32>(
7676
bitset + (x >> 5 << shift32),
77-
load<i32>(bitset + (x >> 5 << shift32)) ^ (1 << (x & 31))
77+
load<u32>(bitset + (x >> 5 << shift32)) ^ (1 << (x & 31))
7878
);
79-
storeUnsafe<T,V>(buffer, x, a); // arr[x] = a
80-
storeUnsafe<T,V>(buffer, 0, b); // arr[0] = b
79+
storeUnsafe<T,T>(buffer, x, a); // arr[x] = a
80+
storeUnsafe<T,T>(buffer, 0, b); // arr[0] = b
8181
}
8282
x >>= 1;
8383
}
8484
}
8585

8686
free_memory(bitset);
8787

88-
var t = loadUnsafe<T,V>(buffer, 1); // t = arr[1]
89-
storeUnsafe<T,V>(buffer, 1, loadUnsafe<T,V>(buffer, 0)); // arr[1] = arr[0]
90-
storeUnsafe<T,V>(buffer, 0, t); // arr[0] = t
88+
var t = loadUnsafe<T,T>(buffer, 1); // t = arr[1]
89+
storeUnsafe<T,T>(buffer, 1, loadUnsafe<T,T>(buffer, 0)); // arr[1] = arr[0]
90+
storeUnsafe<T,T>(buffer, 0, t); // arr[0] = t
9191
return arr;
9292
}

0 commit comments

Comments
 (0)