From 33b4fef2d8cbf925791c62ee83a41d75c9eaf202 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Fri, 11 Apr 2025 08:51:10 +0100 Subject: [PATCH] Restart without the trait system --- src/finitenimber.rs | 163 ++++++++++++++++++++++++-------------------- src/lib.rs | 16 +---- 2 files changed, 91 insertions(+), 88 deletions(-) diff --git a/src/finitenimber.rs b/src/finitenimber.rs index 610fa3d..51cfc68 100644 --- a/src/finitenimber.rs +++ b/src/finitenimber.rs @@ -1,54 +1,15 @@ -use std::fmt::Debug; -use std::ops::BitXor; +use std::ops::Add; -pub trait FiniteNimberBase: - BitXor + Eq + Debug + Sized -{ - type Cheap<'a>: FiniteNimberBase where Self: 'a; - type Owned: FiniteNimberBase + Clone; +type Word = u64; // element type of the vectors we use +const WORDLEVELS: usize = 6; // 2^{2^6} = 64 = size of Word - fn to_cheap<'a>(&'a self) -> Self::Cheap<'a>; - fn to_owned(self) -> Self::Owned; -} - -impl FiniteNimberBase for u64 { - type Cheap<'a> = Self where Self: 'a; - type Owned = Self; - - fn to_cheap<'a>(&'a self) -> Self::Cheap<'a> { - *self - } - - fn to_owned(self) -> Self::Owned { - self - } -} - -#[derive(Clone, PartialEq, Eq, Debug)] -pub struct IntVector(pub Vec); - -#[derive(PartialEq, Eq, Debug)] -pub struct IntSlice<'a>(pub &'a [u64]); - -impl BitXor for IntVector { - type Output = Self; - - fn bitxor(self, other: Self) -> Self { - Self( - self.0 - .into_iter() - .zip(other.0.into_iter()) - .map(|(a, b)| a ^ b) - .collect(), - ) - } -} +#[derive(Debug, PartialEq, Eq, Clone, Hash)] +pub struct FiniteNimber(Vec); -impl BitXor for IntSlice<'_> { - type Output = IntVector; - - fn bitxor(self, other: Self) -> IntVector { - IntVector( +impl Add<&FiniteNimber> for &FiniteNimber { + type Output = FiniteNimber; + fn add(self, other: &FiniteNimber) -> FiniteNimber { + FiniteNimber( self.0 .iter() .zip(other.0.iter()) @@ -58,47 +19,99 @@ impl BitXor for IntSlice<'_> { } } -impl FiniteNimberBase for IntVector { - type Cheap<'a> = IntSlice<'a> where Self: 'a; - type Owned = IntVector; - - fn to_cheap<'a>(&'a self) -> Self::Cheap<'a> { - IntSlice(&self.0) +impl Add<&FiniteNimber> for FiniteNimber { + type Output = FiniteNimber; + fn add(self, other: &FiniteNimber) -> FiniteNimber { + (&self) + other } +} - fn to_owned(self) -> Self::Owned { - self +impl Add for &FiniteNimber { + type Output = FiniteNimber; + fn add(self, other: FiniteNimber) -> FiniteNimber { + self + (&other) } } -impl<'a> FiniteNimberBase for IntSlice<'a> { - type Cheap<'b> = IntSlice<'b> where Self: 'b; - type Owned = IntVector; - - fn to_cheap<'b>(&'b self) -> Self::Cheap<'b> { - IntSlice(self.0) +impl Add for FiniteNimber { + type Output = FiniteNimber; + fn add(self, other: FiniteNimber) -> FiniteNimber { + (&self) + (&other) } +} - fn to_owned(self) -> Self::Owned { - IntVector(self.0.into()) +impl From for FiniteNimber { + fn from(val: Word) -> FiniteNimber { + FiniteNimber(vec![val]) } } -#[derive(Clone, PartialEq, Eq, Debug)] -pub struct FiniteNimber { - n: T, +#[derive(Clone, Copy, Debug)] +pub enum FiniteNimberRef<'a> { + OneWord(Word), + Slice(&'a [Word]), } +use FiniteNimberRef::*; -impl FiniteNimber { - pub fn new(n: T) -> Self { - Self { n } +impl<'a> FiniteNimberRef<'a> { + fn zero() -> Self { + OneWord(0) } -} -impl std::ops::Add> for FiniteNimber { - type Output = FiniteNimber; + fn low_word(self) -> Word { + match self { + OneWord(v) => v, + Slice(s) => { + *(s.first().expect("FiniteNimberRef::Slice is never empty")) + } + } + } + + fn as_slice<'b, 'c>(&'b self) -> &'c [Word] + where + 'a: 'c, + 'b: 'c, + { + match self { + OneWord(v) => std::slice::from_ref(v), + Slice(s) => s, + } + } - fn add(self, other: Self) -> Self::Output { - Self::Output::new(self.n ^ other.n) + fn split( + self, + level: usize, + ) -> (FiniteNimberRef<'a>, FiniteNimberRef<'a>) { + match level.checked_sub(WORDLEVELS) { + None => { + // If level < WORDLEVELS then we can cast to Word any old way + let bits = 1 << (level as Word); + let mask = bits - 1; + let v = self.low_word(); + return (OneWord(v & mask), OneWord((v >> bits) & mask)); + } + Some(wordlevel) => match self { + OneWord(v) => (OneWord(v), Self::zero()), + Slice(s) => { + match wordlevel + .try_into() + .ok() + .and_then(|w| 1usize.checked_shl(w)) + { + Some(words) => { + let mut iter = s.chunks(words); + let lo = iter.next().expect( + "FiniteNimberRef::Slice is never empty", + ); + match iter.next() { + Some(hi) => (Slice(lo), Slice(hi)), + None => (Slice(lo), Self::zero()), + } + } + None => (self.clone(), Self::zero()), + } + } + }, + } } } diff --git a/src/lib.rs b/src/lib.rs index d40eed0..4f79e4f 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,8 +1,6 @@ mod finitenimber; pub use finitenimber::FiniteNimber; -pub use finitenimber::IntSlice; -pub use finitenimber::IntVector; #[cfg(test)] mod tests { @@ -10,16 +8,8 @@ mod tests { #[test] fn addition() { - let a = FiniteNimber::new(0b1100u64); - let b = FiniteNimber::new(0b1010u64); - assert_eq!(a + b, FiniteNimber::new(0b0110u64)); - - let a = FiniteNimber::new(IntVector(vec![1, 1, 0, 0])); - let b = FiniteNimber::new(IntVector(vec![1, 0, 1, 0])); - assert_eq!(a + b, FiniteNimber::new(IntVector(vec![0, 1, 1, 0]))); - - let a = FiniteNimber::new(IntSlice(&[1, 1, 0, 0])); - let b = FiniteNimber::new(IntSlice(&[1, 0, 1, 0])); - assert_eq!(a + b, FiniteNimber::new(IntVector(vec![0, 1, 1, 0]))); + let a = FiniteNimber::from(0b1100); + let b = FiniteNimber::from(0b1010); + assert_eq!(a + b, FiniteNimber::from(0b0110)); } } -- 2.30.2