# 機能設計書 46-Setクラス

## 概要

本ドキュメントは、mruby-set gemが提供するSetクラスの機能設計を記述する。重複のないコレクション（集合）を表現し、要素の追加・削除・集合演算（和集合・積集合・差集合・対称差）・比較演算を提供する。

### 本機能の処理概要

mruby-set gemは、数学的な集合の概念を実装するSetクラスを提供する。内部的にはkhash.hベースのハッシュテーブル（セットモード：キーのみ、値なし）を使用し、C言語(src/set.c)でコアメソッドを、Ruby(mrblib/set.rb)で高レベルメソッドを実装する。MRB_TT_SETという独自のオブジェクト型を持ち、RSet構造体にkhashテーブルを埋め込む形で実装されている。

**業務上の目的・背景**：集合はデータ処理において頻繁に使用される基本データ構造であり、重複排除、集合演算、メンバーシップ判定などの操作を効率的に行える。mrubyにSetクラスを提供することで、組み込み環境でも集合操作が可能になる。

**機能の利用シーン**：重複のないデータ管理、集合演算（和集合・積集合・差集合）、メンバーシップ判定、部分集合・上位集合の判定、データの分類（classify, divide）に使用される。

**主要な処理内容**：
1. 要素管理: add, delete, include?, size, empty?, clear, to_a
2. 集合演算: union(|), intersection(&), difference(-), xor(^)
3. 変更操作: merge, subtract, replace
4. 比較演算: ==, <=>, subset?, superset?, proper_subset?, proper_superset?
5. イテレーション: each, delete_if, keep_if, collect!, select!, reject!
6. その他: flatten, classify, divide, join, inspect

**関連システム・外部連携**：mruby-hash-ext、mruby-enumeratorに依存する。Enumerableモジュールをincludeしている。

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

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本機能はライブラリ機能であり、画面との関連はない |

## 機能種別

データ構造ライブラリ（集合操作）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| enum (initialize) | Enumerable | No | 初期要素のenumerable | eachメソッドを持つこと |
| block (initialize) | Block | No | 要素の前処理ブロック | - |
| object (add/delete/include?) | Any | Yes | 操作対象の要素 | - |
| other (集合演算) | Set/Enumerable | Yes | 相手の集合 | Set以外はeach可能なenumerable |

### 入力データソース

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

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| size戻り値 | Integer | 要素数 |
| include?戻り値 | Boolean | 包含判定結果 |
| to_a戻り値 | Array | 要素の配列 |
| 集合演算戻り値 | Set | 演算結果の新しいSet |
| ==戻り値 | Boolean | 等価判定結果 |
| <=>戻り値 | -1/0/+1/nil | 集合比較結果 |

### 出力先

メソッドの戻り値として呼び出し元に返却

## 処理フロー

### 処理シーケンス

```
1. Set.new(enum, &block)
   ├─ __initで内部khashテーブルを初期化
   ├─ enumがnilの場合: 空セット
   ├─ blockありの場合: 各要素をblock変換してadd
   └─ blockなしの場合: merge(enum)で一括追加

2. set.add(obj)
   ├─ kset_put(mrb, set, obj)でkhashテーブルに追加
   └─ mrb_field_write_barrier_valueでGCバリア設定

3. set & other (intersection)
   ├─ otherがSetの場合: C実装(__intersection)
   │   └─ 新しいSetを生成し、otherの要素がselfに含まれるものを追加
   └─ Set以外の場合: Ruby実装でeachイテレーション
```

### フローチャート

```mermaid
flowchart TD
    A[Set.new enum] --> B[__init: khash初期化]
    B --> C{enum nil?}
    C -->|Yes| D[空Set返却]
    C -->|No| E{block?}
    E -->|Yes| F[各要素をblock変換してadd]
    E -->|No| G[merge enum]

    H[set & other] --> I{other is Set?}
    I -->|Yes| J[C実装: __intersection]
    I -->|No| K[Ruby: each + include? でフィルタ]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-46-01 | 重複排除 | 同一要素（eql?が真）は1つだけ保持 | add操作時 |
| BR-46-02 | Set優先パス | 集合演算でotherがSetの場合、C実装の高速パスを使用 | 集合演算時 |
| BR-46-03 | Enumerable互換 | Set以外のenumerableも集合演算の相手として使用可 | merge, subtract等 |
| BR-46-04 | 順序非保証 | 要素の順序は保証されない（ハッシュテーブル実装） | 常時 |
| BR-46-05 | flatten深度制限 | ネスト深度はMAX_NESTED_DEPTH(16)まで | flatten操作時 |
| BR-46-06 | ハッシュ順序不変 | Setのhash値はXOR演算により要素順序に依存しない | hash計算時 |

### 計算ロジック

Set#hashの計算: XORベースの順序非依存ハッシュ。各要素のhash_codeにGOLDEN_RATIO_PRIMEを乗じてXOR。最終的にhash ^= hash >> 32で混合。

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

該当なし

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | RuntimeError | 未初期化のSetにアクセスした場合 | initializeを先に呼ぶ |
| - | RuntimeError | 初期化済みSetを再初期化した場合 | 一度だけ初期化する |
| - | ArgumentError | mergeに非enumerableを渡した場合 | eachを持つオブジェクトを渡す |
| - | ArgumentError | flattenでネスト深度が16を超えた場合 | 循環参照を避ける |
| - | ArgumentError | 比較メソッドに非Setを渡した場合 | Setオブジェクトを渡す |
| - | FrozenError | frozenなSetを変更しようとした場合 | dupして変更する |

### リトライ仕様

リトライは不要

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

該当なし

## パフォーマンス要件

- add/delete/include?: O(1)平均（ハッシュテーブル操作）
- 集合演算: O(n+m)（n,m=各集合のサイズ）
- flatten: O(n*d)（n=全要素数、d=ネスト深度）

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

khashのハッシュ計算でmrb_protect_errorを使用して例外安全性を確保している。ハッシュ関数の衝突攻撃に対する耐性はmrubyコアのハッシュ関数に依存する。

## 備考

- MRB_TT_SET独自のオブジェクト型を持つ
- MRB_USE_SETビルドフラグが必要（mrbgem.rakeで自動定義）
- RSet構造体にkhashテーブルを直接埋め込み（ポインタではなく実体）
- Enumerableモジュールをinclude
- eql?は==のエイリアスとして定義
- GCマーク・解放用の専用関数（mrb_gc_mark_set, mrb_gc_free_set）を提供

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | set.c | `mrbgems/mruby-set/src/set.c` | RSet構造体とkhashマクロ定義（20-101行目） |

**読解のコツ**: `KHASH_DECLARE`と`KHASH_DEFINE`マクロでkhash.hベースのハッシュテーブルをセットモード(FALSEパラメータ)で宣言・定義している。`kset_t`はkhashテーブルの型エイリアス。RSet構造体はMRB_OBJECT_HEADERにkset_tを直接埋め込む（ポインタではない）。

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | set.c | `mrbgems/mruby-set/src/set.c` | gem初期化（1513-1530行目） |

**主要処理フロー**:
1. **1518行目**: `mrb_define_class("Set", mrb->object_class)` - SetクラスをObject直下に定義
2. **1519行目**: `MRB_SET_INSTANCE_TT(set, MRB_TT_SET)` - インスタンス型をMRB_TT_SETに設定
3. **1521行目**: `mrb_include_module(mrb, set, Enumerable)` - Enumerableをinclude
4. **1523行目**: `Set[]`クラスメソッド登録
5. **1527行目**: `MRB_MT_INIT_ROM` - ROMテーブルによる大量メソッド一括登録

#### Step 3: 基本操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | set.c | `mrbgems/mruby-set/src/set.c` | add, delete, include?, size等 |

**主要処理フロー**:
- **199-208行目**: `set_init` - khashテーブル初期化（KSET_INITIAL_SIZE=4）
- **248-254行目**: `set_size` - kset_sizeで要素数取得
- **317-325行目**: `set_include_p` - kset_getでキー検索、kset_is_endで存在判定
- **334-344行目**: `set_add` - kset_putで追加、GCバリア設定
- **372-384行目**: `set_delete` - kset_getで検索、kset_delで削除

#### Step 4: 集合演算を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | set.c | `mrbgems/mruby-set/src/set.c` | union, intersection, difference, xor |
| 4-2 | set.rb | `mrbgems/mruby-set/mrblib/set.rb` | Rubyラッパー（Set以外のenumerable対応） |

**主要処理フロー**:
- **469-493行目**: `set_core_union` - selfをdup後otherをmerge
- **536-567行目**: `set_core_intersection` - 新Set作成、otherの要素がselfに含まれるものを追加
- **499-529行目**: `set_core_difference` - selfをdup後otherの要素を削除
- **574-630行目**: `set_core_xor` - 対称差：selfにあってotherにない + otherにあってselfにないを新Setに
- **mrblib/set.rb 93-99行目**: `intersection` - C実装を試行、失敗時はRubyフォールバック

#### Step 5: 比較演算とイテレーションを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | set.c | `mrbgems/mruby-set/src/set.c` | 比較演算メソッド群 |
| 5-2 | set.rb | `mrbgems/mruby-set/mrblib/set.rb` | each, delete_if等のイテレーション |

**主要処理フロー**:
- **731-767行目**: `set_superset_p` - otherの全要素がselfに含まれるか検証
- **823-858行目**: `set_subset_p` - selfの全要素がotherに含まれるか検証
- **975-1053行目**: `set_cmp` - サイズ比較後に包含関係を検証、-1/0/+1/nilを返す
- **mrblib/set.rb 176-181行目**: `each` - to_aでC側から配列取得してeach

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

```
mrb_mruby_set_gem_init
    |
    +-- mrb_define_class("Set")
    +-- MRB_SET_INSTANCE_TT(MRB_TT_SET)
    +-- mrb_include_module(Enumerable)
    +-- Set.[] (set_s_create)
    |       +-- mrb_obj_new + kset_put
    +-- インスタンスメソッド (ROMテーブル)
            +-- set_add / set_delete / set_include_p
            |       +-- kset_put / kset_del / kset_get
            +-- set_core_union / set_core_intersection / ...
            |       +-- kset_copy_merge / kset_put / kset_del
            +-- set_superset_p / set_subset_p / set_cmp
            |       +-- KSET_FOREACH + kset_get
            +-- set_flatten
                    +-- set_flatten_recursive
```

### データフロー図

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

Enumerable          --> Set.new(enum)                 --> Set{elements}
Set, element        --> set.add(element)              --> Set (self)
Set, Set            --> set & other                   --> new Set (intersection)
Set, Set            --> set | other                   --> new Set (union)
Set, Set            --> set - other                   --> new Set (difference)
Set                 --> set.to_a                      --> Array
Set                 --> set.each {|x| ...}            --> Set (self)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| set.c | `mrbgems/mruby-set/src/set.c` | ソース | コアメソッドのC実装・RSet構造体定義 |
| set.rb | `mrbgems/mruby-set/mrblib/set.rb` | ソース | 高レベルメソッドのRuby実装 |
| mrbgem.rake | `mrbgems/mruby-set/mrbgem.rake` | 設定 | gem定義・依存関係 |
| set.rb | `mrbgems/mruby-set/test/set.rb` | テスト | Setクラスのテスト |
