//! Test breadth-first search algorithm variations.
use cnetworks::*;

#[test]
fn test_path_distance() {
    let mut net = Network::new(3, Model::None, Weight::default());
    assert_eq!(bfs::distance(&net, 0, 0).unwrap(), Some(0));

    net.link(0, 1).unwrap();
    net.link(1, 2).unwrap();
    assert_eq!(
        bfs::distance(&net, 0, 100).unwrap_err(),
        cn::Err::NoSuchNode(100)
    );
    assert_eq!(bfs::distance(&net, 0, 2).unwrap(), Some(2));

    net.link(0, 2).unwrap();
    assert_eq!(bfs::distance(&net, 0, 2).unwrap(), Some(1));

    net.unlink(0, 1).unwrap();
    net.unlink(0, 2).unwrap();
    assert_eq!(bfs::distance(&net, 0, 2).unwrap(), None);
}

#[test]
fn test_path_distance_many() {
    let mut net = Network::new(5, Model::None, Weight::default());
    assert_eq!(
        bfs::distance_many(&net, 0, &[1, 100]).unwrap_err(),
        cn::Err::NoSuchNode(100)
    );

    net.link(0, 1).unwrap();
    net.link(1, 2).unwrap();
    net.link(1, 3).unwrap();
    net.link(2, 3).unwrap();

    assert_eq!(
        bfs::distance_many(&net, 0, &[1, 2, 3]).unwrap(),
        vec![(1, 1), (2, 2), (3, 2)]
            .into_iter()
            .collect(),
    );
    assert_eq!(
        bfs::path_many(&net, 0, &[1, 2, 3])
            .unwrap()
            .iter()
            .map(|(idx, p)| { (idx, p.visited()) }).collect::<cn::IndexMap<_, _>>(),
        vec![
            (1, Some(vec![1, 0])),
            (2, Some(vec![2, 1, 0])),
            (3, Some(vec![3, 1, 0]))
        ]
        .into_iter()
        .collect::<cn::IndexMap<_, _>>(),
    );

    net.unlink(1, 2).unwrap();
    assert_eq!(
        bfs::path_many(&net, 0, &[1, 2, 3])
            .unwrap()
            .iter()
            .map(|(idx, p)| { (idx, p.visited()) }).collect::<cn::IndexMap<_, _>>(),
        vec![
            (1, Some(vec![1, 0])),
            (2, Some(vec![2, 3, 1, 0])),
            (3, Some(vec![3, 1, 0])),
        ]
        .into_iter()
        .collect::<cn::IndexMap<_, _>>(),
    );
    assert_eq!(
        bfs::distance_many(&net, 0, &[1, 2, 3]).unwrap(),
        vec![(1, 1), (2, 3), (3, 2)]
            .into_iter()
            .collect(),
    );
}

#[test]
fn test_traverse() {
    let mut net = Network::new(5, Model::None, Weight::default());
    net.link(0, 1).unwrap();
    net.link(1, 2).unwrap();
    net.link(1, 3).unwrap();
    net.link(2, 3).unwrap();
    net.link(2, 4).unwrap();

    let mut visited: Vec<usize> = Vec::new();

    assert!(bfs::traverse(&net, 0, |current, _, _, _| {
        visited.push(current);
        bfs::CONTINUE
    })
    .is_ok());
    assert_eq!(visited, vec![0, 1, 2, 3, 4]);
}

#[test]
fn test_tree() {
    let mut net = Network::new(6, Model::None, Weight::default());

    for i in [1, 2, 3] {
        net.link(0, i).unwrap();
    }
    for i in [1, 2, 4, 5] {
        net.link(3, i).unwrap();
    }
    net.link(4, 5).unwrap();

    let tree = bfs::tree(&net, 0).unwrap();
    for i in tree.nodes() {
        let mut links = tree.links_of(i).unwrap().keys().cloned().collect::<Vec<usize>>();
        links.sort_unstable();
        match i {
            0 => assert_eq!(links, vec![1, 2, 3]),
            1 | 2 => assert_eq!(links, vec![0]),
            3 => assert_eq!(links, vec![0, 4, 5]),
            4 | 5 => assert_eq!(links, vec![3]),
            _ => panic!("There should not be a node with index {}", i),
        }
    }
}

#[test]
fn test_tree_active() {
    let mut net = Network::new(10, Model::None, Weight::default());
    net.link(0, 1).unwrap();
    net.link(1, 2).unwrap();
    // This branches out
    net.link(2, 7).unwrap();
    net.link(2, 8).unwrap();

    net.link(0, 3).unwrap();
    net.link(3, 4).unwrap();

    // This is a non-branch
    net.link(0, 5).unwrap();
    net.link(5, 6).unwrap();
    let mut tree = bfs::tree_active(&net, 0, &[2, 4, 7, 8]).unwrap();

    assert_eq!(
        tree.nodes().into_iter().collect::<cn::VecSet>(),
        vec![0, 1, 2, 3, 4, 7, 8].into_iter().collect::<cn::VecSet>()
    );

    // Try to remove the paths that SHOULD exist
    assert!(tree.unlink(0, 1).unwrap().is_some());
    assert!(tree.unlink(1, 2).unwrap().is_some());
    assert!(tree.unlink(2, 7).unwrap().is_some());
    assert!(tree.unlink(2, 8).unwrap().is_some());
    assert!(tree.unlink(0, 3).unwrap().is_some());
    assert!(tree.unlink(3, 4).unwrap().is_some());
    assert_eq!(tree.links().count(), 0);
}

#[test]
fn test_explore() {
    let mut net = Network::new(3, Model::None, Weight::default());
    net.link(0, 1).unwrap();
    net.link(1, 2).unwrap();
    for node in [0, 1, 2] {
        assert_eq!(
            bfs::explore(&net, node).unwrap(),
            (vec![0, 1, 2].into_iter().collect(), cn::VecSet::default())
        );
    }
    net.unlink(1, 2).unwrap();
    for node in [0, 1] {
        assert_eq!(
            bfs::explore(&net, node).unwrap(),
            (
                vec![0, 1].into_iter().collect(),
                vec![2].into_iter().collect()
            )
        );
    }
    assert_eq!(
        bfs::explore(&net, 2).unwrap(),
        (
            vec![2].into_iter().collect(),
            vec![1, 0].into_iter().collect()
        )
    );
}