swarm_engine_core/exploration/

map.rs

//! Exploration Map - 探索マップの抽象層
//!
//! 課題空間を「マップ走査」として解くための抽象インターフェース。
//!
//! # 設計思想
//!
//! - **Tick ベース更新**: `apply(update) -> Result` で状態を確定的に更新
//! - **Node の抽象化**: 何を Node とするかは実装が決める
//! - **内部表現の自由**: Graph / Grid / Tree など実装詳細は隠蔽
//!
//! # 使用例
//!
//! ```ignore
//! // 課題を Node とするマップ
//! let mut map = TaskMap::new();
//!
//! // Tick ごとに更新を適用
//! let result = map.apply(update);
//!
//! // フロンティアから次の探索対象を取得
//! for node_id in map.frontiers() {
//!     let node = map.get(node_id);
//!     // ...
//! }
//! ```
//!
//! # 旧 ExplorationSpace からの移行
//!
//! 旧 `ExplorationSpace` には以下の機能があったが、クリーンな探索マップ設計では
//! 多くが不要になる（または別レイヤーの責務となる）。
//!
//! ## 新設計で解決済み
//!
//! | 旧機能 | 問題点 | 新設計での解決 |
//! |--------|--------|----------------|
//! | `NodeKind` (Exploration/ActionNode) | 分岐がコード全体に散らばる | Node 型パラメータ `<N>` で柔軟に |
//! | 2つの apply API | `apply_update` と `apply_results` 混在 | `apply()` に統一 |
//! | `ExplorationNode` 固定 | 拡張性がない | `MapNode<T>` で任意データを格納 |
//!
//! ## 別レイヤーの責務（マップ外で処理）
//!
//! | 旧機能 | 新設計での扱い |
//! |--------|----------------|
//! | `DependencyGraph` 統合 | Orchestrator/Strategy 層で注入 |
//! | `SubRoot` 管理 | 上位レイヤーで課題分解を担当 |
//! | `NodeSelectionStrategy` | Strategy 層で `frontiers()` を使って実装 |
//! | `has_successful_action_globally` | 上位レイヤーで履歴管理 |
//!
//! ## シンプル化により不要
//!
//! | 旧機能 | 理由 |
//! |--------|------|
//! | `NodeState` (5状態) | `Open`/`Closed` の2状態で十分。詳細は Node データ `T` で管理 |
//! | `TrialPolicy` (OneShot/Retriable/Probabilistic) | Node データ `T` でリトライ回数を管理 |
//! | `ActionCategory` (NodeExpand/NodeStateChange) | Update バリアントで明示 |
//! | `ExplorationTarget` / `ExplorationUpdate` | `GraphMapUpdate` で統一 |
//! | `NodeAssignment` (複雑なメタデータ) | シンプルな `MapNodeId` で足りる |
//!
//! ## 設計原則
//!
//! 1. **マップは純粋なデータ構造**: 戦略やポリシーは外から注入
//! 2. **Tick ベースの確定的更新**: `apply()` で全ての状態遷移を表現
//! 3. **Node の抽象化**: 課題/Action/状態など、用途に応じて型で表現
//! 4. **複雑さは上位レイヤーへ**: DependencyGraph、SubRoot 等は Orchestrator の責務

use std::collections::hash_map::DefaultHasher;
use std::fmt::Debug;
use std::hash::{Hash, Hasher};

use serde::{Deserialize, Serialize};

// ============================================================================
// Core ID Types
// ============================================================================

/// ノード ID（マップ内で一意）
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct MapNodeId(pub u64);

impl MapNodeId {
    pub fn new(id: u64) -> Self {
        Self(id)
    }
}

/// エッジ ID（マップ内で一意）
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct MapEdgeId(pub u64);

impl MapEdgeId {
    pub fn new(id: u64) -> Self {
        Self(id)
    }
}

// ============================================================================
// Error Types
// ============================================================================

/// マップ操作のエラー
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum MapError {
    /// ノードが見つからない
    #[error("Node not found: {0:?}")]
    NodeNotFound(MapNodeId),

    /// エッジが見つからない
    #[error("Edge not found: {0:?}")]
    EdgeNotFound(MapEdgeId),

    /// ノード ID の衝突
    #[error("Node ID conflict: {0:?}")]
    NodeConflict(MapNodeId),

    /// エッジ ID の衝突
    #[error("Edge ID conflict: {0:?}")]
    EdgeConflict(MapEdgeId),

    /// 無効な状態遷移
    #[error("Invalid state transition: {from:?} -> {to:?}")]
    InvalidStateTransition {
        node_id: MapNodeId,
        from: MapNodeState,
        to: MapNodeState,
    },

    /// ルートノードが既に存在
    #[error("Root node already exists: {0:?}")]
    RootAlreadyExists(MapNodeId),

    /// 親ノードが見つからない
    #[error("Parent node not found: {0:?}")]
    ParentNotFound(MapNodeId),

    /// ノードが既に Closed
    #[error("Node already closed: {0:?}")]
    AlreadyClosed(MapNodeId),
}

/// マップ操作の結果型
pub type MapResult<T> = Result<T, MapError>;

/// 追加操作の結果
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AddResult<T> {
    /// 新規追加された
    Added(T),
    /// 既に存在していた（既存の値を返す）
    AlreadyExists(T),
}

impl<T> AddResult<T> {
    /// 追加されたかどうか
    pub fn is_added(&self) -> bool {
        matches!(self, Self::Added(_))
    }

    /// 既に存在していたかどうか
    pub fn is_already_exists(&self) -> bool {
        matches!(self, Self::AlreadyExists(_))
    }

    /// 内部の値を取得
    pub fn into_inner(self) -> T {
        match self {
            Self::Added(v) | Self::AlreadyExists(v) => v,
        }
    }

    /// 内部の値への参照を取得
    pub fn as_inner(&self) -> &T {
        match self {
            Self::Added(v) | Self::AlreadyExists(v) => v,
        }
    }
}

// ============================================================================
// Core Trait: ExplorationMap
// ============================================================================

/// 探索マップの抽象インターフェース
///
/// Tick ベースでマップを更新し、探索状態を管理する。
///
/// # 型パラメータ
///
/// - `Node`: ノードに持たせるデータ（課題 / Action / 状態 など）
/// - `Edge`: エッジに持たせるデータ（遷移情報など）
/// - `Update`: Tick 更新の入力型
/// - `Result`: apply の結果型
///
/// # 実装例
///
/// - `GraphMap`: グラフ構造のマップ（現在の ExplorationSpace に相当）
/// - `GridMap`: グリッド構造のマップ
/// - `TreeMap`: 木構造のマップ
pub trait ExplorationMap {
    /// ノードに持たせるデータ型
    type Node: Debug + Clone;

    /// エッジに持たせるデータ型
    type Edge: Debug + Clone;

    /// Tick 更新の入力型
    type Update;

    /// apply の結果型
    type Result;

    // ========================================================================
    // Core Tick API
    // ========================================================================

    /// 更新を適用する（Tick の中心 API）
    ///
    /// 毎 Tick でこのメソッドを呼び、マップ状態を更新する。
    /// 更新は確定的に処理され、結果が返される。
    fn apply(&mut self, update: Self::Update) -> Self::Result;

    /// 複数の更新をバッチ適用
    fn apply_batch(&mut self, updates: Vec<Self::Update>) -> Vec<Self::Result> {
        updates.into_iter().map(|u| self.apply(u)).collect()
    }

    // ========================================================================
    // Node API
    // ========================================================================

    /// ノードを取得
    fn get(&self, id: MapNodeId) -> Option<&Self::Node>;

    /// ノードを変更可能で取得
    fn get_mut(&mut self, id: MapNodeId) -> Option<&mut Self::Node>;

    /// ノード数
    fn node_count(&self) -> usize;

    // ========================================================================
    // Frontier API
    // ========================================================================

    /// 現在のフロンティア（Expandable なノード群）を取得
    ///
    /// Closed になったノードは含まれない。
    /// これを「枯渇」「完了」と解釈するかは利用者の責務。
    fn frontiers(&self) -> Vec<MapNodeId>;
}

// ============================================================================
// Extended Traits
// ============================================================================

/// グラフ構造を持つマップ
///
/// ノード間のエッジ関係をクエリ可能。
pub trait GraphExplorationMap: ExplorationMap {
    /// エッジを取得
    fn get_edge(&self, id: MapEdgeId) -> Option<&Self::Edge>;

    /// ノードからの出ていくエッジを取得
    fn outgoing_edges(&self, node: MapNodeId) -> Vec<MapEdgeId>;

    /// ノードに入ってくるエッジを取得（親エッジ）
    fn incoming_edge(&self, node: MapNodeId) -> Option<MapEdgeId>;

    /// エッジ数
    fn edge_count(&self) -> usize;

    /// ルートノードを取得
    fn root(&self) -> Option<MapNodeId>;
}

/// 階層構造を持つマップ
///
/// 親子関係をクエリ可能。
pub trait HierarchicalMap: ExplorationMap {
    /// 親ノードを取得
    fn parent(&self, node: MapNodeId) -> Option<MapNodeId>;

    /// 子ノード群を取得
    fn children(&self, node: MapNodeId) -> Vec<MapNodeId>;

    /// ノードの深さを取得
    fn depth(&self, node: MapNodeId) -> u32;
}

// ============================================================================
// Common Update Types
// ============================================================================

/// 汎用的な更新結果
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MapApplyResult<N> {
    /// 新しいノードが作成された
    NodeCreated { node_id: MapNodeId, data: N },
    /// ノードの状態が更新された
    NodeUpdated { node_id: MapNodeId },
    /// ノードが完了としてマークされた
    NodeCompleted { node_id: MapNodeId },
    /// ノードが行き止まりとしてマークされた
    NodeDeadEnd { node_id: MapNodeId },
    /// 失敗（リトライ可能かどうかを含む）
    Failed {
        node_id: MapNodeId,
        can_retry: bool,
        reason: String,
    },
    /// 無視された（重複や Pending など）
    Ignored,
}

// ============================================================================
// MapState Trait - 状態型の最小制約
// ============================================================================

/// Map が状態型 S に要求する制約
///
/// Map は状態の「意味」を知らない。Map が興味を持つのは2点のみ:
///
/// - **Expandable**: 子ノード追加可能（フロンティアとして管理）
/// - **Closed**: 終了（フロンティアから除外）
///
/// 具体的な状態の詳細（Unexplored/Exploring/Explored/DeadEnd/Completed/Processing 等）は
/// この trait を実装する型で自由に定義できる。Map はそれらを
/// `is_expandable()` / `is_closed()` で抽象化して扱う。
///
/// # 例: カスタム状態型
///
/// ```ignore
/// #[derive(Clone, Debug)]
/// enum MyState {
///     Pending,      // → Expandable
///     Processing,   // → neither (Map は関与しない)
///     Completed,    // → Closed
///     Failed,       // → Closed
/// }
///
/// impl MapState for MyState {
///     fn is_expandable(&self) -> bool {
///         matches!(self, Self::Pending)
///     }
///     fn is_closed(&self) -> bool {
///         matches!(self, Self::Completed | Self::Failed)
///     }
///     fn closed() -> Self {
///         Self::Completed
///     }
/// }
/// ```
pub trait MapState: Clone + std::fmt::Debug {
    /// フロンティアとして展開可能か
    fn is_expandable(&self) -> bool;

    /// 終了状態か（フロンティアから除外される）
    fn is_closed(&self) -> bool;

    /// デフォルトの Closed 状態を返す（カスケード操作等で使用）
    fn closed() -> Self;
}

// ============================================================================
// MapNodeState - デフォルトの2状態実装
// ============================================================================

/// ノードの基本状態
///
/// シンプルに Open（探索可能）と Closed（終了）の2状態のみ。
/// 詳細な状態（成功/失敗/リトライ回数など）は Node のデータ `T` で管理する。
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, Default)]
pub enum MapNodeState {
    /// 探索可能（フロンティア）
    #[default]
    Open,
    /// 終了（フロンティアから除外）
    Closed,
}

impl MapState for MapNodeState {
    fn is_expandable(&self) -> bool {
        matches!(self, Self::Open)
    }

    fn is_closed(&self) -> bool {
        matches!(self, Self::Closed)
    }

    fn closed() -> Self {
        Self::Closed
    }
}

impl MapNodeState {
    /// フロンティアになりうる状態か
    pub fn is_open(&self) -> bool {
        matches!(self, Self::Open)
    }

    /// 終了状態か
    pub fn is_closed(&self) -> bool {
        matches!(self, Self::Closed)
    }
}

// ============================================================================
// Node Wrapper
// ============================================================================

/// 汎用ノードラッパー
///
/// ユーザー定義のデータ `N` と状態 `S` に共通のメタデータを付与する。
///
/// # 型パラメータ
///
/// - `N`: ノードデータの型
/// - `S`: 状態の型（MapState を実装）
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct MapNode<N, S: MapState> {
    /// ノード ID
    pub id: MapNodeId,
    /// ユーザー定義データ
    pub data: N,
    /// 状態
    pub state: S,
    /// 深さ
    pub depth: u32,
    /// 親エッジ（ルートは None）
    pub parent_edge: Option<MapEdgeId>,
}

impl<N, S: MapState> MapNode<N, S> {
    pub fn new(id: MapNodeId, data: N, state: S) -> Self {
        Self {
            id,
            data,
            state,
            depth: 0,
            parent_edge: None,
        }
    }

    pub fn with_state(mut self, state: S) -> Self {
        self.state = state;
        self
    }

    pub fn with_depth(mut self, depth: u32) -> Self {
        self.depth = depth;
        self
    }

    pub fn with_parent(mut self, edge: MapEdgeId) -> Self {
        self.parent_edge = Some(edge);
        self
    }
}

// ============================================================================
// Edge Wrapper
// ============================================================================

/// 汎用エッジラッパー
///
/// ユーザー定義のデータ `T` に共通のメタデータを付与する。
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct MapEdge<T> {
    /// エッジ ID
    pub id: MapEdgeId,
    /// 元ノード
    pub from: MapNodeId,
    /// 先ノード（成功時のみ設定）
    pub to: Option<MapNodeId>,
    /// ユーザー定義データ
    pub data: T,
    /// 試行回数
    pub attempts: u32,
    /// 成功したか
    pub succeeded: bool,
}

impl<T> MapEdge<T> {
    pub fn new(id: MapEdgeId, from: MapNodeId, data: T) -> Self {
        Self {
            id,
            from,
            to: None,
            data,
            attempts: 0,
            succeeded: false,
        }
    }

    pub fn mark_success(&mut self, to: MapNodeId) {
        self.succeeded = true;
        self.to = Some(to);
        self.attempts += 1;
    }

    pub fn mark_failure(&mut self) {
        self.succeeded = false;
        self.attempts += 1;
    }
}

// ============================================================================
// GraphMap - グラフ構造のマップ実装
// ============================================================================

use std::collections::{HashMap, HashSet};

/// グラフベースの探索マップ
///
/// ノードとエッジでグラフ構造を表現する。
/// `ExplorationMap` と `GraphExplorationMap` を実装。
///
/// # 型パラメータ
///
/// - `N`: ノードデータの型（課題 / Action / 状態 など）
/// - `E`: エッジデータの型（アクション / 遷移情報 など）
/// - `S`: 状態の型（MapState を実装）
///
/// # 使用例
///
/// ```ignore
/// // 文字列をノードデータとするマップ
/// let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
///
/// // ルートノードを作成
/// let root = map.create_root("start".to_string(), MapNodeState::Open);
///
/// // 子ノードを追加
/// let update = GraphMapUpdate::AddChild {
///     parent: root,
///     edge_data: "action-1".to_string(),
///     node_data: "state-1".to_string(),
///     node_state: MapNodeState::Open,
///     dedup_key: "state-1".to_string(),
/// };
/// let result = map.apply(update);
/// ```
#[derive(Debug, Clone)]
pub struct GraphMap<N, E, S: MapState> {
    /// ノード群
    nodes: HashMap<MapNodeId, MapNode<N, S>>,
    /// エッジ群
    edges: HashMap<MapEdgeId, MapEdge<E>>,
    /// フロンティア（展開可能なノード群）- O(1) 操作のため HashSet
    expandables: HashSet<MapNodeId>,
    /// ルートノード
    root: Option<MapNodeId>,
    /// 次のノード ID
    next_node_id: u64,
    /// 次のエッジ ID
    next_edge_id: u64,
    /// ノードインデックス（キーハッシュ → ノードID）
    /// 重複チェック用。キー抽出関数のハッシュ値でノードを検索可能にする。
    index: HashMap<u64, MapNodeId>,
}

impl<N, E, S: MapState> Default for GraphMap<N, E, S> {
    fn default() -> Self {
        Self::new()
    }
}

impl<N, E, S: MapState> GraphMap<N, E, S> {
    /// 空のマップを作成
    pub fn new() -> Self {
        Self {
            nodes: HashMap::new(),
            edges: HashMap::new(),
            expandables: HashSet::new(),
            root: None,
            next_node_id: 0,
            next_edge_id: 0,
            index: HashMap::new(),
        }
    }

    // ========================================================================
    // Index API (D)
    // ========================================================================

    /// キーのハッシュ値を計算
    fn compute_hash<K: Hash>(key: &K) -> u64 {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        hasher.finish()
    }

    /// ノードをインデックスに登録
    ///
    /// キー抽出関数でキーを取得し、ハッシュ値でインデックスに登録する。
    pub fn index_node<K, F>(&mut self, node_id: MapNodeId, key_fn: F)
    where
        K: Hash,
        F: FnOnce(&N) -> K,
    {
        if let Some(node) = self.nodes.get(&node_id) {
            let key = key_fn(&node.data);
            let hash = Self::compute_hash(&key);
            self.index.insert(hash, node_id);
        }
    }

    /// キーでノードを検索
    ///
    /// インデックスを使って O(1) で検索。
    pub fn get_by_key<K: Hash>(&self, key: &K) -> Option<MapNodeId> {
        let hash = Self::compute_hash(key);
        self.index.get(&hash).copied()
    }

    /// キーが存在するか確認
    pub fn contains_key<K: Hash>(&self, key: &K) -> bool {
        self.get_by_key(key).is_some()
    }

    /// インデックスをクリア
    pub fn clear_index(&mut self) {
        self.index.clear();
    }

    /// インデックスを再構築
    ///
    /// 全ノードに対してキー抽出関数を適用し、インデックスを再構築する。
    pub fn rebuild_index<K, F>(&mut self, key_fn: F)
    where
        K: Hash,
        F: Fn(&N) -> K,
    {
        self.index.clear();
        for (&node_id, node) in &self.nodes {
            let key = key_fn(&node.data);
            let hash = Self::compute_hash(&key);
            self.index.insert(hash, node_id);
        }
    }

    // ========================================================================
    // Search API (B)
    // ========================================================================

    /// 条件に一致する最初のノードを検索
    ///
    /// O(n) の線形検索。頻繁に呼ぶ場合はインデックスを使う。
    pub fn find_node<F>(&self, predicate: F) -> Option<MapNodeId>
    where
        F: Fn(&MapNode<N, S>) -> bool,
    {
        self.nodes.values().find(|n| predicate(n)).map(|n| n.id)
    }

    /// 条件に一致する全ノードを検索
    pub fn find_nodes<F>(&self, predicate: F) -> Vec<MapNodeId>
    where
        F: Fn(&MapNode<N, S>) -> bool,
    {
        self.nodes
            .values()
            .filter(|n| predicate(n))
            .map(|n| n.id)
            .collect()
    }

    /// データで検索（N: PartialEq の場合）
    pub fn find_by_data(&self, data: &N) -> Option<MapNodeId>
    where
        N: PartialEq,
    {
        self.nodes.values().find(|n| &n.data == data).map(|n| n.id)
    }

    /// 状態で検索（S: PartialEq の場合）
    ///
    /// 指定した状態のノードを全て返す。
    /// 利用者が「Completed 状態のノード」「Failed 状態のノード」等を
    /// 取得するのに使う。
    pub fn find_by_state(&self, state: &S) -> Vec<MapNodeId>
    where
        S: PartialEq,
    {
        self.nodes
            .values()
            .filter(|n| &n.state == state)
            .map(|n| n.id)
            .collect()
    }

    /// 状態の条件で検索
    ///
    /// 状態に対する任意の条件でノードを検索する。
    pub fn find_nodes_by_state<F>(&self, predicate: F) -> Vec<MapNodeId>
    where
        F: Fn(&S) -> bool,
    {
        self.nodes
            .values()
            .filter(|n| predicate(&n.state))
            .map(|n| n.id)
            .collect()
    }

    // ========================================================================
    // Add with Dedup API
    // ========================================================================

    /// 重複チェック付きルートノード作成
    ///
    /// キーが既に存在する場合は既存ノードを返す。
    pub fn create_root_if_absent<K, F>(
        &mut self,
        data: N,
        state: S,
        key_fn: F,
    ) -> AddResult<MapNodeId>
    where
        K: Hash,
        F: FnOnce(&N) -> K,
    {
        let key = key_fn(&data);
        let hash = Self::compute_hash(&key);

        if let Some(&existing) = self.index.get(&hash) {
            return AddResult::AlreadyExists(existing);
        }

        let id = self.create_root(data, state);
        self.index.insert(hash, id);
        AddResult::Added(id)
    }

    /// 重複チェック付きノード追加（親ノード指定）
    ///
    /// キーが既に存在する場合は既存ノードを返す。
    /// 親ノードが見つからない場合はエラー。
    pub fn add_child_if_absent<K, F>(
        &mut self,
        parent: MapNodeId,
        edge_data: E,
        node_data: N,
        node_state: S,
        key_fn: F,
    ) -> MapResult<AddResult<MapNodeId>>
    where
        K: Hash,
        F: FnOnce(&N) -> K,
    {
        let key = key_fn(&node_data);
        let hash = Self::compute_hash(&key);

        if let Some(&existing) = self.index.get(&hash) {
            return Ok(AddResult::AlreadyExists(existing));
        }

        // 親ノードの深さを取得
        let parent_depth = self
            .nodes
            .get(&parent)
            .map(|n| n.depth)
            .ok_or(MapError::ParentNotFound(parent))?;

        // エッジとノードを作成
        let edge_id = self.add_edge(parent, edge_data);
        let id = self.add_node(node_data, node_state, edge_id, parent_depth + 1);

        // エッジの to を設定（親子関係を確立）
        if let Some(edge) = self.edges.get_mut(&edge_id) {
            edge.to = Some(id);
        }

        // インデックスに登録
        self.index.insert(hash, id);

        Ok(AddResult::Added(id))
    }

    /// ルートノードを作成
    pub fn create_root(&mut self, data: N, state: S) -> MapNodeId {
        let id = self.allocate_node_id();
        let node = MapNode::new(id, data, state.clone());
        self.nodes.insert(id, node);
        if state.is_expandable() {
            self.expandables.insert(id);
        }
        self.root = Some(id);
        id
    }

    /// ノードを追加（内部用）
    fn add_node(&mut self, data: N, state: S, parent_edge: MapEdgeId, depth: u32) -> MapNodeId {
        let id = self.allocate_node_id();
        let node = MapNode::new(id, data, state.clone())
            .with_parent(parent_edge)
            .with_depth(depth);
        self.nodes.insert(id, node);
        if state.is_expandable() {
            self.expandables.insert(id);
        }
        id
    }

    /// エッジを追加（内部用）
    fn add_edge(&mut self, from: MapNodeId, data: E) -> MapEdgeId {
        let id = self.allocate_edge_id();
        let edge = MapEdge::new(id, from, data);
        self.edges.insert(id, edge);

        id
    }

    /// ノード ID を割り当て
    fn allocate_node_id(&mut self) -> MapNodeId {
        let id = MapNodeId(self.next_node_id);
        self.next_node_id += 1;
        id
    }

    /// エッジ ID を割り当て
    fn allocate_edge_id(&mut self) -> MapEdgeId {
        let id = MapEdgeId(self.next_edge_id);
        self.next_edge_id += 1;
        id
    }

    /// ノードの状態を更新
    ///
    /// 状態変更時に expandables インデックスを自動更新する。
    pub fn set_state(&mut self, id: MapNodeId, state: S) {
        if let Some(node) = self.nodes.get_mut(&id) {
            let was_expandable = node.state.is_expandable();
            node.state = state;
            let is_expandable = node.state.is_expandable();

            // expandables インデックス更新（O(1)）
            if was_expandable && !is_expandable {
                self.expandables.remove(&id);
            } else if !was_expandable && is_expandable {
                self.expandables.insert(id);
            }
        }
    }

    // ========================================================================
    // Batch Operations
    // ========================================================================

    /// 複数ノードを一括追加
    ///
    /// 各 (data, state) ペアからノードを作成。
    /// 最初のノードがルートになり、以降は独立したノードとして追加。
    pub fn add_nodes(&mut self, nodes: Vec<(N, S)>) -> Vec<MapNodeId> {
        nodes
            .into_iter()
            .map(|(data, state)| {
                if self.root.is_none() {
                    self.create_root(data, state)
                } else {
                    // ルートが既にある場合は独立ノードとして追加
                    let id = self.allocate_node_id();
                    let is_expandable = state.is_expandable();
                    let node = MapNode::new(id, data, state);
                    self.nodes.insert(id, node);
                    if is_expandable {
                        self.expandables.insert(id);
                    }
                    id
                }
            })
            .collect()
    }

    /// 複数ノードの状態を一括変更
    pub fn set_states(&mut self, ids: &[MapNodeId], state: S) -> Vec<MapNodeId> {
        let mut changed = Vec::new();
        for &id in ids {
            if self.nodes.contains_key(&id) {
                self.set_state(id, state.clone());
                changed.push(id);
            }
        }
        changed
    }

    /// 複数ノードを一括 Close（S::closed() を使用）
    ///
    /// 存在しないノード ID はスキップされる。
    /// 戻り値は実際に Close されたノード ID のリスト。
    pub fn close_nodes(&mut self, ids: &[MapNodeId]) -> Vec<MapNodeId> {
        self.set_states(ids, S::closed())
    }

    // ========================================================================
    // Cascade Operations
    // ========================================================================

    /// 下方向カスケード: 自身と全子孫を Close
    ///
    /// 戻り値は Close されたノード ID のリスト（指定ノード含む）。
    pub fn cascade_down(&mut self, id: MapNodeId) -> Vec<MapNodeId> {
        let mut closed = Vec::new();
        self.cascade_down_recursive(id, &mut closed);
        closed
    }

    fn cascade_down_recursive(&mut self, id: MapNodeId, closed: &mut Vec<MapNodeId>) {
        if !self.nodes.contains_key(&id) {
            return;
        }

        // 子ノードを先に処理（深さ優先）
        let children: Vec<MapNodeId> = self.children_internal(id);
        for child in children {
            self.cascade_down_recursive(child, closed);
        }

        // 自身を Close
        self.set_state(id, S::closed());
        closed.push(id);
    }

    /// 子ノード一覧を取得
    pub fn children(&self, node: MapNodeId) -> Vec<MapNodeId> {
        self.children_internal(node)
    }

    /// 子ノード一覧を取得（内部用）
    fn children_internal(&self, node: MapNodeId) -> Vec<MapNodeId> {
        self.edges
            .values()
            .filter(|e| e.from == node && e.to.is_some())
            .filter_map(|e| e.to)
            .collect()
    }

    /// 上方向カスケード: 全子が is_closed() なら親を Close（再帰）
    ///
    /// 戻り値は Close されたノード ID のリスト。
    pub fn cascade_up_if_all_closed(&mut self, id: MapNodeId) -> Vec<MapNodeId> {
        let mut closed = Vec::new();
        self.cascade_up_recursive(id, &mut closed);
        closed
    }

    fn cascade_up_recursive(&mut self, id: MapNodeId, closed: &mut Vec<MapNodeId>) {
        let parent = self.parent_internal(id);
        if let Some(parent_id) = parent {
            let all_children_closed = self.children_internal(parent_id).iter().all(|&child| {
                self.nodes
                    .get(&child)
                    .map(|n| n.state.is_closed())
                    .unwrap_or(true)
            });

            if all_children_closed {
                self.set_state(parent_id, S::closed());
                closed.push(parent_id);
                self.cascade_up_recursive(parent_id, closed);
            }
        }
    }

    /// 親ノードを取得
    pub fn parent(&self, node: MapNodeId) -> Option<MapNodeId> {
        self.parent_internal(node)
    }

    /// 親ノードを取得（内部用）
    fn parent_internal(&self, node: MapNodeId) -> Option<MapNodeId> {
        self.nodes
            .get(&node)
            .and_then(|n| n.parent_edge)
            .and_then(|edge_id| self.edges.get(&edge_id))
            .map(|e| e.from)
    }

    /// 状態変更 + 上方向カスケード
    ///
    /// ノードを Close した後、親が Close 可能ならカスケード。
    /// 戻り値は Close されたノード ID のリスト（自身含む）。
    pub fn close_with_cascade_up(&mut self, id: MapNodeId) -> Vec<MapNodeId> {
        let mut closed = Vec::new();

        if self.nodes.contains_key(&id) {
            self.set_state(id, S::closed());
            closed.push(id);
            closed.extend(self.cascade_up_if_all_closed(id));
        }

        closed
    }

    // ========================================================================
    // Query Operations
    // ========================================================================

    /// 複数ノードを一括取得
    ///
    /// 存在しない ID はスキップされる。
    /// 順序は入力の順序を保持。
    pub fn get_nodes(&self, ids: &[MapNodeId]) -> Vec<&MapNode<N, S>> {
        ids.iter().filter_map(|id| self.nodes.get(id)).collect()
    }

    /// 複数ノードのデータを一括取得
    ///
    /// 存在しない ID はスキップされる。
    /// ノード全体ではなくデータ部分のみが必要な場合に使用。
    pub fn get_node_data(&self, ids: &[MapNodeId]) -> Vec<&N> {
        ids.iter()
            .filter_map(|id| self.nodes.get(id).map(|n| &n.data))
            .collect()
    }

    /// 展開可能なノード一覧（= expandables）
    pub fn expandables(&self) -> impl Iterator<Item = MapNodeId> + '_ {
        self.expandables.iter().copied()
    }

    /// 展開可能なノード数
    pub fn expandables_count(&self) -> usize {
        self.expandables.len()
    }

    /// Closed なノード一覧
    pub fn closed_nodes(&self) -> Vec<MapNodeId> {
        self.nodes
            .values()
            .filter(|n| n.state.is_closed())
            .map(|n| n.id)
            .collect()
    }

    /// 作業中のノード一覧（!is_expandable && !is_closed）
    ///
    /// フロンティアでも終了でもない中間状態のノード。
    /// 例: Processing, Pending など。
    pub fn working_nodes(&self) -> Vec<MapNodeId> {
        self.nodes
            .values()
            .filter(|n| !n.state.is_expandable() && !n.state.is_closed())
            .map(|n| n.id)
            .collect()
    }
}

// ============================================================================
// GraphMap Update Types
// ============================================================================

/// GraphMap の更新入力
#[derive(Debug, Clone)]
pub enum GraphMapUpdate<N, E, S: MapState> {
    /// 子ノードを追加
    AddChild {
        /// 親ノード
        parent: MapNodeId,
        /// エッジデータ
        edge_data: E,
        /// 新しいノードのデータ
        node_data: N,
        /// 新しいノードの状態
        node_state: S,
        /// 重複チェック用キー
        dedup_key: String,
    },
    /// 状態変更
    SetState {
        /// 対象ノード
        node_id: MapNodeId,
        /// 新しい状態
        state: S,
    },
    /// 何もしない
    Noop,
}

// ============================================================================
// ExplorationMap impl for GraphMap
// ============================================================================

impl<N, E, S> ExplorationMap for GraphMap<N, E, S>
where
    N: Debug + Clone,
    E: Debug + Clone,
    S: MapState,
{
    type Node = MapNode<N, S>;
    type Edge = MapEdge<E>;
    type Update = GraphMapUpdate<N, E, S>;
    type Result = MapApplyResult<N>;

    fn apply(&mut self, update: Self::Update) -> Self::Result {
        match update {
            GraphMapUpdate::AddChild {
                parent,
                edge_data,
                node_data,
                node_state,
                dedup_key,
            } => {
                // 重複チェック
                if self.contains_key(&dedup_key) {
                    return MapApplyResult::Ignored;
                }

                // 親ノードが存在するか確認
                let parent_depth = match self.nodes.get(&parent) {
                    Some(node) => node.depth,
                    None => {
                        return MapApplyResult::Failed {
                            node_id: parent,
                            can_retry: false,
                            reason: "Parent node not found".to_string(),
                        }
                    }
                };

                // エッジを作成
                let edge_id = self.add_edge(parent, edge_data);

                // 新しいノードを作成
                let new_node_id =
                    self.add_node(node_data.clone(), node_state, edge_id, parent_depth + 1);

                // エッジを成功としてマーク
                if let Some(edge) = self.edges.get_mut(&edge_id) {
                    edge.mark_success(new_node_id);
                }

                // インデックスに登録
                self.index_node(new_node_id, |_| dedup_key);

                MapApplyResult::NodeCreated {
                    node_id: new_node_id,
                    data: node_data,
                }
            }

            GraphMapUpdate::SetState { node_id, state } => {
                self.set_state(node_id, state);
                MapApplyResult::NodeUpdated { node_id }
            }

            GraphMapUpdate::Noop => MapApplyResult::Ignored,
        }
    }

    fn get(&self, id: MapNodeId) -> Option<&Self::Node> {
        self.nodes.get(&id)
    }

    fn get_mut(&mut self, id: MapNodeId) -> Option<&mut Self::Node> {
        self.nodes.get_mut(&id)
    }

    fn node_count(&self) -> usize {
        self.nodes.len()
    }

    fn frontiers(&self) -> Vec<MapNodeId> {
        self.expandables.iter().copied().collect()
    }
}

// ============================================================================
// GraphExplorationMap impl for GraphMap
// ============================================================================

impl<N, E, S> GraphExplorationMap for GraphMap<N, E, S>
where
    N: Debug + Clone,
    E: Debug + Clone,
    S: MapState,
{
    fn get_edge(&self, id: MapEdgeId) -> Option<&Self::Edge> {
        self.edges.get(&id)
    }

    fn outgoing_edges(&self, node: MapNodeId) -> Vec<MapEdgeId> {
        self.edges
            .values()
            .filter(|e| e.from == node)
            .map(|e| e.id)
            .collect()
    }

    fn incoming_edge(&self, node: MapNodeId) -> Option<MapEdgeId> {
        self.nodes.get(&node).and_then(|n| n.parent_edge)
    }

    fn edge_count(&self) -> usize {
        self.edges.len()
    }

    fn root(&self) -> Option<MapNodeId> {
        self.root
    }
}

// ============================================================================
// HierarchicalMap impl for GraphMap
// ============================================================================

impl<N, E, S> HierarchicalMap for GraphMap<N, E, S>
where
    N: Debug + Clone,
    E: Debug + Clone,
    S: MapState,
{
    fn parent(&self, node: MapNodeId) -> Option<MapNodeId> {
        self.nodes
            .get(&node)
            .and_then(|n| n.parent_edge)
            .and_then(|edge_id| self.edges.get(&edge_id))
            .map(|e| e.from)
    }

    fn children(&self, node: MapNodeId) -> Vec<MapNodeId> {
        self.edges
            .values()
            .filter(|e| e.from == node && e.to.is_some())
            .filter_map(|e| e.to)
            .collect()
    }

    fn depth(&self, node: MapNodeId) -> u32 {
        self.nodes.get(&node).map(|n| n.depth).unwrap_or(0)
    }
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_map_node_state() {
        assert!(MapNodeState::Open.is_open());
        assert!(!MapNodeState::Open.is_closed());
        assert!(!MapNodeState::Closed.is_open());
        assert!(MapNodeState::Closed.is_closed());
    }

    #[test]
    fn test_map_node_builder() {
        // MapNode::new は (id, data, state) の3引数
        let node = MapNode::new(MapNodeId(1), "task-1", MapNodeState::Open).with_depth(2);

        assert_eq!(node.id, MapNodeId(1));
        assert_eq!(node.data, "task-1");
        assert_eq!(node.state, MapNodeState::Open);
        assert_eq!(node.depth, 2);
        assert!(node.parent_edge.is_none()); // ルートなので親エッジなし
    }

    #[test]
    fn test_map_node_with_parent() {
        // 親エッジ付きノード
        let node = MapNode::new(MapNodeId(2), "child", MapNodeState::Open)
            .with_parent(MapEdgeId(0))
            .with_depth(1);

        assert_eq!(node.depth, 1);
        assert_eq!(node.parent_edge, Some(MapEdgeId(0)));
    }

    #[test]
    fn test_map_edge() {
        let mut edge = MapEdge::new(MapEdgeId(1), MapNodeId(0), "action-1");
        assert!(!edge.succeeded);
        assert_eq!(edge.attempts, 0);

        edge.mark_success(MapNodeId(1));
        assert!(edge.succeeded);
        assert_eq!(edge.attempts, 1);
        assert_eq!(edge.to, Some(MapNodeId(1)));
    }

    // ========================================================================
    // GraphMap Tests
    // ========================================================================

    #[test]
    fn test_graph_map_create_root() {
        // GraphMap<N, E, S> - 3つのジェネリック引数が必要
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        assert_eq!(map.node_count(), 1);
        assert_eq!(map.frontiers().len(), 1);
        assert_eq!(map.root(), Some(root));

        let node = map.get(root).unwrap();
        assert_eq!(node.data, "root");
        assert_eq!(node.state, MapNodeState::Open);
        assert_eq!(node.depth, 0);
        assert!(node.parent_edge.is_none()); // ルートは親エッジなし
    }

    #[test]
    fn test_graph_map_create_root_closed() {
        // Closed 状態でルートを作成した場合、frontiers には含まれない
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Closed);

        assert_eq!(map.node_count(), 1);
        assert!(map.frontiers().is_empty()); // Closed なのでフロンティアに含まれない
        assert_eq!(map.root(), Some(root));
    }

    /// AddChild で子ノードが追加されることを検証
    ///
    /// マップの責務:
    /// - 子ノードが作成される
    /// - エッジが作成される
    /// - 深さが親+1 になる
    /// - 親エッジが設定される
    /// - 状態に応じて frontiers に含まれる
    #[test]
    fn test_graph_map_apply_add_child() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        // AddChild で子ノードを追加
        let update = GraphMapUpdate::AddChild {
            parent: root,
            edge_data: "action-1".to_string(),
            node_data: "child-1".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "child-1".to_string(),
        };
        let result = map.apply(update);

        // 結果を確認
        match result {
            MapApplyResult::NodeCreated { node_id, data } => {
                assert_eq!(data, "child-1");

                let node = map.get(node_id).unwrap();
                assert_eq!(node.depth, 1); // 親の深さ + 1
                assert!(node.parent_edge.is_some()); // 親エッジあり
                assert_eq!(node.state, MapNodeState::Open);
            }
            _ => panic!("Expected NodeCreated, got {:?}", result),
        }

        // マップ状態を確認
        assert_eq!(map.node_count(), 2); // root + child
        assert_eq!(map.edge_count(), 1); // 1本のエッジ

        // 両方 Open なので frontiers に含まれる
        assert_eq!(map.frontiers().len(), 2);

        // 注意: マップは親を自動的に Close しない
        // それは上位レイヤーの責務
        let root_node = map.get(root).unwrap();
        assert_eq!(root_node.state, MapNodeState::Open);
    }

    /// 存在しない親に AddChild した場合、Failed が返る
    #[test]
    fn test_graph_map_add_child_parent_not_found() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        // ルートを作らずに、存在しない親を指定

        let update = GraphMapUpdate::AddChild {
            parent: MapNodeId(999), // 存在しない
            edge_data: "action".to_string(),
            node_data: "child".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "child".to_string(),
        };
        let result = map.apply(update);

        match result {
            MapApplyResult::Failed {
                node_id, reason, ..
            } => {
                assert_eq!(node_id, MapNodeId(999));
                assert!(reason.contains("not found"));
            }
            _ => panic!("Expected Failed, got {:?}", result),
        }

        // ノードもエッジも作成されない
        assert_eq!(map.node_count(), 0);
        assert_eq!(map.edge_count(), 0);
    }

    /// 重複キーで AddChild した場合、Ignored が返る
    #[test]
    fn test_graph_map_add_child_duplicate_key() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        // 1回目: 成功
        let update1 = GraphMapUpdate::AddChild {
            parent: root,
            edge_data: "action-1".to_string(),
            node_data: "child".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "unique-key".to_string(),
        };
        let result1 = map.apply(update1);
        assert!(matches!(result1, MapApplyResult::NodeCreated { .. }));

        // 2回目: 同じキーで追加 → Ignored
        let update2 = GraphMapUpdate::AddChild {
            parent: root,
            edge_data: "action-2".to_string(),
            node_data: "child-different-data".to_string(), // データは違う
            node_state: MapNodeState::Open,
            dedup_key: "unique-key".to_string(), // キーが同じ
        };
        let result2 = map.apply(update2);
        assert!(matches!(result2, MapApplyResult::Ignored));

        // ノードは2つのまま（root + child）
        assert_eq!(map.node_count(), 2);
        // エッジも1つのまま
        assert_eq!(map.edge_count(), 1);
    }

    /// SetState で状態が変わり、frontiers が更新されることを検証
    ///
    /// マップの責務:
    /// - 状態が変わる
    /// - Open → Closed で frontiers から除外される
    /// - Closed → Open で frontiers に追加される
    #[test]
    fn test_graph_map_apply_set_state() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        // 子ノードを追加
        let update = GraphMapUpdate::AddChild {
            parent: root,
            edge_data: "action-1".to_string(),
            node_data: "child".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "child".to_string(),
        };
        let child = match map.apply(update) {
            MapApplyResult::NodeCreated { node_id, .. } => node_id,
            _ => panic!("Expected NodeCreated"),
        };

        // 初期状態: 両方 Open → frontiers に2つ
        assert_eq!(map.frontiers().len(), 2);

        // child を Closed に変更
        let update = GraphMapUpdate::SetState {
            node_id: child,
            state: MapNodeState::Closed,
        };
        let result = map.apply(update);

        // 結果確認
        assert!(matches!(result, MapApplyResult::NodeUpdated { .. }));

        // child は Closed になった
        let child_node = map.get(child).unwrap();
        assert_eq!(child_node.state, MapNodeState::Closed);

        // frontiers から除外された
        assert_eq!(map.frontiers().len(), 1);
        assert!(map.frontiers().contains(&root));
        assert!(!map.frontiers().contains(&child));
    }

    /// SetState で Closed → Open に戻せることを検証
    #[test]
    fn test_graph_map_set_state_reopen() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Closed);

        // 初期状態: Closed → frontiers は空
        assert!(map.frontiers().is_empty());

        // Open に変更
        let update = GraphMapUpdate::SetState {
            node_id: root,
            state: MapNodeState::Open,
        };
        map.apply(update);

        // frontiers に追加された
        assert_eq!(map.frontiers().len(), 1);
        assert!(map.frontiers().contains(&root));
    }

    /// 階層構造（親子関係、深さ）が正しく維持されることを検証
    #[test]
    fn test_graph_map_hierarchical() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        // 2段階のノードを作成: root → node1 → node2
        let node1 = match map.apply(GraphMapUpdate::AddChild {
            parent: root,
            edge_data: "edge-1".to_string(),
            node_data: "node-1".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "node-1".to_string(),
        }) {
            MapApplyResult::NodeCreated { node_id, .. } => node_id,
            r => panic!("Expected NodeCreated, got {:?}", r),
        };

        let node2 = match map.apply(GraphMapUpdate::AddChild {
            parent: node1,
            edge_data: "edge-2".to_string(),
            node_data: "node-2".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "node-2".to_string(),
        }) {
            MapApplyResult::NodeCreated { node_id, .. } => node_id,
            r => panic!("Expected NodeCreated, got {:?}", r),
        };

        // 親子関係を確認
        assert_eq!(map.parent(node1), Some(root));
        assert_eq!(map.parent(node2), Some(node1));
        assert_eq!(map.parent(root), None); // ルートは親なし

        // 子ノードを確認
        assert_eq!(map.children(root), vec![node1]);
        assert_eq!(map.children(node1), vec![node2]);
        assert!(map.children(node2).is_empty()); // 葉ノード

        // 深さを確認
        assert_eq!(map.depth(root), 0);
        assert_eq!(map.depth(node1), 1);
        assert_eq!(map.depth(node2), 2);
    }

    // ========================================================================
    // Search API Tests (B)
    // ========================================================================

    #[test]
    fn test_find_node() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        // 子ノードを作成
        let target_id = match map.apply(GraphMapUpdate::AddChild {
            parent: root,
            edge_data: "edge".to_string(),
            node_data: "target".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "target".to_string(),
        }) {
            MapApplyResult::NodeCreated { node_id, .. } => node_id,
            r => panic!("Expected NodeCreated, got {:?}", r),
        };

        // 条件で検索
        let found = map.find_node(|n| n.data == "target");
        assert_eq!(found, Some(target_id));

        // 存在しないものは None
        let not_found = map.find_node(|n| n.data == "nonexistent");
        assert!(not_found.is_none());
    }

    #[test]
    fn test_find_nodes() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        // 複数ノードを作成
        let id1 = match map.apply(GraphMapUpdate::AddChild {
            parent: root,
            edge_data: "edge-1".to_string(),
            node_data: "match-1".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "match-1".to_string(),
        }) {
            MapApplyResult::NodeCreated { node_id, .. } => node_id,
            r => panic!("Expected NodeCreated, got {:?}", r),
        };

        let id2 = match map.apply(GraphMapUpdate::AddChild {
            parent: id1,
            edge_data: "edge-2".to_string(),
            node_data: "match-2".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "match-2".to_string(),
        }) {
            MapApplyResult::NodeCreated { node_id, .. } => node_id,
            r => panic!("Expected NodeCreated, got {:?}", r),
        };

        // "match" で始まるものを検索
        let found = map.find_nodes(|n| n.data.starts_with("match"));
        assert_eq!(found.len(), 2);
        assert!(found.contains(&id1));
        assert!(found.contains(&id2));
    }

    #[test]
    fn test_find_by_data() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        let found = map.find_by_data(&"root".to_string());
        assert_eq!(found, Some(root));

        let not_found = map.find_by_data(&"nonexistent".to_string());
        assert!(not_found.is_none());
    }

    // ========================================================================
    // Index API Tests (D)
    // ========================================================================

    #[test]
    fn test_index_basic() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("file:auth.rs".to_string(), MapNodeState::Open);

        // インデックスに登録
        map.index_node(root, |data| data.clone());

        // キーで検索
        let found = map.get_by_key(&"file:auth.rs".to_string());
        assert_eq!(found, Some(root));

        // 存在しないキー
        let not_found = map.get_by_key(&"file:other.rs".to_string());
        assert!(not_found.is_none());
    }

    #[test]
    fn test_contains_key() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("task-1".to_string(), MapNodeState::Open);
        map.index_node(root, |data| data.clone());

        assert!(map.contains_key(&"task-1".to_string()));
        assert!(!map.contains_key(&"task-2".to_string()));
    }

    #[test]
    fn test_rebuild_index() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map.create_root("root".to_string(), MapNodeState::Open);

        let child = match map.apply(GraphMapUpdate::AddChild {
            parent: root,
            edge_data: "edge".to_string(),
            node_data: "child".to_string(),
            node_state: MapNodeState::Open,
            dedup_key: "child".to_string(),
        }) {
            MapApplyResult::NodeCreated { node_id, .. } => node_id,
            r => panic!("Expected NodeCreated, got {:?}", r),
        };

        // インデックスを再構築
        map.rebuild_index(|data| data.clone());

        // 両方検索できる
        assert_eq!(map.get_by_key(&"root".to_string()), Some(root));
        assert_eq!(map.get_by_key(&"child".to_string()), Some(child));
    }

    // ========================================================================
    // Add with Dedup Tests
    // ========================================================================

    #[test]
    fn test_create_root_if_absent() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();

        // 最初の追加
        let result1 =
            map.create_root_if_absent("task-1".to_string(), MapNodeState::Open, |d| d.clone());
        assert!(result1.is_added());
        let id1 = result1.into_inner();

        // 同じキーで追加しようとすると AlreadyExists
        let result2 =
            map.create_root_if_absent("task-1".to_string(), MapNodeState::Open, |d| d.clone());
        assert!(result2.is_already_exists());
        assert_eq!(result2.into_inner(), id1);

        // 違うキーは追加できる
        let result3 =
            map.create_root_if_absent("task-2".to_string(), MapNodeState::Open, |d| d.clone());
        assert!(result3.is_added());
        assert_ne!(result3.into_inner(), id1);
    }

    #[test]
    fn test_add_child_if_absent() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map
            .create_root_if_absent("root".to_string(), MapNodeState::Open, |d| d.clone())
            .into_inner();

        // 子ノードを追加
        let result1 = map
            .add_child_if_absent(
                root,
                "edge-1".to_string(),
                "child-1".to_string(),
                MapNodeState::Open,
                |d| d.clone(),
            )
            .unwrap();
        assert!(result1.is_added());
        let child1 = result1.into_inner();

        // 同じキーで追加しようとすると AlreadyExists
        let result2 = map
            .add_child_if_absent(
                root,
                "edge-2".to_string(),
                "child-1".to_string(),
                MapNodeState::Open,
                |d| d.clone(),
            )
            .unwrap();
        assert!(result2.is_already_exists());
        assert_eq!(result2.into_inner(), child1);

        // 違うキーは追加できる
        let result3 = map
            .add_child_if_absent(
                root,
                "edge-3".to_string(),
                "child-2".to_string(),
                MapNodeState::Open,
                |d| d.clone(),
            )
            .unwrap();
        assert!(result3.is_added());
    }

    #[test]
    fn test_add_child_if_absent_parent_not_found() {
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();

        // 存在しない親に追加しようとするとエラー
        let result = map.add_child_if_absent(
            MapNodeId(999),
            "edge".to_string(),
            "child".to_string(),
            MapNodeState::Open,
            |d| d.clone(),
        );
        assert!(result.is_err());
        assert!(matches!(result.unwrap_err(), MapError::ParentNotFound(_)));
    }

    #[test]
    fn test_dedup_prevents_infinite_loop() {
        // シナリオ: Grep で同じファイルが繰り返し発見される
        let mut map: GraphMap<String, String, MapNodeState> = GraphMap::new();
        let root = map
            .create_root_if_absent("search:auth".to_string(), MapNodeState::Open, |d| d.clone())
            .into_inner();

        // Worker A: auth.rs を発見
        let result_a = map.add_child_if_absent(
            root,
            "grep".to_string(),
            "file:auth.rs".to_string(),
            MapNodeState::Open,
            |d| d.clone(),
        );
        assert!(result_a.unwrap().is_added());

        // Worker B: 同じ auth.rs を発見（重複追加されない）
        let result_b = map.add_child_if_absent(
            root,
            "grep".to_string(),
            "file:auth.rs".to_string(),
            MapNodeState::Open,
            |d| d.clone(),
        );
        assert!(result_b.unwrap().is_already_exists());

        // Worker C: 別のファイル user.rs を発見
        let result_c = map.add_child_if_absent(
            root,
            "grep".to_string(),
            "file:user.rs".to_string(),
            MapNodeState::Open,
            |d| d.clone(),
        );
        assert!(result_c.unwrap().is_added());

        // ノード数は 3 (root + auth.rs + user.rs)
        assert_eq!(map.node_count(), 3);
    }

    #[test]
    fn test_add_result_methods() {
        let added: AddResult<i32> = AddResult::Added(42);
        assert!(added.is_added());
        assert!(!added.is_already_exists());
        assert_eq!(*added.as_inner(), 42);
        assert_eq!(added.into_inner(), 42);

        let exists: AddResult<i32> = AddResult::AlreadyExists(42);
        assert!(!exists.is_added());
        assert!(exists.is_already_exists());
        assert_eq!(*exists.as_inner(), 42);
        assert_eq!(exists.into_inner(), 42);
    }
}