1515// specific language governing permissions and limitations
1616// under the License.
1717
18- use crate :: bit_chunk_iterator:: BitChunks ;
18+ use crate :: bit_chunk_iterator:: { BitChunks , UnalignedBitChunk } ;
1919use crate :: bit_iterator:: { BitIndexIterator , BitIndexU32Iterator , BitIterator , BitSliceIterator } ;
2020use crate :: bit_util:: read_u64;
2121use crate :: {
@@ -611,6 +611,11 @@ impl BooleanBuffer {
611611 self . into_iter ( )
612612 }
613613
614+ /// Returns an [`UnalignedBitChunk`] over this buffer's values.
615+ fn unaligned_bit_chunks ( & self ) -> UnalignedBitChunk < ' _ > {
616+ UnalignedBitChunk :: new ( self . values ( ) , self . offset ( ) , self . len ( ) )
617+ }
618+
614619 /// Returns an iterator over the set bit positions in this [`BooleanBuffer`]
615620 pub fn set_indices ( & self ) -> BitIndexIterator < ' _ > {
616621 BitIndexIterator :: new ( self . values ( ) , self . bit_offset , self . bit_len )
@@ -625,6 +630,61 @@ impl BooleanBuffer {
625630 pub fn set_slices ( & self ) -> BitSliceIterator < ' _ > {
626631 BitSliceIterator :: new ( self . values ( ) , self . bit_offset , self . bit_len )
627632 }
633+
634+ /// Block size for chunked fold operations in [`Self::has_true`] and [`Self::has_false`].
635+ /// Using `chunks_exact` with this size lets the compiler fully unroll the inner
636+ /// fold (no inner branch/loop), enabling short-circuit exits every N chunks.
637+ const CHUNK_FOLD_BLOCK_SIZE : usize = 16 ;
638+
639+ /// Returns whether there is at least one `true` value in this buffer.
640+ ///
641+ /// This is more efficient than `count_set_bits() > 0` because it can short-circuit
642+ /// as soon as a `true` value is found, without counting all set bits.
643+ ///
644+ /// Returns `false` for empty buffer.
645+ pub fn has_true ( & self ) -> bool {
646+ let bit_chunks = self . unaligned_bit_chunks ( ) ;
647+ let chunks = bit_chunks. chunks ( ) ;
648+ let mut exact = chunks. chunks_exact ( Self :: CHUNK_FOLD_BLOCK_SIZE ) ;
649+ let found = bit_chunks. prefix ( ) . unwrap_or ( 0 ) != 0
650+ || exact. any ( |block| block. iter ( ) . fold ( 0u64 , |acc, & c| acc | c) != 0 ) ;
651+ found || exact. remainder ( ) . iter ( ) . any ( |& c| c != 0 ) || bit_chunks. suffix ( ) . unwrap_or ( 0 ) != 0
652+ }
653+
654+ /// Returns whether there is at least one `false` value in this buffer.
655+ ///
656+ /// This is more efficient than `len() > count_set_bits()` because it can short-circuit
657+ /// as soon as a `false` value is found, without counting all set bits.
658+ ///
659+ /// Returns `false` for empty buffer.
660+ pub fn has_false ( & self ) -> bool {
661+ let bit_chunks = self . unaligned_bit_chunks ( ) ;
662+ // UnalignedBitChunk zeros padding bits; fill them with 1s so
663+ // they don't appear as false values.
664+ let lead_mask = !( ( 1u64 << bit_chunks. lead_padding ( ) ) - 1 ) ;
665+ let trail_mask = if bit_chunks. trailing_padding ( ) == 0 {
666+ u64:: MAX
667+ } else {
668+ ( 1u64 << ( 64 - bit_chunks. trailing_padding ( ) ) ) - 1
669+ } ;
670+ let ( prefix_fill, suffix_fill) = match ( bit_chunks. prefix ( ) , bit_chunks. suffix ( ) ) {
671+ ( Some ( _) , Some ( _) ) => ( !lead_mask, !trail_mask) ,
672+ ( Some ( _) , None ) => ( !lead_mask | !trail_mask, 0 ) ,
673+ ( None , Some ( _) ) => ( 0 , !trail_mask) ,
674+ ( None , None ) => ( 0 , 0 ) ,
675+ } ;
676+ let chunks = bit_chunks. chunks ( ) ;
677+ let mut exact = chunks. chunks_exact ( Self :: CHUNK_FOLD_BLOCK_SIZE ) ;
678+ let found = bit_chunks
679+ . prefix ( )
680+ . is_some_and ( |v| ( v | prefix_fill) != u64:: MAX )
681+ || exact. any ( |block| block. iter ( ) . fold ( u64:: MAX , |acc, & c| acc & c) != u64:: MAX ) ;
682+ found
683+ || exact. remainder ( ) . iter ( ) . any ( |& c| c != u64:: MAX )
684+ || bit_chunks
685+ . suffix ( )
686+ . is_some_and ( |v| ( v | suffix_fill) != u64:: MAX )
687+ }
628688}
629689
630690impl Not for & BooleanBuffer {
@@ -1245,4 +1305,107 @@ mod tests {
12451305 let buffer = BooleanBuffer :: new_unset ( 100 ) ;
12461306 assert_eq ! ( buffer. clone( ) . find_nth_set_bit_position( 0 , 1 ) , 100 ) ;
12471307 }
1308+
1309+ #[ test]
1310+ fn test_has_true_has_false_all_true ( ) {
1311+ let arr = BooleanBuffer :: from ( vec ! [ true , true , true ] ) ;
1312+ assert ! ( arr. has_true( ) ) ;
1313+ assert ! ( !arr. has_false( ) ) ;
1314+ }
1315+
1316+ #[ test]
1317+ fn test_has_true_has_false_all_false ( ) {
1318+ let arr = BooleanBuffer :: from ( vec ! [ false , false , false ] ) ;
1319+ assert ! ( !arr. has_true( ) ) ;
1320+ assert ! ( arr. has_false( ) ) ;
1321+ }
1322+
1323+ #[ test]
1324+ fn test_has_true_has_false_mixed ( ) {
1325+ let arr = BooleanBuffer :: from ( vec ! [ true , false , true ] ) ;
1326+ assert ! ( arr. has_true( ) ) ;
1327+ assert ! ( arr. has_false( ) ) ;
1328+ }
1329+
1330+ #[ test]
1331+ fn test_has_true_has_false_empty ( ) {
1332+ let arr = BooleanBuffer :: from ( Vec :: < bool > :: new ( ) ) ;
1333+ assert ! ( !arr. has_true( ) ) ;
1334+ assert ! ( !arr. has_false( ) ) ;
1335+ }
1336+
1337+ #[ test]
1338+ fn test_has_false_aligned_suffix_all_true ( ) {
1339+ let arr = BooleanBuffer :: from ( vec ! [ true ; 129 ] ) ;
1340+ assert ! ( arr. has_true( ) ) ;
1341+ assert ! ( !arr. has_false( ) ) ;
1342+ }
1343+
1344+ #[ test]
1345+ fn test_has_false_non_aligned_all_true ( ) {
1346+ // 65 elements: exercises the remainder path in has_false
1347+ let arr = BooleanBuffer :: from ( vec ! [ true ; 65 ] ) ;
1348+ assert ! ( arr. has_true( ) ) ;
1349+ assert ! ( !arr. has_false( ) ) ;
1350+ }
1351+
1352+ #[ test]
1353+ fn test_has_false_non_aligned_last_false ( ) {
1354+ // 64 trues + 1 false: remainder path should find the false
1355+ let mut values = vec ! [ true ; 64 ] ;
1356+ values. push ( false ) ;
1357+ let arr = BooleanBuffer :: from ( values) ;
1358+ assert ! ( arr. has_true( ) ) ;
1359+ assert ! ( arr. has_false( ) ) ;
1360+ }
1361+
1362+ #[ test]
1363+ fn test_has_false_exact_64_all_true ( ) {
1364+ // Exactly 64 elements, no remainder
1365+ let arr = BooleanBuffer :: from ( vec ! [ true ; 64 ] ) ;
1366+ assert ! ( arr. has_true( ) ) ;
1367+ assert ! ( !arr. has_false( ) ) ;
1368+ }
1369+
1370+ #[ test]
1371+ fn test_has_true_has_false_unaligned_slices ( ) {
1372+ let cases = [
1373+ ( 1 , 129 , true , false ) ,
1374+ ( 3 , 130 , true , false ) ,
1375+ ( 5 , 65 , true , false ) ,
1376+ ( 7 , 64 , true , false ) ,
1377+ ] ;
1378+
1379+ let base = BooleanBuffer :: from ( vec ! [ true ; 300 ] ) ;
1380+
1381+ for ( offset, len, expected_has_true, expected_has_false) in cases {
1382+ let arr = base. slice ( offset, len) ;
1383+ assert_eq ! (
1384+ arr. has_true( ) ,
1385+ expected_has_true,
1386+ "offset={offset} len={len}"
1387+ ) ;
1388+ assert_eq ! (
1389+ arr. has_false( ) ,
1390+ expected_has_false,
1391+ "offset={offset} len={len}"
1392+ ) ;
1393+ }
1394+ }
1395+
1396+ #[ test]
1397+ fn test_has_true_has_false_exact_multiples_of_64 ( ) {
1398+ let cases = [
1399+ ( 64 , true , false ) ,
1400+ ( 128 , true , false ) ,
1401+ ( 192 , true , false ) ,
1402+ ( 256 , true , false ) ,
1403+ ] ;
1404+
1405+ for ( len, expected_has_true, expected_has_false) in cases {
1406+ let arr = BooleanBuffer :: from ( vec ! [ true ; len] ) ;
1407+ assert_eq ! ( arr. has_true( ) , expected_has_true, "len={len}" ) ;
1408+ assert_eq ! ( arr. has_false( ) , expected_has_false, "len={len}" ) ;
1409+ }
1410+ }
12481411}
0 commit comments