分厚い参考書を1ページ目から読むとなぜ挫折するのか？——知識の木構造（AST）と認知心理学による「逆算学習」の仕組み

use std::collections::{BTreeMap, BTreeSet, VecDeque};

/// 知識ノード（概念単位）の定義
#[derive(Debug, Clone)]
pub struct KnowledgeNode {
    pub id: u32,
    pub title: String,
    pub estimated_minutes: u32,
    pub stability_days: f64,
}

/// 知識依存グラフ（DAG: Prerequisite -> Dependent）
#[derive(Debug, Default)]
pub struct KnowledgeDag {
    pub nodes: BTreeMap<u32, KnowledgeNode>,
    pub forward_edges: BTreeMap<u32, BTreeSet<u32>>, // u -> v (uはvの前提)
    pub reverse_edges: BTreeMap<u32, BTreeSet<u32>>, // v -> u (vに必要な前提u)
}

impl KnowledgeDag {
    pub fn add_node(&mut self, node: KnowledgeNode) {
        self.nodes.insert(node.id, node);
    }

    /// 前提関係 `prerequisite_id -> target_id` を追加する
    pub fn add_dependency(&mut self, prerequisite_id: u32, target_id: u32) {
        self.forward_edges.entry(prerequisite_id).or_default().insert(target_id);
        self.reverse_edges.entry(target_id).or_default().insert(prerequisite_id);
    }

    /// 目標ノード集合 `goal_ids` から逆方向BFSを行い、最小限必要な前提ノード集合（先祖閉包）を抽出する
    pub fn extract_minimal_ancestor_closure(&self, goal_ids: &[u32]) -> BTreeSet<u32> {
        let mut required = BTreeSet::new();
        let mut queue = VecDeque::new();

        for &g in goal_ids {
            if self.nodes.contains_key(&g) && required.insert(g) {
                queue.push_back(g);
            }
        }

        while let Some(curr) = queue.pop_front() {
            if let Some(prereqs) = self.reverse_edges.get(&curr) {
                for &p in prereqs {
                    if required.insert(p) {
                        queue.push_back(p);
                    }
                }
            }
        }
        required
    }

    /// 抽出された最小部分グラフに対し、Kahnのアルゴリズムで最適な学習順序（トポロジカル順序）を算出する
    pub fn compute_optimal_study_plan(&self, goal_ids: &[u32]) -> Result<Vec<u32>, &'static str> {
        let closure = self.extract_minimal_ancestor_closure(goal_ids);
        let mut in_degree: BTreeMap<u32, usize> = BTreeMap::new();

        for &u in &closure {
            in_degree.insert(u, 0);
        }
        for &u in &closure {
            if let Some(deps) = self.forward_edges.get(&u) {
                for &v in deps {
                    if closure.contains(&v) {
                        *in_degree.entry(v).or_insert(0) += 1;
                    }
                }
            }
        }

        let mut queue: VecDeque<u32> = in_degree
            .iter()
            .filter(|&(_, &deg)| deg == 0)
            .map(|(&id, _)| id)
            .collect();

        let mut order = Vec::with_capacity(closure.len());
        while let Some(u) = queue.pop_front() {
            order.push(u);
            if let Some(deps) = self.forward_edges.get(&u) {
                for &v in deps {
                    if let Some(deg) = in_degree.get_mut(&v) {
                        *deg -= 1;
                        if *deg == 0 {
                            queue.push_back(v);
                        }
                    }
                }
            }
        }

        if order.len() != closure.len() {
            return Err("Cycle detected in knowledge graph");
        }
        Ok(order)
    }

    /// 目標記憶保持率 `target_retention` (例: 0.82) を維持するための次回検索練習までの最適日数
    pub fn next_retrieval_interval_days(stability_days: f64, target_retention: f64) -> f64 {
        let clamped_r = target_retention.clamp(0.50, 0.99);
        -stability_days * clamped_r.ln()
    }
}

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

    #[test]
    fn test_reverse_ast_prunes_unnecessary_chapters() {
        let mut dag = KnowledgeDag::default();
        dag.add_node(KnowledgeNode { id: 1, title: "基礎概念A".into(), estimated_minutes: 15, stability_days: 2.0 });
        dag.add_node(KnowledgeNode { id: 2, title: "不要な歴史的経緯B".into(), estimated_minutes: 60, stability_days: 2.0 });
        dag.add_node(KnowledgeNode { id: 3, title: "中核ルールC".into(), estimated_minutes: 20, stability_days: 3.0 });
        dag.add_node(KnowledgeNode { id: 4, title: "実務ゴールD".into(), estimated_minutes: 25, stability_days: 5.0 });

        dag.add_dependency(1, 3);
        dag.add_dependency(3, 4);
        // ノード2（60分）はゴール4に依存しない枝葉

        let plan = dag.compute_optimal_study_plan(&[4]).unwrap();
        assert_eq!(plan, vec![1, 3, 4]);
    }
}