# 機能設計書 36-Array拡張

## 概要

本ドキュメントは、mrubyのArrayクラスにassoc, compact, flatten, rotate, uniq, values_at, slice!, insert, bsearch, combination, permutation, product, fill, fetch, difference, union, intersection等の拡張メソッドを追加するgem（mruby-array-ext）の機能設計を記述する。

### 本機能の処理概要

**業務上の目的・背景**：CRuby互換のArray操作メソッドを提供し、配列操作の表現力を大幅に向上させる。集合演算（union, intersection, difference）、構造変換（flatten, transpose, compact）、検索（assoc, rassoc, bsearch）、組合せ（combination, permutation, product）等を利用可能にする。

**機能の利用シーン**：データの重複除去（uniq）、nil除去（compact）、集合演算（|, &, -, union, intersection, difference）、ネスト配列の平坦化（flatten）、二分探索（bsearch）、組合せ列挙（combination, permutation）、配列回転（rotate）、パターンマッチング（deconstruct）等。

**主要な処理内容**：
1. 集合演算: -(差集合), |(和集合), &(積集合), union, intersection, difference, intersect?
2. 構造変換: flatten/flatten!, compact/compact!, rotate/rotate!, transpose
3. 検索: assoc, rassoc, at, bsearch, bsearch_index, find, rfind
4. 取得: values_at, fetch, fetch_values, dig
5. 変更: slice!, insert, fill, uniq/uniq!, delete_if, reject!, keep_if, select!
6. 組合せ: combination, permutation, repeated_combination, repeated_permutation, product
7. パターンマッチング: deconstruct

**関連システム・外部連携**：なし。

**権限による制御**：なし。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面なし |

## 機能種別

コレクション操作 / 集合演算 / 検索処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| other_ary | Array | Yes(集合演算) | 演算相手配列 | Arrayであること |
| level | Integer | No(flatten) | 平坦化の深さ | -1で無制限 |
| count | Integer | No(rotate) | 回転量 | デフォルト1 |
| n | Integer | Yes(combination等) | 組合せ長 | 非負整数 |
| index | Integer | Yes(fetch等) | インデックス | 負の値は末尾からカウント |
| block | Block | No | 各要素に適用するブロック | - |

### 入力データソース

メソッド呼び出し時の引数。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Array | Array | 各種操作の結果配列 |
| Object | Object | at, fetch, bsearch等の検索結果 |
| Boolean | true/false | intersect?の判定結果 |
| nil | nil | 見つからなかった場合 |

### 出力先

メソッドの戻り値。

## 処理フロー

### 処理シーケンス

```
1. 集合演算（union/intersection/difference）
   └─ 小配列はO(n*m)線形探索、大配列(>32要素)はkhashセットでO(n+m)
2. flatten
   └─ スタックベースの反復アルゴリズムで再帰的配列を平坦化
3. bsearch
   └─ 二分探索でfind-minimum/find-anyモードをサポート
4. combination/permutation
   └─ 再帰的生成（Rubyレベル）またはCステート管理（repeated_combination）
```

### フローチャート

```mermaid
flowchart TD
    A[集合演算呼び出し] --> B{total_len > 32?}
    B -->|Yes| C[khashセット構築]
    C --> D[ハッシュベース重複除去/判定]
    B -->|No| E[線形探索]
    D --> F[結果配列返却]
    E --> F
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | ハッシュ最適化閾値 | 要素数合計32超でkhashベースのアルゴリズムに切り替え | 集合演算・uniq |
| BR-02 | flatten循環検出なし | mruby版flattenは循環参照を検出しない | flatten |
| BR-03 | bang!のnil返却 | compact!/flatten!/uniq!は変更がなかった場合nilを返す | 破壊的メソッド |
| BR-04 | fetchのデフォルト動作 | デフォルト値もブロックもない場合はIndexError | fetch |
| BR-05 | 負インデックス | 負の値は配列末尾からカウント | 多くのメソッド |

### 計算ロジック

- **flatten**: スタックに配列とインデックスをpushし、ネスト配列を発見したら新しい配列をpush。levelで深さ制限。
- **rotate!**: 三回reverseアルゴリズム `rev(0,len); rev(0,len-idx); rev(len-idx,len)`

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

該当なし。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | IndexError | fetchで範囲外かつデフォルトなし | "index X outside of array bounds" |
| - | TypeError | 集合演算の引数がArrayでない | "can't convert passed argument to Array" |
| - | TypeError | productの引数がArrayでない | "no implicit conversion into Array" |
| - | IndexError | transposeで要素サイズ不一致 | "element size differs" |
| - | RuntimeError | 反復中の配列変更 | "array modified during iteration" |

### リトライ仕様

なし。

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

なし。

## パフォーマンス要件

- 集合演算: 小配列O(n*m)、大配列O(n+m)（khashによるハッシュベース）
- flatten: O(全要素数)
- bsearch: O(log n)
- combination: O(C(n,k) * k)

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

- MRB_ENSUREマクロでkhashの確実なクリーンアップを保証（メモリリーク防止）

## 備考

- CとRubyのハイブリッド実装
- SET_OP_HASH_THRESHOLD=32でハッシュベースアルゴリズムへの切替閾値を定義
- repeated_combination/repeated_permutationはCのステート管理オブジェクト（CombinationState）を使用

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | array.c | `mrbgems/mruby-array-ext/src/array.c` | ary_set_t（khashセット）、mrb_combination_state構造体 |

**読解のコツ**: `KHASH_DECLARE`/`KHASH_DEFINE`マクロでkhashのハッシュセット型を宣言している。`SET_OP_HASH_THRESHOLD`が集合演算のアルゴリズム切替閾値。

#### Step 2: C実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | array.c | `mrbgems/mruby-array-ext/src/array.c` | 各メソッドのC実装 |

**主要処理フロー**:
- **77-89行目**: ary_assoc - 連想配列検索
- **194-236行目**: ary_slice_bang - 破壊的スライス
- **249-269行目**: ary_compact_bang - nil除去
- **306-330行目**: ary_rotate - 配列回転
- **359-399行目**: ary_rotate_bang - 破壊的回転（三回reverseアルゴリズム）
- **476-524行目**: ary_subtract_internal - 差集合（ハッシュ/線形切替）
- **615-658行目**: ary_union_internal - 和集合
- **727-791行目**: ary_intersection_internal - 積集合
- **1087-1151行目**: ary_uniq - 重複除去
- **1154-1191行目**: flatten_internal - スタックベース平坦化
- **1437-1537行目**: ary_combination_init/next - 組合せステート管理

#### Step 3: Ruby実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | array.rb | `mrbgems/mruby-array-ext/mrblib/array.rb` | Ruby実装メソッド群 |

**主要処理フロー**:
- **18-38行目**: uniq!/uniq - ブロック付き重複除去
- **99-114行目**: fetch - インデックス取得
- **149-170行目**: fill - 配列充填
- **290-298行目**: bsearch - 二分探索
- **312-345行目**: bsearch_index - 二分探索インデックス
- **452-474行目**: permutation - 順列生成
- **499-522行目**: combination - 組合せ生成
- **613-645行目**: product - 直積

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

```
Array#union / Array#|
    +-- ary_union_internal
            +-- [大配列] ary_init_temp_set -> ary_union_body -> ary_destroy_temp_set
            +-- [小配列] add_uniq (線形探索)

Array#flatten
    +-- flatten_internal (スタックベース反復)

Array#combination
    +-- [Ruby] 再帰的生成

Array#repeated_combination
    +-- __combination_init (Cステート生成)
    +-- __combination_next (Cステート進行)
```

### データフロー図

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

Array (self)    ──────▶ C/Ruby処理関数 ──────▶ 新規Array / self変更
other_ary等引数          集合演算/変換処理        結果配列
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| array.c | `mrbgems/mruby-array-ext/src/array.c` | ソース(C) | C実装メソッド群 |
| array.rb | `mrbgems/mruby-array-ext/mrblib/array.rb` | ソース(Ruby) | Ruby実装メソッド群 |
| mrbgem.rake | `mrbgems/mruby-array-ext/mrbgem.rake` | 設定 | gem定義 |
| array.rb | `mrbgems/mruby-array-ext/test/array.rb` | テスト | テストケース |
