use std::{
hash::{Hash, Hasher},
iter::{ExactSizeIterator, FusedIterator},
ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, Shl, ShlAssign, Shr, ShrAssign},
};
pub mod arith;
pub use arith::{ArithIndexSet, ArithRangeFrom, ArithRangeIter};
#[derive(Debug, Clone, Eq)]
pub enum IndexSet {
Small(u32),
Medium(u64),
Large(u128),
Heap(Vec<u64>),
}
impl Default for IndexSet {
#[inline]
fn default() -> Self {
IndexSet::Small(0)
}
}
impl IndexSet {
#[inline]
pub fn singleton(slot: usize) -> Self {
if slot < 32 {
IndexSet::Small(1u32 << slot)
} else if slot < 64 {
IndexSet::Medium(1u64 << slot)
} else if slot < 128 {
IndexSet::Large(1u128 << slot)
} else {
let chunks = (slot / 64) + 1;
let mut vec = vec![0u64; chunks];
vec[slot / 64] |= 1u64 << (slot % 64);
IndexSet::Heap(vec)
}
}
pub fn insert(&mut self, slot: usize, value: bool) {
match self {
IndexSet::Small(bits) => {
if slot < 32 {
if value {
*bits |= 1u32 << slot;
} else {
*bits &= !(1u32 << slot);
}
} else if value {
if slot < 64 {
*self = IndexSet::Medium((*bits as u64) | (1u64 << slot));
} else if slot < 128 {
*self = IndexSet::Large((*bits as u128) | (1u128 << slot));
} else {
let chunks = (slot / 64) + 1;
let mut vec = vec![0u64; chunks];
vec[0] = *bits as u64;
vec[slot / 64] |= 1u64 << (slot % 64);
*self = IndexSet::Heap(vec);
}
}
}
IndexSet::Medium(bits) => {
if slot < 64 {
if value {
*bits |= 1u64 << slot;
} else {
*bits &= !(1u64 << slot);
}
} else if value {
if slot < 128 {
*self = IndexSet::Large((*bits as u128) | (1u128 << slot));
} else {
let chunks = (slot / 64) + 1;
let mut vec = vec![0u64; chunks];
vec[0] = *bits;
vec[slot / 64] |= 1u64 << (slot % 64);
*self = IndexSet::Heap(vec);
}
}
}
IndexSet::Large(bits) => {
if slot < 128 {
if value {
*bits |= 1u128 << slot;
} else {
*bits &= !(1u128 << slot);
}
} else if value {
let chunks = (slot / 64) + 1;
let mut vec = vec![0u64; chunks];
vec[0] = *bits as u64;
vec[1] = (*bits >> 64) as u64;
vec[slot / 64] |= 1u64 << (slot % 64);
*self = IndexSet::Heap(vec);
}
}
IndexSet::Heap(vec) => {
let idx = slot / 64;
let bit = slot % 64;
if value {
if idx >= vec.len() {
vec.resize(idx + 1, 0);
}
vec[idx] |= 1u64 << bit;
} else {
if idx < vec.len() {
vec[idx] &= !(1u64 << bit);
}
}
}
}
}
pub fn is_disjoint(&self, other: &Self) -> bool {
match (self, other) {
(IndexSet::Small(a), IndexSet::Small(b)) => (a & b) == 0,
(IndexSet::Small(a), IndexSet::Medium(b)) => ((*a as u64) & b) == 0,
(IndexSet::Medium(a), IndexSet::Small(b)) => (a & (*b as u64)) == 0,
(IndexSet::Small(a), IndexSet::Large(b)) => ((*a as u128) & b) == 0,
(IndexSet::Large(a), IndexSet::Small(b)) => (a & (*b as u128)) == 0,
(IndexSet::Medium(a), IndexSet::Medium(b)) => (a & b) == 0,
(IndexSet::Medium(a), IndexSet::Large(b)) => ((*a as u128) & b) == 0,
(IndexSet::Large(a), IndexSet::Medium(b)) => (a & (*b as u128)) == 0,
(IndexSet::Large(a), IndexSet::Large(b)) => (a & b) == 0,
(IndexSet::Heap(a), IndexSet::Heap(b)) => {
let min_len = a.len().min(b.len());
for i in 0..min_len {
if (a[i] & b[i]) != 0 {
return false;
}
}
true
}
(IndexSet::Small(a), IndexSet::Heap(b)) => {
b.first().is_none_or(|&x| ((*a as u64) & x) == 0)
}
(IndexSet::Heap(a), IndexSet::Small(b)) => {
a.first().is_none_or(|&x| (x & (*b as u64)) == 0)
}
(IndexSet::Medium(a), IndexSet::Heap(b)) => b.first().is_none_or(|&x| (a & x) == 0),
(IndexSet::Heap(a), IndexSet::Medium(b)) => a.first().is_none_or(|&x| (x & b) == 0),
(IndexSet::Large(a), IndexSet::Heap(b)) => {
if b.is_empty() {
return true;
}
if (b[0] & (*a as u64)) != 0 {
return false;
}
if b.len() > 1 && (b[1] & ((*a >> 64) as u64)) != 0 {
return false;
}
true
}
(IndexSet::Heap(a), IndexSet::Large(b)) => {
if a.is_empty() {
return true;
}
if (a[0] & (*b as u64)) != 0 {
return false;
}
if a.len() > 1 && (a[1] & ((*b >> 64) as u64)) != 0 {
return false;
}
true
}
}
}
#[inline]
pub fn contains(&self, slot: usize) -> bool {
match self {
IndexSet::Small(bits) => slot < 32 && (*bits & (1u32 << slot)) != 0,
IndexSet::Medium(bits) => slot < 64 && (*bits & (1u64 << slot)) != 0,
IndexSet::Large(bits) => slot < 128 && (*bits & (1u128 << slot)) != 0,
IndexSet::Heap(vec) => {
let idx = slot / 64;
let bit = slot % 64;
idx < vec.len() && (vec[idx] & (1u64 << bit)) != 0
}
}
}
#[inline]
pub fn iter<'a>(&'a self) -> IndexSetIter<'a> {
let max = self.max_chunks().saturating_sub(1);
IndexSetIter {
inner: self,
front_chunk: 0,
front_bits: self.get_first_chunk(),
back_chunk: max,
back_bits: if max == 0 {
self.get_first_chunk()
} else {
match self {
IndexSet::Large(b) => (*b >> 64) as u64,
IndexSet::Heap(v) => v.last().copied().unwrap_or(0),
_ => unreachable!("Small/Medium have only one chunk"),
}
},
remaining: self.count_ones(),
}
}
#[inline]
fn get_first_chunk(&self) -> u64 {
match self {
IndexSet::Small(b) => *b as u64,
IndexSet::Medium(b) => *b,
IndexSet::Large(b) => *b as u64,
IndexSet::Heap(v) => v.first().copied().unwrap_or(0),
}
}
#[inline]
fn max_chunks(&self) -> usize {
match self {
IndexSet::Small(_) | IndexSet::Medium(_) => 1,
IndexSet::Large(_) => 2,
IndexSet::Heap(vec) => vec.len(),
}
}
#[inline]
pub fn count_ones(&self) -> usize {
match self {
IndexSet::Small(bits) => bits.count_ones() as usize,
IndexSet::Medium(bits) => bits.count_ones() as usize,
IndexSet::Large(bits) => bits.count_ones() as usize,
IndexSet::Heap(vec) => vec.iter().map(|&x| x.count_ones() as usize).sum(),
}
}
#[inline]
pub fn is_empty(&self) -> bool {
match self {
IndexSet::Small(bits) => *bits == 0,
IndexSet::Medium(bits) => *bits == 0,
IndexSet::Large(bits) => *bits == 0,
IndexSet::Heap(vec) => vec.iter().all(|&x| x == 0),
}
}
#[inline]
pub fn minimized(mut self) -> Self {
self.minimize();
self
}
pub fn minimize(&mut self) {
*self = match std::mem::take(self) {
IndexSet::Heap(mut vec) => {
let last = vec.iter().rposition(|&x| x != 0);
match last {
None => IndexSet::Small(0),
Some(0) => {
let v = vec[0];
if v as u32 as u64 == v {
IndexSet::Small(v as u32)
} else {
IndexSet::Medium(v)
}
}
Some(1) => IndexSet::Large((vec[0] as u128) | ((vec[1] as u128) << 64)),
_ => {
vec.truncate(last.unwrap() + 1);
IndexSet::Heap(vec)
}
}
}
IndexSet::Large(0) => IndexSet::Small(0),
IndexSet::Large(v) if (v as u64 as u128) == v => {
let low = v as u64;
if low as u32 as u64 == low {
IndexSet::Small(low as u32)
} else {
IndexSet::Medium(low)
}
}
IndexSet::Medium(0) => IndexSet::Small(0),
IndexSet::Medium(v) if (v as u32 as u64) == v => IndexSet::Small(v as u32),
other => other,
};
}
}
impl From<IndexSet> for Vec<u64> {
fn from(set: IndexSet) -> Self {
match set {
IndexSet::Small(bits) => vec![bits as u64],
IndexSet::Medium(bits) => vec![bits],
IndexSet::Large(bits) => vec![bits as u64, (bits >> 64) as u64],
IndexSet::Heap(vec) => vec,
}
}
}
impl PartialEq for IndexSet {
fn eq(&self, other: &Self) -> bool {
match (self, other) {
(IndexSet::Small(a), IndexSet::Small(b)) => a == b,
(IndexSet::Medium(a), IndexSet::Medium(b)) => a == b,
(IndexSet::Large(a), IndexSet::Large(b)) => a == b,
_ => self.iter().eq(other.iter()),
}
}
}
impl PartialOrd for IndexSet {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for IndexSet {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
match (self, other) {
(IndexSet::Small(a), IndexSet::Small(b)) => a.cmp(b),
(IndexSet::Medium(a), IndexSet::Medium(b)) => a.cmp(b),
(IndexSet::Large(a), IndexSet::Large(b)) => a.cmp(b),
_ => self.iter().rev().cmp(other.iter().rev()),
}
}
}
impl Hash for IndexSet {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
self.count_ones().hash(state);
for idx in self.iter() {
idx.hash(state);
}
}
}
impl BitOr for IndexSet {
type Output = Self;
fn bitor(self, rhs: Self) -> Self {
match (self, rhs) {
(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::Small(a), IndexSet::Large(b)) => IndexSet::Large((a as u128) | b),
(IndexSet::Large(a), IndexSet::Small(b)) => IndexSet::Large(a | (b as u128)),
(IndexSet::Small(a), IndexSet::Heap(mut b)) => {
if b.is_empty() {
b.push(a as u64);
} else {
b[0] |= a as u64;
}
IndexSet::Heap(b)
}
(IndexSet::Heap(mut a), IndexSet::Small(b)) => {
if a.is_empty() {
a.push(b as u64);
} else {
a[0] |= b as u64;
}
IndexSet::Heap(a)
}
(IndexSet::Medium(a), IndexSet::Medium(b)) => IndexSet::Medium(a | b),
(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::Medium(a), IndexSet::Heap(mut b)) => {
if b.is_empty() {
b.push(a);
} else {
b[0] |= a;
}
IndexSet::Heap(b)
}
(IndexSet::Heap(mut a), IndexSet::Medium(b)) => {
if a.is_empty() {
a.push(b);
} else {
a[0] |= b;
}
IndexSet::Heap(a)
}
(IndexSet::Large(a), IndexSet::Large(b)) => IndexSet::Large(a | b),
(IndexSet::Large(a), IndexSet::Heap(mut b)) => {
if b.len() < 2 {
b.resize(2, 0);
}
b[0] |= a as u64;
b[1] |= (a >> 64) as u64;
IndexSet::Heap(b)
}
(IndexSet::Heap(mut a), IndexSet::Large(b)) => {
if a.len() < 2 {
a.resize(2, 0);
}
a[0] |= b as u64;
a[1] |= (b >> 64) as u64;
IndexSet::Heap(a)
}
(IndexSet::Heap(mut a), IndexSet::Heap(b)) => {
if a.len() < b.len() {
a.resize(b.len(), 0);
}
for (x, y) in a.iter_mut().zip(b.iter()) {
*x |= *y;
}
IndexSet::Heap(a)
}
}
}
}
impl BitOrAssign for IndexSet {
#[inline]
fn bitor_assign(&mut self, rhs: Self) {
*self = std::mem::take(self) | rhs;
}
}
impl BitAnd for IndexSet {
type Output = Self;
fn bitand(self, rhs: Self) -> Self {
match (self, rhs) {
(IndexSet::Small(a), IndexSet::Small(b)) => IndexSet::Small(a & b),
(IndexSet::Small(a), IndexSet::Medium(b)) => IndexSet::Small((a as u64 & b) as u32),
(IndexSet::Medium(a), IndexSet::Small(b)) => IndexSet::Small((a & (b as u64)) as u32),
(IndexSet::Small(a), IndexSet::Large(b)) => IndexSet::Small((a as u128 & b) as u32),
(IndexSet::Large(a), IndexSet::Small(b)) => IndexSet::Small((a & (b as u128)) as u32),
(IndexSet::Small(a), IndexSet::Heap(b)) => {
if b.is_empty() {
IndexSet::default()
} else {
IndexSet::Small((a as u64 & b[0]) as u32)
}
}
(IndexSet::Heap(a), IndexSet::Small(b)) => {
if a.is_empty() {
IndexSet::default()
} else {
IndexSet::Small((a[0] & (b as u64)) as u32)
}
}
(IndexSet::Medium(a), IndexSet::Medium(b)) => IndexSet::Medium(a & b),
(IndexSet::Medium(a), IndexSet::Large(b)) => IndexSet::Medium((a as u128 & b) as u64),
(IndexSet::Large(a), IndexSet::Medium(b)) => IndexSet::Medium((a & (b as u128)) as u64),
(IndexSet::Medium(a), IndexSet::Heap(b)) => {
if b.is_empty() {
IndexSet::Medium(0)
} else {
IndexSet::Medium(a & b[0])
}
}
(IndexSet::Heap(a), IndexSet::Medium(b)) => {
if a.is_empty() {
IndexSet::Medium(0)
} else {
IndexSet::Medium(a[0] & b)
}
}
(IndexSet::Large(a), IndexSet::Large(b)) => IndexSet::Large(a & b),
(IndexSet::Large(a), IndexSet::Heap(b)) => {
let lo = b.first().map(|&x| a as u64 & x).unwrap_or(0);
let hi = b.get(1).map(|&x| (a >> 64) as u64 & x).unwrap_or(0);
if hi == 0 {
IndexSet::Medium(lo)
} else {
IndexSet::Large((lo as u128) | ((hi as u128) << 64))
}
}
(IndexSet::Heap(a), IndexSet::Large(b)) => {
let lo = a.first().map(|&x| x & (b as u64)).unwrap_or(0);
let hi = a.get(1).map(|&x| x & ((b >> 64) as u64)).unwrap_or(0);
if hi == 0 {
IndexSet::Medium(lo)
} else {
IndexSet::Large((lo as u128) | ((hi as u128) << 64))
}
}
(IndexSet::Heap(mut a), IndexSet::Heap(b)) => {
let min_len = a.len().min(b.len());
a.truncate(min_len);
for (x, y) in a.iter_mut().zip(b.iter()) {
*x &= *y;
}
IndexSet::Heap(a)
}
}
.minimized()
}
}
impl BitAndAssign for IndexSet {
#[inline]
fn bitand_assign(&mut self, rhs: Self) {
*self = std::mem::take(self) & rhs;
}
}
#[inline]
fn heap_shl(vec: Vec<u64>, rhs: usize) -> IndexSet {
let chunk_shift = rhs / 64;
let bit_shift = rhs % 64;
let mut new_vec = Vec::with_capacity(chunk_shift + vec.len() + 1);
new_vec.extend(std::iter::repeat_n(0u64, chunk_shift));
if bit_shift == 0 {
new_vec.extend(vec);
} else {
let mut carry = 0u64;
for v in vec {
let val = (v << bit_shift) | carry;
carry = v >> (64 - bit_shift);
new_vec.push(val);
}
if carry != 0 {
new_vec.push(carry);
}
}
IndexSet::Heap(new_vec)
}
impl Shl<usize> for IndexSet {
type Output = Self;
fn shl(self, rhs: usize) -> Self {
if rhs == 0 || self.is_empty() {
return self;
}
match self {
IndexSet::Small(bits) => {
let val = bits as u128;
if (val.leading_zeros() as usize) < rhs {
heap_shl(vec![bits as u64], rhs)
} else {
let shifted = val << rhs;
if shifted as u32 as u128 == shifted {
IndexSet::Small(shifted as u32)
} else if shifted as u64 as u128 == shifted {
IndexSet::Medium(shifted as u64)
} else {
IndexSet::Large(shifted)
}
}
}
IndexSet::Medium(bits) => {
let val = bits as u128;
if (val.leading_zeros() as usize) < rhs {
heap_shl(vec![bits], rhs)
} else {
let shifted = val << rhs;
if shifted as u64 as u128 == shifted {
IndexSet::Medium(shifted as u64)
} else {
IndexSet::Large(shifted)
}
}
}
IndexSet::Large(bits) => {
if (bits.leading_zeros() as usize) < rhs {
let lo = bits as u64;
let hi = (bits >> 64) as u64;
let vec = if hi != 0 { vec![lo, hi] } else { vec![lo] };
heap_shl(vec, rhs)
} else {
IndexSet::Large(bits << rhs)
}
}
IndexSet::Heap(vec) => heap_shl(vec, rhs),
}
}
}
impl ShlAssign<usize> for IndexSet {
#[inline]
fn shl_assign(&mut self, rhs: usize) {
*self = std::mem::take(self) << rhs;
}
}
impl Shr<usize> for IndexSet {
type Output = Self;
fn shr(self, rhs: usize) -> Self {
if rhs == 0 || self.is_empty() {
return self;
}
match self {
IndexSet::Small(bits) => {
if rhs >= 32 {
IndexSet::Small(0)
} else {
IndexSet::Small(bits >> rhs)
}
}
IndexSet::Medium(bits) => {
if rhs >= 64 {
IndexSet::Small(0)
} else {
IndexSet::Medium(bits >> rhs)
}
}
IndexSet::Large(bits) => {
if rhs >= 128 {
IndexSet::Small(0)
} else {
IndexSet::Large(bits >> rhs)
}
}
IndexSet::Heap(vec) => {
let chunk_shift = rhs / 64;
let bit_shift = rhs % 64;
if chunk_shift >= vec.len() {
return IndexSet::Small(0);
}
let remaining = &vec[chunk_shift..];
if bit_shift == 0 {
IndexSet::Heap(remaining.to_vec())
} else {
let mut new_vec = Vec::with_capacity(remaining.len());
for i in 0..remaining.len() {
let mut val = remaining[i] >> bit_shift;
if i + 1 < remaining.len() {
val |= remaining[i + 1] << (64 - bit_shift);
}
new_vec.push(val);
}
IndexSet::Heap(new_vec)
}
}
}
.minimized()
}
}
impl ShrAssign<usize> for IndexSet {
#[inline]
fn shr_assign(&mut self, rhs: usize) {
*self = std::mem::take(self) >> rhs;
}
}
#[derive(Debug, Clone)]
pub struct IndexSetIter<'a> {
inner: &'a IndexSet,
front_chunk: usize,
front_bits: u64,
back_chunk: usize,
back_bits: u64,
remaining: usize,
}
impl IndexSetIter<'_> {
#[inline]
fn chunk_bits(&self, chunk: usize) -> u64 {
match self.inner {
IndexSet::Small(bits) if chunk == 0 => *bits as u64,
IndexSet::Medium(bits) if chunk == 0 => *bits,
IndexSet::Large(bits) if chunk == 0 => *bits as u64,
IndexSet::Large(bits) if chunk == 1 => (*bits >> 64) as u64,
IndexSet::Heap(vec) => vec.get(chunk).copied().unwrap_or(0),
_ => 0,
}
}
}
impl<'a> Iterator for IndexSetIter<'a> {
type Item = usize;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
loop {
if self.front_bits != 0 {
let tz = self.front_bits.trailing_zeros() as usize;
let mask = 1u64 << tz;
self.front_bits &= !mask;
if self.front_chunk == self.back_chunk {
self.back_bits &= !mask;
}
self.remaining -= 1;
return Some(self.front_chunk * 64 + tz);
}
if self.remaining == 0 {
return None;
}
self.front_chunk += 1;
self.front_bits = self.chunk_bits(self.front_chunk);
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.remaining, Some(self.remaining))
}
}
impl<'a> DoubleEndedIterator for IndexSetIter<'a> {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
loop {
if self.back_bits != 0 {
let lz = self.back_bits.ilog2() as usize;
let mask = 1u64 << lz;
self.back_bits &= !mask;
if self.front_chunk == self.back_chunk {
self.front_bits &= !mask;
}
self.remaining -= 1;
return Some(self.back_chunk * 64 + lz);
}
if self.remaining == 0 {
return None;
}
if self.back_chunk == 0 {
self.remaining = 0;
return None;
}
self.back_chunk -= 1;
self.back_bits = self.chunk_bits(self.back_chunk);
}
}
}
impl<'a> ExactSizeIterator for IndexSetIter<'a> {}
impl<'a> FusedIterator for IndexSetIter<'a> {}