# 機能設計書: SortedList

## 1. 機能概要

### 1.1 機能名
SortedList（ソート済みリスト）

### 1.2 機能ID
No.22

### 1.3 機能分類
System.Collections - コレクション

### 1.4 概要説明
SortedListは、キーに基づいてソートされた順序を維持するキー/値ペアのコレクションを表す。.NET FrameworkのSortedListクラスをVB6で実装したもので、二分探索による高速な検索と、常にソート順を維持した状態での要素管理を提供する。

### 1.5 主な用途
- キーでソートされた順序でデータを格納・検索する
- インデックスによる高速なアクセスが必要なシナリオでの利用
- キーと値の両方による検索が必要な場合
- ソート済みの辞書型データ構造の実装

---

## 2. 機能詳細

### 2.1 提供機能一覧

| No | 機能名 | 説明 |
|----|--------|------|
| 1 | Add | 指定したキーと値を持つ要素をソート順に追加 |
| 2 | Clear | すべての要素を削除 |
| 3 | Clone | 浅いコピーを作成 |
| 4 | Contains | 指定したキーが存在するか判定 |
| 5 | ContainsKey | 指定したキーが存在するか判定（二分探索） |
| 6 | ContainsValue | 指定した値が存在するか判定（線形探索） |
| 7 | CopyTo | 要素を配列にコピー |
| 8 | Item | キーに関連付けられた値を取得/設定 |
| 9 | Keys | キーのコレクションを取得 |
| 10 | Values | 値のコレクションを取得 |
| 11 | Remove | 指定したキーの要素を削除 |
| 12 | RemoveAt | 指定したインデックスの要素を削除 |
| 13 | GetByIndex | インデックスで値を取得 |
| 14 | GetKey | インデックスでキーを取得 |
| 15 | IndexOfKey | キーのインデックスを取得（二分探索） |
| 16 | IndexOfValue | 値のインデックスを取得（線形探索） |
| 17 | SetByIndex | インデックスで値を設定 |
| 18 | TrimToSize | 容量を要素数に縮小 |
| 19 | GetEnumerator | 列挙子を取得 |
| 20 | GetKeyList | キーリスト（IList）を取得 |
| 21 | GetValueList | 値リスト（IList）を取得 |

### 2.2 処理フロー

#### 2.2.1 要素追加フロー（Add）
```
1. 要素数が0より大きい場合
   ↓
2. InternalBinarySearch（二分探索でキー位置を検索）
   ↓ キーが見つかった場合
3. ArgumentException（重複キーエラー）をスロー
   ↓ 見つからなかった場合
4. 挿入位置を計算（Not Index）
   ↓
5. Insert（指定位置に要素を挿入）
   ├── EnsureCapacity（容量確保）
   ├── 後続要素のシフト（CopyMemory）
   └── キー/値の格納
   ↓
6. Count増加、Version更新
```

#### 2.2.2 要素検索フロー（Item取得）
```
1. InternalBinarySearch（二分探索）
   ↓
2. インデックス >= 0 の場合
   ↓
3. mValues(Index) から値を返却
   ↓ インデックス < 0 の場合
4. Empty を返却
```

### 2.3 データ構造

#### 2.3.1 クラスメンバ変数
```vb
Private mKeys()     As Variant      ' キー配列（ソート済み）
Private mValues()   As Variant      ' 値配列（キーと対応）
Private mComparer   As IComparer    ' キー比較オブジェクト
Private mCapacity   As Long         ' 容量
Private mCount      As Long         ' 要素数
Private mVersion    As Long         ' バージョン（変更検出用）
```

#### 2.3.2 定数定義
```vb
Private Const DefaultCapacity   As Long = 16    ' デフォルト容量
Private Const PropCount         As String = "Count"
Private Const PropCapacity      As String = "Capacity"
Private Const PropComparer      As String = "Comparer"
```

### 2.4 アルゴリズム詳細

#### 2.4.1 二分探索アルゴリズム
キーの検索にはCorArray.InternalBinarySearchを使用：
```vb
Index = CorArray.InternalBinarySearch(mKeys, 0, mCount, Key, mComparer)
' 戻り値:
'   >= 0: キーが見つかった位置
'   < 0: キーが見つからなかった（Not Index で挿入位置を取得）
```

#### 2.4.2 容量拡張アルゴリズム
```vb
Private Sub EnsureCapacity(ByVal RequiredCapacity As Long)
    ' 容量が0の場合はDefaultCapacity(16)を設定
    ' それ以外は現在の容量を2倍に拡張
    ' 必要容量がそれより大きい場合は必要容量を使用
End Sub
```

### 2.5 実装インターフェース

| インターフェース | 説明 |
|------------------|------|
| IObject | 基本オブジェクト機能（Equals, GetHashCode, ToString） |
| IDictionary | 辞書型コレクション機能 |
| ICollection | コレクション基本機能 |
| IEnumerable | 列挙機能 |
| IVersionable | バージョン管理機能 |

---

## 3. インターフェース仕様

### 3.1 パブリックAPI

#### 3.1.1 Add メソッド
```vb
Public Sub Add(ByRef Key As Variant, ByRef Value As Variant)
```
**パラメータ**:
- Key: 追加する要素のキー
- Value: 追加する要素の値

**例外**:
- ArgumentException: キーが既に存在する場合

#### 3.1.2 Item プロパティ
```vb
Public Property Get Item(ByRef Key As Variant) As Variant
Public Property Let Item(ByRef Key As Variant, ByRef Value As Variant)
Public Property Set Item(ByRef Key As Variant, ByRef Value As Variant)
```
**パラメータ**:
- Key: 取得/設定する要素のキー

**戻り値**: 指定したキーに関連付けられた値、キーが存在しない場合はEmpty

**備考**: キーが存在しない場合は新規追加、存在する場合は上書き

#### 3.1.3 GetByIndex メソッド
```vb
Public Function GetByIndex(ByVal Index As Long) As Variant
```
**パラメータ**:
- Index: 0ベースのインデックス

**戻り値**: 指定インデックスの値

**例外**: ArgumentOutOfRangeException: インデックスが範囲外の場合

#### 3.1.4 GetKey メソッド
```vb
Public Function GetKey(ByVal Index As Long) As Variant
```
**パラメータ**:
- Index: 0ベースのインデックス

**戻り値**: 指定インデックスのキー

**例外**: ArgumentOutOfRangeException: インデックスが範囲外の場合

#### 3.1.5 IndexOfKey メソッド
```vb
Public Function IndexOfKey(ByRef Key As Variant) As Long
```
**戻り値**: キーが見つかった場合はインデックス、見つからない場合は-1

**備考**: 二分探索を使用、O(log n)の計算量

#### 3.1.6 IndexOfValue メソッド
```vb
Public Function IndexOfValue(ByRef Value As Variant) As Long
```
**戻り値**: 値が見つかった場合は最初のインデックス、見つからない場合は-1

**備考**: 線形探索を使用、O(n)の計算量

#### 3.1.7 Remove メソッド
```vb
Public Sub Remove(ByRef Key As Variant)
```
**パラメータ**:
- Key: 削除する要素のキー

**備考**: キーが存在しない場合は何もしない

#### 3.1.8 RemoveAt メソッド
```vb
Public Sub RemoveAt(ByVal Index As Long)
```
**パラメータ**:
- Index: 削除する要素のインデックス

**例外**: ArgumentOutOfRangeException: インデックスが範囲外の場合

---

## 4. 内部処理詳細

### 4.1 Insert サブルーチン
要素を指定位置に挿入する内部サブルーチン。

```vb
Private Sub Insert(ByVal Index As Long, ByRef Key As Variant, ByRef Value As Variant)
```
**処理概要**（803-823行目）:
1. EnsureCapacity で必要容量を確保
2. 挿入位置以降の要素をCopyMemoryで後方シフト
3. 挿入位置をZeroMemoryでクリア
4. VariantCopyIndでキーと値を格納
5. Count増加、Version更新

### 4.2 EnsureCapacity サブルーチン
容量を確保する内部サブルーチン。

```vb
Private Sub EnsureCapacity(ByVal RequiredCapacity As Long)
```
**処理概要**（825-841行目）:
1. 容量が0の場合、DefaultCapacity(16)を設定
2. それ以外は現在容量の2倍を計算
3. 必要容量が計算値より大きければ必要容量を使用
4. ReDim Preserveでキー/値配列を拡張

### 4.3 RemoveAt サブルーチン
要素を削除する内部処理。

**処理概要**（627-651行目）:
1. インデックスの範囲チェック
2. 削除位置の要素をEmptyに設定
3. 後続要素をCopyMemoryで前方シフト
4. 最後の要素をZeroMemoryでクリア
5. Count減少、Version更新

---

## 5. 関連コンポーネント

### 5.1 依存クラス

| クラス名 | 用途 |
|----------|------|
| IComparer | キーの比較（ソート順の決定） |
| Comparer | デフォルトの比較実装 |
| SortedListEnumerator | SortedList専用の列挙子 |
| SortedKeyList | キーコレクションのビュー（IList実装） |
| SortedValueList | 値コレクションのビュー（IList実装） |
| DictionaryEntry | キー/値ペアの表現 |
| CorArray | 二分探索、ソート、コピー機能 |

### 5.2 シリアライゼーション
PropertyBagを使用した永続化をサポート（763-797行目）:
- Count, Capacity, Comparerを保存
- 各キー/値ペアを個別に保存（Key0, Value0, Key1, Value1...）

---

## 6. エラー処理

### 6.1 例外一覧

| 例外 | 発生条件 |
|------|----------|
| ArgumentException | 重複キーの追加時 |
| ArgumentNullException | 配列がNullの場合 |
| ArgumentOutOfRangeException | インデックスが範囲外の場合、容量がCount未満の場合 |
| InvalidCastException | CopyTo時に型が一致しない場合 |
| InvalidOperationException | Comparerが例外をスローした場合 |

### 6.2 エラーメッセージ
```vb
' 重複キーエラー
Argument_AddingDuplicate_Key = "重複キー '{0}' を追加しようとしました"
' 容量不足エラー
ArgumentOutOfRange_SmallCapacity = "容量がCount未満です"
```

---

## 7. パフォーマンス考慮

### 7.1 計算量

| 操作 | 平均 | 最悪 |
|------|------|------|
| Add | O(n) | O(n) |
| Remove | O(n) | O(n) |
| Item取得 | O(log n) | O(log n) |
| ContainsKey | O(log n) | O(log n) |
| ContainsValue | O(n) | O(n) |
| IndexOfKey | O(log n) | O(log n) |
| IndexOfValue | O(n) | O(n) |
| GetByIndex | O(1) | O(1) |

### 7.2 推奨事項
- 頻繁な追加/削除がある場合はHashtableの使用を検討
- インデックスによるアクセスが多い場合に最適
- 事前に容量がわかる場合は初期容量を指定
- 大量追加後はTrimToSizeでメモリ最適化

---

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

### 8.1 推奨読解順序

1. **データ構造の理解**
   - `SortedList.cls` 63-68行目: メンバ変数定義
   - 57行目: DefaultCapacity定数

2. **初期化処理**
   - `Init` (732-744行目): パラメータ付き初期化
   - `InitClone` (746-752行目): クローン用初期化
   - `Class_InitProperties` (754-757行目): デフォルト初期化

3. **基本操作**
   - `Add` (85-98行目): 要素追加（二分探索+挿入）
   - `Item Get` (473-481行目): 要素取得（二分探索）
   - `Item Let` (515-526行目): 要素設定
   - `Remove` (606-617行目): 要素削除
   - `RemoveAt` (627-651行目): インデックス指定削除

4. **内部アルゴリズム**
   - `Insert` (803-823行目): 挿入ロジック
   - `EnsureCapacity` (825-841行目): 容量拡張
   - `CorArray.InternalBinarySearch`: 二分探索（外部モジュール）

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

```
SortedList.Add
  ├── CorArray.InternalBinarySearch (キー検索)
  └── Insert
        ├── EnsureCapacity
        │     └── ReDim Preserve (配列拡張)
        ├── CopyMemory (要素シフト)
        └── VariantCopyInd (値格納)

SortedList.Item(Get)
  └── CorArray.InternalBinarySearch
        └── IComparer.Compare (キー比較)

SortedList.Remove
  ├── CorArray.InternalBinarySearch
  └── RemoveAt
        ├── CopyMemory (要素シフト)
        └── ZeroMemory (メモリクリア)

SortedList.GetEnumerator
  └── SortedListEnumerator.Init
```

### 8.3 データフロー図

```
[キー/値] ──→ [InternalBinarySearch] ──→ [挿入位置計算]
                     │                          │
                     ↓                          ↓
              [IComparer.Compare]        [Insert/EnsureCapacity]
                     │                          │
                     └──────→ [mKeys配列] ←─────┘
                              [mValues配列]
                                    │
                                    ↓
                              [ソート済み格納]
```

### 8.4 関連ファイル一覧

| パス | 種別 | 役割 |
|------|------|------|
| Source/CorLib/System.Collections/SortedList.cls | クラス | メインクラス |
| Source/CorLib/System.Collections/SortedListEnumerator.cls | クラス | 列挙子 |
| Source/CorLib/System.Collections/SortedKeyList.cls | クラス | キーリストビュー |
| Source/CorLib/System.Collections/SortedValueList.cls | クラス | 値リストビュー |
| Source/CorLib/System.Collections/Comparer.cls | クラス | デフォルト比較 |
| Source/CorLib/System.Collections/IComparer.cls | インターフェース | 比較契約 |
| Source/CorLib/System/CorArray.cls | モジュール | 二分探索、配列操作 |

### 8.5 読解のコツ
- Add時の `Not Index` は二分探索で見つからなかった場合の挿入位置取得
- CopyMemory/ZeroMemoryはWin32 APIによる高速メモリ操作
- mVersionはFor Each中の変更検出に使用される
- vbSizeOfVariantはVariant型のバイトサイズ（16バイト）

---

## 9. 変更履歴

| 日付 | バージョン | 変更内容 |
|------|------------|----------|
| 2015 | 1.0 | 初期実装（Kelly Ethridge） |

---

## 10. 備考

- .NET FrameworkのSystem.Collections.SortedListと互換性のあるAPI設計
- Hashtableと異なり、キーによるソート順を常に維持
- インデックスによるアクセスが可能（Hashtableでは不可）
- 二分探索による高速なキー検索（O(log n)）
- 追加/削除は要素シフトのためO(n)のコスト
