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

use num::traits::Zero;
use grid_2d::*;
use direction::*;

#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
pub struct DijkstraMapCell<Cost> {
    pub(crate) seen: u64,
    pub(crate) visited: u64,
    pub(crate) cost: Cost,
    pub(crate) direction: Direction,
    pub(crate) coord: Coord,
}

impl<Cost: Zero> DijkstraMapCell<Cost> {
    fn new(coord: Coord) -> Self {
        Self {
            seen: 0,
            visited: 0,
            cost: Zero::zero(),
            direction: Direction::North,
            coord,
        }
    }
}

impl<Cost> DijkstraMapCell<Cost>
where
    Cost: Copy,
{
    pub fn cost(&self) -> Cost {
        self.cost
    }
    pub fn direction(&self) -> Direction {
        self.direction
    }
}

#[derive(Debug, Clone)]
pub enum DijkstraMapEntry<'a, Cost: 'a> {
    Origin,
    Unvisited,
    Outside,
    Cell(&'a DijkstraMapCell<Cost>),
}

impl<'a, Cost> DijkstraMapEntry<'a, Cost> {
    pub fn cell(self) -> Option<&'a DijkstraMapCell<Cost>> {
        match self {
            DijkstraMapEntry::Cell(c) => Some(c),
            _ => None,
        }
    }
    pub fn is_origin(self) -> bool {
        match self {
            DijkstraMapEntry::Origin => true,
            _ => false,
        }
    }
    pub fn is_unvisited(self) -> bool {
        match self {
            DijkstraMapEntry::Unvisited => true,
            _ => false,
        }
    }
    pub fn is_outside(self) -> bool {
        match self {
            DijkstraMapEntry::Outside => true,
            _ => false,
        }
    }
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct DijkstraMap<Cost> {
    pub(crate) seq: u64,
    pub(crate) grid: Grid<DijkstraMapCell<Cost>>,
    pub(crate) origin: Coord,
}

impl<Cost> DijkstraMap<Cost>
where
    Cost: Zero + Copy,
{
    pub fn new(width: u32, height: u32) -> Self {
        Self {
            seq: 1,
            grid: Grid::new_from_fn(width, height, DijkstraMapCell::new),
            origin: Coord::new(0, 0),
        }
    }

    pub fn get(&self, coord: Coord) -> DijkstraMapEntry<Cost> {
        if let Some(cell) = self.grid.get(coord) {
            if cell.seen == self.seq {
                if coord == self.origin {
                    DijkstraMapEntry::Origin
                } else {
                    DijkstraMapEntry::Cell(cell)
                }
            } else {
                DijkstraMapEntry::Unvisited
            }
        } else {
            DijkstraMapEntry::Outside
        }
    }
}