sux 0.14.0

/*
 *
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
 * SPDX-FileCopyrightText: 2023 Inria
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

//! An implementation of the Elias–Fano representation of monotone sequences.
//!
//! Given a monotone sequence 0 ≤ *x*₀ ≤ *x*₁ ≤ ... ≤ *x*<sub>*n* – 1</sub> ≤
//! *u*, where *u* is a given upper bound, the Elias–Fano representation makes
//! it possible to store the sequence using at most 2 + log₂(*u*/*n*) bits per
//! element, which is very close to the information-theoretical lower bound ≈ lg
//! *e* + log₂(*u*/*n*) when *n* is much smaller than *u*. A typical example is a
//! list of pointers into records of a large file: instead of using, for each
//! pointer, a number of bits sufficient to express the length of the file, the
//! Elias–Fano representation makes it possible to use, for each pointer, a
//! number of bits roughly equal to the logarithm of the average length of a
//! record.
//!
//! The representation was introduced by Peter Elias in "[Efficient storage and
//! retrieval by content and address of static files]”, *J. Assoc. Comput.
//! Mach.*, 21(2):246–260, ACM, 1974, and also independently by Robert Fano in
//! “[On the number of bits required to implement an associative memory]”,
//! Memorandum 61, Computer Structures Group, Project MAC, MIT, Cambridge,
//! Mass., n.d., 1971.
//!
//! This implementation is based on algorithmic engineering ideas proposed by
//! Sebastiano Vigna in “[Quasi-succinct indices]”, *Proceedings of the 6th ACM
//! International Conference on Web Search and Data Mining, WSDM'13*, pages
//! 83–92, ACM, 2013. The name “Elias–Fano” for this representation was used for
//! the first time by Sebastiano Vigna in “[Broadword Implementation of
//! Rank/Select Queries]”, _Proc. of the 7th International Workshop on
//! Experimental Algorithms, WEA 2008_, volume 5038 of Lecture Notes in Computer
//! Science, pages 154–168, Springer, 2008.
//!
//! The elements of the sequence are recorded by storing separately the lower
//! *s* = ⌊log₂(*u*/*n*)⌋ bits and the remaining upper bits. The lower bits are
//! stored contiguously, whereas the upper bits are stored in an array of *n* +
//! ⌊*u* / 2*ˢ*⌋ bits by setting, for each 0 ≤ *i* < *n*, the bit of
//! index ⌊*xᵢ* / 2*ˢ*⌋ + *i*; the value can then be
//! recovered by selecting the *i*-th bit of the resulting bit array and
//! subtracting *i* (note that this will work because the upper bits are
//! nondecreasing).
//!
//! [Broadword Implementation of Rank/Select Queries]: https://link.springer.com/chapter/10.1007/978-3-540-68552-4_12
//! [Quasi-succinct indices]: https://dl.acm.org/doi/10.1145/2433396.2433409
//! [On the number of bits required to implement an associative memory]: http://csg.csail.mit.edu/pubs/memos/Memo-61/Memo-61.pdf
//! [Efficient storage and retrieval by content and address of static files]: https://dl.acm.org/doi/abs/10.1145/321812.321820

use crate::prelude::{indexed_dict::*, *};
use crate::traits::{AtomicBitVecOps, BitVecOpsMut, TryIntoUnaligned, Word, bit_field_slice::*};
use crate::utils::SelectInWord;
use atomic_primitive::{Atomic, AtomicPrimitive, PrimitiveAtomicUnsigned};
use core::sync::atomic::Ordering;
use mem_dbg::*;
use num_primitive::PrimitiveNumberAs;
use std::borrow::Borrow;
use std::iter::FusedIterator;
use value_traits::slices::{SliceByValue, SliceByValueMut};

/// The default type for an Elias–Fano structure implementing an [`IndexedSeq`],
/// but not [`IndexedDict`], [`Succ`], or [`Pred`].
///
/// You can start from this type to customize your Elias–Fano structure using
/// different const parameters or a different selection structure altogether.
pub type EfSeq<V = usize> =
    EliasFano<V, SelectAdaptConst<BitVec<Box<[usize]>>, Box<[usize]>, 12, 3>>;

/// The default type for an Elias–Fano structure implementing
/// [`IndexedDict`], [`Succ`], and [`Pred`].
///
/// You can start from this type to customize your Elias–Fano structure using
/// different const parameters or a different selection structure altogether.
pub type EfDict<V = usize> =
    EliasFano<V, SelectZeroAdaptConst<BitVec<Box<[usize]>>, Box<[usize]>, 12, 3>>;

/// The default type for an Elias–Fano structure implementing an
/// [`IndexedSeq`], [`IndexedDict`], [`Succ`], and [`Pred`].
///
/// You can start from this type to customize your Elias–Fano structure using
/// different const parameters or different selection structures altogether.
pub type EfSeqDict<V = usize> = EliasFano<
    V,
    SelectZeroAdaptConst<
        SelectAdaptConst<BitVec<Box<[usize]>>, Box<[usize]>, 12, 3>,
        Box<[usize]>,
        12,
        3,
    >,
>;

/// A structure that stores a monotone sequence of integers of type `V` using
/// the Elias–Fano representation.
///
/// There are two main ways to build a base [`EliasFano`] structure: creating an
/// [`EliasFanoBuilder`] (adding values using `push` or `extend`), or an
/// [`EliasFanoConcurrentBuilder`] (using `set`). Additionally, a [`From`]
/// convenience implementation makes it possible to build an [`EliasFano`]
/// from a slice.
///
/// In both cases, if you use the [`build`] method you will only be able to
/// iterate over the sequence. Using the methods [`build_with_seq`],
/// [`build_with_dict`], or [`build_with_seq_and_dict`] you will have
/// access to the additional functionalities of an [`IndexedSeq`] or an
/// [`IndexedDict`] with [`Succ`] and [`Pred`].
///
/// It is also possible to manually enrich the base structure by calling
/// [`EliasFano::map_high_bits`]. To use the structure as an [`IndexedSeq`] you
/// need to add a selection structure for ones, whereas to use it as an
/// [`IndexedDict`] with [`SuccUnchecked`] and [`PredUnchecked`] you need to add
/// a selection structure for zeros. [`SelectAdaptConst`] and
/// [`SelectZeroAdaptConst`] are the structures of choice for this purpose. If
/// you add both structures, you will have an [`IndexedDict`] with [`Succ`] and
/// [`Pred`].
///
/// # Type Parameters
///
/// - `V`: The value type (e.g., `u64`). Must implement [`Word`].
/// - `H`: The higher-bits storage. Defaults to [`BitVec<Box<[usize]>>`][bitvec-box].
///   Enriching this with selection structures enables [`IndexedSeq`] and/or
///   successor/predecessor queries.
/// - `L`: The lower-bits storage. Defaults to [`BitFieldVec<Box<[V]>>`][bfvec-box].
///
/// # Bound Checks for Successor and Predecessor Queries
///
/// The unchecked version of successor and predecessor queries (i.e.,
/// [`SuccUnchecked`] and [`PredUnchecked`]) require that the required successor
/// or predecessor exists, otherwise you have undefined behavior. We provide these
/// versions because in applications it is quite common to have a guarantee that
/// the successor or predecessor of a value exists.
///
/// The checked versions (i.e., [`Succ`] and [`Pred`]) use the cached
/// first and last values stored in the structure to determine whether the
/// requested successor or predecessor exists. This makes the bounds check
/// essentially free and does not require [`SelectUnchecked`] on the high
/// bits.
///
/// # Iterators
///
/// We provide a number of iterators over the values of the sequence:
///
/// - Forward iterators, returned by [`iter`] and
///   [`iter_from`], that iterate over the values in increasing order, are the
///   fastest. The returned iterators implement also [`UncheckedIterator`].
///
/// - Backward iterators, returned by [`iter_back`] and
///   [`iter_back_from`], that iterate over the values in decreasing order, are
///   slightly slower than forward iterators. The returned iterators implement
///   also [`UncheckedIterator`].
///
/// - Bidirectional iterators, returned by [`iter_bidi`]
///   and [`iter_bidi_from`], that can iterate in both directions, are the
///   slowest, but they are significantly faster than selecting values.
///
/// Besides the convenience inherent methods, we implement [`IntoIterator`],
/// [`IntoIteratorFrom`], [`IntoBackIterator`], [`IntoBackIteratorFrom`],
/// [`IntoBidiIterator`], and [`IntoBidiIteratorFrom`] for references to an
/// [`EliasFano`] structure.
///
/// Iterators can also be obtained from methods in [`SuccUnchecked`],
/// [`PredUnchecked`], [`Succ`], and [`Pred`] that return an iterator starting
/// from the successor or predecessor of a given value.
///
/// # Unaligned access
///
/// This structure can use [unaligned access] to retrieve the lower bits. On
/// some architectures this provides a mild performance improvement. To use
/// unaligned access, call [`try_into_unaligned`]:
///
/// ```ignore
/// use sux::traits::TryIntoUnaligned;
/// let ef = ef.try_into_unaligned()?;
/// ```
///
/// See the [`BitFieldVecU`] documentation for more details and caveats about
/// unaligned access.
///
/// # Examples
///
/// Using convenience builders:
/// ```rust
/// # use sux::rank_sel::{SelectAdaptConst, SelectZeroAdaptConst};
/// # use sux::dict::{EliasFanoBuilder};
/// # use sux::traits::{Types,IndexedSeq,IndexedDict,SuccUnchecked,Succ};
/// let mut efb = EliasFanoBuilder::new(4, 10u64);
/// efb.push(0);
/// efb.push(2);
/// efb.push(8);
/// efb.push(10);
///
/// let ef = efb.build_with_seq();
///
/// assert_eq!(ef.get(0), 0);
/// assert_eq!(ef.get(1), 2);
///
/// let mut efb = EliasFanoBuilder::new(4, 10u64);
/// efb.push(0);
/// efb.push(2);
/// efb.push(8);
/// efb.push(10);
///
/// let ef = efb.build_with_dict();
///
/// assert_eq!(unsafe { ef.succ_unchecked::<false>(6) }, (2, 8));
/// // Calling unsafe { ef.succ_unchecked::<false>(11) } would be UB
///
/// let mut efb = EliasFanoBuilder::new(4, 10u64);
/// efb.push(0);
/// efb.push(2);
/// efb.push(8);
/// efb.push(10);
///
/// let ef = efb.build_with_seq_and_dict();
/// assert_eq!(ef.get(0), 0);
/// assert_eq!(ef.get(1), 2);
/// assert_eq!(ef.succ(6), Some((2, 8)));
/// assert_eq!(ef.succ(11), None);
/// ```
///
/// Enriching manually a base structure with [`map_high_bits`]:
/// ```rust
/// # use sux::rank_sel::{SelectAdaptConst, SelectZeroAdaptConst};
/// # use sux::dict::{EliasFanoBuilder};
/// # use sux::traits::{Types,IndexedSeq,IndexedDict,Succ};
/// let mut efb = EliasFanoBuilder::new(4, 10u64);
/// efb.push(0);
/// efb.push(2);
/// efb.push(8);
/// efb.push(10);
///
/// let ef = efb.build();
/// // Add a selection structure for ones (implements IndexedSeq)
/// let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };
///
/// assert_eq!(ef.get(0), 0);
/// assert_eq!(ef.get(1), 2);
///
/// // Add a further selection structure for zeros (implements IndexedDict, Succ, Pred)
/// let ef = unsafe { ef.map_high_bits(SelectZeroAdaptConst::<_, _>::new) };
///
/// assert_eq!(ef.succ(6), Some((2, 8)));
/// assert_eq!(ef.succ(11), None);
/// ```
///
/// Building a base structure with convenience methods:
/// ```rust
/// # use sux::rank_sel::{SelectAdaptConst};
/// # use sux::dict::{EliasFano, EliasFanoBuilder};
/// # use sux::traits::{Types,IndexedSeq};
///
/// // Convenience constructor that iterates over a slice
/// let mut ef: EliasFano = vec![0, 2, 8, 10].into();
/// // Add a selection structure for ones (implements IndexedSeq)
/// let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };
///
/// assert_eq!(ef.get(0), 0);
/// assert_eq!(ef.get(1), 2);
///
/// let mut efb = EliasFanoBuilder::new(4, 10u64);
/// // Add values using an iterator
/// efb.extend(vec![0, 2, 8, 10]);
/// let ef = efb.build();
/// // Add a selection structure for ones (implements IndexedSeq)
/// let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };
///
/// assert_eq!(ef.get(0), 0);
/// assert_eq!(ef.get(1), 2);
/// ```
///
/// [`build`]: EliasFanoBuilder::build
/// [`build_with_seq`]: EliasFanoBuilder::build_with_seq
/// [`build_with_dict`]: EliasFanoBuilder::build_with_dict
/// [`build_with_seq_and_dict`]: EliasFanoBuilder::build_with_seq_and_dict
/// [bitvec-box]: crate::bits::BitVec
/// [bfvec-box]: crate::bits::BitFieldVec
/// [`map_high_bits`]: EliasFano::map_high_bits
/// [`try_into_unaligned`]: TryIntoUnaligned::try_into_unaligned
/// [unaligned access]: BitFieldVec::get_unaligned
/// [`iter_bidi_from`]: EliasFano::iter_bidi_from
/// [`iter_bidi`]: EliasFano::iter_bidi
/// [`iter_back_from`]: EliasFano::iter_back_from
/// [`iter_back`]: EliasFano::iter_back
/// [`iter_from`]: EliasFano::iter_from
/// [`iter`]: EliasFano::iter
#[derive(Debug, Clone, Hash, MemSize, MemDbg, value_traits::Subslices)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[value_traits_subslices(bound = "V: Word + PrimitiveNumberAs<usize>")]
#[value_traits_subslices(bound = "H: AsRef<[usize]> + SelectUnchecked")]
#[value_traits_subslices(bound = "L: SliceByValue<Value = V>")]
pub struct EliasFano<V = usize, H = BitVec<Box<[usize]>>, L = BitFieldVec<Box<[V]>>> {
    /// The number of values.
    n: usize,
    /// An upper bound to the values.
    u: V,
    /// The number of lower bits.
    l: usize,
    /// The first value in the sequence, or `V::MAX` if the sequence is empty.
    first_val: V,
    /// The last value in the sequence, or `V::MIN` if the sequence is empty.
    last_val: V,
    /// The lower-bits array.
    low_bits: L,
    /// The higher-bits array.
    high_bits: H,
}

impl<V, H, L> EliasFano<V, H, L> {
    /// Returns the parts composing the structure (number of elements, upper
    /// bound, number of lower bits, low bits, high bits, first value, last
    /// value). For an empty sequence, first value is `V::MAX` and last value
    /// is `V::MIN`.
    pub fn into_parts(self) -> (usize, V, usize, L, H, V, V) {
        (
            self.n,
            self.u,
            self.l,
            self.low_bits,
            self.high_bits,
            self.first_val,
            self.last_val,
        )
    }

    /// Estimate the size of an instance.
    pub fn estimate_size(u: u64, n: usize) -> usize {
        2 * n + (n * (u as f64 / n as f64).log2().ceil() as usize)
    }

    /// Returns the number of elements in the sequence.
    ///
    /// This method is equivalent to [`IndexedSeq::len`], but it is provided to
    /// reduce ambiguity in method resolution.
    #[inline]
    pub const fn len(&self) -> usize {
        self.n
    }

    /// Returns the upper bound used to build the structure.
    #[inline]
    pub fn upper_bound(&self) -> V
    where
        V: Copy,
    {
        self.u
    }

    /// Replaces the high bits.
    ///
    /// # Safety
    ///
    /// This method is unsafe because it is not possible to guarantee that the
    /// new high bits are identical to the old ones as a bit vector.
    pub unsafe fn map_high_bits<H2>(self, func: impl FnOnce(H) -> H2) -> EliasFano<V, H2, L> {
        EliasFano {
            n: self.n,
            u: self.u,
            l: self.l,
            first_val: self.first_val,
            last_val: self.last_val,
            low_bits: self.low_bits,
            high_bits: func(self.high_bits),
        }
    }

    /// Replaces the low bits.
    ///
    /// # Safety
    ///
    /// This method is unsafe because it is not possible to guarantee that the
    /// new low bits are identical to the old ones as a vector.
    pub unsafe fn map_low_bits<L2>(self, func: impl FnOnce(L) -> L2) -> EliasFano<V, H, L2> {
        EliasFano {
            n: self.n,
            u: self.u,
            l: self.l,
            first_val: self.first_val,
            last_val: self.last_val,
            low_bits: func(self.low_bits),
            high_bits: self.high_bits,
        }
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>> Types
    for EliasFano<V, H, L>
{
    type Output<'a> = V;
    type Input = V;
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> IndexedSeq for EliasFano<V, H, L>
{
    #[inline]
    fn len(&self) -> usize {
        self.n
    }

    #[inline(always)]
    unsafe fn get_unchecked(&self, index: usize) -> V {
        unsafe {
            let high_bits = V::as_from(self.high_bits.select_unchecked(index) - index);
            let low_bits = self.low_bits.get_value_unchecked(index);
            (high_bits << self.l) | low_bits
        }
    }

    #[inline]
    fn first_value(&self) -> Option<V> {
        (self.n != 0).then_some(self.first_val)
    }

    #[inline]
    fn last_value(&self) -> Option<V> {
        (self.n != 0).then_some(self.last_val)
    }
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectZeroUnchecked,
    L: SliceByValue<Value = V>,
> IndexedDict for EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    fn index_of(&self, value: impl Borrow<Self::Input>) -> Option<usize> {
        let value = *value.borrow();
        if value > self.u {
            return None;
        }
        let zeros_to_skip: usize = (value >> self.l).try_into().unwrap();
        let bit_pos = if zeros_to_skip == 0 {
            0
        } else {
            unsafe { self.high_bits.select_zero_unchecked(zeros_to_skip - 1) + 1 }
        };

        let mut rank = bit_pos - zeros_to_skip;
        let mut iter = self.low_bits.into_unchecked_iter_from(rank);
        let mut word_idx = bit_pos / (usize::BITS as usize);
        let bits_to_clean = bit_pos % (usize::BITS as usize);

        // SAFETY: we are certainly iterating within the length of the arrays
        // and within the range of the iterator because there is a successor for sure

        let mut window = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) }
            & (usize::MAX << bits_to_clean);

        loop {
            while window == 0 {
                word_idx += 1;
                if word_idx >= self.high_bits.as_ref().len() {
                    return None;
                }
                window = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) };
            }
            // find the lowest bit set index in the word
            let bit_idx = window.trailing_zeros() as usize;
            // compute the global bit index
            let high_bits = (word_idx * usize::BITS as usize) + bit_idx - rank;
            // compose the value
            let res = (V::as_from(high_bits) << self.l) | unsafe { iter.next_unchecked() };
            if res == value {
                return Some(rank);
            }
            if res > value {
                return None;
            }

            // clear the lowest bit set
            window &= window - 1;
            rank += 1;
        }
    }
}

// Iteration

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    /// Returns a forward iterator over the values of the sequence.
    #[inline(always)]
    pub fn iter(&self) -> EliasFanoIter<'_, V, H, L> {
        EliasFanoIter::new(self)
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
    /// Returns a backward iterator over the values of the sequence, starting
    /// from the last element and going backward.
    ///
    /// This method does not require [`SelectUnchecked`] on the high bits,
    /// as it finds the last word by scanning from the end of the high-bits
    /// array.
    pub fn iter_back(&self) -> EliasFanoBackIter<'_, V, H, L> {
        let high = self.high_bits.as_ref();
        let (word_idx, window) = if high.is_empty() {
            (0, 0)
        } else {
            let mut word_idx = high.len() - 1;
            // SAFETY: word_idx < high.len() throughout the loop.
            let mut window = unsafe { *high.get_unchecked(word_idx) };
            while window == 0 && word_idx > 0 {
                word_idx -= 1;
                window = unsafe { *high.get_unchecked(word_idx) };
            }
            (word_idx, window)
        };
        EliasFanoBackIter {
            ef: self,
            index: self.n,
            word_idx,
            window,
            low_bits: self.low_bits.into_unchecked_iter_back_from(self.n),
        }
    }
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    /// Returns a forward iterator starting from position `from`.
    #[inline(always)]
    pub fn iter_from(&self, from: usize) -> EliasFanoIter<'_, V, H, L> {
        EliasFanoIter::new_from(self, from)
    }
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V> + IntoUncheckedBackIterator<Item = V>,
{
    /// Returns a backward iterator that yields elements before position `from`
    /// in decreasing order.
    ///
    /// This is equivalent to `self.iter_from(from).backward()`.
    #[inline(always)]
    pub fn iter_back_from(&self, from: usize) -> EliasFanoBackIter<'_, V, H, L> {
        self.iter_from(from).backward()
    }
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> IntoIteratorFrom for &'a EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    type IntoIterFrom = EliasFanoIter<'a, V, H, L>;

    #[inline(always)]
    fn into_iter_from(self, from: usize) -> EliasFanoIter<'a, V, H, L> {
        EliasFanoIter::new_from(self, from)
    }
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> IntoBidiIterator for &'a EliasFano<V, H, L>
{
    type Item = V;
    type IntoIterBidi = EliasFanoBidiIter<'a, V, H, L>;

    #[inline(always)]
    fn into_iter_bidi(self) -> EliasFanoBidiIter<'a, V, H, L> {
        self.into_iter_bidi_from(0)
    }
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> IntoBidiIteratorFrom for &'a EliasFano<V, H, L>
{
    type IntoIterBidiFrom = EliasFanoBidiIter<'a, V, H, L>;

    #[inline(always)]
    fn into_iter_bidi_from(self, from: usize) -> EliasFanoBidiIter<'a, V, H, L> {
        if from > self.n {
            panic!("Index out of bounds: {} > {}", from, self.n);
        }
        if self.n == 0 {
            return EliasFanoBidiIter {
                ef: self,
                index: 0,
                word_idx: 0,
                window: 0,
                index_in_word: 0,
            };
        }
        // When from == n we use select(n - 1) to find the last element's
        // word, then set index_in_word past all ones in that word.
        let bit_pos = if from == self.n {
            unsafe { self.high_bits.select_unchecked(from - 1) }
        } else {
            unsafe { self.high_bits.select_unchecked(from) }
        };
        let word_idx = bit_pos / (usize::BITS as usize);
        let window = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) };
        let index_in_word = if from == self.n {
            (window & (usize::MAX >> (usize::BITS as usize - 1 - bit_pos % usize::BITS as usize)))
                .count_ones() as usize
        } else {
            (window & (((1_usize) << (bit_pos % usize::BITS as usize)) - 1)).count_ones() as usize
        };
        EliasFanoBidiIter {
            ef: self,
            index: from,
            word_idx,
            window,
            index_in_word,
        }
    }
}

impl<'a, V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    IntoBackIterator for &'a EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
    type Item = V;
    type IntoIterBack = EliasFanoBackIter<'a, V, H, L>;

    #[inline(always)]
    fn into_iter_back(self) -> EliasFanoBackIter<'a, V, H, L> {
        self.iter_back()
    }
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> IntoBackIteratorFrom for &'a EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V> + IntoUncheckedBackIterator<Item = V>,
{
    type IntoIterBackFrom = EliasFanoBackIter<'a, V, H, L>;

    #[inline(always)]
    fn into_iter_back_from(self, from: usize) -> EliasFanoBackIter<'a, V, H, L> {
        self.iter_back_from(from + 1)
    }
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> EliasFano<V, H, L>
{
    /// Returns a bidirectional iterator positioned at the first element.
    #[inline(always)]
    pub fn iter_bidi(&self) -> EliasFanoBidiIter<'_, V, H, L> {
        self.into_iter_bidi()
    }

    /// Returns a bidirectional iterator positioned at the given index.
    #[inline(always)]
    pub fn iter_bidi_from(&self, from: usize) -> EliasFanoBidiIter<'_, V, H, L> {
        self.into_iter_bidi_from(from)
    }
}

// Succ / Pred

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectZeroUnchecked,
    L: SliceByValue<Value = V>,
> SuccUnchecked for EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    type Iter<'a>
        = EliasFanoIter<'a, V, H, L>
    where
        Self: 'a;
    type BidiIter<'a>
        = EliasFanoBidiIter<'a, V, H, L>
    where
        Self: 'a;

    unsafe fn succ_unchecked<const STRICT: bool>(
        &self,
        value: impl Borrow<Self::Input>,
    ) -> (usize, Self::Output<'_>) {
        let value = *value.borrow();
        let zeros_to_skip: usize = (value >> self.l).try_into().unwrap();
        let bit_pos = if zeros_to_skip == 0 {
            0
        } else {
            unsafe { self.high_bits.select_zero_unchecked(zeros_to_skip - 1) + 1 }
        };

        let mut rank = bit_pos - zeros_to_skip;
        let mut iter = self.low_bits.into_unchecked_iter_from(rank);
        let mut word_idx = bit_pos / (usize::BITS as usize);
        let bits_to_clean = bit_pos % (usize::BITS as usize);

        // SAFETY: we are certainly iterating within the length of the arrays
        // and within the range of the iterator because there is a successor for sure

        let mut window = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) }
            & (usize::MAX << bits_to_clean);

        loop {
            while window == 0 {
                word_idx += 1;
                debug_assert!(word_idx < self.high_bits.as_ref().len());
                window = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) };
            }
            // find the lowest bit set index in the word
            let bit_idx = window.trailing_zeros() as usize;
            // compute the global bit index
            let high_bits = (word_idx * usize::BITS as usize) + bit_idx - rank;
            // compose the value
            let res = (V::as_from(high_bits) << self.l) | unsafe { iter.next_unchecked() };

            let found = if STRICT { res > value } else { res >= value };
            if found {
                return (rank, res);
            }

            // clear the lowest bit set
            window &= window - 1;
            rank += 1;
        }
    }

    unsafe fn iter_from_succ_unchecked<const STRICT: bool>(
        &self,
        value: impl Borrow<Self::Input>,
    ) -> (usize, Self::Iter<'_>) {
        let value = *value.borrow();
        let zeros_to_skip: usize = (value >> self.l).try_into().unwrap();
        let bit_pos = if zeros_to_skip == 0 {
            0
        } else {
            unsafe { self.high_bits.select_zero_unchecked(zeros_to_skip - 1) + 1 }
        };

        let mut rank = bit_pos - zeros_to_skip;
        let mut iter = self.low_bits.into_unchecked_iter_from(rank);
        let mut word_idx = bit_pos / (usize::BITS as usize);
        let bits_to_clean = bit_pos % (usize::BITS as usize);

        let mut window = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) }
            & (usize::MAX << bits_to_clean);

        loop {
            while window == 0 {
                word_idx += 1;
                debug_assert!(word_idx < self.high_bits.as_ref().len());
                window = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) };
            }
            let bit_idx = window.trailing_zeros() as usize;
            let high_bits = (word_idx * usize::BITS as usize) + bit_idx - rank;
            let res = (V::as_from(high_bits) << self.l) | unsafe { iter.next_unchecked() };

            let found = if STRICT { res > value } else { res >= value };
            if found {
                return (
                    rank,
                    EliasFanoIter {
                        ef: self,
                        index: rank,
                        word_idx,
                        window,
                        low_bits: self.low_bits.into_unchecked_iter_from(rank),
                    },
                );
            }

            window &= window - 1;
            rank += 1;
        }
    }

    unsafe fn iter_bidi_from_succ_unchecked<const STRICT: bool>(
        &self,
        value: impl Borrow<Self::Input>,
    ) -> (usize, Self::BidiIter<'_>) {
        let value = *value.borrow();
        let zeros_to_skip: usize = (value >> self.l).try_into().unwrap();
        let bit_pos = if zeros_to_skip == 0 {
            0
        } else {
            unsafe { self.high_bits.select_zero_unchecked(zeros_to_skip - 1) + 1 }
        };

        let mut rank = bit_pos - zeros_to_skip;
        let mut word_idx = bit_pos / (usize::BITS as usize);
        let bits_to_clean = bit_pos % (usize::BITS as usize);

        let full_word = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) };
        let mut window = full_word & (usize::MAX << bits_to_clean);

        loop {
            while window == 0 {
                word_idx += 1;
                debug_assert!(word_idx < self.high_bits.as_ref().len());
                window = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) };
            }
            let bit_idx = window.trailing_zeros() as usize;
            let high_bits = (word_idx * usize::BITS as usize) + bit_idx - rank;
            let low = unsafe { self.low_bits.get_value_unchecked(rank) };
            let res = (V::as_from(high_bits) << self.l) | low;

            let found = if STRICT { res > value } else { res >= value };
            if found {
                let full_word = unsafe { *self.high_bits.as_ref().get_unchecked(word_idx) };
                let index_in_word =
                    (full_word & (((1_usize) << bit_idx) - 1)).count_ones() as usize;
                return (
                    rank,
                    EliasFanoBidiIter {
                        ef: self,
                        index: rank,
                        word_idx,
                        window: full_word,
                        index_in_word,
                    },
                );
            }

            window &= window - 1;
            rank += 1;
        }
    }
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectZeroUnchecked,
    L: SliceByValue<Value = V>,
> Succ for EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    #[inline]
    fn succ(&self, value: impl Borrow<V>) -> Option<(usize, V)> {
        if self.n == 0 || *value.borrow() > self.last_val {
            None
        } else {
            Some(unsafe { self.succ_unchecked::<false>(value) })
        }
    }

    #[inline]
    fn succ_strict(&self, value: impl Borrow<V>) -> Option<(usize, V)> {
        if *value.borrow() >= self.last_val {
            None
        } else {
            Some(unsafe { self.succ_unchecked::<true>(value) })
        }
    }

    #[inline]
    fn iter_from_succ(
        &self,
        value: impl Borrow<V>,
    ) -> Option<(usize, <Self as SuccUnchecked>::Iter<'_>)> {
        if self.n == 0 || *value.borrow() > self.last_val {
            None
        } else {
            Some(unsafe { self.iter_from_succ_unchecked::<false>(value) })
        }
    }

    #[inline]
    fn iter_from_succ_strict(
        &self,
        value: impl Borrow<V>,
    ) -> Option<(usize, <Self as SuccUnchecked>::Iter<'_>)> {
        if *value.borrow() >= self.last_val {
            None
        } else {
            Some(unsafe { self.iter_from_succ_unchecked::<true>(value) })
        }
    }

    #[inline]
    fn iter_bidi_from_succ(
        &self,
        value: impl Borrow<V>,
    ) -> Option<(usize, <Self as SuccUnchecked>::BidiIter<'_>)> {
        if self.n == 0 || *value.borrow() > self.last_val {
            None
        } else {
            Some(unsafe { self.iter_bidi_from_succ_unchecked::<false>(value) })
        }
    }

    #[inline]
    fn iter_bidi_from_succ_strict(
        &self,
        value: impl Borrow<V>,
    ) -> Option<(usize, <Self as SuccUnchecked>::BidiIter<'_>)> {
        if *value.borrow() >= self.last_val {
            None
        } else {
            Some(unsafe { self.iter_bidi_from_succ_unchecked::<true>(value) })
        }
    }
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectZeroUnchecked,
    L: SliceByValue<Value = V>,
> PredUnchecked for EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
    type BackIter<'a>
        = EliasFanoBackIter<'a, V, H, L>
    where
        Self: 'a;
    type BidiIter<'a>
        = EliasFanoBidiIter<'a, V, H, L>
    where
        Self: 'a;

    unsafe fn pred_unchecked<const STRICT: bool>(
        &self,
        value: impl Borrow<Self::Input>,
    ) -> (usize, Self::Output<'_>) {
        let value = *value.borrow();
        let zeros_to_skip: usize = (value >> self.l).try_into().unwrap();
        let mut bit_pos = unsafe { self.high_bits.select_zero_unchecked(zeros_to_skip) } - 1;

        let mut rank = bit_pos - zeros_to_skip;
        let mut iter = self.low_bits.into_unchecked_iter_back_from(rank + 1);

        // SAFETY: we are certainly iterating within the length of the arrays
        // and within the range of the iterator because there is a predecessor for sure
        unsafe {
            loop {
                let lower_bits = iter.next_unchecked();
                let mut word_idx = bit_pos / (usize::BITS as usize);
                let bit_idx = bit_pos % (usize::BITS as usize);
                if self.high_bits.as_ref().get_unchecked(word_idx) & ((1_usize) << bit_idx) == 0 {
                    let mut zeros = bit_idx;
                    let mut window =
                        *self.high_bits.as_ref().get_unchecked(word_idx) & !(usize::MAX << bit_idx);
                    while window == 0 {
                        word_idx -= 1;
                        window = *self.high_bits.as_ref().get_unchecked(word_idx);
                        zeros += usize::BITS as usize;
                    }
                    return (
                        rank,
                        (V::as_from(
                            (usize::BITS as usize) - 1 + bit_pos
                                - zeros
                                - window.leading_zeros() as usize
                                - rank,
                        ) << self.l)
                            | lower_bits,
                    );
                }

                let low_value = value & ((V::ONE << self.l) - V::ONE);
                let found = if STRICT {
                    lower_bits < low_value
                } else {
                    lower_bits <= low_value
                };
                if found {
                    return (rank, (V::as_from(bit_pos - rank) << self.l) | lower_bits);
                }

                bit_pos -= 1;
                rank -= 1;
            }
        }
    }

    unsafe fn iter_back_from_pred_unchecked<const STRICT: bool>(
        &self,
        value: impl Borrow<Self::Input>,
    ) -> (usize, Self::BackIter<'_>) {
        let value = *value.borrow();
        let zeros_to_skip: usize = (value >> self.l).try_into().unwrap();
        let mut bit_pos = unsafe { self.high_bits.select_zero_unchecked(zeros_to_skip) } - 1;

        let mut rank = bit_pos - zeros_to_skip;
        let mut iter_back = self.low_bits.into_unchecked_iter_back_from(rank + 1);

        // SAFETY: we are certainly iterating within the length of the arrays
        // and within the range of the iterator because there is a predecessor for sure
        unsafe {
            loop {
                let lower_bits = iter_back.next_unchecked();
                let mut word_idx = bit_pos / (usize::BITS as usize);
                let bit_idx = bit_pos % (usize::BITS as usize);
                if self.high_bits.as_ref().get_unchecked(word_idx) & ((1_usize) << bit_idx) == 0 {
                    // bit_pos is a zero: the predecessor must be below this
                    // position. Find the highest set bit at or below bit_pos.
                    let mut window =
                        *self.high_bits.as_ref().get_unchecked(word_idx) & !(usize::MAX << bit_idx);
                    while window == 0 {
                        word_idx -= 1;
                        window = *self.high_bits.as_ref().get_unchecked(word_idx);
                    }
                    // The window contains all bits in this word up to (but
                    // not including) bit_idx, including the predecessor's bit.
                    // The backward iterator starts at index rank + 1 so that
                    // its first next() yields the predecessor at rank.
                    return (
                        rank,
                        EliasFanoBackIter {
                            ef: self,
                            index: rank + 1,
                            word_idx,
                            window,
                            low_bits: self.low_bits.into_unchecked_iter_back_from(rank + 1),
                        },
                    );
                }

                let low_value = value & ((V::ONE << self.l) - V::ONE);
                let found = if STRICT {
                    lower_bits < low_value
                } else {
                    lower_bits <= low_value
                };
                if found {
                    // bit_pos is a one and the low bits match: predecessor
                    // is at rank. Build window with bits 0..=bit_idx.
                    let window = *self.high_bits.as_ref().get_unchecked(word_idx)
                        & (usize::MAX >> (usize::BITS as usize - 1 - bit_idx));
                    return (
                        rank,
                        EliasFanoBackIter {
                            ef: self,
                            index: rank + 1,
                            word_idx,
                            window,
                            low_bits: self.low_bits.into_unchecked_iter_back_from(rank + 1),
                        },
                    );
                }

                bit_pos -= 1;
                rank -= 1;
            }
        }
    }

    unsafe fn iter_bidi_from_pred_unchecked<const STRICT: bool>(
        &self,
        value: impl Borrow<Self::Input>,
    ) -> (usize, Self::BidiIter<'_>) {
        let value = *value.borrow();
        let zeros_to_skip: usize = (value >> self.l).try_into().unwrap();
        let mut bit_pos = unsafe { self.high_bits.select_zero_unchecked(zeros_to_skip) } - 1;

        let mut rank = bit_pos - zeros_to_skip;

        unsafe {
            loop {
                let mut word_idx = bit_pos / (usize::BITS as usize);
                let bit_idx = bit_pos % (usize::BITS as usize);
                if self.high_bits.as_ref().get_unchecked(word_idx) & ((1_usize) << bit_idx) == 0 {
                    // bit_pos is a zero: the predecessor must be below this
                    // position. Find the highest set bit at or below bit_pos.
                    let mut masked =
                        *self.high_bits.as_ref().get_unchecked(word_idx) & !(usize::MAX << bit_idx);
                    while masked == 0 {
                        word_idx -= 1;
                        masked = *self.high_bits.as_ref().get_unchecked(word_idx);
                    }
                    // The predecessor's bit is the highest set bit in masked.
                    let pred_bit = usize::BITS as usize - 1 - masked.leading_zeros() as usize;
                    let full_word = *self.high_bits.as_ref().get_unchecked(word_idx);
                    // index_in_word for cursor at rank: ones at positions < pred_bit
                    let index_in_word =
                        (full_word & (((1_usize) << pred_bit) - 1)).count_ones() as usize;
                    return (
                        rank,
                        EliasFanoBidiIter {
                            ef: self,
                            index: rank,
                            word_idx,
                            window: full_word,
                            index_in_word,
                        },
                    );
                }

                let low = self.low_bits.get_value_unchecked(rank);

                let low_value = value & ((V::ONE << self.l) - V::ONE);
                let found = if STRICT {
                    low < low_value
                } else {
                    low <= low_value
                };
                if found {
                    let full_word = *self.high_bits.as_ref().get_unchecked(word_idx);
                    let index_in_word =
                        (full_word & (((1_usize) << bit_idx) - 1)).count_ones() as usize;
                    return (
                        rank,
                        EliasFanoBidiIter {
                            ef: self,
                            index: rank,
                            word_idx,
                            window: full_word,
                            index_in_word,
                        },
                    );
                }

                bit_pos -= 1;
                rank -= 1;
            }
        }
    }
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectZeroUnchecked,
    L: SliceByValue<Value = V>,
> Pred for EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
    #[inline]
    fn pred(&self, value: impl Borrow<V>) -> Option<(usize, V)> {
        if self.n == 0 || *value.borrow() < self.first_val {
            None
        } else {
            Some(unsafe { self.pred_unchecked::<false>(value) })
        }
    }

    #[inline]
    fn pred_strict(&self, value: impl Borrow<V>) -> Option<(usize, V)> {
        if *value.borrow() <= self.first_val {
            None
        } else {
            Some(unsafe { self.pred_unchecked::<true>(value) })
        }
    }

    #[inline]
    fn iter_back_from_pred(
        &self,
        value: impl Borrow<V>,
    ) -> Option<(usize, <Self as PredUnchecked>::BackIter<'_>)> {
        if self.n == 0 || *value.borrow() < self.first_val {
            None
        } else {
            Some(unsafe { self.iter_back_from_pred_unchecked::<false>(value) })
        }
    }

    #[inline]
    fn iter_back_from_pred_strict(
        &self,
        value: impl Borrow<V>,
    ) -> Option<(usize, <Self as PredUnchecked>::BackIter<'_>)> {
        if *value.borrow() <= self.first_val {
            None
        } else {
            Some(unsafe { self.iter_back_from_pred_unchecked::<true>(value) })
        }
    }

    #[inline]
    fn iter_bidi_from_pred(
        &self,
        value: impl Borrow<V>,
    ) -> Option<(usize, <Self as PredUnchecked>::BidiIter<'_>)> {
        if self.n == 0 || *value.borrow() < self.first_val {
            None
        } else {
            Some(unsafe { self.iter_bidi_from_pred_unchecked::<false>(value) })
        }
    }

    #[inline]
    fn iter_bidi_from_pred_strict(
        &self,
        value: impl Borrow<V>,
    ) -> Option<(usize, <Self as PredUnchecked>::BidiIter<'_>)> {
        if *value.borrow() <= self.first_val {
            None
        } else {
            Some(unsafe { self.iter_bidi_from_pred_unchecked::<true>(value) })
        }
    }
}

// -----------------------------------------------------------------------------
// Value traits

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::slices::SliceByValue for EliasFano<V, H, L>
{
    type Value = V;

    fn len(&self) -> usize {
        self.n
    }
    unsafe fn get_value_unchecked(&self, index: usize) -> Self::Value {
        unsafe { <Self as IndexedSeq>::get_unchecked(self, index) }
    }
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::iter::IterateByValueGat<'a> for EliasFano<V, H, L>
where
    for<'c> &'c L: IntoUncheckedIterator<Item = V>,
{
    type Item = V;
    type Iter = EliasFanoIter<'a, V, H, L>;
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::iter::IterateByValue for EliasFano<V, H, L>
where
    for<'c> &'c L: IntoUncheckedIterator<Item = V>,
{
    fn iter_value(&self) -> <Self as value_traits::iter::IterateByValueGat<'_>>::Iter {
        self.iter_from(0)
    }
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::iter::IterateByValueFromGat<'a> for EliasFano<V, H, L>
where
    for<'c> &'c L: IntoUncheckedIterator<Item = V>,
{
    type Item = V;
    type IterFrom = EliasFanoIter<'a, V, H, L>;
}

impl<
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::iter::IterateByValueFrom for EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    fn iter_value_from(
        &self,
        from: usize,
    ) -> <Self as value_traits::iter::IterateByValueGat<'_>>::Iter {
        self.iter_from(from)
    }
}

impl<
    'a,
    'b,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::iter::IterateByValueGat<'a> for EliasFanoSubsliceImpl<'b, V, H, L>
where
    for<'c> &'c L: IntoUncheckedIterator<Item = V>,
{
    type Item = V;
    type Iter = EliasFanoIter<'a, V, H, L>;
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::iter::IterateByValue for EliasFanoSubsliceImpl<'a, V, H, L>
where
    for<'c> &'c L: IntoUncheckedIterator<Item = V>,
{
    fn iter_value(&self) -> <Self as value_traits::iter::IterateByValueGat<'_>>::Iter {
        self.slice.iter_from(0)
    }
}

impl<
    'a,
    'b,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::iter::IterateByValueFromGat<'a> for EliasFanoSubsliceImpl<'b, V, H, L>
where
    for<'c> &'c L: IntoUncheckedIterator<Item = V>,
{
    type Item = V;
    type IterFrom = EliasFanoIter<'a, V, H, L>;
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> value_traits::iter::IterateByValueFrom for EliasFanoSubsliceImpl<'a, V, H, L>
where
    for<'c> &'c L: IntoUncheckedIterator<Item = V>,
{
    fn iter_value_from(
        &self,
        from: usize,
    ) -> <Self as value_traits::iter::IterateByValueGat<'_>>::Iter {
        self.slice.iter_from(from)
    }
}

/// An iterator for [`EliasFano`].
#[derive(MemSize, MemDbg)]
pub struct EliasFanoIter<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]>,
    L: SliceByValue<Value = V>,
> where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    ef: &'a EliasFano<V, H, L>,
    /// The index of the next value that will be returned when `next` is called.
    index: usize,
    /// Index of the word loaded in the `window` field.
    word_idx: usize,
    /// Current window on the high bits.
    window: usize,
    low_bits: <&'a L as IntoUncheckedIterator>::IntoUncheckedIter,
}

impl<'a, V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    EliasFanoIter<'a, V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    pub fn new(ef: &'a EliasFano<V, H, L>) -> Self {
        let window = if ef.high_bits.as_ref().is_empty() {
            0
        } else {
            // SAFETY: the array is non-empty
            unsafe { *ef.high_bits.as_ref().get_unchecked(0) }
        };
        Self {
            ef,
            index: 0,
            word_idx: 0,
            window,
            low_bits: ef.low_bits.into_unchecked_iter(),
        }
    }
}

impl<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]> + SelectUnchecked,
    L: SliceByValue<Value = V>,
> EliasFanoIter<'a, V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    pub fn new_from(ef: &'a EliasFano<V, H, L>, start_index: usize) -> Self {
        if start_index > ef.len() {
            panic!("Index out of bounds: {} > {}", start_index, ef.len());
        }
        if start_index == ef.len() {
            return Self {
                ef,
                index: start_index,
                word_idx: 0,
                window: 0,
                low_bits: ef.low_bits.into_unchecked_iter_from(start_index),
            };
        }
        // SAFETY: start_index < ef.len(), so it's a valid rank
        let bit_pos = unsafe { ef.high_bits.select_unchecked(start_index) };
        let word_idx = bit_pos / (usize::BITS as usize);
        let bits_to_clean = bit_pos % (usize::BITS as usize);

        let window = if ef.high_bits.as_ref().is_empty() {
            0
        } else {
            // SAFETY: word_idx derives from select_unchecked, which
            // returns a valid bit position
            let word = unsafe { *ef.high_bits.as_ref().get_unchecked(word_idx) };
            // clean off the bits that we don't care about
            word & (usize::MAX << bits_to_clean)
        };

        Self {
            ef,
            index: start_index,
            word_idx,
            window,
            low_bits: ef.low_bits.into_unchecked_iter_from(start_index),
        }
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    UncheckedIterator for EliasFanoIter<'_, V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    type Item = V;

    #[inline(always)]
    unsafe fn next_unchecked(&mut self) -> V {
        // find the next word with ones
        while self.window == 0 {
            self.word_idx += 1;
            debug_assert!(self.word_idx < self.ef.high_bits.as_ref().len());
            self.window = unsafe { *self.ef.high_bits.as_ref().get_unchecked(self.word_idx) };
        }
        // find the lowest bit set index in the word
        let bit_idx = self.window.trailing_zeros() as usize;
        // compute the global bit index
        let high_bits = (self.word_idx * usize::BITS as usize) + bit_idx - self.index;
        // clear the lowest bit set
        self.window &= self.window - 1;
        // compose the value
        let res = V::as_from(high_bits) << self.ef.l | unsafe { self.low_bits.next_unchecked() };
        self.index += 1;
        res
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>> Iterator
    for EliasFanoIter<'_, V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    type Item = V;

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        if self.index >= self.ef.len() {
            return None;
        }
        Some(unsafe { self.next_unchecked() })
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len(), Some(self.len()))
    }

    #[inline(always)]
    fn count(self) -> usize {
        self.ef.len() - self.index
    }

    #[inline(always)]
    fn last(self) -> Option<Self::Item> {
        if self.index >= self.ef.n {
            return None;
        }
        let words = self.ef.high_bits.as_ref();
        let mut word_idx = words.len() - 1;
        // SAFETY: n > 0 implies the high bits contain at least one set bit
        while unsafe { *words.get_unchecked(word_idx) } == 0 {
            debug_assert!(word_idx > 0);
            word_idx -= 1;
        }
        let word = unsafe { *words.get_unchecked(word_idx) };
        let bit_idx = usize::BITS as usize - 1 - word.leading_zeros() as usize;
        let high_bits = (word_idx * usize::BITS as usize) + bit_idx - (self.ef.n - 1);
        let low = unsafe { self.ef.low_bits.get_value_unchecked(self.ef.n - 1) };
        Some(V::as_from(high_bits) << self.ef.l | low)
    }

    #[inline(always)]
    fn fold<B, F>(mut self, init: B, mut f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    {
        let mut accum = init;
        let n = self.ef.len();
        while self.index < n {
            // SAFETY: self.index < n guarantees there is a next element
            accum = f(accum, unsafe { self.next_unchecked() });
        }
        accum
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    ExactSizeIterator for EliasFanoIter<'_, V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    #[inline(always)]
    fn len(&self) -> usize {
        self.ef.len() - self.index
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    FusedIterator for EliasFanoIter<'_, V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
}

impl<'a, V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    EliasFanoIter<'a, V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V> + IntoUncheckedBackIterator<Item = V>,
{
    /// Converts this forward iterator into a backward iterator at the current
    /// cursor position.
    ///
    /// The backward iterator will yield elements before the current position
    /// in decreasing order. The high-bits window is converted using XOR with
    /// the original word, and the low-bits backward iterator is created from
    /// the current index.
    pub fn backward(self) -> EliasFanoBackIter<'a, V, H, L> {
        // When the forward iterator is exhausted (index >= n), the
        // word_idx/window state may not reflect the actual end position
        // (e.g., when created via new_from(ef, n)). We delegate to
        // iter_back() which correctly scans from the end.
        // This also handles the n == 0 case, since 0 >= 0.
        if self.index >= self.ef.n {
            return self.ef.iter_back();
        }
        let original = unsafe { *self.ef.high_bits.as_ref().get_unchecked(self.word_idx) };
        EliasFanoBackIter {
            ef: self.ef,
            index: self.index,
            word_idx: self.word_idx,
            window: self.window ^ original,
            low_bits: self.ef.low_bits.into_unchecked_iter_back_from(self.index),
        }
    }
}

/// A backward iterator for [`EliasFano`].
///
/// Instead of scanning bits from right to left (using [`trailing_zeros`]), it
/// scans from left to right (using [`leading_zeros`]), and accesses low bits
/// through a backward unchecked iterator.
///
/// This iterator is slightly slower than a [forward iterator].
///
/// [forward iterator]: EliasFanoIter
/// [`leading_zeros`]: usize::leading_zeros
/// [`trailing_zeros`]: usize::trailing_zeros
#[derive(MemSize, MemDbg)]
pub struct EliasFanoBackIter<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]>,
    L: SliceByValue<Value = V>,
> where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
    ef: &'a EliasFano<V, H, L>,
    /// The index of the next value that will be returned when `next` is
    /// called, plus one; that is, `next` will return the value at position
    /// `index - 1` and then decrement `index`.
    index: usize,
    /// Index of the word loaded in the `window` field.
    word_idx: usize,
    /// Current window on the high bits.
    window: usize,
    low_bits: <&'a L as IntoUncheckedBackIterator>::IntoUncheckedIterBack,
}

impl<'a, V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    EliasFanoBackIter<'a, V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V> + IntoUncheckedBackIterator<Item = V>,
{
    /// Converts this backward iterator back into a forward iterator at the
    /// current cursor position.
    ///
    /// The forward iterator will yield elements from the current position
    /// onward in increasing order. The high-bits window is converted using
    /// XOR with the original word, and the low-bits forward iterator is
    /// created from the current index.
    pub fn forward(self) -> EliasFanoIter<'a, V, H, L> {
        let window = if self.ef.high_bits.as_ref().is_empty() {
            self.window
        } else {
            self.window ^ unsafe { *self.ef.high_bits.as_ref().get_unchecked(self.word_idx) }
        };
        EliasFanoIter {
            ef: self.ef,
            index: self.index,
            word_idx: self.word_idx,
            window,
            low_bits: self.ef.low_bits.into_unchecked_iter_from(self.index),
        }
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    UncheckedIterator for EliasFanoBackIter<'_, V, H, L>
where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
    type Item = V;

    #[inline(always)]
    unsafe fn next_unchecked(&mut self) -> V {
        while self.window == 0 {
            self.word_idx -= 1;
            self.window = unsafe { *self.ef.high_bits.as_ref().get_unchecked(self.word_idx) };
        }
        let bit_idx = usize::BITS as usize - 1 - self.window.leading_zeros() as usize;
        self.window ^= (1_usize) << bit_idx;
        self.index -= 1;
        let high_bits = (self.word_idx * usize::BITS as usize) + bit_idx - self.index;
        let low = unsafe { self.low_bits.next_unchecked() };
        V::as_from(high_bits) << self.ef.l | low
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>> Iterator
    for EliasFanoBackIter<'_, V, H, L>
where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
    type Item = V;

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        if self.index == 0 {
            return None;
        }
        Some(unsafe { self.next_unchecked() })
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len(), Some(self.len()))
    }

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

    #[inline(always)]
    fn last(self) -> Option<Self::Item> {
        if self.index == 0 {
            return None;
        }
        let words = self.ef.high_bits.as_ref();
        let mut word_idx = 0;
        // SAFETY: index > 0 implies the high bits contain at least one set bit
        while unsafe { *words.get_unchecked(word_idx) } == 0 {
            debug_assert!(word_idx + 1 < words.len());
            word_idx += 1;
        }
        let bit_idx = unsafe { *words.get_unchecked(word_idx) }.trailing_zeros() as usize;
        let high_bits = (word_idx * usize::BITS as usize) + bit_idx;
        let low = unsafe { self.ef.low_bits.get_value_unchecked(0) };
        Some(V::as_from(high_bits) << self.ef.l | low)
    }

    #[inline(always)]
    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.index > 0 {
            // SAFETY: self.index > 0 guarantees there is a previous element
            accum = f(accum, unsafe { self.next_unchecked() });
        }
        accum
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    ExactSizeIterator for EliasFanoBackIter<'_, V, H, L>
where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
    #[inline(always)]
    fn len(&self) -> usize {
        self.index
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    FusedIterator for EliasFanoBackIter<'_, V, H, L>
where
    for<'b> &'b L: IntoUncheckedBackIterator<Item = V>,
{
}

impl<'a, V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    IntoIterator for &'a EliasFano<V, H, L>
where
    for<'b> &'b L: IntoUncheckedIterator<Item = V>,
{
    type Item = V;
    type IntoIter = EliasFanoIter<'a, V, H, L>;

    #[inline(always)]
    fn into_iter(self) -> Self::IntoIter {
        EliasFanoIter::new(self)
    }
}

/// A bidirectional iterator (cursor) for [`EliasFano`].
///
/// Unlike [`EliasFanoIter`] and [`EliasFanoBackIter`], this cursor does not
/// clear bits from the current word. Instead, it uses [`select_in_word`] to
/// find the relevant bit on each call to [`next`] or [`prev`]. Low bits are
/// accessed via random access ([`get_value_unchecked`]).
///
/// The cursor position `index` ranges from 0 to *n*. Calling `next()` yields
/// element `index` and increments the cursor; calling `prev()` yields element
/// `index - 1` and decrements it.
///
/// This iterator is slightly slower than a [backward iterator], but much faster
/// than using selection.
///
/// [backward iterator]: EliasFanoBackIter
/// [`get_value_unchecked`]: SliceByValue::get_value_unchecked
/// [`prev`]: BidiIterator::prev
/// [`next`]: Iterator::next
/// [`select_in_word`]: SelectInWord::select_in_word
#[derive(Debug, Clone, MemSize, MemDbg)]
pub struct EliasFanoBidiIter<
    'a,
    V: Word + PrimitiveNumberAs<usize>,
    H: AsRef<[usize]>,
    L: SliceByValue<Value = V>,
> {
    ef: &'a EliasFano<V, H, L>,
    /// Cursor position: `next()` yields element `index`, `prev()` yields
    /// element `index - 1`.
    index: usize,
    /// Index of the word loaded in `window`.
    word_idx: usize,
    /// The full, unmodified word from `high_bits[word_idx]`.
    window: usize,
    /// Rank of the cursor within the current word: the number of ones in
    /// `window` that correspond to elements at positions < `index`.
    index_in_word: usize,
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>> Iterator
    for EliasFanoBidiIter<'_, V, H, L>
{
    type Item = V;

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        if self.index >= self.ef.n {
            return None;
        }
        // Advance to the next word if we've exhausted the ones in this word.
        while self.index_in_word >= self.window.count_ones() as usize {
            self.index_in_word -= self.window.count_ones() as usize;
            self.word_idx += 1;
            self.window = unsafe { *self.ef.high_bits.as_ref().get_unchecked(self.word_idx) };
        }
        let bit_idx = self.window.select_in_word(self.index_in_word);
        let high_bits = (self.word_idx * usize::BITS as usize) + bit_idx - self.index;
        let low = unsafe { self.ef.low_bits.get_value_unchecked(self.index) };
        self.index += 1;
        self.index_in_word += 1;
        Some((V::as_from(high_bits) << self.ef.l) | low)
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.ef.n - self.index;
        (remaining, Some(remaining))
    }

    #[inline(always)]
    fn count(self) -> usize {
        self.ef.n - self.index
    }

    #[inline(always)]
    fn last(self) -> Option<Self::Item> {
        if self.index >= self.ef.n {
            return None;
        }
        let words = self.ef.high_bits.as_ref();
        let mut word_idx = words.len() - 1;
        // SAFETY: n > 0 implies the high bits contain at least one set bit
        while unsafe { *words.get_unchecked(word_idx) } == 0 {
            debug_assert!(word_idx > 0);
            word_idx -= 1;
        }
        let word = unsafe { *words.get_unchecked(word_idx) };
        let bit_idx = usize::BITS as usize - 1 - word.leading_zeros() as usize;
        let high_bits = (word_idx * usize::BITS as usize) + bit_idx - (self.ef.n - 1);
        let low = unsafe { self.ef.low_bits.get_value_unchecked(self.ef.n - 1) };
        Some((V::as_from(high_bits) << self.ef.l) | low)
    }

    #[inline(always)]
    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.index < self.ef.n {
            while self.index_in_word >= self.window.count_ones() as usize {
                self.index_in_word -= self.window.count_ones() as usize;
                self.word_idx += 1;
                self.window = unsafe { *self.ef.high_bits.as_ref().get_unchecked(self.word_idx) };
            }
            let bit_idx = self.window.select_in_word(self.index_in_word);
            let high_bits = (self.word_idx * usize::BITS as usize) + bit_idx - self.index;
            let low = unsafe { self.ef.low_bits.get_value_unchecked(self.index) };
            self.index += 1;
            self.index_in_word += 1;
            accum = f(accum, (V::as_from(high_bits) << self.ef.l) | low);
        }
        accum
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    ExactSizeIterator for EliasFanoBidiIter<'_, V, H, L>
{
    #[inline(always)]
    fn len(&self) -> usize {
        self.ef.n - self.index
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    FusedIterator for EliasFanoBidiIter<'_, V, H, L>
{
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>> BidiIterator
    for EliasFanoBidiIter<'_, V, H, L>
{
    type SwappedIter = SwappedIter<Self>;

    #[inline(always)]
    fn swap(self) -> SwappedIter<Self> {
        SwappedIter(self)
    }

    #[inline(always)]
    fn prev(&mut self) -> Option<V> {
        if self.index == 0 {
            return None;
        }
        // Move to the previous word if we're at the start of this word.
        while self.index_in_word == 0 {
            self.word_idx -= 1;
            self.window = unsafe { *self.ef.high_bits.as_ref().get_unchecked(self.word_idx) };
            self.index_in_word = self.window.count_ones() as usize;
        }
        self.index -= 1;
        self.index_in_word -= 1;
        let bit_idx = self.window.select_in_word(self.index_in_word);
        let high_bits = (self.word_idx * usize::BITS as usize) + bit_idx - self.index;
        let low = unsafe { self.ef.low_bits.get_value_unchecked(self.index) };
        Some((V::as_from(high_bits) << self.ef.l) | low)
    }

    #[inline(always)]
    fn prev_size_hint(&self) -> (usize, Option<usize>) {
        (self.index, Some(self.index))
    }

    #[inline(always)]
    fn prev_count(self) -> usize {
        self.index
    }

    #[inline(always)]
    fn prev_last(self) -> Option<V> {
        if self.index == 0 {
            return None;
        }
        let words = self.ef.high_bits.as_ref();
        let mut word_idx = 0;
        // SAFETY: index > 0 implies the high bits contain at least one set bit
        while unsafe { *words.get_unchecked(word_idx) } == 0 {
            debug_assert!(word_idx + 1 < words.len());
            word_idx += 1;
        }
        let bit_idx = unsafe { *words.get_unchecked(word_idx) }.trailing_zeros() as usize;
        let high_bits = (word_idx * usize::BITS as usize) + bit_idx;
        let low = unsafe { self.ef.low_bits.get_value_unchecked(0) };
        Some((V::as_from(high_bits) << self.ef.l) | low)
    }

    #[inline(always)]
    fn prev_fold<B, F>(mut self, init: B, mut f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    {
        let mut accum = init;
        while self.index > 0 {
            while self.index_in_word == 0 {
                self.word_idx -= 1;
                self.window = unsafe { *self.ef.high_bits.as_ref().get_unchecked(self.word_idx) };
                self.index_in_word = self.window.count_ones() as usize;
            }
            self.index -= 1;
            self.index_in_word -= 1;
            let bit_idx = self.window.select_in_word(self.index_in_word);
            let high_bits = (self.word_idx * usize::BITS as usize) + bit_idx - self.index;
            let low = unsafe { self.ef.low_bits.get_value_unchecked(self.index) };
            accum = f(accum, (V::as_from(high_bits) << self.ef.l) | low);
        }
        accum
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    ExactSizeBidiIterator for EliasFanoBidiIter<'_, V, H, L>
{
    #[inline(always)]
    fn prev_len(&self) -> usize {
        self.index
    }
}

impl<V: Word + PrimitiveNumberAs<usize>, H: AsRef<[usize]>, L: SliceByValue<Value = V>>
    FusedBidiIterator for EliasFanoBidiIter<'_, V, H, L>
{
}

/// Convenience constructor that iterates over a slice.
///
/// Note that this implementation requires a first scan to check monotonicity
/// and find the maximum value, but then it uses
/// [`EliasFanoBuilder::push_unchecked`], thus partially compensating for the
/// cost of the first scan.
impl<V: Word + PrimitiveNumberAs<usize>, A: AsRef<[V]>> From<A>
    for EliasFano<V, BitVec<Box<[usize]>>, BitFieldVec<Box<[V]>>>
{
    fn from(values: A) -> Self {
        let values = values.as_ref();
        let mut max = V::ZERO;
        let mut prev = V::ZERO;
        for &value in values {
            if value < prev {
                panic!("The values provided are not monotone");
            }
            max = max.max(value);
            prev = value;
        }
        let mut builder = EliasFanoBuilder::<V>::new(values.len(), max);
        for &value in values {
            // SAFETY: pre-scan checked monotonicity and max
            unsafe {
                builder.push_unchecked(value);
            }
        }
        builder.build()
    }
}

/// A sequential builder for [`EliasFano`].
///
/// After creating an instance, you can use [`EliasFanoBuilder::push`] to add
/// new values, and then call [`EliasFanoBuilder::build`] to create the
/// [`EliasFano`] instance.
///
/// # Examples
///
/// ```rust
/// # use sux::dict::EliasFanoBuilder;
/// let mut efb = EliasFanoBuilder::new(4, 10u64);
///
/// efb.push(0);
/// efb.push(2);
/// efb.push(8);
/// efb.push(10);
///
/// let ef = efb.build();
/// let mut iter = ef.iter();
/// assert_eq!(iter.next(), Some(0u64));
/// assert_eq!(iter.next(), Some(2u64));
/// assert_eq!(iter.next(), Some(8u64));
/// assert_eq!(iter.next(), Some(10u64));
/// assert_eq!(iter.next(), None);
/// ```
#[derive(Debug, Clone, MemSize, MemDbg)]
pub struct EliasFanoBuilder<V: Word = usize> {
    n: usize,
    u: V,
    l: usize,
    low_bits: BitFieldVec<Vec<V>>,
    high_bits: BitVec,
    first_val: V,
    last_val: V,
    count: usize,
}

impl<V: Word + PrimitiveNumberAs<u128>> EliasFanoBuilder<V> {
    /// Creates a builder for an [`EliasFano`] containing
    /// `n` numbers smaller than or equal to `u`.
    ///
    /// # Panics
    ///
    /// When any of the underlying structures would exceed `usize` in length.
    #[must_use]
    pub fn new(n: usize, u: V) -> Self {
        let n_u128 = n as u128;
        let u_u128: u128 = u.as_to();
        let l = if n_u128 > 0 && u_u128 >= n_u128 {
            // This is equal to ⌊log₂(u / n)⌋
            (u_u128 / n_u128).ilog2() as usize
        } else {
            0
        };

        let u_high: usize = (u >> l).try_into().unwrap_or(usize::MAX);
        let num_high_bits = n
            .checked_add(1)
            .unwrap_or_else(|| panic!("n ({n}) is too large"))
            .checked_add(u_high)
            .unwrap_or_else(|| panic!("n ({n}) and/or u {u} is too large"));
        Self {
            n,
            u,
            l,
            low_bits: BitFieldVec::<Vec<V>>::new(l, n),
            high_bits: BitVec::new(num_high_bits),
            first_val: V::MAX,
            last_val: V::MIN,
            count: 0,
        }
    }
    /// Adds a new value to the builder.
    ///
    /// # Panics
    /// May panic if the value is smaller than the last provided
    /// value, or if too many values are provided.
    pub fn push(&mut self, value: V) {
        if self.count == self.n {
            panic!("Too many values");
        }
        if value > self.u {
            panic!("Value too large");
        }
        if value < self.last_val {
            panic!("The values provided are not monotone");
        }
        unsafe {
            self.push_unchecked(value);
        }
    }

    /// # Safety
    ///
    /// Values passed to this function must be smaller than or equal to `u` and must be monotone.
    /// Moreover, the function should not be called more than `n` times.
    pub unsafe fn push_unchecked(&mut self, value: V) {
        let low = value & ((V::ONE << self.l) - V::ONE);
        self.low_bits.set_value(self.count, low);

        let high: usize = (value >> self.l).try_into().unwrap_or(usize::MAX);
        let high = high + self.count;
        self.high_bits.set(high, true);

        if self.count == 0 {
            self.first_val = value;
        }
        self.count += 1;
        self.last_val = value;
    }

    /// Returns the number of values added so far.
    pub fn count(&self) -> usize {
        self.count
    }

    /// Builds an Elias–Fano structure.
    ///
    /// The resulting structure has no selection structure attached. To use it
    /// properly, you need to call [`EliasFano::map_high_bits`] to add to the
    /// high bits a selection structure.
    ///
    /// Usually, however, the default implementations returned by the
    /// [`build_with_seq`], [`build_with_dict`], and [`build_with_seq_and_dict`]
    /// methods are more convenient.
    ///
    /// [`build_with_seq_and_dict`]: EliasFanoBuilder::build_with_seq_and_dict
    /// [`build_with_dict`]: EliasFanoBuilder::build_with_dict
    /// [`build_with_seq`]: EliasFanoBuilder::build_with_seq
    #[must_use]
    pub fn build(self) -> EliasFano<V> {
        assert!(
            self.count == self.n,
            "The declared size ({}) is not equal to the number of values ({})",
            self.n,
            self.count
        );
        let high_bits: BitVec<Box<[usize]>> = self.high_bits.into();
        EliasFano {
            n: self.n,
            u: self.u,
            l: self.l,
            first_val: self.first_val,
            last_val: self.last_val,
            low_bits: self.low_bits.into(),
            // SAFETY: n is the number of ones in the high_bits
            high_bits,
        }
    }
}

impl<V: Word + PrimitiveNumberAs<usize>> EliasFanoBuilder<V> {
    /// Builds an Elias–Fano structure with constant-time access, using
    /// default values.
    ///
    /// The resulting structure implements [`IndexedSeq`], but not
    /// [`IndexedDict`], [`Succ`], or [`Pred`].
    #[must_use]
    pub fn build_with_seq(self) -> EfSeq<V> {
        let ef = self.build();
        unsafe { ef.map_high_bits(SelectAdaptConst::<_, _, 12, 3>::new) }
    }

    /// Builds an Elias–Fano structure with constant-time successor and
    /// predecessor, using default values.
    ///
    /// The resulting structure implements [`IndexedDict`], [`Succ`], and
    /// [`Pred`], but not [`IndexedSeq`].
    #[must_use]
    pub fn build_with_dict(self) -> EfDict<V> {
        let ef = self.build();
        unsafe { ef.map_high_bits(SelectZeroAdaptConst::<_, _, 12, 3>::new) }
    }

    /// Builds an Elias–Fano structure with constant-time access, successor,
    /// and predecessor, using default values.
    ///
    /// The resulting structure implements [`IndexedDict`], [`Succ`],
    /// [`Pred`], and [`IndexedSeq`].
    #[must_use]
    pub fn build_with_seq_and_dict(self) -> EfSeqDict<V> {
        let ef = self.build();
        unsafe {
            ef.map_high_bits(SelectAdaptConst::<_, _, 12, 3>::new)
                .map_high_bits(SelectZeroAdaptConst::<_, _, 12, 3>::new)
        }
    }
}

impl<V: Word + PrimitiveNumberAs<usize>> Extend<V> for EliasFanoBuilder<V> {
    fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
        for value in iter {
            self.push(value);
        }
    }
}

/// A concurrent builder for [`EliasFano`].
///
/// After creating an instance, you can use [`EliasFanoConcurrentBuilder::set`]
/// to set the values concurrently. However, this operation is inherently
/// unsafe as no check is performed on the provided data (e.g., duplicate
/// indices and lack of monotonicity are not detected).
///
/// # Examples
///
/// ```rust
/// # use sux::dict::EliasFanoConcurrentBuilder;
/// let mut efcb = EliasFanoConcurrentBuilder::new(4, 10u64);
/// std::thread::scope(|s| {
///     s.spawn(|| { unsafe { efcb.set(0, 0); } });
///     s.spawn(|| { unsafe { efcb.set(1, 2); } });
///     s.spawn(|| { unsafe { efcb.set(2, 8); } });
///     s.spawn(|| { unsafe { efcb.set(3, 10); } });
/// });
///
/// let ef = efcb.build();
/// let mut iter = ef.iter();
/// assert_eq!(iter.next(), Some(0u64));
/// assert_eq!(iter.next(), Some(2u64));
/// assert_eq!(iter.next(), Some(8u64));
/// assert_eq!(iter.next(), Some(10u64));
/// assert_eq!(iter.next(), None);
/// ```

#[derive(MemSize, MemDbg)]
pub struct EliasFanoConcurrentBuilder<V: Word + AtomicPrimitive>
where
    Atomic<V>: PrimitiveAtomicUnsigned,
{
    n: usize,
    u: V,
    l: usize,
    low_bits: AtomicBitFieldVec<Vec<Atomic<V>>>,
    high_bits: AtomicBitVec,
}

impl<V: Word + AtomicPrimitive + PrimitiveNumberAs<u128>> EliasFanoConcurrentBuilder<V>
where
    Atomic<V>: PrimitiveAtomicUnsigned,
{
    /// Creates a concurrent builder for a sequence containing `n` numbers
    /// smaller than or equal to `u`.
    #[must_use]
    pub fn new(n: usize, u: V) -> Self {
        let n_u128 = n as u128;
        let u_u128: u128 = u.as_to();
        let l = if n_u128 > 0 && u_u128 >= n_u128 {
            // This is equal to ⌊log₂(u / n)⌋
            (u_u128 / n_u128).ilog2() as usize
        } else {
            0
        };

        let u_high: usize = (u >> l).try_into().unwrap_or(usize::MAX);
        let num_high_bits = n
            .checked_add(1)
            .unwrap_or_else(|| panic!("n ({n}) is too large"))
            .checked_add(u_high)
            .unwrap_or_else(|| panic!("n ({n}) and/or u ({u}) is too large"));

        Self {
            n,
            u,
            l,
            low_bits: AtomicBitFieldVec::<Vec<Atomic<V>>>::new(l, n),
            high_bits: AtomicBitVec::new(num_high_bits),
        }
    }

    /// Sets a value concurrently.
    ///
    /// # Safety
    /// - All indices must be distinct.
    /// - All values must be smaller than or equal to `u`.
    /// - All indices must be smaller than `n`.
    /// - You must call this function exactly `n` times.
    pub unsafe fn set(&self, index: usize, value: V)
    where
        V: PrimitiveNumberAs<usize>,
    {
        let low = value & ((V::ONE << self.l) - V::ONE);
        // Note that the concurrency guarantees of BitFieldVec
        // are sufficient for us.
        unsafe {
            self.low_bits
                .set_atomic_unchecked(index, low, Ordering::Relaxed)
        };

        let high = (value >> self.l).as_to::<usize>() + index;
        self.high_bits.set(high, true, Ordering::Relaxed);
    }

    /// Builds an Elias–Fano structure.
    ///
    /// The resulting structure has no selection structure attached. To use it
    /// properly, you need to call [`EliasFano::map_high_bits`] to add to the
    /// high bits a selection structure.
    ///
    /// Usually, however, the default implementations returned by the
    /// [`build_with_seq`], [`build_with_dict`], and [`build_with_seq_and_dict`]
    /// methods are more convenient.
    ///
    /// [`build_with_seq_and_dict`]: EliasFanoConcurrentBuilder::build_with_seq_and_dict
    /// [`build_with_dict`]: EliasFanoConcurrentBuilder::build_with_dict
    /// [`build_with_seq`]: EliasFanoConcurrentBuilder::build_with_seq
    #[must_use]
    pub fn build(self) -> EliasFano<V> {
        let high_bits: BitVec<Box<[usize]>> = self.high_bits.into();
        let low_bits: BitFieldVec<Vec<V>> = self.low_bits.into();
        let low_bits: BitFieldVec<Box<[V]>> = low_bits.into();

        let (first_val, last_val) = if self.n == 0 {
            (V::MAX, V::MIN)
        } else {
            let words = high_bits.as_ref();

            // First 1-bit position → high part of first value.
            let mut w = 0;
            while unsafe { *words.get_unchecked(w) } == 0 {
                w += 1;
            }
            let first_high = w * usize::BITS as usize
                + unsafe { *words.get_unchecked(w) }.trailing_zeros() as usize;
            let first_low = unsafe { low_bits.get_value_unchecked(0) };
            let first = (V::as_from(first_high) << self.l) | first_low;

            // Last 1-bit position → high part of last value.
            let mut w = words.len() - 1;
            while unsafe { *words.get_unchecked(w) } == 0 {
                w -= 1;
            }
            let last_high = w * usize::BITS as usize + usize::BITS as usize
                - 1
                - unsafe { *words.get_unchecked(w) }.leading_zeros() as usize
                - (self.n - 1);
            let last_low = unsafe { low_bits.get_value_unchecked(self.n - 1) };
            let last = (V::as_from(last_high) << self.l) | last_low;

            (first, last)
        };

        EliasFano {
            n: self.n,
            u: self.u,
            l: self.l,
            first_val,
            last_val,
            low_bits,
            high_bits,
        }
    }

    /// Builds an Elias–Fano structure with constant-time access, using
    /// default values.
    ///
    /// The resulting structure implements [`IndexedSeq`], but not [`IndexedDict`],
    /// [`Succ`], or [`Pred`].
    #[must_use]
    pub fn build_with_seq(self) -> EfSeq<V> {
        let ef = self.build();
        unsafe { ef.map_high_bits(SelectAdaptConst::<_, _, 12, 3>::new) }
    }

    /// Builds an Elias–Fano structure with constant-time successor and
    /// predecessor, using default values.
    ///
    /// The resulting structure implements [`IndexedDict`], [`Succ`],
    /// and [`Pred`], but not [`IndexedSeq`].
    #[must_use]
    pub fn build_with_dict(self) -> EfDict<V> {
        let ef = self.build();
        unsafe { ef.map_high_bits(SelectZeroAdaptConst::<_, _, 12, 3>::new) }
    }

    /// Builds an Elias–Fano structure with constant-time access, successor,
    /// and predecessor, using default values.
    ///
    /// The resulting structure implements [`IndexedDict`], [`Succ`],
    /// [`Pred`], and [`IndexedSeq`].
    #[must_use]
    pub fn build_with_seq_and_dict(self) -> EfSeqDict<V> {
        let ef = self.build();
        unsafe {
            ef.map_high_bits(SelectAdaptConst::<_, _, 12, 3>::new)
                .map_high_bits(SelectZeroAdaptConst::<_, _, 12, 3>::new)
        }
    }
}

// ── Aligned ↔ Unaligned conversion ──────────────────────────────────

use crate::traits::Unaligned;

impl<V: Word, H> TryIntoUnaligned for EliasFano<V, H, BitFieldVec<Box<[V]>>> {
    type Unaligned = EliasFano<V, H, Unaligned<BitFieldVec<Box<[V]>>>>;
    fn try_into_unaligned(
        self,
    ) -> Result<Self::Unaligned, crate::traits::UnalignedConversionError> {
        Ok(EliasFano {
            n: self.n,
            u: self.u,
            l: self.l,
            first_val: self.first_val,
            last_val: self.last_val,
            low_bits: self.low_bits.try_into_unaligned()?,
            high_bits: self.high_bits,
        })
    }
}

impl<V: Word, H> From<Unaligned<EliasFano<V, H, BitFieldVec<Box<[V]>>>>>
    for EliasFano<V, H, BitFieldVec<Box<[V]>>>
{
    fn from(ef: Unaligned<EliasFano<V, H, BitFieldVec<Box<[V]>>>>) -> Self {
        EliasFano {
            n: ef.n,
            u: ef.u,
            l: ef.l,
            first_val: ef.first_val,
            last_val: ef.last_val,
            low_bits: ef.low_bits.into(),
            high_bits: ef.high_bits,
        }
    }
}