bit_iter/

lib.rs

//! Iterate over the bits set in a word.
//!
//! A `BitIter` may be constructed from any integral value.
//!
//! A `BitIter` may be constructed from any integral value, and returns the positions of the `1`
//! bits in ascending order.
//!
//! `BitIter` implements `DoubleEndedIterator`, so you can iterate over the positions of the set
//! bits in descending order too.
//!
//! ## Example
//!
//! ```rust
//! # use bit_iter::*;
//! let x : u32 = 0x10001;
//!
//! for b in BitIter::from(x) {
//!     println!("Bit {} is set.", b);
//! }
//!
//! println!("In reverse order:");
//!
//! for b in BitIter::from(x).rev() {
//!     println!("Bit {} is set.", b);
//! }
//! ```
//!
//! Output:
//!
//! ```text
//! Bit 0 is set.
//! Bit 16 is set.
//! In reverse order:
//! Bit 16 is set.
//! Bit 0 is set.
//! ```

#![no_std]
#![doc(html_root_url = "https://docs.rs/bit-iter/1.3.0")]

use core::iter::{ExactSizeIterator, FusedIterator};

#[cfg(test)]
mod tests;

/// An iterator which returns the positions of the set bits in a word, in ascending order.
///
/// ## Examples
///
/// Construct a `BitIter` from an integer:
///
/// ```rust
/// # use bit_iter::*;
/// let mut iter = BitIter::from(0b10000001);
/// assert_eq!(iter.next(), Some(0usize));
/// assert_eq!(iter.next(), Some(7usize));
/// assert_eq!(iter.next(), None);
/// ```
///
/// Iterate over the bits in an integer in ascending order:
///
/// ```rust
/// # use bit_iter::*;
/// let v : Vec<usize> = BitIter::from(0b10000001).collect();
/// assert_eq!(v, vec![0, 7]);
/// ```
///
/// `BitIter` implements `DoubleEndedIterator`, so you can also get the set bit positions in
/// descending order:
///
/// ```rust
/// # use bit_iter::*;
/// let v : Vec<usize> = BitIter::from(0b10000001).rev().collect();
/// assert_eq!(v, vec![7, 0]);
/// ```
#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
pub struct BitIter<T>(T);

macro_rules! iter_impl {
    ($($t:ty)*) => {$(
        #[doc(hidden)]
        impl BitIter<$t> {
            #[inline]
            fn rightmost_one_pos(&self) -> usize {
                self.0.trailing_zeros() as usize
            }

            #[inline]
            fn leftmost_one_pos(&self) -> usize {
                (<$t>::BITS - 1 - self.0.leading_zeros()) as usize
            }

            #[inline]
            fn count_ones(&self) -> usize {
                self.0.count_ones() as usize
            }

            #[inline]
            fn clear_rightmost_one(&mut self) {
                self.0 &= self.0.wrapping_sub(1);
            }
        }

        /// `From` implementation for `BitIter`.
        impl From<$t> for BitIter<$t> {
            /// Construct a BitIter value.
            #[inline]
            fn from(value: $t) -> Self {
                Self(value)
            }
        }

        /// `Iterator` implementation for `BitIter`.
        impl Iterator for BitIter<$t> {
            type Item = usize;

            #[inline]
            fn next(&mut self) -> Option<Self::Item> {
                if self.0 != 0 {
                    let trailing = self.rightmost_one_pos();
                    self.clear_rightmost_one();
                    Some(trailing)
                } else {
                    None
                }
            }

            // TODO: next_chunk() - currently nightly only (1.72.0)

            #[inline]
            fn size_hint(&self) -> (usize, Option<usize>) {
                let sz = self.count_ones();
                (sz, Some(sz))
            }

            #[inline]
            fn count(self) -> usize {
                self.count_ones()
            }

            #[inline]
            fn last(self) -> Option<Self::Item> {
                if self.0 != 0 {
                    Some(self.leftmost_one_pos())
                } else {
                    None
                }
            }

            // TODO: advance_by() - currently nightly only (1.72.0)

            #[inline]
            fn nth(&mut self, n: usize) -> Option<Self::Item> {
                let mut i = 0;
                while self.0 != 0 && i < n {
                    self.clear_rightmost_one();
                    i += 1;
                }
                self.next()
            }

            // TODO: step_by()
            // TODO: chain()
            // TODO: zip()

            // TODO: intersperse() - currently nightly only (1.72.0)
            // TODO: intersperse_with() - currently nightly only (1.72.0)

            // TODO: map()
            // TODO: for_each()
            // TODO: filter()
            // TODO: filter_map()
            // TODO: enumerate()
            // TODO: peekable()
            // TODO: skip_while()
            // TODO: take_while()
            // TODO: map_while()
            // TODO: skip()
            // TODO: scan()
            // TODO: flat_map()
            // TODO: flatten()
            // TODO: fuse()
            // TODO: inspect()
            // TODO: by_ref()
            // TODO: collect()
            // TODO: try_collect() - currently nightly only (1.72.0)
            // TODO: collect_into() - currently nightly only (1.72.0)
            // TODO: partition()
            // TODO: partition_in_place() - currently nightly only (1.72.0)
            // TODO: is_partitioned() - currently nightly only (1.72.0)
            // TODO: try_fold()
            // TODO: try_for_each()

            #[inline]
            fn fold<B, F>(mut self, init: B, mut f: F) -> B
            where
                F: FnMut(B, Self::Item) -> B
            {
                let mut accum = init;
                while self.0 != 0 {
                    accum = f(accum, self.rightmost_one_pos());
                    self.clear_rightmost_one();
                }
                accum
            }

            // TODO: reduce() - good candidate?
            // TODO: try_reduce() - currently nightly only (1.72.0)
            // TODO: all() - good candidate?
            // TODO: any() - good candidate?
            // TODO: find() - good candidate?
            // TODO: find_map()
            // TODO: try_find() - currently nightly only (1.72.0)
            // TODO: position() - good candidate?
            // TODO: rposition() - good candidate?

            #[inline]
            fn max(self) -> Option<Self::Item> {
                self.last()
            }

            #[inline]
            fn min(self) -> Option<Self::Item> {
                if self.0 != 0 {
                    Some(self.rightmost_one_pos())
                } else {
                    None
                }
            }

            // TODO: max_by_key()
            // TODO: max_by()
            // TODO: min_by_key()
            // TODO: min_by()
            // TODO: rev()
            // TODO: unzip() - not applicable
            // TODO: copied()
            // TODO: cloned()
            // TODO: cycle()
            // TODO: array_chunks() - currently nightly only (1.72.0)

            // TODO: sum() - interesting candidate
            // TODO: product() - interesting candidate

            // TODO: cmp()
            // TODO: cmp_by() - currently nightly only (1.72.0)
            // TODO: partial_cmp()
            // TODO: partial_cmp_by() - currently nightly only (1.72.0)
            // TODO: eq()
            // TODO: eq_by() - currently nightly only (1.72.0)
            // TODO: ne()
            // TODO: lt()
            // TODO: le()
            // TODO: gt()
            // TODO: ge()

            fn is_sorted(self) -> bool {
                true
            }

            // TODO: is_sorted_by() - currently nightly only (1.72.0)
            // TODO: is_sorted_by_key() - currently nightly only (1.72.0)
        }

        /// `FusedIterator` implementation for `BitIter`.
        impl FusedIterator for BitIter<$t> {}

        /// `DoubleEndedIterator` implementation for `BitIter`.
        impl DoubleEndedIterator for BitIter<$t> {
            #[inline]
            fn next_back(&mut self) -> Option<Self::Item> {
                if self.0 != 0 {
                    let highest = self.leftmost_one_pos();
                    self.0 ^= 1 as $t << highest;
                    Some(highest)
                } else {
                    None
                }
            }

            // TODO: advance_back_by() - currently nightly only (1.72.0)
            // TODO: nth_back()
            // TODO: try_rfold()
            // TODO: rfold()
            // TODO: rfind()
        }

        /// `ExactSizeIterator` implementation for `BitIter`.
        impl ExactSizeIterator for BitIter<$t> {
            #[inline]
            fn len(&self) -> usize {
                self.count_ones()
            }

            // TODO: is_empty() - currently nightly only (1.72.0)
        }
    )*}
}

iter_impl! { u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize }