Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add DoubleEndedIterator to Ones for reverse iteration #98

Merged
merged 11 commits into from
Feb 26, 2024
Merged

Add DoubleEndedIterator to Ones for reverse iteration #98

Changes from 1 commit
Commits
Show all changes
11 commits
Select commit Hold shift click to select a range
ce02fff
first step
tikhu Oct 17, 2023
98df931
first working test
tikhu Oct 17, 2023
91f4d13
alternating test added
tikhu Oct 17, 2023
88df2e7
try branching
Oct 17, 2023
e573488
op change
Oct 17, 2023
66c90a8
add different test
Oct 17, 2023
23014b8
separate
tikhu Oct 18, 2023
89566da
performance via inlining
tikhu Oct 18, 2023
2853cec
add size_hint test
tikhu Oct 18, 2023
ffefedf
add new version for rev
tikhu Oct 18, 2023
37eaf05
fix bench
tikhu Oct 18, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
first working test
  • Loading branch information
@tikhu
tikhu committed Oct 17, 2023
commit 98df931506363e671dd0abce8578dd55e34a0147
44 changes: 38 additions & 6 deletions src/lib.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -416,7 416,7 @@ impl FixedBitSet {
bitset_front: first_block,
bitset_back: last_block,
block_idx_front: 0,
block_idx_back: self.length,
block_idx_back: (1 rem.len()) * BITS,
remaining_blocks: rem.iter(),
}
}
Expand Down Expand Up @@ -780,7 780,32 @@ pub struct Ones<'a> {

impl<'a> DoubleEndedIterator for Ones<'a> {
fn next_back(&mut self) -> Option<Self::Item> {
todo!()
let mut active_block: &mut Block = &mut self.bitset_back;
while *active_block == 0 {
match self.remaining_blocks.next_back() {
None => {
if self.bitset_front != 0 {
self.bitset_back = 0;
self.block_idx_back = self.block_idx_front;
active_block = &mut self.bitset_front;
} else {
return None;
}
}
Some(next_block) => {
*active_block = *next_block;
self.block_idx_back -= BITS;
}
};
}
/* Identify the first non zero bit */
let bit_idx = active_block.leading_zeros();

/* set that bit to zero */
let mask = !((1 as Block) << (BITS as u32 - bit_idx - 1));
active_block.bitand_assign(mask);

Some(self.block_idx_back BITS - bit_idx as usize - 1)
}
}

Expand All @@ -794,20 819,22 @@ impl<'a> Iterator for Ones<'a> {
match self.remaining_blocks.next() {
None => {
if self.bitset_back != 0 {
self.bitset_front = 0;
self.block_idx_front = self.block_idx_back;
active_block = &mut self.bitset_back;
} else {
return None;
}
}
Some(next_block) => {
*active_block = *next_block;
self.block_idx_front = BITS;
}
};
self.block_idx_front = BITS;
}
let t = *active_block & (0 as Block).wrapping_sub(*active_block);
let r = active_block.trailing_zeros() as usize;
self.bitset_front ^= t;
*active_block ^= t;
Some(self.block_idx_front r)
}

Expand Down Expand Up @@ -1175,8 1202,13 @@ mod tests {
fb.set(99, true);

let ones: Vec<_> = fb.ones().collect();
let ones_rev: Vec<_> = fb.ones().rev().collect();

let mut known_result = vec![7, 11, 12, 35, 40, 50, 77, 95, 99];

assert_eq!(vec![7, 11, 12, 35, 40, 50, 77, 95, 99], ones);
assert_eq!(known_result, ones);
known_result.reverse();
assert_eq!(known_result, ones_rev);
}

#[test]
Expand Down Expand Up @@ -1659,7 1691,7 @@ mod tests {
let b = b_ones.iter().cloned().collect::<FixedBitSet>();
a |= b;
let res = a.ones().collect::<Vec<usize>>();
assert!(res == a_or_b);
assert_eq!(res, a_or_b);
}

#[test]
Expand Down