amazeing 0.8.1

Amazeing is a maze generator/solver application with simulation/visualization.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

use super::{Maze, Node, OPEN, Rank, Trace};
use std::collections::{BTreeMap, HashMap};

pub(crate) fn validate_node(maze: &Maze, node: Node) {
    if node.row >= maze.rows() || node.col >= maze.cols() {
        panic!(
            "Invalid node({},{}), available nodes (0,0 - {},{})",
            node.row,
            node.col,
            maze.rows() - 1,
            maze.cols() - 1
        );
    }
}

pub(crate) fn validate_node_open(maze: &Maze, node: Node) {
    if maze[node] != OPEN {
        panic!("Invalid node({},{} [{}])", node.row, node.col, maze[node])
    }
}

pub(crate) fn reconstruct_path(destination: Node, parent: &BTreeMap<Node, Node>) -> Vec<Node> {
    let mut path = Vec::<Node>::new();
    let mut current_node = destination;
    while parent.contains_key(&current_node) {
        path.push(current_node);
        current_node = parent[&current_node];
    }
    path.push(current_node);
    path.reverse();
    path
}

pub(crate) fn reconstruct_trace_path(destination: Node, parent: &BTreeMap<Node, Node>) -> Trace {
    let mut nodes = Vec::with_capacity(parent.len() + 1);
    let mut current = destination;
    nodes.push(current);
    while let Some(&next) = parent.get(&current) {
        current = next;
        nodes.push(current);
    }

    let mut path = HashMap::with_capacity(nodes.len());
    let mut rank = Rank::MAX;
    for &node in &nodes {
        path.insert(node, rank);
        rank -= 1;
    }
    path
}

pub(crate) fn validate(maze: &Maze, source: Node, destination: Node) {
    validate_node(maze, source);
    validate_node_open(maze, source);

    validate_node(maze, destination);
    validate_node_open(maze, destination);
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::maze::{Maze, NodeFactory, OPEN, UnitShape, VOID};

    #[test]
    fn reconstruct_helpers_build_expected_sequences() {
        let f = NodeFactory::new(3, 3);
        let a = f.at(0, 0).unwrap();
        let b = f.at(0, 1).unwrap();
        let c = f.at(0, 2).unwrap();

        let mut parent = BTreeMap::new();
        parent.insert(b, a);
        parent.insert(c, b);

        let path = reconstruct_path(c, &parent);
        assert_eq!(path, vec![a, b, c]);

        let trace = reconstruct_trace_path(c, &parent);
        assert_eq!(trace.get(&c), Some(&Rank::MAX));
        assert_eq!(trace.get(&b), Some(&(Rank::MAX - 1)));
        assert_eq!(trace.get(&a), Some(&(Rank::MAX - 2)));
    }

    #[test]
    fn validate_accepts_open_source_and_destination() {
        let mut maze = Maze::new(UnitShape::Square, 3, 3, VOID);
        let f = NodeFactory::new(3, 3);
        let s = f.at(0, 0).unwrap();
        let d = f.at(0, 1).unwrap();
        maze[s] = OPEN;
        maze[d] = OPEN;
        validate(&maze, s, d);
    }

    #[test]
    #[should_panic]
    fn validate_panics_for_out_of_bounds_node() {
        let maze = Maze::new(UnitShape::Square, 2, 2, OPEN);
        let bad = NodeFactory::new(3, 3).at(2, 2).unwrap();
        validate_node(&maze, bad);
    }

    #[test]
    #[should_panic]
    fn validate_node_open_panics_for_block() {
        let maze = Maze::new(UnitShape::Square, 2, 2, VOID);
        let node = NodeFactory::new(2, 2).at(1, 1).unwrap();
        validate_node_open(&maze, node);
    }
}