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

use direction::Direction;
use grid_2d::*;
use search::*;
use std::slice;

pub(crate) trait PathNode {
    fn from_parent(&self) -> Option<Direction>;
    fn coord(&self) -> Coord;
}

pub(crate) fn make_path_all_adjacent<N: PathNode>(
    node_grid: &Grid<N>,
    goal_index: usize,
    path: &mut Vec<Direction>,
) {
    path.clear();
    let mut index = goal_index;
    while let Some(from_parent) = node_grid[index].from_parent() {
        path.push(from_parent);
        let offset = from_parent.opposite().coord();
        index = node_grid
            .index_of_coord(node_grid[index].coord() + offset)
            .expect("Invalid search state");
    }
    path.reverse();
}

pub(crate) fn make_path_jump_points<Cost>(
    node_grid: &Grid<SearchNode<Cost>>,
    goal_coord: Coord,
    seq: u64,
    path: &mut Vec<Direction>,
) {
    path.clear();

    let mut node = node_grid.get(goal_coord).expect("Invalid search state");

    loop {
        let from_parent = if let Some(from_parent) = node.from_parent() {
            from_parent
        } else {
            break;
        };

        path.push(from_parent);

        let step = from_parent.opposite().coord();
        let mut coord = node.coord;
        loop {
            coord += step;
            let next_node = node_grid.get(coord).expect("Invalid search state");
            if next_node.seen == seq {
                node = next_node;
                break;
            }

            path.push(from_parent);
        }
    }

    path.reverse();
}

pub struct PathWalk<'a> {
    current_coord: Coord,
    directions: slice::Iter<'a, Direction>,
}

impl<'a> PathWalk<'a> {
    pub fn new(start: Coord, path: &'a Vec<Direction>) -> Self {
        Self {
            current_coord: start,
            directions: path.iter(),
        }
    }
}

impl<'a> Iterator for PathWalk<'a> {
    type Item = (Coord, Direction);
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(&direction) = self.directions.next() {
            let offset: Coord = direction.coord();
            self.current_coord = self.current_coord + offset;
            Some((self.current_coord, direction))
        } else {
            None
        }
    }
}