Repository: syuilo/aiscript (ts)

Issue:
Ability to sort arrays
## Summary

I wish I could sort the array.

## API usage

```aiscript
sort(array, @(x, y))   //comparison predicate that returns positive value if x > y, 0 if equal, and negative value if x < y
```

Pull request description:
feat: Sort array
<!-- ℹ お読みください
PRありがとうございます！ PRを作成する前に、以下をご確認ください:
- 可能であればタイトルに、以下で示すようなPRの種類が分かるキーワードをプリフィクスしてください。
  - fix / refactor / feat / enhance / perf / chore
  - また、PRの粒度が適切であることを確認してください。ひとつのPRに複数の種類の変更や関心を含めることは避けてください。
- このPRによって解決されるIssueがある場合は、そのIssueへの参照を本文内に含めてください。
- CHANGELOG.mdに変更点を追記してください。リファクタリングなど、利用者に影響を与えない変更についてはこの限りではありません。
- この変更により新たに作成、もしくは更新すべきドキュメントがないか確認してください。
- 機能追加やバグ修正をした場合は、可能であればテストケースを追加してください。
- テスト、Lintが通っていることを予め確認してください。
  - `npm run test`、`npm run lint`でぞれぞれ実施可能です
- `npm run api`を実行してAPIレポートを更新し、差分がある場合はコミットしてください。
ご協力ありがとうございます🤗
-->
<!-- ℹ README
Thank you for your PR! Before creating a PR, please check the following:
- If possible, prefix the title with a keyword that identifies the type of this PR, as shown below.
  - fix / refactor / feat / enhance / perf / chore
  - Also, make sure that the granularity of this PR is appropriate. Please do not include more than one type of change or interest in a single PR.
- If there is an Issue which will be resolved by this PR, please include a reference to the Issue in the text.
- Please add the summary of the changes to CHANGELOG.md. However, this is not necessary for changes that do not affect the users, such as refactoring.
- Check if there are any documents that need to be created or updated due to this change.
- If you have added a feature or fixed a bug, please add a test case if possible.
- Please make sure that tests and Lint are passed in advance.
  - You can run it with `npm run test` and `npm run lint`.
- Run `npm run api` to update the API report and commit it if there are any diffs.
Thanks for your cooperation 🤗
-->

# What
<!-- このPRで何をしたのか？ どう変わるのか？ -->
<!-- What did you do with this PR? How will it change things? -->
`arr.sort(comp)` 関数と、String用のデフォルトcomp関数 `Str:lt(a, b)` `Str:gt(a, b)` を実装しました。
JSのArray.sortを利用しようとするとasyncなcomp処理を渡せなかったため、マージソートを実装しています。

Str:lt Str:gt という名前は微妙な気もしています。Str:asc Str:descの方が良いかも？


# Why
<!-- なぜそうするのか？ どういう意図なのか？ 何が困っているのか？ -->
<!-- Why do you do it? What are your intentions? What is the problem? -->
close #253 
# Additional info (optional)
<!-- テスト観点など -->
<!-- Test perspective, etc -->

```
var a = []
for(let i = 0, n) {
  a[i] = i
}
a.sort(@(a, b) {a - b})
```

のようなコードで計測した実行時間はn=400で280msほどでした。(for文での初期化処理を含む)

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index c2c56c0..de7586a 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,5 +1,5 @@
 [Read translated version (en)](./translations/en/CHANGELOG.md)
-
+- array.sortとString用比較関数Str:lt, Str:gtの追加
 # 0.13.1
 - Json:stringifyに関数を渡すと不正な値が生成されるのを修正
 
diff --git a/docs/std.md b/docs/std.md
index 5add719..7f59d59 100644
--- a/docs/std.md
+++ b/docs/std.md
@@ -116,6 +116,14 @@ _min_ および _max_ を渡した場合、_min_ <= x, x <= _max_ の整数、
 型: `str`  
 改行コード(LF)です。  
 
+### #Str:lt(a: str, b: str): num
+a < b ならば -1、a == b ならば 0、a > b ならば 1 を返します。
+arr.sortの比較関数として使用できます。
+
+### #Str:gt(a: str, b: str): num
+a > b ならば -1、a == b ならば 0、a < b ならば 1 を返します。
+arr.sortの比較関数として使用できます。
+
 ### @(_v_: str).to_num(): num | null
 値を表す数値を取得します。  
 
@@ -182,6 +190,9 @@ _min_ および _max_ を渡した場合、_min_ <= x, x <= _max_ の整数、
 ### @(_v_: arr).copy(): arr
 配列のコピーを生成します。  
 
+### @(_v_: arr).sort(comp: @(a: value, b: value)): arr
+配列をソートします。compにはStr:lt, Str:gtと同様のnumを返す比較関数を渡します。
+
 ## :: Obj
 
 ### @Obj:keys(_v_: obj): arr
diff --git a/src/interpreter/lib/std.ts b/src/interpreter/lib/std.ts
index 3c3dd74..23c7a6b 100644
--- a/src/interpreter/lib/std.ts
+++ b/src/interpreter/lib/std.ts
@@ -276,6 +276,29 @@ export const std: Record<string, Value> = {
 
 	//#region Str
 	'Str:lf': STR('\n'),
+
+	'Str:lt': FN_NATIVE(([a, b]) => {
+		assertString(a);
+		assertString(b);
+		if (a.value < b.value) {
+			return NUM(-1);
+		}else if (a.value === b.value){
+			return NUM(0);
+		}else {
+			return NUM(1);
+		}
+	}),
+	'Str:gt': FN_NATIVE(([a, b]) => {
+		assertString(a);
+		assertString(b);
+		if (a.value > b.value) {
+			return NUM(-1);
+		}else if (a.value === b.value){
+			return NUM(0);
+		}else {
+			return NUM(1);
+		}
+	}),
 	//#endregion
 
 	//#region Arr
diff --git a/src/interpreter/primitive-props.ts b/src/interpreter/primitive-props.ts
index 1c97d7c..c848008 100644
--- a/src/interpreter/primitive-props.ts
+++ b/src/interpreter/primitive-props.ts
@@ -174,5 +174,38 @@ export const PRIMITIVE_PROPS = {
 		copy: (target: VArr): VFn => FN_NATIVE(async ([], opts) => {
 			return ARR([...target.value]);
 		}),
+		sort: (target: VArr): VFn => FN_NATIVE(async ([comp], opts) => {
+			const mergeSort = async (arr: Value[], comp: VFn): Promise<Value[]> => {
+				if (arr.length <= 1) return arr;
+				const mid = Math.floor(arr.length / 2);
+				const left = await mergeSort(arr.slice(0, mid), comp);
+				const right = await mergeSort(arr.slice(mid), comp);
+				return merge(left, right, comp);
+			}
+			const merge = async (left: Value[], right: Value[], comp: VFn): Promise<Value[]> => {
+				const result: Value[] = [];
+				let leftIndex = 0;
+				let rightIndex = 0;
+				while (leftIndex < left.length && rightIndex < right.length) {
+					const l = left[leftIndex] as Value;
+					const r = right[rightIndex] as Value;
+					let compValue = await opts.call(comp, [l, r]);
+					assertNumber(compValue);
+					if (compValue.value < 0) {
+						result.push(left[leftIndex] as Value);
+						leftIndex++;
+					} else {
+						result.push(right[rightIndex] as Value);
+						rightIndex++;
+					}
+				}
+				return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
+			}
+
+			assertFunction(comp);
+			assertArray(target);
+			target.value = await mergeSort(target.value, comp);
+			return target
+		}),
 	},
 } as const;


Test patch:
diff --git a/test/index.ts b/test/index.ts
index 87ec9e1..60f8858 100644
--- a/test/index.ts
+++ b/test/index.ts
@@ -2349,6 +2349,41 @@ describe('primitive props', () => {
 				ARR([NUM(1), NUM(2), NUM(3)])
 			]));
 		});
+	test.concurrent('sort num array', async () => {
+			const res = await exe(`
+					var arr = [2, 10, 3]
+					let comp = @(a, b) { a - b }
+					arr.sort(comp)
+					<: arr
+				`);
+			eq(res, ARR([NUM(2), NUM(3), NUM(10)]));
+	});
+	test.concurrent('sort string array (with Str:lt)', async () => {
+			const res = await exe(`
+					var arr = ["hoge", "huga", "piyo", "hoge"]
+					arr.sort(Str:lt)
+					<: arr
+				`);
+			eq(res, ARR([STR('hoge'), STR('hoge'), STR('huga'), STR('piyo')]));
+	});
+	test.concurrent('sort string array (with Str:gt)', async () => {
+			const res = await exe(`
+					var arr = ["hoge", "huga", "piyo", "hoge"]
+					arr.sort(Str:gt)
+					<: arr
+				`);
+		eq(res, ARR([ STR('piyo'),  STR('huga'), STR('hoge'), STR('hoge')]));
+	});
+	test.concurrent('sort object array', async () => {
+			const res = await exe(`
+					var arr = [{x: 2}, {x: 10}, {x: 3}]
+					let comp = @(a, b) { a.x - b.x }
+
+					arr.sort(comp)
+					<: arr
+				`);
+			eq(res, ARR([OBJ(new Map([['x', NUM(2)]])), OBJ(new Map([['x', NUM(3)]])), OBJ(new Map([['x', NUM(10)]]))]));
+	});
 	});
 });