#![allow(dead_code)]
pub mod util;
pub mod iter;
use std::collections::VecDeque;
use std::convert::TryFrom;
use std::ops::{Shl, Shr};
use util::*;
use iter::BorrowedNumberIter;
pub type Digit = u8;
pub type Pair = (Digit, Digit);
pub type Bucket = usize;
#[derive(Debug)]
pub struct Base {
base: u32,
addition_table: Vec<Pair>,
multiplication_table: Vec<Pair>,
digit_width: usize,
digits_per_bucket: usize,
digit_bitmask: usize,
}
impl Base {
pub fn new(base: u32) -> Self {
let mut addition_table = Vec::new();
let mut multiplication_table = Vec::new();
for (add, mul) in ArithmeticPrecomputation::new(base) {
addition_table.push(add);
multiplication_table.push(mul);
}
let (digit_width, digits_per_bucket, digit_bitmask) = bitwise_parameters(base);
Self {
base,
addition_table,
multiplication_table,
digit_width,
digits_per_bucket,
digit_bitmask
}
}
pub fn add_digits(&self, a: Digit, b: Digit) -> Pair {
*self.addition_table.get(pair_index((a, b), self.base)).unwrap()
}
pub fn multiply_digits(&self, a: Digit, b: Digit) -> Pair {
*self.multiplication_table.get(pair_index((a, b), self.base)).unwrap()
}
pub fn digits_per_bucket(&self) -> usize {
self.digits_per_bucket
}
pub fn digit_width(&self) -> usize {
self.digit_width
}
pub fn digit_bitmask(&self) -> usize {
self.digit_bitmask
}
pub fn bucket_index(&self, idx: usize) -> usize {
idx / self.digits_per_bucket
}
pub fn digit_index(&self, idx: usize) -> usize {
idx % self.digits_per_bucket
}
pub fn indexes(&self, idx: usize) -> (usize, usize) {
(self.bucket_index(idx), self.digit_index(idx))
}
}
#[derive(Debug)]
pub struct Number<'base> {
buckets: VecDeque<Bucket>,
digits: usize,
power: isize,
sign: Sign,
base: &'base Base
}
impl<'base> Number<'base> {
pub fn new(base: &'base Base) -> Self {
Self {
buckets: VecDeque::new(),
digits: 0,
power: 0,
sign: Sign::Positive,
base
}
}
pub fn with_capacity(base: &'base Base, digits: usize) -> Self {
let mut buckets = digits / base.digits_per_bucket();
if digits % base.digits_per_bucket() != 0 {
buckets += 1;
}
Self {
buckets: VecDeque::with_capacity(buckets),
digits: 0,
power: 0,
sign: Sign::Positive,
base
}
}
pub fn digits(&self) -> usize {
self.digits
}
pub fn power(&self) -> isize {
self.power
}
pub fn sign(&self) -> Sign {
self.sign
}
pub fn positive(&self) -> bool {
self.sign == Sign::Positive
}
pub fn negative(&self) -> bool {
self.sign == Sign::Negative
}
pub fn get(&self, idx: usize) -> Option<Digit> {
if idx > self.digits || self.digits == 0 {
return None;
}
let (bucket_idx, digit_idx) = self.base.indexes(idx);
Some(self.get_digit(bucket_idx, digit_idx))
}
pub fn set(&mut self, idx: usize, digit: Digit) {
if idx > self.digits {
panic!("Attempted to set inaccessible digit.");
}
if idx == self.digits {
self.push_high(digit);
return;
}
let (bucket_idx, digit_idx) = self.base.indexes(idx);
self.set_digit(bucket_idx, digit_idx, digit);
}
pub fn push_high(&mut self, digit: Digit) {
let (bucket_idx, digit_idx) = self.base.indexes(self.digits);
if digit_idx == 0 {
self.buckets.push_back(digit as Bucket)
} else {
self.set_digit(bucket_idx, digit_idx, digit)
}
self.digits += 1;
}
pub fn pop_high(&mut self) -> Option<Digit> {
if self.digits == 0 {
return None;
}
let (bucket_idx, digit_idx) = self.base.indexes(self.digits - 1);
let digit = self.get_digit(bucket_idx, digit_idx);
self.digits -= 1;
if digit_idx == 0 {
self.buckets.pop_back();
}
Some(digit)
}
pub fn push_low(&mut self, digit: Digit) {
let (bucket_idx, digit_idx) = (0, 0);
if self.digits == 0 || self.base.digit_index(self.digits - 1) == self.base.digits_per_bucket - 1 {
self.buckets.push_back(0)
}
self.shift_digits_high(1);
self.set_digit(bucket_idx, digit_idx, digit);
self.digits += 1;
}
pub fn pop_low(&mut self) -> Option<Digit> {
if self.digits == 0 {
return None;
}
let (bucket_idx, digit_idx) = (0, 0);
let digit = self.get_digit(bucket_idx, digit_idx);
self.shift_digits_low(1);
self.digits -= 1;
Some(digit)
}
fn set_digit(&mut self, bucket_idx: usize, digit_idx: usize, digit: Digit) {
let bucket = self.buckets.get_mut(bucket_idx).expect("Attempted to set digit in uninitialzed bucket");
let shift = self.base.digit_width() * digit_idx;
*bucket = (*bucket & !(self.base.digit_bitmask() << shift)) | ((digit as usize) << shift);
}
fn get_digit(&self, bucket_idx: usize, digit_idx: usize) -> Digit {
let bucket = self.buckets.get(bucket_idx).expect("Attempted to fetch digit from uninitialzed bucket.");
let shift = self.base.digit_width() * digit_idx;
((bucket & (self.base.digit_bitmask() << shift)) >> shift) as Digit
}
fn shift_digits_high(&mut self, shift: usize) {
if self.digits == 0 {
return;
}
for _ in 0..shift {
for idx in (0..self.digits).into_iter().rev() {
let (current_bucket_idx, current_digit_idx) = self.base.indexes(idx);
let digit = self.get_digit(current_bucket_idx, current_digit_idx);
let (new_bucket_idx, new_digit_idx) = self.base.indexes(idx + 1);
self.set_digit(new_bucket_idx, new_digit_idx, digit);
}
}
}
fn shift_digits_low(&mut self, shift: usize) {
if self.digits == 0 {
return;
}
for _ in 0..shift {
for idx in 1..self.digits {
let (current_bucket_idx, current_digit_idx) = self.base.indexes(idx);
let digit = self.get_digit(current_bucket_idx, current_digit_idx);
let (new_bucket_idx, new_digit_idx) = self.base.indexes(idx - 1);
self.set_digit(new_bucket_idx, new_digit_idx, digit);
}
}
}
fn add_buckets_high(&mut self, buckets: usize) {
self.buckets.reserve(buckets);
for _bucket in 0..buckets {
self.buckets.push_front(0);
}
}
fn add_buckets_low(&mut self, buckets: usize) {
self.buckets.reserve(buckets);
for _bucket in 0..buckets {
self.buckets.push_back(0);
}
}
fn pad_digits_high(&mut self, digits: usize) {
for _ in 0..digits {
self.push_high(0);
}
}
fn pad_digits_low(&mut self, digits: usize) {
for _ in 0..digits {
self.push_low(0);
}
self.power -= isize::try_from(digits).expect("Overflowed isize while adding low-order digits.");
}
fn power_idx(&self, power: isize) -> Result<usize, PowerIndexError> {
if self.digits == 0 {
if power == 0 {
return Err(PowerIndexError::InsufficientDigitsHigh(1));
} else if power > 0 {
return Err(PowerIndexError::InsufficientDigitsHigh(power as usize));
} else {
return Err(PowerIndexError::InsufficientDigitsLow(-power as usize));
}
}
let highest_digit = self.power + isize::try_from(self.digits - 1).expect("Couldn't convert digit count to isize");
if power > highest_digit {
return Err(PowerIndexError::InsufficientDigitsHigh((power - highest_digit) as usize));
} else if power < self.power {
return Err(PowerIndexError::InsufficientDigitsLow((self.power - power) as usize));
}
Ok((power - self.power) as usize)
}
fn arithmetic_setup(&mut self, power: isize) -> usize {
match self.power_idx(power) {
Ok(idx) => idx,
Err(PowerIndexError::InsufficientDigitsLow(digits_needed)) => {
self.pad_digits_low(digits_needed);
0
},
Err(PowerIndexError::InsufficientDigitsHigh(digits_needed)) => {
let idx = (self.digits - 1) + digits_needed;
self.pad_digits_high(digits_needed);
idx
}
}
}
pub fn add_digit(&mut self, digit: Digit, power: isize) {
let mut idx = self.arithmetic_setup(power);
let (bucket_idx, digit_idx) = self.base.indexes(idx);
let (new_digit, mut carry) = self.base.add_digits(digit, self.get_digit(bucket_idx, digit_idx));
self.set_digit(bucket_idx, digit_idx, new_digit);
idx += 1;
while idx < self.digits && carry != 0 {
let (bucket_idx, digit_idx) = self.base.indexes(idx);
let (new_digit, new_carry) = self.base.add_digits(carry, self.get_digit(bucket_idx, digit_idx));
carry = new_carry;
self.set_digit(bucket_idx, digit_idx, new_digit);
idx += 1;
}
if carry != 0 {
self.push_high(carry);
}
}
pub fn negate(&mut self) {
self.sign = match self.sign {
Sign::Positive => Sign::Negative,
Sign::Negative => Sign::Positive
}
}
pub fn iter(&self) -> BorrowedNumberIter {
BorrowedNumberIter::new(self)
}
}
impl Shl<usize> for Number<'_> {
type Output = Self;
fn shl(mut self, rhs: usize) -> Self::Output {
self.power += isize::try_from(rhs).expect("Failed to convert into isize during left shift.");
self
}
}
impl Shr<usize> for Number<'_> {
type Output = Self;
fn shr(mut self, rhs: usize) -> Self::Output {
self.power -= isize::try_from(rhs).expect("Failed to convert into isize during right shift.");
self
}
}
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
pub enum Sign {
Positive,
Negative
}
enum PowerIndexError {
InsufficientDigitsHigh(usize),
InsufficientDigitsLow(usize)
}
fn bitwise_parameters(base: u32) -> (usize, usize, usize) {
let base = base as usize;
let highest_digit = base - 1;
let usize_bits = 0usize.leading_zeros();
let digits_width = usize_bits - highest_digit.leading_zeros();
let digits_per_bucket = usize_bits / digits_width;
let mask = !(usize::MAX << digits_width as usize);
(digits_width as usize, digits_per_bucket as usize, mask)
}
#[cfg(test)]
pub mod test {
use super::*;
#[test]
fn push_high_puts_digit_on_left() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(5);
n.push_high(1);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(1, 5));
}
#[test]
fn push_low_puts_digit_on_right() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_low(1);
n.push_low(5);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(1, 5));
}
#[test]
fn pop_high_takes_digits_from_right() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(5);
n.push_high(1);
assert_eq!(n.pop_high(), Some(1));
assert_eq!(n.pop_high(), Some(5));
assert_eq!(n.pop_high(), None);
}
#[test]
fn pop_low_takes_digits_from_left() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_low(1);
n.push_low(5);
assert_eq!(n.pop_low(), Some(5));
assert_eq!(n.pop_low(), Some(1));
assert_eq!(n.pop_low(), None);
}
#[test]
fn push_high_and_pop_high_are_inverse() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(5);
n.push_high(1);
assert_eq!(n.pop_high(), Some(1));
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(5));
}
#[test]
fn push_low_and_pop_low_are_inverse() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_low(5);
n.push_low(1);
assert_eq!(n.pop_low(), Some(1));
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(5));
}
#[test]
fn pushing_increases_digits() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(5);
assert_eq!(n.digits, 1);
n.push_low(1);
assert_eq!(n.digits, 2);
}
#[test]
fn popping_reduces_digits() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(5);
n.push_low(1);
n.pop_high();
assert_eq!(n.digits, 1);
n.pop_low();
assert_eq!(n.digits, 0);
}
#[test]
fn alternating_pushing_high_and_low() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(1);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(1));
n.push_low(2);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(1, 2));
n.push_high(3);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(3, 1, 2));
n.push_low(4);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(3, 1, 2, 4));
}
#[test]
fn alternating_popping_high_and_low() {
let b = Base::new(10);
let mut n = Number::new(&b);
for i in 1..=9 {
n.push_low(i);
}
assert_eq!(n.pop_high(), Some(1));
assert_eq!(n.pop_low(), Some(9));
assert_eq!(n.pop_high(), Some(2));
assert_eq!(n.pop_low(), Some(8));
assert_eq!(n.pop_high(), Some(3));
assert_eq!(n.pop_low(), Some(7));
assert_eq!(n.pop_high(), Some(4));
assert_eq!(n.pop_low(), Some(6));
assert_eq!(n.pop_high(), Some(5));
assert_eq!(n.pop_high(), None);
assert_eq!(n.pop_low(), None);
}
#[test]
fn pushing_high_past_bucket_boundary() {
let b = Base::new(10);
let mut n = Number::new(&b);
for _ in 0..(b.digits_per_bucket() + 1) {
n.push_high(1);
}
assert_eq!(
n.iter().collect::<Vec<_>>(),
(0..b.digits_per_bucket() + 1).map(|_| 1).collect::<Vec<_>>()
);
}
#[test]
fn pushing_low_past_bucket_boundary() {
let b = Base::new(10);
let mut n = Number::new(&b);
for _ in 0..(b.digits_per_bucket() + 1) {
n.push_low(1);
}
assert_eq!(
n.iter().collect::<Vec<_>>(),
(0..b.digits_per_bucket() + 1).map(|_| 1).collect::<Vec<_>>()
);
}
#[test]
fn popping_high_past_bucket_boundary() {
let b = Base::new(10);
let mut n = Number::new(&b);
for _ in 0..(b.digits_per_bucket() + 1) {
n.push_high(1);
}
for _ in 0..(b.digits_per_bucket() + 1) {
assert_eq!(n.pop_high(), Some(1));
}
assert_eq!(n.pop_high(), None);
}
#[test]
fn popping_low_past_bucket_boundary() {
let b = Base::new(10);
let mut n = Number::new(&b);
for _ in 0..(b.digits_per_bucket() + 1) {
n.push_high(1);
}
for _ in 0..(b.digits_per_bucket() + 1) {
assert_eq!(n.pop_low(), Some(1));
}
assert_eq!(n.pop_low(), None);
}
#[test]
fn get_returns_correct_digit() {
let b = Base::new(10);
let mut n = Number::new(&b);
for i in 1..=9 {
n.push_high(i);
}
for i in 0..8 {
assert_eq!(n.get(i), Some((i+1) as Digit));
}
}
#[test]
fn set_alters_correct_digit() {
let b = Base::new(10);
let mut n = Number::new(&b);
for i in 0..9 {
n.push_high(i);
}
for i in (0..9).into_iter().rev() {
n.set(i, (i+1) as Digit);
}
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(9, 8, 7, 6, 5, 4, 3, 2, 1));
}
#[test]
fn set_can_alter_1_digit_past_last_digit() {
let b = Base::new(10);
let mut n = Number::new(&b);
for i in 0..9 {
n.push_high(i);
}
n.set(9, 9);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(9, 8, 7, 6, 5, 4, 3, 2, 1, 0));
}
#[test]
fn single_digit_addition() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(1);
n.add_digit(1, 0);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(2));
}
#[test]
fn single_digit_addition_with_carry() {
let b = Base::new(10);
let mut n = Number::new(&b);
for _ in 0..3 {
n.push_high(9);
}
n.add_digit(1, 0);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(1,0,0,0));
}
#[test]
fn single_digit_addition_with_carry_across_bucket_boundary() {
let b = Base::new(10);
let mut n = Number::new(&b);
for _ in 0..b.digits_per_bucket() {
n.push_high(9);
}
n.add_digit(1, 0);
let mut expected = Vec::new();
expected.push(1);
for _ in 0..b.digits_per_bucket() {
expected.push(0);
}
assert_eq!(n.iter().collect::<Vec<_>>(), expected);
}
#[test]
fn single_digit_addition_with_carry_that_does_not_travel_all_the_way() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(8);
n.push_high(9);
n.push_high(9);
n.push_high(1);
n.add_digit(2, 0);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(2, 0, 0, 0));
}
#[test]
fn single_digit_addition_with_new_digit_high() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(1);
n.add_digit(2, 1);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(2, 1));
}
#[test]
fn single_digit_addition_with_new_digit_low() {
let b = Base::new(10);
let mut n = Number::new(&b);
n.push_high(1);
n.add_digit(2, -1);
assert_eq!(n.iter().collect::<Vec<_>>(), vec!(1, 2));
}
#[test]
fn shift_left_increases_power() {
let b = Base::new(10);
let mut n = Number::new(&b);
n = n << 1;
assert_eq!(n.power(), 1);
}
#[test]
fn shift_right_decreases_power() {
let b = Base::new(10);
let mut n = Number::new(&b);
n = n >> 1;
assert_eq!(n.power(), -1);
}
}