finite-fields 0.5.2

use std::fmt;
use std::cmp::Ordering;
use std::ops::{Add, Sub, Mul, Div, BitXor, Index, IndexMut};
use error::{DivisionError, OverflowError};

/// The base binary type, a unit-width binary digit.
#[derive(Clone,Copy,PartialEq,Eq)]
pub struct b1(bool);

NewtypeFrom! {
  () pub struct b1(bool);
}

impl b1 {
  pub fn new(val: bool) -> b1 {
    b1(val)
  }
}

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

/// Shorthand for zero in unit-width binary type.
pub const ZERO: b1 = b1(false);
/// Shorthand for one in unit-width binary type.
pub const ONE: b1 = b1(true);

impl<'a> PartialEq<b1> for &'a b1 {
  fn eq(&self, other: &b1) -> bool {
    self.0 == other.0
  }
}
impl<'a> PartialEq<&'a b1> for b1 {
  fn eq(&self, other: &&'a b1) -> bool {
    self.0 == other.0
  }
}

/// Peano arithmetic operators.
pub trait Peano where Self: Sized {
  /// Produces the next integer value in the field of self (i.e., increment).
  fn successor(&self) -> Result<Self, OverflowError>;
  /// Produces the previous integer value in the field of self (i.e.,
  /// decrement).
  fn predecessor(&self) -> Result<Self, OverflowError>;
  /// Total ordering function.
  fn cmp (&self, other: &Self) -> Ordering;
}

impl Peano for b1 {
  fn successor(&self) -> Result<b1, OverflowError> {
    match self {
      &ZERO => Ok(ONE),
      &ONE => Err(OverflowError::Default { arg1: self.to_string(),
                                           arg2: ONE.to_string() })
    }
  }

  /// Peano arithmetic function.
  fn predecessor(&self) -> Result<b1, OverflowError> {
    match self {
      &ONE => Ok(ZERO),
      &ZERO => Err(OverflowError::Default { arg1: self.to_string(),
                                            arg2: ONE.to_string() })
    }
  }

  /// Total ordering function.
  fn cmp (&self, other: &Self) -> Ordering {
    if &self == other { Ordering::Equal }
    else if let &Ok(next) = &self.successor() {
      if next == other { Ordering::Less }
      else { Ordering::Greater }
    }
    else { Ordering::Greater }
  }
}

impl PartialOrd for b1 {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

/// Arithmetic addition with overflow error.
impl Add for b1 {
  type Output = Result<b1, OverflowError>;
  fn add(self, other: b1) -> Result<b1, OverflowError> {
    match other {
      ZERO => Ok(self),
      ONE => self.successor()
    }
  }
}
impl<'a> Add<b1> for &'a b1 {
  type Output = Result<b1, OverflowError>;
  fn add(self, other: b1) -> Result<b1, OverflowError> {
    match other {
      ZERO => Ok(*self),
      ONE => self.successor()
    }    
  }
}
impl<'a> Add<&'a b1> for &'a b1 {
  type Output = Result<b1, OverflowError>;
  fn add(self, other: &b1) -> Result<b1, OverflowError> {
    match other {
      &ZERO => Ok(ZERO),
      &ONE => self.successor()
    }
  }
}

/// Arithmetic subtraction with overflow as error.
impl Sub for b1 {
  type Output = Result<b1, OverflowError>;
  fn sub(self, other: b1) -> Result<b1, OverflowError> {
    match other {
      ZERO => Ok(self),
      ONE => self.predecessor()
    }
  }
}
impl<'a> Sub<b1> for &'a b1 {
  type Output = Result<b1, OverflowError>;
  fn sub(self, other: b1) -> Result<b1, OverflowError> {
    match other {
      ZERO => Ok(*self),
      ONE => self.predecessor()
    }
  }
}
impl<'a> Sub<&'a b1> for &'a b1 {
  type Output = Result<b1, OverflowError>;
  fn sub(self, other: &b1) -> Result<b1, OverflowError> {
    match other {
      &ZERO => Ok(*self),
      &ONE => self.predecessor()
    }
  }
}

impl Mul for b1 {
  type Output = Result<Self, OverflowError>;
  fn mul(self, other: b1) -> Result<b1, OverflowError> {
    Ok(b1(self.0 && other.0))
  }
}
impl<'a> Mul<b1> for &'a b1 {
  type Output = Result<b1, OverflowError>;
  fn mul(self, other: b1) -> Result<b1, OverflowError> {
    Ok(b1(self.0 && other.0))
  }

}
impl<'a> Mul<&'a b1> for &'a b1 {
  type Output = Result<b1, OverflowError>;
  fn mul(self, other: &b1) -> Result<b1, OverflowError> {
    Ok(b1(self.0 && other.0))
  }
}

impl Div for b1 {
  type Output = Result<Self, DivisionError>;
  fn div(self, other: b1) -> Result<b1, DivisionError> {
    if other == ZERO {
      Err(DivisionError::DivideByZeroError {
        arg1: self.to_string()
      })
    } else { Ok(self) }
  }
}
impl<'a> Div<b1> for &'a b1 {
  type Output = Result<b1, DivisionError>;
  fn div(self, other: b1) -> Result<b1, DivisionError> {
    if other == ZERO {
      Err(DivisionError::DivideByZeroError {
        arg1: self.to_string()
      })
    } else { Ok(*self) }
  }

}
impl<'a> Div<&'a b1> for &'a b1 {
  type Output = Result<b1, DivisionError>;
  fn div(self, other: &b1) -> Result<b1, DivisionError> {
    if other == ZERO {
      Err(DivisionError::DivideByZeroError {
        arg1: self.to_string()
      })
    } else { Ok(*self) }
  }
}

impl BitXor for b1 {
  type Output = Self;
  fn bitxor(self, other: b1) -> Self {
    b1(self.0 ^ other.0)
  }
}

/// A two-digit binary number.
#[derive(Clone, Copy, PartialEq)]
pub struct b2([b1; 2]);

impl b2 {
  pub fn new(vals: [b1; 2]) -> b2 {
    b2(vals)
  }
}

impl fmt::Display for b2 {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    write!(f, "{}{}", self.0[0], self.0[1])
  }
}

// fn index<'a>(&'a self, index: Idx) -> &'a Self::Output;
impl<'a> Index<usize> for b2 {
  type Output = b1;

  fn index<'b>(&'b self, index: usize) -> &'b b1 {
    &self.0[index]
  }
}

impl IndexMut<usize> for b2 {
  fn index_mut<'a>(&'a mut self, index: usize) -> &'a mut b1 {
    &mut self.0[index]
  }
}

/// Arithmetic addition with overflow error.
impl Add for b2 {
  type Output = Result<Self, OverflowError>;

  fn add(self, other: b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO; 2]);
    let mut carry = false;
    
    for place in (0..other.0.len()).rev() {
      // Handle the carry flag first if true
      let augend = match carry {
        false => self.0[place].clone(),
        true => match self.0[place].successor() {
          Ok(res) => {
            res.clone()
          },
          Err(_) => {
            ZERO
          }
        }
      };

      // Do the addition
      match augend + other.0[place] {
        Ok(res) => {
          output.0[place] = res;
          carry = false;
        }
        Err(_) => {
          output.0[place] = ZERO;
          carry = true
        }
      }
    }

    if carry {
      Err(OverflowError::Default { arg1: self.to_string(),
                                   arg2: other.to_string() })
    } else {
      Ok(output)
    }
  }
}
impl<'a> Add<b2> for &'a b2 {
  type Output = Result<b2, OverflowError>;

  fn add(self, other: b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO; 2]);
    let mut carry = false;
    
    for place in (0..other.0.len()).rev() {
      // Handle the carry flag first if true
      let augend = match carry {
        false => self.0[place].clone(),
        true => match self.0[place].successor() {
          Ok(res) => {
            res.clone()
          },
          Err(_) => {
            ZERO
          }
        }
      };

      // Do the addition
      match augend + other.0[place] {
        Ok(res) => {
          output.0[place] = res;
          carry = false;
        }
        Err(_) => {
          output.0[place] = ZERO;
          carry = true
        }
      }
    }

    if carry {
      Err(OverflowError::Default { arg1: self.to_string(),
                                   arg2: other.to_string() })
    } else {
      Ok(output)
    }
  }
}
impl<'a> Add<&'a b2> for &'a b2 {
  type Output = Result<b2, OverflowError>;

  fn add(self, other: &b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO; 2]);
    let mut carry = false;
    
    for place in (0..other.0.len()).rev() {
      // Handle the carry flag first if true
      let augend = match carry {
        false => self.0[place].clone(),
        true => match self.0[place].successor() {
          Ok(res) => {
            res.clone()
          },
          Err(_) => {
            ZERO
          }
        }
      };

      // Do the addition
      match augend + other.0[place] {
        Ok(res) => {
          output.0[place] = res;
          carry = false;
        }
        Err(_) => {
          output.0[place] = ZERO;
          carry = true
        }
      }
    }

    if carry {
      Err(OverflowError::Default { arg1: self.to_string(),
                                   arg2: other.to_string() })
    } else {
      Ok(output)
    }
  }
}

/// Wrapping arithmetic subtraction with overflow error.
impl Sub for b2 {
  type Output = Result<b2, OverflowError>;

  fn sub(self, other: b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO; 2]);
    let mut carry = false;
    
    for place in (0..other.0.len()).rev() {
      // Handle the carry flag first if true
      let augend = match carry {
        false => self.0[place],
        true => match self.0[place].predecessor() {
          Ok(res) => {
            res
          },
          Err(_) => {
            ZERO
          }
        }
      };

      // Do the addition
      match augend - other.0[place] {
        Ok(res) => {
          output.0[place] = res;
          carry = false;
        }
        Err(_) => {
          output.0[place] = ONE;
          carry = true
        }
      }
    }

    if carry {
      Err(OverflowError::Default { arg1: self.to_string(),
                                   arg2: other.to_string() })
    } else {
      Ok(output)
    }
  }
}
impl<'a> Sub<b2> for &'a b2 {
  type Output = Result<b2, OverflowError>;

  fn sub(self, other: b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO; 2]);
    let mut carry = false;
    
    for place in (0..other.0.len()).rev() {
      // Handle the carry flag first if true
      let augend = match carry {
        false => self.0[place],
        true => match self.0[place].predecessor() {
          Ok(res) => {
            res
          },
          Err(_) => {
            ZERO
          }
        }
      };

      // Do the addition
      match augend - other.0[place] {
        Ok(res) => {
          output.0[place] = res;
          carry = false;
        }
        Err(_) => {
          output.0[place] = ONE;
          carry = true
        }
      }
    }

    if carry {
      Err(OverflowError::Default { arg1: self.to_string(),
                                   arg2: other.to_string() })
    } else {
      Ok(output)
    }
  }
}
impl<'a> Sub<&'a b2> for &'a b2 {
  type Output = Result<b2, OverflowError>;

  fn sub(self, other: &b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO; 2]);
    let mut carry = false;
    
    for place in (0..other.0.len()).rev() {
      // Handle the carry flag first if true
      let augend = match carry {
        false => self.0[place],
        true => match self.0[place].predecessor() {
          Ok(res) => {
            res
          },
          Err(_) => {
            ZERO
          }
        }
      };

      // Do the addition
      match augend - other.0[place] {
        Ok(res) => {
          output.0[place] = res;
          carry = false;
        }
        Err(_) => {
          output.0[place] = ONE;
          carry = true
        }
      }
    }

    if carry {
      Err(OverflowError::Default { arg1: self.to_string(),
                                   arg2: other.to_string() })
    } else {
      Ok(output)
    }
  }
}

/// This implementation is done "in reverse" of the expected logical order; it
/// uses the `Add` and `Sub` impls instead of the converse.
impl Peano for b2 {
  fn successor(&self) -> Result<b2, OverflowError> {
    self + b2([ZERO, ONE])
  }

  /// Peano arithmetic function.
  fn predecessor(&self) -> Result<b2, OverflowError> {
    self - b2([ZERO, ONE])
  }

  /// Total ordering function.
  fn cmp (&self, other: &Self) -> Ordering {
    if *self == *other { Ordering::Equal }
    else {
      match *self - *other {
        Ok(_) => Ordering::Greater,
        Err(_) => Ordering::Less
      }
    }
  }
}

impl PartialOrd for b2 {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

impl BitXor for b2 {
  type Output = Self;
  fn bitxor(self, other: b2) -> Self {
    let mut output = b2([ZERO; 2]);
    for place in (0..other.0.len()).rev() {
      output.0[place] = self.0[place] ^ other.0[place]
    }
    output
  }
}

/// Bit shifting.
pub trait Shift {
  /// Shifts the bit vector once to the right, padding with zero on the left and
  /// discarding on the right.
  fn shift_right(&self) -> Self;
  /// Shifts the bit vector once to the left, padding with zero on the right and
  /// discarding on the left.
  fn shift_left(&self) -> Self;
}

impl Shift for b2 {
  fn shift_right(&self) -> Self {
    b2([ZERO, self.0[0]])
  }
  fn shift_left(&self) -> Self {
    b2([self.0[1], ZERO])
  }
}


impl Mul for b2 {
  type Output = Result<b2, OverflowError>;
  
  fn mul(self, other: b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO, ZERO]);
    let mut mult_rhs = other.clone();
    let one = b2([ZERO, ONE]);
    let zero = b2([ZERO; 2]);
    
    while mult_rhs > zero {
      if let Ok(sum) = output + self {
        output = sum
      } else {
        // overflow case
        return Err(OverflowError::Default { arg1: self.to_string(),
                                            arg2: other.to_string() })
      }
      mult_rhs = (mult_rhs - one).unwrap();
    }
    
    Ok(output)
  }
}
impl<'a> Mul<b2> for &'a b2 {
  type Output = Result<b2, OverflowError>;
  
  fn mul(self, other: b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO, ZERO]);
    let mut mult_rhs = other.clone();
    let one = b2([ZERO, ONE]);
    let zero = b2([ZERO; 2]);
    
    while mult_rhs > zero {
      if let Ok(sum) = output + *self {
        output = sum
      } else {
        // overflow case
        return Err(OverflowError::Default { arg1: self.to_string(),
                                            arg2: other.to_string() })
      }
      mult_rhs = (mult_rhs - one).unwrap();
    }
    
    Ok(output)
  }
}
impl<'a> Mul<&'a b2> for &'a b2 {
  type Output = Result<b2, OverflowError>;
  
  fn mul(self, other: &'a b2) -> Result<b2, OverflowError> {
    let mut output = b2([ZERO, ZERO]);
    let mut mult_rhs = other.clone();
    let one = b2([ZERO, ONE]);
    let zero = b2([ZERO; 2]);
    
    while mult_rhs > zero {
      if let Ok(sum) = output + *self {
        output = sum
      } else {
        // overflow case
        return Err(OverflowError::Default { arg1: self.to_string(),
                                            arg2: other.to_string() })
      }
      mult_rhs = (mult_rhs - one).unwrap();
    }
    
    Ok(output)
  }
}
/// Implementation of division as repeated subtraction.
impl Div<b2> for b2 {
  type Output = Result<b2, DivisionError>;
  
  fn div(self, other: b2) -> Result<b2, DivisionError> {
    let one = b2([ZERO, ONE]);
    let zero = b2([ZERO; 2]);

    if other == zero {
      return Err(DivisionError::DivideByZeroError { arg1: self.to_string() });
    } else if self < other {
      // division is guaranteed to overflow in this case
      return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                arg2: other.to_string() })
    }
    
    let mut div_lhs = other.clone();
    let mut sub_count = zero;
    
    while div_lhs > other {
      if let Ok(difference) = div_lhs - other {
        div_lhs = difference;
        if let Ok(sum) = sub_count + one {
          sub_count = sum;
        } else {
          return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                    arg2: other.to_string() })
        }
      } else {
        break;
      }
    }

    Ok(sub_count)
  }
}
impl<'a> Div<b2> for &'a b2 {
  type Output = Result<b2, DivisionError>;
  
  fn div(self, other: b2) -> Result<b2, DivisionError> {
    let one = b2([ZERO, ONE]);
    let zero = b2([ZERO; 2]);

    if other == zero {
      return Err(DivisionError::DivideByZeroError { arg1: self.to_string() })
    } else if self < &other {
      // division is guaranteed to overflow in this case
      return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                arg2: other.to_string() })
    }
    
    let mut div_lhs = other.clone();
    let mut sub_count = zero;
    
    while div_lhs > other {
      if let Ok(difference) = div_lhs - other {
        div_lhs = difference;
        if let Ok(sum) = sub_count + one {
          sub_count = sum;
        } else {
          return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                    arg2: other.to_string() })
        }
      } else {
        break;
      }
    }

    Ok(sub_count)
  }
}
impl<'a> Div<&'a b2> for &'a b2 {
  type Output = Result<b2, DivisionError>;
  
  fn div(self, other: &b2) -> Result<b2, DivisionError> {
    let one = b2([ZERO, ONE]);
    let zero = b2([ZERO; 2]);

    if *other == zero {
      return Err(DivisionError::DivideByZeroError { arg1: self.to_string() })
    } else if self < other {
      // division is guaranteed to overflow in this case
      return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                arg2: other.to_string() })
    }
    
    let mut div_lhs = other.clone();
    let mut sub_count = zero;
    
    while div_lhs > *other {
      if let Ok(difference) = div_lhs - *other {
        div_lhs = difference;
        if let Ok(sum) = sub_count + one {
          sub_count = sum;
        } else {
          return Err(DivisionError::OverflowError { arg1: self.to_string(),
                                                    arg2: other.to_string() })
        }
      } else {
        break;
      }
    }

    Ok(sub_count)
  }
}