sokoban_elements/
board_area.rs

1use std::iter::{FusedIterator, IntoIterator, Iterator};
2
3use bitvec::prelude::*;
4
5use crate::{Point2D, Size2D};
6
7/// `Set` of [`Point2D`](crate::Point2D) with small(ish) memory footprint.
8///
9/// Area is bound to game board [`Size2D`](crate::Size2D) given at construction time and only
10/// positions on that board can be its members. [`Point2D`](crate::Point2D) outside of it is not a
11/// member of any `BoardArea` and is silently ignored by [`contains()`](BoardArea::contains),
12/// [`add_point()`](BoardArea::add_point) and [`remove_point()`](BoardArea::remove_point).
13///
14/// # Examples
15///
16/// ```rust
17/// use sokoban_elements::*;
18///
19/// let mut area = BoardArea::new(Size2D::new(10, 10));
20/// assert!(area.is_empty());
21///
22/// assert!(area.add_point(Point2D::new(3, 4)));
23/// assert!(!area.add_point(Point2D::new(3, 4))); // ...it was already there
24///
25/// area.extend([Point2D::new(1, 8), Point2D::new(7, 2)]);
26/// assert_eq!(area.len(), 3);
27/// assert!(area.contains(Point2D::new(7, 2)));
28///
29/// // Positions off the board are never members.
30/// assert!(!area.add_point(Point2D::new(42, 0)));
31/// assert!(!area.contains(Point2D::new(42, 0)));
32///
33/// // Iteration is row-major, from top-left to bottom-right.
34/// assert_eq!(
35///     Vec::from_iter(&area),
36///     vec![Point2D::new(7, 2), Point2D::new(3, 4), Point2D::new(1, 8)]
37/// );
38///
39/// let other = BoardArea::from_points(area.board_size(), [Point2D::new(3, 4)]);
40/// assert!(other.is_subset(&area));
41/// assert_eq!(
42///     Vec::from_iter(&area.difference(&other).unwrap()),
43///     vec![Point2D::new(7, 2), Point2D::new(1, 8)]
44/// );
45/// ```
46///
47/// # Todo
48///
49/// - operator implementations (`BitOr`, `BitAnd`, `BitXor`, `Sub`, `Not`) for set operations
50/// - `retain()`
51/// - `Display`
52/// - `serde` support
53#[derive(Debug, Clone, PartialEq, Eq)]
54pub struct BoardArea {
55    board_size: Size2D,
56    data:       BitVec,
57}
58
59impl BoardArea {
60    /// Constructs empty area for board of `for_board_size`.
61    pub fn new(for_board_size: Size2D) -> Self {
62        Self {
63            board_size: for_board_size,
64            data:       BitVec::repeat(false, for_board_size.size()),
65        }
66    }
67
68    /// Constructs area for board of `for_board_size`, containing `points`.
69    ///
70    /// Positions in `points` that are off board are ignored - see
71    /// [`add_point()`](BoardArea::add_point).
72    ///
73    /// There is deliberately no `FromIterator` implementation:
74    /// [`board_size()`](BoardArea::board_size) can't be recovered from a stream of positions,
75    /// since their bounding box is not the board they live on.
76    pub fn from_points<I: IntoIterator<Item = Point2D>>(for_board_size: Size2D, points: I) -> Self {
77        let mut retv = Self::new(for_board_size);
78        retv.extend(points);
79        retv
80    }
81
82    /// Size of game board `self` was constructed for.
83    ///
84    /// Only positions on that board can be members of `self`.
85    pub fn board_size(&self) -> Size2D { self.board_size }
86
87    /// Count of [`Point2D`](crate::Point2D) in `self`.
88    pub fn len(&self) -> usize { self.data.count_ones() }
89
90    /// Returns `true` if `self` contains no [`Point2D`](crate::Point2D).
91    pub fn is_empty(&self) -> bool { self.len() == 0 }
92
93    /// Removes all [`Point2D`](crate::Point2D) from `self`, leaving
94    /// [`board_size()`](BoardArea::board_size) unchanged.
95    pub fn clear(&mut self) { self.data.fill(false); }
96
97    /// Returns `true` if `value` is member of `self`.
98    ///
99    /// Positions off [`board_size()`](BoardArea::board_size) are never members, so `false` is
100    /// returned for them.
101    pub fn contains(&self, value: Point2D) -> bool {
102        match self.bit_idx(value) {
103            Some(idx) => self.data.get(idx).as_deref() == Some(&true),
104            None => false,
105        }
106    }
107
108    /// Adds `value` to `self`, returning `true` if it wasn't already there.
109    ///
110    /// Positions off [`board_size()`](BoardArea::board_size) can't be members of `self`. They are
111    /// silently ignored - `false` is returned and `self` is left unchanged.
112    ///
113    /// The check is not merely defensive: [`Point2D::idx()`](crate::Point2D::idx) saturates instead
114    /// of failing, so on a 10x10 board `(15, 0)` computes the same 1D index as on-board `(5,
115    /// 1)`. Without it, adding the former would silently set the latter.
116    ///
117    /// # Examples
118    ///
119    /// ```rust
120    /// use sokoban_elements::*;
121    ///
122    /// let mut area = BoardArea::new(Size2D::new(10, 10));
123    ///
124    /// assert!(area.add_point(Point2D::new(5, 1)));
125    /// assert!(!area.add_point(Point2D::new(5, 1)));
126    ///
127    /// assert!(!area.add_point(Point2D::new(15, 0)));
128    /// assert_eq!(area.len(), 1);
129    /// ```
130    pub fn add_point(&mut self, value: Point2D) -> bool {
131        match self.bit_idx(value) {
132            Some(idx) => !self.data.replace(idx, true),
133            None => false,
134        }
135    }
136
137    /// Removes `value` from `self`, returning `true` if it was present in `self`.
138    ///
139    /// Positions off [`board_size()`](BoardArea::board_size) are never members, so `false` is
140    /// returned for them and `self` is left unchanged.
141    pub fn remove_point(&mut self, value: Point2D) -> bool {
142        match self.bit_idx(value) {
143            Some(idx) => self.data.replace(idx, false),
144            None => false,
145        }
146    }
147
148    /// Bounding box of `self`, as `(top_left, bottom_right)` corners.
149    ///
150    /// Returns `None` for empty area.
151    ///
152    /// Corners are extremes of member coordinates taken independently per axis, which means they
153    /// are not necessarily members of `self` themselves.
154    ///
155    /// # Examples
156    ///
157    /// ```rust
158    /// use sokoban_elements::*;
159    ///
160    /// let empty = BoardArea::new(Size2D::new(10, 10));
161    /// assert_eq!(empty.bounds(), None);
162    ///
163    /// let area =
164    ///     BoardArea::from_points(Size2D::new(10, 10), [Point2D::new(7, 2), Point2D::new(3, 8)]);
165    ///
166    /// // Neither corner is a member of `area`.
167    /// assert_eq!(area.bounds(), Some((Point2D::new(3, 2), Point2D::new(7, 8))));
168    /// assert_eq!(area.min_x(), Some(3));
169    /// assert_eq!(area.max_y(), Some(8));
170    /// ```
171    pub fn bounds(&self) -> Option<(Point2D, Point2D)> {
172        let mut ones = self.data.iter_ones();
173
174        // Non-empty `data` implies non-zero `board_size.width`, which `new_from_idx` requires.
175        let first = Point2D::new_from_idx(ones.next()?, &self.board_size);
176        let mut top_left = first;
177        let mut bottom_right = first;
178
179        for idx in ones {
180            let pos = Point2D::new_from_idx(idx, &self.board_size);
181            top_left.x = top_left.x.min(pos.x);
182            bottom_right.x = bottom_right.x.max(pos.x);
183            // 1D index is `y * width + x`, so `y` grows with it while `x` doesn't. `iter_ones()`
184            // ascends, which makes each `y` seen the largest so far - but says nothing about `x`.
185            bottom_right.y = pos.y;
186        }
187
188        Some((top_left, bottom_right))
189    }
190
191    /// Smallest `x` of all members of `self`, or `None` for empty area.
192    ///
193    /// See [`bounds()`](BoardArea::bounds()).
194    pub fn min_x(&self) -> Option<usize> { self.bounds().map(|(top_left, _)| top_left.x) }
195
196    /// Smallest `y` of all members of `self`, or `None` for empty area.
197    ///
198    /// See [`bounds()`](BoardArea::bounds()).
199    pub fn min_y(&self) -> Option<usize> { self.bounds().map(|(top_left, _)| top_left.y) }
200
201    /// Largest `x` of all members of `self`, or `None` for empty area.
202    ///
203    /// See [`bounds()`](BoardArea::bounds()).
204    pub fn max_x(&self) -> Option<usize> { self.bounds().map(|(_, bottom_right)| bottom_right.x) }
205
206    /// Largest `y` of all members of `self`, or `None` for empty area.
207    ///
208    /// See [`bounds()`](BoardArea::bounds()).
209    pub fn max_y(&self) -> Option<usize> { self.bounds().map(|(_, bottom_right)| bottom_right.y) }
210
211    /// Set union - positions that are in `self`, in `other`, or in both.
212    ///
213    /// Returns `None` if `self` and `other` were constructed for boards of different
214    /// [`board_size()`](BoardArea::board_size), because areas of differently sized boards are not
215    /// comparable.
216    ///
217    /// # Examples
218    ///
219    /// ```rust
220    /// use sokoban_elements::*;
221    ///
222    /// let size = Size2D::new(10, 10);
223    /// let left = BoardArea::from_points(size, [Point2D::new(1, 1), Point2D::new(2, 2)]);
224    /// let right = BoardArea::from_points(size, [Point2D::new(2, 2), Point2D::new(3, 3)]);
225    ///
226    /// assert_eq!(left.union(&right).unwrap().len(), 3);
227    /// assert_eq!(left.intersection(&right).unwrap().len(), 1);
228    ///
229    /// // Areas of differently sized boards are not comparable.
230    /// let other_board = BoardArea::new(Size2D::new(5, 5));
231    /// assert_eq!(left.union(&other_board), None);
232    /// ```
233    pub fn union(&self, other: &Self) -> Option<Self> {
234        let mut retv = self.cloned_for_op_with(other)?;
235        retv.data |= &other.data;
236        Some(retv)
237    }
238
239    /// Set intersection - positions that are in both `self` and `other`.
240    ///
241    /// Returns `None` for areas of differently sized boards - see [`union()`](BoardArea::union()).
242    pub fn intersection(&self, other: &Self) -> Option<Self> {
243        let mut retv = self.cloned_for_op_with(other)?;
244        retv.data &= &other.data;
245        Some(retv)
246    }
247
248    /// Set difference - positions that are in `self` but not in `other`.
249    ///
250    /// Returns `None` for areas of differently sized boards - see [`union()`](BoardArea::union()).
251    pub fn difference(&self, other: &Self) -> Option<Self> {
252        let mut retv = self.cloned_for_op_with(other)?;
253        // `Not` consumes its operand, hence the clone.
254        retv.data &= !other.data.clone();
255        Some(retv)
256    }
257
258    /// Set symmetric difference - positions that are in `self` or in `other`, but not in both.
259    ///
260    /// Returns `None` for areas of differently sized boards - see [`union()`](BoardArea::union()).
261    pub fn symmetric_difference(&self, other: &Self) -> Option<Self> {
262        let mut retv = self.cloned_for_op_with(other)?;
263        retv.data ^= &other.data;
264        Some(retv)
265    }
266
267    /// Returns `true` if every member of `self` is also member of `other`.
268    ///
269    /// Areas of differently sized boards are not comparable, and for them `false` is returned. Note
270    /// that this scopes the usual empty set law to boards of equal size: empty area is subset of
271    /// every area *of the same [`board_size()`](BoardArea::board_size)*, and of no other.
272    pub fn is_subset(&self, other: &Self) -> bool {
273        self.board_size == other.board_size
274            && self
275                .data
276                .iter_ones()
277                .all(|idx| other.data.get(idx).as_deref() == Some(&true))
278    }
279
280    /// Returns `true` if every member of `other` is also member of `self`.
281    ///
282    /// Areas of differently sized boards are not comparable - see
283    /// [`is_subset()`](BoardArea::is_subset).
284    pub fn is_superset(&self, other: &Self) -> bool { other.is_subset(self) }
285
286    /// Returns `true` if `self` and `other` have no members in common.
287    ///
288    /// Areas of differently sized boards are not comparable, and for them `true` is returned. This
289    /// is the same answer given for genuinely non-overlapping areas of one board, so it can't be
290    /// used to tell "no common members" from "not comparable" - compare
291    /// [`board_size()`](BoardArea::board_size) first if that distinction matters.
292    pub fn is_disjoint(&self, other: &Self) -> bool {
293        self.board_size != other.board_size
294            || !self
295                .data
296                .iter_ones()
297                .any(|idx| other.data.get(idx).as_deref() == Some(&true))
298    }
299
300    /// Iterator over members of `self`, in row-major order.
301    pub fn iter(&self) -> BoardAreaIter<'_> { BoardAreaIter { idx: 0, obj: self } }
302
303    /// 1D index of `value` in [`data`](BoardArea::data), or `None` if `value` is off board.
304    fn bit_idx(&self, value: Point2D) -> Option<usize> {
305        // `is_on_board` is what guarantees `idx < data.len()`, as required by `BitVec::replace`.
306        value
307            .is_on_board(self.board_size)
308            .then(|| value.idx(self.board_size))
309    }
310
311    /// `self.clone()`, or `None` if `other` is area of differently sized board.
312    ///
313    /// Equal [`board_size()`](BoardArea::board_size) implies equal [`data`](BoardArea::data)
314    /// length, which set operations rely on.
315    fn cloned_for_op_with(&self, other: &Self) -> Option<Self> {
316        (self.board_size == other.board_size).then(|| self.clone())
317    }
318}
319
320// `Extend` rather than `FromIterator` - see `from_points`.
321
322impl<'a> Extend<&'a Point2D> for BoardArea {
323    fn extend<T: IntoIterator<Item = &'a Point2D>>(&mut self, iter: T) {
324        for pos in iter {
325            self.add_point(*pos);
326        }
327    }
328}
329
330impl Extend<Point2D> for BoardArea {
331    fn extend<T: IntoIterator<Item = Point2D>>(&mut self, iter: T) {
332        for pos in iter {
333            self.add_point(pos);
334        }
335    }
336}
337
338impl<'a> IntoIterator for &'a BoardArea {
339    type Item = Point2D;
340    type IntoIter = BoardAreaIter<'a>;
341
342    fn into_iter(self) -> Self::IntoIter { self.iter() }
343}
344
345impl IntoIterator for BoardArea {
346    type Item = Point2D;
347    type IntoIter = BoardAreaIntoIter;
348
349    fn into_iter(self) -> Self::IntoIter { BoardAreaIntoIter { idx: 0, obj: self } }
350}
351
352// ----------------------------------------
353// Iterator
354// ----------------------------------------
355
356/// Iterator over [`Point2D`] in [`BoardArea`].
357#[derive(Debug, Clone)]
358pub struct BoardAreaIter<'a> {
359    obj: &'a BoardArea,
360    idx: usize,
361}
362
363impl Iterator for BoardAreaIter<'_> {
364    type Item = Point2D;
365
366    fn next(&mut self) -> Option<Self::Item> {
367        let found = self.idx + self.obj.data.get(self.idx..)?.first_one()?;
368        self.idx = found + 1;
369        Some(Point2D::new_from_idx(found, &self.obj.board_size))
370    }
371
372    fn size_hint(&self) -> (usize, Option<usize>) {
373        let remaining = self
374            .obj
375            .data
376            .get(self.idx..)
377            .map_or(0, bitvec::slice::BitSlice::count_ones);
378        (remaining, Some(remaining))
379    }
380}
381
382impl ExactSizeIterator for BoardAreaIter<'_> {}
383
384impl FusedIterator for BoardAreaIter<'_> {}
385
386// ----------------------------------------
387// Owning iterator
388// ----------------------------------------
389
390/// Owning iterator over [`Point2D`] in [`BoardArea`].
391#[derive(Debug, Clone)]
392pub struct BoardAreaIntoIter {
393    obj: BoardArea,
394    idx: usize,
395}
396
397impl Iterator for BoardAreaIntoIter {
398    type Item = Point2D;
399
400    fn next(&mut self) -> Option<Self::Item> {
401        let found = self.idx + self.obj.data.get(self.idx..)?.first_one()?;
402        self.idx = found + 1;
403        Some(Point2D::new_from_idx(found, &self.obj.board_size))
404    }
405
406    fn size_hint(&self) -> (usize, Option<usize>) {
407        let remaining = self
408            .obj
409            .data
410            .get(self.idx..)
411            .map_or(0, bitvec::slice::BitSlice::count_ones);
412        (remaining, Some(remaining))
413    }
414}
415
416impl ExactSizeIterator for BoardAreaIntoIter {}
417
418impl FusedIterator for BoardAreaIntoIter {}
419
420#[cfg(test)]
421mod tests {
422    use super::*;
423
424    fn board_size() -> Size2D { Size2D::new(10, 10) }
425
426    #[test]
427    fn it_can_check_if_it_is_empty() {
428        let mut area = BoardArea::new(board_size());
429
430        assert!(area.is_empty());
431        assert_eq!(area.len(), 0);
432
433        area.add_point(Point2D::new(5, 5));
434        assert!(!area.is_empty());
435        assert_eq!(area.len(), 1);
436    }
437
438    #[test]
439    fn it_can_be_cleared_while_keeping_board_size() {
440        let mut area = BoardArea::from_points(board_size(), [Point2D::new(5, 5)]);
441
442        area.clear();
443        assert!(area.is_empty());
444        assert_eq!(area.board_size(), board_size());
445    }
446
447    #[test]
448    fn it_can_add_points() {
449        let mut area = BoardArea::new(board_size());
450        let pos = Point2D::new(5, 5);
451
452        assert!(area.add_point(pos));
453        assert!(area.contains(pos));
454
455        // ...it was already there
456        assert!(!area.add_point(pos));
457        assert_eq!(area.len(), 1);
458    }
459
460    #[test]
461    fn it_can_remove_points() {
462        let mut area = BoardArea::new(board_size());
463        let pos = Point2D::new(5, 5);
464
465        area.add_point(pos);
466        assert!(area.contains(pos));
467
468        assert!(area.remove_point(pos));
469        assert!(!area.contains(pos));
470
471        // ...it was already gone
472        assert!(!area.remove_point(pos));
473    }
474
475    #[test]
476    fn it_can_be_extended_from_points_and_from_references() {
477        let mut area = BoardArea::new(board_size());
478
479        area.extend([Point2D::new(1, 1), Point2D::new(2, 2)]);
480
481        let more = [Point2D::new(3, 3)];
482        area.extend(more.iter());
483
484        assert_eq!(
485            Vec::from_iter(&area),
486            vec![Point2D::new(1, 1), Point2D::new(2, 2), Point2D::new(3, 3)]
487        );
488    }
489
490    #[test]
491    fn it_can_iterate_over_points() {
492        let mut area = BoardArea::new(board_size());
493        let pos1 = Point2D::new(5, 5);
494        let pos2 = Point2D::new(6, 6);
495
496        area.add_point(pos1);
497        area.add_point(pos2);
498
499        let mut data: Vec<Point2D> = vec![];
500        for pos in &area {
501            data.push(pos);
502        }
503        assert_eq!(data, vec![pos1, pos2]);
504
505        let mut data: Vec<Point2D> = vec![];
506        for pos in &area {
507            data.push(pos);
508        }
509        assert_eq!(data, vec![pos1, pos2]);
510
511        let data: Vec<Point2D> = Vec::from_iter(area);
512        assert_eq!(data, vec![pos1, pos2]);
513    }
514
515    #[test]
516    fn it_iterates_in_row_major_order() {
517        let area = BoardArea::from_points(
518            board_size(),
519            [Point2D::new(9, 0), Point2D::new(0, 9), Point2D::new(4, 4)],
520        );
521
522        assert_eq!(
523            Vec::from_iter(&area),
524            vec![Point2D::new(9, 0), Point2D::new(4, 4), Point2D::new(0, 9)]
525        );
526    }
527
528    #[test]
529    fn it_reports_count_of_remaining_points_while_iterating() {
530        let area = BoardArea::from_points(board_size(), [Point2D::new(5, 5), Point2D::new(6, 6)]);
531
532        let mut iter = area.iter();
533        assert_eq!(iter.len(), 2);
534        assert_eq!(iter.size_hint(), (2, Some(2)));
535
536        iter.next();
537        assert_eq!(iter.len(), 1);
538        assert_eq!(iter.size_hint(), (1, Some(1)));
539
540        iter.next();
541        assert_eq!(iter.len(), 0);
542        assert_eq!(iter.size_hint(), (0, Some(0)));
543
544        // ...and it stays exhausted
545        assert!(iter.next().is_none());
546        assert_eq!(iter.len(), 0);
547    }
548
549    #[test]
550    fn owning_iterator_reports_count_of_remaining_points_while_iterating() {
551        let area = BoardArea::from_points(board_size(), [Point2D::new(5, 5), Point2D::new(6, 6)]);
552
553        let mut iter = area.into_iter();
554        assert_eq!(iter.len(), 2);
555        assert_eq!(iter.size_hint(), (2, Some(2)));
556
557        iter.next();
558        assert_eq!(iter.len(), 1);
559        assert_eq!(iter.size_hint(), (1, Some(1)));
560
561        iter.next();
562        assert_eq!(iter.len(), 0);
563        assert_eq!(iter.size_hint(), (0, Some(0)));
564
565        assert!(iter.next().is_none());
566        assert_eq!(iter.len(), 0);
567    }
568
569    #[test]
570    fn when_point_is_off_board_it_is_not_a_member() {
571        let mut area = BoardArea::new(board_size());
572
573        // `Point2D::idx` saturates, so this shares 1D index with on-board `(5, 1)`.
574        let off_board_x = Point2D::new(15, 0);
575        assert!(!area.add_point(off_board_x));
576        assert!(!area.contains(off_board_x));
577        assert!(!area.contains(Point2D::new(5, 1)));
578        assert!(area.is_empty());
579
580        // ...while index of this one lands past the end of underlying storage.
581        let off_board_y = Point2D::new(0, 15);
582        assert!(!area.add_point(off_board_y));
583        assert!(!area.contains(off_board_y));
584        assert!(area.is_empty());
585
586        assert!(!area.remove_point(off_board_x));
587        assert!(!area.remove_point(off_board_y));
588    }
589
590    #[test]
591    fn when_board_has_no_tiles_area_is_always_empty() {
592        for size in [Size2D::new(0, 0), Size2D::new(0, 5), Size2D::new(5, 0)] {
593            let mut area = BoardArea::new(size);
594
595            assert!(area.is_empty());
596            assert!(!area.add_point(Point2D::origin()));
597            assert!(!area.contains(Point2D::origin()));
598            assert_eq!(area.bounds(), None);
599            assert!(area.iter().next().is_none());
600        }
601    }
602
603    #[test]
604    fn when_area_is_empty_it_has_no_bounds() {
605        let area = BoardArea::new(board_size());
606
607        assert_eq!(area.bounds(), None);
608        assert_eq!(area.min_x(), None);
609        assert_eq!(area.min_y(), None);
610        assert_eq!(area.max_x(), None);
611        assert_eq!(area.max_y(), None);
612    }
613
614    #[test]
615    fn it_calculates_bounds_of_single_point_area() {
616        let area = BoardArea::from_points(board_size(), [Point2D::new(3, 7)]);
617
618        assert_eq!(area.bounds(), Some((Point2D::new(3, 7), Point2D::new(3, 7))));
619        assert_eq!(area.min_x(), Some(3));
620        assert_eq!(area.max_x(), Some(3));
621        assert_eq!(area.min_y(), Some(7));
622        assert_eq!(area.max_y(), Some(7));
623    }
624
625    #[test]
626    fn it_calculates_bounds_when_extremes_are_in_different_rows() {
627        // Leftmost point is not in topmost row and rightmost one is not in bottom row, so neither
628        // corner of the bounding box is a member of the area.
629        let area = BoardArea::from_points(
630            board_size(),
631            [Point2D::new(7, 2), Point2D::new(3, 4), Point2D::new(5, 8)],
632        );
633
634        assert_eq!(area.bounds(), Some((Point2D::new(3, 2), Point2D::new(7, 8))));
635        assert_eq!(area.min_x(), Some(3));
636        assert_eq!(area.max_x(), Some(7));
637        assert_eq!(area.min_y(), Some(2));
638        assert_eq!(area.max_y(), Some(8));
639    }
640
641    #[test]
642    fn it_calculates_set_operations() {
643        let size = board_size();
644        let left = BoardArea::from_points(size, [Point2D::new(1, 1), Point2D::new(2, 2)]);
645        let right = BoardArea::from_points(size, [Point2D::new(2, 2), Point2D::new(3, 3)]);
646
647        assert_eq!(
648            left.union(&right),
649            Some(BoardArea::from_points(
650                size,
651                [Point2D::new(1, 1), Point2D::new(2, 2), Point2D::new(3, 3)]
652            ))
653        );
654        assert_eq!(
655            left.intersection(&right),
656            Some(BoardArea::from_points(size, [Point2D::new(2, 2)]))
657        );
658        assert_eq!(
659            left.difference(&right),
660            Some(BoardArea::from_points(size, [Point2D::new(1, 1)]))
661        );
662        assert_eq!(
663            left.symmetric_difference(&right),
664            Some(BoardArea::from_points(size, [Point2D::new(1, 1), Point2D::new(3, 3)]))
665        );
666    }
667
668    #[test]
669    fn it_calculates_set_operations_on_disjoint_and_equal_areas() {
670        let size = board_size();
671        let left = BoardArea::from_points(size, [Point2D::new(1, 1)]);
672        let right = BoardArea::from_points(size, [Point2D::new(9, 9)]);
673        let empty = BoardArea::new(size);
674
675        assert_eq!(left.intersection(&right), Some(empty.clone()));
676        assert_eq!(left.difference(&right), Some(left.clone()));
677        assert_eq!(left.symmetric_difference(&right), left.union(&right));
678
679        assert_eq!(left.union(&left), Some(left.clone()));
680        assert_eq!(left.intersection(&left), Some(left.clone()));
681        assert_eq!(left.difference(&left), Some(empty.clone()));
682        assert_eq!(left.symmetric_difference(&left), Some(empty));
683    }
684
685    #[test]
686    fn it_checks_subset_superset_and_disjoint() {
687        let size = board_size();
688        let whole = BoardArea::from_points(
689            size,
690            [Point2D::new(1, 1), Point2D::new(2, 2), Point2D::new(3, 3)],
691        );
692        let part = BoardArea::from_points(size, [Point2D::new(2, 2)]);
693        let elsewhere = BoardArea::from_points(size, [Point2D::new(9, 9)]);
694
695        assert!(part.is_subset(&whole));
696        assert!(whole.is_superset(&part));
697        assert!(!whole.is_subset(&part));
698        assert!(!part.is_superset(&whole));
699
700        // ...every area is subset and superset of itself
701        assert!(whole.is_subset(&whole));
702        assert!(whole.is_superset(&whole));
703
704        assert!(!part.is_disjoint(&whole));
705        assert!(elsewhere.is_disjoint(&whole));
706        assert!(whole.is_disjoint(&elsewhere));
707    }
708
709    #[test]
710    fn it_treats_empty_area_as_subset_of_every_area_of_same_board_size() {
711        let size = board_size();
712        let empty = BoardArea::new(size);
713        let area = BoardArea::from_points(size, [Point2D::new(1, 1)]);
714
715        assert!(empty.is_subset(&area));
716        assert!(empty.is_subset(&empty));
717        assert!(area.is_superset(&empty));
718        assert!(empty.is_disjoint(&area));
719        assert!(empty.is_disjoint(&empty));
720    }
721
722    #[test]
723    fn when_board_sizes_differ_set_operations_return_none() {
724        let left = BoardArea::from_points(board_size(), [Point2D::new(1, 1)]);
725        let right = BoardArea::from_points(Size2D::new(5, 5), [Point2D::new(1, 1)]);
726
727        assert_eq!(left.union(&right), None);
728        assert_eq!(left.intersection(&right), None);
729        assert_eq!(left.difference(&right), None);
730        assert_eq!(left.symmetric_difference(&right), None);
731
732        assert_eq!(right.union(&left), None);
733        assert_eq!(right.intersection(&left), None);
734        assert_eq!(right.difference(&left), None);
735        assert_eq!(right.symmetric_difference(&left), None);
736    }
737
738    #[test]
739    fn when_board_sizes_differ_areas_are_not_comparable() {
740        let left = BoardArea::from_points(board_size(), [Point2D::new(1, 1)]);
741        let right = BoardArea::from_points(Size2D::new(5, 5), [Point2D::new(1, 1)]);
742
743        // Same members, but of different boards.
744        assert!(!left.is_subset(&right));
745        assert!(!left.is_superset(&right));
746        assert!(left.is_disjoint(&right));
747
748        // Empty set laws hold only within one board size.
749        let empty = BoardArea::new(Size2D::new(5, 5));
750        assert!(!empty.is_subset(&left));
751        assert!(!left.is_superset(&empty));
752
753        // ...two empty areas of different boards are still not comparable, even though
754        // `is_disjoint` can't show it - it answers `true` here for both possible reasons.
755        let other_empty = BoardArea::new(board_size());
756        assert!(!empty.is_subset(&other_empty));
757        assert!(!empty.is_superset(&other_empty));
758        assert!(empty.is_disjoint(&other_empty));
759    }
760}
sokoban_elements/board_area.rs

sokoban_elements/
board_area.rs
