modular 1.0.0

//! # Modular arithmetic
//!
//! `edition: Rust-2018`
//!
//! Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon
//! reaching a certain value - which is known as the **modulus**. A common example would be values
//! on a clock, which wrap around the modulus 12 (for a 12-hour clock)
//!
//! For further information on modular arithmetic, see the
//! [wikipedia](https://en.wikipedia.org/wiki/Modular_arithmetic) article on the same.
//!
//! This crate allows for the creation and usage of such numbers.
//!
//! # 1. Usage
//!
//! To use this crate, add it to your `Cargo.toml`. Sample usage is shown below
//!
//! ### main.rs
//!
//! ```rust
//! use modular::*;
//!
//! // Create a new modulo number from an integer, given a modulus
//! let mod_num = 76.to_modulo(7);
//! let mod_num2 = 45.to_modulo(16);
//!
//! // This is equivalent to using the modulo! macro
//! let mod_mac = modulo!(76, 7);
//! let mod_mac2 = modulo!(78, 16);
//!
//! // Check equality
//! assert!(mod_num == mod_mac);
//! assert!(mod_num2 != mod_mac2);
//!
//! // Addition
//! assert_eq!(mod_num + mod_mac, modulo!(5, 7));
//!
//! // Subtraction
//! assert_eq!(mod_mac2 - mod_num2, modulo!(1, 16));
//!
//! // Multipication
//! assert_eq!(mod_num * mod_mac, modulo!(1, 7));
//!
//! // Congruence
//! assert!(76.is_congruent(41, 7));
//! ```
//!
//! Further examples are given in the examples folder.
//!
//! # 2. Installation
//!
//! For development, you can fork this repo, or clone it directly from github/gitlab.
//! The repo comes with examples of usage in the `/examples` directory.
//!
//! ```bash
//! $> cd <work_dir>
//! $> git clone <gitlab/github>/modulo.git
//! $> cd modulo
//! $> cargo build && cargo test
//! $> cargo run --example fib
//! ```
//!

#![warn(missing_docs)]

use std::fmt;
use std::ops::{Add, Mul, Sub};

/// Trait for modular operations on integers
///
/// Implementing this trait allows for conversion of integers to modular numbers, as well as
/// determining congruence relations between integers.
pub trait Modular {
    /// Returns the modular representation of an integer
    ///
    /// This is the idiomatic way of creating a new modulo number. Alternatively, the `modulo!`
    /// macro is provided, which provides the same functionality.
    fn to_modulo(self, modulus: u32) -> Modulo;

    /// Returns true if the two integers are congruent modulo `n`
    ///
    /// Congruence is determined by the relation:
    ///
    /// `a === b (mod n) if a - b = kn where k is some integer.`
    ///
    /// # Example
    /// ```
    /// # use modular::*;
    /// // Given some integers
    /// let a = 27;
    /// let b = 91;
    /// let c = -1;
    ///
    /// // Assert their congruence for different modulus values
    /// assert_eq!(a.is_congruent(b, 4), true);  // True:  27 - 91 = -64 => n = 4, k = -16
    /// assert_eq!(b.is_congruent(a, 5), false); // False: 91 - 27 = 64  => n = 5, k = 12.8
    /// assert_eq!(a.is_congruent(c, 4), true);  // True:  27 - -1 = 28  => n = 4, k = 7
    /// ```
    fn is_congruent(self, with: impl Into<i32>, modulus: u32) -> bool;
}

/// Holds the modulo representation of a number
///
/// In mathematics, the `%` operation returns the remainder obtained when an integer `a` is divided
/// by another `n`. For instance `32 % 6 = 2`: in this example, 32 can be written in terms of its
/// reminder after being divided by the specified dividend as `2 mod 6`. This is the modulo
/// representation of the number 32, with modulus 6.
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct Modulo {
    remainder: i32,
    modulus: u32,
}

impl Modulo {
    /// Returns the 'remainder' part of a modulo number
    pub fn remainder(self) -> i32 {
        self.remainder
    }

    /// Returns the modulus of a modulo number
    ///
    /// This is sometimes referred to as the 'dividend' as well
    pub fn modulus(self) -> u32 {
        self.modulus
    }
}

impl Modular for i32 {
    fn to_modulo(self, modulus: u32) -> Modulo {
        Modulo {
            remainder: self % modulus as i32,
            modulus,
        }
    }

    fn is_congruent(self, with: impl Into<i32>, modulus: u32) -> bool {
        (self - with.into()) % modulus as i32 == 0
    }
}

impl Add for Modulo {
    type Output = Self;

    /// Adds two `Modulo` numbers
    ///
    /// # Panics
    ///
    /// Panics if the two numbers have different modulus values
    fn add(self, rhs: Self) -> Self {
        if self.modulus() != rhs.modulus() {
            panic!("Addition is only valid for modulo numbers with the same dividend")
        }

        (self.remainder() + rhs.remainder()).to_modulo(self.modulus())
    }
}

impl Sub for Modulo {
    type Output = Self;

    /// Subtracts two `Modulo` numbers
    ///
    /// # Panics
    ///
    /// Panics if the two numbers have different modulus values
    fn sub(self, rhs: Self) -> Self {
        if self.modulus() != rhs.modulus() {
            panic!("Subtraction is only valid for modulo numbers with the same dividend")
        }

        if self.remainder() >= rhs.remainder() {
            modulo!(self.remainder() - rhs.remainder(), self.modulus())
        } else {
            modulo!(
                self.remainder() - rhs.remainder() + self.modulus() as i32,
                self.modulus()
            )
        }
    }
}

impl Mul for Modulo {
    type Output = Self;

    /// Multiplies two `Modulo` numbers
    ///
    /// # Panics
    ///
    /// Panics if the two numbers have different modulus values
    fn mul(self, rhs: Self) -> Self {
        if self.modulus() != rhs.modulus() {
            panic!("Multiplication is only valid for modulo numbers with the same dividend")
        }

        (self.remainder() * rhs.remainder()).to_modulo(self.modulus())
    }
}

impl fmt::Display for Modulo {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?} mod {:?}", self.remainder, self.modulus)
    }
}

/// Creates a new `Modulo` instance
///
/// Delegates to the `to_modulo()` function provided by the `Modular` trait
#[macro_export]
macro_rules! modulo {
    ($rem:expr, $div:expr) => {
        $rem.to_modulo($div)
    };
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn create_using_trait() {
        assert!(27.to_modulo(5) == modulo!(2, 5));
    }

    #[test]
    fn create_using_macro() {
        assert!(modulo!(99, 4) == 99.to_modulo(4));
    }

    #[test]
    fn get_remainder() {
        assert_eq!(modulo!(26, 11).remainder(), 4);
    }

    #[test]
    fn get_modulus() {
        assert_eq!(modulo!(121, 17).modulus(), 17);
    }

    #[test]
    fn add_successfully() {
        assert!(modulo!(23, 4) + modulo!(11, 4) == modulo!(2, 4));
    }

    #[test]
    #[should_panic]
    fn add_panics_with_different_moduli() {
        assert!(modulo!(23, 5) + modulo!(11, 6) == modulo!(2, 5));
    }

    #[test]
    fn subtract_successfully() {
        assert!(modulo!(22, 4) - modulo!(13, 4) == modulo!(1, 4));
    }

    #[test]
    #[should_panic]
    fn subtract_panics_with_different_moduli() {
        assert!(modulo!(47, 43) - modulo!(5, 27) == modulo!(12, 13));
    }

    #[test]
    fn multiply_successfully() {
        assert!(modulo!(2, 4) * modulo!(19, 4) == modulo!(2, 4));
    }

    #[test]
    #[should_panic]
    fn multiply_panics_with_different_moduli() {
        assert!(modulo!(91, 92) - modulo!(8, 9) == modulo!(12, 47));
    }

    #[test]
    fn string_representation() {
        let mod_new = modulo!(6, 7u32);
        assert_eq!(format!("{}", mod_new), "6 mod 7");
    }
}