# 機能設計書 24-集合（Set）

## 概要

本ドキュメントは、Julia Base ライブラリが提供する集合（Set）機能の設計について記述する。集合は一意な要素のコレクションであり、高速なメンバーシップテストと集合演算（和・積・差・対称差）を提供する。

### 本機能の処理概要

集合機能は、`Set{T}` を中心に、`BitSet`（整数に特化したビットベース集合）、`IdSet{T}`（オブジェクトIDベースの集合）の各バリアントを提供する。Set{T} は内部的に `Dict{T,Nothing}` をラップして実装されており、Dict のハッシュテーブル機能を再利用している。集合演算として `union` / `intersect` / `setdiff` / `symdiff` と、それらの破壊的バージョン（`!` 付き）を提供する。

**業務上の目的・背景**：重複のないデータの管理、要素の存在判定、集合論的演算（和集合・積集合・差集合）は、データ処理やアルゴリズム実装における基本操作である。Set は isequal/hash ベースの等値判定を使用し、平均 O(1) のメンバーシップテストを提供する。BitSet はメモリ効率に優れた整数集合の実装を提供する。

**機能の利用シーン**：重複除去（unique関数の内部実装）、メンバーシップテスト（要素がコレクションに含まれるか）、集合演算によるデータのフィルタリング・比較、アルゴリズムにおける訪問済み要素の追跡で利用される。

**主要な処理内容**：
1. `Set{T}()` / `Set(itr)` による集合の作成
2. `push!` / `pop!` / `delete!` による要素の追加・削除
3. `in` / `in!` によるメンバーシップテスト
4. `union` / `union!` による和集合
5. `intersect` / `intersect!` による積集合
6. `setdiff` / `setdiff!` による差集合
7. `symdiff` / `symdiff!` による対称差
8. `unique` / `unique!` / `allunique` / `allequal` による一意性関連関数
9. `BitSet` によるメモリ効率の良い整数集合操作
10. `issubset` / `issetequal` による集合関係判定

**関連システム・外部連携**：なし。Base モジュール内で完結する。

**権限による制御**：なし。すべてのユーザーが利用可能である。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 9 | MultiSelectMenu（複数選択メニュー） | 補助機能 | Set{Int}による選択済みアイテムの管理。Enterでトグル、a=全選択、n=全解除 |

## 機能種別

CRUD操作（要素の作成・読取・削除） / 計算処理（集合演算）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| T | Type | No | 要素の型 | 任意の型（hashable） |
| x | T | Yes（操作時） | 操作対象の要素 | isequal/hash が定義されていること |
| itr | Iterable | No | 初期要素のイテラブル | iterateプロトコルを実装 |

### 入力データソース

Julia プログラム内のリテラル、コレクション、イテラブルオブジェクト。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | Bool | in / issubset 等の判定結果 |
| set | Set{T} | 集合演算の結果 |
| array | Vector{T} | unique の結果（順序付き配列） |

### 出力先

呼び出し元への戻り値。

## 処理フロー

### 処理シーケンス

```
1. Set{T}(itr) 作成
   └─ union!(Set{T}(), itr) を呼び出し
   └─ 各要素を push! で追加（Dict{T,Nothing} へ委譲）
2. in(x, s::Set)
   └─ haskey(s.dict, x) へ委譲
   └─ Dict の ht_keyindex で O(1) 検索
3. union(s1, s2)
   └─ copymutable(s1) でコピー
   └─ union!(copy, s2) で要素追加
4. intersect(s1, s2)
   └─ 小さい方の集合を走査
   └─ in チェックで共通要素を抽出
5. setdiff!(s, t)
   └─ サイズ比較で走査戦略を選択
   └─ 2*|s| < |t| の場合: s を走査して t に含まれるものを削除
   └─ それ以外: t を走査して s から削除
6. unique(itr)
   └─ Set を使った重複検出
   └─ in! で追加と判定を一度に実行
```

### フローチャート

```mermaid
flowchart TD
    A[Set 操作] --> B{操作種別}
    B -->|in/push!/delete!| C[Dict 操作に委譲]
    B -->|union| D[copymutable + union!]
    B -->|intersect| E{サイズ比較}
    B -->|setdiff!| F{2*len_s < len_t?}
    B -->|unique| G[Set + in! で重複検出]
    C --> H[ht_keyindex / _setindex!]
    D --> I[push! ループ]
    E -->|s < t| J[sを走査、tでin判定]
    E -->|s >= t| K[tを走査、sでin判定]
    F -->|Yes| L[sを走査、tに含まれるなら削除]
    F -->|No| M[tを走査、sから削除]
    G --> N[Vector に push! + in! 判定]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 一意性保証 | 同じ要素（isequal判定）は集合内に1つだけ存在 | 常時 |
| BR-02 | 順序非保証 | Set 内の要素の順序は実装依存で保証されない | 常時 |
| BR-03 | Dict委譲 | Set{T} は内部的に Dict{T,Nothing} として実装 | 常時 |
| BR-04 | setdiff最適化 | サイズ比率0.5を閾値として走査戦略を切り替え | setdiff! 時 |
| BR-05 | unique保持順序 | unique は最初の出現順序を保持する | unique 呼び出し時 |

### 計算ロジック

- `in(x, s::Set)` = `haskey(s.dict, x)` - Dict の O(1) ルックアップに委譲
- `in!(x, s::Set)` - 要素追加と存在判定を1回のハッシュ検索で実行
- `setdiff!` の走査戦略: `2 * length(s) < length(t)` で切り替え

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

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

該当なし（インメモリデータ構造）。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | KeyError | pop!(s, x) で存在しない要素を指定 | in で事前確認するか pop!(s, x, default) を使用 |
| - | ArgumentError | pop!(s) で空集合 | isempty で事前確認 |

### リトライ仕様

リトライは不要。

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

Set はスレッドセーフではない。並行アクセス時は外部での排他制御が必要。

## パフォーマンス要件

- 平均 O(1) のメンバーシップテスト・挿入・削除（Dict に委譲）
- BitSet は整数に特化し、ビット演算により高速な集合演算を実現
- unique は in! を使用して追加と判定を1回のハッシュ検索で実行

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

特になし。

## 備考

- `BitSet` は `Vector{UInt64}` のビット列として整数を格納し、密な整数集合に最適
- `IdSet{T}` は IdDict を内部に使用し、objectid/=== による等値判定を行う
- `in!` は Julia 1.11 で追加された関数
- `unique(f, itr)` は関数 f の結果に基づく一意性判定をサポート

---

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

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

### 推奨読解順序

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

Set の内部構造（Dict ラッパー）と BitSet のビット列構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | set.jl | `base/set.jl` | Set{T} 構造体 - Dict{T,Nothing} をラップ |
| 1-2 | bitset.jl | `base/bitset.jl` | BitSet 構造体 - Vector{UInt64} とオフセットによるビット配列 |

**読解のコツ**: Set{T} は Dict{T,Nothing} の薄いラッパーなので、Dict の理解が前提となる。BitSet は 64ビット整数のベクトルとオフセットでビット位置を管理する。`NO_OFFSET` の特殊値に注意。

- **set.jl 39-43行目**: `Set{T}` 構造体定義 - `dict::Dict{T,Nothing}` フィールド
- **set.jl 45-48行目**: コンストラクタ群
- **bitset.jl 3-5行目**: `Bits` 型エイリアスと定数
- **bitset.jl 13-23行目**: `BitSet` 構造体定義 - `bits::Vector{UInt64}` と `offset::Int`

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | set.jl | `base/set.jl` | in, push!, pop!, delete! などの基本操作 |

**主要処理フロー**:
1. **90-92行目**: `isempty`, `length`, `in` - Dict に委譲
2. **125-135行目**: `in!` - 追加と判定を1回のハッシュ検索で実行
3. **137行目**: `push!` - Dict の setindex! に委譲
4. **139-157行目**: `pop!` - Dict のキー検索と削除
5. **164行目**: `delete!` - Dict の delete! に委譲

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | set.jl | `base/set.jl` | setdiff!, unique, unique!, allunique 等の集合演算 |

**主要処理フロー**:
- **187-198行目**: `setdiff!` - サイズ比較による走査戦略の切り替え
- **224-241行目**: `unique(itr)` - Set を使った重複検出
- **301-321行目**: `unique(f, C)` - 関数適用による一意性判定

#### Step 4: BitSet を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | bitset.jl | `base/bitset.jl` | BitSet のビット操作と集合演算 |

**主要処理フロー**:
- **63-68行目**: `_bits_getindex` - ビット位置の取得
- **70-76行目**: `_bits_findnext` - 次のセットビットの検索

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

```
Set{T}(itr) / Set(itr)
    |
    +-- push!(s, x)
    |       +-- s.dict[x] = nothing (Dict.setindex! に委譲)
    |
    +-- in(x, s)
    |       +-- haskey(s.dict, x) (Dict.ht_keyindex に委譲)
    |
    +-- in!(x, s)
    |       +-- ht_keyindex2_shorthash!(s.dict, xT)
    |       +-- _setindex!(s.dict, nothing, xT, -idx, sh)
    |
    +-- union(s1, s2)
    |       +-- copymutable(s1)
    |       +-- union!(copy, s2) → push! ループ
    |
    +-- setdiff!(s, t)
    |       +-- [2*|s|<|t|] s走査 + in(x, t) + delete!(s, x)
    |       +-- [else] t走査 + delete!(s, x)
    |
    +-- unique(itr)
            +-- Set{T}() 作成
            +-- in!(x, seen) で重複検出
            +-- push!(out, x) で結果配列に追加
```

### データフロー図

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

itr (iterable)   ---->  Set{T}(itr)
                        +-- union!(Set{T}(), itr)
                        +-- push!(s, x) for x in itr     ---->  Set{T}

s1, s2 (Set)     ---->  union(s1, s2)
                        +-- copymutable + union!           ---->  Set{T} (和集合)

itr (iterable)   ---->  unique(itr)
                        +-- Set{T}() + in! + push!         ---->  Vector{T} (順序保持)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| set.jl | `base/set.jl` | ソース | Set{T} の実装と集合演算（union, intersect, setdiff, unique等） |
| bitset.jl | `base/bitset.jl` | ソース | BitSet のビット配列ベース整数集合実装 |
| idset.jl | `base/idset.jl` | ソース | IdSet{T} のオブジェクトIDベース集合実装 |
| dict.jl | `base/dict.jl` | ソース | Dict{K,V} - Set の内部実装基盤 |
| abstractset.jl | `base/abstractset.jl` | ソース | AbstractSet の抽象インタフェース定義 |
