vec2d/
lib.rs

1// Copyright 2015 Nicholas Bishop
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Vec2D is a very simple 2D container for storing rectangular data
16
17#![deny(missing_docs)]
18
19#[cfg(feature = "serde_support")]
20extern crate serde;
21#[cfg(feature = "serde_support")]
22use serde::{Deserialize, Serialize};
23
24/// 2D coordinate
25#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
26#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq)]
27pub struct Coord {
28    /// X component
29    pub x: usize,
30
31    /// Y component
32    pub y: usize,
33}
34
35/// Rectangle defined by inclusive minimum and maximum coordinates
36#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
37#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq)]
38pub struct Rect {
39    /// Minimum coordinate (inclusive)
40    min_coord: Coord,
41
42    /// Maximum coordinate (inclusive)
43    max_coord: Coord,
44}
45
46/// Rectangle dimensions
47#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
48#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq)]
49pub struct Size {
50    /// Width of rectangle
51    pub width: usize,
52    /// Height of rectangle
53    pub height: usize,
54}
55
56/// Container for 2D data
57#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
58#[derive(Clone, Debug, Hash, Eq, PartialEq)]
59pub struct Vec2D<T> {
60    elems: Vec<T>,
61    size: Size,
62}
63
64/// Iterator over a rectangle within a Vec2D
65pub struct RectIter<'a, Elem: 'a> {
66    grid: std::marker::PhantomData<&'a Vec2D<Elem>>,
67
68    rect: Rect,
69    cur_elem: *const Elem,
70    cur_coord: Coord,
71    stride: isize,
72}
73
74/// Mutable iterator over a rectangle within a Vec2D
75pub struct RectIterMut<'a, Elem: 'a> {
76    grid: std::marker::PhantomData<&'a mut Vec2D<Elem>>,
77
78    rect: Rect,
79    cur_elem: *mut Elem,
80    cur_coord: Coord,
81    stride: isize,
82}
83
84impl Coord {
85    /// Create a coordinate at (x, y)
86    pub fn new(x: usize, y: usize) -> Coord {
87        Coord { x, y }
88    }
89}
90
91impl std::ops::Add for Coord {
92    type Output = Coord;
93
94    fn add(self, other: Coord) -> Coord {
95        Coord::new(self.x + other.x, self.y + other.y)
96    }
97}
98
99impl Rect {
100    /// Calculate rectangle width
101    pub fn width(&self) -> usize {
102        self.max_coord.x - self.min_coord.x + 1
103    }
104
105    /// Calculate rectangle height
106    pub fn height(&self) -> usize {
107        self.max_coord.y - self.min_coord.y + 1
108    }
109
110    /// Calculate rectangle size
111    pub fn size(&self) -> Size {
112        Size::new(self.width(), self.height())
113    }
114
115    /// Return true if the coordinate is between `min_coord` and
116    /// `max_coord` (inclusive).
117    pub fn contains_coord(&self, coord: Coord) -> bool {
118        coord.x >= self.min_coord.x
119            && coord.x <= self.max_coord.x
120            && coord.y >= self.min_coord.y
121            && coord.y <= self.max_coord.y
122    }
123}
124
125impl Size {
126    /// Create a 2D size of (width, height)
127    pub fn new(width: usize, height: usize) -> Size {
128        Size { width, height }
129    }
130
131    /// width * height
132    pub fn area(&self) -> usize {
133        self.width * self.height
134    }
135
136    /// Return true if the coordinate fits within self's width and
137    /// height, false otherwise.
138    pub fn contains_coord(&self, coord: Coord) -> bool {
139        coord.x < self.width && coord.y < self.height
140    }
141
142    /// Create a rectangle starting at (0, 0) with `self`'s size.
143    pub fn rect(&self) -> Rect {
144        Rect {
145            min_coord: Coord::new(0, 0),
146            max_coord: Coord::new(self.width - 1, self.height - 1),
147        }
148    }
149}
150
151impl<Elem: Clone> Vec2D<Elem> {
152    /// Create a Vec2D with the given `size`. All elements are
153    /// initialized as copies of the `example` element.
154    ///
155    /// ```
156    /// # use vec2d::{Vec2D, Size};
157    /// let vector = Vec2D::from_example(Size::new(10, 10), &42);
158    /// for (_coord, &item) in vector.iter() {
159    ///     assert_eq!(item, 42);
160    /// }
161    /// ```
162    pub fn from_example(size: Size, example: &Elem) -> Vec2D<Elem> {
163        Vec2D {
164            elems: vec![example.clone(); size.area()],
165            size,
166        }
167    }
168
169    /// Resize in-place so that `size()` is equal to `new_size`
170    pub fn resize(&mut self, new_size: Size, value: Elem) {
171        self.elems.resize(new_size.area(), value);
172        self.size = new_size;
173    }
174}
175
176impl<Elem> Vec2D<Elem> {
177    /// Create a Vec2D with the given `size`. The contents are set to
178    /// `src`. None is returned if the `size` does not match the
179    /// length of `src`.
180    pub fn from_vec(size: Size, src: Vec<Elem>) -> Option<Vec2D<Elem>> {
181        if size.area() == src.len() {
182            Some(Vec2D { elems: src, size })
183        } else {
184            None
185        }
186    }
187
188    /// Returns element at the given coord or `None` if the coord is
189    /// outside the Vec2D
190    ///
191    /// # Example
192    ///
193    /// ```
194    /// # extern crate vec2d; use vec2d::*;
195    /// # fn main () {
196    /// let v = Vec2D::from_vec (
197    ///   Size { width: 3, height: 3 },
198    ///   vec!['a','b','c','d','e','f','g','h','i']
199    /// ).unwrap();
200    /// assert_eq!(v.get (Coord { x: 1, y: 0 }), Some(&'b'));
201    /// assert_eq!(v.get (Coord { x: 1, y: 2 }), Some(&'h'));
202    /// assert_eq!(v.get (Coord { x: 3, y: 0 }), None);
203    /// # }
204    /// ```
205    pub fn get(&self, coord: Coord) -> Option<&Elem> {
206        if self.size.contains_coord(coord) {
207            // column major coords
208            let i = coord.y * self.size.width + coord.x;
209            return Some(&self.elems[i]);
210        }
211        None
212    }
213
214    /// Returns a mutable reference to the element at the given coord or
215    /// `None` if the coord is outside the Vec2D
216    ///
217    /// # Example
218    ///
219    /// ```
220    /// # extern crate vec2d; use vec2d::*;
221    /// # fn main () {
222    /// let mut v = Vec2D::from_vec (
223    ///   Size { width: 3, height: 3 },
224    ///   vec!['a','b','c','d','e','f','g','h','i']
225    /// ).unwrap();
226    /// assert_eq!(v.get_mut (Coord { x: 1, y: 0 }), Some(&mut 'b'));
227    /// assert_eq!(v.get_mut (Coord { x: 1, y: 2 }), Some(&mut 'h'));
228    /// assert_eq!(v.get_mut (Coord { x: 3, y: 0 }), None);
229    /// # }
230    /// ```
231    pub fn get_mut(&mut self, coord: Coord) -> Option<&mut Elem> {
232        if self.size.contains_coord(coord) {
233            // column major coords
234            let i = coord.y * self.size.width + coord.x;
235            return Some(&mut self.elems[i]);
236        }
237        None
238    }
239
240    /// Shortcut for self.size.rect()
241    pub fn rect(&self) -> Rect {
242        self.size.rect()
243    }
244
245    /// Width and height
246    pub fn size(&self) -> Size {
247        self.size
248    }
249
250    fn stride(&self, rect: &Rect) -> isize {
251        (self.size.width + 1 - rect.width()) as isize
252    }
253
254    /// Calculate pointer offset for `start` element.
255    fn start_offset(&self, start: Coord) -> isize {
256        debug_assert!(self.size.contains_coord(start));
257        (start.y * self.size.width + start.x) as isize
258    }
259
260    /// Iterator over the entire Vec2D.
261    pub fn iter(&self) -> RectIter<Elem> {
262        self.rect_iter(self.size.rect()).unwrap()
263    }
264
265    /// Create an iterator over a rectangular region of the
266    /// Vec2D. None is returned if the given `rect` does not fit
267    /// entirely within the Vec2D.
268    pub fn rect_iter(&self, rect: Rect) -> Option<RectIter<Elem>> {
269        self.rect_iter_at(rect, rect.min_coord)
270    }
271
272    /// Create an iterator over a rectangular region of the Vec2D with
273    /// the `start` coord. None is returned if the given `rect` does
274    /// not fit entirely within the Vec2D or if the `start` coord is
275    /// not within `rect`.
276    pub fn rect_iter_at(&self, rect: Rect, start: Coord) -> Option<RectIter<Elem>> {
277        if self.size.contains_coord(rect.max_coord) && rect.contains_coord(start) {
278            Some(RectIter {
279                grid: std::marker::PhantomData,
280                stride: self.stride(&rect),
281                cur_elem: unsafe { self.elems.as_ptr().offset(self.start_offset(start)) },
282                rect,
283                cur_coord: start,
284            })
285        } else {
286            None
287        }
288    }
289
290    /// Mutable iterater over the entire Vec2D.
291    pub fn iter_mut(&mut self) -> RectIterMut<Elem> {
292        let rect = self.size.rect();
293        self.rect_iter_mut(rect).unwrap()
294    }
295
296    /// Create a mutable iterator over a rectangular region of the
297    /// Vec2D. None is returned if the given `rect` does not fit
298    /// entirely within the Vec2D.
299    pub fn rect_iter_mut(&mut self, rect: Rect) -> Option<RectIterMut<Elem>> {
300        self.rect_iter_mut_at(rect, rect.min_coord)
301    }
302
303    /// Create a mutable iterator over a rectangular region of the
304    /// Vec2D with the `start` coord. None is returned if the given
305    /// `rect` does not fit entirely within the Vec2D or if the
306    /// `start` coord is not within `rect`.
307    pub fn rect_iter_mut_at(&mut self, rect: Rect, start: Coord) -> Option<RectIterMut<Elem>> {
308        if self.size.contains_coord(rect.max_coord) && rect.contains_coord(start) {
309            Some(RectIterMut {
310                grid: std::marker::PhantomData,
311                stride: self.stride(&rect),
312                cur_elem: unsafe { self.elems.as_mut_ptr().offset(self.start_offset(start)) },
313                rect,
314                cur_coord: start,
315            })
316        } else {
317            None
318        }
319    }
320}
321
322impl<'a, Elem> Iterator for RectIter<'a, Elem> {
323    type Item = (Coord, &'a Elem);
324
325    fn next(&mut self) -> Option<Self::Item> {
326        if self.cur_coord.y <= self.rect.max_coord.y {
327            let result = (self.cur_coord, unsafe { &*self.cur_elem });
328
329            self.cur_coord.x += 1;
330            if self.cur_coord.x <= self.rect.max_coord.x {
331                unsafe {
332                    self.cur_elem = self.cur_elem.offset(1);
333                }
334            } else {
335                self.cur_coord.x = self.rect.min_coord.x;
336                self.cur_coord.y += 1;
337                unsafe {
338                    self.cur_elem = self.cur_elem.offset(self.stride);
339                }
340            }
341            Some(result)
342        } else {
343            None
344        }
345    }
346}
347
348impl<'a, Elem> Iterator for RectIterMut<'a, Elem> {
349    type Item = (Coord, &'a mut Elem);
350
351    fn next(&mut self) -> Option<Self::Item> {
352        if self.cur_coord.y <= self.rect.max_coord.y {
353            let result = (self.cur_coord, unsafe { &mut *self.cur_elem });
354
355            self.cur_coord.x += 1;
356            if self.cur_coord.x <= self.rect.max_coord.x {
357                unsafe {
358                    self.cur_elem = self.cur_elem.offset(1);
359                }
360            } else {
361                self.cur_coord.x = self.rect.min_coord.x;
362                self.cur_coord.y += 1;
363                unsafe {
364                    self.cur_elem = self.cur_elem.offset(self.stride);
365                }
366            }
367            Some(result)
368        } else {
369            None
370        }
371    }
372}
373
374impl Rect {
375    /// Create a new Rect defined by inclusive minimum and maximum
376    /// coordinates. If min_coord is greater than max_coord on either
377    /// axis then None is returned.
378    pub fn new(min_coord: Coord, max_coord: Coord) -> Option<Rect> {
379        if min_coord.x <= max_coord.x && min_coord.y <= max_coord.y {
380            Some(Rect {
381                min_coord,
382                max_coord,
383            })
384        } else {
385            None
386        }
387    }
388}
389
390#[cfg(test)]
391#[cfg(feature = "serde_support")]
392mod serde_derive_test {
393    use super::*;
394    use serde::de::DeserializeOwned;
395    use std::{cmp::PartialEq, fmt::Debug};
396
397    fn test_serde<T: Serialize + DeserializeOwned + Debug + PartialEq>(test_subject: &T) {
398        let serialized = serde_json::to_string(test_subject).unwrap();
399        let deserialized = serde_json::from_str::<T>(&serialized).unwrap();
400
401        assert_eq!(&deserialized, test_subject);
402    }
403
404    #[test]
405    fn test_coord_serde() {
406        let coord = Coord::new(5, 10);
407        test_serde(&coord);
408    }
409
410    #[test]
411    fn test_size_serde() {
412        let size = Size::new(5, 10);
413
414        test_serde(&size);
415    }
416
417    #[test]
418    fn test_rect_serde() {
419        let rect = Rect::new(Coord::new(0, 0), Coord::new(4, 2)).unwrap();
420
421        test_serde(&rect);
422    }
423
424    #[test]
425    fn test_vec2d_serde() {
426        let vec: Vec<i32> = (0..16).collect();
427        let vec2d = Vec2D::from_vec(Size::new(4, 4), vec).unwrap();
428
429        test_serde(&vec2d);
430    }
431}
432
433#[cfg(test)]
434mod test {
435    use super::*;
436
437    #[test]
438    fn test_coord() {
439        let coord = Coord::new(1, 2);
440        assert_eq!(coord.x, 1);
441        assert_eq!(coord.y, 2);
442    }
443
444    #[test]
445    fn test_coord_add() {
446        let a = Coord::new(1, 2);
447        let b = Coord::new(5, 9);
448        assert_eq!(a + b, Coord::new(6, 11));
449    }
450
451    #[test]
452    fn test_rect() {
453        let rect = Rect::new(Coord::new(1, 2), Coord::new(5, 3)).unwrap();
454        assert_eq!(rect.width(), 5);
455        assert_eq!(rect.height(), 2);
456
457        assert_eq!(rect.width(), rect.size().width);
458        assert_eq!(rect.height(), rect.size().height);
459
460        assert_eq!(rect.contains_coord(Coord::new(0, 0)), false);
461        assert_eq!(rect.contains_coord(Coord::new(4, 3)), true);
462    }
463
464    #[test]
465    fn test_bad_rect() {
466        assert_eq!(
467            Rect::new(Coord::new(2, 1), Coord::new(1, 1)).is_none(),
468            true
469        );
470        assert_eq!(
471            Rect::new(Coord::new(1, 2), Coord::new(1, 1)).is_none(),
472            true
473        );
474    }
475
476    #[test]
477    fn test_size() {
478        let size = Size::new(3, 2);
479        assert_eq!(size.width, 3);
480        assert_eq!(size.height, 2);
481
482        assert_eq!(size.area(), 6);
483
484        assert_eq!(size.contains_coord(Coord::new(1, 1)), true);
485        assert_eq!(size.contains_coord(Coord::new(4, 1)), false);
486        assert_eq!(size.contains_coord(Coord::new(1, 3)), false);
487
488        let rect = size.rect();
489        assert_eq!(rect.min_coord, Coord::new(0, 0));
490        assert_eq!(rect.max_coord, Coord::new(2, 1));
491    }
492
493    #[test]
494    fn test_rect_iter_mut() {
495        let elems = vec![1, 2, 3, 4];
496        let mut grid = Vec2D::from_vec(Size::new(2, 2), elems).unwrap();
497        let rect = Rect::new(Coord::new(0, 0), Coord::new(1, 1)).unwrap();
498
499        let mut actual_coords = Vec::new();
500        for (coord, elem) in grid.rect_iter_mut(rect).unwrap() {
501            *elem = -(*elem);
502            actual_coords.push((coord.x, coord.y));
503        }
504        assert_eq!(actual_coords, [(0, 0), (1, 0), (0, 1), (1, 1)]);
505        assert_eq!(grid.elems, [-1, -2, -3, -4]);
506    }
507
508    #[test]
509    fn test_two_iterators() {
510        let size = Size::new(2, 1);
511        let v = Vec2D::from_vec(size, vec![0, 1]).unwrap();
512
513        let iter1 = v.rect_iter(size.rect()).unwrap();
514        let iter2 = v.rect_iter(size.rect()).unwrap();
515
516        for ((coord1, elem1), (coord2, elem2)) in iter1.zip(iter2) {
517            assert_eq!(coord1, coord2);
518            assert_eq!(elem1, elem2);
519        }
520    }
521
522    #[test]
523    fn test_rect_iter_at() {
524        let size = Size::new(1, 2);
525        let v = Vec2D::from_vec(size, vec![0, 1]).unwrap();
526
527        let start = Coord::new(0, 1);
528        let mut iter = v.rect_iter_at(size.rect(), start).unwrap();
529        let (coord, elem) = iter.next().unwrap();
530        assert_eq!((coord, *elem), (start, 1));
531        assert_eq!(iter.next().is_none(), true);
532    }
533}