1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
use crate::natural::InnerNatural::{Large, Small};
use crate::natural::Natural;
use crate::platform::Limb;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::conversion::traits::{ExactFrom, WrappingFrom};
use malachite_base::num::logic::traits::{BitScan, TrailingZeros};
use malachite_base::slices::slice_leading_zeros;
// Interpreting a slice of `Limb`s as the limbs (in ascending order) of a `Natural`, finds the
// lowest index greater than or equal to `start` at which the `Natural` has a `false` bit.
//
// # Worst-case complexity
// $T(n) = O(n)$
//
// $M(n) = O(1)$
//
// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
//
// This is equivalent to `mpn_scan0` from `mpn/generic/scan0.c`, GMP 6.2.1.
pub_crate_test! {limbs_index_of_next_false_bit(xs: &[Limb], start: u64) -> u64 {
let starting_index = usize::exact_from(start >> Limb::LOG_WIDTH);
if starting_index >= xs.len() {
return start;
}
if let Some(result) = xs[starting_index].index_of_next_false_bit(start & Limb::WIDTH_MASK) {
if result != Limb::WIDTH {
return (u64::wrapping_from(starting_index) << Limb::LOG_WIDTH) + result;
}
}
if starting_index == xs.len() - 1 {
return u64::wrapping_from(xs.len()) << Limb::LOG_WIDTH;
}
let false_index = starting_index
+ 1
+ xs[starting_index + 1..]
.iter()
.take_while(|&&y| y == Limb::MAX)
.count();
let mut result_offset = u64::exact_from(false_index) << Limb::LOG_WIDTH;
if false_index != xs.len() {
result_offset += TrailingZeros::trailing_zeros(!xs[false_index]);
}
result_offset
}}
// Interpreting a slice of `Limb`s as the limbs (in ascending order) of a `Natural`, finds the
// lowest index greater than or equal to `start` at which the `Natural` has a `true` bit. If the
// starting index is too large and there are no more `true` bits above it, `None` is returned.
//
// # Worst-case complexity
// $T(n) = O(n)$
//
// $M(n) = O(1)$
//
// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
//
// This is equivalent to `mpn_scan1` from `mpn/generic/scan1.c`, GMP 6.2.1.
pub_crate_test! {limbs_index_of_next_true_bit(xs: &[Limb], start: u64) -> Option<u64> {
let starting_index = usize::exact_from(start >> Limb::LOG_WIDTH);
if starting_index >= xs.len() {
None
} else if let Some(result) = xs[starting_index].index_of_next_true_bit(start & Limb::WIDTH_MASK)
{
Some((u64::wrapping_from(starting_index) << Limb::LOG_WIDTH) + result)
} else if starting_index == xs.len() - 1 {
None
} else {
let true_index = starting_index + 1 + slice_leading_zeros(&xs[starting_index + 1..]);
if true_index == xs.len() {
None
} else {
let result_offset = u64::wrapping_from(true_index) << Limb::LOG_WIDTH;
Some(
result_offset
.checked_add(TrailingZeros::trailing_zeros(xs[true_index]))
.unwrap(),
)
}
}
}}
impl<'a> BitScan for &'a Natural {
/// Given a [`Natural`] and a starting index, searches the [`Natural`] for the smallest index
/// of a `false` bit that is greater than or equal to the starting index.
///
/// Since every [`Natural`] has an implicit prefix of infinitely-many zeros, this function
/// always returns a value.
///
/// Starting beyond the [`Natural`]'s width is allowed; the result is the starting index.
///
/// # Worst-case complexity
/// $T(n) = O(n)$
///
/// $M(n) = O(1)$
///
/// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
///
/// # Examples
/// ```
/// extern crate malachite_base;
///
/// use malachite_base::num::logic::traits::BitScan;
/// use malachite_nz::natural::Natural;
///
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(0), Some(0));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(20), Some(20));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(31), Some(31));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(32), Some(34));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(33), Some(34));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(34), Some(34));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(35), Some(36));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_false_bit(100), Some(100));
/// ```
fn index_of_next_false_bit(self, start: u64) -> Option<u64> {
match *self {
Natural(Small(small)) => small.index_of_next_false_bit(start),
Natural(Large(ref limbs)) => Some(limbs_index_of_next_false_bit(limbs, start)),
}
}
/// Given a [`Natural`] and a starting index, searches the [`Natural`] for the smallest index
/// of a `true` bit that is greater than or equal to the starting index.
///
/// If the starting index is greater than or equal to the [`Natural`]'s width, the result is
/// `None` since there are no `true` bits past that point.
///
/// # Worst-case complexity
/// $T(n) = O(n)$
///
/// $M(n) = O(1)$
///
/// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
///
/// # Examples
/// ```
/// extern crate malachite_base;
///
/// use malachite_base::num::logic::traits::BitScan;
/// use malachite_nz::natural::Natural;
///
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(0), Some(32));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(20), Some(32));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(31), Some(32));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(32), Some(32));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(33), Some(33));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(34), Some(35));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(35), Some(35));
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(36), None);
/// assert_eq!(Natural::from(0xb00000000u64).index_of_next_true_bit(100), None);
/// ```
fn index_of_next_true_bit(self, start: u64) -> Option<u64> {
match *self {
Natural(Small(small)) => small.index_of_next_true_bit(start),
Natural(Large(ref limbs)) => limbs_index_of_next_true_bit(limbs, start),
}
}
}