geometry/span.rs
1//! A one-dimensional span.
2//!
3//! A span represents the closed interval `[start, stop]`.
4use serde::{Deserialize, Serialize};
5
6use crate::contains::{Containment, Contains};
7use crate::intersect::Intersect;
8use crate::sign::Sign;
9use crate::snap::snap_to_grid;
10use crate::union::BoundingUnion;
11
12/// A closed interval of coordinates in one dimension.
13///
14/// Represents the range `[start, stop]`.
15#[derive(
16 Debug, Default, Clone, Copy, Hash, Ord, PartialOrd, Serialize, Deserialize, PartialEq, Eq,
17)]
18pub struct Span {
19 start: i64,
20 stop: i64,
21}
22
23impl Span {
24 /// Creates a new [`Span`] from 0 until the specified stop.
25 ///
26 /// # Panics
27 ///
28 /// This function panics if `stop` is less than 0.
29 pub const fn until(stop: i64) -> Self {
30 assert!(stop >= 0);
31 Self { start: 0, stop }
32 }
33
34 /// Creates a new [`Span`] between two integers.
35 ///
36 /// # Safety
37 ///
38 /// The caller must ensure that `start` is less
39 /// than or equal to `stop`.
40 pub const unsafe fn new_unchecked(start: i64, stop: i64) -> Self {
41 Self { start, stop }
42 }
43
44 /// Creates a new [`Span`] between two integers.
45 pub fn new(start: i64, stop: i64) -> Self {
46 use std::cmp::{max, min};
47 let lower = min(start, stop);
48 let upper = max(start, stop);
49 Self {
50 start: lower,
51 stop: upper,
52 }
53 }
54
55 /// Creates a span of zero length encompassing the given point.
56 pub const fn from_point(x: i64) -> Self {
57 Self { start: x, stop: x }
58 }
59
60 /// Creates a span of the given length starting from `start`.
61 pub const fn with_start_and_length(start: i64, length: i64) -> Self {
62 Self {
63 stop: start + length,
64 start,
65 }
66 }
67
68 /// Creates a span of the given length ending at `stop`.
69 pub const fn with_stop_and_length(stop: i64, length: i64) -> Self {
70 Self {
71 start: stop - length,
72 stop,
73 }
74 }
75
76 /// Creates a span with the given endpoint and length.
77 ///
78 /// If `sign` is [`Sign::Pos`], `point` is treated as the ending/stopping point of the span.
79 /// If `sign` is [`Sign::Neg`], `point` is treated as the beginning/starting point of the span.
80 pub const fn with_point_and_length(sign: Sign, point: i64, length: i64) -> Self {
81 match sign {
82 Sign::Pos => Self::with_stop_and_length(point, length),
83 Sign::Neg => Self::with_start_and_length(point, length),
84 }
85 }
86
87 /// Creates a new [`Span`] expanded by `amount` in the direction indicated by `pos`.
88 pub const fn expand(mut self, sign: Sign, amount: i64) -> Self {
89 match sign {
90 Sign::Pos => self.stop += amount,
91 Sign::Neg => self.start -= amount,
92 }
93 self
94 }
95
96 /// Creates a new [`Span`] expanded by `amount` in both directions.
97 pub const fn expand_all(mut self, amount: i64) -> Self {
98 self.stop += amount;
99 self.start -= amount;
100 self
101 }
102
103 /// Gets the starting ([`Sign::Neg`]) or stopping ([`Sign::Pos`]) endpoint of a span.
104 #[inline]
105 pub const fn endpoint(&self, sign: Sign) -> i64 {
106 match sign {
107 Sign::Neg => self.start(),
108 Sign::Pos => self.stop(),
109 }
110 }
111
112 /// Gets the shortest distance between this span and a point.
113 ///
114 /// # Example
115 ///
116 /// ```
117 /// # use geometry::prelude::*;
118 /// let span = Span::new(10, 20);
119 /// assert_eq!(span.dist_to(4), 6);
120 /// assert_eq!(span.dist_to(12), 0);
121 /// assert_eq!(span.dist_to(27), 7);
122 /// ```
123 pub fn dist_to(&self, point: i64) -> i64 {
124 if point < self.start() {
125 self.start() - point
126 } else if point > self.stop() {
127 point - self.stop()
128 } else {
129 0
130 }
131 }
132
133 /// Creates a new [`Span`] with center `center` and length `span`.
134 ///
135 /// `span` must be a positive, even integer.
136 ///
137 /// # Example
138 ///
139 /// ```
140 /// # use geometry::prelude::*;
141 /// let span = Span::from_center_span(0, 40);
142 /// assert_eq!(span, Span::new(-20, 20));
143 /// ```
144 ///
145 /// # Panics
146 ///
147 /// Passing an odd `span` to this method results in a panic:
148 ///
149 /// ```should_panic
150 /// # use geometry::prelude::*;
151 /// let span = Span::from_center_span(0, 25);
152 /// ```
153 ///
154 /// Passing a negative `span` to this method also results in a panic:
155 ///
156 /// ```should_panic
157 /// # use geometry::prelude::*;
158 /// let span = Span::from_center_span(0, -200);
159 /// ```
160 pub fn from_center_span(center: i64, span: i64) -> Self {
161 assert!(span >= 0);
162 assert_eq!(span % 2, 0);
163
164 Self::new(center - (span / 2), center + (span / 2))
165 }
166
167 /// Creates a new [`Span`] with center `center` and length `span` and snap the edges to the
168 /// grid.
169 ///
170 /// # Example
171 ///
172 /// ```
173 /// # use geometry::prelude::*;
174 /// let span = Span::from_center_span_gridded(0, 40, 5);
175 /// assert_eq!(span, Span::new(-20, 20));
176 ///
177 /// let span = Span::from_center_span_gridded(35, 40, 5);
178 /// assert_eq!(span, Span::new(15, 55));
179 /// ```
180 ///
181 /// # Panics
182 ///
183 /// This function panics if `span` is negative, odd, or not an integer multiple of `grid`.
184 pub fn from_center_span_gridded(center: i64, span: i64, grid: i64) -> Self {
185 assert!(span >= 0);
186 assert_eq!(span % 2, 0);
187 assert_eq!(span % grid, 0);
188
189 let start = snap_to_grid(center - (span / 2), grid);
190
191 Self::new(start, start + span)
192 }
193
194 /// Gets the center of the span.
195 #[inline]
196 pub const fn center(&self) -> i64 {
197 (self.start + self.stop) / 2
198 }
199
200 /// Gets the length of the span.
201 #[inline]
202 pub const fn length(&self) -> i64 {
203 self.stop - self.start
204 }
205
206 /// Gets the start of the span.
207 #[inline]
208 pub const fn start(&self) -> i64 {
209 self.start
210 }
211
212 /// Gets the stop of the span.
213 #[inline]
214 pub const fn stop(&self) -> i64 {
215 self.stop
216 }
217
218 /// Checks if the span intersects with the [`Span`] `other`.
219 #[inline]
220 pub const fn intersects(&self, other: &Self) -> bool {
221 !(other.stop < self.start || self.stop < other.start)
222 }
223
224 /// Creates a new minimal [`Span`] that contains all of the elements of `spans`.
225 pub fn merge(spans: impl IntoIterator<Item = Self>) -> Self {
226 use std::cmp::{max, min};
227 let mut spans = spans.into_iter();
228 let (mut start, mut stop) = spans
229 .next()
230 .expect("Span::merge requires at least one span")
231 .into();
232
233 for span in spans {
234 start = min(start, span.start);
235 stop = max(stop, span.stop);
236 }
237
238 assert!(start <= stop);
239
240 Span { start, stop }
241 }
242
243 /// Merges adjacent spans when `merge_fn` evaluates to true.
244 #[doc(hidden)]
245 pub fn merge_adjacent(
246 spans: impl IntoIterator<Item = Self>,
247 mut merge_fn: impl FnMut(Span, Span) -> bool,
248 ) -> impl Iterator<Item = Span> {
249 let mut spans: Vec<Span> = spans.into_iter().collect();
250 spans.sort_by_key(|span| span.start());
251
252 let mut merged_spans = Vec::new();
253
254 let mut j = 0;
255 while j < spans.len() {
256 let mut curr_span = spans[j];
257 j += 1;
258 while j < spans.len() && merge_fn(curr_span, spans[j]) {
259 curr_span = curr_span.union(spans[j]);
260 j += 1;
261 }
262 merged_spans.push(curr_span);
263 }
264
265 merged_spans.into_iter()
266 }
267
268 /// Calculates the smallest interval containing this span and `other`.
269 pub fn union(self, other: Self) -> Self {
270 use std::cmp::{max, min};
271 Self {
272 start: min(self.start, other.start),
273 stop: max(self.stop, other.stop),
274 }
275 }
276
277 /// Calculates the minimal bounding interval of all spans provided.
278 ///
279 /// # Example
280 ///
281 /// ```
282 /// # use geometry::prelude::*;
283 /// let spans = vec![
284 /// Span::new(10, 40),
285 /// Span::new(35, 60),
286 /// Span::new(20, 30),
287 /// Span::new(-10, 5),
288 /// ];
289 /// assert_eq!(Span::union_all(spans.into_iter()), Span::new(-10, 60));
290 /// ```
291 ///
292 /// # Panics
293 ///
294 /// This function panics if the provided iterator has no elements.
295 /// If your iterator may be empty, consider using [`Span::union_all_option`].
296 pub fn union_all<T>(spans: impl Iterator<Item = T>) -> Self
297 where
298 T: Into<Self>,
299 {
300 spans
301 .fold(None, |acc: Option<Span>, s| match acc {
302 Some(acc) => Some(acc.union(s.into())),
303 None => Some(s.into()),
304 })
305 .unwrap()
306 }
307
308 /// Calculates the minimal bounding interval of all `Option<Span>`s provided.
309 ///
310 /// All `None` elements in the iterator are ignored.
311 /// If the iterator has no `Some(_)` elements, this function returns [`None`].
312 ///
313 /// # Example
314 ///
315 /// ```
316 /// # use geometry::prelude::*;
317 /// let spans = vec![
318 /// Some(Span::new(10, 40)),
319 /// Some(Span::new(35, 60)),
320 /// None,
321 /// Some(Span::new(20, 30)),
322 /// None,
323 /// Some(Span::new(-10, 5)),
324 /// ];
325 /// assert_eq!(Span::union_all_option(spans.into_iter()), Some(Span::new(-10, 60)));
326 /// ```
327 pub fn union_all_option<T>(spans: impl Iterator<Item = T>) -> Option<Self>
328 where
329 T: Into<Option<Self>>,
330 {
331 spans
332 .filter_map(|s| s.into())
333 .fold(None, |acc, s| match acc {
334 Some(acc) => Some(acc.union(s)),
335 None => Some(s),
336 })
337 }
338
339 /// Calculates the intersection of this span with `other`.
340 pub fn intersection(self, other: Self) -> Option<Self> {
341 let _start = std::cmp::max(self.start(), other.start());
342 let _stop = std::cmp::min(self.stop(), other.stop());
343 if _start > _stop {
344 None
345 } else {
346 Some(Self::new(_start, _stop))
347 }
348 }
349
350 /// Returns a new [`Span`] representing the union of the current span with the given point.
351 pub fn add_point(self, pos: i64) -> Self {
352 use std::cmp::{max, min};
353 Self {
354 start: min(self.start, pos),
355 stop: max(self.stop, pos),
356 }
357 }
358
359 /// Shrinks the given side by the given amount.
360 ///
361 /// Behavior is controlled by the given [`Sign`]:
362 /// * If `side` is [`Sign::Pos`], shrinks from the positive end (ie. decreases the `stop`).
363 /// * If `side` is [`Sign::Neg`], shrinks from the negative end (ie. increases the `start`).
364 pub fn shrink(self, side: Sign, amount: i64) -> Self {
365 assert!(self.length() >= amount);
366 match side {
367 Sign::Pos => Self::new(self.start, self.stop - amount),
368 Sign::Neg => Self::new(self.start + amount, self.stop),
369 }
370 }
371
372 /// Shrinks the span by the given amount on all sides.
373 pub const fn shrink_all(self, amount: i64) -> Self {
374 assert!(self.length() >= 2 * amount);
375 Self {
376 start: self.start + amount,
377 stop: self.stop - amount,
378 }
379 }
380
381 /// Translates the span by the given amount.
382 pub const fn translate(self, amount: i64) -> Self {
383 Self {
384 start: self.start + amount,
385 stop: self.stop + amount,
386 }
387 }
388
389 /// The minimum separation between this span and `other`.
390 ///
391 /// # Example
392 ///
393 /// ```
394 /// # use geometry::prelude::*;
395 /// let s1 = Span::new(10, 20);
396 /// let s2 = Span::new(30, 50);
397 /// let s3 = Span::new(25, 40);
398 /// assert_eq!(s1.dist_to_span(s2), 10);
399 /// assert_eq!(s1.dist_to_span(s3), 5);
400 /// assert_eq!(s2.dist_to_span(s3), 0);
401 /// assert_eq!(s3.dist_to_span(s3), 0);
402 /// ```
403 pub fn dist_to_span(self, other: Span) -> i64 {
404 std::cmp::max(
405 0,
406 self.union(other).length() - self.length() - other.length(),
407 )
408 }
409
410 /// Returns whether the span's center is at an integer coordinate.
411 ///
412 /// # Example
413 ///
414 /// ```
415 /// # use geometry::prelude::*;
416 /// let span = Span::new(0, 100);
417 /// assert!(span.has_integer_center());
418 ///
419 /// let span = Span::new(0, 99);
420 /// assert!(!span.has_integer_center());
421 /// ```
422 pub fn has_integer_center(&self) -> bool {
423 (self.start() + self.stop()) % 2 == 0
424 }
425}
426
427impl Intersect<Span> for Span {
428 type Output = Self;
429 fn intersect(&self, other: &Span) -> Option<Self::Output> {
430 self.intersection(*other)
431 }
432}
433
434impl Contains<Span> for Span {
435 fn contains(&self, other: &Span) -> Containment {
436 if other.start() >= self.start() && other.stop() <= self.stop() {
437 Containment::Full
438 } else if other.start() <= self.stop() || other.stop() >= self.start() {
439 Containment::Partial
440 } else {
441 Containment::None
442 }
443 }
444}
445
446impl BoundingUnion<Span> for Span {
447 type Output = Span;
448 fn bounding_union(&self, other: &Span) -> Self::Output {
449 self.union(*other)
450 }
451}
452
453impl From<(i64, i64)> for Span {
454 #[inline]
455 fn from(tup: (i64, i64)) -> Self {
456 Self::new(tup.0, tup.1)
457 }
458}
459
460impl From<Span> for (i64, i64) {
461 #[inline]
462 fn from(s: Span) -> Self {
463 (s.start(), s.stop())
464 }
465}