# 機能設計書 40-sets

## 概要

本ドキュメントは、Nimプログラミング言語の汎用ハッシュセットモジュールである`sets`モジュールの機能設計を記載する。setsモジュールは効率的なハッシュセット（HashSet）と順序付きハッシュセット（OrderedSet）を提供する。

### 本機能の処理概要

setsモジュールはハッシュ可能な任意の型の要素を格納できるセット（集合）データ構造を提供する。通常のHashSetと挿入順序を保持するOrderedSetの2種類がある。

**業務上の目的・背景**：セット（集合）は重複のない要素の集まりを表現する基本的なデータ構造である。メンバーシップテスト（要素の存在確認）が高速で、数学的な集合演算（和・積・差）を効率的に実行できる。

**機能の利用シーン**：
- 重複の除去（配列やシーケンスから重複を排除）
- メンバーシップテスト（要素の存在確認）
- 数学的な集合演算（union, intersection, difference, symmetric difference）
- ユニークなIDの管理
- 訪問済みノードの追跡（グラフ探索等）

**主要な処理内容**：
1. HashSet[A]型（通常のハッシュセット）
2. OrderedSet[A]型（挿入順序を保持）
3. セット作成（initHashSet, toHashSet, initOrderedSet, toOrderedSet）
4. 要素操作（incl, excl, contains, containsOrIncl, missingOrExcl）
5. 集合演算（union/+, intersection/*, difference/-, symmetricDifference/-+-）
6. 比較演算（==, <, <=, disjoint）
7. イテレータ（items, pairs）

**関連システム・外部連携**：hashesモジュールのHash型とhash関数を使用。

**権限による制御**：権限による制御は存在しない。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面には関連しない（ライブラリモジュール） |

## 機能種別

データ構造 / ハッシュセット / コレクション

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| A | type | Yes | 要素の型（hash関数が必要） | ハッシュ可能 |
| key | A | Yes | 要素 | なし |
| initialSize | int | No | 初期サイズ（デフォルト64） | 正の整数 |

### 入力データソース

プログラム内のデータ。要素型にはhash関数と==演算子が必要。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| HashSet[A] | object | ハッシュセット |
| OrderedSet[A] | object | 順序付きハッシュセット |
| exists | bool | 要素の存在確認結果 |
| count | int | 要素数 |

### 出力先

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

## 処理フロー

### 処理シーケンス

```
1. セットの作成
   └─ initHashSet/toHashSet/initOrderedSet/toOrderedSetで初期化
2. ハッシュ計算
   └─ 要素のhash関数を呼び出し
3. スロット検索
   └─ 開放アドレス法（線形探査）
4. 操作実行
   └─ 挿入（incl）、検索（contains）、削除（excl）
5. リハッシュ（必要時）
   └─ 負荷率に応じてテーブル拡張
```

### フローチャート

```mermaid
flowchart TD
    A[操作要求] --> B{操作種別}
    B -->|挿入| C[hash計算]
    B -->|検索| D[rawGet呼び出し]
    B -->|削除| E[excl呼び出し]
    C --> F[スロット検索]
    F --> G{空きスロット?}
    G -->|Yes| H[要素を挿入]
    G -->|No| I[次のスロットへ]
    I --> G
    H --> J{リハッシュ必要?}
    J -->|Yes| K[テーブル拡張]
    J -->|No| L[完了]
    K --> L
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 値セマンティクス | =演算子はセットをコピー | HashSet, OrderedSet |
| BR-02 | 重複なし | 同じ要素は1回のみ格納 | すべてのセット |
| BR-03 | ハッシュ要件 | 要素型にはhash関数と==演算子が必要 | すべてのセット |
| BR-04 | 初期化不要 | Nim v0.20以降はデフォルトで初期化済み | initHashSet/initOrderedSet |
| BR-05 | 順序保持 | OrderedSetは挿入順序を保持 | OrderedSetのみ |

### 計算ロジック

集合演算の定義:
- **union（和集合）**: A ∪ B = AまたはBに含まれる全要素
- **intersection（積集合）**: A ∩ B = AとBの両方に含まれる要素
- **difference（差集合）**: A ∖ B = Aに含まれBに含まれない要素
- **symmetricDifference（対称差）**: A △ B = AまたはBのどちらか一方のみに含まれる要素

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

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

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | データベース操作なし |

### テーブル別操作詳細

データベース操作は行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------| ---------|
| KeyError | Exception | []で存在しない要素へのアクセス | containsでチェック |
| KeyError | Exception | popで空のセットから取得 | lenでチェック |

### リトライ仕様

リトライは不要。事前チェックで対処。

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

トランザクション管理は不要。

## パフォーマンス要件

- contains、incl、excl（HashSet）: 平均O(1)
- excl（OrderedSet）: O(n)
- 集合演算: O(n)（要素数に比例）
- リハッシュ: O(n)（負荷率に応じて発生）
- OrderedSetの挿入順序イテレーション: O(n)

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

- ハッシュ衝突攻撃に対する耐性は標準的なレベル
- ユーザー入力を要素として大量に挿入する場合は注意が必要

## 備考

整数専用の効率的なセットが必要な場合はintsets モジュールの使用も検討すること。組み込みのset型（範囲が限定された列挙型や小さな整数用）とは異なり、HashSetは任意のハッシュ可能な型を格納できる。

---

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

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

### 推奨読解順序

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

HashSet型とOrderedSet型の定義を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | sets.nim | `lib/pure/collections/sets.nim` | KeyValuePair, HashSet型（63-72行目） |
| 1-2 | sets.nim | `lib/pure/collections/sets.nim` | OrderedKeyValuePair, OrderedSet型（74-86行目） |

**読解のコツ**: HashSet[A]はdata（KeyValuePairSeq）とcounter（要素数）を持つ。KeyValuePairはhcode（ハッシュコード）とkeyのタプル。OrderedSetは追加でfirst、last、nextを持ち、挿入順序を連結リストで保持する。

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

モジュール冒頭のドキュメントを確認。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | sets.nim | `lib/pure/collections/sets.nim` | モジュールドキュメント（10-49行目） |

**主要処理フロー**:
1. **10-11行目**: HashSetとOrderedSetの概要
2. **13-15行目**: 組み込みset型との違い
3. **17-26行目**: 主な用途（重複除去、メンバーシップテスト、集合演算）
4. **44-45行目**: 値セマンティクスの説明

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | sets.nim | `lib/pure/collections/sets.nim` | initHashSet, toHashSet（117-246行目） |
| 3-2 | sets.nim | `lib/pure/collections/sets.nim` | contains, incl, excl（151-328行目） |
| 3-3 | sets.nim | `lib/pure/collections/sets.nim` | len, card（172-191行目） |

**主要処理フロー**:
- **117-134行目**: initHashSet - 空のセットを作成
- **228-246行目**: toHashSet - 配列からセットを作成
- **151-170行目**: contains - 要素の存在確認
- **193-208行目**: incl - 要素の追加
- **294-309行目**: excl - 要素の削除

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | sets.nim | `lib/pure/collections/sets.nim` | union（390-410行目） |
| 4-2 | sets.nim | `lib/pure/collections/sets.nim` | intersection（412-440行目） |
| 4-3 | sets.nim | `lib/pure/collections/sets.nim` | difference（443-465行目） |
| 4-4 | sets.nim | `lib/pure/collections/sets.nim` | symmetricDifference（467-489行目） |

**主要処理フロー**:
- **390-410行目**: union - 和集合（+演算子）
- **412-440行目**: intersection - 積集合（*演算子）
- **443-465行目**: difference - 差集合（-演算子）
- **467-489行目**: symmetricDifference - 対称差（-+-演算子）

#### Step 5: 比較演算を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | sets.nim | `lib/pure/collections/sets.nim` | disjoint（508-519行目） |
| 5-2 | sets.nim | `lib/pure/collections/sets.nim` | <, <=, ==（521-565行目） |

**主要処理フロー**:
- **508-519行目**: disjoint - 素な集合かを判定
- **521-534行目**: < - 真部分集合かを判定
- **536-555行目**: <= - 部分集合かを判定
- **557-565行目**: == - 等しいかを判定

#### Step 6: OrderedSetを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | sets.nim | `lib/pure/collections/sets.nim` | initOrderedSet, toOrderedSet（657-694行目） |
| 6-2 | sets.nim | `lib/pure/collections/sets.nim` | OrderedSet固有の動作（846-868行目） |

**主要処理フロー**:
- **657-674行目**: initOrderedSet - 空の順序付きセットを作成
- **676-694行目**: toOrderedSet - 配列から順序付きセットを作成
- **846-868行目**: == - 順序も含めた等価性判定
- **894-916行目**: items イテレータ - 挿入順序でイテレート

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

```
sets.nim (メインモジュール)
    │
    ├─ HashSet[A]
    │      ├─ initHashSet / toHashSet
    │      ├─ incl / excl
    │      ├─ contains / containsOrIncl / missingOrExcl
    │      ├─ len / card / pop / clear
    │      ├─ items (イテレータ)
    │      └─ map / hash / $
    │
    ├─ 集合演算
    │      ├─ union / + (和集合)
    │      ├─ intersection / * (積集合)
    │      ├─ difference / - (差集合)
    │      └─ symmetricDifference / -+- (対称差)
    │
    ├─ 比較演算
    │      ├─ == (等価)
    │      ├─ < (真部分集合)
    │      ├─ <= (部分集合)
    │      └─ disjoint (素)
    │
    ├─ OrderedSet[A]
    │      ├─ initOrderedSet / toOrderedSet
    │      ├─ incl / excl / containsOrIncl / missingOrExcl
    │      ├─ len / card / clear
    │      ├─ items / pairs (イテレータ、挿入順序)
    │      └─ hash / $
    │
    └─ include setimpl
           └─ rawGet / rawInsert / inclImpl 等
```

### データフロー図

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

[9, 5, 1]          ───▶  toHashSet            ───▶  HashSet[int] {9, 5, 1}
                         (セット構築)

s.incl(3)          ───▶  incl                 ───▶  セット更新
                         (hash→検索→挿入)

3 in s             ───▶  contains             ───▶  true
                         (hash→検索)

s1 + s2            ───▶  union                ───▶  和集合
                         (要素結合)

s1 * s2            ───▶  intersection         ───▶  積集合
                         (共通要素抽出)

s1 - s2            ───▶  difference           ───▶  差集合
                         (差分抽出)

s1 -+- s2          ───▶  symmetricDifference  ───▶  対称差
                         (排他的要素抽出)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| sets.nim | `lib/pure/collections/sets.nim` | ソース | メインモジュール、HashSet型、OrderedSet型、集合演算 |
| setimpl.nim | `lib/pure/collections/setimpl.nim` | インクルード | rawGet, rawInsert等の実装 |
| hashes.nim | `lib/pure/hashes.nim` | ソース | Hash型、hash関数 |
| math.nim | `lib/pure/math.nim` | ソース | 数学関数（セットサイズ計算） |
| intsets.nim | `lib/pure/collections/intsets.nim` | ソース | 整数専用の効率的なセット |
