use std::iter::FusedIterator;
use std::ops::{Add, AddAssign, Sub, SubAssign};
use super::IndexSet;
use crate::ArithIndexSetTryFromError;
#[derive(Debug, Clone, Default, PartialEq, Eq, PartialOrd, Ord)]
pub struct ArithIndexSet(pub IndexSet);
impl From<IndexSet> for ArithIndexSet {
#[inline]
fn from(set: IndexSet) -> Self {
ArithIndexSet(set)
}
}
impl From<ArithIndexSet> for IndexSet {
#[inline]
fn from(set: ArithIndexSet) -> Self {
set.0
}
}
impl From<u8> for ArithIndexSet {
#[inline]
fn from(value: u8) -> Self {
ArithIndexSet(IndexSet::Small(value as u32))
}
}
impl From<u16> for ArithIndexSet {
#[inline]
fn from(value: u16) -> Self {
ArithIndexSet(IndexSet::Small(value as u32))
}
}
impl From<u32> for ArithIndexSet {
#[inline]
fn from(value: u32) -> Self {
ArithIndexSet(IndexSet::Small(value))
}
}
impl From<u64> for ArithIndexSet {
#[inline]
fn from(value: u64) -> Self {
ArithIndexSet(IndexSet::Medium(value))
}
}
impl From<u128> for ArithIndexSet {
#[inline]
fn from(value: u128) -> Self {
ArithIndexSet(IndexSet::Large(value))
}
}
impl From<usize> for ArithIndexSet {
#[inline]
#[cfg(target_pointer_width = "32")]
fn from(value: usize) -> Self {
ArithIndexSet(IndexSet::Small(value as u32))
}
#[inline]
#[cfg(target_pointer_width = "64")]
fn from(value: usize) -> Self {
ArithIndexSet(IndexSet::Medium(value as u64))
}
}
impl ArithIndexSet {
#[inline]
pub fn to_u128(&self) -> Option<u128> {
match &self.0 {
IndexSet::Small(v) => Some(*v as u128),
IndexSet::Medium(v) => Some(*v as u128),
IndexSet::Large(v) => Some(*v),
IndexSet::Heap(v) => {
let required = v.iter().rposition(|&chunk| chunk != 0).map_or(0, |i| i + 1);
match required {
0 => Some(0),
1 => Some(v[0] as u128),
2 => Some(v[0] as u128 | (v[1] as u128) << 64),
_ => None,
}
}
}
}
}
macro_rules! impl_try_from_arith {
($($ty:ty),+ $(,)?) => {
$(
impl TryFrom<ArithIndexSet> for $ty {
type Error = ArithIndexSetTryFromError;
#[inline]
fn try_from(value: ArithIndexSet) -> Result<Self, Self::Error> {
let v = value.to_u128().ok_or(ArithIndexSetTryFromError::Overflow)?;
<$ty>::try_from(v).map_err(|_| ArithIndexSetTryFromError::Overflow)
}
}
)+
};
}
macro_rules! impl_try_from_int_to_arith {
($($ty:ty),+ $(,)?) => {
$(
impl TryFrom<$ty> for ArithIndexSet {
type Error = ArithIndexSetTryFromError;
#[inline]
fn try_from(value: $ty) -> Result<Self, Self::Error> {
if value < 0 {
Err(ArithIndexSetTryFromError::Negative)
} else {
Ok(ArithIndexSet::from(value.unsigned_abs()))
}
}
}
)+
};
}
impl_try_from_arith!(
u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize
);
impl_try_from_int_to_arith!(i8, i16, i32, i64, i128, isize);
impl std::ops::Deref for ArithIndexSet {
type Target = IndexSet;
#[inline]
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl std::ops::DerefMut for ArithIndexSet {
#[inline]
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
impl Add for ArithIndexSet {
type Output = Self;
#[inline]
fn add(self, rhs: Self) -> Self {
self.overflowing_add(rhs).0
}
}
impl AddAssign for ArithIndexSet {
#[inline]
fn add_assign(&mut self, rhs: Self) {
*self = std::mem::take(self) + rhs;
}
}
impl ArithIndexSet {
#[must_use]
pub fn overflowing_add(self, rhs: Self) -> (Self, bool) {
let (a, b) = (self.0, rhs.0);
let (inner, overflow) =
match (a, b) {
(IndexSet::Small(a), IndexSet::Small(b)) => add_small(a, b),
(IndexSet::Small(b), IndexSet::Medium(a))
| (IndexSet::Medium(a), IndexSet::Small(b)) => add_medium(a, b as u64),
(IndexSet::Medium(a), IndexSet::Medium(b)) => add_medium(a, b),
(IndexSet::Small(b), IndexSet::Large(a))
| (IndexSet::Large(a), IndexSet::Small(b)) => add_large(a, b as u128),
(IndexSet::Medium(b), IndexSet::Large(a))
| (IndexSet::Large(a), IndexSet::Medium(b)) => add_large(a, b as u128),
(IndexSet::Large(a), IndexSet::Large(b)) => add_large(a, b),
(IndexSet::Small(b), IndexSet::Heap(a))
| (IndexSet::Heap(a), IndexSet::Small(b)) => add_heap(a, b as u64),
(IndexSet::Medium(b), IndexSet::Heap(a))
| (IndexSet::Heap(a), IndexSet::Medium(b)) => add_heap(a, b),
(a, b) => {
let a: Vec<u64> = a.into();
let b: Vec<u64> = b.into();
let max_len = a.len().max(b.len());
let mut result = Vec::with_capacity(max_len + 1);
let mut carry: bool = false;
for i in 0..max_len {
let av = a.get(i).copied().unwrap_or(0);
let bv = b.get(i).copied().unwrap_or(0);
let (sum, ov1) = av.overflowing_add(bv);
let (sum2, ov2) = sum.overflowing_add(u64::from(carry));
result.push(sum2);
carry = ov1 || ov2;
}
if carry {
result.push(1);
}
(IndexSet::Heap(result), carry)
}
};
(ArithIndexSet(inner), overflow)
}
#[inline]
#[must_use]
pub fn checked_add(self, rhs: Self) -> Option<Self> {
let (result, overflow) = self.overflowing_add(rhs);
if overflow {
None
} else {
Some(ArithIndexSet(result.0.minimized()))
}
}
}
#[inline]
fn add_small(a: u32, b: u32) -> (IndexSet, bool) {
let (wrapped, overflow) = a.overflowing_add(b);
if overflow {
(IndexSet::Medium((1u64 << 32) | (wrapped as u64)), true)
} else {
(IndexSet::Small(wrapped), false)
}
}
#[inline]
fn add_medium(a: u64, b: u64) -> (IndexSet, bool) {
let (wrapped, overflow) = a.overflowing_add(b);
if overflow {
(IndexSet::Large((1u128 << 64) | (wrapped as u128)), true)
} else {
(IndexSet::Medium(wrapped), false)
}
}
#[inline]
fn add_large(a: u128, b: u128) -> (IndexSet, bool) {
let (wrapped, overflow) = a.overflowing_add(b);
if overflow {
(
IndexSet::Heap(vec![wrapped as u64, (wrapped >> 64) as u64, 1]),
true,
)
} else {
(IndexSet::Large(wrapped), false)
}
}
#[inline]
fn add_heap(mut a: Vec<u64>, b: u64) -> (IndexSet, bool) {
let mut carry = b;
for item in a.iter_mut() {
let (sum, ov) = item.overflowing_add(carry);
*item = sum;
carry = u64::from(ov);
if carry == 0 {
break;
}
}
let overflow = carry > 0;
if overflow {
a.push(carry);
}
(IndexSet::Heap(a), overflow)
}
impl Sub for ArithIndexSet {
type Output = Self;
#[inline]
fn sub(self, rhs: Self) -> Self {
let (result, underflow) = self.overflowing_sub(rhs);
assert!(!underflow, "attempt to subtract with overflow");
result
}
}
impl SubAssign for ArithIndexSet {
#[inline]
fn sub_assign(&mut self, rhs: Self) {
*self = std::mem::take(self) - rhs;
}
}
impl ArithIndexSet {
#[must_use]
pub fn overflowing_sub(self, rhs: Self) -> (Self, bool) {
let (a, b) = (self.0, rhs.0);
if a < b {
return (ArithIndexSet(IndexSet::Small(0)), true);
}
let inner = match (a, b) {
(IndexSet::Small(a), IndexSet::Small(b)) => IndexSet::Small(a - b),
(IndexSet::Small(a), IndexSet::Medium(b)) => IndexSet::Medium(a as u64 - b),
(IndexSet::Medium(a), IndexSet::Small(b)) => IndexSet::Medium(a - b as u64),
(IndexSet::Medium(a), IndexSet::Medium(b)) => IndexSet::Medium(a - b),
(IndexSet::Small(a), IndexSet::Large(b)) => IndexSet::Large(a as u128 - b),
(IndexSet::Large(a), IndexSet::Small(b)) => IndexSet::Large(a - b as u128),
(IndexSet::Medium(a), IndexSet::Large(b)) => IndexSet::Large(a as u128 - b),
(IndexSet::Large(a), IndexSet::Medium(b)) => IndexSet::Large(a - b as u128),
(IndexSet::Large(a), IndexSet::Large(b)) => IndexSet::Large(a - b),
(IndexSet::Small(a), IndexSet::Heap(b)) => {
IndexSet::Small(a - b.first().copied().unwrap_or(0) as u32)
}
(IndexSet::Heap(a), IndexSet::Small(b)) => sub_heap(a, b as u64),
(IndexSet::Medium(a), IndexSet::Heap(b)) => {
IndexSet::Medium(a - b.first().copied().unwrap_or(0))
}
(IndexSet::Heap(a), IndexSet::Medium(b)) => sub_heap(a, b),
(a, b) => {
let a: Vec<u64> = a.into();
let b: Vec<u64> = b.into();
let mut result = Vec::with_capacity(a.len());
let mut borrow: bool = false;
for i in 0..a.len() {
let av = a.get(i).copied().unwrap_or(0);
let bv = b.get(i).copied().unwrap_or(0);
let (diff, ov1) = av.overflowing_sub(bv);
let (diff2, ov2) = diff.overflowing_sub(u64::from(borrow));
result.push(diff2);
borrow = ov1 || ov2;
}
debug_assert!(
!borrow,
"subtraction underflow should have been caught earlier"
);
IndexSet::Heap(result)
}
}
.minimized();
(ArithIndexSet(inner), false)
}
#[inline]
#[must_use]
pub fn checked_sub(self, rhs: Self) -> Option<Self> {
let (result, underflow) = self.overflowing_sub(rhs);
if underflow { None } else { Some(result) }
}
}
#[inline]
fn sub_heap(a: Vec<u64>, b: u64) -> IndexSet {
let mut result = a;
let mut borrow = b;
for item in result.iter_mut() {
let (diff, ov) = item.overflowing_sub(borrow);
*item = diff;
borrow = u64::from(ov);
if borrow == 0 {
break;
}
}
debug_assert_eq!(
borrow, 0,
"subtraction underflow should have been caught earlier"
);
IndexSet::Heap(result)
}
#[derive(Debug, Clone)]
pub struct ArithRangeIter {
start: ArithIndexSet,
end: ArithIndexSet,
}
#[derive(Debug, Clone)]
pub struct ArithRangeFrom {
current: ArithIndexSet,
}
impl ArithIndexSet {
#[inline]
pub fn range(self, end: ArithIndexSet) -> ArithRangeIter {
ArithRangeIter { start: self, end }
}
#[inline]
pub fn range_from(self) -> ArithRangeFrom {
ArithRangeFrom { current: self }
}
#[inline]
pub fn range_to(self) -> ArithRangeIter {
ArithRangeIter {
start: ArithIndexSet::default(),
end: self,
}
}
}
impl Iterator for ArithRangeIter {
type Item = ArithIndexSet;
#[inline]
fn next(&mut self) -> Option<ArithIndexSet> {
if self.start < self.end {
let current = self.start.clone();
self.start += ArithIndexSet::from(1u32);
Some(current)
} else {
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let diff =
if let (Some(end_val), Some(start_val)) = (self.end.to_u128(), self.start.to_u128()) {
end_val.saturating_sub(start_val).into()
} else {
self.end
.clone()
.checked_sub(self.start.clone())
.unwrap_or_default()
};
match usize::try_from(diff) {
Ok(len) => (len, Some(len)),
Err(_) => (usize::MAX, None),
}
}
}
impl DoubleEndedIterator for ArithRangeIter {
#[inline]
fn next_back(&mut self) -> Option<ArithIndexSet> {
if self.start < self.end {
self.end -= ArithIndexSet::from(1u32);
Some(self.end.clone())
} else {
None
}
}
}
impl FusedIterator for ArithRangeIter {}
impl Iterator for ArithRangeFrom {
type Item = ArithIndexSet;
#[inline]
fn next(&mut self) -> Option<ArithIndexSet> {
let current = self.current.clone();
self.current += ArithIndexSet::from(1u32);
Some(current)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(usize::MAX, None)
}
}
impl FusedIterator for ArithRangeFrom {}