# 機能設計書 80-sort_by

## 概要

本ドキュメントは、Hack Standard Library（HSL）のVec名前空間が提供する`sort_by`関数の機能設計を記述する。この関数は、Traversableの各要素から計算したスカラープロパティに基づいてソートした新しいvecを生成する機能を提供する。

### 本機能の処理概要

`Vec\sort_by`関数は、各要素からスカラー値を抽出する関数を受け取り、そのスカラー値に基づいてソートを行う。これにより、オブジェクトの特定のプロパティでソートする、文字列の長さでソートするなど、柔軟なソート条件を簡潔に記述できる。

**業務上の目的・背景**：実際のアプリケーション開発では、オブジェクトや複雑なデータ構造を特定の属性でソートする必要がある。例えば、ユーザーを名前順にソートする、商品を価格順にソートするなどである。`sort_by`関数は、このようなプロパティベースのソートを、比較関数を直接書くことなく簡潔に実装することを可能にする。

**機能の利用シーン**：
- オブジェクト配列を特定のプロパティでソートする
- 文字列配列を長さでソートする
- 文字列を逆順にした値でソートする
- 複合キー（タプル）でソートする
- 日付や数値の計算結果でソートする

**主要な処理内容**：
1. 入力としてTraversable、スカラー関数、オプションの比較関数を受け取る
2. Traversableをvecに変換する
3. 各要素にスカラー関数を適用してソートキーを計算する
4. ソートキーでソートを実行する
5. 元の要素を新しい順序で並べ替えたvecを返却する

**関連システム・外部連携**：本機能は純粋な関数であり、外部システムとの連携はない。内部でDict\map、\uasort、\asort、map_with_keyを使用する。

**権限による制御**：本機能はスカラー関数と比較関数のコンテキストを伝播する（`[ctx $scalar_func, ctx $comparator]`）。これらの関数が純粋であれば、sort_by関数全体も純粋として扱われる。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | 画面なし | - | 本プロジェクトはUIを持たないライブラリ |

## 機能種別

計算処理 / データ変換

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| $traversable | Traversable<Tv> | Yes | ソート対象のコレクション | なし（空コレクションも許容） |
| $scalar_func | (function(Tv)[_]: Ts) | Yes | 各要素からソートキーを計算する関数 | なし |
| $comparator | ?(function(Ts, Ts)[_]: num) | No | ソートキーを比較するカスタム関数（デフォルト: null） | なし |

### 入力データソース

関数引数として直接渡される。スカラー関数は各要素からソートキーを抽出し、比較関数はそのソートキーを比較する。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | vec<Tv> | ソートされた新しいvec（元の要素型を保持） |

### 出力先

関数の戻り値として呼び出し元に返却される。

## 処理フロー

### 処理シーケンス

```
1. Traversableをvecに変換
   └─ $vec = cast_clear_legacy_array_mark($traversable)
2. 各要素にスカラー関数を適用してソートキーを計算
   └─ $order_by = Dict\map($vec, $scalar_func)
3. 比較関数の有無を判定
   └─ if ($comparator)
3a. 比較関数がある場合: uasortでソート
    └─ \uasort(inout $order_by, $comparator)
3b. 比較関数がない場合: asortでソート
    └─ \asort(inout $order_by)
4. ソートされた順序に基づいて元の要素を並べ替え
   └─ map_with_key($order_by, ($k, $v) ==> $vec[$k])
5. 結果を返却
   └─ return map_with_key(...)
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B[$traversableをvecに変換]
    B --> C[Dict\mapでスカラー値を計算]
    C --> D{$comparatorが指定されているか}
    D -->|Yes| E[\uasort inout $order_by, $comparator\]
    D -->|No| F[\asort inout $order_by\]
    E --> G[map_with_keyで元の要素を並べ替え]
    F --> G
    G --> H[結果を返却]
    H --> I[終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-80-01 | スカラー値ソート | スカラー関数の戻り値でソートする | 常時 |
| BR-80-02 | デフォルト昇順 | 比較関数なしの場合は昇順ソート | $comparator = null |
| BR-80-03 | 元要素保持 | 出力には元の要素（Tv型）が含まれる | 常時 |
| BR-80-04 | 空入力処理 | 空のTraversableは空のvecを返す | 入力が空の場合 |
| BR-80-05 | キー破棄 | KeyedTraversableのキーは破棄される | KeyedTraversable入力時 |
| BR-80-06 | タプルソート | スカラー関数がタプルを返す場合、要素ごとにソート | タプル返却時 |
| BR-80-07 | 安定ソート | 等しいスカラー値の要素は元の順序を保持 | 常時 |
| BR-80-08 | 非破壊操作 | 入力のTraversableは変更されない | 常時 |

### 計算ロジック

1. スカラー関数を各要素に適用してソートキーを生成
2. ソートキーでソートを行い、インデックスの順序を決定
3. 元のvecからインデックス順に要素を取り出して新しいvecを構築

## データベース操作仕様

### 操作別データベース影響一覧

本機能はデータベース操作を行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | スカラー関数内例外 | $scalar_funcが例外をスローした場合 | 呼び出し元で適切にハンドリング |
| - | 比較関数内例外 | $comparatorが例外をスローした場合 | 呼び出し元で適切にハンドリング |

### リトライ仕様

本機能にリトライ仕様はない。

## トランザクション仕様

本機能はデータベーストランザクションを使用しない。

## パフォーマンス要件

- 時間計算量: O((n log n) * c + n * s) - nは入力要素数、cは比較関数の計算量（デフォルトO(1)）、sはスカラー関数の計算量
- 空間計算量: O(n) - 結果格納用のvecとソートキー用のdict

## セキュリティ考慮事項

本機能は純粋関数（スカラー関数と比較関数が純粋な場合）であり、特別なセキュリティ考慮事項はない。

## 備考

- 単純な値のソートには`Vec\sort`を使用する
- スカラー関数がタプルを返す場合、タプルの要素順に多段ソートが行われる
- コンテキスト記法`[ctx $scalar_func, ctx $comparator]`により、両関数の副作用特性が伝播される
- 内部でuasort/asortを使用しているため、ソートは安定（stable）である

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

`sort_by`関数は2段階の型変換を行う。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | Hack言語組み込み型 | - | Tv（元の要素型）とTs（スカラー型）の関係を理解する |
| 1-2 | Dict\map | HSL Dict名前空間 | 各要素にスカラー関数を適用してdictを生成する処理 |

**読解のコツ**: sort_byは「要素→スカラー値→ソート→元の要素を並べ替え」という流れで動作する。Dict\mapでインデックスとスカラー値のマッピングを作成し、ソート後にインデックスを使って元の要素を取り出す。

#### Step 2: 補助関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | cast.php | `src/vec/cast.php` | cast_clear_legacy_array_mark関数の実装を確認 |
| 2-2 | PHPの\uasort | PHP組み込み関数 | ユーザー定義比較関数でソート（キー保持） |
| 2-3 | PHPの\asort | PHP組み込み関数 | 値でソート（キー保持） |
| 2-4 | map_with_key | Vec名前空間 | キーと値を使った変換 |

#### Step 3: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | order.php | `src/vec/order.php` | sort_by関数の定義と実装を確認 |

**主要処理フロー**:
1. **122-126行目**: 関数シグネチャ - Traversable、スカラー関数、比較関数を受け取る
2. **127行目**: cast_clear_legacy_array_markでvecに変換
3. **128行目**: Dict\mapでスカラー値を計算
4. **129-133行目**: 比較関数の有無で分岐してソート
5. **134行目**: map_with_keyで元の要素を並べ替え

#### Step 4: テストケースを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | VecOrderTest.php | `tests/vec/VecOrderTest.php` | sort_by関数のテストケースを確認 |

**主要処理フロー**:
- **191-240行目**: provideTestSortByメソッドで豊富なテストデータを提供
- **193-198行目**: 文字列を逆順にした値でソート
- **207-211行目**: 比較関数で降順ソート
- **212-218行目**: すべて同じスカラー値の場合（元の順序保持）
- **219-224行目**: 文字列の長さでソート
- **232-238行目**: タプルを返すスカラー関数での多段ソート
- **242-251行目**: 実際のテスト実行メソッド

### プログラム呼び出し階層図

```
呼び出し元コード
    │
    └─ Vec\sort_by($traversable, $scalar_func, $comparator)
           │
           ├─ cast_clear_legacy_array_mark($traversable) → $vec
           │
           ├─ Dict\map($vec, $scalar_func) → $order_by
           │
           ├─ $comparator の有無で分岐
           │      │
           │      ├─ \uasort(inout $order_by, $comparator)（比較関数あり）
           │      │
           │      └─ \asort(inout $order_by)（比較関数なし）
           │
           └─ map_with_key($order_by, ($k, $v) ==> $vec[$k])
                  │
                  └─ ソートされた順序で元の要素を取得
```

### データフロー図

```
[入力]                              [処理]                         [出力]

Traversable<Tv>               ───▶  vecに変換: $vec
                                          │
                                          ▼
$scalar_func(Tv): Ts          ───▶  Dict\map: $order_by
                                          │
                                          ▼
$comparator                   ───▶  uasort/asort
                                          │
                                          ▼
                                    map_with_key           ───▶  vec<Tv>
                                    ($k, $v) ==> $vec[$k]        (ソート済み)

例:
vec['the', 'quick', 'brown', 'fox', 'jumped']
     │
     ▼ $scalar_func = Str\reverse
dict[0 => 'eht', 1 => 'kciuq', 2 => 'nworb', 3 => 'xof', 4 => 'depmuj']
     │
     ▼ asort
dict[4 => 'depmuj', 0 => 'eht', 1 => 'kciuq', 2 => 'nworb', 3 => 'xof']
     │
     ▼ map_with_key
vec['jumped', 'the', 'quick', 'brown', 'fox']
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| order.php | `src/vec/order.php` | ソース | sort_by関数の実装 |
| cast.php | `src/vec/cast.php` | ソース | cast_clear_legacy_array_mark関数の実装 |
| transform.php | `src/vec/transform.php` | ソース | map_with_key関数の実装 |
| VecOrderTest.php | `tests/vec/VecOrderTest.php` | テスト | sort_by関数のユニットテスト |
