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}