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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

use std::collections::{HashMap, HashSet};

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct GridPosition(i64, i64);

impl GridPosition {
    #[inline(always)]
    pub fn new(x: i64, y: i64) -> Self {
        Self(x, y)
    }

    #[inline(always)]
    pub fn neighbours(self) -> [GridPosition; 8] {
        let x = self.0;
        let y = self.1;

        [
            GridPosition::new(x - 1, y),
            GridPosition::new(x - 1, y - 1),
            GridPosition::new(x, y - 1),
            GridPosition::new(x + 1, y - 1),
            GridPosition::new(x + 1, y),
            GridPosition::new(x + 1, y + 1),
            GridPosition::new(x, y + 1),
            GridPosition::new(x - 1, y + 1),
        ]
    }
}

macro_rules! impl_into_grid_position {
    ( $tuple_ty: ty) => {
        impl Into<GridPosition> for ($tuple_ty, $tuple_ty) {
            fn into(self) -> GridPosition {
                GridPosition::new(self.0 as i64, self.1 as i64)
            }
        }
    };
    ( $tuple_ty_1: ty, $tuple_ty_2: ty) => {
        impl Into<GridPosition> for ($tuple_ty_1, $tuple_ty_2) {
            fn into(self) -> GridPosition {
                GridPosition::new(self.0 as i64, self.1 as i64)
            }
        }

        impl Into<GridPosition> for ($tuple_ty_2, $tuple_ty_1) {
            fn into(self) -> GridPosition {
                GridPosition::new(self.0 as i64, self.1 as i64)
            }
        }
    };
}

// TODO: expand this as required
impl_into_grid_position!(i64);
impl_into_grid_position!(i64, usize);
impl_into_grid_position!(i64, i32);
impl_into_grid_position!(i32);

#[derive(Clone, Debug)]
pub struct Grid {
    // TODO: think about different data structures that could be used here
    /// A set containing all of the inhabited states
    alive_states: HashSet<GridPosition>,

    /// A map from GridPosition -> {number of neighbouring alive cells}
    neighbour_count: HashMap<GridPosition, usize>,
}

impl Grid {
    #[inline(always)]
    pub fn empty() -> Self {
        Self {
            alive_states: HashSet::new(),
            neighbour_count: HashMap::new(),
        }
    }

    #[inline(always)]
    pub fn new(alive_states: HashSet<GridPosition>) -> Self {
        let mut grid = Self::empty();

        // TODO: investigate if we could do this smarter
        for pos in alive_states {
            grid.mark_as_alive(pos);
        }

        grid
    }

    #[inline(always)]
    pub fn is_live(&self, pos: GridPosition) -> bool {
        self.alive_states.contains(&pos)
    }

    #[inline(always)]
    pub fn is_dead(&self, pos: GridPosition) -> bool {
        !self.is_live(pos)
    }

    #[inline(always)]
    pub fn neighbour_count(&self, pos: GridPosition) -> usize {
        *self.neighbour_count.get(&pos).unwrap_or(&0)
    }

    #[inline(always)]
    fn _make_live(&mut self, pos: GridPosition) {
        // If pos is already alive, don't do anything
        if self.is_live(pos) {
            return;
        }

        // Otherwise increment the neighbour count for all neighbouring positions
        for neighbour in pos.neighbours().iter() {
            *self.neighbour_count.entry(*neighbour).or_default() += 1;
        }

        // Mark this state as alive
        self.alive_states.insert(pos);
    }

    pub fn mark_as_alive<P: Into<GridPosition>>(&mut self, into_pos: P) {
        self._make_live(into_pos.into())
    }

    #[inline(always)]
    fn _make_dead(&mut self, pos: GridPosition) {
        // If `pos` isn't alive, do nothing.
        if self.is_dead(pos) {
            return;
        }

        // Otherwise decrement the neighbour count for all neighbouring positions
        for neighbour in pos.neighbours().iter() {
            let neighbour_count = self.neighbour_count.entry(*neighbour).or_default();

            if *neighbour_count == 1 {
                // destroy this entry
                self.neighbour_count.remove(neighbour);
            } else {
                // should never be zero
                debug_assert!(*neighbour_count > 0);
                *neighbour_count -= 1;
            }
        }

        // remove this state
        self.alive_states.remove(&pos);
    }

    pub fn mark_as_dead<P: Into<GridPosition>>(&mut self, into_pos: P) {
        self._make_dead(into_pos.into())
    }

    #[inline(always)]
    pub fn alive_positions_iter(&self) -> impl Iterator<Item = &GridPosition> {
        self.alive_states.iter()
    }

    #[inline(always)]
    pub fn neighbour_count_iter(&self) -> impl Iterator<Item = (&GridPosition, &usize)> {
        self.neighbour_count.iter()
    }
}