# 機能設計書 46-algorithm

## 概要

本ドキュメントは、Nim標準ライブラリの`algorithm`モジュールの機能設計について記述する。`algorithm`は、`openArray`に対する一般的なアルゴリズム（ソート、二分探索、回転、順列等）を提供するモジュールである。

### 本機能の処理概要

**業務上の目的・背景**：`algorithm`モジュールは、配列やシーケンスに対する基本的なアルゴリズム操作を提供する。マージソートによる安定ソート、効率的な二分探索、配列の回転、順列生成など、多くのプログラミングタスクで必要とされる基本操作を提供する。ソートの安定性保証と最悪計算量O(n log n)により、信頼性の高いソート処理を実現。

**機能の利用シーン**：
- データのソート：数値や文字列、カスタムオブジェクトの整列
- 二分探索：ソート済み配列での高速な検索
- 挿入位置の決定：lowerBound/upperBoundによるソート済み配列への挿入
- 配列の反転・回転：データの順序変更
- 順列生成：組み合わせ最適化問題での全探索
- デカルト積：複数の配列の組み合わせ生成

**主要な処理内容**：
1. ソート（sort, sorted）：マージソートによる安定ソート
2. 二分探索（binarySearch）：ソート済み配列での検索
3. 境界検索（lowerBound, upperBound）：挿入位置の決定
4. 配列操作（fill, reverse, reversed）：要素の充填、反転
5. 回転（rotateLeft, rotatedLeft）：配列の左回転
6. 順列（nextPermutation, prevPermutation）：辞書順での次/前の順列
7. 積集合（product）：デカルト積の生成
8. マージ（merge）：ソート済み配列の結合
9. ソート検査（isSorted）：ソート済みかの確認

**関連システム・外部連携**：本モジュールは純粋なアルゴリズムライブラリであり、外部システムとの直接連携はない。`sequtils`モジュールと組み合わせて使用されることが多い。

**権限による制御**：該当なし（ライブラリモジュールのため）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本モジュールはCLIライブラリのため画面関連なし |

## 機能種別

アルゴリズムライブラリ / コレクション操作 / ソート・検索

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| a | openArray[T] | Yes | 操作対象の配列 | - |
| cmp | proc(x, y: T): int | No | 比較関数 | 戻り値: <0, 0, >0 |
| order | SortOrder | No | ソート順序（デフォルト: Ascending） | - |
| key | T / K | Yes（検索時） | 検索対象のキー | - |
| dist | int | Yes（回転時） | 回転距離 | 正負の整数 |

### 入力データソース

- プログラム内の配列・シーケンス
- カスタム比較関数

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | seq[T] | ソート・反転・回転後の新規シーケンス |
| result | int | 検索結果インデックス（-1は未発見） |
| result | bool | ソート済み判定（isSorted）、順列生成結果（nextPermutation等） |
| result | seq[seq[T]] | デカルト積（product） |

### 出力先

呼び出し元プログラムへの戻り値として返却、またはin-place変更

## 処理フロー

### 処理シーケンス

```
1. sort処理（マージソート）
   └─ 一時バッファ（n/2）を確保
   └─ ボトムアップで隣接ブロックをマージ
   └─ ブロックサイズを2倍にしながら繰り返し

2. binarySearch処理
   └─ 配列長が2のべき乗の場合: シフト演算で高速化
   └─ それ以外: 標準的な二分探索

3. lowerBound/upperBound処理
   └─ 二分探索で挿入位置を決定
   └─ lowerBound: key以上の最初の位置
   └─ upperBound: keyより大きい最初の位置

4. rotateLeft処理
   └─ C++のstd::rotateをポート
   └─ スワップベースの効率的な回転
```

### フローチャート

```mermaid
flowchart TD
    A[algorithm操作] --> B{操作種別}
    B -->|sort| C[マージソート]
    B -->|binarySearch| D[二分探索]
    B -->|lowerBound/upperBound| E[境界検索]
    B -->|rotateLeft| F[左回転]
    B -->|nextPermutation| G[次の順列]
    C --> H[一時バッファ確保]
    H --> I[ボトムアップマージ]
    D --> J{長さが2のべき乗?}
    J -->|Yes| K[シフト演算最適化]
    J -->|No| L[標準二分探索]
    E --> M[挿入位置返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 安定ソート | 同値要素の相対順序を保持 | sort関数 |
| BR-02 | 最悪O(n log n) | マージソートによる保証 | sort関数 |
| BR-03 | 一時バッファ | n/2の一時領域を使用 | sort関数 |
| BR-04 | 二分探索前提 | binarySearch/lowerBound/upperBoundはソート済み配列を前提 | 検索関数 |
| BR-05 | 負の距離 | rotateLeftに負値を渡すと右回転 | rotateLeft |
| BR-06 | 順列の境界 | 最後/最初の順列でnextPermutation/prevPermutationはfalseを返却 | 順列関数 |

### 計算ロジック

- **SortOrder乗算**: `(x xor y) - y` （y = order.ord - 1）で符号を反転
- **lowerBound**: cmp(a[pos], key) < 0 の間、探索範囲を狭める
- **upperBound**: cmp(a[pos], key) <= 0 の間、探索範囲を狭める
- **rotateLeft**: modulo演算で距離を正規化

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

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

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | 本モジュールはデータベース操作を行わない |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IndexDefect | 範囲エラー | fill/reverse/rotateLeftで無効な範囲指定 | 有効な範囲を指定 |

### リトライ仕様

該当なし（同期処理のためリトライ不要）

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

該当なし（データベース操作なし）

## パフォーマンス要件

- **sort**: O(n log n)の時間計算量、O(n/2)の追加空間
- **binarySearch**: O(log n)の時間計算量
- **lowerBound/upperBound**: O(log n)の時間計算量
- **reverse/fill**: O(n)の時間計算量
- **rotateLeft**: O(n)の時間計算量
- **nextPermutation/prevPermutation**: O(n)の時間計算量
- **product**: O(∏|x[i]|)の時間計算量（指数的）

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

- 本モジュールはメモリ安全性を保証
- onlySafeCode = trueでshallowCopyを使用（安全な実装）
- gcDestructors定義時はmove semanticsを使用

## 備考

- Nim 1.5.1以降で追加された機能（merge）には`since`プラグマが付与
- sortedByItテンプレートは`it`変数をinjectする
- C++のstd::rotateをポートしたrotateInternal関数が内部で使用される

---

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

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

### 推奨読解順序

#### Step 1: 型定義とユーティリティを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | algorithm.nim | `lib/pure/algorithm.nim` | 51-69行目: SortOrder型と乗算演算子 |
| 1-2 | algorithm.nim | `lib/pure/algorithm.nim` | 71-98行目: fill関数 |

**読解のコツ**:
- **52-53行目**: `SortOrder = enum Descending, Ascending` - 0がDescending、1がAscending
- **55-69行目**: `*`演算子 - Descendingの場合符号を反転、`(x xor y) - y`で実現
- **71-98行目**: fill関数 - スライス指定版と全体版

#### Step 2: reverse/reversed操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | algorithm.nim | `lib/pure/algorithm.nim` | 101-153行目: reverse/reversed関数 |

**主要処理フロー**:
- **101-121行目**: reverse(slice) - 両端からswapで中央に向かって進行
- **123-136行目**: reverse(全体) - max(0, a.high)で空配列対応
- **138-149行目**: reversed - 新規シーケンスを作成して逆順コピー

#### Step 3: 二分探索を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | algorithm.nim | `lib/pure/algorithm.nim` | 160-217行目: binarySearch関数 |
| 3-2 | algorithm.nim | `lib/pure/algorithm.nim` | 222-320行目: lowerBound/upperBound関数 |

**主要処理フロー**:
- **182-195行目**: 2のべき乗長の場合の最適化 - `step = len shr 1`
- **196-209行目**: 標準的な二分探索
- **246-256行目**: lowerBound - `cmp < 0`で右に移動
- **296-306行目**: upperBound - `cmp <= 0`で右に移動

#### Step 4: マージソートを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | algorithm.nim | `lib/pure/algorithm.nim` | 322-328行目: `<-`テンプレート |
| 4-2 | algorithm.nim | `lib/pure/algorithm.nim` | 330-367行目: mergeAlt関数 |
| 4-3 | algorithm.nim | `lib/pure/algorithm.nim` | 369-420行目: sort関数 |

**主要処理フロー**:
- **322-328行目**: `<-`テンプレート - move/shallowCopy/copyMemの分岐
- **330-367行目**: mergeAlt - 2つのソート済み区間をマージ、336行目で最適化判定
- **412-420行目**: sort - ボトムアップマージソート、s=1から開始し2倍ずつ拡大

#### Step 5: sorted/sortedByItを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | algorithm.nim | `lib/pure/algorithm.nim` | 432-470行目: sorted関数 |
| 5-2 | algorithm.nim | `lib/pure/algorithm.nim` | 472-506行目: sortedByItテンプレート |

**主要処理フロー**:
- **432-452行目**: sorted - 新規シーケンスにコピーしてsort
- **472-506行目**: sortedByIt - `it`変数をinjectしてcmp関数を生成

#### Step 6: isSorted/mergeを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | algorithm.nim | `lib/pure/algorithm.nim` | 508-553行目: isSorted関数 |
| 6-2 | algorithm.nim | `lib/pure/algorithm.nim` | 555-645行目: merge関数 |

**主要処理フロー**:
- **530-533行目**: isSorted - 隣接要素を比較、順序違反があればfalse
- **555-630行目**: merge - 2つのソート済み配列を1つにマージ（安定）

#### Step 7: 回転・順列を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 7-1 | algorithm.nim | `lib/pure/algorithm.nim` | 684-757行目: nextPermutation/prevPermutation |
| 7-2 | algorithm.nim | `lib/pure/algorithm.nim` | 759-918行目: rotateLeft/rotatedLeft |

**主要処理フロー**:
- **684-722行目**: nextPermutation - 右端から降順区間を探し、交換・反転
- **759-797行目**: rotateInternal - C++ std::rotateのポート
- **813-849行目**: rotateLeft - modulo正規化後rotateInternal呼び出し

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

```
algorithm.nim (ユーザーコード)
    │
    ├─ ソート
    │   ├─ sort(a, cmp, order) → mergeAlt (ボトムアップ)
    │   │                            └─ `<-` (move/shallowCopy)
    │   ├─ sorted(a, cmp, order) → newSeq + sort
    │   └─ sortedByIt(seq, op) → sorted + inject `it`
    │
    ├─ 検索
    │   ├─ binarySearch(a, key, cmp) → 二分探索（2のべき乗最適化）
    │   ├─ lowerBound(a, key, cmp) → cmp < 0 で右移動
    │   └─ upperBound(a, key, cmp) → cmp <= 0 で右移動
    │
    ├─ 配列操作
    │   ├─ fill(a, first, last, value) → fillImpl
    │   ├─ reverse(a, first, last) → swap loop
    │   └─ reversed(a) → newSeq + 逆順コピー
    │
    ├─ 回転
    │   ├─ rotateLeft(a, slice, dist) → rotateInternal
    │   └─ rotatedLeft(a, slice, dist) → rotatedInternal
    │
    └─ 順列
        ├─ nextPermutation(x) → 降順区間探索 + swap + reverse
        └─ prevPermutation(x) → 昇順区間探索 + reverse + swap
```

### データフロー図

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

openArray[T] ──────────────▶ sort ─────────────────────────▶ 変更済み配列
                                 │
                                 └─ mergeAlt (n/2一時バッファ)

openArray[T] ──────────────▶ sorted ───────────────────────▶ seq[T] (新規)

openArray[T], key ─────────▶ binarySearch ─────────────────▶ int (index or -1)

openArray[T], key ─────────▶ lowerBound ───────────────────▶ int (挿入位置)

openArray[T], dist ────────▶ rotateLeft ───────────────────▶ 変更済み配列

openArray[T] ──────────────▶ nextPermutation ──────────────▶ bool, 変更済み配列

openArray[seq[T]] ─────────▶ product ──────────────────────▶ seq[seq[T]]
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| algorithm.nim | `lib/pure/algorithm.nim` | ソース | メインモジュール（全機能実装） |
| sequtils.nim | `lib/pure/collections/sequtils.nim` | ソース | 関連モジュール（シーケンス操作） |
| since.nim | `lib/std/private/since.nim` | ソース | バージョン管理プラグマ |
| assertions.nim | `lib/std/assertions.nim` | ソース | assert機能を提供 |
