sux 0.14.0

/*
 *
 * SPDX-FileCopyrightText: 2024 Michele Andreata
 * SPDX-FileCopyrightText: 2024 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use super::SmallCounters;
use crate::prelude::*;
use crate::traits::{Backend, Word};
use crate::utils::SelectInWord;
use ambassador::Delegate;
use mem_dbg::{MemDbg, MemSize};
use num_primitive::PrimitiveInteger;

use crate::ambassador_impl_Index;
use crate::rank_sel::ambassador_impl_SmallCounters;
use crate::traits::ambassador_impl_Backend;
use crate::traits::bal_paren::ambassador_impl_BalParen;
use crate::traits::bit_vec_ops::ambassador_impl_BitLength;
use crate::traits::rank_sel::ambassador_impl_BitCount;
use crate::traits::rank_sel::ambassador_impl_NumBits;
use crate::traits::rank_sel::ambassador_impl_Rank;
use crate::traits::rank_sel::ambassador_impl_RankHinted;
use crate::traits::rank_sel::ambassador_impl_RankUnchecked;
use crate::traits::rank_sel::ambassador_impl_RankZero;
use crate::traits::rank_sel::ambassador_impl_SelectHinted;
use crate::traits::rank_sel::ambassador_impl_SelectZero;
use crate::traits::rank_sel::ambassador_impl_SelectZeroHinted;
use crate::traits::rank_sel::ambassador_impl_SelectZeroUnchecked;
use std::ops::Deref;
use std::ops::Index;

/// A selection structure over [`RankSmall`] using negligible additional space
/// and providing constant-time selection.
///
/// # Implementation details
///
/// [`SelectSmall`] adds a very sparse first-level inventory to a [`RankSmall`]
/// structure to locate approximately the position of the desired one; the bit
/// is then located using binary searches over [`RankSmall`]'s counters; this
/// technique is called _hinted bsearch_ and is described in “[Broadword
/// Implementation of Rank/Select Queries]”.
///
/// The resulting selection methods are quite slow, and in general it is
/// convenient and faster to use a sparse [`SelectAdapt`], with similar space
/// usage. However, when used in combination with [`RankSmall`], [`SelectSmall`]
/// and [`SelectZeroSmall`] provide effective and almost zero-cost selection
/// structures.
///
/// The implementation uses a further trick from Piotr Beling's [`bsuccinct`]
/// library: the first-level inventory is enriched with midpoint blocks that
/// allow the binary search to start from a better initial position, reducing
/// the number of steps and thus the query time. The midpoint blocks are stored
/// in the high bits of the inventory entries, so they do not require additional
/// space.
///
/// This structure forwards several traits and [`Deref`]'s to its backend.
///
/// # Examples
///
/// ```rust
/// # #[cfg(target_pointer_width = "64")]
/// # {
/// # use sux::{rank_small, bit_vec};
/// # use sux::rank_sel::{SelectSmall, SelectZeroSmall};
/// # use sux::traits::{Rank, Select, SelectZero};
/// let bits = bit_vec![1, 0, 1, 1, 0, 1, 0, 1];
/// let rank_small = rank_small![u64: 1; bits];
/// // Note that at present the compiler cannot infer const parameters
/// let sel = SelectSmall::<1, 9, _>::new(rank_small);
///
/// assert_eq!(sel.select(0), Some(0));
/// assert_eq!(sel.select(1), Some(2));
/// assert_eq!(sel.select(2), Some(3));
/// assert_eq!(sel.select(3), Some(5));
/// assert_eq!(sel.select(4), Some(7));
/// assert_eq!(sel.select(5), None);
///
/// // Rank methods are forwarded
/// assert_eq!(sel.rank(0), 0);
/// assert_eq!(sel.rank(1), 1);
/// assert_eq!(sel.rank(2), 1);
/// assert_eq!(sel.rank(3), 2);
/// assert_eq!(sel.rank(4), 3);
/// assert_eq!(sel.rank(5), 3);
/// assert_eq!(sel.rank(6), 4);
/// assert_eq!(sel.rank(7), 4);
/// assert_eq!(sel.rank(8), 5);
///
/// // Access to the underlying bit vector is forwarded, too
/// assert_eq!(sel[0], true);
/// assert_eq!(sel[1], false);
/// assert_eq!(sel[2], true);
/// assert_eq!(sel[3], true);
/// assert_eq!(sel[4], false);
/// assert_eq!(sel[5], true);
/// assert_eq!(sel[6], false);
/// assert_eq!(sel[7], true);
///
/// // One can also stack a SelectSmall on top of a SelectZeroSmall:
/// let rank_small = sel.into_inner();
/// let sel = SelectSmall::<1, 9, _>::new(SelectZeroSmall::<1, 9, _>::new(rank_small));
///
/// assert_eq!(sel.select(0), Some(0));
/// assert_eq!(sel.select(1), Some(2));
/// assert_eq!(sel.select(2), Some(3));
/// assert_eq!(sel.select(3), Some(5));
/// assert_eq!(sel.select(4), Some(7));
/// assert_eq!(sel.select(5), None);
///
/// assert_eq!(sel.select_zero(0), Some(1));
/// assert_eq!(sel.select_zero(1), Some(4));
/// assert_eq!(sel.select_zero(2), Some(6));
/// assert_eq!(sel.select_zero(3), None);
/// # }
/// ```
///
/// [Broadword Implementation of Rank/Select Queries]: https://link.springer.com/chapter/10.1007/978-3-540-68552-4_12
/// [`bsuccinct`]: https://github.com/beling/bsuccinct-rs/
#[derive(Debug, Clone, MemSize, MemDbg, Delegate)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[delegate(crate::traits::Backend, target = "small_counters")]
#[delegate(Index<usize>, target = "small_counters")]
#[delegate(crate::traits::rank_sel::BitCount, target = "small_counters")]
#[delegate(crate::traits::bit_vec_ops::BitLength, target = "small_counters")]
#[delegate(crate::traits::rank_sel::NumBits, target = "small_counters")]
#[delegate(crate::traits::rank_sel::Rank, target = "small_counters")]
#[delegate(crate::traits::rank_sel::RankHinted, target = "small_counters")]
#[delegate(crate::traits::rank_sel::RankUnchecked, target = "small_counters")]
#[delegate(crate::traits::rank_sel::RankZero, target = "small_counters")]
#[delegate(crate::traits::rank_sel::SelectHinted, target = "small_counters")]
#[delegate(crate::traits::rank_sel::SelectZero, target = "small_counters")]
#[delegate(crate::traits::rank_sel::SelectZeroHinted, target = "small_counters")]
#[delegate(
    crate::traits::rank_sel::SelectZeroUnchecked,
    target = "small_counters"
)]
#[delegate(crate::bal_paren::BalParen, target = "small_counters")]
#[delegate(crate::rank_sel::SmallCounters<NUM_U32S, COUNTER_WIDTH>, target = "small_counters")]
pub struct SelectSmall<
    const NUM_U32S: usize,
    const COUNTER_WIDTH: usize,
    C,
    I = Box<[u32]>,
    O = Box<[usize]>,
> {
    small_counters: C,
    inventory: I,
    inventory_begin: O,
    log2_ones_per_inventory: usize,
}

impl<const NUM_U32S: usize, const COUNTER_WIDTH: usize, C: Backend + AsRef<[C::Word]>, I, O>
    AsRef<[C::Word]> for SelectSmall<NUM_U32S, COUNTER_WIDTH, C, I, O>
{
    #[inline(always)]
    fn as_ref(&self) -> &[C::Word] {
        self.small_counters.as_ref()
    }
}

impl<const NUM_U32S: usize, const COUNTER_WIDTH: usize, C, I, O> Deref
    for SelectSmall<NUM_U32S, COUNTER_WIDTH, C, I, O>
{
    type Target = C;

    #[inline(always)]
    fn deref(&self) -> &Self::Target {
        &self.small_counters
    }
}

impl<const NUM_U32S: usize, const COUNTER_WIDTH: usize, C, I, O>
    SelectSmall<NUM_U32S, COUNTER_WIDTH, C, I, O>
{
    // On 64-bit, superblocks contain 2^32 bits.
    // On 32-bit, a single superblock covers the entire address space.
    #[cfg(target_pointer_width = "64")]
    const SUPERBLOCK_BIT_SIZE: usize = 1 << 32;
    #[cfg(not(target_pointer_width = "64"))]
    const SUPERBLOCK_BIT_SIZE: usize = usize::MAX;
    const BLOCK_BIT_SIZE: usize = 1 << COUNTER_WIDTH;
    const NUM_SUBBLOCKS: usize = match NUM_U32S {
        1 => 4,
        2 | 3 => 8,
        _ => panic!("Unsupported number of u32s"),
    };
    const SUBBLOCK_BIT_SIZE: usize = Self::BLOCK_BIT_SIZE / Self::NUM_SUBBLOCKS;
    /// Bits in each inventory `u32` used for the block index within the superblock.
    /// The remaining high `COUNTER_WIDTH` bits store the midpoint-block delta.
    const BLOCK_IDX_BITS: usize = 32 - COUNTER_WIDTH;
    const BLOCK_IDX_MASK: usize = (1 << Self::BLOCK_IDX_BITS) - 1;

    /// Returns the underlying rank-small structure, consuming this structure.
    pub fn into_inner(self) -> C {
        self.small_counters
    }
}

impl<const NUM_U32S: usize, const COUNTER_WIDTH: usize, C: BitLength, I, O>
    SelectSmall<NUM_U32S, COUNTER_WIDTH, C, I, O>
{
    /// Returns the number of bits in the underlying bit vector.
    ///
    /// This method is equivalent to [`BitLength::len`], but it is provided to
    /// reduce ambiguity in method resolution.
    #[inline(always)]
    pub fn len(&self) -> usize {
        BitLength::len(self)
    }
}

macro_rules! impl_rank_small_sel {
    ($NUM_U32S: tt; $COUNTER_WIDTH: literal) => {
        impl<
            C: SmallCounters<$NUM_U32S, $COUNTER_WIDTH>
                + Backend<Word: Word + SelectInWord>
                + AsRef<[C::Word]>
                + BitLength
                + NumBits
                + SelectHinted,
        > SelectSmall<$NUM_U32S, $COUNTER_WIDTH, C>
        {
            /// Creates a new selection structure with four [`RankSmall`]
            /// blocks per inventory on average.
            #[must_use]
            pub fn new(small_counters: C) -> Self {
                Self::with_inv(small_counters, 4)
            }

            /// Creates a new selection structure with a given number of
            /// [`RankSmall`] blocks per inventory on average.
            #[must_use]
            pub fn with_inv(small_counters: C, blocks_per_inv: usize) -> Self {
                let num_bits = small_counters.len();
                let num_ones = small_counters.num_ones();

                let target_inventory_span = blocks_per_inv * Self::BLOCK_BIT_SIZE;
                let log2_ones_per_inventory = (num_ones as u64 * target_inventory_span as u64)
                    .div_ceil(num_bits.max(1) as u64)
                    .max(1)
                    .ilog2() as usize;

                Self::_new(small_counters, num_ones, log2_ones_per_inventory)
            }

            fn _new(small_counters: C, num_ones: usize, log2_ones_per_inventory: usize) -> Self {
                let bits_per_word = C::Word::BITS as usize;
                let ones_per_inventory = 1 << log2_ones_per_inventory;
                // half_ones is the midpoint within each inventory interval. We advance
                // next_quantum by half_ones each step, alternating between primary and
                // midpoint quantums. When ones_per_inventory == 1 (log2 == 0) half_ones
                // is 0, so step falls back to 1 and no midpoints are recorded.
                let half_ones = ones_per_inventory >> 1;
                let step = half_ones.max(1);

                let inventory_size = num_ones.div_ceil(ones_per_inventory);
                let mut inventory = Vec::<u32>::with_capacity(inventory_size + 1);

                // The inventory_begin vector stores the index of the first element of
                // each superblock in the inventory.
                let mut inventory_begin =
                    Vec::<usize>::with_capacity(small_counters.upper_counts().len() + 1);

                let mut past_ones: usize = 0;
                let mut next_quantum: usize = 0;

                for superblock in small_counters
                    .as_ref()
                    .chunks(Self::SUPERBLOCK_BIT_SIZE / bits_per_word)
                {
                    let mut first = true;
                    for (i, word) in superblock.iter().copied().enumerate() {
                        let ones_in_word = word.count_ones() as usize;

                        while past_ones + ones_in_word > next_quantum {
                            let in_word_index = word.select_in_word(next_quantum - past_ones);
                            let in_superblock_index = i * bits_per_word + in_word_index;
                            let block_in_superblock = in_superblock_index / Self::BLOCK_BIT_SIZE;

                            if half_ones == 0 || next_quantum & half_ones == 0 {
                                // Primary quantum: store the block index in the low
                                // BLOCK_IDX_BITS bits; high COUNTER_WIDTH bits will be
                                // filled when the midpoint quantum is encountered.
                                if first {
                                    inventory_begin.push(inventory.len());
                                    first = false;
                                }
                                inventory.push(block_in_superblock as u32);
                            } else {
                                // Midpoint quantum: pack the delta (midpoint block minus
                                // primary block) into the high COUNTER_WIDTH bits.
                                let last = inventory.last_mut().unwrap();
                                let delta =
                                    block_in_superblock - (*last as usize & Self::BLOCK_IDX_MASK);
                                debug_assert!(
                                    delta < Self::BLOCK_BIT_SIZE,
                                    "midpoint delta {delta} overflows COUNTER_WIDTH bits"
                                );
                                *last |= (delta as u32) << Self::BLOCK_IDX_BITS;
                            }
                            next_quantum += step;
                        }

                        past_ones += ones_in_word;
                    }
                }
                assert_eq!(num_ones, past_ones);

                if inventory.is_empty() {
                    inventory.push(0);
                    inventory_begin.push(0);
                } else {
                    inventory_begin.push(small_counters.as_ref().len());
                }

                let inventory = inventory.into_boxed_slice();
                let inventory_begin = inventory_begin.into_boxed_slice();

                Self {
                    small_counters,
                    inventory,
                    inventory_begin,
                    log2_ones_per_inventory,
                }
            }
        }

        impl<
            C: SmallCounters<$NUM_U32S, $COUNTER_WIDTH>
                + Backend<Word: Word + SelectInWord>
                + AsRef<[C::Word]>
                + BitLength
                + NumBits
                + SelectHinted,
        > SelectUnchecked for SelectSmall<$NUM_U32S, $COUNTER_WIDTH, C>
        {
            unsafe fn select_unchecked(&self, rank: usize) -> usize {
                unsafe {
                    let upper_counts = self.small_counters.upper_counts();
                    let counts = self.small_counters.counts();

                    let upper_block_idx =
                        upper_counts.linear_partition_point(|&x| x as usize <= rank) - 1;
                    let upper_rank = *upper_counts.get_unchecked(upper_block_idx) as usize;
                    let local_rank = rank - upper_rank;

                    let inventory = self.inventory.as_ref();
                    let inventory_begin = self.inventory_begin.as_ref();

                    // we find the two inventory entries containing the rank and from that
                    // the blocks containing the rank.
                    // if the span of the two entries is not contained in the same upper block
                    // we clip the span to the upper block boundaries since we know that
                    // the rank is in the upper block with index upper_block_idx.

                    let inv_idx = rank >> self.log2_ones_per_inventory;
                    let inv_upper_block_idx =
                        inventory_begin.linear_partition_point(|&x| x as usize <= inv_idx) - 1;
                    // half_ones is ones_per_inventory / 2; rank & half_ones != 0 means
                    // we are in the second half of the inventory interval, so we use the
                    // stored midpoint block (base_block + mid_delta) as our starting point.
                    let half_ones = 1usize << self.log2_ones_per_inventory >> 1;
                    // Branchless: compute a mask that is all-ones in the second half
                    // and all-zeros in the first half, avoiding a ~50/50 branch that
                    // would cause systematic mispredictions.
                    let second_half_mask = ((rank & half_ones != 0) as usize).wrapping_neg();
                    let mut block_idx = if inv_upper_block_idx == upper_block_idx {
                        let inv_entry = *inventory.get_unchecked(inv_idx) as usize;
                        let base_block = inv_entry & Self::BLOCK_IDX_MASK;
                        let mid_delta = inv_entry >> Self::BLOCK_IDX_BITS;
                        base_block + (mid_delta & second_half_mask)
                    } else {
                        // For extremely sparse and large bit vectors, the inventory entry
                        // containing the rank could fall in a previous upper block.
                        // Since we know the rank is in upper block upper_block_idx, start
                        // from the beginning of that superblock.
                        0
                    } + upper_block_idx
                        * (Self::SUPERBLOCK_BIT_SIZE / Self::BLOCK_BIT_SIZE);

                    // Prefetch all subblocks of the approximate target block now,
                    // so the bit-vector DRAM fetch can proceed in parallel with
                    // the upcoming counts DRAM fetch (same idea as rank_unchecked).
                    {
                        let bits_ref: &[C::Word] = self.as_ref();
                        let words_per_subblock = Self::SUBBLOCK_BIT_SIZE / C::Word::BITS as usize;
                        let base_word = block_idx * (Self::BLOCK_BIT_SIZE / C::Word::BITS as usize);
                        for k in 0..Self::NUM_SUBBLOCKS {
                            crate::utils::prefetch_index(
                                bits_ref,
                                base_word + k * words_per_subblock,
                            );
                        }
                    }

                    let last_block_idx;
                    if inv_idx + 1 < inventory.len() {
                        // linear_partition_point returns the first index where
                        // the predicate is false; subtracting 1 gives the last
                        // superblock whose inventory start is <= inv_idx + 1,
                        // i.e., the superblock containing inventory[inv_idx + 1].
                        let next_inv_upper_block_idx = inventory_begin
                            .linear_partition_point(|&x| x as usize <= inv_idx + 1)
                            - 1;
                        last_block_idx = if next_inv_upper_block_idx == upper_block_idx {
                            let next_base_block = (*inventory.get_unchecked(inv_idx + 1) as usize)
                                & Self::BLOCK_IDX_MASK;
                            // +1 because the next primary may be anywhere within next_base_block,
                            // so we must include that block in the scan range.
                            next_base_block
                                + 1
                                + upper_block_idx
                                    * (Self::SUPERBLOCK_BIT_SIZE / Self::BLOCK_BIT_SIZE)
                        } else {
                            (upper_block_idx + 1)
                                * (Self::SUPERBLOCK_BIT_SIZE / Self::BLOCK_BIT_SIZE)
                        };
                    } else {
                        // Since we use 32-bit inventory entries, we cannot add
                        // a sentinel with value equal to the number of bits
                        // (which may exceed 2^32). Thus, we handle the last
                        // inventory entry as a special case.
                        last_block_idx = self.len().div_ceil(Self::BLOCK_BIT_SIZE);
                    }

                    debug_assert!(block_idx < counts.len());

                    debug_assert!(
                        block_idx <= last_block_idx,
                        "{} > {}",
                        block_idx,
                        last_block_idx
                    );

                    debug_assert!(block_idx < last_block_idx);

                    block_idx += counts[block_idx..last_block_idx]
                        .linear_partition_point(|x| x.absolute as usize <= local_rank)
                        - 1;

                    let block_count = counts.get_unchecked(block_idx);
                    let hint_rank = upper_rank + block_count.absolute as usize;
                    let hint_pos = block_idx * Self::BLOCK_BIT_SIZE;

                    self.complete_select(block_count, hint_pos, rank, hint_rank)
                }
            }
        }

        impl<
            C: SmallCounters<$NUM_U32S, $COUNTER_WIDTH>
                + Backend<Word: Word + SelectInWord>
                + AsRef<[C::Word]>
                + BitLength
                + NumBits
                + SelectHinted,
        > Select for SelectSmall<$NUM_U32S, $COUNTER_WIDTH, C>
        {
        }
    };
}

impl<
    C: SmallCounters<2, 9>
        + Backend<Word: Word + SelectInWord>
        + AsRef<[C::Word]>
        + BitLength
        + NumBits,
> SelectSmall<2, 9, C>
{
    #[inline(always)]
    unsafe fn complete_select(
        &self,
        block_count: &Block32Counters<2, 9>,
        mut hint_pos: usize,
        rank: usize,
        hint_rank: usize,
    ) -> usize {
        const ONES_STEP_9: u64 = (1_u64 << 0)
            | (1_u64 << 9)
            | (1_u64 << 18)
            | (1_u64 << 27)
            | (1_u64 << 36)
            | (1_u64 << 45)
            | (1_u64 << 54);
        const MSBS_STEP_9: u64 = 0x100_u64 * ONES_STEP_9;
        macro_rules! ULEQ_STEP_9 {
            ($x:ident, $y:ident) => {
                (((((($y) | MSBS_STEP_9) - (($x) & !MSBS_STEP_9)) | ($x ^ $y)) ^ ($x & !$y))
                    & MSBS_STEP_9)
            };
        }

        let rank_in_block = rank - hint_rank;
        let rank_in_block_step_9 = rank_in_block as u64 * ONES_STEP_9;
        let relative = block_count.all_rel();
        let offset_in_block = ULEQ_STEP_9!(relative, rank_in_block_step_9).count_ones() as usize;

        let rank_in_word = rank_in_block - block_count.rel(offset_in_block);
        hint_pos += offset_in_block * Self::SUBBLOCK_BIT_SIZE;

        hint_pos
            + unsafe {
                self.as_ref()
                    .get_unchecked(hint_pos / C::Word::BITS as usize)
                    .select_in_word(rank_in_word)
            }
    }
}

impl<
    C: SmallCounters<1, 9>
        + Backend<Word: Word + SelectInWord>
        + AsRef<[C::Word]>
        + BitLength
        + NumBits
        + SelectHinted,
> SelectSmall<1, 9, C>
{
    #[inline(always)]
    unsafe fn complete_select(
        &self,
        block_count: &Block32Counters<1, 9>,
        hint_pos: usize,
        rank: usize,
        hint_rank: usize,
    ) -> usize {
        const ONES_STEP_9: u64 = (1_u64 << 0) | (1_u64 << 9) | (1_u64 << 18);
        const MSBS_STEP_9: u64 = 0x100_u64 * ONES_STEP_9;

        macro_rules! ULEQ_STEP_9 {
            ($x:ident, $y:ident) => {
                (((((($y) | MSBS_STEP_9) - (($x) & !MSBS_STEP_9)) | ($x ^ $y)) ^ ($x & !$y))
                    & MSBS_STEP_9)
            };
        }

        let rank_in_block = rank - hint_rank;
        let rank_in_block_step_9 = rank_in_block as u64 * ONES_STEP_9;
        let relative = block_count.all_rel();

        let offset_in_block = ULEQ_STEP_9!(relative, rank_in_block_step_9).count_ones() as usize;

        let hint_pos = hint_pos + offset_in_block * Self::SUBBLOCK_BIT_SIZE;
        let hint_rank = hint_rank + block_count.rel(offset_in_block);
        let subblock_words = Self::SUBBLOCK_BIT_SIZE / C::Word::BITS as usize;
        unsafe {
            match subblock_words {
                1 => self.select_hinted::<1>(rank, hint_pos, hint_rank),
                2 => self.select_hinted::<2>(rank, hint_pos, hint_rank),
                4 => self.select_hinted::<4>(rank, hint_pos, hint_rank),
                8 => self.select_hinted::<8>(rank, hint_pos, hint_rank),
                16 => self.select_hinted::<16>(rank, hint_pos, hint_rank),
                32 => self.select_hinted::<32>(rank, hint_pos, hint_rank),
                _ => self.select_hinted::<{ usize::MAX }>(rank, hint_pos, hint_rank),
            }
        }
    }
}

impl<
    C: SmallCounters<1, 10>
        + Backend<Word: Word + SelectInWord>
        + AsRef<[C::Word]>
        + BitLength
        + NumBits
        + SelectHinted,
> SelectSmall<1, 10, C>
{
    #[inline(always)]
    unsafe fn complete_select(
        &self,
        block_count: &Block32Counters<1, 10>,
        hint_pos: usize,
        rank: usize,
        hint_rank: usize,
    ) -> usize {
        const ONES_STEP_10: u64 = (1_u64 << 0) | (1_u64 << 10) | (1_u64 << 20);
        const MSBS_STEP_10: u64 = 0x200_u64 * ONES_STEP_10;

        macro_rules! ULEQ_STEP_10 {
            ($x:ident, $y:ident) => {
                (((((($y) | MSBS_STEP_10) - (($x) & !MSBS_STEP_10)) | ($x ^ $y)) ^ ($x & !$y))
                    & MSBS_STEP_10)
            };
        }

        let rank_in_block = rank - hint_rank;
        let rank_in_block_step_10 = rank_in_block as u64 * ONES_STEP_10;
        let relative = block_count.all_rel();

        let offset_in_block = ULEQ_STEP_10!(relative, rank_in_block_step_10).count_ones() as usize;

        let hint_pos = hint_pos + offset_in_block * Self::SUBBLOCK_BIT_SIZE;
        let hint_rank = hint_rank + block_count.rel(offset_in_block);
        let subblock_words = Self::SUBBLOCK_BIT_SIZE / C::Word::BITS as usize;
        unsafe {
            match subblock_words {
                1 => self.select_hinted::<1>(rank, hint_pos, hint_rank),
                2 => self.select_hinted::<2>(rank, hint_pos, hint_rank),
                4 => self.select_hinted::<4>(rank, hint_pos, hint_rank),
                8 => self.select_hinted::<8>(rank, hint_pos, hint_rank),
                16 => self.select_hinted::<16>(rank, hint_pos, hint_rank),
                32 => self.select_hinted::<32>(rank, hint_pos, hint_rank),
                _ => self.select_hinted::<{ usize::MAX }>(rank, hint_pos, hint_rank),
            }
        }
    }
}

impl<
    C: SmallCounters<1, 11>
        + Backend<Word: Word + SelectInWord>
        + AsRef<[C::Word]>
        + BitLength
        + NumBits
        + SelectHinted,
> SelectSmall<1, 11, C>
{
    #[inline(always)]
    unsafe fn complete_select(
        &self,
        block_count: &Block32Counters<1, 11>,
        hint_pos: usize,
        rank: usize,
        hint_rank: usize,
    ) -> usize {
        const ONES_STEP_11: u64 = (1_u64 << 0) | (1_u64 << 11) | (1_u64 << 22);
        const MSBS_STEP_11: u64 = 0x400_u64 * ONES_STEP_11;

        macro_rules! ULEQ_STEP_11 {
            ($x:ident, $y:ident) => {
                (((((($y) | MSBS_STEP_11) - (($x) & !MSBS_STEP_11)) | ($x ^ $y)) ^ ($x & !$y))
                    & MSBS_STEP_11)
            };
        }

        let rank_in_block = rank - hint_rank;
        let rank_in_block_step_11 = rank_in_block as u64 * ONES_STEP_11;
        let relative = block_count.all_rel();

        let offset_in_block = ULEQ_STEP_11!(relative, rank_in_block_step_11).count_ones() as usize;

        let hint_pos = hint_pos + offset_in_block * Self::SUBBLOCK_BIT_SIZE;
        let hint_rank = hint_rank + block_count.rel(offset_in_block);
        let subblock_words = Self::SUBBLOCK_BIT_SIZE / C::Word::BITS as usize;
        unsafe {
            match subblock_words {
                1 => self.select_hinted::<1>(rank, hint_pos, hint_rank),
                2 => self.select_hinted::<2>(rank, hint_pos, hint_rank),
                4 => self.select_hinted::<4>(rank, hint_pos, hint_rank),
                8 => self.select_hinted::<8>(rank, hint_pos, hint_rank),
                16 => self.select_hinted::<16>(rank, hint_pos, hint_rank),
                32 => self.select_hinted::<32>(rank, hint_pos, hint_rank),
                _ => self.select_hinted::<{ usize::MAX }>(rank, hint_pos, hint_rank),
            }
        }
    }
}

impl<
    C: SmallCounters<3, 13>
        + Backend<Word: Word + SelectInWord>
        + AsRef<[C::Word]>
        + BitLength
        + NumBits
        + SelectHinted,
> SelectSmall<3, 13, C>
{
    #[inline(always)]
    unsafe fn complete_select(
        &self,
        block_count: &Block32Counters<3, 13>,
        hint_pos: usize,
        rank: usize,
        hint_rank: usize,
    ) -> usize {
        const ONES_STEP_13: u128 = (1_u128 << 0)
            | (1_u128 << 13)
            | (1_u128 << 26)
            | (1_u128 << 39)
            | (1_u128 << 52)
            | (1_u128 << 65)
            | (1_u128 << 78);
        const MSBS_STEP_13: u128 = 0x1000_u128 * ONES_STEP_13;

        macro_rules! ULEQ_STEP_13 {
            ($x:ident, $y:ident) => {
                (((((($y) | MSBS_STEP_13) - (($x) & !MSBS_STEP_13)) | ($x ^ $y)) ^ ($x & !$y))
                    & MSBS_STEP_13)
            };
        }

        let rank_in_block = rank - hint_rank;
        let rank_in_block_step_13 = rank_in_block as u128 * ONES_STEP_13;
        let relative = block_count.all_rel();

        let offset_in_block = ULEQ_STEP_13!(relative, rank_in_block_step_13).count_ones() as usize;

        let hint_pos = hint_pos + offset_in_block * Self::SUBBLOCK_BIT_SIZE;
        let hint_rank = hint_rank + block_count.rel(offset_in_block);
        let subblock_words = Self::SUBBLOCK_BIT_SIZE / C::Word::BITS as usize;
        unsafe {
            match subblock_words {
                1 => self.select_hinted::<1>(rank, hint_pos, hint_rank),
                2 => self.select_hinted::<2>(rank, hint_pos, hint_rank),
                4 => self.select_hinted::<4>(rank, hint_pos, hint_rank),
                8 => self.select_hinted::<8>(rank, hint_pos, hint_rank),
                16 => self.select_hinted::<16>(rank, hint_pos, hint_rank),
                32 => self.select_hinted::<32>(rank, hint_pos, hint_rank),
                _ => self.select_hinted::<{ usize::MAX }>(rank, hint_pos, hint_rank),
            }
        }
    }
}

impl<
    C: SmallCounters<2, 8>
        + Backend<Word: Word + SelectInWord>
        + AsRef<[C::Word]>
        + BitLength
        + NumBits,
> SelectSmall<2, 8, C>
{
    #[inline(always)]
    unsafe fn complete_select(
        &self,
        block_count: &Block32Counters<2, 8>,
        mut hint_pos: usize,
        rank: usize,
        hint_rank: usize,
    ) -> usize {
        const ONES_STEP_8: u64 = (1_u64 << 0)
            | (1_u64 << 8)
            | (1_u64 << 16)
            | (1_u64 << 24)
            | (1_u64 << 32)
            | (1_u64 << 40)
            | (1_u64 << 48);
        const MSBS_STEP_8: u64 = 0x80_u64 * ONES_STEP_8;
        macro_rules! ULEQ_STEP_8 {
            ($x:ident, $y:ident) => {
                (((((($y) | MSBS_STEP_8) - (($x) & !MSBS_STEP_8)) | ($x ^ $y)) ^ ($x & !$y))
                    & MSBS_STEP_8)
            };
        }

        let rank_in_block = rank - hint_rank;
        let rank_in_block_step_8 = rank_in_block as u64 * ONES_STEP_8;
        let relative = block_count.all_rel();
        let offset_in_block = ULEQ_STEP_8!(relative, rank_in_block_step_8).count_ones() as usize;

        let rank_in_word = rank_in_block - block_count.rel(offset_in_block);
        hint_pos += offset_in_block * Self::SUBBLOCK_BIT_SIZE;

        hint_pos
            + unsafe {
                self.as_ref()
                    .get_unchecked(hint_pos / C::Word::BITS as usize)
                    .select_in_word(rank_in_word)
            }
    }
}

impl<
    C: SmallCounters<1, 8>
        + Backend<Word: Word + SelectInWord>
        + AsRef<[C::Word]>
        + BitLength
        + NumBits
        + SelectHinted,
> SelectSmall<1, 8, C>
{
    #[inline(always)]
    unsafe fn complete_select(
        &self,
        block_count: &Block32Counters<1, 8>,
        hint_pos: usize,
        rank: usize,
        hint_rank: usize,
    ) -> usize {
        const ONES_STEP_8: u64 = (1_u64 << 0) | (1_u64 << 8) | (1_u64 << 16);
        const MSBS_STEP_8: u64 = 0x80_u64 * ONES_STEP_8;
        macro_rules! ULEQ_STEP_8 {
            ($x:ident, $y:ident) => {
                (((((($y) | MSBS_STEP_8) - (($x) & !MSBS_STEP_8)) | ($x ^ $y)) ^ ($x & !$y))
                    & MSBS_STEP_8)
            };
        }

        let rank_in_block = rank - hint_rank;
        let rank_in_block_step_8 = rank_in_block as u64 * ONES_STEP_8;
        let relative = block_count.all_rel();

        let offset_in_block = ULEQ_STEP_8!(relative, rank_in_block_step_8).count_ones() as usize;

        let hint_pos = hint_pos + offset_in_block * Self::SUBBLOCK_BIT_SIZE;
        let hint_rank = hint_rank + block_count.rel(offset_in_block);
        let subblock_words = Self::SUBBLOCK_BIT_SIZE / C::Word::BITS as usize;
        unsafe {
            match subblock_words {
                1 => self.select_hinted::<1>(rank, hint_pos, hint_rank),
                2 => self.select_hinted::<2>(rank, hint_pos, hint_rank),
                4 => self.select_hinted::<4>(rank, hint_pos, hint_rank),
                8 => self.select_hinted::<8>(rank, hint_pos, hint_rank),
                16 => self.select_hinted::<16>(rank, hint_pos, hint_rank),
                32 => self.select_hinted::<32>(rank, hint_pos, hint_rank),
                _ => self.select_hinted::<{ usize::MAX }>(rank, hint_pos, hint_rank),
            }
        }
    }
}

// One invocation per unique (NUM_U32S, COUNTER_WIDTH) pair.
// The impl is generic over C, so it covers both u32 and u64 backends.
impl_rank_small_sel!(2; 9);
impl_rank_small_sel!(1; 9);
impl_rank_small_sel!(1; 10);
impl_rank_small_sel!(1; 11);
impl_rank_small_sel!(3; 13);
impl_rank_small_sel!(2; 8);
impl_rank_small_sel!(1; 8);

/// A trait providing the semantics of [`partition_point`], but using a
/// linear search.
///
/// [`partition_point`]: slice::partition_point
trait LinearPartitionPointExt<T>: AsRef<[T]> {
    fn linear_partition_point<P>(&self, mut pred: P) -> usize
    where
        P: FnMut(&T) -> bool,
    {
        let as_ref = self.as_ref();
        as_ref.iter().position(|x| !pred(x)).unwrap_or(as_ref.len())
    }
}

impl<T> LinearPartitionPointExt<T> for [T] {}