//!
//! Algebraic _fields_.
//!
//! An algebraic _field_ is a _commutative_ _ring_ (with identity) `R`,
//! where each _invertible_ field element `f` has a unique
//! _multiplicative_ _inverse_ `f^-1`. The inverse operation is called
//! _invert_.
//!
//! # Axioms
//!
//! ```notrust
//! ∀g, 1 ∈ R
//!
//! Inverse: ∃g^-1 ∈ R: g × g^-1 = g^-1 × g = 1.
//! ```
//!
//! # References
//!
//! See [references] for a formal definition of a field.
//!
#![doc(include = "../doc/references.md")]

use crate::helpers::*;
use crate::numeric::*;
use crate::com_ring::*;


///
/// An algebraic _field_.
///
pub trait Field: ComRing {

  /// The unique _multiplicative_ _inverse_ of a field element. The
  /// inverse is only defined for _invertible_ field elements.
  fn invert(&self) -> Self;


  /// Test for an _invertible_ field element.
  fn is_invertible(&self) -> bool {
    *self != Self::zero()
  }


  /// The multiplicative "division" of two field elements.
  fn div(&self, other: &Self) -> Self {
    self.mul(&other.invert())
  }
}


///
/// The _left_ _multiplicative_ _inverse_ axiom.
///
pub fn left_inverse<T: Field>(x: &T) -> bool {
  x.invert().mul(x) == T::one()
}


///
/// The _right_ _multiplicative_ _inverse_ axiom.
///
pub fn right_inverse<T: Field>(x: &T) -> bool {
  x.mul(&x.invert()) == T::one()
}


///
/// The _two_ _sided_ _multiplicative_ _inverse_ axiom.
///
pub fn inverse<T: Field>(x: &T) -> bool {
  left_inverse(x) && right_inverse(x)
}


///
/// The derived property of _additive_ _cancellation_.
///
pub fn add_cancellation<T: Field>(x: &T, y: &T, z: &T) -> bool {
  imply(x.add(y) == z.add(y), x == z)
}


///
/// The derived property of _multiplicative_ _cancellation_.
///
pub fn mul_cancellation<T: Field>(x: &T, y: &T, z: &T) -> bool {
  if y.is_zero() {return true;}

  imply(x.mul(y) == z.mul(y), x == z)
}


///
/// The derived property of _zero_ _cancellation_.
///
pub fn zero_cancellation<T: Field>(x: &T, y: &T) -> bool {
  imply(x.mul(y).is_zero(), x.is_zero() || y.is_zero())
}


///
/// The left _numeric_ _multiplicative_ _inverse_ axiom.
///
pub fn num_left_inverse<T: Field + NumEq>(x: &T, eps: &T::Eps) -> bool {
  x.invert().mul(x).num_eq(&T::one(), eps)
}


///
/// The right _numeric_ _multiplicative_ _inverse_ axiom.
///
pub fn num_right_inverse<T: Field + NumEq>(x: &T, eps: &T::Eps) -> bool {
  x.mul(&x.invert()).num_eq(&T::one(), eps)
}


///
/// The two sided _numeric_ _multiplicative_ _inverse_ axiom.
///
pub fn num_inverse<T: Field + NumEq>(x: &T, eps: &T::Eps) -> bool {
  num_left_inverse(x, eps) && num_right_inverse(x, eps)
}


///
/// The derived property of _numeric_ _additive_ _cancellation_.
///
pub fn num_add_cancellation<T: Field + NumEq>(x: &T, y: &T, z: &T, eps: &T::Eps) -> bool {
  imply(x.add(y).num_eq(&z.add(y), eps), x.num_eq(z, eps))
}


///
/// The derived property of _numeric_ _multiplicative_ _cancellation_.
///
pub fn num_mul_cancellation<T: Field + NumEq>(x: &T, y: &T, z: &T, eps: &T::Eps) -> bool {
  if y.is_zero() {return true;}

  imply(x.mul(y).num_eq(&z.mul(y), eps), x.num_eq(z, eps))
}


///
/// The derived property of _numeric_ _zero_ _cancellation_.
///
pub fn num_zero_cancellation<T: Field + NumEq>(x: &T, y: &T, _eps: &T::Eps) -> bool {
  imply(x.mul(y).is_zero(), x.is_zero() || y.is_zero())
}


///
/// A macro for `Field` implementations for built-in floating point
/// types. Probably not needed if Rust had a `Float` super-trait.
///
macro_rules! float_field {
  ($type:ty) => {
    impl Field for $type {

      /// Inversion is just floating point inverse.
      fn invert(&self) -> Self {
        self.recip()
      }
    }
  };

  ($type:ty, $($others:ty),+) => {
    float_field! {$type}
    float_field! {$($others),+}
  };
}


// Field floating point types.
float_field! {
  f32, f64
}


///
/// 0-tuples form a field.
///
impl Field for () {

  /// Inverted value can only be `()`.
  fn invert(&self) -> Self {}


  /// The only value is invertible.
  fn is_invertible(&self) -> bool {
    true
  }
}


///
/// 1-tuples form a field when their items do.
///
impl<A: Field> Field for (A,) {

  /// Inversion is by matching element.
  fn invert(&self) -> Self {
    (self.0.invert(), )
  }


  /// Invertibility is across the tuple.
  fn is_invertible(&self) -> bool {
    self.0.is_invertible()
  }
}


///
/// 2-tuples form a field when their items do.
///
impl<A: Field, B: Field> Field for (A, B) {

  /// Inversion is by matching element.
  fn invert(&self) -> Self {
    (self.0.invert(), self.1.invert())
  }


  /// Invertibility is across the tuple.
  fn is_invertible(&self) -> bool {
    self.0.is_invertible() && self.1.is_invertible()
  }
}


///
/// 3-tuples form a field when their items do.
///
impl<A: Field, B: Field, C: Field> Field for (A, B, C) {

  /// Inversion is by matching element.
  fn invert(&self) -> Self {
    let (a, b, c) = self;

    (a.invert(), b.invert(), c.invert())
  }


  /// Invertibility is across the tuple.
  fn is_invertible(&self) -> bool {
    let (a, b, c) = self;

    a.is_invertible() && b.is_invertible() && c.is_invertible()
  }
}


///
/// A macro for `Field` implementations for arrays. Maybe not needed if
/// Rust had _const_ _generics_.
///
macro_rules! array_field {
  ($size:expr) => {
    impl<T: Copy + Field> Field for [T; $size] {

      // Invert each array element.
      fn invert(&self) -> Self {
        self.map(&|&x| x.invert())
      }


      // Test each array element for invertibility.
      fn is_invertible(&self) -> bool {
        self.all(&|&x| x.is_invertible())
      }
    }
  };

  ($size:expr, $($others:expr),+) => {
    array_field! {$size}
    array_field! {$($others),+}
  };
}


// Array field types.
array_field! {
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
}


// Module unit tests are in a sub-module.
#[cfg(test)]
mod tests;