# 機能設計書 45-critbits

## 概要

本ドキュメントは、Nim標準ライブラリの`critbits`モジュールの機能設計について記述する。`critbits`は、Crit-bit木（Critical Bit Tree）を実装し、文字列のソート済みセットまたは文字列をキーとするソート済みマッピングを効率的に扱えるデータ構造を提供する。

### 本機能の処理概要

**業務上の目的・背景**：Crit-bit木は、基数木（Radix Tree）またはパトリシアトライ（Patricia Trie）の一種であり、文字列キーの効率的な格納と検索を実現する。ハッシュテーブルとは異なり、キーが辞書順でソートされた状態で保持され、プレフィックス検索や範囲検索が効率的に行える。Adam Langleyの論文に基づく実装。

**機能の利用シーン**：
- 辞書順ソート済みのキー集合管理：文字列キーをソートされた状態で保持
- プレフィックス検索：特定のプレフィックスで始まるキーの列挙
- オートコンプリート機能：入力中の文字列に一致する候補の提示
- 文字列のユニーク化：重複を排除した文字列セットの構築
- 文字列→値のマッピング：辞書順でソートされたキーバリューストア

**主要な処理内容**：
1. セット操作（incl, excl, contains）：文字列の追加・削除・存在確認
2. マッピング操作（[]=, []）：キーバリューの設定・取得
3. イテレーション（keys, values, pairs）：辞書順での全要素走査
4. プレフィックス操作（keysWithPrefix, valuesWithPrefix, pairsWithPrefix）：プレフィックスマッチする要素の走査
5. ユーティリティ（len, hasKey, commonPrefixLen）：長さ取得、キー存在確認、共通プレフィックス長
6. 変換（toCritBitTree）：配列からCritBitTreeへの変換
7. 条件付き操作（containsOrIncl, missingOrExcl）：条件付きの追加・削除

**関連システム・外部連携**：本モジュールは純粋なデータ構造ライブラリであり、外部システムとの直接連携はない。

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

## 関連画面

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

## 機能種別

データ構造ライブラリ / コレクション操作 / 文字列トライ木

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| key | string | Yes | 操作対象のキー | - |
| val | T | Yes（マッピング時） | キーに対応する値 | - |
| prefix | string | Yes（プレフィックス検索時） | 検索プレフィックス | - |
| pairs | openArray[(string, T)] | Yes（変換時） | 変換元のキーバリューペア | - |
| items | openArray[string] | Yes（変換時） | 変換元の文字列配列 | - |

### 入力データソース

- プログラム内で生成されたCritBitTreeインスタンス
- openArray（toCritBitTree使用時）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | CritBitTree[T] | 新規作成または変更されたCritBitTree |
| result | T | キーに対応する値（[]） |
| result | bool | 存在確認結果（contains, hasKey, containsOrIncl, missingOrExcl） |
| result | int | 要素数（len）、共通プレフィックス長（commonPrefixLen） |
| result | string | 文字列表現（$） |

### 出力先

呼び出し元プログラムへの戻り値として返却

## 処理フロー

### 処理シーケンス

```
1. 要素検索（rawGet）
   └─ rootからleafまで走査
   └─ 各ノードでbyteインデックスとotherBitsを使用して方向を決定

2. 要素挿入（rawInsert）
   └─ 既存キーとの差分バイト位置を特定
   └─ 新しい内部ノードを作成し、適切な位置に挿入

3. 要素削除（exclImpl）
   └─ leafまで走査しながら親ノードを記録
   └─ leaf削除後、親の兄弟を昇格

4. プレフィックス検索（allprefixedAux）
   └─ プレフィックスに一致するサブツリーを特定
   └─ そのサブツリー内の全leafを走査
```

### フローチャート

```mermaid
flowchart TD
    A[CritBitTree操作] --> B{操作種別}
    B -->|検索| C[rawGet: ビット比較で走査]
    B -->|挿入| D[rawInsert: 差分位置特定]
    B -->|削除| E[exclImpl: 親追跡+削除]
    B -->|プレフィックス| F[allprefixedAux: サブツリー特定]
    C --> G[leaf到達: キー比較]
    D --> H[内部ノード作成: 適切な位置に挿入]
    E --> I[兄弟ノードを親に昇格]
    F --> J[leaves走査: 該当要素をyield]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 辞書順保証 | keys/items/pairsは辞書順でソートされた順序で返却 | 常時 |
| BR-02 | void型セット | T=voidの場合、値なしのセットとして動作 | CritBitTree[void] |
| BR-03 | KeyError | 存在しないキーへの[]アクセスでKeyErrorを発生 | []アクセス時 |
| BR-04 | 空文字列対応 | 空文字列("")もキーとして使用可能 | 常時 |
| BR-05 | 重複キー | 同一キーの重複挿入は上書きとなる | incl/[]= |

### 計算ロジック

- **方向決定**: `dir = (1 + (ch.ord or otherBits.ord)) shr 8`
- **差分ビット計算**: XOR演算で異なるバイトを特定し、最上位ビットを抽出
- **commonPrefixLen**: root.byteが最長共通プレフィックス長（単一要素時はキー長）

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

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| KeyError | キーエラー | 存在しないキーへの[]アクセス | hasKeyで事前確認、またはtry-except |

### リトライ仕様

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

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

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

## パフォーマンス要件

- **contains/hasKey**: O(k)の時間計算量（k=キー長）
- **incl/excl**: O(k)の時間計算量
- **keysWithPrefix**: O(k + m)の時間計算量（m=結果数）
- **len**: O(1)の時間計算量
- **commonPrefixLen**: O(1)の時間計算量
- **空間計算量**: O(n * k)（n=要素数、k=平均キー長）

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

- 本モジュールはメモリ安全性を保証
- ノードはrefオブジェクトとしてGCにより管理される
- `{.acyclic.}`プラグマにより循環参照がないことを示唆

## 備考

- Nim 1.3以降で追加された機能（toCritBitTree, commonPrefixLen等）には`since`プラグマが付与
- Adam Langleyの論文に基づく実装: https://www.imperialviolet.org/binary/critbit.pdf
- CritBitTree[void]はセットとして、CritBitTree[T]はマッピングとして使用

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | critbits.nim | `lib/pure/collections/critbits.nim` | 42-59行目: NodeObj型とCritBitTree型 |

**読解のコツ**:
- **43-51行目**: `NodeObj[T]` - byte（差分バイト位置）、otherBits（マスク）、isLeaf判別式、child配列またはkey/val
- **53行目**: `Node[T] = ref NodeObj[T]` - 参照型
- **54-59行目**: `CritBitTree[T]` - root（ルートノード）、count（要素数）

**注意点**:
- `{.acyclic.}`プラグマはノードに循環参照がないことを示す
- `T isnot void`でセット/マッピングの分岐

#### Step 2: 検索操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | critbits.nim | `lib/pure/collections/critbits.nim` | 69-78行目: rawGet関数 |
| 2-2 | critbits.nim | `lib/pure/collections/critbits.nim` | 80-91行目: contains/hasKey関数 |

**主要処理フロー**:
- **69-78行目**: rawGet - rootからleafまで走査、`(1 + (ch.ord or otherBits.ord)) shr 8`で方向決定
- **74-76行目**: byte位置の文字を取得し、方向を計算してchild[dir]へ移動
- **78行目**: leafでキー一致確認、一致すればノードを返却、不一致ならnil

#### Step 3: 挿入操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | critbits.nim | `lib/pure/collections/critbits.nim` | 93-141行目: rawInsert関数 |

**主要処理フロー**:
- **94-96行目**: 空ツリーの場合、rootに新ノードを直接設定
- **98-102行目**: leafまで走査
- **104-119行目**: 既存キーとの差分バイト位置（newByte）と差分ビット（newOtherBits）を計算
- **123-140行目**: 新しい内部ノード（inner）を作成し、適切な位置に挿入

**注意点**:
- **117行目**: newOtherBitsの最上位ビット以外を0にする処理
- **119行目**: 255とのXORでマスクを反転

#### Step 4: 削除操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | critbits.nim | `lib/pure/collections/critbits.nim` | 143-165行目: exclImpl関数 |
| 4-2 | critbits.nim | `lib/pure/collections/critbits.nim` | 167-180行目: excl関数 |

**主要処理フロー**:
- **143-156行目**: leafまで走査しながら、wherep（現在位置）とwhereq/q（親位置）を追跡
- **157-163行目**: キー一致時に削除処理、whereqがnilならroot=nil、そうでなければ兄弟を親に昇格

#### Step 5: incl/[]=操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | critbits.nim | `lib/pure/collections/critbits.nim` | 264-275行目: incl (void) |
| 5-2 | critbits.nim | `lib/pure/collections/critbits.nim` | 277-289行目: incl (T) |
| 5-3 | critbits.nim | `lib/pure/collections/critbits.nim` | 291-298行目: []= |

**主要処理フロー**:
- **264-275行目**: `incl(void)` - rawInsertを呼び出すだけ（値なし）
- **277-289行目**: `incl(T)` - rawInsert後にn.val = val
- **291-298行目**: `[]=` - inclのエイリアス

#### Step 6: []アクセスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | critbits.nim | `lib/pure/collections/critbits.nim` | 300-324行目: get/[]関数 |

**主要処理フロー**:
- **300-305行目**: getテンプレート - rawGetで検索、nilならKeyErrorを発生
- **307-315行目**: `[]` (lent T) - getを呼び出して不変参照を返却
- **317-324行目**: `[]` (var T) - getを呼び出して可変参照を返却

#### Step 7: イテレーションを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 7-1 | critbits.nim | `lib/pure/collections/critbits.nim` | 326-337行目: leavesイテレータ |
| 7-2 | critbits.nim | `lib/pure/collections/critbits.nim` | 339-395行目: keys/values/items/pairs |

**主要処理フロー**:
- **326-337行目**: leaves - スタックベースの深さ優先走査、左優先（辞書順保証）
- **339-347行目**: keys - leavesを呼び出してx.keyをyield
- **349-361行目**: values - leavesを呼び出してx.valをyield
- **375-387行目**: pairs - leavesを呼び出して(x.key, x.val)をyield

#### Step 8: プレフィックス検索を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 8-1 | critbits.nim | `lib/pure/collections/critbits.nim` | 397-410行目: allprefixedAux |
| 8-2 | critbits.nim | `lib/pure/collections/critbits.nim` | 412-475行目: *WithPrefixイテレータ群 |

**主要処理フロー**:
- **397-410行目**: allprefixedAux - プレフィックスに一致するサブツリーのルートを返却
- **402-407行目**: prefixのバイト位置まで走査し、サブツリーのトップを記録
- **408-409行目**: prefix全体がキーに含まれているか確認

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

```
critbits.nim (ユーザーコード)
    │
    ├─ 検索操作
    │   ├─ contains(key) → rawGet(key) → ノードまたはnil
    │   ├─ hasKey(key) → rawGet(key) → bool
    │   └─ [](key) → get() → rawGet() → KeyError or T
    │
    ├─ 挿入操作
    │   ├─ incl(key) → rawInsert(key) → 新ノード作成
    │   ├─ incl(key, val) → rawInsert(key) → n.val = val
    │   └─ []=(key, val) → incl(key, val)
    │
    ├─ 削除操作
    │   ├─ excl(key) → exclImpl(key)
    │   └─ missingOrExcl(key) → exclImpl(key) → bool
    │
    ├─ イテレーション
    │   ├─ keys() → leaves(root) → yield x.key
    │   ├─ values() → leaves(root) → yield x.val
    │   ├─ items() → leaves(root) → yield x.key
    │   └─ pairs() → leaves(root) → yield (x.key, x.val)
    │
    └─ プレフィックス検索
        ├─ keysWithPrefix(prefix) → allprefixedAux → leaves
        ├─ valuesWithPrefix(prefix) → allprefixedAux → leaves
        └─ pairsWithPrefix(prefix) → allprefixedAux → leaves
```

### データフロー図

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

openArray[string] ──────▶ toCritBitTree ───────────────▶ CritBitTree[void]

openArray[(string, T)] ──▶ toCritBitTree ───────────────▶ CritBitTree[T]

                    ┌─────────────────────────────┐
                    │  CritBitTree[T]             │
                    │  ┌───────────────────────┐  │
                    │  │ root: Node[T]         │  │
                    │  │   ┌─────────────┐     │  │
string (key) ───────│──│──▶│ byte, bits │     │──│─▶ bool (contains)
                    │  │   │ child[0/1] │     │  │
                    │  │   └─────────────┘     │  │
                    │  │         │             │  │
                    │  │    ┌────▼────┐        │  │─▶ T (value)
                    │  │    │  leaf   │        │  │
                    │  │    │ key,val │        │  │
                    │  │    └─────────┘        │  │
                    │  │ count: int            │  │─▶ int (len)
                    │  └───────────────────────┘  │
                    └─────────────────────────────┘

プレフィックス検索:
    prefix ───▶ allprefixedAux ───▶ サブツリールート ───▶ leaves ───▶ keys/values
```

### 関連ファイル一覧

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