board_game_geom/
lib.rs

1//! Geometric types for 2D lattice-shaped puzzles.
2
3use std::ops::{Add, Index, IndexMut, Mul, Neg, Range, Sub};
4
5/// A two-dimensional lattice point.
6#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
7pub struct Point(pub i32, pub i32);
8
9/// A size of a rectangle.
10#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
11pub struct Size(pub i32, pub i32);
12
13/// A difference between two `Point`s.
14///
15/// `Point(y0, x0)` - `Point(y1, x1) == `Move(y0 - y1, x0 - x1)`
16#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
17pub struct Move(pub i32, pub i32);
18
19/// A 2x2 rotation matrix.
20///
21/// `Rotation(yy, yx, xy, xx) * Move(y, x) == Move(yy*y + yx*x, xy*y + xx*x)`
22#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
23pub struct Rotation(i32, i32, i32, i32);
24
25/// An upward `Move` vector.
26pub const MOVE_UP: Move = Move(-1, 0);
27
28/// A rightward `Move` vector.
29pub const MOVE_RIGHT: Move = Move(0, 1);
30
31/// A downward `Move` vector.
32pub const MOVE_DOWN: Move = Move(1, 0);
33
34/// A leftward `Move` vector.
35pub const MOVE_LEFT: Move = Move(0, -1);
36
37/// `Move` vectors that is toward four adjacent points.
38pub const MOVE_ALL_DIRECTIONS: [Move; 4] = [MOVE_UP, MOVE_RIGHT, MOVE_DOWN, MOVE_LEFT];
39
40/// `Move` vectors that is toward eight adjacent points.
41pub const MOVE_ALL_ADJACENTS: [Move; 8] = [
42    MOVE_UP,
43    Move(-1, 1),
44    MOVE_RIGHT,
45    Move(1, 1),
46    MOVE_DOWN,
47    Move(1, -1),
48    MOVE_LEFT,
49    Move(-1, -1),
50];
51
52impl Add<Move> for Point {
53    type Output = Point;
54
55    #[inline]
56    fn add(self, other: Move) -> Point {
57        Point(self.0 + other.0, self.1 + other.1)
58    }
59}
60
61impl Sub<Point> for Point {
62    type Output = Move;
63
64    #[inline]
65    fn sub(self, other: Point) -> Move {
66        Move(self.0 - other.0, self.1 - other.1)
67    }
68}
69
70impl Add<Move> for Move {
71    type Output = Move;
72
73    #[inline]
74    fn add(self, other: Move) -> Move {
75        Move(self.0 + other.0, self.1 + other.1)
76    }
77}
78
79impl Sub<Move> for Move {
80    type Output = Move;
81
82    #[inline]
83    fn sub(self, other: Move) -> Move {
84        Move(self.0 - other.0, self.1 - other.1)
85    }
86}
87
88impl Neg for Move {
89    type Output = Move;
90
91    #[inline]
92    fn neg(self) -> Move {
93        Move(-self.0, -self.1)
94    }
95}
96
97impl Mul<i32> for Move {
98    type Output = Move;
99
100    #[inline]
101    fn mul(self, other: i32) -> Move {
102        Move(self.0 * other, self.1 * other)
103    }
104}
105
106/// A 0-degree `Rotation` to the left (counterclockwise).
107pub const ROT_CCW0: Rotation = Rotation(1, 0, 0, 1);
108
109/// A 90-degree `Rotation` to the left (counterclockwise).
110pub const ROT_CCW90: Rotation = Rotation(0, -1, 1, 0);
111
112/// A 180-degree `Rotation` to the left (counterclockwise).
113pub const ROT_CCW180: Rotation = Rotation(-1, 0, 0, -1);
114
115/// A 270-degree `Rotation` to the left (counterclockwise).
116pub const ROT_CCW270: Rotation = Rotation(0, 1, -1, 0);
117
118/// Flip horizontal.
119pub const ROT_H_FLIP: Rotation = Rotation(1, 0, 0, -1);
120
121/// Flip vertical.
122pub const ROT_V_FLIP: Rotation = Rotation(-1, 0, 0, 1);
123
124impl Mul<Rotation> for Rotation {
125    type Output = Rotation;
126
127    #[inline]
128    fn mul(self, other: Rotation) -> Rotation {
129        Rotation(
130            self.0 * other.0 + self.1 * other.2,
131            self.0 * other.1 + self.1 * other.3,
132            self.2 * other.0 + self.3 * other.2,
133            self.2 * other.1 + self.3 * other.3,
134        )
135    }
136}
137
138impl Mul<Move> for Rotation {
139    type Output = Move;
140
141    #[inline]
142    fn mul(self, other: Move) -> Move {
143        Move(
144            self.0 * other.0 + self.1 * other.1,
145            self.2 * other.0 + self.3 * other.1,
146        )
147    }
148}
149
150/// An ID identifying a cell in lattice rectangle.
151#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
152pub struct CellId(usize);
153
154/// An ID being given to cells on outside the rectangle.
155pub const CELL_ID_OUTSIDE: CellId = CellId(0);
156
157impl CellId {
158    /// Creates a new `CellId` from an ID.
159    #[inline]
160    pub fn new(id: usize) -> CellId {
161        CellId(id)
162    }
163
164    /// Gets an ID of the cell.
165    #[inline]
166    pub fn id(self) -> usize {
167        self.0
168    }
169
170    /// Returns if the cell is on outside of the rectangle.
171    #[inline]
172    pub fn is_outside(self) -> bool {
173        self == CELL_ID_OUTSIDE
174    }
175}
176
177/// A representative `Point` of points on outside the rectangle.
178const OUTSIDE_POINT: Point = Point(-1, -1);
179
180/// A rectangle area.
181pub trait Geom {
182    /// Returns the rectangle's size.
183    fn size(&self) -> Size;
184
185    /// Returns the number of the rectangle's rows.
186    #[inline]
187    fn row(&self) -> i32 {
188        self.size().0
189    }
190
191    /// Returns the number of the rectangle's columns.
192    #[inline]
193    fn column(&self) -> i32 {
194        self.size().1
195    }
196
197    /// Returns the cell length which is contained in the rectangle.
198    #[inline]
199    fn cell_len(&self) -> usize {
200        (self.row() * self.column() + 1) as usize
201    }
202
203    /// Returns true if the point is contained in the rectangle.
204    #[inline]
205    fn contains(&self, p: Point) -> bool {
206        let size = self.size();
207        0 <= p.0 && p.0 < size.0 && 0 <= p.1 && p.1 < size.1
208    }
209
210    /// Convert a point to a corresponding cell ID.
211    #[inline]
212    fn point_to_cellid(&self, p: Point) -> CellId {
213        if self.contains(p) {
214            CellId::new((p.0 * self.column() + p.1 + 1) as usize)
215        } else {
216            CELL_ID_OUTSIDE
217        }
218    }
219
220    /// Convert a cell ID to a corresponding point.
221    #[inline]
222    fn cellid_to_point(&self, id: CellId) -> Point {
223        if id.is_outside() {
224            OUTSIDE_POINT
225        } else {
226            let idx = id.id() - 1;
227            Point((idx as i32) / self.column(), (idx as i32) % self.column())
228        }
229    }
230
231    /// Returns an iterator iterating all points.
232    #[inline]
233    fn points(&self) -> Points {
234        if self.row() > 0 && self.column() > 0 {
235            Points {
236                point: Some(Point(0, 0)),
237                size: self.size(),
238            }
239        } else {
240            Points {
241                point: None,
242                size: self.size(),
243            }
244        }
245    }
246
247    /// Returns an iterator iterating all points in the row.
248    #[inline]
249    fn points_in_row(&self, row: i32) -> PointsInRow {
250        PointsInRow {
251            row,
252            columns: 0..self.column(),
253        }
254    }
255
256    /// Returns an iterator iterating all points in the column.
257    #[inline]
258    fn points_in_column(&self, column: i32) -> PointsInColumn {
259        PointsInColumn {
260            column,
261            rows: 0..self.row(),
262        }
263    }
264}
265
266/// An iterator iterating all points in the rectangle.
267#[derive(Copy, Clone, Debug)]
268pub struct Points {
269    point: Option<Point>,
270    size: Size,
271}
272
273impl Iterator for Points {
274    type Item = Point;
275
276    #[inline]
277    fn next(&mut self) -> Option<Point> {
278        if let Some(cur) = self.point {
279            let mut next = cur;
280            let mut end = false;
281            next.1 += 1;
282            if next.1 >= self.size.1 {
283                next.0 += 1;
284                next.1 = 0;
285                if next.0 >= self.size.0 {
286                    end = true;
287                }
288            }
289            if !end {
290                self.point = Some(next);
291            } else {
292                self.point = None;
293            }
294            return Some(cur);
295        }
296        None
297    }
298}
299
300/// An iterator iterating all points in a row of the rectangle.
301#[derive(Clone, Debug)]
302pub struct PointsInRow {
303    row: i32,
304    columns: Range<i32>,
305}
306
307impl Iterator for PointsInRow {
308    type Item = Point;
309
310    #[inline]
311    fn next(&mut self) -> Option<Point> {
312        if let Some(c) = self.columns.next() {
313            Some(Point(self.row, c))
314        } else {
315            None
316        }
317    }
318}
319
320/// An iterator iterating all points in a column of the rectangle.
321#[derive(Clone, Debug)]
322pub struct PointsInColumn {
323    rows: Range<i32>,
324    column: i32,
325}
326
327impl Iterator for PointsInColumn {
328    type Item = Point;
329
330    #[inline]
331    fn next(&mut self) -> Option<Point> {
332        if let Some(r) = self.rows.next() {
333            Some(Point(r, self.column))
334        } else {
335            None
336        }
337    }
338}
339
340/// A table that stores values for each cells.
341#[derive(Clone, Debug, Eq, PartialEq)]
342pub struct Table<T> {
343    size: Size,
344    data: Vec<T>,
345}
346
347impl<T> Table<T> {
348    /// Creates a new table with data.
349    #[inline]
350    pub fn new(size: Size, outside: T, mut data: Vec<T>) -> Table<T> {
351        assert_eq!((size.0 * size.1) as usize, data.len());
352        data.insert(0, outside);
353        Table { size, data }
354    }
355
356    /// Creates a new empty table.
357    #[inline]
358    pub fn new_empty(size: Size, outside: T, init: T) -> Table<T>
359    where
360        T: Clone,
361    {
362        let data = vec![init; (size.0 * size.1) as usize];
363        Table::new(size, outside, data)
364    }
365}
366
367impl<T> Geom for Table<T> {
368    #[inline]
369    fn size(&self) -> Size {
370        self.size
371    }
372}
373
374impl<T> Index<Point> for Table<T> {
375    type Output = T;
376
377    #[inline]
378    fn index(&self, p: Point) -> &T {
379        let idx = self.point_to_cellid(p).id();
380        &self.data[idx]
381    }
382}
383
384impl<T> IndexMut<Point> for Table<T> {
385    #[inline]
386    fn index_mut(&mut self, p: Point) -> &mut T {
387        let idx = self.point_to_cellid(p).id();
388        &mut self.data[idx]
389    }
390}
391
392#[cfg(test)]
393mod tests {
394    use super::*;
395
396    struct Rect(Size);
397    impl Geom for Rect {
398        fn size(&self) -> Size {
399            self.0
400        }
401    }
402
403    #[test]
404    fn points() {
405        let pts = [
406            Point(0, 0),
407            Point(0, 1),
408            Point(0, 2),
409            Point(1, 0),
410            Point(1, 1),
411            Point(1, 2),
412            Point(2, 0),
413            Point(2, 1),
414            Point(2, 2),
415            Point(3, 0),
416            Point(3, 1),
417            Point(3, 2),
418        ];
419        let rect = Rect(Size(4, 3));
420        assert_eq!(&pts[..], &rect.points().collect::<Vec<_>>()[..]);
421    }
422
423    #[test]
424    fn rotate_mat() {
425        let mat = [ROT_CCW0, ROT_CCW90, ROT_CCW180, ROT_CCW270];
426        for i in 0..mat.len() {
427            for j in 0..mat.len() {
428                assert_eq!(mat[(i + j) % mat.len()], mat[i] * mat[j]);
429            }
430        }
431    }
432
433    #[test]
434    fn rotate_point() {
435        let mat = [ROT_CCW0, ROT_CCW90, ROT_CCW180, ROT_CCW270];
436        let vec = [
437            [MOVE_UP, MOVE_LEFT, MOVE_DOWN, MOVE_RIGHT],
438            [
439                MOVE_UP + MOVE_RIGHT,
440                MOVE_LEFT + MOVE_UP,
441                MOVE_DOWN + MOVE_LEFT,
442                MOVE_RIGHT + MOVE_DOWN,
443            ],
444        ];
445        for i in 0..mat.len() {
446            for v in &vec {
447                for j in 0..v.len() {
448                    assert_eq!(v[(i + j) % v.len()], mat[i] * v[j]);
449                }
450            }
451        }
452    }
453}
board_game_geom/lib.rs

board_game_geom/
lib.rs
