# 機能設計書 42-deques

## 概要

本ドキュメントは、Nim標準ライブラリの`deques`モジュールの機能設計について記述する。`deques`は、両端キュー（double-ended queue）のデータ構造を提供するモジュールであり、先頭と末尾の両方から効率的に要素の追加・削除が可能である。

### 本機能の処理概要

**業務上の目的・背景**：両端キュー（Deque）は、スタック（LIFO）とキュー（FIFO）の両方の機能を併せ持つ汎用的なデータ構造である。スライディングウィンドウアルゴリズム、BFS（幅優先探索）、タスクスケジューリング、undo/redo機能の実装など、多様なユースケースで活用される。`seq`を基盤とするリングバッファ実装により、メモリ効率と操作効率を両立している。

**機能の利用シーン**：
- キュー/スタック操作：FIFO・LIFO両方の操作が必要な場面
- スライディングウィンドウ：固定サイズのウィンドウを移動しながらデータ処理
- BFS（幅優先探索）：グラフ・木構造の探索アルゴリズム
- undo/redo実装：操作履歴の両端からのアクセス
- バッファ管理：固定容量のリングバッファとして使用

**主要な処理内容**：
1. 初期化処理（initDeque, toDeque）：空のDequeの作成、配列からの変換
2. 先頭操作（addFirst, peekFirst, popFirst）：先頭への追加、先頭要素の参照・削除
3. 末尾操作（addLast, peekLast, popLast）：末尾への追加、末尾要素の参照・削除
4. インデックスアクセス（[], []=）：任意位置の要素への読み書きアクセス
5. イテレーション（items, mitems, pairs）：全要素の走査
6. サイズ管理（len, clear, shrink）：長さ取得、クリア、縮小
7. ユーティリティ（contains, ==, hash, $）：検索、比較、ハッシュ、文字列化

**関連システム・外部連携**：本モジュールは純粋なデータ構造ライブラリであり、外部システムとの直接連携はない。`std/lists`モジュールの連結リストとは相補的な関係にある。

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

## 関連画面

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

## 機能種別

データ構造ライブラリ / コレクション操作 / 両端キュー

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| initialSize | int | No | 初期容量（デフォルト: 4） | 2のべき乗に切り上げ |
| item | T | Yes（追加時） | 追加する要素 | - |
| i | Natural / BackwardsIndex | Yes（アクセス時） | アクセス位置 | 境界チェック |
| fromFirst, fromLast | int | No（shrink時） | 削除する要素数 | 非負整数 |

### 入力データソース

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

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | Deque[T] | 新規作成または変更されたDeque |
| result | T | 要素の参照（peek系、pop系、[]） |
| result | int | 要素数（len） |
| result | bool | 検索結果（contains）、比較結果（==） |
| result | Hash | ハッシュ値（hash） |
| result | string | 文字列表現（$） |

### 出力先

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

## 処理フロー

### 処理シーケンス

```
1. Deque初期化
   └─ initDeque: 指定サイズ（2のべき乗に切り上げ）でseqを確保
   └─ toDeque: openArrayから要素をコピーして初期化

2. 要素追加（容量チェック付き）
   └─ expandIfNeeded: 容量不足時に2倍に拡張
   └─ addFirst: headをデクリメントして先頭に追加
   └─ addLast: 末尾に追加してtailをインクリメント

3. 要素参照
   └─ peekFirst/peekLast: 削除せずに先頭/末尾を参照
   └─ []: 任意インデックスの要素を参照

4. 要素削除
   └─ popFirst: 先頭要素を削除して返却
   └─ popLast: 末尾要素を削除して返却
   └─ shrink: 先頭/末尾から指定数の要素を削除
   └─ clear: 全要素を削除
```

### フローチャート

```mermaid
flowchart TD
    A[Deque操作] --> B{操作種別}
    B -->|初期化| C[initDeque/toDeque]
    B -->|追加| D{容量チェック}
    B -->|参照| E[peek/インデックスアクセス]
    B -->|削除| F[pop/shrink/clear]
    D -->|不足| G[expandIfNeeded: 容量2倍に拡張]
    D -->|十分| H[要素追加]
    G --> H
    C --> I[Deque使用可能]
    H --> I
    E --> J[要素返却]
    F --> K[要素削除・返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 空Deque禁止操作 | 空Dequeに対するpeek/pop操作はIndexDefectを発生 | boundChecks有効時 |
| BR-02 | 自動拡張 | 容量不足時は自動的に2倍に拡張 | 要素追加時 |
| BR-03 | 2のべき乗容量 | 内部バッファは常に2のべき乗サイズ | 初期化・拡張時 |
| BR-04 | リングバッファ | head/tailはマスク演算で循環アクセス | 常時 |
| BR-05 | イテレーション中の変更禁止 | イテレーション中にDequeの長さを変更するとassertエラー | items/mitems/pairs使用時 |

### 計算ロジック

- **インデックス計算**: `(head + i) and mask` でリングバッファ内の実際の位置を算出
- **マスク計算**: `mask = data.len - 1`（2のべき乗前提でビット演算による高速化）
- **長さ計算**: `len = tail - head`（uint演算でラップアラウンドを正しく処理）

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

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IndexDefect | 範囲エラー | 空Dequeに対するpeek/pop操作 | 事前にlen > 0を確認 |
| IndexDefect | 範囲エラー | 範囲外インデックスへのアクセス | 有効な範囲（0..<len）でアクセス |
| AssertionDefect | アサーション | イテレーション中のDeque長さ変更 | イテレーション中は構造を変更しない |

### リトライ仕様

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

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

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

## パフォーマンス要件

- **addFirst/addLast**: 償却O(1)の時間計算量（拡張時O(n)）
- **popFirst/popLast**: O(1)の時間計算量
- **peekFirst/peekLast**: O(1)の時間計算量
- **インデックスアクセス**: O(1)の時間計算量
- **contains**: O(n)の時間計算量（線形探索）
- **空間計算量**: O(n)、ただし容量は要素数の2倍程度まで拡張される可能性あり

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

- 本モジュールはメモリ安全性を保証（boundChecks有効時）
- `-d:danger`や`--checks:off`ではboundChecksが無効化され、不正アクセスでクラッシュやガベージ値の可能性あり
- head/tailはuintで管理され、オーバーフロー/アンダーフローを正しく処理

## 備考

- Nim 1.3以降で追加された機能（toDeque、mutableなpeekFirst/peekLast）には`since`プラグマが付与
- defaultInitialSizeは4（定数として公開）
- 内部的には`seq[T]`と`head`/`tail`ポインタ（uint）で実装

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | deques.nim | `lib/pure/collections/deques.nim` | 55-72行目: Deque型定義とコンスタント |

**読解のコツ**:
- **56-69行目**: `Deque[T]`型は`data: seq[T]`と`head, tail: uint`で構成
- **63-68行目**: head/tailがuintである理由（ラップアラウンド処理の正確性）
- **71-72行目**: `defaultInitialSize = 4`の定数定義

#### Step 2: 初期化とヘルパーテンプレートを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | deques.nim | `lib/pure/collections/deques.nim` | 74-96行目: initImplとinitDeque |
| 2-2 | deques.nim | `lib/pure/collections/deques.nim` | 82-84行目: maskテンプレート |

**主要処理フロー**:
1. **74-76行目**: `initImpl` - nextPowerOfTwoで2のべき乗に切り上げてseqを確保
2. **78-80行目**: `checkIfInitialized` - 遅延初期化サポート
3. **82-83行目**: `mask` - ビットマスク計算（data.len - 1）
4. **85-96行目**: `initDeque` - 公開API、initImplを呼び出し

#### Step 3: インデックスアクセスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | deques.nim | `lib/pure/collections/deques.nim` | 102-116行目: 境界チェックテンプレート |
| 3-2 | deques.nim | `lib/pure/collections/deques.nim` | 118-190行目: []演算子と[]=演算子 |

**主要処理フロー**:
- **102-106行目**: `emptyCheck` - 空Dequeチェック
- **108-116行目**: `xBoundsCheck` - インデックス境界チェック
- **118-127行目**: `[]` (Natural) - 正方向インデックスアクセス
- **152-163行目**: `[]` (BackwardsIndex) - 逆方向インデックスアクセス（^記法）
- **127行目**: `(deq.head + i.uint) and deq.mask` - リングバッファアドレス計算

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | deques.nim | `lib/pure/collections/deques.nim` | 253-266行目: expandIfNeeded |
| 4-2 | deques.nim | `lib/pure/collections/deques.nim` | 268-296行目: addFirst/addLast |
| 4-3 | deques.nim | `lib/pure/collections/deques.nim` | 375-405行目: popFirst/popLast |

**主要処理フロー**:
- **253-266行目**: `expandIfNeeded` - 容量不足時に2倍拡張、要素を新バッファにmove
- **268-281行目**: `addFirst` - headをデクリメント後に要素を配置
- **283-296行目**: `addLast` - 要素を配置後にtailをインクリメント
- **375-389行目**: `popFirst` - headの要素をmoveして返却、headをインクリメント
- **391-405行目**: `popLast` - tailをデクリメント、その位置の要素をmoveして返却

#### Step 5: peek・shrink・clear操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | deques.nim | `lib/pure/collections/deques.nim` | 312-370行目: peekFirst/peekLast |
| 5-2 | deques.nim | `lib/pure/collections/deques.nim` | 407-448行目: clear/shrink |

**主要処理フロー**:
- **312-325行目**: `peekFirst` - 先頭要素を削除せずに返却
- **327-340行目**: `peekLast` - `(tail - 1) and mask`で末尾要素を返却
- **407-419行目**: `clear` - 全要素をdestroyしてtail=headに設定
- **421-448行目**: `shrink` - 前後から指定数の要素を削除

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | deques.nim | `lib/pure/collections/deques.nim` | 192-236行目: items/mitems/pairs |
| 6-2 | deques.nim | `lib/pure/collections/deques.nim` | 238-251行目: contains |
| 6-3 | deques.nim | `lib/pure/collections/deques.nim` | 462-487行目: ==とhash |

**主要処理フロー**:
- **192-206行目**: `items` - 全要素をyield、長さ変更検出のassert付き
- **238-251行目**: `contains` - 線形探索で要素の存在確認
- **462-480行目**: `==` - 長さと各要素の一致を確認
- **482-487行目**: `hash` - 各要素のハッシュを組み合わせ

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

```
deques.nim (ユーザーコード)
    │
    ├─ 初期化
    │   ├─ initDeque(initialSize) → initImpl → nextPowerOfTwo → newSeq
    │   └─ toDeque(openArray) → initImpl → addLast (loop)
    │
    ├─ 追加操作
    │   ├─ addFirst(item) → expandIfNeeded → checkIfInitialized
    │   │                                  → capacity check → 2x拡張
    │   └─ addLast(item) → expandIfNeeded
    │
    ├─ 参照操作
    │   ├─ peekFirst() → emptyCheck → data[head and mask]
    │   ├─ peekLast() → emptyCheck → data[(tail-1) and mask]
    │   └─ [i] → xBoundsCheck → data[(head+i) and mask]
    │
    ├─ 削除操作
    │   ├─ popFirst() → emptyCheck → move → inc head
    │   ├─ popLast() → emptyCheck → dec tail → move
    │   ├─ shrink(fromFirst, fromLast) → destroy (loop)
    │   └─ clear() → mitems → destroy → tail = head
    │
    └─ ユーティリティ
        ├─ len() → tail - head
        ├─ contains(item) → items iteration
        ├─ ==() → len check → element comparison
        └─ hash() → items → hash combination
```

### データフロー図

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

openArray[T] ──────────▶ toDeque ────────────────────────▶ Deque[T]
                              │
                              ▼
initialSize ───────────▶ initDeque ──────────────────────▶ Deque[T]
                              │
                              ▼
                    ┌─────────────────────┐
                    │  Deque[T]           │
                    │  ┌───────────────┐  │
item ──────────────▶│  │ data: seq[T] │  │
                    │  │ head: uint   │  │──────▶ T (peek/pop)
                    │  │ tail: uint   │  │
                    │  └───────────────┘  │──────▶ int (len)
                    │                     │
                    │  リングバッファ構造  │──────▶ bool (contains)
                    └─────────────────────┘
                              │
                              ▼
                    [head + i) and mask]  ──────▶ T (index access)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| deques.nim | `lib/pure/collections/deques.nim` | ソース | メインモジュール（全機能実装） |
| lists.nim | `lib/pure/collections/lists.nim` | ソース | 関連モジュール（連結リスト） |
| math.nim | `lib/pure/math.nim` | ソース | nextPowerOfTwo関数を提供 |
| hashes.nim | `lib/pure/hashes.nim` | ソース | Hash型とhash関数を提供 |
| assertions.nim | `lib/std/assertions.nim` | ソース | assert機能を提供 |
| since.nim | `lib/std/private/since.nim` | ソース | バージョン管理プラグマ |
