use std::collections::HashMap;
use std::collections::LinkedList;

use anyhow::Result;
use anyhow::anyhow;
use petgraph::algo::toposort;
use petgraph::stable_graph::StableDiGraph;

use crate::markdown_document_in_collection::MarkdownDocumentInCollection;
use crate::markdown_document_tree_node::MarkdownDocumentTreeNode;

fn find_children(
    collection_name: String,
    parent: &MarkdownDocumentInCollection,
    sorted_documents: &mut LinkedList<MarkdownDocumentInCollection>,
) -> LinkedList<MarkdownDocumentTreeNode> {
    let children = sorted_documents
        .extract_if(|document| {
            document.collection_placement.parent == Some(parent.reference.basename())
        })
        .collect::<LinkedList<_>>();

    children
        .iter()
        .map(|document| MarkdownDocumentTreeNode {
            children: find_children(collection_name.clone(), document, sorted_documents),
            collection_name: collection_name.clone(),
            reference: document.reference.clone(),
        })
        .collect::<LinkedList<MarkdownDocumentTreeNode>>()
}

#[derive(Clone, Debug)]
pub struct MarkdownDocumentCollection {
    pub documents: Vec<MarkdownDocumentInCollection>,
    pub name: String,
}

impl MarkdownDocumentCollection {
    /// Returns a list of roots
    pub fn build_hierarchy(&self) -> Result<Vec<MarkdownDocumentTreeNode>> {
        let mut sorted_documents = self.sort_by_successors()?;
        let roots = sorted_documents
            .extract_if(|document| document.collection_placement.parent.is_none())
            .collect::<LinkedList<MarkdownDocumentInCollection>>();

        Ok(roots
            .iter()
            .map(|document| MarkdownDocumentTreeNode {
                children: find_children(self.name.clone(), document, &mut sorted_documents),
                collection_name: self.name.clone(),
                reference: document.reference.clone(),
            })
            .collect::<Vec<_>>())
    }

    pub fn sort_by_successors(&self) -> Result<LinkedList<MarkdownDocumentInCollection>> {
        let mut basename_to_node = HashMap::new();
        let mut successors_graph: StableDiGraph<String, ()> = StableDiGraph::new();
        let mut node_to_document = HashMap::new();

        // First pass, register all the documents
        for document in &self.documents {
            let node = successors_graph.add_node(document.reference.basename());

            basename_to_node.insert(document.reference.basename(), node);
            node_to_document.insert(node, document.clone());
        }

        // Second pass, register edges
        for document in &self.documents {
            if let Some(after) = &document.collection_placement.after {
                successors_graph.try_add_edge(
                    *basename_to_node.get(after).ok_or(anyhow!(
                        "Unable to find node '{after}' in collection '{}'",
                        self.name
                    ))?,
                    *basename_to_node
                        .get(&document.reference.basename())
                        .ok_or(anyhow!(
                            "Unable to find node {}",
                            document.reference.basename()
                        ))?,
                    (),
                )?;
            }
        }

        match toposort(&successors_graph, None) {
            Ok(sorted_nodes) => {
                let mut sorted_documents: LinkedList<MarkdownDocumentInCollection> =
                    LinkedList::new();

                for node_id in sorted_nodes {
                    sorted_documents.push_back(
                        node_to_document
                            .get(&node_id)
                            .ok_or(anyhow!("Unable to inverse find document for node"))?
                            .clone(),
                    );
                }

                Ok(sorted_documents)
            }
            Err(_) => Err(anyhow!("Found cycle in documents successors")),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::front_matter::FrontMatter;
    use crate::front_matter::collection_placement::CollectionPlacement;
    use crate::markdown_document_reference::MarkdownDocumentReference;

    fn create_document_reference(name: &str) -> MarkdownDocumentReference {
        MarkdownDocumentReference {
            basename_path: name.into(),
            front_matter: FrontMatter::mock(name),
            generated_page_base_path: "/".to_string(),
        }
    }

    #[test]
    fn test_sort_by_successors() -> Result<()> {
        let mut collection = MarkdownDocumentCollection {
            documents: Default::default(),
            name: "my_collection".to_string(),
        };

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: None,
                name: "my_collection".to_string(),
                parent: None,
            },
            reference: create_document_reference("1"),
        });

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: Some("3".to_string()),
                name: "my_collection".to_string(),
                parent: None,
            },
            reference: create_document_reference("5"),
        });

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: Some("3".to_string()),
                name: "my_collection".to_string(),
                parent: None,
            },
            reference: create_document_reference("4"),
        });

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: Some("1".to_string()),
                name: "my_collection".to_string(),
                parent: None,
            },
            reference: create_document_reference("2"),
        });

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: Some("2".to_string()),
                name: "my_collection".to_string(),
                parent: None,
            },
            reference: create_document_reference("3"),
        });

        let sorted: Vec<String> = collection
            .sort_by_successors()?
            .iter()
            .map(|document| document.reference.front_matter.title.clone())
            .collect();

        assert_eq!(sorted, ["1", "2", "3", "4", "5"]);

        Ok(())
    }

    #[test]
    fn test_hierarchy() -> Result<()> {
        let mut collection = MarkdownDocumentCollection {
            documents: Default::default(),
            name: "my_collection".to_string(),
        };

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: None,
                name: "my_collection".to_string(),
                parent: None,
            },
            reference: create_document_reference("1"),
        });

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: Some("3".to_string()),
                name: "my_collection".to_string(),
                parent: Some("3".to_string()),
            },
            reference: create_document_reference("5"),
        });

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: Some("3".to_string()),
                name: "my_collection".to_string(),
                parent: Some("3".to_string()),
            },
            reference: create_document_reference("4"),
        });

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: Some("1".to_string()),
                name: "my_collection".to_string(),
                parent: None,
            },
            reference: create_document_reference("2"),
        });

        collection.documents.push(MarkdownDocumentInCollection {
            collection_placement: CollectionPlacement {
                after: Some("2".to_string()),
                name: "my_collection".to_string(),
                parent: Some("1".to_string()),
            },
            reference: create_document_reference("3"),
        });

        let hierarchy = collection.build_hierarchy()?;

        // println!("hierarchy: {hierarchy:#?}");
        // assert!(false);

        let sorted: Vec<String> = hierarchy
            .iter()
            .map(|node| node.reference.front_matter.title.clone())
            .collect();

        assert_eq!(sorted, ["1", "2"]);

        Ok(())
    }
}
