# 機能設計書 79-sort

## 概要

本ドキュメントは、Hack Standard Library（HSL）のVec名前空間が提供する`sort`関数の機能設計を記述する。この関数は、Traversableの要素をソートした新しいvecを生成する機能を提供する。

### 本機能の処理概要

`Vec\sort`関数は、入力されたTraversableの要素を昇順（または指定した比較関数に基づいて）ソートした新しいvecを返却する。オプションで比較関数を指定することで、カスタムのソート順序を定義できる。

**業務上の目的・背景**：データのソートは、表示順の制御、検索の効率化、分析前のデータ整理など、多くの場面で必要となる。`sort`関数は、このようなソート処理を型安全かつ柔軟に実行することを可能にする。比較関数を指定することで、様々なソート条件に対応できる。

**機能の利用シーン**：
- 数値配列を昇順または降順にソートする
- 文字列配列をアルファベット順にソートする
- カスタム比較関数で複雑なソート条件を適用する
- データを表示する前に整列する

**主要な処理内容**：
1. 入力としてTraversableとオプションの比較関数を受け取る
2. Traversableをvecに変換する
3. 比較関数が指定された場合はusort、そうでなければsortでソートする
4. ソートされたvecを返却する

**関連システム・外部連携**：本機能は純粋な関数であり、外部システムとの連携はない。内部でPHPの組み込み関数\usortまたは\sortを使用する。

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

## 関連画面

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

## 機能種別

計算処理 / データ変換

## 入力仕様

### 入力パラメータ

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

### 入力データソース

関数引数として直接渡される。比較関数は、2つの要素を受け取り、負の数（最初の要素が小さい）、0（等しい）、正の数（最初の要素が大きい）を返す必要がある。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | vec<Tv> | ソートされた新しいvec |

### 出力先

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

## 処理フロー

### 処理シーケンス

```
1. Traversableをvecに変換
   └─ $vec = cast_clear_legacy_array_mark($traversable)
2. 比較関数の有無を判定
   └─ if ($comparator)
3a. 比較関数がある場合: usortでソート
    └─ \usort(inout $vec, $comparator)
3b. 比較関数がない場合: sortでソート
    └─ \sort(inout $vec)
4. ソートされたvecを返却
   └─ return $vec
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B[$traversableをvecに変換]
    B --> C{$comparatorが指定されているか}
    C -->|Yes| D[\usort inout $vec, $comparator\]
    C -->|No| E[\sort inout $vec\]
    D --> F[ソートされた$vecを返却]
    E --> F
    F --> G[終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-79-01 | デフォルト昇順 | 比較関数なしの場合は昇順ソート | $comparator = null |
| BR-79-02 | 比較関数動作 | 負:第1引数が前、0:同値、正:第1引数が後 | $comparatorあり |
| BR-79-03 | 空入力処理 | 空のTraversableは空のvecを返す | 入力が空の場合 |
| BR-79-04 | キー破棄 | KeyedTraversableのキーは破棄される | KeyedTraversable入力時 |
| BR-79-05 | 安定性非保証 | 等しい要素の相対順序は保証されない | 常時 |
| BR-79-06 | 非破壊操作 | 入力のTraversableは変更されない | 常時 |

### 計算ロジック

比較関数のセマンティクス（<=>演算子と同様）：
- `$comparator($a, $b) < 0` の場合、$aは$bより前に配置される
- `$comparator($a, $b) === 0` の場合、$aと$bは等しい
- `$comparator($a, $b) > 0` の場合、$aは$bより後に配置される

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

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

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

## エラー処理

### エラーケース一覧

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

### リトライ仕様

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

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

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

## パフォーマンス要件

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

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

本機能は純粋関数（比較関数が純粋な場合）であり、特別なセキュリティ考慮事項はない。比較関数内でのセキュリティ処理は呼び出し元の責務となる。

## 備考

- スカラープロパティによるソートが必要な場合は`Vec\sort_by`を使用する
- コンテキスト記法`[ctx $comparator]`により、比較関数の副作用特性が伝播される
- PHPの\usortと\sortを内部で使用している

---

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

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

### 推奨読解順序

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

`sort`関数は比較関数を使用したソートを行う。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | Hack言語組み込み型 | - | Traversable<Tv>とvec<Tv>の関係を理解する |
| 1-2 | 比較関数の型 | - | `(function(Tv, Tv)[_]: num)`は2つの要素を受け取り数値を返す関数 |

**読解のコツ**: 比較関数の戻り値は`num`型（intまたはfloat）で、<=>演算子と同じセマンティクスを持つ。`[_]`はコンテキストをキャプチャすることを示す。

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | cast.php | `src/vec/cast.php` | cast_clear_legacy_array_mark関数の実装を確認 |
| 2-2 | PHPの\usort | PHP組み込み関数 | ユーザー定義の比較関数でソートする関数 |
| 2-3 | PHPの\sort | PHP組み込み関数 | デフォルトの昇順ソート関数 |

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

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

**主要処理フロー**:
1. **91-94行目**: 関数シグネチャ - Traversableとオプションの比較関数を受け取る
2. **95行目**: cast_clear_legacy_array_markでvecに変換
3. **96-99行目**: 比較関数の有無で分岐
4. **97行目**: 比較関数ありの場合は\usort
5. **99行目**: 比較関数なしの場合は\sort
6. **101行目**: 結果を返却

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

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

**主要処理フロー**:
- **160-180行目**: provideTestSortメソッドでテストデータを提供
- **162-166行目**: 文字列配列のデフォルトソート
- **167-172行目**: カスタム比較関数（2文字目でソート）
- **173行目**: 数値のソート（負数含む）
- **174-178行目**: Iteratorのソート
- **182-189行目**: 実際のテスト実行メソッド

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

```
呼び出し元コード
    │
    └─ Vec\sort($traversable, $comparator)
           │
           ├─ cast_clear_legacy_array_mark($traversable) → $vec
           │
           └─ $comparator の有無で分岐
                  │
                  ├─ \usort(inout $vec, $comparator)（比較関数あり）
                  │
                  └─ \sort(inout $vec)（比較関数なし）
```

### データフロー図

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

Traversable<Tv>            ───┐
                              │
                              ├──▶  vecに変換 → ソート  ───▶  vec<Tv>
                              │                               (ソート済み)
$comparator                ───┘

例:
vec['the', 'quick', 'brown', 'fox']  ───▶  sort処理  ───▶  vec['brown', 'fox', 'quick', 'the']
```

### 関連ファイル一覧

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