fix: new sorting algorithm (AssemblyScript#1904)

nearprotocol · Jul 12, 2021 · 6b774d4 · 6b774d4
1 parent bf24bb9
commit 6b774d4
Show file tree

Hide file tree

Showing 14 changed files with 40,288 additions and 20,183 deletions.
diff --git a/std/assembly/array.ts b/std/assembly/array.ts
@@ -440,19 +440,7 @@ export class Array<T> {
   }
 
   sort(comparator: (a: T, b: T) => i32 = COMPARATOR<T>()): this {
-    var length = this.length_;
-    if (length <= 1) return this;
-    var base = this.dataStart;
-    if (length == 2) {
-      let a: T = load<T>(base, sizeof<T>()); // a = arr[1]
-      let b: T = load<T>(base); // b = arr[0]
-      if (comparator(a, b) < 0) {
-        store<T>(base, b, sizeof<T>()); // arr[1] = b;
-        store<T>(base, a); // arr[0] = a;
-      }
-      return this;
-    }
-    SORT<T>(base, length, comparator);
+    SORT<T>(this.dataStart, this.length_, comparator);
     return this;
   }
 

diff --git a/std/assembly/typedarray.ts b/std/assembly/typedarray.ts
@@ -1,4 +1,4 @@
-import { COMPARATOR, SORT as SORT_IMPL } from "./util/sort";
+import { COMPARATOR, SORT } from "./util/sort";
 import { E_INDEXOUTOFRANGE, E_INVALIDLENGTH, E_NOTIMPLEMENTED } from "./util/error";
 import { joinIntegerArray, joinFloatArray } from "./util/string";
 import { idof } from "./builtins";
@@ -65,7 +65,8 @@ export class Int8Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: i8, b: i8) => i32 = COMPARATOR<i8>()): Int8Array {
-    return SORT<Int8Array, i8>(this, comparator);
+    SORT<i8>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Int8Array {
@@ -200,7 +201,8 @@ export class Uint8Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: u8, b: u8) => i32 = COMPARATOR<u8>()): Uint8Array {
-    return SORT<Uint8Array, u8>(this, comparator);
+    SORT<u8>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Uint8Array {
@@ -334,8 +336,9 @@ export class Uint8ClampedArray extends ArrayBufferView {
     return FILL<Uint8ClampedArray, u8>(this, value, start, end);
   }
 
-  sort(fn: (a: u8, b: u8) => i32 = COMPARATOR<u8>()): Uint8ClampedArray {
-    return SORT<Uint8ClampedArray, u8>(this, fn);
+  sort(comparator: (a: u8, b: u8) => i32 = COMPARATOR<u8>()): Uint8ClampedArray {
+    SORT<u8>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Uint8ClampedArray {
@@ -470,7 +473,8 @@ export class Int16Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: i16, b: i16) => i32 = COMPARATOR<i16>()): Int16Array {
-    return SORT<Int16Array, i16>(this, comparator);
+    SORT<i16>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Int16Array {
@@ -605,7 +609,8 @@ export class Uint16Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: u16, b: u16) => i32 = COMPARATOR<u16>()): Uint16Array {
-    return SORT<Uint16Array, u16>(this, comparator);
+    SORT<u16>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Uint16Array {
@@ -740,7 +745,8 @@ export class Int32Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: i32, b: i32) => i32 = COMPARATOR<i32>()): Int32Array {
-    return SORT<Int32Array, i32>(this, comparator);
+    SORT<i32>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Int32Array {
@@ -875,7 +881,8 @@ export class Uint32Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: u32, b: u32) => i32 = COMPARATOR<u32>()): Uint32Array {
-    return SORT<Uint32Array, u32>(this, comparator);
+    SORT<u32>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Uint32Array {
@@ -1010,7 +1017,8 @@ export class Int64Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: i64, b: i64) => i32 = COMPARATOR<i64>()): Int64Array {
-    return SORT<Int64Array, i64>(this, comparator);
+    SORT<i64>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Int64Array {
@@ -1145,7 +1153,8 @@ export class Uint64Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: u64, b: u64) => i32 = COMPARATOR<u64>()): Uint64Array {
-    return SORT<Uint64Array, u64>(this, comparator);
+    SORT<u64>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Uint64Array {
@@ -1280,7 +1289,8 @@ export class Float32Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: f32, b: f32) => i32 = COMPARATOR<f32>()): Float32Array {
-    return SORT<Float32Array, f32>(this, comparator);
+    SORT<f32>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Float32Array {
@@ -1415,7 +1425,8 @@ export class Float64Array extends ArrayBufferView {
   }
 
   sort(comparator: (a: f64, b: f64) => i32 = COMPARATOR<f64>()): Float64Array {
-    return SORT<Float64Array, f64>(this, comparator);
+    SORT<f64>(this.dataStart, this.length, comparator);
+    return this;
   }
 
   slice(begin: i32 = 0, end: i32 = i32.MAX_VALUE): Float64Array {
@@ -1511,28 +1522,6 @@ function FILL<TArray extends ArrayBufferView, T extends number>(
   return array;
 }
 
-// @ts-ignore: decorator
-@inline
-function SORT<TArray extends ArrayBufferView, T>(
-  array: TArray,
-  comparator: (a: T, b: T) => i32
-): TArray {
-  var len = array.length;
-  if (len <= 1) return array;
-  var base = array.dataStart;
-  if (len == 2) {
-    let a: T = load<T>(base, sizeof<T>()); // a = arr[1]
-    let b: T = load<T>(base); // b = arr[0]
-    if (comparator(a, b) < 0) {
-      store<T>(base, b, sizeof<T>()); // arr[1] = b
-      store<T>(base, a); // arr[0] = a
-    }
-    return array;
-  }
-  SORT_IMPL<T>(base, len, comparator);
-  return array;
-}
-
 // @ts-ignore: decorator
 @inline
 function SLICE<TArray extends ArrayBufferView, T>(