#[test]
fn ut_ungraph_manual_bfs() {
    use gdsl::ungraph::*;
    use std::collections::{HashSet, VecDeque};

    let g = vec![
        Node::new(0, ()),
        Node::new(1, ()),
        Node::new(2, ()),
        Node::new(3, ()),
        Node::new(4, ()),
        Node::new(5, ()),
    ];

    g[0].connect(&g[1], ());
    g[0].connect(&g[2], ());
    g[0].connect(&g[3], ());
    g[1].connect(&g[4], ());
    g[2].connect(&g[5], ());
    g[3].connect(&g[4], ());
    g[3].connect(&g[5], ());

    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();

    queue.push_back(g[0].clone());
    visited.insert(g[0].key().clone());

    while let Some(node) = queue.pop_front() {
        for Edge(_, v, _) in &node {
            if !visited.contains(v.key()) {
                if v == g[4] {
                    return;
                }
                visited.insert(v.key().clone());
                queue.push_back(v);
            }
        }
    }
    panic!();
}

#[test]
fn ut_ungraph_bfs() {
    use gdsl::*;

    let g = ungraph![
        (usize)
        (0) => [1, 2, 3]
        (1) => [3]
        (2) => [4]
        (3) => [2]
        (4) => []
    ];

    let path = g[0].bfs().target(&4).search_path().unwrap().to_vec_nodes();

    assert!(path[0] == g[0]);
    assert!(path[1] == g[2]);
    assert!(path[2] == g[4]);
}

#[test]
fn ut_ungraph() {
    use gdsl::ungraph::*;

    let a = Node::new(0x1, "A");
    let b = Node::new(0x2, "B");
    let c = Node::new(0x4, "C");

    a.connect(&b, 0.42);
    a.connect(&c, 1.7);
    b.connect(&c, 0.09);
    c.connect(&b, 12.9);

    let Edge(u, v, e) = a.iter().next().unwrap();

    assert!(u == a);
    assert!(v == b);
    assert!(e == 0.42);
}

#[test]
fn ut_ungraph_new() {
    use gdsl::ungraph::*;

    let n1 = Node::<i32, char, ()>::new(1, 'A');

    assert!(*n1.key() == 1);
    assert!(*n1.value() == 'A');
}

#[test]
fn ut_ungraph_connect() {
    use gdsl::ungraph::*;

    let n1 = Node::new(1, ());
    let n2 = Node::new(2, ());

    n1.connect(&n2, 4.20);

    assert!(n1.is_connected(n2.key()));
}

#[test]
fn ut_ungraph_try_connect() {
    use gdsl::ungraph::*;

    let n1 = Node::new(1, ());
    let n2 = Node::new(2, ());

    match n1.try_connect(&n2, ()) {
        Ok(_) => assert!(n1.is_connected(n2.key())),
        Err(_) => panic!("n1 should be connected to n2"),
    }

    match n1.try_connect(&n2, ()) {
        Ok(_) => panic!("n1 should be connected to n2"),
        Err(_) => assert!(n1.is_connected(n2.key())),
    }
}

#[test]
fn ut_ungraph_disconnect() {
    use gdsl::ungraph::*;

    let n1 = Node::new(1, ());
    let n2 = Node::new(2, ());

    n1.connect(&n2, ());

    assert!(n1.is_connected(n2.key()));

    if n1.disconnect(n2.key()).is_err() {
        panic!("n1 should be connected to n2");
    }

    assert!(!n1.is_connected(n2.key()));
}

#[test]
fn ut_ungraph_isolate() {
    use gdsl::ungraph::*;

    let n1 = Node::new(1, ());
    let n2 = Node::new(2, ());
    let n3 = Node::new(3, ());
    let n4 = Node::new(4, ());

    n1.connect(&n2, ());
    n1.connect(&n3, ());
    n2.connect(&n1, ());
    n3.connect(&n1, ());
    n4.connect(&n3, ());
    n3.connect(&n2, ());

    n1.isolate();

    assert!(n3.is_connected(n2.key()));
    assert!(n4.is_connected(n3.key()));
    assert!(!n1.is_connected(n2.key()));
    assert!(!n1.is_connected(n3.key()));
    assert!(n1.is_orphan());
}

// TEST Dfs

#[test]
fn ut_ungraph_dfs_find_1() {
    use gdsl::*;

    let g = ungraph![
        (usize)
        (0) => [1, 2, 3]
        (1) => [3]
        (2) => [4]
        (3) => [2, 0]
        (4) => []
    ];

    let target = g[0].dfs().target(&4).search().unwrap();

    let source = g[4].dfs().target(&0).search().unwrap();

    assert!(target == g[4]);
    assert!(source == g[0]);
}

#[test]
fn ut_ungraph_dfs_cycle_1() {
    use gdsl::*;

    let g = ungraph![
        (usize)
        (0) => [0, 2, 3]
        (1) => [3]
        (2) => [4]
        (3) => [2, 0]
        (4) => []
    ];

    let cycle = g[0].dfs().search_cycle().unwrap().to_vec_nodes();

    assert!(cycle[0] == g[0]);
    assert!(cycle[1] == g[0]);
}

#[test]
fn ut_ungraph_dfs_cycle_2() {
    use gdsl::*;

    let g = ungraph![
        (usize)
        (0) => [1, 2, 3]
        (1) => [3]
        (2) => [4]
        (3) => [2, 0]
        (4) => []
    ];

    let cycle = g[0].dfs().search_cycle().unwrap().to_vec_nodes();

    assert!(cycle[0] == g[0]);
    assert!(cycle.last().unwrap() == &g[0]);
}

// TEST Bfs

#[test]
fn ut_ungraph_bfs_find_1() {
    use gdsl::*;

    let g = ungraph![
        (usize)
        (0) => [1, 2, 3]
        (1) => [3]
        (2) => [4]
        (3) => [2, 0]
        (4) => []
    ];

    let target = g[0].bfs().target(&4).search().unwrap();

    let source = g[4].bfs().target(&0).search().unwrap();

    assert!(target == g[4]);
    assert!(source == g[0]);
}

#[test]
fn ut_ungraph_bfs_cycle_1() {
    use gdsl::*;

    let g = ungraph![
        (usize)
        (0) => [0, 2, 3]
        (1) => [3]
        (2) => [4]
        (3) => [2, 0]
        (4) => []
    ];

    let cycle = g[0].bfs().search_cycle().unwrap().to_vec_nodes();

    assert!(cycle[0] == g[0]);
    assert!(cycle[1] == g[0]);
}

#[test]
fn ut_ungraph_bfs_cycle_2() {
    use gdsl::*;

    let g = ungraph![
        (usize)
        (0) => [1, 2, 3]
        (1) => [3]
        (2) => [4]
        (3) => [2, 0]
        (4) => []
    ];

    let cycle = g[0].bfs().search_cycle().unwrap().to_vec_nodes();

    assert!(cycle[0] == g[0]);
    assert!(cycle.last().unwrap() == &g[0]);
}

#[test]
fn ut_ungraph_sizes() {
    use gdsl::ungraph::*;

    type N1 = Node;
    type N2 = Node<usize>;
    type N3 = Node<usize, usize>;
    type N4 = Node<usize, usize, usize>;

    let n1 = N1::new(1, ());
    let n2 = N2::new(2, ());
    let n3 = N3::new(3, 42);
    let n4 = N4::new(4, 42);

    assert!(n1.sizeof() == 72);
    assert!(n2.sizeof() == 72);
    assert!(n3.sizeof() == 80);
    assert!(n4.sizeof() == 80);

    let n1t1 = N1::new(1, ());
    let n1t2 = N1::new(1, ());
    let n1t3 = N1::new(1, ());

    n1.connect(&n1t1, ());
    n1.connect(&n1t2, ());
    n1.connect(&n1t3, ());

    assert!(n1.sizeof() == 96);
    assert!(n1t1.sizeof() == 73);
}

#[test]
fn ut_ungraph_dijkstra() {
    use gdsl::ungraph::*;
    use gdsl::*;
    use std::cell::Cell;

    // https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
    let g = ungraph![
        (char, Cell<u64>) => [u64]
        ('A', Cell::new(u64::MAX)) => [ ('B', 4), ('H', 8) ]
        ('B', Cell::new(u64::MAX)) => [ ('A', 4), ('H', 11), ('C', 8) ]
        ('C', Cell::new(u64::MAX)) => [ ('B', 8), ('C', 2), ('F', 4), ('D', 7) ]
        ('D', Cell::new(u64::MAX)) => [ ('C', 7), ('F', 14), ('E', 9) ]
        ('E', Cell::new(u64::MAX)) => [ ('D', 9), ('F', 10) ]
        ('F', Cell::new(u64::MAX)) => [ ('G', 2), ('C', 4), ('D', 14), ('E', 10) ]
        ('G', Cell::new(u64::MAX)) => [ ('H', 1), ('I', 6), ('F', 2) ]
        ('H', Cell::new(u64::MAX)) => [ ('A', 8), ('B', 11), ('I', 7), ('G', 1) ]
        ('I', Cell::new(u64::MAX)) => [ ('H', 7), ('C', 2), ('G', 6) ]
    ];

    g['A'].set(0);
    g['A']
        .pfs()
        .for_each(&mut |Edge(u, v, e)| {
            if v.get() > u.get() + e {
                v.set(u.get() + e);
            }
        })
        .search();

    assert!(g['A'].get() == 0);
    assert!(g['B'].get() == 4);
    assert!(g['C'].get() == 12);
    assert!(g['D'].get() == 19);
    assert!(g['E'].get() == 21);
    assert!(g['F'].get() == 11);
    assert!(g['G'].get() == 9);
    assert!(g['H'].get() == 8);
    assert!(g['I'].get() == 14);
}