int_interval/

u8.rs

use crate::res::{OneTwo, ZeroOneTwo};

#[cfg(test)]
mod basic_tests;
#[cfg(test)]
mod between_tests;
#[cfg(test)]
mod checked_minkowski_tests;
#[cfg(test)]
mod convex_hull_tests;
#[cfg(test)]
mod difference_tests;
#[cfg(test)]
mod intersection_tests;
#[cfg(test)]
mod saturating_minkowski_tests;
#[cfg(test)]
mod symmetric_difference_tests;
#[cfg(test)]
mod union_tests;

#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct U8CO {
    start: u8,
    end_excl: u8,
}

// ------------------------------------------------------------
// low-level api: construction / accessors / predicates
// ------------------------------------------------------------

mod basic {

    use super::*;

    impl U8CO {
        #[inline]
        pub const fn try_new(start: u8, end_excl: u8) -> Option<Self> {
            if start < end_excl {
                Some(Self { start, end_excl })
            } else {
                None
            }
        }

        #[inline]
        pub const unsafe fn new_unchecked(start: u8, end_excl: u8) -> Self {
            debug_assert!(start < end_excl);
            Self { start, end_excl }
        }

        #[inline]
        pub const fn start(self) -> u8 {
            self.start
        }

        #[inline]
        pub const fn end_excl(self) -> u8 {
            self.end_excl
        }

        #[inline]
        pub const fn end_incl(self) -> u8 {
            // u8_low_bound =< start < end_excl
            self.end_excl - 1
        }

        #[inline]
        pub const fn len(self) -> u8 {
            self.end_excl - self.start
        }

        /// Returns the midpoint of the interval (floor division).
        #[inline]
        pub const fn midpoint(self) -> u8 {
            self.start + (self.len() / 2)
        }

        /// Construct a `U8CO` from a midpoint and a length.
        ///
        /// Returns `None` if the computed interval is invalid or overflows u8.
        #[inline]
        pub const fn checked_from_midpoint_len(mid: u8, len: u8) -> Option<Self> {
            if len == 0 {
                return None;
            }
            // Compute start = mid - floor(len/2)
            let Some(start) = mid.checked_sub(len / 2) else {
                return None;
            };
            // Compute end_excl = start + len, return None if overflow
            let Some(end_excl) = start.checked_add(len) else {
                return None;
            };

            // # Safety
            // This function uses `unsafe { Self::new_unchecked(start, end_excl) }` internally.
            // The safety is guaranteed by the following checks:
            // 1. `mid.checked_sub(len / 2)` ensures `start` does not underflow `u8`.
            // 2. `start.checked_add(len)` ensures `end_excl` does not overflow `u8`.
            // 3. Because `len > 0`, we have `start < end_excl`.
            // 4. Therefore, the half-open interval invariant `[start, end_excl)` is preserved.
            Some(unsafe { Self::new_unchecked(start, end_excl) })
        }

        /// Saturating version: from midpoint + length, keeps start < end_excl
        #[inline]
        pub const fn saturating_from_midpoint_len(mid: u8, len: u8) -> Option<Self> {
            if len == 0 {
                return None;
            }

            let start = mid.saturating_sub(len / 2);
            let end_excl = start.saturating_add(len);

            // Use try_new to enforce start < end_excl invariant
            Self::try_new(start, end_excl)
        }

        #[inline]
        pub const fn contains(self, x: u8) -> bool {
            self.start <= x && x < self.end_excl
        }

        #[inline]
        pub const fn contains_interval(self, other: Self) -> bool {
            self.start <= other.start && other.end_excl <= self.end_excl
        }

        #[inline]
        pub const fn iter(self) -> core::ops::Range<u8> {
            self.start..self.end_excl
        }

        #[inline]
        pub const fn to_range(self) -> core::ops::Range<u8> {
            self.start..self.end_excl
        }

        #[inline]
        pub const fn intersects(self, other: Self) -> bool {
            !(self.end_excl <= other.start || other.end_excl <= self.start)
        }

        #[inline]
        pub const fn is_adjacent(self, other: Self) -> bool {
            self.end_excl == other.start || other.end_excl == self.start
        }

        #[inline]
        pub const fn is_contiguous_with(self, other: Self) -> bool {
            self.intersects(other) || self.is_adjacent(other)
        }
    }
}

// ------------------------------------------------------------
// interval algebra api: intersection / convex_hull / between / union / difference / symmetric_difference
// ------------------------------------------------------------

mod interval_algebra {

    use super::*;

    impl U8CO {
        /// Returns the intersection of two intervals.
        ///
        /// If the intervals do not overlap, returns `None`.
        #[inline]
        pub const fn intersection(self, other: Self) -> Option<Self> {
            let start = if self.start >= other.start {
                self.start
            } else {
                other.start
            };

            let end_excl = if self.end_excl <= other.end_excl {
                self.end_excl
            } else {
                other.end_excl
            };

            Self::try_new(start, end_excl)
        }

        /// Returns the convex hull (smallest interval containing both) of two intervals.
        ///
        /// Always returns a valid `U8CO`.
        #[inline]
        pub const fn convex_hull(self, other: Self) -> Self {
            let start = if self.start <= other.start {
                self.start
            } else {
                other.start
            };

            let end_excl = if self.end_excl >= other.end_excl {
                self.end_excl
            } else {
                other.end_excl
            };

            Self { start, end_excl }
        }

        /// Returns the interval strictly between two intervals.
        ///
        /// If the intervals are contiguous or overlap, returns `None`.
        #[inline]
        pub const fn between(self, other: Self) -> Option<Self> {
            let (left, right) = if self.start <= other.start {
                (self, other)
            } else {
                (other, self)
            };

            Self::try_new(left.end_excl, right.start)
        }

        /// Returns the union of two intervals.
        ///
        /// - If intervals are contiguous or overlapping, returns `One` containing the merged interval.
        /// - Otherwise, returns `Two` containing both intervals in ascending order.
        #[inline]
        pub const fn union(self, other: Self) -> OneTwo<Self> {
            if self.is_contiguous_with(other) {
                OneTwo::One(self.convex_hull(other))
            } else if self.start <= other.start {
                OneTwo::Two(self, other)
            } else {
                OneTwo::Two(other, self)
            }
        }

        /// Returns the difference of two intervals (self - other).
        ///
        /// - If no overlap, returns `One(self)`.
        /// - If partial overlap, returns `One` or `Two` depending on remaining segments.
        /// - If fully contained, returns `Zero`.
        #[inline]
        pub const fn difference(self, other: Self) -> ZeroOneTwo<Self> {
            match self.intersection(other) {
                None => ZeroOneTwo::One(self),
                Some(inter) => {
                    let left = Self::try_new(self.start, inter.start);
                    let right = Self::try_new(inter.end_excl, self.end_excl);

                    match (left, right) {
                        (None, None) => ZeroOneTwo::Zero,
                        (Some(x), None) | (None, Some(x)) => ZeroOneTwo::One(x),
                        (Some(x), Some(y)) => ZeroOneTwo::Two(x, y),
                    }
                }
            }
        }

        /// Returns the symmetric difference of two intervals.
        ///
        /// Equivalent to `(self - other) ∪ (other - self)`.
        /// - If intervals do not overlap, returns `Two(self, other)` in order.
        /// - If intervals partially overlap, returns remaining non-overlapping segments as `One` or `Two`.
        #[inline]
        pub const fn symmetric_difference(self, other: Self) -> ZeroOneTwo<Self> {
            match self.intersection(other) {
                None => {
                    if self.start <= other.start {
                        ZeroOneTwo::Two(self, other)
                    } else {
                        ZeroOneTwo::Two(other, self)
                    }
                }
                Some(inter) => {
                    let hull = self.convex_hull(other);
                    let left = Self::try_new(hull.start, inter.start);
                    let right = Self::try_new(inter.end_excl, hull.end_excl);

                    match (left, right) {
                        (None, None) => ZeroOneTwo::Zero,
                        (Some(x), None) | (None, Some(x)) => ZeroOneTwo::One(x),
                        (Some(x), Some(y)) => ZeroOneTwo::Two(x, y),
                    }
                }
            }
        }
    }
}

// ------------------------------------------------------------
// Module: Minkowski arithmetic for U8CO
// Provides checked and saturating Minkowski operations
// ------------------------------------------------------------

pub mod minkowski {
    use super::*;

    pub mod checked {
        use super::*;

        // --------------------------------------------------------
        // Interval-to-interval Minkowski operations
        // --------------------------------------------------------
        impl U8CO {
            /// Minkowski addition: [a_start, a_end) + [b_start, b_end)
            #[inline]
            pub const fn checked_minkowski_add(self, other: Self) -> Option<Self> {
                let Some(start) = self.start.checked_add(other.start) else {
                    return None;
                };
                let Some(end_excl) = self.end_excl.checked_add(other.end_incl()) else {
                    return None;
                };

                // SAFETY:
                // `checked_add` guarantees both bounds are computed without overflow.
                // For half-open intervals, addition preserves ordering:
                // self.start <= self.end_excl - 1 and other.start <= other.end_incl(),
                // therefore `start < end_excl` still holds for the resulting interval.
                Some(unsafe { Self::new_unchecked(start, end_excl) })
            }

            /// Minkowski subtraction: [a_start, a_end) - [b_start, b_end)
            #[inline]
            pub const fn checked_minkowski_sub(self, other: Self) -> Option<Self> {
                let Some(start) = self.start.checked_sub(other.end_incl()) else {
                    return None;
                };
                let Some(end_excl) = self.end_excl.checked_sub(other.start) else {
                    return None;
                };

                // SAFETY:
                // `checked_sub` guarantees both bounds are computed without underflow.
                // Since `self.start <= self.end_excl - 1` and `other.start <= other.end_incl()`,
                // we have `self.start - other.end_incl() < self.end_excl - other.start`,
                // so the resulting half-open interval remains valid.
                Some(unsafe { Self::new_unchecked(start, end_excl) })
            }

            /// Minkowski multiplication: [a_start, a_end) * [b_start, b_end)
            #[inline]
            pub const fn checked_minkowski_mul(self, other: Self) -> Option<Self> {
                let Some(start) = self.start.checked_mul(other.start) else {
                    return None;
                };
                let Some(end_incl) = self.end_incl().checked_mul(other.end_incl()) else {
                    return None;
                };
                let Some(end_excl) = end_incl.checked_add(1) else {
                    return None;
                };

                // SAFETY:
                // For `U8CO`, all values are non-negative, so endpoint-wise multiplication
                // is monotone. `start` is the minimum product and `end_incl` is the maximum.
                // `checked_add(1)` converts the inclusive upper bound back to half-open form,
                // and overflow has already been excluded.
                Some(unsafe { Self::new_unchecked(start, end_excl) })
            }

            /// Minkowski division: [a_start, a_end) / [b_start, b_end)
            #[inline]
            pub const fn checked_minkowski_div(self, other: Self) -> Option<Self> {
                if other.start == 0 {
                    return None;
                }

                let Some(start) = self.start.checked_div(other.end_incl()) else {
                    return None;
                };
                let Some(end_incl) = self.end_incl().checked_div(other.start) else {
                    return None;
                };
                let Some(end_excl) = end_incl.checked_add(1) else {
                    return None;
                };

                // SAFETY:
                // `other.start != 0` excludes division by zero, and all operands are unsigned.
                // Over positive integers, division is monotone with respect to the dividend and
                // anti-monotone with respect to the divisor, so:
                //   min = self.start / other.end_incl()
                //   max = self.end_incl() / other.start
                // Thus `start <= end_incl`, and `end_excl = end_incl + 1` is checked.
                Some(unsafe { Self::new_unchecked(start, end_excl) })
            }
        }

        // --------------------------------------------------------
        // Interval-to-scalar Minkowski operations
        // --------------------------------------------------------
        impl U8CO {
            /// Add a scalar to an interval: [start, end) + n
            #[inline]
            pub const fn checked_minkowski_add_n(self, n: u8) -> Option<Self> {
                let Some(start) = self.start.checked_add(n) else {
                    return None;
                };
                let Some(end_excl) = self.end_excl.checked_add(n) else {
                    return None;
                };

                // SAFETY:
                // `checked_add` excludes overflow, and adding the same scalar to both bounds
                // preserves the half-open interval ordering.
                Some(unsafe { Self::new_unchecked(start, end_excl) })
            }

            /// Subtract a scalar from an interval: [start, end) - n
            #[inline]
            pub const fn checked_minkowski_sub_n(self, n: u8) -> Option<Self> {
                let Some(start) = self.start.checked_sub(n) else {
                    return None;
                };
                let Some(end_excl) = self.end_excl.checked_sub(n) else {
                    return None;
                };

                // SAFETY:
                // `checked_sub` excludes underflow, and subtracting the same scalar from both
                // bounds preserves the half-open interval ordering.
                Some(unsafe { Self::new_unchecked(start, end_excl) })
            }

            /// Multiply an interval by a scalar: [start, end) * n
            #[inline]
            pub const fn checked_minkowski_mul_n(self, n: u8) -> Option<Self> {
                let Some(start) = self.start.checked_mul(n) else {
                    return None;
                };
                let Some(end_incl) = self.end_incl().checked_mul(n) else {
                    return None;
                };
                let Some(end_excl) = end_incl.checked_add(1) else {
                    return None;
                };

                // SAFETY:
                // For unsigned integers, multiplication by a scalar is monotone.
                // Therefore `start * n` is the lower bound and `end_incl * n` is the upper bound.
                // `checked_*` operations exclude overflow, and `end_excl` restores half-open form.
                Some(unsafe { Self::new_unchecked(start, end_excl) })
            }

            /// Divide an interval by a scalar: [start, end) / n
            #[inline]
            pub const fn checked_minkowski_div_n(self, n: u8) -> Option<Self> {
                if n == 0 {
                    return None;
                }

                let start = self.start / n;
                let end_incl = self.end_incl() / n;
                let Some(end_excl) = end_incl.checked_add(1) else {
                    return None;
                };

                // SAFETY:
                // `n != 0` excludes division by zero. For unsigned integers and positive scalar `n`,
                // division is monotone, so `self.start / n <= self.end_incl() / n`.
                // `checked_add(1)` safely converts the inclusive upper bound to half-open form.
                Some(unsafe { Self::new_unchecked(start, end_excl) })
            }
        }
    }

    pub mod saturating {
        use super::*;

        // --------------------------------------------------------
        // Interval-to-interval Minkowski operations
        // --------------------------------------------------------
        impl U8CO {
            #[inline]
            pub const fn saturating_minkowski_add(self, other: Self) -> Option<Self> {
                let start = self.start.saturating_add(other.start);
                let end_excl = self.end_excl.saturating_add(other.end_incl());
                Self::try_new(start, end_excl)
            }

            #[inline]
            pub const fn saturating_minkowski_sub(self, other: Self) -> Option<Self> {
                let start = self.start.saturating_sub(other.end_incl());
                let end_excl = self.end_excl.saturating_sub(other.start);
                Self::try_new(start, end_excl)
            }

            #[inline]
            pub const fn saturating_minkowski_mul(self, other: Self) -> Option<Self> {
                let start = self.start.saturating_mul(other.start);
                let end_incl = self.end_incl().saturating_mul(other.end_incl());
                let end_excl = end_incl.saturating_add(1);
                Self::try_new(start, end_excl)
            }

            #[inline]
            pub const fn saturating_minkowski_div(self, other: Self) -> Option<Self> {
                if other.start == 0 {
                    return None;
                }

                let start = self.start / other.end_incl();
                let end_incl = self.end_incl() / other.start;
                let end_excl = end_incl.saturating_add(1);
                Self::try_new(start, end_excl)
            }
        }

        // --------------------------------------------------------
        // Interval-to-scalar Minkowski operations
        // --------------------------------------------------------
        impl U8CO {
            /// Saturating add scalar: [start, end) + n
            #[inline]
            pub const fn saturating_minkowski_add_n(self, n: u8) -> Option<Self> {
                let start = self.start.saturating_add(n);
                let end_excl = self.end_excl.saturating_add(n);
                Self::try_new(start, end_excl)
            }

            /// Saturating sub scalar: [start, end) - n
            #[inline]
            pub const fn saturating_minkowski_sub_n(self, n: u8) -> Option<Self> {
                let start = self.start.saturating_sub(n);
                let end_excl = self.end_excl.saturating_sub(n);
                Self::try_new(start, end_excl)
            }

            /// Saturating mul scalar: [start, end) * n
            #[inline]
            pub const fn saturating_minkowski_mul_n(self, n: u8) -> Option<Self> {
                let start = self.start.saturating_mul(n);
                let end_incl = self.end_incl().saturating_mul(n);
                let end_excl = end_incl.saturating_add(1);
                Self::try_new(start, end_excl)
            }

            /// Saturating div scalar: [start, end) / n
            #[inline]
            pub const fn saturating_minkowski_div_n(self, n: u8) -> Option<Self> {
                if n == 0 {
                    return None;
                }

                let start = self.start / n;
                let end_incl = self.end_incl() / n;
                let end_excl = end_incl.saturating_add(1);
                Self::try_new(start, end_excl)
            }
        }
    }
}