use crate::DbError;
use crate::StorageData;
use crate::collections::bit_set::BitSet;
use crate::graph::GraphData;
use crate::graph::GraphImpl;
use crate::graph::GraphIndex;
use crate::storage::Storage;
use std::cmp::Ordering;

pub trait PathSearchHandler {
    fn process(&self, index: GraphIndex, distance: u64) -> Result<(u64, bool), DbError>;
}

#[derive(Clone)]
struct Path {
    elements: Vec<(GraphIndex, bool)>,
    cost: u64,
}

pub struct PathSearch<'a, D, Data, Handler>
where
    Data: GraphData<D>,
    D: StorageData,
    Handler: PathSearchHandler,
{
    current_path: Path,
    destination: GraphIndex,
    graph: &'a GraphImpl<D, Data>,
    storage: &'a Storage<D>,
    handler: Handler,
    paths: Vec<Path>,
    result: Vec<(GraphIndex, bool)>,
    visited: BitSet,
}

impl<'a, D, Data, Handler> PathSearch<'a, D, Data, Handler>
where
    Data: GraphData<D>,
    D: StorageData,
    Handler: PathSearchHandler,
{
    pub fn new(
        graph: &'a GraphImpl<D, Data>,
        storage: &'a Storage<D>,
        from: GraphIndex,
        to: GraphIndex,
        handler: Handler,
    ) -> Self {
        let add = handler.process(from, 0).unwrap_or_default();

        Self {
            current_path: Path {
                elements: vec![],
                cost: 0,
            },
            destination: to,
            graph,
            storage,
            handler,
            paths: vec![Path {
                elements: vec![(from, add.1)],
                cost: 0,
            }],
            result: vec![],
            visited: BitSet::new(),
        }
    }

    pub fn search(&mut self) -> Result<Vec<GraphIndex>, DbError> {
        while !self.is_finished() {
            self.sort_paths();
            self.process_last_path()?;
        }

        Ok(self.result.iter().filter(|e| e.1).map(|e| e.0).collect())
    }

    fn expand_edge(
        &mut self,
        mut path: Path,
        index: GraphIndex,
        node_index: GraphIndex,
    ) -> Result<(), DbError> {
        let cost = self
            .handler
            .process(index, self.current_path.elements.len() as u64 + 1)?;

        if cost.0 != 0 && !self.visited.value(node_index.as_u64()) {
            path.elements.push((index, cost.1));
            path.cost += cost.0;
            self.expand_node(path, node_index)?;
        }

        Ok(())
    }

    fn expand_node(&mut self, mut path: Path, index: GraphIndex) -> Result<(), DbError> {
        let cost = self
            .handler
            .process(index, self.current_path.elements.len() as u64 + 1)?;

        if cost.0 != 0 {
            path.elements.push((index, cost.1));
            path.cost += cost.0;
            self.paths.push(path);
        }

        Ok(())
    }

    fn expand(&mut self, index: GraphIndex) -> Result<(), DbError> {
        let node = self
            .graph
            .node(self.storage, index)
            .expect("unexpected invalid node index");
        for edge in node.edge_iter_from() {
            self.expand_edge(self.current_path.clone(), edge.index(), edge.index_to())?;
        }

        Ok(())
    }

    fn is_finished(&self) -> bool {
        self.paths.is_empty() || !self.result.is_empty()
    }

    fn process_path(&mut self) -> Result<(), DbError> {
        let index = self
            .current_path
            .elements
            .last()
            .map_or(GraphIndex::default(), |index| index.0);
        self.process_index(index)
    }

    fn process_index(&mut self, index: GraphIndex) -> Result<(), DbError> {
        if !self.visited.value(index.as_u64()) {
            if index.0 == self.destination.0 {
                std::mem::swap(&mut self.result, &mut self.current_path.elements);
            } else {
                self.visited.set(index.as_u64());
                self.expand(index)?;
            }
        }

        Ok(())
    }

    fn process_last_path(&mut self) -> Result<(), DbError> {
        self.current_path = self.paths.pop().unwrap_or(Path {
            elements: vec![],
            cost: 0,
        });
        self.process_path()
    }

    fn sort_paths(&mut self) {
        self.paths.sort_by(|left, right| {
            let ordering = left.cost.cmp(&right.cost);

            if ordering == Ordering::Equal {
                return left.elements.len().cmp(&right.elements.len()).reverse();
            }

            ordering.reverse()
        });
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::graph::DbGraph;
    use crate::graph_search::GraphSearch;
    use crate::storage::file_storage::FileStorage;
    use crate::test_utilities::test_file::TestFile;

    struct Handler {
        pub processor: fn(GraphIndex, u64) -> (u64, bool),
    }

    impl Default for Handler {
        fn default() -> Self {
            Self {
                processor: |_index: GraphIndex, _distance: u64| (1_u64, true),
            }
        }
    }

    impl PathSearchHandler for Handler {
        fn process(&self, index: GraphIndex, distance: u64) -> Result<(u64, bool), DbError> {
            Ok((self.processor)(index, distance))
        }
    }

    #[test]
    fn circular_path() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();
        let node = graph.insert_node(&mut storage).unwrap();
        let _edge = graph.insert_edge(&mut storage, node, node).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(node, node, Handler::default());

        assert_eq!(result, Ok(vec![]));
    }

    #[test]
    fn empty_graph() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let graph = DbGraph::new(&mut storage).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(
            GraphIndex::default(),
            GraphIndex::default(),
            Handler::default(),
        );

        assert_eq!(result, Ok(vec![]));
    }

    #[test]
    fn multi_edge_path() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();

        let node1 = graph.insert_node(&mut storage).unwrap();
        let node2 = graph.insert_node(&mut storage).unwrap();
        let node3 = graph.insert_node(&mut storage).unwrap();

        let edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
        let _edge2 = graph.insert_edge(&mut storage, node1, node2).unwrap();

        let edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();
        let _edge4 = graph.insert_edge(&mut storage, node2, node3).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(node1, node3, Handler::default());

        assert_eq!(result, Ok(vec![node1, edge1, node2, edge3, node3]));
    }

    #[test]
    fn origin_is_destination() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();
        let node = graph.insert_node(&mut storage).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(node, node, Handler::default());

        assert_eq!(result, Ok(vec![]));
    }

    #[test]
    fn short_circuit_path() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();

        let node1 = graph.insert_node(&mut storage).unwrap();
        let node2 = graph.insert_node(&mut storage).unwrap();
        let node3 = graph.insert_node(&mut storage).unwrap();

        let edge1 = graph.insert_edge(&mut storage, node1, node3).unwrap();
        let _edge2 = graph.insert_edge(&mut storage, node1, node2).unwrap();
        let _edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(node1, node3, Handler::default());

        assert_eq!(result, Ok(vec![node1, edge1, node3]));
    }

    #[test]
    fn single_path() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();

        let node1 = graph.insert_node(&mut storage).unwrap();
        let node2 = graph.insert_node(&mut storage).unwrap();
        let node3 = graph.insert_node(&mut storage).unwrap();

        let edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
        let edge2 = graph.insert_edge(&mut storage, node2, node3).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(node1, node3, Handler::default());

        assert_eq!(result, Ok(vec![node1, edge1, node2, edge2, node3]));
    }

    #[test]
    fn skip_short_circuit_path() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();

        let node1 = graph.insert_node(&mut storage).unwrap();
        let node2 = graph.insert_node(&mut storage).unwrap();
        let node3 = graph.insert_node(&mut storage).unwrap();

        let _edge1 = graph.insert_edge(&mut storage, node1, node3).unwrap();
        let edge2 = graph.insert_edge(&mut storage, node1, node2).unwrap();
        let edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(
            node1,
            node3,
            Handler {
                processor: |index: GraphIndex, _distance: u64| {
                    if index.0 == -4 {
                        return (0, true);
                    }

                    (1, true)
                },
            },
        );

        assert_eq!(result, Ok(vec![node1, edge2, node2, edge3, node3]));
    }

    #[test]
    fn unconnected() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();

        let node1 = graph.insert_node(&mut storage).unwrap();
        let node2 = graph.insert_node(&mut storage).unwrap();
        let node3 = graph.insert_node(&mut storage).unwrap();

        let _edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(node1, node3, Handler::default());

        assert_eq!(result, Ok(vec![]));
    }

    #[test]
    fn filtered_nodes() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();

        let node1 = graph.insert_node(&mut storage).unwrap();
        let node2 = graph.insert_node(&mut storage).unwrap();
        let node3 = graph.insert_node(&mut storage).unwrap();

        let _edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
        let _edge2 = graph.insert_edge(&mut storage, node2, node2).unwrap();
        let _edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(
            node1,
            node3,
            Handler {
                processor: |index: GraphIndex, _distance: u64| (1, index.is_node()),
            },
        );

        assert_eq!(result, Ok(vec![node1, node2, node3]));
    }

    #[test]
    fn filtered_edges() {
        let test_file = TestFile::new();
        let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
        let mut graph = DbGraph::new(&mut storage).unwrap();

        let node1 = graph.insert_node(&mut storage).unwrap();
        let node2 = graph.insert_node(&mut storage).unwrap();
        let node3 = graph.insert_node(&mut storage).unwrap();

        let edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
        let _edge2 = graph.insert_edge(&mut storage, node2, node2).unwrap();
        let edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();

        let result = GraphSearch::from((&graph, &storage)).path(
            node1,
            node3,
            Handler {
                processor: |index: GraphIndex, _distance: u64| (1, index.is_edge()),
            },
        );

        assert_eq!(result, Ok(vec![edge1, edge3]));
    }
}
