palindromeda 2.1.0

//! # Palindrome generator and checker for numbers.
//! A palindrome is a letter, number or any other sequence that is the exact same forwards and backwards.
//! This crate is specifically for palindromic numbers.
//!
//! ## Checking for palindromes
//! If you want to check whether an **unsigned integer** is a palindrome,
//! use the [`is_palindrome`](`IsPalindrome::is_palindrome`) function:
//! ```
//! use palindromeda::IsPalindrome;
//!
//! let pal1: u64 = 8008; // This is a palindrome.
//! println!("Is {pal1} a palindrome? {}", pal1.is_palindrome());
//!
//! let pal2: u8 = 69; // This is NOT a palindrome.
//! println!("Is {pal2} a palindrome? {}", pal2.is_palindrome());
//! ```
//! Output:
//! ```text
//! Is 8008 a palindrome? true
//! Is 69 a palindrome? false
//! ```
//!
//! ## Generating palindromes
//! Generating a palindrome is as easy as using either [`Palindrome::le`],
//! [`Palindrome::ge`] or [`Palindrome::closest`] for the nearest palindrome
//! to a number, or by retrieving it based on its palindrome-index
//! with [`Palindrome::nth`]:
//! ```
//! use palindromeda::Palindrome;
//!
//! let number1: u64 = 420; // This number is too high.
//! // Let's get a palindrome that's lower.
//! println!("Palindrome that's lower: {}", Palindrome::le(number1));
//!
//! let number2: u64 = 1337;
//! // Let's get a palindrome that's higher.
//! println!("Palindrome that's higher: {}", Palindrome::ge(number2));
//!
//! let number3: u64 = 5340; // Which palindrome is closest?
//! println!("Closest palindrome: {}", Palindrome::closest(number3));
//!
//! let number4: usize = 1000; // 1001st palindrome (0-based indexing)
//! println!("1001st palindrome: {}", Palindrome::nth(number4).unwrap());
//! ```
//! Output:
//! ```text
//! Palindrome that's lower: 414
//! Palindrome that's higher: 1441
//! Closest palindrome: 5335
//! 1001st palindrome: 90109
//! ```
//! And if you want, you can go from palindrome to palindrome with the
//! [`Palindrome::previous`] and [`Palindrome::next`] functions.
//!
//! ## Iterating over palindromes
//! With [`PalindromeIter`] you can iterate over a large swathe of palindromes.
//! You can iterate over a custom range with [`PalindromeIter::from`] or
//! iterate over the first `n` palindromes with [`PalindromeIter::first_n`].
//!
//! You can also iterate over the first `n` palindromes after (and including)
//! a specific palindrome with [`PalindromeIter::first_n_from`].
//! Be sure to use [`PalindromeIter::len`] for quickly determining the
//! length of the iterator.

use forward_ref::{forward_ref_binop, forward_ref_op_assign, forward_ref_unop};
use std::{
    fmt::Display,
    ops::{
        Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Deref, Div,
        DivAssign, Mul, MulAssign, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
        SubAssign,
    },
    u64,
};

struct PalindromeDigits {
    arr: [u8; Self::MAX_N],
    start: usize,
    length: usize,
}

impl PalindromeDigits {
    const MAX_N: usize = 20; // Length of largest possible palindrome.

    /// Return a PalindromeDigits.
    /// NOTE: Wasting stack since arrays can't have dynamic length.
    const fn from(mut x: u64) -> Self {
        let length = match x.checked_ilog10() {
            Some(x) => x as usize + 1,
            None => 1,
        };
        let mut arr: [u8; Palindrome::MAX_LEN] = [0; Palindrome::MAX_LEN];

        let mut idx = 1;
        while idx <= length {
            arr[Palindrome::MAX_LEN - idx] = (x % 10) as u8;
            x /= 10;
            idx += 1;
        }

        Self {
            arr,
            length,
            start: Self::MAX_N - length,
        }
    }

    /// Return a PalindromeDigits.
    /// NOTE: Wasting stack since arrays can't have dynamic length.
    const fn from_unchecked(mut x: u64) -> Self {
        let length = x.ilog10() as usize + 1;
        let mut arr: [u8; Palindrome::MAX_LEN] = [0; Palindrome::MAX_LEN];

        let mut idx = 1;
        while idx <= length {
            arr[Palindrome::MAX_LEN - idx] = (x % 10) as u8;
            x /= 10;
            idx += 1;
        }

        Self {
            arr,
            length,
            start: Self::MAX_N - length,
        }
    }

    #[inline]
    const fn get(&self, idx: usize) -> u8 {
        self.arr[self.start + idx]
    }

    #[inline]
    const fn get_mut(&mut self, idx: usize) -> &mut u8 {
        &mut self.arr[self.start + idx]
    }

    #[inline]
    const fn len(&self) -> usize {
        self.length
    }
}

#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
pub struct Palindrome(u64);

impl Palindrome {
    pub const MIN: Self = Palindrome(0);
    /// The largest possible palindrome that can fit in a [`std::u64`].
    pub const MAX: Self = Palindrome(18_446_744_066_044_764_481);
    /// Length of the largest possible palindrome.
    const MAX_LEN: usize = 20;
    /// The 0-based index of the largest palindrome that can fit in a [`std::u64`].
    const MAX_N: usize = 11844674405;

    #[inline]
    const fn is_palindrome(mut x: u64) -> bool {
        if x % 10 == 0 && x != 0 {
            return false;
        }

        let mut right_half = 0;
        while x > right_half {
            right_half = right_half * 10 + x % 10;
            x /= 10;
        }

        return x == right_half || x == right_half / 10;
    }

    /// Return the palindrome closest to `x`.
    ///
    /// **NOTE:** If the closest palindrome is in both directions,
    /// return the higher number. E.g.: `x=10` returns `11`.
    pub const fn closest(x: u64) -> Self {
        let ge = Self::ge(x);
        let le = Self::le(x);
        if ge.0 - x <= x - le.0 {
            return ge;
        }

        le
    }

    /// Construct a palindrome from the first half of a digit and a provided length.
    ///
    /// NOTE: Will panic if `length` isn't `2x` or `2x - 1` the size of `digits_half.len()`.
    const fn construct(digits_half: &PalindromeDigits, length: usize) -> Self {
        // If we have a 5-digit number, then we construct by using
        // the 1st, 2nd, 3rd, 2nd, and 1st elements.
        // If we have a 6-digit number, then we construct by using
        // the 1st, 2nd, 3rd, 3rd, 2nd, and 1st elements.
        let second_half_length = length / 2;
        let first_half_length = length - second_half_length;
        let mut palindrome = 0;
        let mut idx = 0; // first half idx
        while idx < first_half_length {
            palindrome *= 10;
            palindrome += digits_half.get(idx) as u64;
            idx += 1;
        }
        idx = 1; // second half reverse idx
        while idx <= second_half_length {
            palindrome *= 10;
            palindrome += digits_half.get(second_half_length - idx) as u64;
            idx += 1;
        }

        Palindrome(palindrome)
    }

    /// Return the nth palindrome (0-based indexing).
    ///
    /// **NOTE:** Returns [`None`] if the palindrome is larger than [`Self::MAX`].
    pub const fn nth(n: usize) -> Option<Self> {
        if n > Self::MAX_N {
            return None;
        }

        // 10th number (9 on 0-based indexing) is an edge case.
        if n < 10 {
            return Some(Self(n as u64));
        }

        let mut n_copy = n;
        let mut n_digits = 1;
        while n_digits <= Self::MAX_N {
            // n_digits = 2
            if n_copy < PalindromeIter::palindromes_in_n_digits(n_digits as u8) {
                // Remove the palindromes below n-digit palindromes.
                n_copy -= PalindromeIter::palindromes_in_n_digits(n_digits as u8 - 1);
                let first_n_digits = n_digits.div_ceil(2);
                let first_half = 10u64.pow(first_n_digits as u32 - 1) + n_copy as u64;
                let digits_half = PalindromeDigits::from_unchecked(first_half);

                return Some(Self::construct(&digits_half, n_digits));
            }
            n_digits += 1;
        }

        None
    }

    /// Return the `n` value of [`Self`].
    ///
    /// Opposite of [`Self::nth`].
    #[inline]
    pub const fn to_n(&self) -> usize {
        PalindromeIter::len_from_0(self.0)
    }

    /// Return the previous palindromic number.
    ///
    /// **NOTE:** Lowest return-value is [`Self::MIN`].
    pub const fn previous(&self) -> Self {
        if self.0 == 0 {
            return Palindrome(0);
        }

        Self::le(self.0 - 1)
    }

    /// Return the next palindromic number.
    ///
    /// **NOTE:** Highest return-value is [`Self::MAX`].
    pub const fn next(&self) -> Self {
        Self::ge(self.0 + 1)
    }

    /// Return the first palindromic number that is less than or equal to `x`.
    pub const fn le(x: u64) -> Self {
        if Palindrome::is_palindrome(x) {
            return Palindrome(x);
        }

        let mut digits = PalindromeDigits::from_unchecked(x);
        let half_length = digits.len().div_ceil(2); // As in amount of digits.
        let mut fh_idx = half_length - 1 - digits.len() % 2; // We don't want center value of uneven number.
        let mut sh_idx = half_length;

        loop {
            // 100 -> 99
            // 372 -> 363
            // 4847 -> 4774
            // 4003 -> 3993
            if digits.get(fh_idx) < digits.get(sh_idx) {
                return Self::construct(&digits, digits.len());
            }
            if digits.get(fh_idx) > digits.get(sh_idx) {
                // First try to downgrade center value, if it's 0, set to 9 and continue.
                // Once non-0 value found, -- it.
                let center_idx = half_length - 1; // Center idx.
                let mut i = 0;
                while i < half_length {
                    let current_digit = digits.get_mut(center_idx - i);
                    if *current_digit == 0 {
                        *current_digit = 9;
                        i += 1;
                        continue;
                    }
                    *current_digit -= 1;
                    // EDGE CASE: 100 -> 99 (length of first half digits CHANGES).
                    // EDGE CASE: 10 -> 9 (length of first half digits DOESN'T CHANGE).
                    if center_idx - i == 0 && *current_digit == 0 {
                        *current_digit = 9;
                        return Self::construct(&digits, digits.len() - 1); // Length always decreases by one.
                    }
                    break;
                }
                return Self::construct(&digits, digits.len());
            }

            fh_idx -= 1;
            sh_idx += 1;
        }
    }

    /// Return the first palindromic number that is greater than or equal to `x`.
    ///
    /// **ATTENTION:** Any value above [`Self::MAX`] will return [`Self::MAX`].
    pub const fn ge(x: u64) -> Self {
        if x >= Self::MAX.0 {
            return Self::MAX;
        }

        if Palindrome::is_palindrome(x) {
            return Palindrome(x);
        }

        let mut digits = PalindromeDigits::from_unchecked(x);
        let half_length = digits.len().div_ceil(2); // As in amount of digits.
        let mut fh_idx = half_length - 1 - digits.len() % 2; // We don't want center value of uneven number.
        let mut sh_idx = half_length;

        loop {
            if digits.get(fh_idx) > digits.get(sh_idx) {
                return Self::construct(&digits, digits.len());
            }
            if digits.get(fh_idx) < digits.get(sh_idx) {
                // First try to upgrade center value, if it's 9, set to 0 and continue.
                // Once non-9 value found, ++ it. 999 is palindrome and can't happen.
                let center_idx = half_length - 1; // Center idx.
                let mut i = 0;
                while i < half_length {
                    let current_digit = digits.get_mut(center_idx - i);
                    if *current_digit == 9 {
                        *current_digit = 0;
                        i += 1;
                        continue;
                    }
                    *current_digit += 1;
                    break;
                }
                return Self::construct(&digits, digits.len());
            }

            fh_idx -= 1;
            sh_idx += 1;
        }
    }
}

impl Deref for Palindrome {
    type Target = u64;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl Display for Palindrome {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl From<Palindrome> for u64 {
    fn from(value: Palindrome) -> Self {
        value.0
    }
}

impl From<&Palindrome> for u64 {
    fn from(value: &Palindrome) -> Self {
        value.0
    }
}

impl PartialEq<u64> for Palindrome {
    fn eq(&self, other: &u64) -> bool {
        self.0 == *other
    }
}

impl PartialEq<Palindrome> for u64 {
    fn eq(&self, other: &Palindrome) -> bool {
        *self == other.0
    }
}

impl PartialOrd<u64> for Palindrome {
    fn ge(&self, other: &u64) -> bool {
        self.0 >= *other
    }

    fn gt(&self, other: &u64) -> bool {
        self.0 > *other
    }

    fn le(&self, other: &u64) -> bool {
        self.0 <= *other
    }

    fn lt(&self, other: &u64) -> bool {
        self.0 < *other
    }

    fn partial_cmp(&self, other: &u64) -> Option<std::cmp::Ordering> {
        self.0.partial_cmp(other)
    }
}

impl PartialOrd<Palindrome> for u64 {
    fn ge(&self, other: &Palindrome) -> bool {
        *self >= other.0
    }

    fn gt(&self, other: &Palindrome) -> bool {
        *self > other.0
    }

    fn le(&self, other: &Palindrome) -> bool {
        *self <= other.0
    }

    fn lt(&self, other: &Palindrome) -> bool {
        *self < other.0
    }

    fn partial_cmp(&self, other: &Palindrome) -> Option<std::cmp::Ordering> {
        self.partial_cmp(&other.0)
    }
}

impl Add<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn add(self, rhs: u64) -> Self::Output {
        self.0 + rhs
    }
}

forward_ref_binop!(impl Add, add for Palindrome, u64);

impl Add<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn add(self, rhs: Palindrome) -> Self::Output {
        self + rhs.0
    }
}

forward_ref_binop!(impl Add, add for u64, Palindrome);

impl AddAssign<Palindrome> for u64 {
    #[inline]
    fn add_assign(&mut self, rhs: Palindrome) {
        *self += rhs.0;
    }
}

forward_ref_op_assign!(impl AddAssign, add_assign for u64, Palindrome);

impl BitAnd<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn bitand(self, rhs: u64) -> Self::Output {
        self.0 & rhs
    }
}

forward_ref_binop!(impl BitAnd, bitand for Palindrome, u64);

impl BitAnd<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn bitand(self, rhs: Palindrome) -> Self::Output {
        self & rhs.0
    }
}

forward_ref_binop!(impl BitAnd, bitand for u64, Palindrome);

impl BitAndAssign<Palindrome> for u64 {
    #[inline]
    fn bitand_assign(&mut self, rhs: Palindrome) {
        *self &= rhs.0
    }
}

forward_ref_op_assign!(impl BitAndAssign, bitand_assign for u64, Palindrome);

impl BitOr<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn bitor(self, rhs: u64) -> Self::Output {
        self.0 | rhs
    }
}

forward_ref_binop!(impl BitOr, bitor for Palindrome, u64);

impl BitOr<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn bitor(self, rhs: Palindrome) -> Self::Output {
        self | rhs.0
    }
}

forward_ref_binop!(impl BitOr, bitor for u64, Palindrome);

impl BitOrAssign<Palindrome> for u64 {
    #[inline]
    fn bitor_assign(&mut self, rhs: Palindrome) {
        *self |= rhs.0
    }
}

forward_ref_op_assign!(impl BitOrAssign, bitor_assign for u64, Palindrome);

impl BitXor<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn bitxor(self, rhs: u64) -> Self::Output {
        self.0 ^ rhs
    }
}

forward_ref_binop!(impl BitXor, bitxor for Palindrome, u64);

impl BitXor<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn bitxor(self, rhs: Palindrome) -> Self::Output {
        self ^ rhs.0
    }
}

forward_ref_binop!(impl BitXor, bitxor for u64, Palindrome);

impl BitXorAssign<Palindrome> for u64 {
    #[inline]
    fn bitxor_assign(&mut self, rhs: Palindrome) {
        *self ^= rhs.0
    }
}

forward_ref_op_assign!(impl BitXorAssign, bitxor_assign for u64, Palindrome);

impl Div<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn div(self, rhs: u64) -> Self::Output {
        self.0 / rhs
    }
}

forward_ref_binop!(impl Div, div for Palindrome, u64);

impl Div<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn div(self, rhs: Palindrome) -> Self::Output {
        self / rhs.0
    }
}

forward_ref_binop!(impl Div, div for u64, Palindrome);

impl DivAssign<Palindrome> for u64 {
    #[inline]
    fn div_assign(&mut self, rhs: Palindrome) {
        *self /= rhs.0
    }
}

forward_ref_op_assign!(impl DivAssign, div_assign for u64, Palindrome);

impl Mul<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn mul(self, rhs: u64) -> Self::Output {
        self.0 * rhs
    }
}

forward_ref_binop!(impl Mul, mul for Palindrome, u64);

impl Mul<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn mul(self, rhs: Palindrome) -> Self::Output {
        self * rhs.0
    }
}

forward_ref_binop!(impl Mul, mul for u64, Palindrome);

impl MulAssign<Palindrome> for u64 {
    #[inline]
    fn mul_assign(&mut self, rhs: Palindrome) {
        *self *= rhs.0
    }
}

forward_ref_op_assign!(impl MulAssign, mul_assign for u64, Palindrome);

impl Not for Palindrome {
    type Output = u64;

    #[inline]
    fn not(self) -> Self::Output {
        !self.0
    }
}

forward_ref_unop!(impl Not, not for Palindrome);

impl Rem<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn rem(self, rhs: u64) -> Self::Output {
        self.0 % rhs
    }
}

forward_ref_binop!(impl Rem, rem for Palindrome, u64);

impl Rem<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn rem(self, rhs: Palindrome) -> Self::Output {
        self % rhs.0
    }
}

forward_ref_binop!(impl Rem, rem for u64, Palindrome);

impl RemAssign<Palindrome> for u64 {
    #[inline]
    fn rem_assign(&mut self, rhs: Palindrome) {
        *self %= rhs.0
    }
}

forward_ref_op_assign!(impl RemAssign, rem_assign for u64, Palindrome);

impl Shl<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn shl(self, rhs: u64) -> Self::Output {
        self.0 << rhs
    }
}

forward_ref_binop!(impl Shl, shl for Palindrome, u64);

impl Shl<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn shl(self, rhs: Palindrome) -> Self::Output {
        self << rhs.0
    }
}

forward_ref_binop!(impl Shl, shl for u64, Palindrome);

impl ShlAssign<Palindrome> for u64 {
    #[inline]
    fn shl_assign(&mut self, rhs: Palindrome) {
        *self <<= rhs.0;
    }
}

forward_ref_op_assign!(impl ShlAssign, shl_assign for u64, Palindrome);

impl Shr<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn shr(self, rhs: u64) -> Self::Output {
        self.0 >> rhs
    }
}

forward_ref_binop!(impl Shr, shr for Palindrome, u64);

impl Shr<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn shr(self, rhs: Palindrome) -> Self::Output {
        self >> rhs.0
    }
}

forward_ref_binop!(impl Shr, shr for u64, Palindrome);

impl ShrAssign<Palindrome> for u64 {
    #[inline]
    fn shr_assign(&mut self, rhs: Palindrome) {
        *self >>= rhs.0;
    }
}

forward_ref_op_assign!(impl ShrAssign, shr_assign for u64, Palindrome);

impl Sub<u64> for Palindrome {
    type Output = u64;

    #[inline]
    fn sub(self, rhs: u64) -> Self::Output {
        self.0 - rhs
    }
}

forward_ref_binop!(impl Sub, sub for Palindrome, u64);

impl Sub<Palindrome> for u64 {
    type Output = u64;

    #[inline]
    fn sub(self, rhs: Palindrome) -> Self::Output {
        self - rhs.0
    }
}

forward_ref_binop!(impl Sub, sub for u64, Palindrome);

impl SubAssign<Palindrome> for u64 {
    #[inline]
    fn sub_assign(&mut self, rhs: Palindrome) {
        *self -= rhs.0
    }
}

forward_ref_op_assign!(impl SubAssign, sub_assign for u64, Palindrome);

pub struct PalindromeIter {
    from: Palindrome,
    to: Palindrome,
}

impl PalindromeIter {
    /// Return an iterator over all palindromes in the range `from..to`.
    ///
    /// **NOTE:** [`std::iter::Step`] is currently nightly/experimental,
    /// so this will have to do for now.
    pub fn from<T: Into<u64>, U: Into<u64>>(from: T, to: U) -> Self {
        Self {
            from: Palindrome::ge(from.into()),
            to: Palindrome::ge(to.into()),
        }
    }

    /// Return an iterator over the first `n` palindromes.
    ///
    /// **NOTE:** Any palindrome larger than [`Palindrome::MAX`] won't be included
    /// and will instead be [`None`].
    pub const fn first_n(n: usize) -> Self {
        Self::first_n_from(n, Palindrome(0))
    }

    /// Return an iterator over the first `n` palindromes from the first palindrome `from`.
    ///
    /// **NOTE:** Any palindrome larger than [`Palindrome::MAX`] won't be included
    /// and will instead be [`None`].
    pub const fn first_n_from(n: usize, from: Palindrome) -> Self {
        let to = match Palindrome::nth(from.to_n() + n) {
            Some(p) => p,
            None => Palindrome::MAX,
        };

        Self { from, to }
    }

    /// Return the length of [`Self`].
    ///
    /// **NOTE:** This function is constant time and much faster than [`Self::count`] for any non-trivial range.
    pub const fn len(&self) -> usize {
        // Calculate length from 0..self.from
        let over_counted = Self::len_from_0(self.from.0);

        // Calculate length from 0..self.to
        let over_count = Self::len_from_0(self.to.0);

        return over_count - over_counted;
    }

    // Doesn't include `to`.
    const fn len_from_0(to: u64) -> usize {
        if to < 10 {
            return to as usize;
        }

        let digits = PalindromeDigits::from_unchecked(to);
        let half_length = digits.len().div_ceil(2);

        let mut count = Self::palindromes_in_n_digits(digits.len() as u8) as isize;
        let mut front_part_as_num = 0isize;
        let mut to_subtract = 1isize;
        let mut idx = 0;
        while idx < half_length {
            to_subtract *= 10;
            front_part_as_num *= 10;
            front_part_as_num += digits.get(idx) as isize;
            idx += 1;
        }
        count += front_part_as_num - to_subtract;

        // If second half of the number is higher than first half, +1.
        let (mut i, mut j) = (half_length - 1, half_length);
        i -= digits.len() % 2; // Don't want to compare center value of uneven digit number.

        // Find the first digits from center and out that differ.
        while i > 0 && digits.get(i) == digits.get(j) {
            i -= 1;
            j += 1;
        }
        if digits.get(i) < digits.get(j) {
            count += 1; // Second half is larger, so ++ that bi***.
        }

        return count as usize;
    }

    // Will crash if n > Self::MAX_N.
    const fn palindromes_in_n_digits(n: u8) -> usize {
        const N_DIGIT_NUMBER_PALINDROME: [usize; 21] = [
            0,
            10,
            19,
            109,
            199,
            1099,
            1999,
            10999,
            19999,
            109999,
            199999,
            1099999,
            1999999,
            10999999,
            19999999,
            109999999,
            199999999,
            1099999999,
            1999999999,
            10999999999,
            19999999999,
        ];

        return N_DIGIT_NUMBER_PALINDROME[n as usize];
    }
}

impl Iterator for PalindromeIter {
    type Item = Palindrome;

    fn next(&mut self) -> Option<Self::Item> {
        if self.from < self.to {
            let next_palindrome = self.from;
            self.from = self.from.next();
            return Some(next_palindrome);
        } else {
            return None;
        }
    }
}

impl DoubleEndedIterator for PalindromeIter {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.to > self.from {
            self.to = self.to.previous();
            return Some(self.to);
        } else {
            return None;
        }
    }
}

pub trait IsPalindrome {
    /// Return whether `self` is a palindrome.
    fn is_palindrome(&self) -> bool;
}

impl IsPalindrome for u64 {
    fn is_palindrome(&self) -> bool {
        if *self % 10 == 0 && *self != 0 {
            return false;
        }

        let mut x = *self;
        let mut right_half = 0;
        while x > right_half {
            right_half = right_half * 10 + x % 10;
            x /= 10;
        }

        return x == right_half || x == right_half / 10;
    }
}

impl IsPalindrome for u32 {
    fn is_palindrome(&self) -> bool {
        (*self as u64).is_palindrome()
    }
}

impl IsPalindrome for u16 {
    fn is_palindrome(&self) -> bool {
        (*self as u64).is_palindrome()
    }
}

impl IsPalindrome for u8 {
    fn is_palindrome(&self) -> bool {
        (*self as u64).is_palindrome()
    }
}

impl IsPalindrome for Palindrome {
    #[inline]
    fn is_palindrome(&self) -> bool {
        true
    }
}

#[cfg(test)]
mod tests {
    use crate::PalindromeIter;

    use super::{Palindrome, PalindromeDigits};

    #[test]
    fn test_palindrome_closest() {
        assert_eq!(11, Palindrome::closest(10));
        assert_eq!(38783, Palindrome::closest(38794));
        assert_eq!(38783, Palindrome::closest(38832));
        assert_eq!(38883, Palindrome::closest(38833));
        assert_eq!(943858349, Palindrome::closest(943854534));
    }

    #[test]
    fn test_palindrome_construct() {
        let pd = PalindromeDigits::from(345);
        assert_eq!(34543, Palindrome::construct(&pd, 5));
        assert_eq!(345543, Palindrome::construct(&pd, 6));
        let pd = PalindromeDigits::from(0);
        assert_eq!(0, Palindrome::construct(&pd, 1));
        assert_eq!(0, Palindrome::construct(&pd, 2));
        let pd = PalindromeDigits::from(1710);
        assert_eq!(1710171, Palindrome::construct(&pd, 7));
        assert_eq!(17100171, Palindrome::construct(&pd, 8));
    }

    #[test]
    #[should_panic]
    fn test_palindrome_construct_panic_on_too_short_length() {
        let pd = PalindromeDigits::from(345);
        assert_eq!(34543, Palindrome::construct(&pd, 4));
    }

    #[test]
    #[should_panic]
    fn test_palindrome_construct_panic_on_too_big_length() {
        let pd = PalindromeDigits::from(345);
        assert_eq!(34543, Palindrome::construct(&pd, 7));
    }

    #[test]
    fn test_palindrome_nth() {
        // REMEMBER IT'S 0-BASED INDEXING.
        for n in 0..=9 {
            assert_eq!(n as u64, Palindrome::nth(n).unwrap());
        }

        // Test large nth values.
        let n = 438907;
        let mut pal = Palindrome::le(0);
        for _ in 0..n {
            pal = pal.next();
        }
        assert_eq!(pal, Palindrome::nth(n).unwrap());

        // Another one.
        let n = 9999;
        let mut pal = Palindrome::le(0);
        for _ in 0..n {
            pal = pal.next();
        }
        assert_eq!(pal, Palindrome::nth(n).unwrap());

        // And another one.
        let n = 109834;
        let mut pal = Palindrome::le(0);
        for _ in 0..n {
            pal = pal.next();
        }
        assert_eq!(pal, Palindrome::nth(n).unwrap());

        // Test None values.
        let n = Palindrome::MAX_N; // 0-based indexing.
        assert_eq!(Palindrome::MAX, Palindrome::nth(n).unwrap());
        let n = Palindrome::MAX_N + 1; // 0-based indexing.
        assert_eq!(None, Palindrome::nth(n));
    }

    #[test]
    fn test_palindrome_previous() {
        let pal = Palindrome(22);
        assert_eq!(11, pal.previous());
        let pal = Palindrome(998899);
        assert_eq!(997799, pal.previous());
        let pal = Palindrome(212);
        assert_eq!(202, pal.previous());
        let pal = Palindrome(202);
        assert_eq!(191, pal.previous());
        let pal = Palindrome(191);
        assert_eq!(181, pal.previous());
        let pal = Palindrome(1991);
        assert_eq!(1881, pal.previous());
        let pal = Palindrome(100001);
        assert_eq!(99999, pal.previous());
        let pal = Palindrome(1001);
        assert_eq!(999, pal.previous())
    }

    #[test]
    fn test_palindrome_next() {
        let pal = Palindrome(22);
        assert_eq!(33, pal.next());
        let pal = Palindrome(998899);
        assert_eq!(999999, pal.next());
        let pal = Palindrome(999999);
        assert_eq!(1000001, pal.next());
        let pal = Palindrome(212);
        assert_eq!(222, pal.next());
        let pal = Palindrome(191);
        assert_eq!(202, pal.next());
        let pal = Palindrome(181);
        assert_eq!(191, pal.next());
        let pal = Palindrome(1881);
        assert_eq!(1991, pal.next());
    }

    #[test]
    fn test_palindrome_le() {
        assert_eq!(9, Palindrome::le(10));
        assert_eq!(11, Palindrome::le(11));
        assert_eq!(11, Palindrome::le(19));
        assert_eq!(99, Palindrome::le(100));
        assert_eq!(997799, Palindrome::le(998001));
        assert_eq!(202, Palindrome::le(209));
        assert_eq!(191, Palindrome::le(201));
        assert_eq!(181, Palindrome::le(190));
        assert_eq!(1881, Palindrome::le(1990));
        assert_eq!(99999, Palindrome::le(100000));
        assert_eq!(999, Palindrome::le(1000));
        assert_eq!(34543, Palindrome::le(34550));
    }

    #[test]
    fn test_palindrome_ge() {
        assert_eq!(11, Palindrome::ge(10));
        assert_eq!(11, Palindrome::ge(11));
        assert_eq!(22, Palindrome::ge(19));
        assert_eq!(101, Palindrome::ge(100));
        assert_eq!(998899, Palindrome::ge(998001));
        assert_eq!(212, Palindrome::ge(209));
        assert_eq!(202, Palindrome::ge(199));
        assert_eq!(191, Palindrome::ge(190));
        assert_eq!(1991, Palindrome::ge(1990));
        assert_eq!(34543, Palindrome::ge(34504));
    }

    #[test]
    fn test_palindromeiter_first_n_palindromes() {
        // First test.
        let n = 912;
        let pal_iter = PalindromeIter::first_n(n);
        assert_eq!(n, pal_iter.len());

        // Second test.
        let n = 0;
        let pal_iter = PalindromeIter::first_n(n);
        assert_eq!(n, pal_iter.len());

        // Third test.
        let n = 1;
        let pal_iter = PalindromeIter::first_n(n);
        assert_eq!(n, pal_iter.len());

        // Fourth test.
        let n = Palindrome::MAX_N; // Max palindromes.
        let pal_iter = PalindromeIter::first_n(n);
        assert_eq!(n, pal_iter.len());

        // Fifth test.
        let n = Palindrome::MAX_N + 1; // Max + 1 palindromes.
        let pal_iter = PalindromeIter::first_n(n);
        assert_eq!(n - 1, pal_iter.len());

        // Test start to end values
        let pal_iter = PalindromeIter::first_n(10);
        for (i, p) in pal_iter.enumerate() {
            assert_eq!(i as u64, p);
        }
    }

    #[test]
    fn test_palindromeiter_first_n_palindromes_from() {
        // First test.
        let n = 912;
        let pal_iter = PalindromeIter::first_n_from(n, Palindrome::le(9));
        assert_eq!(n, pal_iter.len());

        // Second test.
        let n = 0;
        let pal_iter = PalindromeIter::first_n_from(n, Palindrome::closest(38743));
        assert_eq!(n, pal_iter.len());

        // Third test.
        let n = 1;
        let pal_iter = PalindromeIter::first_n_from(n, Palindrome::ge(98734));
        assert_eq!(n, pal_iter.len());

        // Fourth test.
        let n = 32903;
        let pal_iter = PalindromeIter::first_n_from(n, Palindrome::le(2222));
        assert_eq!(n, pal_iter.len());

        // Test start and end values
        let mut pal_iter = PalindromeIter::first_n_from(10, Palindrome::le(22));
        assert_eq!(22u64, pal_iter.next().unwrap());
        for _ in 0..8 {
            pal_iter.next();
        }
        assert_eq!(111u64, pal_iter.next().unwrap());
    }

    #[test]
    fn test_palindromeiter_len() {
        // 10.
        let pal_iter = PalindromeIter::from(0u64, 10u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(2u64, 10u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(3u64, 11u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        // 100.
        let pal_iter = PalindromeIter::from(0u64, 100u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(45u64, 100u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(55u64, 100u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(53u64, 101u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        // 1000.
        let pal_iter = PalindromeIter::from(0u64, 1000u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(34u64, 1000u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(745u64, 1000u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        // 10_000.
        let pal_iter = PalindromeIter::from(0u64, 10_000u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(569u64, 10_000u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        let pal_iter = PalindromeIter::from(28u64, 10_000u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
        // Edge case.
        let pal_iter = PalindromeIter::from(0u64, 668u64);
        assert_eq!(pal_iter.len(), pal_iter.count());
    }

    #[test]
    fn test_palindromeiter_iterate() {
        let pal_iter = PalindromeIter::from(0u64, 101u64);
        let zipped = pal_iter.zip([
            0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99,
        ]);
        for (p, r) in zipped {
            assert_eq!(p, r);
        }
    }

    #[test]
    fn test_palindromeiter_iterate_rev() {
        let pal_iter = PalindromeIter::from(0u64, 101u64).rev();
        let zipped = pal_iter.zip(
            [
                0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99,
            ]
            .iter()
            .rev(),
        );
        for (p, r) in zipped {
            assert_eq!(p, *r);
        }
    }
}