compressed_intvec/fixed/
mod.rs

1//! A generic, compressed, and randomly accessible vector with fixed-width encoding.
2//!
3//! This module provides [`FixedVec`] and its thread-safe counterpart, [`AtomicFixedVec`],
4//! two data structures for storing sequences of integers where each element is encoded
5//! using the same number of bits. This strategy, known as fixed-width encoding,
6//! is suitable for data where values are bounded within a known range, as it
7//! allows for O(1) random access by directly calculating the memory location of any element.
8//!
9//! # Core Concepts
10//!
11//! The design is generic over four parameters: `FixedVec<T, W, E, B>`.
12//! - `T`: The element type as seen by the user (e.g., [`u32`], [`i16`]), constrained by the [`Storable`] trait.
13//! - `W`: The underlying unsigned integer type used for storage (e.g., [`u64`], [`usize`]), constrained by the [`Word`] trait.
14//! - `E`: The [`Endianness`] (e.g., [`LE`] or [`BE`]) for bit-level operations.
15//! - `B`: The backing buffer, which abstracts over ownership. This allows [`FixedVec`] to be an owned container (e.g., `Vec<W>`) or a zero-copy, borrowed view (e.g., `&[W]`).
16//!
17//! ### Immutability and Zero-Copy Views
18//! Immutable access is performed in O(1) time by calculating an element's bit-level offset.
19//! Structures like [`FixedVecSlice`](slice::FixedVecSlice) provide zero-copy views into a vector, representing
20//! a sub-region of the data without requiring data duplication or new allocations.
21//!
22//! ### Mutability via Proxy Objects
23//! Direct mutable references (`&mut T`) to individual bit-packed elements are not possible, as
24//! elements do not align with byte boundaries and may not even exist as discrete entities in memory.
25//! Instead, mutability is managed through the proxy object pattern. Methods like [`at_mut`](FixedVec::at_mut) return a temporary proxy ([`MutProxy`]) that holds a decoded copy of the value.
26//! Modifications are applied to this copy, and the value is automatically encoded and written
27//! back into the vector's bitstream when the proxy object goes out of scope (i.e., is dropped).
28//!
29//! # Core Data Structures
30//!
31//! - [`FixedVec`]: The primary implementation for single-threaded contexts.
32//! - [`AtomicFixedVec`]: A thread-safe variant for concurrent applications. It provides an
33//!   API analogous to Rust's standard atomic types ([`load`](AtomicFixedVec::load), [`store`](AtomicFixedVec::store), [`fetch_add`](AtomicFixedVec::fetch_add), etc.).
34//!   It uses lock-free atomic instructions for elements contained within a single machine word and
35//!   a fine-grained locking strategy (lock striping) for elements that span word boundaries. This
36//!   hybrid approach ensures thread safety for any `bit-width` configuration.
37//!
38//! # Main Components
39//!
40//! - [`FixedVec`] and [`AtomicFixedVec`]
41//! - [`BitWidth`]: An enum to control the bit-width selection strategy. Options include:
42//!     - [`BitWidth::Minimal`]: Selects the minimal bit-width required.
43//!     - [`BitWidth::PowerOfTwo`]: Rounds up to the nearest power of two.
44//!     - [`BitWidth::Explicit`]: Allows specifying a fixed bit-width.
45//! - **Builders**: [`FixedVecBuilder`](builder::FixedVecBuilder) and [`FixedVecFromIterBuilder`](builder::FixedVecFromIterBuilder)
46//! - **Slices**: [`FixedVecSlice`](slice::FixedVecSlice) for creating immutable or mutable views.
47//!
48//! # Examples
49//!
50//! Create a [`FixedVec`] from a slice of data. The builder will
51//! automatically determine the minimal number of bits required.
52//!
53//! ```
54//! use compressed_intvec::fixed::{FixedVec, UFixedVec};
55//!
56//! // The numbers 0-7 can all be represented in 3 bits.
57//! let data: Vec<u32> = (0..8).collect();
58//!
59//! // The builder infers that `bit_width` should be 3.
60//! let vec: UFixedVec<u32> = FixedVec::builder()
61//!     .build(&data)
62//!     .unwrap();
63//!
64//! assert_eq!(vec.len(), 8);
65//! assert_eq!(vec.bit_width(), 3);
66//! assert_eq!(vec.get(5), Some(5));
67//! ```
68//!
69//! ## Storing Signed Integers
70//!
71//! [`FixedVec`] can store signed integers. The underlying storage uses zig-zag encoding,
72//! which maps small negative and positive numbers to small unsigned integers.
73//!
74//! ```
75//! use compressed_intvec::fixed::{FixedVec, SFixedVec};
76//!
77//! // The values range from -2 to 1. Zig-zag encoding maps these to
78//! // unsigned values, so the maximum value is 3, which
79//! // requires 2 bits.
80//! let data: &[i16] = &[-2, -1, 0, 1];
81//! let vec: SFixedVec<i16> = FixedVec::builder().build(data).unwrap();
82//!
83//! assert_eq!(vec.bit_width(), 2);
84//! assert_eq!(vec.get(0), Some(-2));
85//! assert_eq!(vec.get(3), Some(1));
86//! ```
87//!
88//! # Implementation Notes
89//!
90//! To ensure safe and efficient memory access, [`FixedVec`] adds one padding
91//! word at the end of its storage buffer. This padding prevents out-of-bounds
92//! reads in methods like [`get_unchecked`](FixedVec::get_unchecked) and is a
93//! prerequisite for unaligned access with [`get_unaligned_unchecked`](FixedVec::get_unaligned_unchecked).
94//! The builders handle this padding automatically. When creating a [`FixedVec`] from raw parts,
95//! it is the caller's responsibility to ensure this padding is present.
96//!
97//! # Common Type Aliases
98//!
99//! To simplify usage, this crate provides several type aliases for common [`FixedVec`]
100//! configurations. In most cases, you should prefer using these aliases over the
101//! fully generic `FixedVec<T, W, E, B>` struct.
102//!
103//! ### General-Purpose Aliases
104//!
105//! These aliases use [`usize`] for the storage word, which is often the most
106//! efficient choice for the target architecture.
107//!
108//! - [`UFixedVec<T>`]: For unsigned integers (e.g., [`u8`], [`u16`], [`u32`]).
109//! - [`SFixedVec<T>`]: For signed integers (e.g., [`i8`], [`i16`], [`i32`]).
110//!
111//! ### Concrete Aliases for [`u64`]/[`i64`]
112//!
113//! These aliases are specialized for [`u64`]/[`i64`] elements stored in [`u64`] words:
114//!
115//! - [`LEFixedVec`]: [`u64`] elements, Little-Endian.
116//! - [`BEFixedVec`]: [`u64`] elements, Big-Endian.
117//! - [`LESFixedVec`]: [`i64`] elements, Little-Endian.
118//! - [`BESFixedVec`]: [`i64`] elements, Big-Endian.
119//!
120//! The [`atomic`] module provides a similar set of aliases like [`UAtomicFixedVec`]
121//! and [`SAtomicFixedVec`].
122
123// Declare and export submodules.
124#[macro_use]
125pub mod macros;
126pub mod builder;
127pub mod iter;
128pub mod iter_mut;
129pub mod parallel;
130pub mod proxy;
131pub mod slice;
132pub mod traits;
133
134pub mod atomic;
135
136// Conditionally compile the serde module.
137#[cfg(feature = "serde")]
138mod serde;
139
140use dsi_bitstream::{
141    prelude::Endianness,
142    traits::{BE, LE},
143};
144use mem_dbg::{MemDbg, MemSize};
145use num_traits::ToPrimitive;
146use std::{error::Error as StdError, fmt, iter::FromIterator, marker::PhantomData};
147use traits::{Storable, Word};
148
149use crate::fixed::{proxy::MutProxy, traits::DefaultParams};
150
151// Re-export atomic aliases for convenience.
152pub use atomic::{AtomicFixedVec, SAtomicFixedVec, UAtomicFixedVec};
153
154// Type aliases for common `FixedVec` configurations.
155
156/// A [`FixedVec`] for unsigned integers with a `usize` word and Little-Endian layout.
157///
158/// This is a convenient alias for a common configuration. The element type `T`
159/// can be any unsigned integer that implements [`Storable`], such as `u8`, `u16`,
160/// `u32`, [`u64`], `u128`, or `usize`.
161pub type UFixedVec<T, B = Vec<usize>> = FixedVec<T, usize, LE, B>;
162
163/// A [`FixedVec`] for signed integers with a `usize` word and Little-Endian layout.
164///
165/// This alias is suitable for general-purpose use with signed types like `i8`,
166/// `i16`, `i32`, [`i64`], `i128`, or `isize`.
167pub type SFixedVec<T, B = Vec<usize>> = FixedVec<T, usize, LE, B>;
168
169// --- Concrete Aliases for [`u64`]/[`i64`] elements ---
170// These are provided for common use cases and backward compatibility.
171
172/// A [`FixedVec`] for [`u64`] elements with a [`u64`] backend and Little-Endian layout.
173pub type LEFixedVec<B = Vec<u64>> = FixedVec<u64, u64, LE, B>;
174/// A [`FixedVec`] for [`i64`] elements with a [`u64`] backend and Little-Endian layout.
175pub type LESFixedVec<B = Vec<u64>> = FixedVec<i64, u64, LE, B>;
176
177/// A [`FixedVec`] for [`u64`] elements with a [`u64`] backend and Big-Endian layout.
178pub type BEFixedVec<B = Vec<u64>> = FixedVec<u64, u64, BE, B>;
179/// A [`FixedVec`] for [`i64`] elements with a [`u64`] backend and Big-Endian layout.
180pub type BESFixedVec<B = Vec<u64>> = FixedVec<i64, u64, BE, B>;
181
182/// Specifies the strategy for determining the number of bits for each integer.
183///
184/// This enum controls how the bit width of a [`FixedVec`] is determined during
185/// its construction. The choice of strategy involves a trade-off between memory
186/// usage and random access performance.
187///
188/// # Performance Considerations
189///
190/// - **[`Minimal`](BitWidth::Minimal) vs. [`PowerOfTwo`](BitWidth::PowerOfTwo)**: While [`Minimal`](BitWidth::Minimal) provides the most compact
191///   storage, [`PowerOfTwo`](BitWidth::PowerOfTwo) can offer better performance for certain operations.
192///   When the `bit_width` is a power of two (e.g., 8, 16, 32) and aligns with
193///   word boundaries, some in-place operations like [`map_in_place`](FixedVec::map_in_place) can use a
194///   faster, word-at-a-time algorithm.
195///
196/// - **[`Explicit`](BitWidth::Explicit)**: This is the fastest strategy at construction time, as it
197///   avoids the need to iterate through the input data to find the maximum
198///   value. Use this when the required bit width is known in advance.
199#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
200pub enum BitWidth {
201    /// Use the minimum number of bits required to store the largest value.
202    ///
203    /// This strategy analyzes the input data to find the maximum value and sets
204    /// the bit width accordingly. It ensures the most compact memory representation.
205    #[default]
206    Minimal,
207
208    /// Round the bit width up to the next power of two (e.g., 8, 16, 32).
209    ///
210    /// This strategy can improve random access performance for some in-place
211    /// operations, as they can be implemented more efficiently with bit-shift operations on aligned data.
212    PowerOfTwo,
213
214    /// Use a specific number of bits.
215    ///
216    /// This strategy enforces a user-defined bit width. If any value in the
217    /// input data exceeds what can be stored in this many bits, the build
218    /// process will fail.
219    Explicit(usize),
220}
221
222/// Defines errors that can occur during [`FixedVec`] operations.
223#[derive(Debug)]
224pub enum Error {
225    /// A value in the input data is too large to be stored with the configured
226    /// bit width.
227    ValueTooLarge {
228        /// The value that could not be stored.
229        value: u128,
230        /// The index of the value in the input data.
231        index: usize,
232        /// The configured number of bits.
233        bit_width: usize,
234    },
235    /// A parameter is invalid for the requested operation.
236    ///
237    /// This typically occurs if `bit_width` is larger than the storage word size
238    /// or if a provided buffer is too small.
239    InvalidParameters(String),
240}
241
242impl fmt::Display for Error {
243    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
244        match self {
245            Error::ValueTooLarge {
246                value,
247                index,
248                bit_width,
249            } => write!(
250                f,
251                "value {value} at index {index} does not fit in {bit_width} bits"
252            ),
253            Error::InvalidParameters(s) => write!(f, "Invalid parameters: {s}"),
254        }
255    }
256}
257
258impl StdError for Error {}
259
260/// A compressed vector of integers with fixed-width encoding.
261///
262/// [`FixedVec`] stores a sequence of integers where each element is encoded using
263/// the same number of bits. This allows for O(1) random access by calculating
264/// the memory location of any element. It is suitable for data where values are
265/// bounded within a known range.
266///
267/// # Type Parameters
268///
269/// - `T`: The integer type for the elements (e.g., `u32`, `i16`). It must
270///   implement the [`Storable`] trait.
271/// - `W`: The underlying storage word (e.g., [`u64`], `usize`). It must implement
272///   the [`Word`] trait.
273/// - `E`: The [`Endianness`] (e.g., [`LE`] or [`BE`]) for bit-level operations.
274/// - `B`: The backend storage buffer, such as `Vec<W>` for an owned vector or
275///   `&[W]` for a borrowed view.
276///
277/// For common configurations, several [type aliases] are provided.
278///
279/// [type aliases]: crate::fixed#type-aliases
280#[derive(Debug, Clone, MemDbg, MemSize)]
281pub struct FixedVec<T: Storable<W>, W: Word, E: Endianness, B: AsRef<[W]> = Vec<W>> {
282    /// The underlying storage for the bit-packed data.
283    pub(crate) bits: B,
284    /// The number of bits used to encode each element.
285    pub(crate) bit_width: usize,
286    /// A bitmask with the lowest `bit_width` bits set to one.
287    pub(crate) mask: W,
288    /// The number of elements in the vector.
289    pub(crate) len: usize,
290    /// Zero-sized markers for the generic type parameters `T`, `W`, and `E`.
291    pub(crate) _phantom: PhantomData<(T, W, E)>,
292}
293
294// [`FixedVec`] builder implementation.
295impl<T, W, E> FixedVec<T, W, E, Vec<W>>
296where
297    T: Storable<W>,
298    W: Word,
299    E: Endianness,
300    dsi_bitstream::impls::BufBitWriter<E, dsi_bitstream::impls::MemWordWriterVec<W, Vec<W>>>:
301        dsi_bitstream::prelude::BitWrite<E, Error = std::convert::Infallible>,
302{
303    /// Creates a builder for constructing a [`FixedVec`] from a slice.
304    ///
305    /// The builder provides methods to customize the vector's properties, such
306    /// as the [`BitWidth`] strategy.
307    ///
308    /// # Examples
309    ///
310    /// ```
311    /// use compressed_intvec::fixed::{FixedVec, BitWidth, UFixedVec};
312    ///
313    /// let data: &[u32] = &[10, 20, 30, 40, 50];
314    /// let vec: UFixedVec<u32> = FixedVec::builder()
315    ///     .bit_width(BitWidth::Minimal)
316    ///     .build(data)
317    ///     .unwrap();
318    ///
319    /// assert_eq!(vec.get(1), Some(20));
320    /// ```
321    pub fn builder() -> builder::FixedVecBuilder<T, W, E> {
322        builder::FixedVecBuilder::new()
323    }
324
325    /// Creates a builder for constructing a [`FixedVec`] from an iterator.
326    ///
327    /// This builder is suitable for large datasets provided by an iterator,
328    /// as it processes the data in a streaming fashion.
329    ///
330    /// # Arguments
331    ///
332    /// * `iter`: An iterator that yields the integer values.
333    /// * `bit_width`: The number of bits to use for each element. This must be
334    ///   specified, as the builder cannot analyze the data in advance.
335    ///
336    /// # Examples
337    ///
338    /// ```
339    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
340    ///
341    /// let data = 0..100u32;
342    /// let vec: UFixedVec<u32> = FixedVec::from_iter_builder(data, 7)
343    ///     .build()
344    ///     .unwrap();
345    ///
346    /// assert_eq!(vec.len(), 100);
347    /// assert_eq!(vec.bit_width(), 7);
348    /// assert_eq!(vec.get(99), Some(99));
349    /// ```
350    pub fn from_iter_builder<I: IntoIterator<Item = T>>(
351        iter: I,
352        bit_width: usize,
353    ) -> builder::FixedVecFromIterBuilder<T, W, E, I> {
354        builder::FixedVecFromIterBuilder::new(iter, bit_width)
355    }
356
357    /// Creates an owned [`FixedVec`] from a slice of data.
358    ///
359    /// This method is a convenience wrapper around the builder API, using
360    /// the default bit width strategy ([`BitWidth::Minimal`]).
361    ///
362    /// # Examples
363    ///
364    /// ```rust
365    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
366    ///
367    /// let data: &[u32] = &[10, 20, 30];
368    ///
369    /// let vec: UFixedVec<u32> = FixedVec::from_slice(data).unwrap();
370    ///
371    /// assert_eq!(vec.len(), 3);
372    /// assert_eq!(vec.bit_width(), 5); // 30 fits in 5 bits
373    /// assert_eq!(vec.get(0), Some(10));
374    /// ```
375    pub fn from_slice(slice: &[T]) -> Result<Self, Error> {
376        Self::builder().build(slice)
377    }
378}
379
380// Core immutable API.
381impl<T, W, E, B> FixedVec<T, W, E, B>
382where
383    T: Storable<W>,
384    W: Word,
385    E: Endianness,
386    B: AsRef<[W]>,
387{
388    /// Creates a [`FixedVec`] from its raw components.
389    ///
390    /// This constructor allows for the creation of a zero-copy view over an
391    /// existing buffer.
392    ///
393    /// # Errors
394    ///
395    /// Returns an [`Error::InvalidParameters`] if `bit_width` is larger than
396    /// the word size or if the `bits` buffer is too small to hold the specified
397    /// number of elements and the required padding.
398    ///
399    /// # Implementation Notes
400    ///
401    /// The provided `bits` buffer must contain at least one extra "padding"
402    /// word at the end. This padding is essential to prevent out-of-bounds
403    /// memory access in methods like `get_unchecked`.
404    ///
405    /// # Examples
406    ///
407    /// ```
408    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
409    ///
410    /// // 3 elements * 5 bits = 15 bits. This requires 1 data word.
411    /// // We need 1 extra word for padding.
412    /// let mut buffer = vec![0_usize; 2];
413    ///
414    /// // Manually encode data into the first word.
415    /// // 10 (01010), 20 (10100), 30 (11110)
416    /// buffer[0] = 0b11110_10100_01010;
417    ///
418    /// let vec = UFixedVec::<u32, _>::from_parts(&buffer, 3, 5).unwrap();
419    /// assert_eq!(vec.get(0), Some(10));
420    /// assert_eq!(vec.get(1), Some(20));
421    /// assert_eq!(vec.get(2), Some(30));
422    /// ```
423    pub fn from_parts(bits: B, len: usize, bit_width: usize) -> Result<Self, Error> {
424        if bit_width > <W as traits::Word>::BITS {
425            return Err(Error::InvalidParameters(format!(
426                "bit_width ({}) cannot be greater than the word size ({})",
427                bit_width,
428                <W as traits::Word>::BITS
429            )));
430        }
431
432        let total_bits = len * bit_width;
433        let data_words = total_bits.div_ceil(<W as traits::Word>::BITS);
434
435        // Essential safety check: ensure the buffer is large enough for the data
436        // AND the 1 padding word required.
437        if bits.as_ref().len() < data_words + 1 {
438            return Err(Error::InvalidParameters(format!(
439                "The provided buffer is too small. It has {} words, but {} data words + 1 padding word are required.",
440                bits.as_ref().len(),
441                data_words
442            )));
443        }
444
445        Ok(unsafe { Self::new_unchecked(bits, len, bit_width) })
446    }
447
448    /// Returns the number of elements in the vector.
449    #[inline]
450    pub fn len(&self) -> usize {
451        self.len
452    }
453
454    /// Returns `true` if the vector is empty.
455    #[inline]
456    pub fn is_empty(&self) -> bool {
457        self.len == 0
458    }
459
460    /// Returns the number of bits used to encode each element.
461    #[inline]
462    pub fn bit_width(&self) -> usize {
463        self.bit_width
464    }
465
466    /// Returns a read-only slice of the underlying storage words.
467    #[inline]
468    pub fn as_limbs(&self) -> &[W] {
469        self.bits.as_ref()
470    }
471
472    /// Returns a raw pointer to the start of the underlying buffer and its
473    /// length in words.
474    ///
475    /// # Safety
476    ///
477    /// The caller must ensure that the buffer is not mutated in a way that
478    /// violates the invariants of the [`FixedVec`] while the pointer is active.
479    pub fn as_raw_parts(&self) -> (*const W, usize) {
480        let slice = self.bits.as_ref();
481        (slice.as_ptr(), slice.len())
482    }
483
484    /// Creates a [`FixedVec`] from its raw components without performing checks.
485    ///
486    /// # Safety
487    ///
488    /// The caller must ensure that the following invariants are met:
489    /// 1. The `bits` buffer must be large enough to hold `len * bit_width` bits.
490    /// 2. The `bits` buffer must have at least one extra padding word at the end
491    ///    to prevent out-of-bounds reads during access.
492    /// 3. `bit_width` must not be greater than the number of bits in `W`.
493    pub(crate) unsafe fn new_unchecked(bits: B, len: usize, bit_width: usize) -> Self {
494        let mask = if bit_width == <W as traits::Word>::BITS {
495            W::max_value()
496        } else {
497            (W::ONE << bit_width) - W::ONE
498        };
499
500        Self {
501            bits,
502            len,
503            bit_width,
504            mask,
505            _phantom: PhantomData,
506        }
507    }
508
509    /// Returns the element at the specified index, or `None` if the index is
510    /// out of bounds.
511    ///
512    /// This operation is O(1).
513    ///
514    /// # Examples
515    ///
516    /// ```
517    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
518    ///
519    /// let data: &[u32] = &[10, 20, 30];
520    /// let vec: UFixedVec<u32> = FixedVec::builder().build(data).unwrap();
521    ///
522    /// assert_eq!(vec.get(1), Some(20));
523    /// assert_eq!(vec.get(3), None);
524    /// ```
525    #[inline]
526    pub fn get(&self, index: usize) -> Option<T> {
527        if index >= self.len {
528            return None;
529        }
530        Some(unsafe { self.get_unchecked(index) })
531    }
532
533    /// Returns the element at the specified index without bounds checking.
534    ///
535    /// # Safety
536    ///
537    /// Calling this method with an out-of-bounds `index` is undefined behavior.
538    /// The `index` must be less than the vector's `len`.
539    #[inline(always)]
540    pub unsafe fn get_unchecked(&self, index: usize) -> T {
541        debug_assert!(index < self.len);
542
543        let bits_per_word = <W as traits::Word>::BITS;
544        // Optimization: if bit_width matches word size, access is trivial.
545        if self.bit_width == bits_per_word {
546            let val = *self.as_limbs().get_unchecked(index);
547            // Apply endianness correction if needed.
548            let final_val = if E::IS_BIG { val.to_be() } else { val };
549            return <T as Storable<W>>::from_word(final_val);
550        }
551
552        // Calculate the bit position and word index for the element.
553        let bit_pos = index * self.bit_width;
554        let word_index = bit_pos / bits_per_word;
555        let bit_offset = bit_pos % bits_per_word;
556
557        let limbs = self.as_limbs();
558        let final_word: W;
559
560        // The logic is specialized for endianness to maximize performance.
561        if E::IS_LITTLE {
562            // Fast path: the element is fully contained within a single word.
563            if bit_offset + self.bit_width <= bits_per_word {
564                final_word = (*limbs.get_unchecked(word_index) >> bit_offset) & self.mask;
565            } else {
566                // Slow path: the element spans two words.
567                // Read the low part from the first word and the high part from the next.
568                let low = *limbs.get_unchecked(word_index) >> bit_offset;
569                let high = *limbs.get_unchecked(word_index + 1) << (bits_per_word - bit_offset);
570                final_word = (low | high) & self.mask;
571            }
572        } else {
573            // Big-Endian logic requires byte-swapping the words before extraction.
574            let word_hi = (*limbs.get_unchecked(word_index)).to_be();
575            if bit_offset + self.bit_width <= bits_per_word {
576                final_word = (word_hi << bit_offset) >> (bits_per_word - self.bit_width);
577            } else {
578                let word_lo = (*limbs.get_unchecked(word_index + 1)).to_be();
579                let bits_in_first = bits_per_word - bit_offset;
580                let high = word_hi << bit_offset >> (bits_per_word - bits_in_first);
581                let low = word_lo >> (bits_per_word - (self.bit_width - bits_in_first));
582                final_word = (high << (self.bit_width - bits_in_first)) | low;
583            }
584        }
585        <T as Storable<W>>::from_word(final_word)
586    }
587
588    /// Returns the element at the specified index using unaligned memory access,
589    /// or [`None`] if the index is out of bounds.
590    ///
591    /// This method attempts to use a optimized path with a single
592    /// unaligned memory read. For certain `bit_width` configurations where this
593    /// is not safe (e.g., a 63-bit value on a [`u64`] backend), it automatically
594    /// falls back to the safe, two-read implementation of [`get_unchecked`](Self::get_unchecked).
595    ///
596    /// # Note
597    ///
598    /// This method performs various checks to determine if the current configuration
599    /// is safe for a single unaligned read. This will of course add some overhead. If
600    /// your are sure that
601    ///
602    /// # Examples
603    ///
604    /// ```
605    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
606    ///
607    /// let data: &[u32] = &[10, 20, 30];
608    /// let vec: UFixedVec<u32> = FixedVec::builder().build(data).unwrap();
609    ///
610    /// assert_eq!(vec.get_unaligned(1), Some(20));
611    /// assert_eq!(vec.get_unaligned(3), None);
612    /// ```
613    #[inline]
614    pub fn get_unaligned(&self, index: usize) -> Option<T> {
615        if index >= self.len {
616            return None;
617        }
618
619        // SAFETY: We have just performed the bounds check, so both
620        // `get_unchecked` and `get_unaligned_unchecked` are safe to call.
621        unsafe {
622            let bits_per_word = <W as Word>::BITS;
623            let bit_width = self.bit_width;
624
625            // Check if the current configuration is safe for a single unaligned read.
626            // This is a precise check based on the analysis of which bit_widths can
627            // cause a read to span more than W::BITS.
628            let is_safe = (bit_width <= bits_per_word.saturating_sub(6)) // e.g., <= 58 for u64
629                || (bit_width == bits_per_word.saturating_sub(4))        // e.g., == 60 for u64
630                || (bit_width == bits_per_word);
631
632            let value = if is_safe {
633                // Fast path for safe configurations.
634                self.get_unaligned_unchecked(index)
635            } else {
636                // Fallback for unsafe bit_widths (e.g., 59, 61, 62, 63 for u64).
637                self.get_unchecked(index)
638            };
639            Some(value)
640        }
641    }
642
643    /// Returns the element at `index` using unaligned memory access.
644    ///
645    /// This method can be significantly faster for random access. It performs a
646    /// single, potentially unaligned read of a [`Word`] and extracts the value.
647    ///
648    /// # Performance
649    ///
650    /// This method is generally the fastest way to perform random reads on
651    /// Little-Endian architectures, especially when the `bit_width` is not a
652    /// power of two.
653    ///
654    /// - [`get_unchecked`](Self::get_unchecked): May require reading one or two separate machine words
655    ///   and combining them with bit shifts. This is fast if the data is already
656    ///   in the CPU cache.
657    /// - [`get_unaligned_unchecked`](Self::get_unaligned_unchecked): Performs a single memory read that may
658    ///   cross word boundaries. It often results in fewer instructions and better throughput than the two
659    ///   separate reads of [`get_unchecked`](Self::get_unchecked), especially in memory-bound scenarios.
660    ///
661    ///
662    /// # Safety
663    ///
664    /// Calling this method is undefined behavior if:
665    /// - `index` is out of bounds (`index >= self.len()`).
666    /// - The `bit_width` is one for which a single unaligned read is unsafe.
667    ///   This is the case for `bit_width` values such as `59`, `61`, `62`, `63`
668    ///   on a [`u64`] backend, and analogous values for other word sizes.
669    ///
670    /// # Panics
671    ///
672    /// In debug builds, this method will panic if the safety conditions on `index`
673    /// or `bit_width` are not met.
674    ///
675    /// # Implementation Notes
676    ///
677    /// For Big-Endian systems, this method falls back to the standard
678    /// [`get_unchecked`](Self::get_unchecked) implementation, as unaligned
679    /// access logic is more complex and architecture-dependent.
680    #[inline(always)]
681    pub unsafe fn get_unaligned_unchecked(&self, index: usize) -> T {
682        debug_assert!(index < self.len);
683
684        if E::IS_LITTLE {
685            let bits_per_word = <W as Word>::BITS;
686            let bit_width = self.bit_width;
687
688            if bit_width == bits_per_word {
689                return self.get_unchecked(index);
690            }
691
692            // In debug builds, assert that this function is only called for `bit_width`
693            // values where a single unaligned read is guaranteed to be sufficient.
694            debug_assert!({
695                    let is_safe_contiguous = bit_width <= bits_per_word.saturating_sub(6); // e.g., <= 58 for u64
696                    let is_safe_case_60 = bit_width == bits_per_word.saturating_sub(4); // e.g., == 60 for u64
697                    is_safe_contiguous || is_safe_case_60
698                },
699                "get_unaligned_unchecked is not safe for this bit_width ({bit_width}). \
700                The value may span more than {bits_per_word} bits, making a single read insufficient. \
701                Use get_unaligned() for a safe version with an automatic fallback."
702            );
703
704            let bit_pos = index * bit_width;
705            let byte_pos = bit_pos / 8;
706            let bit_rem = bit_pos % 8;
707
708            let limbs_ptr = self.as_limbs().as_ptr() as *const u8;
709
710            // Perform an unaligned read from the calculated byte position.
711            let word: W = (limbs_ptr.add(byte_pos) as *const W).read_unaligned();
712            let extracted_word = word >> bit_rem;
713
714            <T as Storable<W>>::from_word(extracted_word & self.mask)
715        } else {
716            // For Big-Endian, the logic for unaligned reads is complex and
717            // architecture-dependent. Fall back to the standard `get_unchecked`.
718            self.get_unchecked(index)
719        }
720    }
721
722    /// Returns an iterator over the elements of the vector.
723    ///
724    /// # Examples
725    ///
726    /// ```
727    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
728    ///
729    /// let data: &[u32] = &[10, 20, 30];
730    /// let vec: UFixedVec<u32> = FixedVec::builder().build(data).unwrap();
731    /// let mut iter = vec.iter();
732    ///
733    /// for (i, value) in iter.enumerate() {
734    ///     assert_eq!(Some(value), vec.get(i));
735    /// }
736    /// ```
737    pub fn iter(&self) -> iter::FixedVecIter<'_, T, W, E, B> {
738        iter::FixedVecIter::new(self)
739    }
740
741    /// Returns an unchecked iterator over the elements of the vector.
742    ///
743    /// # Safety
744    ///
745    /// The caller must ensure that the iterator is not advanced beyond the
746    /// vector's length.
747    pub unsafe fn iter_unchecked(&self) -> iter::FixedVecUncheckedIter<'_, T, W, E, B> {
748        iter::FixedVecUncheckedIter::new(self)
749    }
750
751    /// Creates an immutable view (slice) of a sub-region of the vector.
752    ///
753    /// Returns `None` if the specified range is out of bounds.
754    ///
755    /// # Arguments
756    /// * `start`: The starting index of the slice.
757    /// * `len`: The number of elements in the slice.
758    pub fn slice(&self, start: usize, len: usize) -> Option<slice::FixedVecSlice<&Self>> {
759        if start.saturating_add(len) > self.len {
760            return None;
761        }
762        Some(slice::FixedVecSlice::new(self, start..start + len))
763    }
764
765    /// Splits the vector into two immutable views at a given index.
766    ///
767    /// Returns `None` if `mid` is out of bounds.
768    ///
769    /// # Arguments
770    /// * `mid`: The index at which to split the vector.
771    pub fn split_at(
772        &self,
773        mid: usize,
774    ) -> Option<(slice::FixedVecSlice<&Self>, slice::FixedVecSlice<&Self>)> {
775        if mid > self.len {
776            return None;
777        }
778        let left = slice::FixedVecSlice::new(self, 0..mid);
779        let right = slice::FixedVecSlice::new(self, mid..self.len);
780        Some((left, right))
781    }
782
783    /// Returns an iterator over non-overlapping chunks of the vector.
784    ///
785    /// Each chunk is a [`FixedVecSlice`] of length `chunk_size`, except for the
786    /// last chunk, which may be shorter.
787    ///
788    /// # Panics
789    ///
790    /// Panics if `chunk_size` is 0.
791    ///
792    /// [`FixedVecSlice`]: slice::FixedVecSlice
793    pub fn chunks(&self, chunk_size: usize) -> iter::Chunks<'_, T, W, E, B> {
794        iter::Chunks::new(self, chunk_size)
795    }
796
797    /// Returns an iterator over all contiguous windows of length `size`.
798    ///
799    /// The windows overlap. If the vector is shorter than `size`, the iterator
800    /// returns no values.
801    ///
802    /// # Panics
803    ///
804    /// Panics if `size` is 0.
805    ///
806    /// # Examples
807    ///
808    /// ```
809    /// use compressed_intvec::fixed_vec;
810    ///
811    /// let vec = fixed_vec![1u32, 2, 3, 4, 5];
812    /// let mut windows = vec.windows(3);
813    ///
814    /// let slice1 = vec.slice(0, 3).unwrap();
815    /// let slice2 = vec.slice(1, 3).unwrap();
816    /// let slice3 = vec.slice(2, 3).unwrap();
817    ///
818    /// assert_eq!(windows.next().unwrap(), slice1);
819    /// assert_eq!(windows.next().unwrap(), slice2);
820    /// assert_eq!(windows.next().unwrap(), slice3);
821    /// assert!(windows.next().is_none());
822    /// ```
823    pub fn windows(&self, size: usize) -> iter::Windows<'_, T, W, E, B> {
824        assert!(size != 0, "window size cannot be zero");
825        iter::Windows::new(self, size)
826    }
827
828    /// Returns a raw pointer to the storage word containing the start of an element.
829    ///
830    /// This method returns a pointer to the [`Word`] in the backing buffer where
831    /// the data for the element at `index` begins.
832    ///
833    /// Returns `None` if `index` is out of bounds.
834    ///
835    /// # Safety
836    ///
837    /// This method is safe as it only returns a raw pointer. Dereferencing the
838    /// pointer is `unsafe`. The caller must ensure that the pointer is not used
839    /// after the [`FixedVec`] is dropped or modified.
840    pub fn addr_of(&self, index: usize) -> Option<*const W> {
841        if index >= self.len {
842            return None;
843        }
844
845        let bit_pos = index * self.bit_width;
846        let word_idx = bit_pos / <W as Word>::BITS;
847
848        let limbs = self.as_limbs();
849        if word_idx < limbs.len() {
850            Some(limbs.as_ptr().wrapping_add(word_idx))
851        } else {
852            None
853        }
854    }
855
856    /// Hints to the CPU to prefetch the data for the element at `index` into cache.
857    ///
858    /// This method uses an intrinsic to reduce memory latency for predictable
859    /// access patterns. It only has an effect on architectures that support it
860    /// (e.g., x86, x86-64) and compiles to a no-op on other platforms.
861    pub fn prefetch(&self, index: usize) {
862        if index >= self.len {
863            return;
864        }
865
866        #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
867        {
868            use std::arch::x86_64::{_mm_prefetch, _MM_HINT_T0};
869
870            let bit_pos = index * self.bit_width;
871            let byte_pos = bit_pos / 8;
872
873            let limbs_ptr = self.as_limbs().as_ptr() as *const i8;
874
875            // SAFETY: Bounds check on `index` ensures `byte_pos` is within the
876            // allocated buffer (including padding). The pointer is valid.
877            unsafe {
878                // Prefetch into all cache levels (a good general-purpose default).
879                _mm_prefetch(limbs_ptr.add(byte_pos), _MM_HINT_T0);
880            }
881        }
882    }
883
884    /// Binary searches this vector for a given element.
885    ///
886    /// If the value is found, returns `Ok(usize)` with the index of the
887    /// matching element. If the value is not found, returns `Err(usize)` with
888    /// the index where the value could be inserted to maintain order.
889    ///
890    /// # Examples
891    ///
892    /// ```
893    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
894    ///
895    /// let data: &[u32] = &[10, 20, 30, 40, 50];
896    /// let vec: UFixedVec<u32> = FixedVec::builder().build(data).unwrap();
897    ///
898    /// assert_eq!(vec.binary_search(&30), Ok(2));
899    /// assert_eq!(vec.binary_search(&35), Err(3));
900    /// ```
901    pub fn binary_search(&self, value: &T) -> Result<usize, usize>
902    where
903        T: Ord,
904    {
905        let mut low = 0;
906        let mut high = self.len();
907
908        while low < high {
909            let mid = low + (high - low) / 2;
910            let mid_val = unsafe { self.get_unchecked(mid) };
911
912            match mid_val.cmp(value) {
913                std::cmp::Ordering::Less => low = mid + 1,
914                std::cmp::Ordering::Equal => return Ok(mid),
915                std::cmp::Ordering::Greater => high = mid,
916            }
917        }
918        Err(low)
919    }
920
921    /// Binary searches this vector with a key extraction function.
922    ///
923    /// This method is useful when searching for a value of a different type
924    /// than the elements of the slice. The function `f` is used to extract a
925    /// key of type `K` from an element, which is then compared to `key`.
926    pub fn binary_search_by_key<K: Ord, F>(&self, key: &K, mut f: F) -> Result<usize, usize>
927    where
928        F: FnMut(T) -> K,
929    {
930        self.binary_search_by(|probe| f(*probe).cmp(key))
931    }
932
933    /// Binary searches this vector with a custom comparison function.
934    ///
935    /// The comparator function `f` should return an `Ordering` indicating
936    /// the relation of a probe element to the value being searched for.
937    ///
938    /// # Examples
939    ///
940    /// ```
941    /// use compressed_intvec::fixed_vec;
942    /// use std::cmp::Ordering;
943    ///
944    /// let vec = fixed_vec![0u32, 1, 1, 2, 3];
945    ///
946    /// // Search for a value by comparing it to the probe.
947    /// let result = vec.binary_search_by(|probe| probe.cmp(&1));
948    /// assert!(matches!(result, Ok(1) | Ok(2)));
949    ///
950    /// let result_not_found = vec.binary_search_by(|probe| probe.cmp(&4));
951    /// assert_eq!(result_not_found, Err(5));
952    /// ```
953    pub fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize>
954    where
955        F: FnMut(&T) -> std::cmp::Ordering,
956    {
957        let mut low = 0;
958        let mut high = self.len();
959
960        while low < high {
961            let mid = low + (high - low) / 2;
962            // SAFETY: The loop invariants ensure `mid` is always in bounds.
963            let mid_val = unsafe { self.get_unchecked(mid) };
964
965            match f(&mid_val) {
966                std::cmp::Ordering::Less => low = mid + 1,
967                std::cmp::Ordering::Equal => return Ok(mid),
968                std::cmp::Ordering::Greater => high = mid,
969            }
970        }
971        Err(low)
972    }
973
974    /// Returns the index of the partition point of the vector.
975    ///
976    /// The vector is partitioned according to the predicate `pred`. This means
977    /// all elements for which `pred` returns `true` are on the left of the
978    /// partition point, and all elements for which `pred` returns `false` are
979    /// on the right.
980    ///
981    /// # Examples
982    ///
983    /// ```
984    /// use compressed_intvec::fixed_vec;
985    ///
986    /// let vec = fixed_vec![0u32, 1, 2, 3, 4, 5];
987    ///
988    /// // Find the partition point for elements `< 3`.
989    /// let partition_idx = vec.partition_point(|&x| x < 3);
990    /// assert_eq!(partition_idx, 3);
991    /// ```
992    pub fn partition_point<P>(&self, mut pred: P) -> usize
993    where
994        P: FnMut(&T) -> bool,
995    {
996        let mut len = self.len();
997        let mut left = 0;
998
999        while len > 0 {
1000            let half = len / 2;
1001            let mid = left + half;
1002            // SAFETY: The loop invariants ensure `mid` is always in bounds.
1003            let value = unsafe { self.get_unchecked(mid) };
1004
1005            if pred(&value) {
1006                left = mid + 1;
1007                len -= half + 1;
1008            } else {
1009                len = half;
1010            }
1011        }
1012        left
1013    }
1014}
1015
1016/// Allows iterating over a borrowed [`FixedVec`] (e.g., `for val in &my_vec`).
1017impl<'a, T, W, E, B> IntoIterator for &'a FixedVec<T, W, E, B>
1018where
1019    T: Storable<W>,
1020    W: Word,
1021    E: Endianness,
1022    B: AsRef<[W]>,
1023{
1024    type Item = T;
1025    type IntoIter = iter::FixedVecIter<'a, T, W, E, B>;
1026
1027    fn into_iter(self) -> Self::IntoIter {
1028        self.iter()
1029    }
1030}
1031
1032/// Allows iterating over an owned [`FixedVec`], consuming it.
1033impl<T, W, E> IntoIterator for FixedVec<T, W, E, Vec<W>>
1034where
1035    T: Storable<W> + 'static,
1036    W: Word,
1037    E: Endianness,
1038{
1039    type Item = T;
1040    type IntoIter = iter::FixedVecIntoIter<'static, T, W, E>;
1041
1042    /// Consumes the vector and returns an iterator over its elements.
1043    fn into_iter(self) -> Self::IntoIter {
1044        iter::FixedVecIntoIter::new(self)
1045    }
1046}
1047
1048impl<T, W, E> FromIterator<T> for FixedVec<T, W, E, Vec<W>>
1049where
1050    T: Storable<W>,
1051    W: Word,
1052    E: Endianness,
1053    dsi_bitstream::impls::BufBitWriter<E, dsi_bitstream::impls::MemWordWriterVec<W, Vec<W>>>:
1054        dsi_bitstream::prelude::BitWrite<E, Error = std::convert::Infallible>,
1055{
1056    /// Creates a [`FixedVec`] by collecting elements from an iterator.
1057    ///
1058    /// The bit width is determined automatically using the [`BitWidth::Minimal`]
1059    /// strategy. This requires collecting the iterator into a temporary `Vec<T>`
1060    /// to analyze its contents before compression.
1061    ///
1062    /// # Memory Usage
1063    ///
1064    /// Because this implementation must first collect all items into a temporary
1065    /// `Vec<T>` to determine the optimal `bit_width`, it may lead to a temporary
1066    /// peak in memory usage that is roughly double the size of the uncompressed
1067    /// data.
1068    ///
1069    /// For very large datasets where this memory overhead is a concern, it is
1070    /// recommended to use [`FixedVec::from_iter_builder`] instead. The builder
1071    /// allows for streaming construction but requires the `bit_width` to be
1072    /// specified manually.
1073    ///
1074    /// # Examples
1075    ///
1076    /// ```
1077    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
1078    ///
1079    /// let data = 0u32..100;
1080    /// let vec: UFixedVec<u32> = data.collect();
1081    ///
1082    /// assert_eq!(vec.len(), 100);
1083    /// assert_eq!(vec.get(50), Some(50));
1084    /// ```
1085    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1086        let data: Vec<T> = iter.into_iter().collect();
1087        Self::builder().build(&data).unwrap()
1088    }
1089}
1090
1091impl<T, W, E> Default for FixedVec<T, W, E, Vec<W>>
1092where
1093    T: Storable<W>,
1094    W: Word,
1095    E: Endianness,
1096{
1097    /// Creates an empty [`FixedVec`] with a default `bit_width` of 1.
1098    fn default() -> Self {
1099        // SAFETY: An empty vector with a valid bit_width is always safe.
1100        unsafe { Self::new_unchecked(Vec::new(), 0, 1) }
1101    }
1102}
1103
1104// Methods for owned vectors (`B = Vec<W>`).
1105impl<T, W, E> FixedVec<T, W, E, Vec<W>>
1106where
1107    T: Storable<W> + ToPrimitive,
1108    W: Word,
1109    E: Endianness,
1110{
1111    /// Creates a new, empty [`FixedVec`] with a specified bit width.
1112    ///
1113    /// # Errors
1114    ///
1115    /// Returns an [`Error::InvalidParameters`] if `bit_width` is greater than
1116    /// the number of bits in the storage word `W`.
1117    ///
1118    /// # Examples
1119    ///
1120    /// ```
1121    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
1122    ///
1123    /// let vec: UFixedVec<u32> = FixedVec::new(8).unwrap();
1124    /// assert!(vec.is_empty());
1125    /// assert_eq!(vec.bit_width(), 8);
1126    /// ```
1127    pub fn new(bit_width: usize) -> Result<Self, Error> {
1128        if bit_width > <W as traits::Word>::BITS {
1129            return Err(Error::InvalidParameters(format!(
1130                "bit_width ({}) cannot be greater than the word size ({})",
1131                bit_width,
1132                <W as traits::Word>::BITS
1133            )));
1134        }
1135        Ok(unsafe { Self::new_unchecked(Vec::new(), 0, bit_width) })
1136    }
1137
1138    /// Appends an element to the end of the vector.
1139    ///
1140    /// This operation has amortized O(1) complexity.
1141    ///
1142    /// # Panics
1143    ///
1144    /// Panics if the `value` is too large to be represented by the configured
1145    /// `bit_width`.
1146    ///
1147    /// # Examples
1148    ///
1149    /// ```
1150    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
1151    ///
1152    /// let mut vec: UFixedVec<u32> = FixedVec::new(4).unwrap();
1153    /// vec.push(10);
1154    /// vec.push(15);
1155    ///
1156    /// assert_eq!(vec.len(), 2);
1157    /// assert_eq!(vec.get(1), Some(15));
1158    /// ```
1159    #[inline(always)]
1160    pub fn push(&mut self, value: T) {
1161        let value_w = <T as Storable<W>>::into_word(value);
1162
1163        // Check if the value fits within the configured bit width.
1164        if (value_w & !self.mask) != W::ZERO {
1165            panic!(
1166                "Value {:?} does not fit in the configured bit_width of {}",
1167                value_w, self.bit_width
1168            );
1169        }
1170
1171        let bits_per_word = <W as traits::Word>::BITS;
1172        // Grow the underlying buffer if the new element would exceed its bit capacity.
1173        if (self.len + 1) * self.bit_width > self.bits.len() * bits_per_word {
1174            self.bits.push(W::ZERO);
1175        }
1176
1177        // SAFETY: We have ensured the value fits and the buffer has capacity.
1178        unsafe {
1179            self.set_unchecked(self.len, value_w);
1180        }
1181
1182        self.len += 1;
1183    }
1184
1185    /// Removes the last element from the vector and returns it.
1186    ///
1187    /// Returns `None` if the vector is empty.
1188    ///
1189    /// # Examples
1190    ///
1191    /// ```
1192    /// use compressed_intvec::fixed_vec;
1193    ///
1194    /// let mut vec = fixed_vec![1u32, 2, 3];
1195    /// assert_eq!(vec.pop(), Some(3));
1196    /// assert_eq!(vec.len(), 2);
1197    /// ```
1198    pub fn pop(&mut self) -> Option<T> {
1199        if self.is_empty() {
1200            return None;
1201        }
1202        let value = self.get(self.len - 1).unwrap();
1203        self.len -= 1;
1204        Some(value)
1205    }
1206
1207    /// Removes all elements from the vector, leaving the capacity unchanged.
1208    pub fn clear(&mut self) {
1209        self.len = 0;
1210    }
1211
1212    /// Creates a new, empty [`FixedVec`] with a specified bit width and capacity.
1213    ///
1214    /// The vector will be able to hold at least `capacity` elements without
1215    /// reallocating.
1216    ///
1217    /// # Errors
1218    ///
1219    /// Returns an [`Error::InvalidParameters`] if `bit_width` is greater than
1220    /// the number of bits in the storage word `W`.
1221    ///
1222    /// # Examples
1223    ///
1224    /// ```
1225    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
1226    ///
1227    /// let vec: UFixedVec<u32> = FixedVec::with_capacity(5, 1000).unwrap();
1228    /// assert!(vec.capacity() >= 1000);
1229    /// ```
1230    pub fn with_capacity(bit_width: usize, capacity: usize) -> Result<Self, Error> {
1231        if bit_width > <W as traits::Word>::BITS {
1232            return Err(Error::InvalidParameters(format!(
1233                "bit_width ({}) cannot be greater than the word size ({})",
1234                bit_width,
1235                <W as traits::Word>::BITS
1236            )));
1237        }
1238        let bits_per_word = <W as traits::Word>::BITS;
1239        let total_bits = capacity.saturating_mul(bit_width);
1240        let num_words = total_bits.div_ceil(bits_per_word);
1241
1242        let buffer = if capacity == 0 {
1243            Vec::new()
1244        } else {
1245            Vec::with_capacity(num_words + 1) // +1 for padding
1246        };
1247
1248        Ok(unsafe { Self::new_unchecked(buffer, 0, bit_width) })
1249    }
1250
1251    /// Returns the number of elements the vector can hold without reallocating.
1252    pub fn capacity(&self) -> usize {
1253        if self.bit_width == 0 {
1254            return usize::MAX;
1255        }
1256        let word_capacity = self.bits.capacity();
1257        if word_capacity <= 1 {
1258            return 0; // Not enough for data + padding.
1259        }
1260        // Subtract padding words before calculating element capacity.
1261        ((word_capacity - 1) * <W as traits::Word>::BITS) / self.bit_width
1262    }
1263
1264    /// Returns the capacity of the underlying storage in words.
1265    pub fn word_capacity(&self) -> usize {
1266        self.bits.capacity()
1267    }
1268
1269    /// Reserves capacity for at least `additional` more elements to be inserted.
1270    ///
1271    /// # Panics
1272    ///
1273    /// Panics if the new capacity overflows [`usize`].
1274    ///
1275    /// # Examples
1276    ///
1277    /// ```
1278    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
1279    ///
1280    /// let mut vec: UFixedVec<u32> = FixedVec::new(4).unwrap();
1281    /// vec.reserve(100);
1282    /// assert!(vec.capacity() >= 100);
1283    /// ```
1284    pub fn reserve(&mut self, additional: usize) {
1285        let target_element_capacity = self.len.saturating_add(additional);
1286        if self.capacity() >= target_element_capacity {
1287            return;
1288        }
1289        let bits_per_word = <W as Word>::BITS;
1290        let required_total_bits = target_element_capacity.saturating_mul(self.bit_width);
1291        let required_data_words = required_total_bits.div_ceil(bits_per_word);
1292        let required_word_capacity = required_data_words + 1; // +1 for padding
1293
1294        let current_len = self.bits.len();
1295        if self.bits.capacity() < required_word_capacity {
1296            self.bits.reserve(required_word_capacity - current_len);
1297        }
1298    }
1299
1300    /// Resizes the vector so that its length is equal to `new_len`.
1301    ///
1302    /// If `new_len` is greater than the current length, the vector is extended
1303    /// by appending `value`. If `new_len` is less than the current length, the
1304    /// vector is truncated.
1305    ///
1306    /// # Panics
1307    ///
1308    /// Panics if the `value` used for filling does not fit in the configured
1309    /// `bit_width`.
1310    ///
1311    /// # Examples
1312    ///
1313    /// ```
1314    /// use compressed_intvec::fixed::{FixedVec, UFixedVec};
1315    ///
1316    /// let mut vec = UFixedVec::<u32>::new(4).unwrap();
1317    /// vec.push(1);
1318    /// vec.push(2);
1319    ///
1320    /// vec.resize(4, 10);
1321    /// assert_eq!(vec.len(), 4);
1322    /// assert_eq!(vec.get(3), Some(10));
1323    ///
1324    /// vec.resize(1, 0);
1325    /// assert_eq!(vec.len(), 1);
1326    /// assert_eq!(vec.get(0), Some(1));
1327    /// ```
1328    #[inline(always)]
1329    pub fn resize(&mut self, new_len: usize, value: T) {
1330        if new_len > self.len {
1331            let value_w = <T as Storable<W>>::into_word(value);
1332
1333            if (value_w & !self.mask) != W::ZERO {
1334                panic!(
1335                    "Value {:?} does not fit in the configured bit_width of {}",
1336                    value_w, self.bit_width
1337                );
1338            }
1339
1340            let bits_per_word = <W as traits::Word>::BITS;
1341            let required_total_bits = new_len * self.bit_width;
1342            let required_data_words = required_total_bits.div_ceil(bits_per_word);
1343            let required_vec_len = required_data_words.saturating_add(1); // Padding
1344
1345            if self.bits.len() < required_vec_len {
1346                self.bits.resize(required_vec_len, W::ZERO);
1347            }
1348
1349            for i in self.len..new_len {
1350                unsafe {
1351                    self.set_unchecked(i, value_w);
1352                }
1353            }
1354            self.len = new_len;
1355        } else {
1356            self.len = new_len;
1357        }
1358    }
1359
1360    /// Shrinks the capacity of the vector as much as possible.
1361    pub fn shrink_to_fit(&mut self) {
1362        let min_word_len = if self.len == 0 {
1363            0
1364        } else {
1365            let bits_per_word = <W as traits::Word>::BITS;
1366            let required_total_bits = self.len.saturating_mul(self.bit_width);
1367            let required_words = required_total_bits.div_ceil(bits_per_word);
1368            required_words + 1 // +1 for padding
1369        };
1370
1371        if self.bits.len() > min_word_len {
1372            self.bits.truncate(min_word_len);
1373        }
1374        self.bits.shrink_to_fit();
1375    }
1376
1377    /// Removes and returns the element at `index`, shifting all elements after
1378    /// it to the left.
1379    ///
1380    /// This operation is O(n), where n is the number of elements after `index`.
1381    ///
1382    /// # Panics
1383    ///
1384    /// Panics if `index` is out of bounds.
1385    ///
1386    /// # Complexity
1387    ///
1388    /// This operation has a complexity of O(L), where L is the number of bits
1389    /// that need to be shifted. In the worst case (removing the first element),
1390    /// this is proportional to the total number of bits in the vector
1391    /// (`self.len() * self.bit_width()`).
1392    ///
1393    /// # Panics
1394    ///
1395    /// Panics if `index` is out of bounds.
1396    pub fn remove(&mut self, index: usize) -> T {
1397        assert!(index < self.len, "remove: index out of bounds");
1398
1399        let value_to_return = self.get(index).unwrap();
1400
1401        let start_bit = index * self.bit_width;
1402        let end_bit = self.len * self.bit_width;
1403        let total_bits_to_shift = end_bit - (start_bit + self.bit_width);
1404
1405        if total_bits_to_shift > 0 {
1406            self.shift_bits_left(start_bit, self.bit_width, total_bits_to_shift);
1407        }
1408
1409        self.len -= 1;
1410
1411        value_to_return
1412    }
1413
1414    /// Inserts an element at `index`, shifting all elements after it to the right.
1415    ///
1416    /// This operation is O(n), where n is the number of elements after `index`.
1417    ///
1418    /// # Panics
1419    ///
1420    /// Panics if `index` is out of bounds or if the `element` is too large to
1421    /// be represented by the configured `bit_width`.
1422    ///
1423    /// # Complexity
1424    ///
1425    /// This operation has a complexity of O(L), where L is the number of bits
1426    /// that need to be shifted. In the worst case (inserting at the beginning),
1427    /// this is proportional to the total number of bits in the vector
1428    /// (`self.len() * self.bit_width()`).
1429    ///
1430    /// # Panics
1431    ///
1432    /// Panics if `index` is out of bounds or if the `element` is too large to
1433    /// be represented by the configured `bit_width`.
1434    pub fn insert(&mut self, index: usize, element: T) {
1435        assert!(index <= self.len, "insert: index out of bounds");
1436        let value_w = <T as Storable<W>>::into_word(element);
1437        let bits_per_word = <W as Word>::BITS;
1438        let limit = if self.bit_width < bits_per_word {
1439            W::ONE << self.bit_width
1440        } else {
1441            W::max_value()
1442        };
1443        if self.bit_width < bits_per_word && value_w >= limit {
1444            panic!(
1445                "Value {:?} does not fit in the configured bit_width of {}",
1446                value_w, self.bit_width
1447            );
1448        }
1449        self.reserve(1);
1450        let start_shift_bit = index * self.bit_width;
1451        let num_bits_to_move = (self.len - index) * self.bit_width;
1452        if num_bits_to_move > 0 {
1453            self.shift_bits_right(start_shift_bit, self.bit_width, num_bits_to_move);
1454        }
1455        self.len += 1;
1456        unsafe {
1457            self.set_unchecked(index, value_w);
1458        }
1459    }
1460
1461    /// Shifts a range of bits to the left in-place.
1462    fn shift_bits_left(&mut self, start_bit: usize, shift_amount: usize, num_bits_to_move: usize) {
1463        if num_bits_to_move == 0 {
1464            return;
1465        }
1466
1467        let bits_per_word = <W as Word>::BITS;
1468
1469        // Fast path for word-aligned shifts, using `copy_within`.
1470        if shift_amount.is_multiple_of(bits_per_word) {
1471            let start_write_word = start_bit / bits_per_word;
1472            let start_read_word = (start_bit + shift_amount) / bits_per_word;
1473            let num_words_to_move = num_bits_to_move.div_ceil(bits_per_word);
1474
1475            if start_read_word < self.bits.len() {
1476                let read_end = (start_read_word + num_words_to_move).min(self.bits.len());
1477                self.bits
1478                    .copy_within(start_read_word..read_end, start_write_word);
1479            }
1480            return;
1481        }
1482
1483        // Slow path for unaligned shifts (word-at-a-time).
1484        let shift_rem = shift_amount % bits_per_word;
1485        let inv_shift_rem = bits_per_word - shift_rem;
1486
1487        let start_write_bit = start_bit;
1488        let end_write_bit = start_bit + num_bits_to_move;
1489
1490        let start_write_word = start_write_bit / bits_per_word;
1491        let end_write_word = (end_write_bit - 1) / bits_per_word;
1492
1493        for write_word_idx in start_write_word..=end_write_word {
1494            // Fetch the source data, which may span two source words.
1495            let read_bit = write_word_idx * bits_per_word + shift_rem;
1496            let read_word_idx = read_bit / bits_per_word;
1497
1498            let low_part = self.bits.get(read_word_idx).copied().unwrap_or(W::ZERO) >> shift_rem;
1499            let high_part =
1500                self.bits.get(read_word_idx + 1).copied().unwrap_or(W::ZERO) << inv_shift_rem;
1501
1502            let value_to_write = low_part | high_part;
1503
1504            // Create a mask for the bits we are about to modify.
1505            let mut mask = W::max_value();
1506            if write_word_idx == start_write_word {
1507                mask &= W::max_value() << (start_write_bit % bits_per_word);
1508            }
1509            if write_word_idx == end_write_word {
1510                let end_offset = end_write_bit % bits_per_word;
1511                if end_offset != 0 {
1512                    mask &= (W::ONE << end_offset).wrapping_sub(W::ONE);
1513                }
1514            }
1515
1516            self.bits[write_word_idx] =
1517                (self.bits[write_word_idx] & !mask) | (value_to_write & mask);
1518        }
1519    }
1520
1521    /// Shifts a range of bits to the right in-place.
1522    fn shift_bits_right(&mut self, start_bit: usize, shift_amount: usize, num_bits_to_move: usize) {
1523        if num_bits_to_move == 0 {
1524            return;
1525        }
1526
1527        let bits_per_word = <W as Word>::BITS;
1528
1529        // Ensure the vector has enough capacity and is resized to accommodate the shift.
1530        let required_end_bit = start_bit + shift_amount + num_bits_to_move;
1531        let required_words = required_end_bit.div_ceil(bits_per_word);
1532        let required_vec_len = required_words.saturating_add(1); // +1 for padding
1533        if self.bits.len() < required_vec_len {
1534            self.bits.resize(required_vec_len, W::ZERO);
1535        }
1536
1537        // Fast path for word-aligned shifts.
1538        if shift_amount.is_multiple_of(bits_per_word) {
1539            let start_read_word = start_bit / bits_per_word;
1540            let start_write_word = (start_bit + shift_amount) / bits_per_word;
1541            let num_words_to_move = num_bits_to_move.div_ceil(bits_per_word);
1542
1543            if start_read_word + num_words_to_move <= self.bits.len() {
1544                self.bits.copy_within(
1545                    start_read_word..start_read_word + num_words_to_move,
1546                    start_write_word,
1547                );
1548            }
1549        } else {
1550            // Slow path for unaligned shifts (iterating from right to left).
1551            let word_shift = shift_amount / bits_per_word;
1552            let shift_rem = shift_amount % bits_per_word;
1553            let inv_shift_rem = bits_per_word - shift_rem;
1554
1555            let start_write_bit = start_bit + shift_amount;
1556            let end_write_bit = start_write_bit + num_bits_to_move;
1557
1558            let start_write_word = start_write_bit / bits_per_word;
1559            let end_write_word = (end_write_bit - 1) / bits_per_word;
1560
1561            for write_word_idx in (start_write_word..=end_write_word).rev() {
1562                let read_word_idx = write_word_idx - word_shift;
1563
1564                // Fetch source data, which may span two words.
1565                let high_part =
1566                    self.bits.get(read_word_idx).copied().unwrap_or(W::ZERO) << shift_rem;
1567                let low_part = if read_word_idx > 0 {
1568                    self.bits.get(read_word_idx - 1).copied().unwrap_or(W::ZERO) >> inv_shift_rem
1569                } else {
1570                    W::ZERO
1571                };
1572                let value_to_write = low_part | high_part;
1573
1574                // Create a mask for the bits we are about to modify.
1575                let mut mask = W::max_value();
1576                if write_word_idx == start_write_word {
1577                    mask &= W::max_value() << (start_write_bit % bits_per_word);
1578                }
1579                if write_word_idx == end_write_word {
1580                    let end_offset = end_write_bit % bits_per_word;
1581                    if end_offset != 0 {
1582                        mask &= (W::ONE << end_offset).wrapping_sub(W::ONE);
1583                    }
1584                }
1585
1586                self.bits[write_word_idx] =
1587                    (self.bits[write_word_idx] & !mask) | (value_to_write & mask);
1588            }
1589        }
1590
1591        // Zero out the vacated bits at the beginning of the shifted region.
1592        let mut clear_bit = start_bit;
1593        let end_clear_bit = start_bit + shift_amount;
1594
1595        while clear_bit < end_clear_bit {
1596            let word_idx = clear_bit / bits_per_word;
1597            let offset = clear_bit % bits_per_word;
1598            let bits_to_clear = (bits_per_word - offset).min(end_clear_bit - clear_bit);
1599
1600            let mask = if bits_to_clear == bits_per_word {
1601                W::max_value()
1602            } else {
1603                ((W::ONE << bits_to_clear).wrapping_sub(W::ONE)) << offset
1604            };
1605
1606            if word_idx < self.bits.len() {
1607                self.bits[word_idx] &= !mask;
1608            }
1609            clear_bit += bits_to_clear;
1610        }
1611    }
1612
1613    /// Removes an element at `index` and returns it, replacing it with the last
1614    /// element of the vector.
1615    ///
1616    /// This operation is O(1) but does not preserve the order of elements.
1617    ///
1618    /// # Panics
1619    ///
1620    /// Panics if `index` is out of bounds.
1621    pub fn swap_remove(&mut self, index: usize) -> T {
1622        assert!(index < self.len, "swap_remove: index out of bounds");
1623
1624        if index == self.len - 1 {
1625            self.pop().unwrap()
1626        } else {
1627            let old_val = unsafe { self.get_unchecked(index) };
1628            let last_val = self.pop().unwrap(); // `pop` already decrements len
1629            self.set(index, last_val);
1630            old_val
1631        }
1632    }
1633
1634    /// Appends an element to the vector, returning an error if the value doesn't fit.
1635    ///
1636    /// # Errors
1637    ///
1638    /// Returns [`Error::ValueTooLarge`] if the `value` cannot be represented
1639    /// by the configured `bit_width`.
1640    pub fn try_push(&mut self, value: T) -> Result<(), Error> {
1641        let value_w = <T as Storable<W>>::into_word(value);
1642        let bits_per_word = <W as traits::Word>::BITS;
1643
1644        let limit = if self.bit_width < bits_per_word {
1645            W::ONE << self.bit_width
1646        } else {
1647            W::max_value()
1648        };
1649
1650        if self.bit_width < bits_per_word && value_w >= limit {
1651            return Err(Error::ValueTooLarge {
1652                value: value_w.to_u128().unwrap(),
1653                index: self.len,
1654                bit_width: self.bit_width,
1655            });
1656        }
1657
1658        self.push(value);
1659        Ok(())
1660    }
1661
1662    /// Extends the vector with the elements from a slice.
1663    ///
1664    /// # Panics
1665    ///
1666    /// Panics if any value in `other` does not fit within the `bit_width`.
1667    pub fn extend_from_slice(&mut self, other: &[T]) {
1668        if other.is_empty() {
1669            return;
1670        }
1671
1672        self.reserve(other.len());
1673
1674        // Pre-validate all values to ensure atomicity.
1675        let bits_per_word = <W as traits::Word>::BITS;
1676        let limit = if self.bit_width < bits_per_word {
1677            W::ONE << self.bit_width
1678        } else {
1679            W::max_value()
1680        };
1681        if self.bit_width < bits_per_word {
1682            for (i, &value) in other.iter().enumerate() {
1683                let value_w = <T as Storable<W>>::into_word(value);
1684                if value_w >= limit {
1685                    panic!(
1686                        "Value at index {} of slice ({:?}) does not fit in the configured bit_width of {}",
1687                        i, value_w, self.bit_width
1688                    );
1689                }
1690            }
1691        }
1692
1693        let old_len = self.len;
1694        let new_len = old_len + other.len();
1695
1696        // Ensure the underlying Vec has enough initialized words to write into.
1697        let required_total_bits = new_len * self.bit_width;
1698        let required_data_words = required_total_bits.div_ceil(bits_per_word);
1699        let required_vec_len = required_data_words.saturating_add(1); // Padding
1700        if self.bits.len() < required_vec_len {
1701            self.bits.resize(required_vec_len, W::ZERO);
1702        }
1703
1704        // Write the new values.
1705        for (i, &value) in other.iter().enumerate() {
1706            // SAFETY: We have reserved, resized, and validated the data.
1707            unsafe {
1708                self.set_unchecked(old_len + i, <T as Storable<W>>::into_word(value));
1709            }
1710        }
1711
1712        self.len = new_len;
1713    }
1714}
1715
1716// Mutable in-place operations.
1717impl<T, W, E, B> FixedVec<T, W, E, B>
1718where
1719    T: Storable<W>,
1720    W: Word,
1721    E: Endianness,
1722    B: AsRef<[W]> + AsMut<[W]>,
1723{
1724    /// Returns a mutable proxy for an element at `index`.
1725    ///
1726    /// This allows for syntax like `*vec.at_mut(i).unwrap() = new_value;`.
1727    ///
1728    /// Returns `None` if the index is out of bounds.
1729    pub fn at_mut(&mut self, index: usize) -> Option<MutProxy<'_, T, W, E, B>> {
1730        if index >= self.len {
1731            return None;
1732        }
1733        Some(MutProxy::new(self, index))
1734    }
1735
1736    /// Returns a mutable slice of the underlying storage words.
1737    ///
1738    /// # Safety
1739    ///
1740    /// Modifying the returned slice is logically unsafe. Any change to the bits
1741    /// can violate the invariants of the [`FixedVec`], leading to panics or
1742    /// incorrect results on subsequent method calls.
1743    pub unsafe fn as_mut_limbs(&mut self) -> &mut [W] {
1744        self.bits.as_mut()
1745    }
1746
1747    /// Sets the value of the element at `index`.
1748    ///
1749    /// # Panics
1750    ///
1751    /// Panics if `index` is out of bounds or if `value` is too large to be
1752    /// represented by the configured `bit_width`.
1753    ///
1754    /// # Examples
1755    ///
1756    /// ```
1757    /// use compressed_intvec::fixed::{FixedVec, UFixedVec, BitWidth};
1758    ///
1759    /// let data: &[u32] = &[10, 20, 30];
1760    /// let mut vec: UFixedVec<u32> = FixedVec::builder().bit_width(BitWidth::Explicit(7)).build(data).unwrap();
1761    ///
1762    /// vec.set(1, 99);
1763    /// assert_eq!(vec.get(1), Some(99));
1764    /// ```
1765    pub fn set(&mut self, index: usize, value: T) {
1766        assert!(
1767            index < self.len,
1768            "Index out of bounds: expected index < {}, got {}",
1769            self.len,
1770            index
1771        );
1772
1773        let value_w = <T as Storable<W>>::into_word(value);
1774        let bits_per_word = <W as traits::Word>::BITS;
1775
1776        let limit = if self.bit_width < bits_per_word {
1777            W::ONE << self.bit_width
1778        } else {
1779            W::max_value()
1780        };
1781
1782        if self.bit_width < bits_per_word && value_w >= limit {
1783            panic!(
1784                "Value {:?} does not fit in the configured bit_width of {}",
1785                value_w, self.bit_width
1786            );
1787        }
1788
1789        unsafe { self.set_unchecked(index, value_w) };
1790    }
1791
1792    /// Sets the value of the element at `index` without bounds or value checking.
1793    ///
1794    /// # Safety
1795    ///
1796    /// The caller must ensure that `index` is within bounds and that `value_w`
1797    /// fits within the configured `bit_width`. Failure to do so will result in
1798    /// data corruption or a panic.
1799    #[inline(always)]
1800    pub unsafe fn set_unchecked(&mut self, index: usize, value_w: W) {
1801        let bits_per_word = <W as traits::Word>::BITS;
1802        if self.bit_width == bits_per_word {
1803            *self.bits.as_mut().get_unchecked_mut(index) = if E::IS_LITTLE {
1804                value_w
1805            } else {
1806                value_w.to_be()
1807            };
1808            return;
1809        }
1810
1811        let bit_pos = index * self.bit_width;
1812        let word_index = bit_pos / bits_per_word;
1813        let bit_offset = bit_pos % bits_per_word;
1814
1815        let limbs = self.bits.as_mut();
1816
1817        if E::IS_LITTLE {
1818            // Fast path: the value fits entirely within a single word.
1819            if bit_offset + self.bit_width <= bits_per_word {
1820                let mut word = *limbs.get_unchecked(word_index);
1821                // Clear the target bits and then OR the new value.
1822                word &= !(self.mask << bit_offset);
1823                word |= value_w << bit_offset;
1824                *limbs.get_unchecked_mut(word_index) = word;
1825            } else {
1826                let remaining_bits_in_first_word = bits_per_word - bit_offset;
1827                let (left, right) = limbs.split_at_mut_unchecked(word_index + 1);
1828                let mut low_word_val = *left.get_unchecked(word_index);
1829                let low_mask = (<W as num_traits::NumCast>::from(1u8).unwrap() << bit_offset)
1830                    .wrapping_sub(<W as num_traits::NumCast>::from(1u8).unwrap());
1831                low_word_val &= low_mask;
1832                low_word_val |= value_w << bit_offset;
1833                *left.get_unchecked_mut(word_index) = low_word_val;
1834
1835                let mut high_word_val = *right.get_unchecked(0);
1836                high_word_val &= !(self.mask >> remaining_bits_in_first_word);
1837                high_word_val |= value_w >> remaining_bits_in_first_word;
1838                *right.get_unchecked_mut(0) = high_word_val;
1839            }
1840        } else {
1841            // Big-Endian set logic.
1842            if bit_offset + self.bit_width <= bits_per_word {
1843                let shift = bits_per_word - self.bit_width - bit_offset;
1844                let mask = self.mask << shift;
1845                let word = limbs.get_unchecked_mut(word_index);
1846                *word &= !mask.to_be();
1847                *word |= (value_w << shift).to_be();
1848            } else {
1849                let (left, right) = limbs.split_at_mut_unchecked(word_index + 1);
1850                let high_word = left.get_unchecked_mut(word_index);
1851                let low_word = right.get_unchecked_mut(0);
1852
1853                let bits_in_first = bits_per_word - bit_offset;
1854                let bits_in_second = self.bit_width - bits_in_first;
1855
1856                let high_mask =
1857                    (self.mask >> bits_in_second) << (bits_per_word - bits_in_first - bit_offset);
1858                let high_value = value_w >> bits_in_second;
1859                *high_word &= !high_mask.to_be();
1860                *high_word |= (high_value << (bits_per_word - bits_in_first - bit_offset)).to_be();
1861
1862                let low_mask = self.mask << (bits_per_word - bits_in_second);
1863                let low_value = value_w << (bits_per_word - bits_in_second);
1864                *low_word &= !low_mask.to_be();
1865                *low_word |= low_value.to_be();
1866            }
1867        }
1868    }
1869
1870    /// Sets the value of an element, returning an error if the value doesn't fit.
1871    ///
1872    /// # Errors
1873    ///
1874    /// Returns [`Error::ValueTooLarge`] if the `value` cannot be represented
1875    /// by the configured `bit_width`.
1876    ///
1877    /// # Panics
1878    ///
1879    /// Panics if `index` is out of bounds.
1880    pub fn try_set(&mut self, index: usize, value: T) -> Result<(), Error> {
1881        assert!(index < self.len, "try_set: index out of bounds");
1882
1883        let value_w = <T as Storable<W>>::into_word(value);
1884        let bits_per_word = <W as traits::Word>::BITS;
1885
1886        let limit = if self.bit_width < bits_per_word {
1887            W::ONE << self.bit_width
1888        } else {
1889            W::max_value()
1890        };
1891
1892        if self.bit_width < bits_per_word && value_w >= limit {
1893            return Err(Error::ValueTooLarge {
1894                value: value_w.to_u128().unwrap(),
1895                index,
1896                bit_width: self.bit_width,
1897            });
1898        }
1899
1900        unsafe { self.set_unchecked(index, value_w) };
1901        Ok(())
1902    }
1903
1904    /// Returns an iterator over non-overlapping, mutable chunks of the vector.
1905    ///
1906    /// # Panics
1907    ///
1908    /// Panics if `chunk_size` is 0.
1909    pub fn chunks_mut(&mut self, chunk_size: usize) -> iter_mut::ChunksMut<'_, T, W, E, B> {
1910        iter_mut::ChunksMut::new(self, chunk_size)
1911    }
1912
1913    /// Returns an unchecked mutable iterator over the elements of the vector.
1914    ///
1915    /// # Safety
1916    ///
1917    /// The caller must ensure that the iterator is not advanced beyond the
1918    /// vector's length.
1919    pub unsafe fn iter_mut_unchecked(&mut self) -> iter_mut::IterMutUnchecked<'_, T, W, E, B> {
1920        iter_mut::IterMutUnchecked::new(self)
1921    }
1922
1923    /// Applies a function to all elements in place, without checking if the
1924    /// returned values fit within the `bit_width`.
1925    ///
1926    /// # Safety
1927    ///
1928    /// The caller must ensure that the function `f` always returns a value
1929    /// that can be represented by `self.bit_width()` bits. Returning a value
1930    /// that is too large will result in data corruption.
1931    pub unsafe fn map_in_place_unchecked<F>(&mut self, mut f: F)
1932    where
1933        F: FnMut(T) -> T,
1934    {
1935        if E::IS_LITTLE {
1936            // This path operates on words directly for efficiency.
1937            let mut word_op = |word: W| -> W {
1938                let val_t = <T as Storable<W>>::from_word(word);
1939                let new_val_t = f(val_t);
1940                <T as Storable<W>>::into_word(new_val_t)
1941            };
1942            self.map_in_place_generic_word_op(&mut word_op);
1943        } else {
1944            // Fallback for BE, which is more complex to optimize at the word level.
1945            for i in 0..self.len {
1946                let old_val_t = self.get_unchecked(i);
1947                let new_val_t = f(old_val_t);
1948                self.set_unchecked(i, <T as Storable<W>>::into_word(new_val_t));
1949            }
1950        }
1951    }
1952
1953    /// Internal worker for `map_in_place_unchecked`, operating on `W`.
1954    unsafe fn map_in_place_generic_word_op<FW>(&mut self, f_w: &mut FW)
1955    where
1956        FW: FnMut(W) -> W,
1957    {
1958        let bit_width = self.bit_width;
1959        if self.len == 0 || bit_width == 0 {
1960            return;
1961        }
1962
1963        let bits_per_word = <W as Word>::BITS;
1964
1965        // Path for power-of-two bit widths that align with word boundaries.
1966        if bit_width.is_power_of_two() && bits_per_word % bit_width == 0 {
1967            let elems_per_word = bits_per_word / bit_width;
1968            let mask = self.mask;
1969            let num_full_words = self.len / elems_per_word;
1970
1971            for word_idx in 0..num_full_words {
1972                let old_word = *self.bits.as_ref().get_unchecked(word_idx);
1973                let mut new_word = W::ZERO;
1974                for i in 0..elems_per_word {
1975                    let shift = i * bit_width;
1976                    let old_val_w = (old_word >> shift) & mask;
1977                    new_word |= f_w(old_val_w) << shift;
1978                }
1979                *self.bits.as_mut().get_unchecked_mut(word_idx) = new_word;
1980            }
1981            // Process remaining elements individually.
1982            let start_idx = num_full_words * elems_per_word;
1983            for i in start_idx..self.len {
1984                let old_val_t = self.get(i).unwrap();
1985                let old_val_w = <T as Storable<W>>::into_word(old_val_t);
1986                self.set_unchecked(i, f_w(old_val_w));
1987            }
1988            return;
1989        }
1990
1991        // Generic path for non-power-of-two bit widths.
1992        let limbs = self.bits.as_mut();
1993        let num_words = (self.len * bit_width).div_ceil(bits_per_word);
1994        let last_word_idx = num_words.saturating_sub(1);
1995
1996        let mut write_buffer = W::ZERO;
1997        let mut read_buffer = *limbs.get_unchecked(0);
1998        let mut global_bit_offset = 0;
1999
2000        for word_idx in 0..last_word_idx {
2001            let lower_word_boundary = word_idx * bits_per_word;
2002            let upper_word_boundary = lower_word_boundary + bits_per_word;
2003
2004            while global_bit_offset + bit_width <= upper_word_boundary {
2005                let offset_in_word = global_bit_offset - lower_word_boundary;
2006                let element = (read_buffer >> offset_in_word) & self.mask;
2007                write_buffer |= f_w(element) << offset_in_word;
2008                global_bit_offset += bit_width;
2009            }
2010
2011            let next_word = *limbs.get_unchecked(word_idx + 1);
2012            let mut new_write_buffer = W::ZERO;
2013
2014            if upper_word_boundary != global_bit_offset {
2015                let elem_idx = global_bit_offset / bit_width;
2016                if elem_idx >= self.len {
2017                    *limbs.get_unchecked_mut(word_idx) = write_buffer;
2018                    return;
2019                }
2020
2021                let remainder_in_word = upper_word_boundary - global_bit_offset;
2022                let offset_in_word = global_bit_offset - lower_word_boundary;
2023
2024                let element = ((read_buffer >> offset_in_word) | (next_word << remainder_in_word))
2025                    & self.mask;
2026                let new_element = f_w(element);
2027
2028                write_buffer |= new_element << offset_in_word;
2029                new_write_buffer = new_element >> remainder_in_word;
2030
2031                global_bit_offset += bit_width;
2032            }
2033
2034            *limbs.get_unchecked_mut(word_idx) = write_buffer;
2035
2036            read_buffer = next_word;
2037            write_buffer = new_write_buffer;
2038        }
2039
2040        let lower_word_boundary = last_word_idx * bits_per_word;
2041
2042        while global_bit_offset < self.len * bit_width {
2043            let offset_in_word = global_bit_offset - lower_word_boundary;
2044            let element = (read_buffer >> offset_in_word) & self.mask;
2045            write_buffer |= f_w(element) << offset_in_word;
2046            global_bit_offset += bit_width;
2047        }
2048
2049        *limbs.get_unchecked_mut(last_word_idx) = write_buffer;
2050    }
2051
2052    /// Applies a function to all elements in the vector, modifying them in-place.
2053    ///
2054    /// # Panics
2055    ///
2056    /// Panics if the function `f` returns a value that does not fit within the
2057    /// configured `bit_width`.
2058    ///
2059    /// # Examples
2060    ///
2061    /// ```
2062    /// use compressed_intvec::fixed::{FixedVec, BitWidth, UFixedVec};
2063    ///
2064    /// // Values up to 9*2=18, requires 5 bits. We must build with enough space.
2065    /// let initial_data: Vec<u32> = (0..10).collect();
2066    /// let mut vec: UFixedVec<u32> = FixedVec::builder()
2067    ///     .bit_width(BitWidth::Explicit(5))
2068    ///     .build(&initial_data)
2069    ///     .unwrap();
2070    ///
2071    /// vec.map_in_place(|x| x * 2);
2072    ///
2073    /// for i in 0..vec.len() {
2074    ///     assert_eq!(vec.get(i), Some(i as u32 * 2));
2075    /// }
2076    /// ```
2077    pub fn map_in_place<F>(&mut self, mut f: F)
2078    where
2079        F: FnMut(T) -> T,
2080    {
2081        let bit_width = self.bit_width;
2082        let limit = if bit_width < <W as Word>::BITS {
2083            W::ONE << bit_width
2084        } else {
2085            W::max_value()
2086        };
2087
2088        let safe_f = |value: T| {
2089            let new_value = f(value);
2090            let new_value_w = <T as Storable<W>>::into_word(new_value);
2091            if bit_width < <W as Word>::BITS && new_value_w >= limit {
2092                panic!(
2093                    "map_in_place: returned value {new_value_w:?} does not fit in bit_width {bit_width}"
2094                );
2095            }
2096            new_value
2097        };
2098
2099        // SAFETY: The `safe_f` wrapper ensures that any value passed to the
2100        // underlying unsafe function is valid for the vector's bit_width.
2101        unsafe {
2102            self.map_in_place_unchecked(safe_f);
2103        }
2104    }
2105
2106    /// Replaces the element at `index` with a new `value`, returning the old value.
2107    ///
2108    /// # Panics
2109    ///
2110    /// Panics if `index` is out of bounds or if `value` does not fit within
2111    /// the configured `bit_width`.
2112    pub fn replace(&mut self, index: usize, value: T) -> T {
2113        assert!(index < self.len, "replace: index out of bounds");
2114
2115        let old_value = unsafe { self.get_unchecked(index) };
2116        self.set(index, value);
2117        old_value
2118    }
2119
2120    /// Swaps the elements at indices `a` and `b`.
2121    ///
2122    /// # Panics
2123    ///
2124    /// Panics if `a` or `b` are out of bounds.
2125    pub fn swap(&mut self, a: usize, b: usize) {
2126        assert!(a < self.len, "swap: index a out of bounds");
2127        assert!(b < self.len, "swap: index b out of bounds");
2128
2129        if a == b {
2130            return;
2131        }
2132
2133        unsafe {
2134            let val_a = self.get_unchecked(a);
2135            let val_b = self.get_unchecked(b);
2136            self.set_unchecked(a, <T as Storable<W>>::into_word(val_b));
2137            self.set_unchecked(b, <T as Storable<W>>::into_word(val_a));
2138        }
2139    }
2140
2141    /// Returns a mutable proxy to the first element, or `None` if empty.
2142    pub fn first_mut(&mut self) -> Option<MutProxy<'_, T, W, E, B>> {
2143        if self.is_empty() {
2144            None
2145        } else {
2146            self.at_mut(0)
2147        }
2148    }
2149
2150    /// Returns a mutable proxy to the last element, or `None` if empty.
2151    pub fn last_mut(&mut self) -> Option<MutProxy<'_, T, W, E, B>> {
2152        if self.is_empty() {
2153            None
2154        } else {
2155            let len = self.len();
2156            self.at_mut(len - 1)
2157        }
2158    }
2159
2160    /// Returns the first element of the vector, or `None` if empty.
2161    pub fn first(&self) -> Option<T> {
2162        if self.is_empty() {
2163            None
2164        } else {
2165            Some(unsafe { self.get_unchecked(0) })
2166        }
2167    }
2168
2169    /// Returns the last element of the vector, or `None` if empty.
2170    pub fn last(&self) -> Option<T> {
2171        if self.is_empty() {
2172            None
2173        } else {
2174            let len = self.len();
2175            Some(unsafe { self.get_unchecked(len - 1) })
2176        }
2177    }
2178
2179    /// Splits the vector into two mutable slices at `mid`.
2180    ///
2181    /// # Panics
2182    ///
2183    /// Panics if `mid > len`.
2184    pub fn split_at_mut(
2185        &mut self,
2186        mid: usize,
2187    ) -> (
2188        slice::FixedVecSlice<&mut Self>,
2189        slice::FixedVecSlice<&mut Self>,
2190    ) {
2191        assert!(mid <= self.len, "mid > len in split_at_mut");
2192        // SAFETY: The two slices are guaranteed not to overlap.
2193        unsafe {
2194            let ptr = self as *mut Self;
2195            let left = slice::FixedVecSlice::new(&mut *ptr, 0..mid);
2196            let right = slice::FixedVecSlice::new(&mut *ptr, mid..self.len());
2197            (left, right)
2198        }
2199    }
2200
2201    /// Returns a mutable iterator over the elements of the vector.
2202    pub fn iter_mut(&mut self) -> iter_mut::IterMut<'_, T, W, E, B> {
2203        iter_mut::IterMut::new(self)
2204    }
2205
2206    /// Rotates the elements of the vector in-place such that the element at `mid`
2207    /// becomes the first element.
2208    ///
2209    /// # Panics
2210    ///
2211    /// Panics if `mid > len`.
2212    pub fn rotate_left(&mut self, mid: usize) {
2213        assert!(mid <= self.len, "mid > len in rotate_left");
2214        if self.is_empty() || mid == 0 || mid == self.len {
2215            return;
2216        }
2217        // A simple, correct implementation.
2218        let mut temp = Vec::with_capacity(mid);
2219        for i in 0..mid {
2220            temp.push(unsafe { self.get_unchecked(i) });
2221        }
2222        for i in mid..self.len {
2223            let val = unsafe { self.get_unchecked(i) };
2224            unsafe { self.set_unchecked(i - mid, <T as Storable<W>>::into_word(val)) };
2225        }
2226        for (i, val) in temp.into_iter().enumerate() {
2227            unsafe { self.set_unchecked(self.len - mid + i, <T as Storable<W>>::into_word(val)) };
2228        }
2229    }
2230
2231    /// Rotates the elements of the vector in-place such that the element at
2232    /// `len - k` becomes the first element.
2233    ///
2234    /// # Panics
2235    ///
2236    /// Panics if `k > len`.
2237    pub fn rotate_right(&mut self, k: usize) {
2238        assert!(k <= self.len, "k > len in rotate_right");
2239        if self.is_empty() || k == 0 || k == self.len {
2240            return;
2241        }
2242        self.rotate_left(self.len - k);
2243    }
2244
2245    /// Fills the vector with the given value.
2246    ///
2247    /// # Panics
2248    ///
2249    /// Panics if `value` does not fit in the configured `bit_width`.
2250    pub fn fill(&mut self, value: T) {
2251        let value_w = <T as Storable<W>>::into_word(value);
2252        let bits_per_word = <W as traits::Word>::BITS;
2253        let limit = if self.bit_width < bits_per_word {
2254            W::ONE << self.bit_width
2255        } else {
2256            W::max_value()
2257        };
2258        if self.bit_width < bits_per_word && value_w >= limit {
2259            panic!(
2260                "Value {:?} does not fit in the configured bit_width of {}",
2261                value_w, self.bit_width
2262            );
2263        }
2264
2265        for i in 0..self.len() {
2266            unsafe { self.set_unchecked(i, value_w) };
2267        }
2268    }
2269
2270    /// Fills the vector with values returned by a closure.
2271    ///
2272    /// # Panics
2273    ///
2274    /// Panics if the closure returns a value that does not fit in the configured
2275    /// `bit_width`.
2276    pub fn fill_with<F>(&mut self, mut f: F)
2277    where
2278        F: FnMut() -> T,
2279    {
2280        let bits_per_word = <W as traits::Word>::BITS;
2281        let limit = if self.bit_width < bits_per_word {
2282            W::ONE << self.bit_width
2283        } else {
2284            W::max_value()
2285        };
2286
2287        for i in 0..self.len() {
2288            let value = f();
2289            let value_w = <T as Storable<W>>::into_word(value);
2290            if self.bit_width < bits_per_word && value_w >= limit {
2291                panic!(
2292                    "Value {:?} returned by closure does not fit in bit_width {}",
2293                    value_w, self.bit_width
2294                );
2295            }
2296            unsafe { self.set_unchecked(i, value_w) };
2297        }
2298    }
2299
2300    /// Copies a sequence of elements from a source [`FixedVec`] into this one.
2301    ///
2302    /// # Panics
2303    ///
2304    /// Panics if the source and destination vectors do not have the same `bit_width`,
2305    /// or if the source or destination ranges are out of bounds.
2306    pub fn copy_from_slice(
2307        &mut self,
2308        src: &Self,
2309        src_range: std::ops::Range<usize>,
2310        dest_index: usize,
2311    ) {
2312        assert_eq!(
2313            self.bit_width, src.bit_width,
2314            "bit_width mismatch in copy_from_slice"
2315        );
2316        assert!(src_range.start <= src_range.end, "source range start > end");
2317        assert!(src_range.end <= src.len(), "source range out of bounds");
2318        let len = src_range.len();
2319        assert!(
2320            dest_index + len <= self.len(),
2321            "destination range out of bounds"
2322        );
2323
2324        if len == 0 {
2325            return;
2326        }
2327
2328        // Fast path: if bit alignments are the same, we can do word-level copies.
2329        let bit_width = self.bit_width;
2330        let bits_per_word = <W as Word>::BITS;
2331        let src_bit_offset = (src_range.start * bit_width) % bits_per_word;
2332        let dest_bit_offset = (dest_index * bit_width) % bits_per_word;
2333
2334        if src_bit_offset == dest_bit_offset {
2335            let src_word_start = (src_range.start * bit_width) / bits_per_word;
2336            let dest_word_start = (dest_index * bit_width) / bits_per_word;
2337            let total_bits_to_copy = len * bit_width;
2338            let num_words_to_copy = total_bits_to_copy.div_ceil(bits_per_word);
2339
2340            let src_words = &src.bits.as_ref()[src_word_start..src_word_start + num_words_to_copy];
2341            let dest_words =
2342                &mut self.bits.as_mut()[dest_word_start..dest_word_start + num_words_to_copy];
2343
2344            // If the last word is not fully copied, we need to mask it.
2345            let residual_bits = total_bits_to_copy % bits_per_word;
2346            if residual_bits == 0 {
2347                dest_words.copy_from_slice(src_words);
2348            } else {
2349                if num_words_to_copy > 1 {
2350                    dest_words[..num_words_to_copy - 1]
2351                        .copy_from_slice(&src_words[..num_words_to_copy - 1]);
2352                }
2353                let last_word_mask = (W::ONE << residual_bits).wrapping_sub(W::ONE);
2354                let dest_last_word = &mut dest_words[num_words_to_copy - 1];
2355                let src_last_word = &src_words[num_words_to_copy - 1];
2356                *dest_last_word =
2357                    (*dest_last_word & !last_word_mask) | (*src_last_word & last_word_mask);
2358            }
2359        } else {
2360            // Slow path: copy element by element if alignments differ.
2361            if dest_index > src_range.start && dest_index < src_range.end {
2362                // Copy backwards if ranges overlap and dest is after src.
2363                for i in (0..len).rev() {
2364                    let val = unsafe { src.get_unchecked(src_range.start + i) };
2365                    unsafe {
2366                        self.set_unchecked(dest_index + i, <T as Storable<W>>::into_word(val))
2367                    };
2368                }
2369            } else {
2370                for i in 0..len {
2371                    let val = unsafe { src.get_unchecked(src_range.start + i) };
2372                    unsafe {
2373                        self.set_unchecked(dest_index + i, <T as Storable<W>>::into_word(val))
2374                    };
2375                }
2376            }
2377        }
2378    }
2379}
2380
2381impl<T, W, E, B, B2> PartialEq<FixedVec<T, W, E, B2>> for FixedVec<T, W, E, B>
2382where
2383    T: Storable<W> + PartialEq,
2384    W: Word,
2385    E: Endianness,
2386    B: AsRef<[W]>,
2387    B2: AsRef<[W]>,
2388{
2389    /// Checks for equality between two [`FixedVec`] instances.
2390    ///
2391    /// It first checks `len` and `bit_width`, then the underlying storage.
2392    fn eq(&self, other: &FixedVec<T, W, E, B2>) -> bool {
2393        if self.len() != other.len() || self.bit_width() != other.bit_width() {
2394            return false;
2395        }
2396        self.as_limbs() == other.as_limbs()
2397    }
2398}
2399
2400/// Implements `PartialEq` for comparing a [`FixedVec`] with a standard slice.
2401impl<T, W, E, B, T2> PartialEq<&[T2]> for FixedVec<T, W, E, B>
2402where
2403    T: Storable<W> + PartialEq<T2>,
2404    W: Word,
2405    E: Endianness,
2406    B: AsRef<[W]>,
2407    T2: Clone,
2408{
2409    fn eq(&self, other: &&[T2]) -> bool {
2410        if self.len() != other.len() {
2411            return false;
2412        }
2413        self.iter().zip(other.iter()).all(|(a, b)| a == *b)
2414    }
2415}
2416
2417impl<T, W, E> Extend<T> for FixedVec<T, W, E, Vec<W>>
2418where
2419    T: Storable<W> + ToPrimitive,
2420    W: Word,
2421    E: Endianness,
2422{
2423    /// Extends the vector with the contents of an iterator.
2424    ///
2425    /// # Panics
2426    ///
2427    /// Panics if any value from the iterator does not fit within the
2428    /// configured `bit_width`.
2429    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
2430        let iter = iter.into_iter();
2431        let (lower_bound, _) = iter.size_hint();
2432        self.reserve(lower_bound);
2433        for item in iter {
2434            self.push(item);
2435        }
2436    }
2437}
2438
2439impl<T, W, E> From<FixedVec<T, W, E, Vec<W>>> for FixedVec<T, W, E, Box<[W]>>
2440where
2441    T: Storable<W>,
2442    W: Word,
2443    E: Endianness,
2444{
2445    /// Converts a `Vec`-backed [`FixedVec`] into a `Box<[]>`-backed [`FixedVec`].
2446    fn from(vec: FixedVec<T, W, E, Vec<W>>) -> Self {
2447        unsafe { Self::new_unchecked(vec.bits.into_boxed_slice(), vec.len, vec.bit_width) }
2448    }
2449}
2450
2451impl<T, W, E> From<FixedVec<T, W, E, Box<[W]>>> for FixedVec<T, W, E, Vec<W>>
2452where
2453    T: Storable<W>,
2454    W: Word,
2455    E: Endianness,
2456{
2457    /// Converts a `Box<[]>`-backed [`FixedVec`] into a `Vec`-backed [`FixedVec`].
2458    fn from(vec: FixedVec<T, W, E, Box<[W]>>) -> Self {
2459        unsafe { Self::new_unchecked(vec.bits.into_vec(), vec.len, vec.bit_width) }
2460    }
2461}
2462
2463impl<'a, T> TryFrom<&'a [T]> for FixedVec<T, <T as DefaultParams>::W, <T as DefaultParams>::E>
2464where
2465    T: Storable<<T as DefaultParams>::W> + DefaultParams,
2466    <T as DefaultParams>::W: Word,
2467    <T as DefaultParams>::E: Endianness,
2468    dsi_bitstream::impls::BufBitWriter<
2469        <T as DefaultParams>::E,
2470        dsi_bitstream::impls::MemWordWriterVec<
2471            <T as DefaultParams>::W,
2472            Vec<<T as DefaultParams>::W>,
2473        >,
2474    >: dsi_bitstream::prelude::BitWrite<<T as DefaultParams>::E, Error = std::convert::Infallible>,
2475{
2476    type Error = Error;
2477
2478    /// Creates a [`FixedVec`] from a slice using [`BitWidth::Minimal`] and default parameters.
2479    ///
2480    /// This is a convenience method equivalent to `FixedVec::builder().build(slice)`.
2481    /// It uses the default [`Word`] ([`usize`]) and [`Endianness`] ([`LE`]) associated with the element type `T`.
2482    ///
2483    /// # Examples
2484    ///
2485    /// ```
2486    /// use compressed_intvec::fixed::{UFixedVec, SFixedVec};
2487    /// use std::convert::TryFrom;
2488    ///
2489    /// // For unsigned types
2490    /// let data_u: &[u32] = &[10, 20, 30];
2491    /// let vec_u = UFixedVec::<u32>::try_from(data_u).unwrap();
2492    /// assert_eq!(vec_u.bit_width(), 5);
2493    ///
2494    /// // For signed types
2495    /// let data_s: &[i16] = &[-10, 0, 10];
2496    /// let vec_s = SFixedVec::<i16>::try_from(data_s).unwrap();
2497    /// assert_eq!(vec_s.bit_width(), 5);
2498    /// ```
2499    fn try_from(slice: &'a [T]) -> Result<Self, Self::Error> {
2500        Self::builder().bit_width(BitWidth::Minimal).build(slice)
2501    }
2502}