|
13917
|
1 |
extern crate vec2d;
|
|
|
2 |
|
|
|
3 |
use std::cmp;
|
|
|
4 |
|
|
|
5 |
pub struct Land2D<T> {
|
|
|
6 |
pixels: vec2d::Vec2D<T>,
|
|
|
7 |
width_mask: usize,
|
|
|
8 |
height_mask: usize,
|
|
|
9 |
}
|
|
|
10 |
|
|
13924
|
11 |
impl<T: Default + Copy + PartialEq> Land2D<T> {
|
|
13917
|
12 |
pub fn new(width: usize, height: usize) -> Self {
|
|
|
13 |
assert!(width.is_power_of_two());
|
|
|
14 |
assert!(height.is_power_of_two());
|
|
|
15 |
|
|
|
16 |
Self {
|
|
|
17 |
pixels: vec2d::Vec2D::new(width, height, T::default()),
|
|
|
18 |
width_mask: !(width - 1),
|
|
|
19 |
height_mask: !(height - 1),
|
|
|
20 |
}
|
|
|
21 |
}
|
|
|
22 |
|
|
|
23 |
#[inline]
|
|
13924
|
24 |
pub fn width(&self) -> usize {
|
|
|
25 |
self.pixels.width()
|
|
|
26 |
}
|
|
|
27 |
|
|
|
28 |
#[inline]
|
|
|
29 |
pub fn height(&self) -> usize {
|
|
|
30 |
self.pixels.height()
|
|
|
31 |
}
|
|
|
32 |
|
|
|
33 |
#[inline]
|
|
|
34 |
pub fn is_valid_coordinate(&self, x: i32, y: i32) -> bool {
|
|
13917
|
35 |
(x as usize & self.width_mask) == 0 && (y as usize & self.height_mask) == 0
|
|
|
36 |
}
|
|
|
37 |
|
|
|
38 |
#[inline]
|
|
|
39 |
pub fn map<U, F: FnOnce(&mut T) -> U>(&mut self, y: i32, x: i32, f: F) {
|
|
|
40 |
if self.is_valid_coordinate(x, y) {
|
|
|
41 |
self.pixels.get_mut(y as usize, x as usize).map(f);
|
|
|
42 |
}
|
|
|
43 |
}
|
|
|
44 |
|
|
|
45 |
pub fn draw_line(&mut self, x1: i32, y1: i32, x2: i32, y2: i32, value: T) {
|
|
|
46 |
let mut e_x: i32 = 0;
|
|
|
47 |
let mut e_y: i32 = 0;
|
|
|
48 |
let mut d_x: i32 = x2 - x1;
|
|
|
49 |
let mut d_y: i32 = y2 - y1;
|
|
|
50 |
|
|
|
51 |
let s_x: i32;
|
|
|
52 |
let s_y: i32;
|
|
|
53 |
|
|
|
54 |
if d_x > 0 {
|
|
|
55 |
s_x = 1;
|
|
|
56 |
} else if d_x < 0 {
|
|
|
57 |
s_x = -1;
|
|
|
58 |
d_x = -d_x;
|
|
|
59 |
} else {
|
|
|
60 |
s_x = d_x;
|
|
|
61 |
}
|
|
|
62 |
|
|
|
63 |
if d_y > 0 {
|
|
|
64 |
s_y = 1;
|
|
|
65 |
} else if d_y < 0 {
|
|
|
66 |
s_y = -1;
|
|
|
67 |
d_y = -d_y;
|
|
|
68 |
} else {
|
|
|
69 |
s_y = d_y;
|
|
|
70 |
}
|
|
|
71 |
|
|
|
72 |
let d = cmp::max(d_x, d_y);
|
|
|
73 |
|
|
|
74 |
let mut x = x1;
|
|
|
75 |
let mut y = y1;
|
|
|
76 |
|
|
|
77 |
for _i in 0..=d {
|
|
|
78 |
e_x += d_x;
|
|
|
79 |
e_y += d_y;
|
|
|
80 |
|
|
|
81 |
if e_x > d {
|
|
|
82 |
e_x -= d;
|
|
|
83 |
x += s_x;
|
|
|
84 |
}
|
|
|
85 |
if e_y > d {
|
|
|
86 |
e_y -= d;
|
|
|
87 |
y += s_y;
|
|
|
88 |
}
|
|
|
89 |
|
|
|
90 |
self.map(y, x, |p| *p = value);
|
|
|
91 |
}
|
|
|
92 |
}
|
|
13924
|
93 |
|
|
|
94 |
pub fn fill(&mut self, start_x: i32, start_y: i32, border_value: T, fill_value: T) {
|
|
|
95 |
debug_assert!(self.is_valid_coordinate(start_x - 1, start_y));
|
|
|
96 |
debug_assert!(self.is_valid_coordinate(start_x, start_y));
|
|
|
97 |
|
|
|
98 |
let mut stack: Vec<(usize, usize, usize, isize)> = Vec::new();
|
|
|
99 |
fn push<T: Default + Copy + PartialEq>(
|
|
|
100 |
land: &Land2D<T>,
|
|
|
101 |
stack: &mut Vec<(usize, usize, usize, isize)>,
|
|
|
102 |
xl: usize,
|
|
|
103 |
xr: usize,
|
|
|
104 |
y: usize,
|
|
|
105 |
dir: isize,
|
|
|
106 |
) {
|
|
|
107 |
let yd = y as isize + dir;
|
|
|
108 |
|
|
|
109 |
if land.is_valid_coordinate(0, yd as i32) {
|
|
|
110 |
stack.push((xl, xr, yd as usize, dir));
|
|
|
111 |
}
|
|
|
112 |
};
|
|
|
113 |
|
|
|
114 |
let start_x_l = (start_x - 1) as usize;
|
|
|
115 |
let start_x_r = start_x as usize;
|
|
|
116 |
push(self, &mut stack, start_x_l, start_x_r, start_y as usize, -1);
|
|
|
117 |
push(self, &mut stack, start_x_l, start_x_r, start_y as usize, 1);
|
|
|
118 |
|
|
|
119 |
loop {
|
|
|
120 |
let a = stack.pop();
|
|
|
121 |
match a {
|
|
|
122 |
None => return,
|
|
|
123 |
Some(a) => {
|
|
|
124 |
let (mut xl, mut xr, y, mut dir) = a;
|
|
|
125 |
|
|
|
126 |
while xl > 0 && self
|
|
|
127 |
.pixels
|
|
|
128 |
.get(y, xl)
|
|
|
129 |
.map_or(false, |v| *v != border_value && *v != fill_value)
|
|
|
130 |
{
|
|
|
131 |
xl -= 1;
|
|
|
132 |
}
|
|
|
133 |
|
|
|
134 |
while xr < self.width() - 1 && self
|
|
|
135 |
.pixels
|
|
|
136 |
.get(y, xr)
|
|
|
137 |
.map_or(false, |v| *v != border_value && *v != fill_value)
|
|
|
138 |
{
|
|
|
139 |
xr += 1;
|
|
|
140 |
}
|
|
|
141 |
|
|
|
142 |
while xl < xr {
|
|
|
143 |
while xl <= xr
|
|
|
144 |
&& (self.pixels[y][xl] == border_value
|
|
|
145 |
|| self.pixels[y][xl] == fill_value)
|
|
|
146 |
{
|
|
|
147 |
xl += 1;
|
|
|
148 |
}
|
|
|
149 |
|
|
|
150 |
let mut x = xl;
|
|
|
151 |
|
|
|
152 |
while xl <= xr
|
|
|
153 |
&& (self.pixels[y][xl] != border_value
|
|
|
154 |
&& self.pixels[y][xl] != fill_value)
|
|
|
155 |
{
|
|
|
156 |
self.pixels[y][xl] = fill_value;
|
|
|
157 |
|
|
|
158 |
xl += 1;
|
|
|
159 |
}
|
|
|
160 |
|
|
|
161 |
if x < xl {
|
|
|
162 |
push(self, &mut stack, x, xl - 1, y, dir);
|
|
|
163 |
push(self, &mut stack, x, xl - 1, y, -dir);
|
|
|
164 |
}
|
|
|
165 |
}
|
|
|
166 |
}
|
|
|
167 |
}
|
|
|
168 |
}
|
|
|
169 |
}
|
|
13917
|
170 |
}
|
|
|
171 |
|
|
|
172 |
#[cfg(test)]
|
|
|
173 |
mod tests {
|
|
|
174 |
use super::*;
|
|
|
175 |
|
|
|
176 |
#[test]
|
|
|
177 |
fn basics() {
|
|
13924
|
178 |
let l: Land2D<u8> = Land2D::new(32, 64);
|
|
13917
|
179 |
|
|
|
180 |
assert!(l.is_valid_coordinate(0, 0));
|
|
|
181 |
assert!(!l.is_valid_coordinate(-1, -1));
|
|
|
182 |
|
|
|
183 |
assert!(l.is_valid_coordinate(31, 63));
|
|
|
184 |
assert!(!l.is_valid_coordinate(32, 63));
|
|
|
185 |
assert!(!l.is_valid_coordinate(31, 64));
|
|
|
186 |
}
|
|
|
187 |
|
|
13924
|
188 |
#[test]
|
|
|
189 |
fn fill() {
|
|
|
190 |
let mut l: Land2D<u8> = Land2D::new(128, 128);
|
|
|
191 |
|
|
|
192 |
l.draw_line(0, 0, 32, 96, 1);
|
|
|
193 |
l.draw_line(32, 96, 64, 32, 1);
|
|
|
194 |
l.draw_line(64, 32, 96, 80, 1);
|
|
|
195 |
l.draw_line(96, 80, 128, 0, 1);
|
|
|
196 |
|
|
|
197 |
l.draw_line(0, 128, 64, 96, 1);
|
|
|
198 |
l.draw_line(128, 128, 64, 96, 1);
|
|
|
199 |
|
|
|
200 |
l.fill(32, 32, 1, 2);
|
|
|
201 |
l.fill(16, 96, 1, 3);
|
|
|
202 |
l.fill(60, 100, 1, 4);
|
|
|
203 |
|
|
|
204 |
assert_eq!(l.pixels[0][0], 1);
|
|
|
205 |
assert_eq!(l.pixels[96][64], 1);
|
|
|
206 |
|
|
|
207 |
assert_eq!(l.pixels[40][32], 2);
|
|
|
208 |
assert_eq!(l.pixels[40][96], 2);
|
|
|
209 |
assert_eq!(l.pixels[5][0], 3);
|
|
|
210 |
assert_eq!(l.pixels[120][0], 3);
|
|
|
211 |
assert_eq!(l.pixels[5][127], 3);
|
|
|
212 |
assert_eq!(l.pixels[120][127], 3);
|
|
|
213 |
assert_eq!(l.pixels[35][64], 3);
|
|
|
214 |
assert_eq!(l.pixels[120][20], 4);
|
|
|
215 |
assert_eq!(l.pixels[120][100], 4);
|
|
|
216 |
assert_eq!(l.pixels[100][64], 4);
|
|
|
217 |
}
|
|
13917
|
218 |
}
|