bit_board/
bitboarddyn.rs

1use std::fmt;
2
3use bitvec::prelude::*;
4
5use crate::{DimensionMismatch, bitboard::BitBoard};
6
7/// BitBoard is a 2D array of booleans, stored in the bits of integers. It does
8/// assumes that the boundaries are hard, and going past a boundary does *not* take
9/// you back to the other side.
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub struct BitBoardDyn {
12    /// The slice of bits that represent the board.
13    pub board: BitVec,
14
15    /// How many rows does the board have
16    pub n_rows: usize,
17
18    /// How many columns does the board have
19    pub n_cols: usize,
20}
21
22impl fmt::Display for BitBoardDyn {
23    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
24        // column indices
25        write!(f, "   ")?; // space for row labels
26        for col in 0..self.n_cols {
27            write!(f, "{}", col % 10)?; // wrap every 10 for readability
28        }
29        writeln!(f)?;
30
31        for row in 0..self.n_rows {
32            // row index, right-aligned to 2 spaces
33            write!(f, "{:>2} ", row)?;
34            for col in 0..self.n_cols {
35                let idx = row * self.n_cols + col;
36                let bit = self.board[idx];
37                let c = if bit { 'X' } else { '.' };
38                write!(f, "{}", c)?;
39            }
40            writeln!(f)?;
41        }
42        Ok(())
43    }
44}
45
46impl BitBoard for BitBoardDyn {
47    fn n_rows(&self) -> usize {
48        self.n_rows
49    }
50
51    fn n_cols(&self) -> usize {
52        self.n_cols
53    }
54
55    fn board_mut(&mut self) -> &mut BitSlice {
56        &mut self.board
57    }
58
59    fn board(&self) -> &BitSlice {
60        &self.board
61    }
62
63    fn or(&self, other: &impl BitBoard) -> Result<Self, DimensionMismatch> {
64        if (self.n_rows != other.n_rows()) || (self.n_cols != other.n_cols()) {
65            return Err(DimensionMismatch);
66        }
67        let mut new_board = BitBoardDyn::new(self.n_rows, self.n_cols);
68        new_board.board = self.board.clone() | other.board().to_bitvec();
69        Ok(new_board)
70    }
71
72    fn and(&self, other: &impl BitBoard) -> Result<Self, DimensionMismatch> {
73        if (self.n_rows != other.n_rows()) || (self.n_cols != other.n_cols()) {
74            return Err(DimensionMismatch);
75        }
76        let mut new_board = BitBoardDyn::new(self.n_rows, self.n_cols);
77        new_board.board = self.board.clone() & other.board().to_bitvec();
78        Ok(new_board)
79    }
80}
81
82impl BitBoardDyn {
83    /// Create a new empty board with `n_rows` and `n_cols`.
84    pub fn new(n_rows: usize, n_cols: usize) -> Self {
85        BitBoardDyn {
86            board: bitvec![0; n_rows * n_cols],
87            n_rows,
88            n_cols,
89        }
90    }
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96    use rstest::rstest;
97
98    #[test]
99    fn can_construct() {
100        let bb = BitBoardDyn::new(2, 2);
101        println!("{:?}", bb);
102    }
103
104    #[test]
105    #[should_panic(expected = "row cannot be greater than n_rows")]
106    fn row_too_big() {
107        let bb = BitBoardDyn::new(2, 2);
108        bb.index_of(10, 0);
109    }
110
111    #[test]
112    #[should_panic(expected = "col cannot be greater than n_col")]
113    fn col_too_big() {
114        let bb = BitBoardDyn::new(2, 2);
115        bb.index_of(0, 10);
116    }
117
118    #[rstest]
119    #[case(0, 0, 0)]
120    #[case(0, 1, 1)]
121    #[case(1, 0, 2)]
122    #[case(1, 1, 3)]
123    fn index_of(#[case] row: usize, #[case] col: usize, #[case] expected: usize) {
124        let bb = BitBoardDyn::new(2, 2);
125        assert_eq!(expected, bb.index_of(row, col))
126    }
127
128    #[rstest]
129    #[case(0, 0, 0)]
130    #[case(1, 0, 1)]
131    #[case(2, 0, 2)]
132    #[case(3, 0, 3)]
133    #[case(4, 0, 4)]
134    fn col_vec_index_of(#[case] row: usize, #[case] col: usize, #[case] expected: usize) {
135        let bb = BitBoardDyn::new(5, 1);
136        assert_eq!(expected, bb.index_of(row, col))
137    }
138
139    #[rstest]
140    #[case(0, 0, 0)]
141    #[case(0, 1, 1)]
142    #[case(0, 2, 2)]
143    #[case(0, 3, 3)]
144    #[case(0, 4, 4)]
145    fn row_vec_index_of(#[case] row: usize, #[case] col: usize, #[case] expected: usize) {
146        let bb = BitBoardDyn::new(1, 5);
147        assert_eq!(expected, bb.index_of(row, col))
148    }
149
150    #[rstest]
151    #[case(0)]
152    #[case(1)]
153    #[case(2)]
154    #[case(3)]
155    #[case(4)]
156    fn set_col(#[case] col: usize) {
157        let mut bb = BitBoardDyn::new(5, 5);
158        bb.set_col(col, true);
159        for ridx in 0..bb.n_rows {
160            for cidx in 0..bb.n_cols {
161                if cidx == col {
162                    assert!(bb.board[bb.index_of(ridx, cidx)])
163                } else {
164                    assert!(!bb.board[bb.index_of(ridx, cidx)])
165                }
166            }
167        }
168    }
169
170    #[rstest]
171    #[case(0)]
172    #[case(1)]
173    #[case(2)]
174    #[case(3)]
175    #[case(4)]
176    fn set_row(#[case] row: usize) {
177        let mut bb = BitBoardDyn::new(5, 5);
178        bb.set_row(row, true);
179        for ridx in 0..bb.n_rows {
180            for cidx in 0..bb.n_cols {
181                if ridx == row {
182                    assert!(bb.board[bb.index_of(ridx, cidx)])
183                } else {
184                    assert!(!bb.board[bb.index_of(ridx, cidx)])
185                }
186            }
187        }
188    }
189
190    #[test]
191    fn can_set_all_bits() {
192        // Create the board
193        let nr = 3;
194        let nc = 3;
195        let mut bb = BitBoardDyn::new(nr, nc);
196
197        bb.set(0, 0, true);
198
199        // Set each bit, and check that all bits are 1
200        for ridx in 0..nr {
201            for cidx in 0..nc {
202                bb.set(ridx, cidx, true);
203            }
204        }
205        assert!(bb.board.all());
206
207        // Unset each bit, and check that all bits are 0
208        for ridx in 0..nr {
209            for cidx in 0..nc {
210                bb.set(ridx, cidx, false);
211            }
212        }
213        assert!(bb.board.not_any());
214    }
215
216    #[rstest]
217    #[case(0, 0, BitBoardDyn { board: bitvec![0, 1, 1, 0], n_rows: 2, n_cols: 2 })]
218    #[case(0, 1, BitBoardDyn { board: bitvec![1, 0, 0, 1], n_rows: 2, n_cols: 2 })]
219    #[case(1, 0, BitBoardDyn { board: bitvec![1, 0, 0, 1], n_rows: 2, n_cols: 2 })]
220    #[case(1, 1, BitBoardDyn { board: bitvec![0, 1, 1, 0], n_rows: 2, n_cols: 2 })]
221    fn set_caridnal_neighbors_2x2(
222        #[case] row: usize,
223        #[case] col: usize,
224        #[case] expect: BitBoardDyn,
225    ) {
226        let mut bb = BitBoardDyn::new(2, 2);
227        bb.set_cardinal_neighbors(row, col, true);
228        assert_eq!(expect, bb);
229    }
230
231    #[rstest]
232    #[case(0, 0, BitBoardDyn { board: bitvec![0, 1, 0, 1, 0, 0, 0, 0, 0], n_rows: 3, n_cols: 3 })]
233    #[case(0, 1, BitBoardDyn { board: bitvec![1, 0, 1, 0, 1, 0, 0, 0, 0], n_rows: 3, n_cols: 3 })]
234    #[case(0, 2, BitBoardDyn { board: bitvec![0, 1, 0, 0, 0, 1, 0, 0, 0], n_rows: 3, n_cols: 3 })]
235    #[case(1, 0, BitBoardDyn { board: bitvec![1, 0, 0, 0, 1, 0, 1, 0, 0], n_rows: 3, n_cols: 3 })]
236    #[case(1, 1, BitBoardDyn { board: bitvec![0, 1, 0, 1, 0, 1, 0, 1, 0], n_rows: 3, n_cols: 3 })]
237    #[case(1, 2, BitBoardDyn { board: bitvec![0, 0, 1, 0, 1, 0, 0, 0, 1], n_rows: 3, n_cols: 3 })]
238    #[case(2, 0, BitBoardDyn { board: bitvec![0, 0, 0, 1, 0, 0, 0, 1, 0], n_rows: 3, n_cols: 3 })]
239    #[case(2, 1, BitBoardDyn { board: bitvec![0, 0, 0, 0, 1, 0, 1, 0, 1], n_rows: 3, n_cols: 3 })]
240    #[case(2, 2, BitBoardDyn { board: bitvec![0, 0, 0, 0, 0, 1, 0, 1, 0], n_rows: 3, n_cols: 3 })]
241    fn set_caridnal_neighbors_3x3(
242        #[case] row: usize,
243        #[case] col: usize,
244        #[case] expect: BitBoardDyn,
245    ) {
246        let mut bb = BitBoardDyn::new(3, 3);
247        bb.set_cardinal_neighbors(row, col, true);
248        assert_eq!(expect, bb);
249    }
250
251    #[rstest]
252    #[case(0, 0, BitBoardDyn { board: bitvec![0, 1, 1, 1], n_rows: 2, n_cols: 2 })]
253    #[case(0, 1, BitBoardDyn { board: bitvec![1, 0, 1, 1], n_rows: 2, n_cols: 2 })]
254    #[case(1, 0, BitBoardDyn { board: bitvec![1, 1, 0, 1], n_rows: 2, n_cols: 2 })]
255    #[case(1, 1, BitBoardDyn { board: bitvec![1, 1, 1, 0], n_rows: 2, n_cols: 2 })]
256    fn set_all_neighbors_2x2(#[case] row: usize, #[case] col: usize, #[case] expect: BitBoardDyn) {
257        let mut bb = BitBoardDyn::new(2, 2);
258        bb.set_all_neighbors(row, col, true);
259        assert_eq!(expect, bb);
260    }
261
262    #[rstest]
263    #[case(0, 0, BitBoardDyn { board: bitvec![0, 1, 0, 1, 1, 0, 0, 0, 0], n_rows: 3, n_cols: 3 })]
264    #[case(0, 1, BitBoardDyn { board: bitvec![1, 0, 1, 1, 1, 1, 0, 0, 0], n_rows: 3, n_cols: 3 })]
265    #[case(0, 2, BitBoardDyn { board: bitvec![0, 1, 0, 0, 1, 1, 0, 0, 0], n_rows: 3, n_cols: 3 })]
266    #[case(1, 0, BitBoardDyn { board: bitvec![1, 1, 0, 0, 1, 0, 1, 1, 0], n_rows: 3, n_cols: 3 })]
267    #[case(1, 1, BitBoardDyn { board: bitvec![1, 1, 1, 1, 0, 1, 1, 1, 1], n_rows: 3, n_cols: 3 })]
268    #[case(1, 2, BitBoardDyn { board: bitvec![0, 1, 1, 0, 1, 0, 0, 1, 1], n_rows: 3, n_cols: 3 })]
269    #[case(2, 0, BitBoardDyn { board: bitvec![0, 0, 0, 1, 1, 0, 0, 1, 0], n_rows: 3, n_cols: 3 })]
270    #[case(2, 1, BitBoardDyn { board: bitvec![0, 0, 0, 1, 1, 1, 1, 0, 1], n_rows: 3, n_cols: 3 })]
271    #[case(2, 2, BitBoardDyn { board: bitvec![0, 0, 0, 0, 1, 1, 0, 1, 0], n_rows: 3, n_cols: 3 })]
272    fn set_all_neighbors_3x3(#[case] row: usize, #[case] col: usize, #[case] expect: BitBoardDyn) {
273        let mut bb = BitBoardDyn::new(3, 3);
274        bb.set_all_neighbors(row, col, true);
275        assert_eq!(expect, bb);
276    }
277
278    #[rstest]
279    #[case(1, 1, 1, 2)]
280    #[case(2, 1, 1, 2)]
281    #[case(2, 1, 2, 7)]
282    fn and_dimension_mismatch(
283        #[case] b1r: usize,
284        #[case] b1c: usize,
285        #[case] b2r: usize,
286        #[case] b2c: usize,
287    ) {
288        let bb1 = BitBoardDyn::new(b1r, b1c);
289        let bb8 = BitBoardDyn::new(b2r, b2c);
290        assert!(bb1.and(&bb8).is_err());
291    }
292
293    #[rstest]
294    #[case(1, 1, 1, 2)]
295    #[case(2, 1, 1, 2)]
296    #[case(2, 1, 2, 7)]
297    fn or_dimension_mismatch(
298        #[case] b1r: usize,
299        #[case] b1c: usize,
300        #[case] b2r: usize,
301        #[case] b2c: usize,
302    ) {
303        let bb1 = BitBoardDyn::new(b1r, b1c);
304        let bb8 = BitBoardDyn::new(b2r, b2c);
305        assert!(bb1.or(&bb8).is_err());
306    }
307
308    #[rstest]
309    #[case(bitvec![0, 0, 0, 0], bitvec![0, 0, 0, 0], bitvec![0, 0, 0, 0])] // empty AND empty
310    #[case(bitvec![1, 1, 1, 1], bitvec![1, 1, 1, 1], bitvec![1, 1, 1, 1])] // full AND full
311    #[case(bitvec![0, 0, 0, 0], bitvec![1, 1, 1, 1], bitvec![0, 0, 0, 0])] // empty AND full
312    #[case(bitvec![1, 1, 1, 1], bitvec![1, 0, 0, 1], bitvec![1, 0, 0, 1])] // full AND partial
313    #[case(bitvec![1, 0, 1, 0], bitvec![0, 1, 0, 1], bitvec![0, 0, 0, 0])] // alternating patterns
314    #[case(bitvec![1, 1, 0, 0], bitvec![1, 0, 1, 0], bitvec![1, 0, 0, 0])] // partial patterns
315    fn and_operations(#[case] board1: BitVec, #[case] board2: BitVec, #[case] expected: BitVec) {
316        let bb1 = BitBoardDyn {
317            board: board1,
318            n_rows: 2,
319            n_cols: 2,
320        };
321        let bb2 = BitBoardDyn {
322            board: board2,
323            n_rows: 2,
324            n_cols: 2,
325        };
326
327        let result = bb1.and(&bb2).unwrap();
328        assert_eq!(result.board().to_bitvec(), expected);
329        assert_eq!(result.n_rows(), 2);
330        assert_eq!(result.n_cols(), 2);
331    }
332
333    #[rstest]
334    #[case(bitvec![0, 0, 0, 0], bitvec![0, 0, 0, 0], bitvec![0, 0, 0, 0])] // empty OR empty
335    #[case(bitvec![1, 1, 1, 1], bitvec![1, 1, 1, 1], bitvec![1, 1, 1, 1])] // full OR full
336    #[case(bitvec![0, 0, 0, 0], bitvec![1, 1, 1, 1], bitvec![1, 1, 1, 1])] // empty OR full
337    #[case(bitvec![0, 0, 0, 0], bitvec![1, 0, 0, 1], bitvec![1, 0, 0, 1])] // empty OR partial
338    #[case(bitvec![1, 0, 1, 0], bitvec![0, 1, 0, 1], bitvec![1, 1, 1, 1])] // alternating patterns
339    #[case(bitvec![1, 1, 0, 0], bitvec![0, 0, 1, 1], bitvec![1, 1, 1, 1])] // complementary patterns
340    #[case(bitvec![1, 0, 0, 1], bitvec![0, 1, 1, 0], bitvec![1, 1, 1, 1])] // diagonal patterns
341    fn or_operations(#[case] board1: BitVec, #[case] board2: BitVec, #[case] expected: BitVec) {
342        let bb1 = BitBoardDyn {
343            board: board1,
344            n_rows: 2,
345            n_cols: 2,
346        };
347        let bb2 = BitBoardDyn {
348            board: board2,
349            n_rows: 2,
350            n_cols: 2,
351        };
352
353        let result = bb1.or(&bb2).unwrap();
354        assert_eq!(result.board().to_bitvec(), expected);
355        assert_eq!(result.n_rows(), 2);
356        assert_eq!(result.n_cols(), 2);
357    }
358
359    #[test]
360    fn and_or_larger_boards() {
361        let mut bb1 = BitBoardDyn::new(3, 3);
362        bb1.set_row(0, true); // First row all true
363        bb1.set(2, 2, true); // Bottom right corner
364
365        let mut bb2 = BitBoardDyn::new(3, 3);
366        bb2.set_col(0, true); // First column all true
367        bb2.set(1, 1, true); // Center
368
369        // Test AND operation
370        let and_result = bb1.and(&bb2).unwrap();
371        assert!(and_result.board()[0]); // (0,0) - both have true
372        assert!(!and_result.board()[1]); // (0,1) - only bb1 has true
373        assert!(!and_result.board()[2]); // (0,2) - only bb1 has true
374        assert!(!and_result.board()[3]); // (1,0) - only bb2 has true
375        assert!(!and_result.board()[4]); // (1,1) - only bb2 has true
376        assert!(!and_result.board()[6]); // (2,0) - only bb2 has true
377
378        // Test OR operation
379        let or_result = bb1.or(&bb2).unwrap();
380        assert!(or_result.board()[0]); // (0,0) - both have true
381        assert!(or_result.board()[1]); // (0,1) - bb1 has true
382        assert!(or_result.board()[2]); // (0,2) - bb1 has true
383        assert!(or_result.board()[3]); // (1,0) - bb2 has true
384        assert!(or_result.board()[4]); // (1,1) - bb2 has true
385        assert!(!or_result.board()[5]); // (1,2) - neither has true
386        assert!(or_result.board()[6]); // (2,0) - bb2 has true
387        assert!(!or_result.board()[7]); // (2,1) - neither has true
388        assert!(or_result.board()[8]); // (2,2) - bb1 has true
389    }
390
391    #[test]
392    fn and_or_preserve_original_boards() {
393        let mut bb1 = BitBoardDyn::new(2, 2);
394        bb1.set(0, 0, true);
395        let bb1_original = bb1.clone();
396
397        let mut bb2 = BitBoardDyn::new(2, 2);
398        bb2.set(1, 1, true);
399        let bb2_original = bb2.clone();
400
401        // Perform operations
402        let _and_result = bb1.and(&bb2).unwrap();
403        let _or_result = bb1.or(&bb2).unwrap();
404
405        // Original boards should be unchanged
406        assert_eq!(bb1, bb1_original);
407        assert_eq!(bb2, bb2_original);
408    }
409}
bit_board/bitboarddyn.rs

bit_board/
bitboarddyn.rs
