/// Calculate a number in the fibonacci sequence,
/// using recursion and a lookup table
///
/// Can calculate up to 186 using native unsigned 128 bit integers.
///
/// Example:
/// ```rust
/// use rusty_fib_facts::mem_fibonacci;
///
/// let valid = mem_fibonacci(45); // Some(1134903170)
/// # assert_eq!(1134903170, mem_fibonacci(45).unwrap());
/// # assert!(valid.is_some());
///
/// let invalid = mem_fibonacci(187); // None
/// # assert!(invalid.is_none());
/// ```
#[inline]
pub fn mem_fibonacci(n: usize) -> Option<u128> {
    let mut table = [0u128; 187];
    table[0] = 0;
    table[1] = 1;
    table[2] = 1;

    /// Actual calculating function for `fibonacci`
    fn f(n: usize, table: &mut [u128]) -> Option<u128> {
        if n < 2 {
            // The first values are predefined.
            return Some(table[n]);
        }

        if n > 186 {
            return None;
        }

        match table[n] {
            // The lookup array starts out zeroed, so a zero
            // is a not yet calculated value
            0 => {
                let a = f(n - 1, table)?;
                let b = f(n - 2, table)?;

                table[n] = a + b;

                Some(table[n])
            }
            x => Some(x),
        }
    }

    f(n, &mut table)
}

/// Calculate a number in the fibonacci sequence,
/// using naive recursion
///
/// REALLY SLOW
///
/// Can calculate up to 186 using native unsigned 128 bit integers.
#[inline]
pub fn rec_fibonacci(n: usize) -> Option<u128> {
    if matches!(n, 0 | 1) {
        Some(n as u128)
    } else {
        let a = rec_fibonacci(n - 1)?;
        let b = rec_fibonacci(n - 2)?;

        a.checked_add(b)
    }
}

/// Calculate a number in the fibonacci sequence,
///
/// Can calculate up to 186 using native unsigned 128 bit integers.
///
/// Example:
/// ```rust
/// use rusty_fib_facts::fibonacci;
///
/// let valid = fibonacci(45); // Some(1134903170)
/// # assert_eq!(1134903170, fibonacci(45).unwrap());
/// # assert!(valid.is_some());
///
/// let invalid = fibonacci(187); // None
/// # assert!(invalid.is_none());
/// ```
#[inline]
pub fn fibonacci(n: usize) -> Option<u128> {
    let mut a: u128 = 0;
    let mut b: u128 = 1;

    if matches!(n, 0 | 1) {
        Some(n as u128)
    } else {
        for _ in 0..n - 1 {
            let c: u128 = a.checked_add(b)?;

            a = b;
            b = c;
        }

        Some(b)
    }
}