#![deny(missing_docs,trivial_casts,trivial_numeric_casts,
missing_debug_implementations, missing_copy_implementations,
unsafe_code,unused_import_braces,unused_qualifications)
]
#![cfg_attr(feature="clippy", feature(plugin))]
#![cfg_attr(feature="clippy", plugin(clippy))]
extern crate base_custom;
#[doc(no_inline)]
pub use base_custom::BaseCustom;
use std::fmt;
use std::ops::{
Add,AddAssign,Mul,MulAssign,BitXor,BitXorAssign
};
use std::cmp::{PartialOrd,Ordering};
extern crate array_tool;
mod internal;
use internal::step_map::StepMap;
use internal::carry_add::{CappedAdd,SignNum,Sign};
#[derive(Clone)]
pub struct Digits {
mapping: BaseCustom<char>,
digit: u64,
left: Option<Box<Digits>>,
}
impl Digits {
pub fn add(&self, other: Self) -> Self {
assert!(self.base() == other.base());
let mut result: Vec<u64> = vec![];
let mut carry: u64 = 0;
let mut c_self: Option<Box<Digits>> = Some(Box::new(self.clone()));
let mut o_self: Option<Box<Digits>> = Some(Box::new(other));
let mut remainder: Option<SignNum<u64>>;
loop {
if carry == 0 && c_self == None && o_self == None { break }
let cs = c_self.clone();
let os = o_self.clone();
result.push(
{
let cr = carry.capped_add({
cs.unwrap_or_else(|| Box::new(self.zero())).digit +
os.unwrap_or_else(|| Box::new(self.zero())).digit},
(0, self.base() as u64)
);
remainder = cr.carry;
cr.sign_num.num
}
);
let guard = remainder.unwrap_or_else(|| SignNum::new(0));
match guard.sign {
Sign::Plus => {
carry = guard.num;
},
Sign::Minus => unimplemented!()
}
c_self = c_self.unwrap_or_else(|| Box::new(self.zero())).left;
o_self = o_self.unwrap_or_else(|| Box::new(self.zero())).left;
}
result.reverse();
self.new_mapped(&result).unwrap()
}
pub fn as_mapping_vec(&self) -> Vec<u64> {
match self.left {
Some(ref l) => {
let mut result = l.as_mapping_vec();
result.extend(vec![self.digit]);
result
},
None => vec![self.digit],
}
}
pub fn base(&self) -> usize {
self.mapping.base as usize
}
pub fn gen<T>(&self, other: T) -> Self
where Self: From<(BaseCustom<char>, T)> {
Digits::from((self.mapping.clone(), other))
}
fn head_tail(self) -> (u64, Option<Box<Self>>) {
match self.left {
Some(bx) => (self.digit, Some(bx)),
None => (self.digit, None),
}
}
pub fn is_valid_adjacent(&self, adjacent: usize) -> bool {
let mut ptr = self;
let mut last_num = self.digit;
let mut last_num_count = 0;
while let Some(ref item) = ptr.left {
if item.digit == last_num {
last_num_count += 1;
} else {
last_num_count = 0;
}
if last_num_count > adjacent { return false; }
last_num = item.digit;
ptr = item;
}
true
}
pub fn is_compat(&self, other: &Self) -> bool {
self.mapping == other.mapping
}
fn is_end(&self) -> bool {
self.digit == 0 && match self.left { None => true, _ => false }
}
pub fn is_one(&self) -> bool {
if self.digit != 1 { return false }
match self.left {
None => { true },
Some(ref bx) => { bx.is_zero() },
}
}
pub fn is_zero(&self) -> bool {
if self.digit != 0 { return false }
match self.left {
None => { true },
Some(ref bx) => { bx.is_zero() },
}
}
pub fn length(&self) -> usize {
match self.left {
None => 1,
Some(ref l) => { l.length() + 1 }
}
}
pub fn max_adjacent(&self) -> usize {
self.max_adj(self.digit, 0, 1) - 1
}
fn max_adj(&self, last_num: u64, last_num_count: usize, max_count: usize) -> usize {
let mut lnc = last_num_count;
if self.digit == last_num { lnc += 1; } else { lnc = 1; }
let max_count = std::cmp::max(lnc, max_count);
match self.left {
None => max_count,
Some(ref l) => { l.max_adj(self.digit, lnc, max_count) },
}
}
pub fn mul(&self, other: Self) -> Self {
self.multiply(other, 0)
}
fn multiply(&self, other: Digits, power_of_ten: usize) -> Self {
assert!(self.base() == other.base());
let mut position: usize = power_of_ten;
let mut o = Some(Box::new(other));
let mut result = self.zero();
while let Some(thing) = o.clone() {
let (dgt, tail) = thing.head_tail();
o = tail;
let mltply = self.propagate((self.digit * dgt).to_string()).pow_ten(position);
let current_digit = self.propagate(self.mapping.gen(dgt).to_string());
if let Some(ref bx) = self.left {
result.mut_add_internal(bx.clone().multiply(current_digit, position + 1), true);
};
result.mut_add_internal( mltply, true );
position += 1;
}
result
}
pub fn mut_add(&mut self, other: Self) -> Self {
self.mut_add_internal(other, false)
}
fn mut_add_internal(&mut self, other: Digits, trim: bool) -> Self {
assert!(self.base() == other.base());
if other.is_end() { return self.clone(); };
let (last, rest) = other.head_tail();
let added = self.propagate(self.mapping.gen(last + self.digit));
let (l, r) = added.head_tail();
self.digit = l;
let mut intermediate = Digits::new_zero(self.mapping.clone());
if let Some(dg) = r { intermediate.mut_add_internal(dg.replicate(), trim); }
if let Some(dg) = rest { intermediate.mut_add_internal(dg.replicate(), trim); }
match self.left.clone() {
Some(bx) => {
self.set_left( bx.replicate().mut_add_internal(intermediate, trim).clone(), trim );
},
None => {
if !intermediate.is_zero() {
self.set_left( intermediate, trim );
}
}
};
self.clone()
}
pub fn mut_mul(&mut self, other: Self) -> Self {
let (d, r) = self.multiply(other, 0).head_tail();
self.digit = d;
if let Some(rest) = r { self.set_left(rest.replicate(), true); }
self.clone()
}
pub fn new<S>(mapping: BaseCustom<char>, number: S) -> Digits
where S: Into<String> {
let number = number.into();
if number.is_empty() { return Digits { mapping: mapping, digit: 0, left: None }; };
let (last, rest) = {
let mut n = number.chars().rev();
(n.next().unwrap(), n.rev().collect::<String>())
};
let continuation = {
if rest.is_empty() {
None
} else {
Some(Box::new(Digits::new(mapping.clone(), rest)))
}
};
Digits {
mapping: mapping.clone(),
digit: mapping.decimal(last.to_string()),
left: continuation,
}
}
pub fn new_mapped(&self, places: &[u64]) -> Result<Self, &'static str> {
if places.iter().any(|&x| x >= self.mapping.base) {
return Err("Character mapping out of range!");
}
let num = places.iter().fold("".to_string(), |mut acc, &x| {
acc.push(*self.mapping.nth(x as usize).unwrap());
acc
}
);
Ok(Digits::new(self.mapping.clone(), num))
}
pub fn new_one(mapping: BaseCustom<char>) -> Self {
Digits { mapping: mapping, digit: 1, left: None }
}
pub fn new_zero(mapping: BaseCustom<char>) -> Self {
Digits { mapping: mapping, digit: 0, left: None }
}
pub fn next_non_adjacent(&mut self, adjacent: usize) -> Self {
self.prep_non_adjacent(adjacent);
self.step_non_adjacent(adjacent)
}
pub fn one(&self) -> Self {
Digits::new_one(self.mapping.clone())
}
pub fn pinky(&self) -> char {
self.mapping.char(self.digit as usize).unwrap()
}
pub fn pow(&mut self, mut pwr: Self) -> Self {
if pwr.is_zero() { return self.one(); }
let copy = self.clone();
loop {
if pwr.is_one() {
break
} else {
self.mut_mul(copy.clone());
}
pwr.pred_till_zero();
}
self.clone()
}
fn pow_ten(&self, positions: usize) -> Self {
let mut result: Digits = self.clone();
for _ in 0..positions {
let original = result;
result = Digits::new_zero(self.mapping.clone());
result.set_left(original, true);
}
result
}
pub fn pred_till_zero(&mut self) -> Self {
if self.is_zero() { return self.clone(); }
if self.digit == 0 {
self.digit = self.mapping.base - 1;
match self.left.clone() {
Some(ref mut bx) => self.set_left(bx.pred_till_zero(), false),
None => self.left = None
}
} else {
self.digit -= 1;
}
self.clone()
}
pub fn prep_non_adjacent(&mut self, adjacent: usize) -> Self {
assert!(self.mapping.base > 3, "\n\n WARNING!\n\n \"You may not use non-adjacent stepping with numeric bases of less than 4!\"\n\n");
if self.is_valid_adjacent(adjacent) {
return self.clone();
}
let mut v = self.as_mapping_vec();
'outer: loop {
let mut last_num: Option<u64> = None;
let mut last_num_count = 0;
let w = v.clone();
let itr = w.iter().enumerate();
for (i, item) in itr {
if last_num == None {
last_num = Some(*item);
continue;
}
if let Some(val) = last_num {
if item == &val {
last_num_count += 1;
} else {
last_num_count = 0;
}
if last_num_count > adjacent {
let i = i + 1;
let mut d = self.new_mapped(&v[0..i].to_vec()).ok().unwrap();
d.succ();
let mut new_v = d.as_mapping_vec();
for _ in v[i..v.len()].iter() {
new_v.push(0)
}
v = new_v;
continue 'outer;
}
}
last_num = Some(*item);
}
break;
}
let result = self.new_mapped(&v).ok().unwrap().pred_till_zero();
self.digit = result.digit;
self.left = result.left.clone();
result
}
pub fn propagate<S>(&self, number: S) -> Self
where S: Into<String> {
Digits::new(self.mapping.clone(), number)
}
pub fn rcount(&self, character_index: u8) -> usize {
if let Some(ref d) = self.left {
if self.digit == u64::from(character_index) {
return d.rcount(character_index) + 1;
}
} else if self.digit == u64::from(character_index) {
return 1;
}
0
}
pub fn replicate(self) -> Self { self.clone() }
fn set_left(&mut self, d: Digits, trim: bool) {
if trim && d.is_end() {
self.left = None;
} else {
self.left = Some(Box::new(d));
}
}
pub fn step_non_adjacent(&mut self, adjacent: usize) -> Self {
let mut step_map = StepMap::new(self.zero(), adjacent as u8);
let mut v: Self;
loop {
let mut builder = self.clone();
v = builder.mut_add(step_map.next().unwrap());
if v.is_valid_adjacent(adjacent) {
break;
}
}
self.digit = v.digit;
self.left = v.left;
self.clone()
}
pub fn succ(&mut self) -> Self {
let one = self.one();
self.mut_add_internal(one, false)
}
pub fn to_s(&self) -> String {
let num = self.mapping.gen(self.digit);
match self.left {
None => num.to_owned(),
Some(ref bx) => format!("{}{}", bx.to_s(), num),
}
}
pub fn to_string(&self) -> String {
self.to_s()
}
pub fn zero(&self) -> Self {
Digits::new_zero(self.mapping.clone())
}
pub fn zero_fill(&mut self, length: usize) {
if self.length() >= length { return; }
if length == 0 { return; }
match self.left.clone() {
None => {
let mut l = self.zero();
l.zero_fill(length - 1);
self.left = Some(Box::new(l));
}
Some(v) => {
self.set_left(
{
let mut l = v.replicate();
l.zero_fill(length -1 );
l
},
false
)
}
}
}
pub fn zero_trim(&mut self) {
let mut lnum: String = "".to_string();
if let Some(ref v) = self.left {
lnum = v.to_s();
}
lnum = lnum.trim_left_matches(*self.mapping.zero()).to_string();
let lval = self.propagate(lnum);
self.set_left(lval, true);
}
}
pub trait Reverse {
fn reverse(&mut self);
}
impl Reverse for Digits {
fn reverse(&mut self) {
let mut curr_node: Option<Digits> = Some(self.clone());
let mut prev_node: Option<Digits> = None;
while curr_node != None {
let cn = curr_node.unwrap();
let next_node = if let Some(n) = cn.clone().left {
Some(n.replicate())
} else { None };
let mut c = cn;
if let Some(prev) = prev_node {
c.set_left(prev, false);
} else {
c.left = None;
}
prev_node = Some(c);
curr_node = next_node;
}
let p = prev_node.unwrap();
self.digit = p.digit;
self.left = p.left;
}
}
#[allow(missing_docs)]
pub trait Into<String> {
fn into(self) -> String;
}
impl From<(BaseCustom<char>, u64)> for Digits {
fn from(d: (BaseCustom<char>, u64)) -> Digits {
let mapping = d.0;
let value = d.1;
Digits::new(mapping.clone(), mapping.gen(value))
}
}
impl From<(BaseCustom<char>, Digits)> for Digits {
fn from(d: (BaseCustom<char>, Digits)) -> Digits {
let mapping = d.0;
let source = d.1;
let from_base = source.mapping.base;
let mut result = Digits::new_zero(mapping.clone());
let mut pointer: Option<Box<Digits>> = Some(Box::new(source.clone()));
let mut position = 0;
if from_base >= mapping.base {
while let Some(bx) = pointer {
let (h, t) = bx.head_tail();
if h != 0 { result.mut_add_internal(
Digits::new(mapping.clone(), mapping.gen(h)).mul(
Digits::new(mapping.clone(), mapping.gen(from_base)).
pow(source.gen(position))
),
true
);
}
position += 1;
pointer = t;
}
} else { while let Some(bx) = pointer {
let (h, t) = bx.head_tail();
if h != 0 { result.mut_add_internal(
Digits::new(mapping.clone(), mapping.gen(h * from_base.pow(position as u32))),
true
);
}
position += 1;
pointer = t;
}
}
result
}
}
impl From<(Digits, Digits)> for Digits {
fn from(d: (Digits, Digits)) -> Digits {
if d.0.base() == d.1.base() { return d.1; }
Digits::from((d.0.mapping, d.1))
}
}
impl From<Digits> for String {
fn from(d: Digits) -> String {
d.to_s()
}
}
impl Into<String> for Digits {
fn into(self) -> String {
self.to_s()
}
}
impl Into<String> for String {
fn into(self) -> String {
self.clone()
}
}
impl fmt::Display for Digits {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "Digits — (Character: '{}', Decimal Value: {}{})",
self.mapping.gen(self.digit), self.digit, {
match self.left {
None => "".to_string(),
Some(ref l) => format!(", With Preceeding: '{}'", l.to_s()),
}
}
)
}
}
impl fmt::Debug for Digits {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{} with base: {:?}", self, self.mapping)
}
}
impl PartialEq for Digits {
fn eq(&self, other: &Digits) -> bool {
self.mapping == other.mapping &&
self.digit == other.digit &&
self.left == other.left
}
}
impl Add for Digits {
type Output = Self;
fn add(self, other: Self) -> Self {
self.clone().mut_add(other)
}
}
impl AddAssign for Digits {
fn add_assign(&mut self, other: Self) {
self.mut_add(other);
}
}
impl Mul for Digits {
type Output = Self;
fn mul(self, other: Self) -> Self {
self.multiply(other, 0)
}
}
impl MulAssign for Digits {
fn mul_assign(&mut self, other: Self) {
self.mut_mul(other);
}
}
impl BitXor for Digits {
type Output = Self;
fn bitxor(self, other: Self) -> Self {
self.clone().pow(other)
}
}
impl BitXorAssign for Digits {
fn bitxor_assign(&mut self, other: Self) {
self.pow(other);
}
}
impl PartialOrd for Digits {
fn partial_cmp(&self, other: &Digits) -> Option<Ordering> {
assert!(self.mapping == other.mapping);
let mut result: Option<Ordering>;
let mut a: Self = self.clone();
let mut b: Self = other.clone();
result = a.digit.partial_cmp(&b.digit);
while let (Some(x),Some(y)) = (a.left.clone(), b.left.clone()) {
a = x.replicate();
b = y.replicate();
match a.digit.partial_cmp(&b.digit) {
Some(Ordering::Equal) | None => (),
Some(change) => { result = Some(change); },
}
}
if a.left.is_some() && !b.left.is_some() && !a.left.clone().unwrap().is_zero() {
result = Some(Ordering::Greater);
}
if !a.left.is_some() && b.left.is_some() && !b.left.unwrap().is_zero() {
result = Some(Ordering::Less);
}
result
}
}
#[allow(missing_docs)]
pub mod prelude {
#[doc(inline)]
pub use super::Digits;
#[doc(inline)]
pub use base_custom::BaseCustom;
}
impl Default for Digits {
fn default() -> Digits {
let base10 = BaseCustom::<char>::new("0123456789".chars().collect());
Digits::new_zero(base10)
}
}
pub mod radices {
use super::*;
pub fn binary_base() -> BaseCustom<char> {
BaseCustom::<char>::new("01".chars().collect())
}
pub fn octal_base() -> BaseCustom<char> {
BaseCustom::<char>::new("01234567".chars().collect())
}
pub fn decimal_base() -> BaseCustom<char> {
BaseCustom::<char>::new("0123456789".chars().collect())
}
pub fn hex_base() -> BaseCustom<char> {
BaseCustom::<char>::new("0123456789ABCDEF".chars().collect())
}
pub fn hexl_base() -> BaseCustom<char> {
BaseCustom::<char>::new("0123456789abcdef".chars().collect())
}
}
pub trait Radix {
fn binary(&self) -> Self;
fn octal(&self) -> Self;
fn decimal(&self) -> Self;
fn hex(&self) -> Self;
fn hexl(&self) -> Self;
}
impl Radix for Digits {
fn binary(&self) -> Digits {
Digits::from((radices::binary_base(), self.clone()))
}
fn octal(&self) -> Digits {
Digits::from((radices::octal_base(), self.clone()))
}
fn decimal(&self) -> Digits {
Digits::from((radices::decimal_base(), self.clone()))
}
fn hex(&self) -> Digits {
Digits::from((radices::hex_base(), self.clone()))
}
fn hexl(&self) -> Digits {
Digits::from((radices::hexl_base(), self.clone()))
}
}