life_backend/
board.rs

1use fnv::FnvBuildHasher;
2use num_iter::range_inclusive;
3use num_traits::{One, ToPrimitive, Zero};
4use std::collections::hash_set;
5use std::collections::HashSet;
6use std::fmt;
7use std::hash::Hash;
8use std::iter::FromIterator;
9
10use crate::{BoardRange, Position};
11
12/// A two-dimensional orthogonal grid map of live/dead cells.
13///
14/// The type parameter `T` is used as the type of the x- and y-coordinate values for each cell.
15///
16/// # Examples
17///
18/// ```
19/// use life_backend::{Board, Position};
20/// let pattern = [Position(0, 0), Position(1, 0), Position(2, 0), Position(1, 1)];
21/// let board: Board<i16> = pattern.iter().collect();
22/// assert_eq!(board.contains(&Position(0, 0)), true);
23/// assert_eq!(board.contains(&Position(0, 1)), false);
24/// assert_eq!(board.iter().count(), 4);
25/// ```
26///
27#[derive(Clone, PartialEq, Eq, Debug)]
28pub struct Board<T>(HashSet<Position<T>, FnvBuildHasher>)
29where
30    T: Eq + Hash;
31
32// Inherent methods
33
34impl<T> Board<T>
35where
36    T: Eq + Hash,
37{
38    /// Creates an empty board.
39    ///
40    /// # Examples
41    ///
42    /// ```
43    /// use life_backend::Board;
44    /// let board = Board::<i16>::new();
45    /// assert_eq!(board.iter().count(), 0);
46    /// ```
47    ///
48    #[inline]
49    pub fn new() -> Self {
50        Self(HashSet::default())
51    }
52
53    /// Returns `true` if the board contains the specified position.
54    ///
55    /// # Examples
56    ///
57    /// ```
58    /// use life_backend::{Board, Position};
59    /// let board = Board::<i16>::new();
60    /// assert_eq!(board.contains(&Position(0, 0)), false);
61    /// ```
62    ///
63    #[inline]
64    pub fn contains(&self, position: &Position<T>) -> bool {
65        self.0.contains(position)
66    }
67
68    /// Adds the specified position to the board.
69    ///
70    /// Returns whether the position was newly inserted, like as [`insert()`] of [`HashSet`].
71    ///
72    /// [`insert()`]: std::collections::HashSet::insert
73    /// [`HashSet`]: std::collections::HashSet
74    ///
75    /// # Examples
76    ///
77    /// ```
78    /// use life_backend::{Board, Position};
79    /// let mut board = Board::<i16>::new();
80    /// assert_eq!(board.insert(Position(0, 0)), true);
81    /// assert_eq!(board.contains(&Position(0, 0)), true);
82    /// ```
83    ///
84    #[inline]
85    pub fn insert(&mut self, position: Position<T>) -> bool {
86        self.0.insert(position)
87    }
88
89    /// Removes the specified position from the board.
90    ///
91    /// Returns whether the position was contained in the board, like as [`remove()`] of [`HashSet`].
92    ///
93    /// [`remove()`]: std::collections::HashSet::remove
94    /// [`HashSet`]: std::collections::HashSet
95    ///
96    /// # Examples
97    ///
98    /// ```
99    /// use life_backend::{Board, Position};
100    /// let mut board = Board::<i16>::new();
101    /// assert_eq!(board.insert(Position(0, 0)), true);
102    /// assert_eq!(board.remove(&Position(0, 0)), true);
103    /// assert_eq!(board.contains(&Position(0, 0)), false);
104    /// ```
105    ///
106    #[inline]
107    pub fn remove(&mut self, position: &Position<T>) -> bool {
108        self.0.remove(position)
109    }
110
111    /// Returns the minimum bounding box of all live cells on the board.
112    ///
113    /// # Examples
114    ///
115    /// ```
116    /// use life_backend::{Board, Position};
117    /// let mut board = Board::new();
118    /// board.insert(Position(-1, 2));
119    /// board.insert(Position(3, -2));
120    /// let bbox = board.bounding_box();
121    /// assert_eq!(bbox.x(), &(-1..=3));
122    /// assert_eq!(bbox.y(), &(-2..=2));
123    /// ```
124    ///
125    #[inline]
126    pub fn bounding_box(&self) -> BoardRange<T>
127    where
128        T: Copy + PartialOrd + Zero + One,
129    {
130        self.0.iter().collect::<BoardRange<_>>()
131    }
132
133    /// Removes all live cells in the board.
134    ///
135    /// # Examples
136    ///
137    /// ```
138    /// use life_backend::{Board, Position};
139    /// let mut board = Board::<i16>::new();
140    /// board.insert(Position(0, 0));
141    /// board.clear();
142    /// assert_eq!(board.contains(&Position(0, 0)), false);
143    /// ```
144    ///
145    #[inline]
146    pub fn clear(&mut self) {
147        self.0.clear();
148    }
149
150    /// Retains only the live cell positions specified by the predicate, similar as [`retain()`] of [`HashSet`].
151    ///
152    /// [`retain()`]: std::collections::HashSet::retain
153    /// [`HashSet`]: std::collections::HashSet
154    ///
155    /// # Examples
156    ///
157    /// ```
158    /// use life_backend::{Board, Position};
159    /// let mut board = Board::<i16>::new();
160    /// board.insert(Position(0, 0));
161    /// board.insert(Position(1, 0));
162    /// board.insert(Position(0, 1));
163    /// board.retain(|&pos| pos.0 == pos.1);
164    /// assert_eq!(board.contains(&Position(0, 0)), true);
165    /// assert_eq!(board.contains(&Position(1, 0)), false);
166    /// assert_eq!(board.contains(&Position(0, 1)), false);
167    /// ```
168    ///
169    #[inline]
170    pub fn retain<F>(&mut self, pred: F)
171    where
172        F: FnMut(&Position<T>) -> bool,
173    {
174        self.0.retain(pred);
175    }
176}
177
178impl<'a, T> Board<T>
179where
180    T: Eq + Hash,
181{
182    /// Creates a non-owning iterator over the series of immutable live cell positions on the board in arbitrary order.
183    ///
184    /// # Examples
185    ///
186    /// ```
187    /// use std::collections::HashSet;
188    /// use life_backend::{Board, Position};
189    /// let mut board = Board::<i16>::new();
190    /// board.insert(Position(1, 0));
191    /// board.insert(Position(0, 1));
192    /// let result: HashSet<_> = board.iter().collect();
193    /// assert_eq!(result.len(), 2);
194    /// assert!(result.contains(&Position(1, 0)));
195    /// assert!(result.contains(&Position(0, 1)));
196    /// ```
197    ///
198    #[inline]
199    pub fn iter(&'a self) -> hash_set::Iter<'a, Position<T>> {
200        self.into_iter()
201    }
202}
203
204// Trait implementations
205
206impl<T> Default for Board<T>
207where
208    T: Eq + Hash,
209{
210    /// Returns the default value of the type, same as the return value of [`new()`].
211    ///
212    /// [`new()`]: #method.new
213    ///
214    #[inline]
215    fn default() -> Self {
216        Self::new()
217    }
218}
219
220impl<T> fmt::Display for Board<T>
221where
222    T: Eq + Hash + Copy + PartialOrd + Zero + One + ToPrimitive,
223{
224    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
225        let bbox = self.bounding_box();
226        for y in range_inclusive(*bbox.y().start(), *bbox.y().end()) {
227            let line: String = range_inclusive(*bbox.x().start(), *bbox.x().end())
228                .map(|x| if self.contains(&Position(x, y)) { 'O' } else { '.' })
229                .collect();
230            writeln!(f, "{line}")?;
231        }
232        Ok(())
233    }
234}
235
236impl<'a, T> IntoIterator for &'a Board<T>
237where
238    T: Eq + Hash,
239{
240    type Item = &'a Position<T>;
241    type IntoIter = hash_set::Iter<'a, Position<T>>;
242
243    /// Creates a non-owning iterator over the series of immutable live cell positions on the board in arbitrary order.
244    ///
245    /// # Examples
246    ///
247    /// ```
248    /// use std::collections::HashSet;
249    /// use life_backend::{Board, Position};
250    /// let pattern = [Position(1, 0), Position(0, 1)];
251    /// let board: Board<i16> = pattern.iter().collect();
252    /// let result: HashSet<_> = (&board).into_iter().collect();
253    /// let expected: HashSet<_> = pattern.iter().collect();
254    /// assert_eq!(result, expected);
255    /// ```
256    ///
257    #[inline]
258    fn into_iter(self) -> Self::IntoIter {
259        self.0.iter()
260    }
261}
262
263impl<T> IntoIterator for Board<T>
264where
265    T: Eq + Hash,
266{
267    type Item = Position<T>;
268    type IntoIter = hash_set::IntoIter<Self::Item>;
269
270    /// Creates an owning iterator over the series of moved live cell positions on the board in arbitrary order.
271    ///
272    /// # Examples
273    ///
274    /// ```
275    /// use std::collections::HashSet;
276    /// use life_backend::{Board, Position};
277    /// let pattern = [Position(1, 0), Position(0, 1)];
278    /// let board: Board<i16> = pattern.iter().collect();
279    /// let result: HashSet<_> = board.into_iter().collect();
280    /// let expected: HashSet<_> = pattern.iter().copied().collect();
281    /// assert_eq!(result, expected);
282    /// ```
283    ///
284    #[inline]
285    fn into_iter(self) -> Self::IntoIter {
286        self.0.into_iter()
287    }
288}
289
290impl<'a, T> FromIterator<&'a Position<T>> for Board<T>
291where
292    T: Eq + Hash + Copy + 'a,
293{
294    /// Creates a value from a non-owning iterator over a series of [`&Position<T>`].
295    /// Each item in the series represents an immutable reference of a live cell position.
296    ///
297    /// [`&Position<T>`]: Position
298    ///
299    /// # Examples
300    ///
301    /// ```
302    /// use life_backend::{Board, Position};
303    /// let pattern = [Position(1, 0), Position(0, 1)];
304    /// let board: Board<i16> = pattern.iter().collect();
305    /// assert_eq!(board.contains(&Position(0, 0)), false);
306    /// assert_eq!(board.contains(&Position(1, 0)), true);
307    /// assert_eq!(board.contains(&Position(0, 1)), true);
308    /// assert_eq!(board.contains(&Position(1, 1)), false);
309    /// ```
310    ///
311    #[inline]
312    fn from_iter<U>(iter: U) -> Self
313    where
314        U: IntoIterator<Item = &'a Position<T>>,
315    {
316        Self::from_iter(iter.into_iter().copied())
317    }
318}
319
320impl<T> FromIterator<Position<T>> for Board<T>
321where
322    T: Eq + Hash,
323{
324    /// Creates a value from an owning iterator over a series of [`Position<T>`].
325    /// Each item in the series represents a moved live cell position.
326    ///
327    /// [`Position<T>`]: Position
328    ///
329    /// # Examples
330    ///
331    /// ```
332    /// use life_backend::{Board, Position};
333    /// let mut pattern = [Position(1, 0), Position(0, 1)];
334    /// let board: Board<i16> = pattern.into_iter().collect();
335    /// assert_eq!(board.contains(&Position(0, 0)), false);
336    /// assert_eq!(board.contains(&Position(1, 0)), true);
337    /// assert_eq!(board.contains(&Position(0, 1)), true);
338    /// assert_eq!(board.contains(&Position(1, 1)), false);
339    /// ```
340    ///
341    #[inline]
342    fn from_iter<U>(iter: U) -> Self
343    where
344        U: IntoIterator<Item = Position<T>>,
345    {
346        Self(HashSet::<Position<T>, _>::from_iter(iter))
347    }
348}
349
350impl<'a, T> Extend<&'a Position<T>> for Board<T>
351where
352    T: Eq + Hash + Copy + 'a,
353{
354    /// Extends the board with the contents of the specified non-owning iterator over the series of [`&Position<T>`].
355    /// Each item in the series represents an immutable reference of a live cell position.
356    ///
357    /// [`&Position<T>`]: Position
358    ///
359    /// # Examples
360    ///
361    /// ```
362    /// use life_backend::{Board, Position};
363    /// let mut board = Board::<i16>::new();
364    /// let pattern = [Position(1, 0), Position(0, 1)];
365    /// board.extend(pattern.iter());
366    /// assert_eq!(board.contains(&Position(0, 0)), false);
367    /// assert_eq!(board.contains(&Position(1, 0)), true);
368    /// assert_eq!(board.contains(&Position(0, 1)), true);
369    /// assert_eq!(board.contains(&Position(1, 1)), false);
370    /// ```
371    ///
372    #[inline]
373    fn extend<U>(&mut self, iter: U)
374    where
375        U: IntoIterator<Item = &'a Position<T>>,
376    {
377        self.0.extend(iter);
378    }
379}
380
381impl<T> Extend<Position<T>> for Board<T>
382where
383    T: Eq + Hash,
384{
385    /// Extends the board with the contents of the specified owning iterator over the series of [`Position<T>`].
386    /// Each item in the series represents a moved live cell position.
387    ///
388    /// [`Position<T>`]: Position
389    ///
390    /// # Examples
391    ///
392    /// ```
393    /// use life_backend::{Board, Position};
394    /// let mut board = Board::<i16>::new();
395    /// let pattern = [Position(1, 0), Position(0, 1)];
396    /// board.extend(pattern.into_iter());
397    /// assert_eq!(board.contains(&Position(0, 0)), false);
398    /// assert_eq!(board.contains(&Position(1, 0)), true);
399    /// assert_eq!(board.contains(&Position(0, 1)), true);
400    /// assert_eq!(board.contains(&Position(1, 1)), false);
401    /// ```
402    ///
403    #[inline]
404    fn extend<U>(&mut self, iter: U)
405    where
406        U: IntoIterator<Item = Position<T>>,
407    {
408        self.0.extend(iter);
409    }
410}
411
412// Unit tests
413
414#[cfg(test)]
415mod tests {
416    use super::*;
417    #[test]
418    fn default() {
419        let target = Board::<i16>::default();
420        let expected = Board::<i16>::new();
421        assert_eq!(target, expected);
422    }
423}
life_backend/board.rs

life_backend/
board.rs
