segmented_vec/
slice.rs

1//! Slice types for SegmentedVec.
2//!
3//! This module provides `SegmentedSlice` and `SegmentedSliceMut` types that
4//! behave like `&[T]` and `&mut [T]` but work with non-contiguous memory.
5
6use std::cmp::Ordering;
7use std::ops::{
8    Index, IndexMut, Range, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive,
9};
10
11use crate::SegmentedVec;
12
13/// An immutable slice view into a `SegmentedVec`.
14///
15/// This type behaves like `&[T]` but works with non-contiguous memory.
16///
17/// # Example
18///
19/// ```
20/// use segmented_vec::SegmentedVec;
21///
22/// let mut vec: SegmentedVec<i32, 4> = SegmentedVec::new();
23/// vec.extend(0..10);
24///
25/// let slice = vec.as_slice();
26/// assert_eq!(slice.len(), 10);
27/// assert_eq!(slice[0], 0);
28/// assert_eq!(slice.first(), Some(&0));
29/// ```
30#[derive(Clone, Copy)]
31pub struct SegmentedSlice<'a, T, const PREALLOC: usize> {
32    vec: &'a SegmentedVec<T, PREALLOC>,
33    start: usize,
34    len: usize,
35}
36
37impl<'a, T, const PREALLOC: usize> SegmentedSlice<'a, T, PREALLOC> {
38    /// Creates a new slice covering the entire vector.
39    #[inline]
40    pub(crate) fn new(vec: &'a SegmentedVec<T, PREALLOC>) -> Self {
41        Self {
42            vec,
43            start: 0,
44            len: vec.len(),
45        }
46    }
47
48    /// Creates a new slice covering a range of the vector.
49    #[inline]
50    pub(crate) fn from_range(vec: &'a SegmentedVec<T, PREALLOC>, start: usize, end: usize) -> Self {
51        debug_assert!(start <= end && end <= vec.len());
52        Self {
53            vec,
54            start,
55            len: end - start,
56        }
57    }
58
59    /// Returns the number of elements in the slice.
60    #[inline]
61    pub const fn len(&self) -> usize {
62        self.len
63    }
64
65    /// Returns `true` if the slice is empty.
66    #[inline]
67    pub const fn is_empty(&self) -> bool {
68        self.len == 0
69    }
70
71    /// Returns a reference to the element at the given index, or `None` if out of bounds.
72    #[inline]
73    pub fn get(&self, index: usize) -> Option<&T> {
74        if index < self.len() {
75            Some(unsafe { self.vec.unchecked_at(self.start + index) })
76        } else {
77            None
78        }
79    }
80
81    /// Returns a reference to the first element, or `None` if empty.
82    #[inline]
83    pub fn first(&self) -> Option<&T> {
84        self.get(0)
85    }
86
87    /// Returns a reference to the last element, or `None` if empty.
88    #[inline]
89    pub fn last(&self) -> Option<&T> {
90        if self.is_empty() {
91            None
92        } else {
93            self.get(self.len() - 1)
94        }
95    }
96
97    /// Returns references to the first and rest of the elements, or `None` if empty.
98    #[inline]
99    pub fn split_first(&self) -> Option<(&T, SegmentedSlice<'a, T, PREALLOC>)> {
100        if self.is_empty() {
101            None
102        } else {
103            Some((
104                unsafe { self.vec.unchecked_at(self.start) },
105                SegmentedSlice::from_range(self.vec, self.start + 1, self.start + self.len),
106            ))
107        }
108    }
109
110    /// Returns references to the last and rest of the elements, or `None` if empty.
111    #[inline]
112    pub fn split_last(&self) -> Option<(&T, SegmentedSlice<'a, T, PREALLOC>)> {
113        if self.is_empty() {
114            None
115        } else {
116            let end = self.start + self.len;
117            Some((
118                unsafe { self.vec.unchecked_at(end - 1) },
119                SegmentedSlice::from_range(self.vec, self.start, end - 1),
120            ))
121        }
122    }
123
124    /// Divides the slice into two at an index.
125    ///
126    /// The first will contain all indices from `[0, mid)` and the second will contain
127    /// all indices from `[mid, len)`.
128    ///
129    /// # Panics
130    ///
131    /// Panics if `mid > len`.
132    #[inline]
133    pub fn split_at(
134        &self,
135        mid: usize,
136    ) -> (
137        SegmentedSlice<'a, T, PREALLOC>,
138        SegmentedSlice<'a, T, PREALLOC>,
139    ) {
140        assert!(mid <= self.len());
141        (
142            SegmentedSlice::from_range(self.vec, self.start, self.start + mid),
143            SegmentedSlice::from_range(self.vec, self.start + mid, self.start + self.len),
144        )
145    }
146
147    /// Returns an iterator over the slice.
148    #[inline]
149    pub fn iter(&self) -> SliceIter<'a, T, PREALLOC> {
150        SliceIter {
151            vec: self.vec,
152            start: self.start,
153            end: self.start + self.len,
154        }
155    }
156
157    /// Returns `true` if the slice contains an element with the given value.
158    #[inline]
159    pub fn contains(&self, x: &T) -> bool
160    where
161        T: PartialEq,
162    {
163        self.iter().any(|elem| elem == x)
164    }
165
166    /// Returns `true` if `needle` is a prefix of the slice.
167    pub fn starts_with(&self, needle: &[T]) -> bool
168    where
169        T: PartialEq,
170    {
171        if needle.len() > self.len() {
172            return false;
173        }
174        for (i, item) in needle.iter().enumerate() {
175            if self.get(i) != Some(item) {
176                return false;
177            }
178        }
179        true
180    }
181
182    /// Returns `true` if `needle` is a suffix of the slice.
183    pub fn ends_with(&self, needle: &[T]) -> bool
184    where
185        T: PartialEq,
186    {
187        if needle.len() > self.len() {
188            return false;
189        }
190        let start = self.len() - needle.len();
191        for (i, item) in needle.iter().enumerate() {
192            if self.get(start + i) != Some(item) {
193                return false;
194            }
195        }
196        true
197    }
198
199    /// Binary searches this slice for a given element.
200    ///
201    /// If the value is found, returns `Ok(index)`. If not found, returns
202    /// `Err(index)` where `index` is the position where the element could be inserted.
203    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
204    where
205        T: Ord,
206    {
207        self.binary_search_by(|elem| elem.cmp(x))
208    }
209
210    /// Binary searches this slice with a comparator function.
211    pub fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize>
212    where
213        F: FnMut(&T) -> Ordering,
214    {
215        let mut left = 0;
216        let mut right = self.len();
217
218        while left < right {
219            let mid = left + (right - left) / 2;
220            let elem = unsafe { self.vec.unchecked_at(self.start + mid) };
221            match f(elem) {
222                Ordering::Less => left = mid + 1,
223                Ordering::Greater => right = mid,
224                Ordering::Equal => return Ok(mid),
225            }
226        }
227        Err(left)
228    }
229
230    /// Binary searches this slice with a key extraction function.
231    pub fn binary_search_by_key<B, F>(&self, b: &B, mut f: F) -> Result<usize, usize>
232    where
233        F: FnMut(&T) -> B,
234        B: Ord,
235    {
236        self.binary_search_by(|elem| f(elem).cmp(b))
237    }
238
239    /// Returns a subslice with elements in the given range.
240    ///
241    /// # Panics
242    ///
243    /// Panics if the range is out of bounds.
244    #[inline]
245    pub fn slice<R>(self, range: R) -> SegmentedSlice<'a, T, PREALLOC>
246    where
247        R: SliceIndex<'a, T, PREALLOC, Output = SegmentedSlice<'a, T, PREALLOC>>,
248    {
249        range.index(self)
250    }
251
252    /// Copies the elements into a new `Vec`.
253    pub fn to_vec(&self) -> Vec<T>
254    where
255        T: Clone,
256    {
257        self.iter().cloned().collect()
258    }
259
260    /// Returns a reference to an element without bounds checking.
261    ///
262    /// # Safety
263    ///
264    /// Calling this method with an out-of-bounds index is undefined behavior.
265    #[inline]
266    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
267        debug_assert!(index < self.len());
268        unsafe { self.vec.unchecked_at(self.start + index) }
269    }
270
271    /// Checks if the elements of this slice are sorted.
272    ///
273    /// That is, for each element `a` and its following element `b`, `a <= b` must hold.
274    pub fn is_sorted(&self) -> bool
275    where
276        T: PartialOrd,
277    {
278        self.is_sorted_by(|a, b| a <= b)
279    }
280
281    /// Checks if the elements of this slice are sorted using the given comparator function.
282    pub fn is_sorted_by<F>(&self, mut compare: F) -> bool
283    where
284        F: FnMut(&T, &T) -> bool,
285    {
286        let len = self.len();
287        if len <= 1 {
288            return true;
289        }
290        for i in 0..len - 1 {
291            let a = unsafe { self.vec.unchecked_at(self.start + i) };
292            let b = unsafe { self.vec.unchecked_at(self.start + i + 1) };
293            if !compare(a, b) {
294                return false;
295            }
296        }
297        true
298    }
299
300    /// Checks if the elements of this slice are sorted using the given key extraction function.
301    pub fn is_sorted_by_key<K, F>(&self, mut f: F) -> bool
302    where
303        F: FnMut(&T) -> K,
304        K: PartialOrd,
305    {
306        self.is_sorted_by(|a, b| f(a) <= f(b))
307    }
308
309    /// Returns the index of the partition point according to the given predicate.
310    ///
311    /// The slice is assumed to be partitioned according to the given predicate.
312    /// This returns the first index where the predicate returns `false`.
313    pub fn partition_point<P>(&self, mut pred: P) -> usize
314    where
315        P: FnMut(&T) -> bool,
316    {
317        let mut left = 0;
318        let mut right = self.len();
319
320        while left < right {
321            let mid = left + (right - left) / 2;
322            let elem = unsafe { self.vec.unchecked_at(self.start + mid) };
323            if pred(elem) {
324                left = mid + 1;
325            } else {
326                right = mid;
327            }
328        }
329        left
330    }
331
332    /// Returns an iterator over all contiguous windows of length `size`.
333    ///
334    /// The windows overlap. If the slice is shorter than `size`, the iterator returns no values.
335    ///
336    /// # Panics
337    ///
338    /// Panics if `size` is 0.
339    pub fn windows(&self, size: usize) -> Windows<'a, T, PREALLOC> {
340        assert!(size != 0);
341        Windows {
342            vec: self.vec,
343            start: self.start,
344            end: self.start + self.len,
345            size,
346        }
347    }
348
349    /// Returns an iterator over `chunk_size` elements of the slice at a time.
350    ///
351    /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length
352    /// of the slice, then the last chunk will not have length `chunk_size`.
353    ///
354    /// # Panics
355    ///
356    /// Panics if `chunk_size` is 0.
357    pub fn chunks(&self, chunk_size: usize) -> Chunks<'a, T, PREALLOC> {
358        assert!(chunk_size != 0);
359        Chunks {
360            vec: self.vec,
361            start: self.start,
362            end: self.start + self.len,
363            chunk_size,
364        }
365    }
366
367    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end.
368    ///
369    /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length
370    /// of the slice, then the last chunk will not have length `chunk_size`.
371    ///
372    /// # Panics
373    ///
374    /// Panics if `chunk_size` is 0.
375    pub fn rchunks(&self, chunk_size: usize) -> RChunks<'a, T, PREALLOC> {
376        assert!(chunk_size != 0);
377        RChunks {
378            vec: self.vec,
379            start: self.start,
380            end: self.start + self.len,
381            chunk_size,
382        }
383    }
384
385    /// Returns an iterator over `chunk_size` elements of the slice at a time.
386    ///
387    /// If `chunk_size` does not divide the length, the last up to `chunk_size-1`
388    /// elements will be omitted and can be retrieved from the `remainder` function
389    /// of the iterator.
390    ///
391    /// # Panics
392    ///
393    /// Panics if `chunk_size` is 0.
394    pub fn chunks_exact(&self, chunk_size: usize) -> ChunksExact<'a, T, PREALLOC> {
395        assert!(chunk_size != 0);
396        let end = self.start + self.len;
397        let remainder_start = self.start + (self.len / chunk_size) * chunk_size;
398        ChunksExact {
399            vec: self.vec,
400            start: self.start,
401            end: remainder_start,
402            remainder_end: end,
403            chunk_size,
404        }
405    }
406}
407
408impl<'a, T: std::fmt::Debug, const PREALLOC: usize> std::fmt::Debug
409    for SegmentedSlice<'a, T, PREALLOC>
410{
411    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
412        f.debug_list().entries(self.iter()).finish()
413    }
414}
415
416impl<'a, T: PartialEq, const PREALLOC: usize> PartialEq for SegmentedSlice<'a, T, PREALLOC> {
417    fn eq(&self, other: &Self) -> bool {
418        if self.len() != other.len() {
419            return false;
420        }
421        self.iter().zip(other.iter()).all(|(a, b)| a == b)
422    }
423}
424
425impl<'a, T: PartialEq, const PREALLOC: usize> PartialEq<[T]> for SegmentedSlice<'a, T, PREALLOC> {
426    fn eq(&self, other: &[T]) -> bool {
427        if self.len() != other.len() {
428            return false;
429        }
430        self.iter().zip(other.iter()).all(|(a, b)| a == b)
431    }
432}
433
434impl<'a, T: PartialEq, const PREALLOC: usize> PartialEq<Vec<T>>
435    for SegmentedSlice<'a, T, PREALLOC>
436{
437    fn eq(&self, other: &Vec<T>) -> bool {
438        self == other.as_slice()
439    }
440}
441
442impl<'a, T: Eq, const PREALLOC: usize> Eq for SegmentedSlice<'a, T, PREALLOC> {}
443
444impl<'a, T, const PREALLOC: usize> Index<usize> for SegmentedSlice<'a, T, PREALLOC> {
445    type Output = T;
446
447    fn index(&self, index: usize) -> &Self::Output {
448        self.get(index).expect("index out of bounds")
449    }
450}
451
452impl<'a, T, const PREALLOC: usize> IntoIterator for SegmentedSlice<'a, T, PREALLOC> {
453    type Item = &'a T;
454    type IntoIter = SliceIter<'a, T, PREALLOC>;
455
456    fn into_iter(self) -> Self::IntoIter {
457        self.iter()
458    }
459}
460
461impl<'a, T, const PREALLOC: usize> IntoIterator for &SegmentedSlice<'a, T, PREALLOC> {
462    type Item = &'a T;
463    type IntoIter = SliceIter<'a, T, PREALLOC>;
464
465    fn into_iter(self) -> Self::IntoIter {
466        self.iter()
467    }
468}
469
470// --- Mutable Slice ---
471
472/// A mutable slice view into a `SegmentedVec`.
473///
474/// This type behaves like `&mut [T]` but works with non-contiguous memory.
475///
476/// # Example
477///
478/// ```
479/// use segmented_vec::SegmentedVec;
480///
481/// let mut vec: SegmentedVec<i32, 4> = SegmentedVec::new();
482/// vec.extend(0..10);
483///
484/// let mut slice = vec.as_mut_slice();
485/// slice[0] = 100;
486/// assert_eq!(slice[0], 100);
487/// ```
488pub struct SegmentedSliceMut<'a, T, const PREALLOC: usize> {
489    vec: &'a mut SegmentedVec<T, PREALLOC>,
490    start: usize,
491    len: usize,
492}
493
494impl<'a, T, const PREALLOC: usize> SegmentedSliceMut<'a, T, PREALLOC> {
495    /// Creates a new mutable slice covering the entire vector.
496    #[inline]
497    pub(crate) fn new(vec: &'a mut SegmentedVec<T, PREALLOC>) -> Self {
498        let len = vec.len();
499        Self { vec, start: 0, len }
500    }
501
502    /// Creates a new mutable slice covering a range of the vector.
503    #[inline]
504    pub(crate) fn from_range(
505        vec: &'a mut SegmentedVec<T, PREALLOC>,
506        start: usize,
507        end: usize,
508    ) -> Self {
509        debug_assert!(start <= end && end <= vec.len());
510        Self {
511            vec,
512            start,
513            len: end - start,
514        }
515    }
516
517    /// Returns the number of elements in the slice.
518    #[inline]
519    pub const fn len(&self) -> usize {
520        self.len
521    }
522
523    /// Returns `true` if the slice is empty.
524    #[inline]
525    pub const fn is_empty(&self) -> bool {
526        self.len == 0
527    }
528
529    /// Returns a reference to the element at the given index, or `None` if out of bounds.
530    #[inline]
531    pub fn get(&self, index: usize) -> Option<&T> {
532        if index < self.len() {
533            Some(unsafe { self.vec.unchecked_at(self.start + index) })
534        } else {
535            None
536        }
537    }
538
539    /// Returns a mutable reference to the element at the given index, or `None` if out of bounds.
540    #[inline]
541    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
542        if index < self.len() {
543            Some(unsafe { self.vec.unchecked_at_mut(self.start + index) })
544        } else {
545            None
546        }
547    }
548
549    /// Returns a reference to the first element, or `None` if empty.
550    #[inline]
551    pub fn first(&self) -> Option<&T> {
552        self.get(0)
553    }
554
555    /// Returns a mutable reference to the first element, or `None` if empty.
556    #[inline]
557    pub fn first_mut(&mut self) -> Option<&mut T> {
558        self.get_mut(0)
559    }
560
561    /// Returns a reference to the last element, or `None` if empty.
562    #[inline]
563    pub fn last(&self) -> Option<&T> {
564        if self.is_empty() {
565            None
566        } else {
567            self.get(self.len() - 1)
568        }
569    }
570
571    /// Returns a mutable reference to the last element, or `None` if empty.
572    #[inline]
573    pub fn last_mut(&mut self) -> Option<&mut T> {
574        if self.is_empty() {
575            None
576        } else {
577            let idx = self.len() - 1;
578            self.get_mut(idx)
579        }
580    }
581
582    /// Swaps two elements in the slice.
583    ///
584    /// # Panics
585    ///
586    /// Panics if `a` or `b` are out of bounds.
587    #[inline]
588    pub fn swap(&mut self, a: usize, b: usize) {
589        assert!(a < self.len() && b < self.len());
590        if a != b {
591            unsafe {
592                let ptr_a = self.vec.unchecked_at_mut(self.start + a) as *mut T;
593                let ptr_b = self.vec.unchecked_at_mut(self.start + b) as *mut T;
594                std::ptr::swap(ptr_a, ptr_b);
595            }
596        }
597    }
598
599    /// Reverses the order of elements in the slice.
600    pub fn reverse(&mut self) {
601        let len = self.len();
602        for i in 0..len / 2 {
603            self.swap(i, len - 1 - i);
604        }
605    }
606
607    /// Returns an iterator over the slice.
608    #[inline]
609    pub fn iter(&self) -> SliceIter<'_, T, PREALLOC> {
610        SliceIter {
611            vec: self.vec,
612            start: self.start,
613            end: self.start + self.len,
614        }
615    }
616
617    /// Returns a mutable iterator over the slice.
618    #[inline]
619    pub fn iter_mut(&mut self) -> SliceIterMut<'_, T, PREALLOC> {
620        SliceIterMut {
621            vec: self.vec,
622            end: self.start + self.len,
623            index: self.start,
624        }
625    }
626
627    /// Returns `true` if the slice contains an element with the given value.
628    #[inline]
629    pub fn contains(&self, x: &T) -> bool
630    where
631        T: PartialEq,
632    {
633        self.iter().any(|elem| elem == x)
634    }
635
636    /// Binary searches this slice for a given element.
637    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
638    where
639        T: Ord,
640    {
641        self.binary_search_by(|elem| elem.cmp(x))
642    }
643
644    /// Binary searches this slice with a comparator function.
645    pub fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize>
646    where
647        F: FnMut(&T) -> Ordering,
648    {
649        let mut left = 0;
650        let mut right = self.len();
651
652        while left < right {
653            let mid = left + (right - left) / 2;
654            let elem = unsafe { self.vec.unchecked_at(self.start + mid) };
655            match f(elem) {
656                Ordering::Less => left = mid + 1,
657                Ordering::Greater => right = mid,
658                Ordering::Equal => return Ok(mid),
659            }
660        }
661        Err(left)
662    }
663
664    /// Binary searches this slice with a key extraction function.
665    pub fn binary_search_by_key<B, F>(&self, b: &B, mut f: F) -> Result<usize, usize>
666    where
667        F: FnMut(&T) -> B,
668        B: Ord,
669    {
670        self.binary_search_by(|elem| f(elem).cmp(b))
671    }
672
673    /// Fills the slice with the given value.
674    pub fn fill(&mut self, value: T)
675    where
676        T: Clone,
677    {
678        for i in 0..self.len() {
679            *unsafe { self.vec.unchecked_at_mut(self.start + i) } = value.clone();
680        }
681    }
682
683    /// Fills the slice with values produced by a function.
684    pub fn fill_with<F>(&mut self, mut f: F)
685    where
686        F: FnMut() -> T,
687    {
688        for i in 0..self.len() {
689            *unsafe { self.vec.unchecked_at_mut(self.start + i) } = f();
690        }
691    }
692
693    /// Copies elements from `src` into the slice.
694    ///
695    /// The length of `src` must be the same as the slice.
696    ///
697    /// # Panics
698    ///
699    /// Panics if the lengths differ.
700    pub fn copy_from_slice(&mut self, src: &[T])
701    where
702        T: Clone,
703    {
704        assert_eq!(self.len(), src.len());
705        for (i, val) in src.iter().enumerate() {
706            *unsafe { self.vec.unchecked_at_mut(self.start + i) } = val.clone();
707        }
708    }
709
710    /// Sorts the slice.
711    pub fn sort(&mut self)
712    where
713        T: Ord,
714    {
715        self.sort_by(|a, b| a.cmp(b));
716    }
717
718    /// Sorts the slice with a comparator function.
719    pub fn sort_by<F>(&mut self, mut compare: F)
720    where
721        F: FnMut(&T, &T) -> Ordering,
722    {
723        if self.len() <= 1 {
724            return;
725        }
726        let mut is_less = |a: &T, b: &T| compare(a, b) == Ordering::Less;
727        crate::sort::merge_sort(self.vec, self.start, self.start + self.len, &mut is_less);
728    }
729
730    /// Sorts the slice with a key extraction function.
731    pub fn sort_by_key<K, F>(&mut self, mut f: F)
732    where
733        F: FnMut(&T) -> K,
734        K: Ord,
735    {
736        self.sort_by(|a, b| f(a).cmp(&f(b)));
737    }
738
739    /// Sorts the slice using an unstable algorithm.
740    pub fn sort_unstable(&mut self)
741    where
742        T: Ord,
743    {
744        self.sort_unstable_by(|a, b| a.cmp(b));
745    }
746
747    /// Sorts the slice with a comparator function using an unstable algorithm.
748    pub fn sort_unstable_by<F>(&mut self, mut compare: F)
749    where
750        F: FnMut(&T, &T) -> Ordering,
751    {
752        if self.len() <= 1 {
753            return;
754        }
755        let mut is_less = |a: &T, b: &T| compare(a, b) == Ordering::Less;
756        crate::sort::quicksort(self.vec, self.start, self.start + self.len, &mut is_less);
757    }
758
759    /// Sorts the slice with a key extraction function using an unstable algorithm.
760    pub fn sort_unstable_by_key<K, F>(&mut self, mut f: F)
761    where
762        F: FnMut(&T) -> K,
763        K: Ord,
764    {
765        self.sort_unstable_by(|a, b| f(a).cmp(&f(b)));
766    }
767
768    /// Copies the elements into a new `Vec`.
769    pub fn to_vec(&self) -> Vec<T>
770    where
771        T: Clone,
772    {
773        self.iter().cloned().collect()
774    }
775
776    /// Returns an immutable view of this slice.
777    #[inline]
778    pub fn as_slice(&self) -> SegmentedSlice<'_, T, PREALLOC> {
779        SegmentedSlice {
780            vec: self.vec,
781            start: self.start,
782            len: self.len,
783        }
784    }
785
786    /// Returns a reference to an element without bounds checking.
787    ///
788    /// # Safety
789    ///
790    /// Calling this method with an out-of-bounds index is undefined behavior.
791    #[inline]
792    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
793        debug_assert!(index < self.len());
794        unsafe { self.vec.unchecked_at(self.start + index) }
795    }
796
797    /// Returns a mutable reference to an element without bounds checking.
798    ///
799    /// # Safety
800    ///
801    /// Calling this method with an out-of-bounds index is undefined behavior.
802    #[inline]
803    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
804        debug_assert!(index < self.len());
805        unsafe { self.vec.unchecked_at_mut(self.start + index) }
806    }
807
808    /// Returns `true` if `needle` is a prefix of the slice.
809    pub fn starts_with(&self, needle: &[T]) -> bool
810    where
811        T: PartialEq,
812    {
813        self.as_slice().starts_with(needle)
814    }
815
816    /// Returns `true` if `needle` is a suffix of the slice.
817    pub fn ends_with(&self, needle: &[T]) -> bool
818    where
819        T: PartialEq,
820    {
821        self.as_slice().ends_with(needle)
822    }
823
824    /// Checks if the elements of this slice are sorted.
825    pub fn is_sorted(&self) -> bool
826    where
827        T: PartialOrd,
828    {
829        self.as_slice().is_sorted()
830    }
831
832    /// Checks if the elements of this slice are sorted using the given comparator function.
833    pub fn is_sorted_by<F>(&self, compare: F) -> bool
834    where
835        F: FnMut(&T, &T) -> bool,
836    {
837        self.as_slice().is_sorted_by(compare)
838    }
839
840    /// Checks if the elements of this slice are sorted using the given key extraction function.
841    pub fn is_sorted_by_key<K, F>(&self, f: F) -> bool
842    where
843        F: FnMut(&T) -> K,
844        K: PartialOrd,
845    {
846        self.as_slice().is_sorted_by_key(f)
847    }
848
849    /// Returns the index of the partition point according to the given predicate.
850    pub fn partition_point<P>(&self, pred: P) -> usize
851    where
852        P: FnMut(&T) -> bool,
853    {
854        self.as_slice().partition_point(pred)
855    }
856
857    /// Rotates the slice in-place such that the first `mid` elements move to the end.
858    ///
859    /// After calling `rotate_left`, the element previously at index `mid` is now at index `0`.
860    ///
861    /// # Panics
862    ///
863    /// Panics if `mid > len`.
864    pub fn rotate_left(&mut self, mid: usize) {
865        assert!(mid <= self.len());
866        if mid == 0 || mid == self.len() {
867            return;
868        }
869        // Use the reversal algorithm: reverse first part, reverse second part, reverse all
870        self.reverse_range(0, mid);
871        self.reverse_range(mid, self.len());
872        self.reverse();
873    }
874
875    /// Rotates the slice in-place such that the last `k` elements move to the front.
876    ///
877    /// After calling `rotate_right`, the element previously at index `len - k` is now at index `0`.
878    ///
879    /// # Panics
880    ///
881    /// Panics if `k > len`.
882    pub fn rotate_right(&mut self, k: usize) {
883        assert!(k <= self.len());
884        if k == 0 || k == self.len() {
885            return;
886        }
887        self.rotate_left(self.len() - k);
888    }
889
890    /// Helper to reverse a range within the slice.
891    fn reverse_range(&mut self, start: usize, end: usize) {
892        let mut left = start;
893        let mut right = end;
894        while left < right {
895            right -= 1;
896            self.swap(left, right);
897            left += 1;
898        }
899    }
900
901    /// Divides one mutable slice into two at an index.
902    ///
903    /// The first will contain all indices from `[0, mid)` and the second will contain
904    /// all indices from `[mid, len)`.
905    ///
906    /// # Panics
907    ///
908    /// Panics if `mid > len`.
909    ///
910    /// # Note
911    ///
912    /// Due to borrowing rules, this method consumes self and returns two new slices.
913    pub fn split_at_mut(
914        self,
915        mid: usize,
916    ) -> (
917        SegmentedSliceMut<'a, T, PREALLOC>,
918        SegmentedSliceMut<'a, T, PREALLOC>,
919    ) {
920        assert!(mid <= self.len());
921        let start = self.start;
922        let len = self.len;
923        // Safety: We consume self and split the range, so no aliasing occurs.
924        // We need to use raw pointers to create two mutable references.
925        let vec_ptr = self.vec as *mut SegmentedVec<T, PREALLOC>;
926        // Note: SegmentedSliceMut doesn't implement Drop, so we don't need to call forget
927        unsafe {
928            (
929                SegmentedSliceMut {
930                    vec: &mut *vec_ptr,
931                    start,
932                    len: mid,
933                },
934                SegmentedSliceMut {
935                    vec: &mut *vec_ptr,
936                    start: start + mid,
937                    len: len - mid,
938                },
939            )
940        }
941    }
942
943    /// Returns an iterator over `chunk_size` elements of the slice at a time.
944    ///
945    /// # Panics
946    ///
947    /// Panics if `chunk_size` is 0.
948    pub fn chunks(&self, chunk_size: usize) -> Chunks<'_, T, PREALLOC> {
949        self.as_slice().chunks(chunk_size)
950    }
951
952    /// Returns an iterator over all contiguous windows of length `size`.
953    ///
954    /// # Panics
955    ///
956    /// Panics if `size` is 0.
957    pub fn windows(&self, size: usize) -> Windows<'_, T, PREALLOC> {
958        self.as_slice().windows(size)
959    }
960}
961
962impl<'a, T: std::fmt::Debug, const PREALLOC: usize> std::fmt::Debug
963    for SegmentedSliceMut<'a, T, PREALLOC>
964{
965    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
966        f.debug_list().entries(self.iter()).finish()
967    }
968}
969
970impl<'a, T, const PREALLOC: usize> Index<usize> for SegmentedSliceMut<'a, T, PREALLOC> {
971    type Output = T;
972
973    fn index(&self, index: usize) -> &Self::Output {
974        self.get(index).expect("index out of bounds")
975    }
976}
977
978impl<'a, T, const PREALLOC: usize> IndexMut<usize> for SegmentedSliceMut<'a, T, PREALLOC> {
979    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
980        self.get_mut(index).expect("index out of bounds")
981    }
982}
983
984// --- Iterators ---
985
986/// An iterator over references to elements of a `SegmentedSlice`.
987pub struct SliceIter<'a, T, const PREALLOC: usize> {
988    vec: &'a SegmentedVec<T, PREALLOC>,
989    start: usize,
990    end: usize,
991}
992
993impl<'a, T, const PREALLOC: usize> Iterator for SliceIter<'a, T, PREALLOC> {
994    type Item = &'a T;
995
996    fn next(&mut self) -> Option<Self::Item> {
997        if self.start >= self.end {
998            None
999        } else {
1000            let item = unsafe { self.vec.unchecked_at(self.start) };
1001            self.start += 1;
1002            Some(item)
1003        }
1004    }
1005
1006    fn size_hint(&self) -> (usize, Option<usize>) {
1007        let len = self.end - self.start;
1008        (len, Some(len))
1009    }
1010
1011    fn count(self) -> usize {
1012        self.end - self.start
1013    }
1014
1015    fn nth(&mut self, n: usize) -> Option<Self::Item> {
1016        if n >= self.end - self.start {
1017            self.start = self.end;
1018            None
1019        } else {
1020            self.start += n;
1021            self.next()
1022        }
1023    }
1024}
1025
1026impl<'a, T, const PREALLOC: usize> DoubleEndedIterator for SliceIter<'a, T, PREALLOC> {
1027    fn next_back(&mut self) -> Option<Self::Item> {
1028        if self.start >= self.end {
1029            None
1030        } else {
1031            self.end -= 1;
1032            Some(unsafe { self.vec.unchecked_at(self.end) })
1033        }
1034    }
1035}
1036
1037impl<'a, T, const PREALLOC: usize> ExactSizeIterator for SliceIter<'a, T, PREALLOC> {}
1038
1039impl<'a, T, const PREALLOC: usize> Clone for SliceIter<'a, T, PREALLOC> {
1040    fn clone(&self) -> Self {
1041        SliceIter {
1042            vec: self.vec,
1043            start: self.start,
1044            end: self.end,
1045        }
1046    }
1047}
1048
1049/// A mutable iterator over elements of a `SegmentedSliceMut`.
1050pub struct SliceIterMut<'a, T, const PREALLOC: usize> {
1051    vec: &'a mut SegmentedVec<T, PREALLOC>,
1052    end: usize,
1053    index: usize,
1054}
1055
1056impl<'a, T, const PREALLOC: usize> Iterator for SliceIterMut<'a, T, PREALLOC> {
1057    type Item = &'a mut T;
1058
1059    fn next(&mut self) -> Option<Self::Item> {
1060        if self.index >= self.end {
1061            None
1062        } else {
1063            let ptr = unsafe { self.vec.unchecked_at_mut(self.index) as *mut T };
1064            self.index += 1;
1065            // Safety: Each index is yielded only once, and we have exclusive access.
1066            Some(unsafe { &mut *ptr })
1067        }
1068    }
1069
1070    fn size_hint(&self) -> (usize, Option<usize>) {
1071        let len = self.end - self.index;
1072        (len, Some(len))
1073    }
1074}
1075
1076impl<'a, T, const PREALLOC: usize> ExactSizeIterator for SliceIterMut<'a, T, PREALLOC> {}
1077
1078// --- SliceIndex trait for range indexing ---
1079
1080/// Helper trait for indexing operations on `SegmentedSlice`.
1081pub trait SliceIndex<'a, T, const PREALLOC: usize> {
1082    /// The output type returned by indexing.
1083    type Output;
1084
1085    /// Returns the indexed slice.
1086    fn index(self, slice: SegmentedSlice<'a, T, PREALLOC>) -> Self::Output;
1087}
1088
1089impl<'a, T: 'a, const PREALLOC: usize> SliceIndex<'a, T, PREALLOC> for Range<usize> {
1090    type Output = SegmentedSlice<'a, T, PREALLOC>;
1091
1092    fn index(self, slice: SegmentedSlice<'a, T, PREALLOC>) -> SegmentedSlice<'a, T, PREALLOC> {
1093        assert!(self.start <= self.end && self.end <= slice.len());
1094        SegmentedSlice::from_range(slice.vec, slice.start + self.start, slice.start + self.end)
1095    }
1096}
1097
1098impl<'a, T: 'a, const PREALLOC: usize> SliceIndex<'a, T, PREALLOC> for RangeFrom<usize> {
1099    type Output = SegmentedSlice<'a, T, PREALLOC>;
1100
1101    fn index(self, slice: SegmentedSlice<'a, T, PREALLOC>) -> SegmentedSlice<'a, T, PREALLOC> {
1102        assert!(self.start <= slice.len());
1103        SegmentedSlice::from_range(slice.vec, slice.start + self.start, slice.start + slice.len)
1104    }
1105}
1106
1107impl<'a, T: 'a, const PREALLOC: usize> SliceIndex<'a, T, PREALLOC> for RangeTo<usize> {
1108    type Output = SegmentedSlice<'a, T, PREALLOC>;
1109
1110    fn index(self, slice: SegmentedSlice<'a, T, PREALLOC>) -> SegmentedSlice<'a, T, PREALLOC> {
1111        assert!(self.end <= slice.len());
1112        SegmentedSlice::from_range(slice.vec, slice.start, slice.start + self.end)
1113    }
1114}
1115
1116impl<'a, T: 'a, const PREALLOC: usize> SliceIndex<'a, T, PREALLOC> for RangeFull {
1117    type Output = SegmentedSlice<'a, T, PREALLOC>;
1118
1119    fn index(self, slice: SegmentedSlice<'a, T, PREALLOC>) -> SegmentedSlice<'a, T, PREALLOC> {
1120        slice
1121    }
1122}
1123
1124impl<'a, T: 'a, const PREALLOC: usize> SliceIndex<'a, T, PREALLOC> for RangeInclusive<usize> {
1125    type Output = SegmentedSlice<'a, T, PREALLOC>;
1126
1127    fn index(self, slice: SegmentedSlice<'a, T, PREALLOC>) -> SegmentedSlice<'a, T, PREALLOC> {
1128        let start = *self.start();
1129        let end = *self.end();
1130        assert!(start <= end && end < slice.len());
1131        SegmentedSlice::from_range(slice.vec, slice.start + start, slice.start + end + 1)
1132    }
1133}
1134
1135impl<'a, T: 'a, const PREALLOC: usize> SliceIndex<'a, T, PREALLOC> for RangeToInclusive<usize> {
1136    type Output = SegmentedSlice<'a, T, PREALLOC>;
1137
1138    fn index(self, slice: SegmentedSlice<'a, T, PREALLOC>) -> SegmentedSlice<'a, T, PREALLOC> {
1139        assert!(self.end < slice.len());
1140        SegmentedSlice::from_range(slice.vec, slice.start, slice.start + self.end + 1)
1141    }
1142}
1143
1144// --- Additional Iterators ---
1145
1146/// An iterator over overlapping windows of elements.
1147pub struct Windows<'a, T, const PREALLOC: usize> {
1148    vec: &'a SegmentedVec<T, PREALLOC>,
1149    start: usize,
1150    end: usize,
1151    size: usize,
1152}
1153
1154impl<'a, T, const PREALLOC: usize> Iterator for Windows<'a, T, PREALLOC> {
1155    type Item = SegmentedSlice<'a, T, PREALLOC>;
1156
1157    fn next(&mut self) -> Option<Self::Item> {
1158        if self.start + self.size > self.end {
1159            None
1160        } else {
1161            let slice = SegmentedSlice::from_range(self.vec, self.start, self.start + self.size);
1162            self.start += 1;
1163            Some(slice)
1164        }
1165    }
1166
1167    fn size_hint(&self) -> (usize, Option<usize>) {
1168        let len = self
1169            .end
1170            .saturating_sub(self.start)
1171            .saturating_sub(self.size - 1);
1172        (len, Some(len))
1173    }
1174
1175    fn count(self) -> usize {
1176        self.len()
1177    }
1178
1179    fn nth(&mut self, n: usize) -> Option<Self::Item> {
1180        self.start = self.start.saturating_add(n);
1181        self.next()
1182    }
1183}
1184
1185impl<'a, T, const PREALLOC: usize> DoubleEndedIterator for Windows<'a, T, PREALLOC> {
1186    fn next_back(&mut self) -> Option<Self::Item> {
1187        if self.start + self.size > self.end {
1188            None
1189        } else {
1190            self.end -= 1;
1191            Some(SegmentedSlice::from_range(
1192                self.vec,
1193                self.end - self.size + 1,
1194                self.end + 1,
1195            ))
1196        }
1197    }
1198}
1199
1200impl<'a, T, const PREALLOC: usize> ExactSizeIterator for Windows<'a, T, PREALLOC> {}
1201
1202impl<'a, T, const PREALLOC: usize> Clone for Windows<'a, T, PREALLOC> {
1203    fn clone(&self) -> Self {
1204        Windows {
1205            vec: self.vec,
1206            start: self.start,
1207            end: self.end,
1208            size: self.size,
1209        }
1210    }
1211}
1212
1213/// An iterator over non-overlapping chunks of elements.
1214pub struct Chunks<'a, T, const PREALLOC: usize> {
1215    vec: &'a SegmentedVec<T, PREALLOC>,
1216    start: usize,
1217    end: usize,
1218    chunk_size: usize,
1219}
1220
1221impl<'a, T, const PREALLOC: usize> Iterator for Chunks<'a, T, PREALLOC> {
1222    type Item = SegmentedSlice<'a, T, PREALLOC>;
1223
1224    fn next(&mut self) -> Option<Self::Item> {
1225        if self.start >= self.end {
1226            None
1227        } else {
1228            let chunk_end = std::cmp::min(self.start + self.chunk_size, self.end);
1229            let slice = SegmentedSlice::from_range(self.vec, self.start, chunk_end);
1230            self.start = chunk_end;
1231            Some(slice)
1232        }
1233    }
1234
1235    fn size_hint(&self) -> (usize, Option<usize>) {
1236        if self.start >= self.end {
1237            (0, Some(0))
1238        } else {
1239            let remaining = self.end - self.start;
1240            let len = remaining.div_ceil(self.chunk_size);
1241            (len, Some(len))
1242        }
1243    }
1244
1245    fn count(self) -> usize {
1246        self.len()
1247    }
1248
1249    fn nth(&mut self, n: usize) -> Option<Self::Item> {
1250        let skip = n.saturating_mul(self.chunk_size);
1251        self.start = self.start.saturating_add(skip);
1252        self.next()
1253    }
1254}
1255
1256impl<'a, T, const PREALLOC: usize> DoubleEndedIterator for Chunks<'a, T, PREALLOC> {
1257    fn next_back(&mut self) -> Option<Self::Item> {
1258        if self.start >= self.end {
1259            None
1260        } else {
1261            let remaining = self.end - self.start;
1262            let last_chunk_size = if remaining.is_multiple_of(self.chunk_size) {
1263                self.chunk_size
1264            } else {
1265                remaining % self.chunk_size
1266            };
1267            let chunk_start = self.end - last_chunk_size;
1268            let slice = SegmentedSlice::from_range(self.vec, chunk_start, self.end);
1269            self.end = chunk_start;
1270            Some(slice)
1271        }
1272    }
1273}
1274
1275impl<'a, T, const PREALLOC: usize> ExactSizeIterator for Chunks<'a, T, PREALLOC> {}
1276
1277impl<'a, T, const PREALLOC: usize> Clone for Chunks<'a, T, PREALLOC> {
1278    fn clone(&self) -> Self {
1279        Chunks {
1280            vec: self.vec,
1281            start: self.start,
1282            end: self.end,
1283            chunk_size: self.chunk_size,
1284        }
1285    }
1286}
1287
1288/// An iterator over non-overlapping chunks of elements, starting from the end.
1289pub struct RChunks<'a, T, const PREALLOC: usize> {
1290    vec: &'a SegmentedVec<T, PREALLOC>,
1291    start: usize,
1292    end: usize,
1293    chunk_size: usize,
1294}
1295
1296impl<'a, T, const PREALLOC: usize> Iterator for RChunks<'a, T, PREALLOC> {
1297    type Item = SegmentedSlice<'a, T, PREALLOC>;
1298
1299    fn next(&mut self) -> Option<Self::Item> {
1300        if self.start >= self.end {
1301            None
1302        } else {
1303            let remaining = self.end - self.start;
1304            let chunk_size = std::cmp::min(self.chunk_size, remaining);
1305            let chunk_start = self.end - chunk_size;
1306            let slice = SegmentedSlice::from_range(self.vec, chunk_start, self.end);
1307            self.end = chunk_start;
1308            Some(slice)
1309        }
1310    }
1311
1312    fn size_hint(&self) -> (usize, Option<usize>) {
1313        if self.start >= self.end {
1314            (0, Some(0))
1315        } else {
1316            let remaining = self.end - self.start;
1317            let len = remaining.div_ceil(self.chunk_size);
1318            (len, Some(len))
1319        }
1320    }
1321
1322    fn count(self) -> usize {
1323        self.len()
1324    }
1325}
1326
1327impl<'a, T, const PREALLOC: usize> DoubleEndedIterator for RChunks<'a, T, PREALLOC> {
1328    fn next_back(&mut self) -> Option<Self::Item> {
1329        if self.start >= self.end {
1330            None
1331        } else {
1332            let chunk_end = std::cmp::min(self.start + self.chunk_size, self.end);
1333            let slice = SegmentedSlice::from_range(self.vec, self.start, chunk_end);
1334            self.start = chunk_end;
1335            Some(slice)
1336        }
1337    }
1338}
1339
1340impl<'a, T, const PREALLOC: usize> ExactSizeIterator for RChunks<'a, T, PREALLOC> {}
1341
1342impl<'a, T, const PREALLOC: usize> Clone for RChunks<'a, T, PREALLOC> {
1343    fn clone(&self) -> Self {
1344        RChunks {
1345            vec: self.vec,
1346            start: self.start,
1347            end: self.end,
1348            chunk_size: self.chunk_size,
1349        }
1350    }
1351}
1352
1353/// An iterator over exact-size chunks of elements.
1354pub struct ChunksExact<'a, T, const PREALLOC: usize> {
1355    vec: &'a SegmentedVec<T, PREALLOC>,
1356    start: usize,
1357    end: usize,
1358    remainder_end: usize,
1359    chunk_size: usize,
1360}
1361
1362impl<'a, T, const PREALLOC: usize> ChunksExact<'a, T, PREALLOC> {
1363    /// Returns the remainder of the original slice that was not consumed.
1364    pub fn remainder(&self) -> SegmentedSlice<'a, T, PREALLOC> {
1365        SegmentedSlice::from_range(self.vec, self.end, self.remainder_end)
1366    }
1367}
1368
1369impl<'a, T, const PREALLOC: usize> Iterator for ChunksExact<'a, T, PREALLOC> {
1370    type Item = SegmentedSlice<'a, T, PREALLOC>;
1371
1372    fn next(&mut self) -> Option<Self::Item> {
1373        if self.start + self.chunk_size > self.end {
1374            None
1375        } else {
1376            let slice =
1377                SegmentedSlice::from_range(self.vec, self.start, self.start + self.chunk_size);
1378            self.start += self.chunk_size;
1379            Some(slice)
1380        }
1381    }
1382
1383    fn size_hint(&self) -> (usize, Option<usize>) {
1384        let remaining = self.end.saturating_sub(self.start);
1385        let len = remaining / self.chunk_size;
1386        (len, Some(len))
1387    }
1388
1389    fn count(self) -> usize {
1390        self.len()
1391    }
1392
1393    fn nth(&mut self, n: usize) -> Option<Self::Item> {
1394        let skip = n.saturating_mul(self.chunk_size);
1395        self.start = self.start.saturating_add(skip);
1396        self.next()
1397    }
1398}
1399
1400impl<'a, T, const PREALLOC: usize> DoubleEndedIterator for ChunksExact<'a, T, PREALLOC> {
1401    fn next_back(&mut self) -> Option<Self::Item> {
1402        if self.start + self.chunk_size > self.end {
1403            None
1404        } else {
1405            self.end -= self.chunk_size;
1406            Some(SegmentedSlice::from_range(
1407                self.vec,
1408                self.end,
1409                self.end + self.chunk_size,
1410            ))
1411        }
1412    }
1413}
1414
1415impl<'a, T, const PREALLOC: usize> ExactSizeIterator for ChunksExact<'a, T, PREALLOC> {}
1416
1417impl<'a, T, const PREALLOC: usize> Clone for ChunksExact<'a, T, PREALLOC> {
1418    fn clone(&self) -> Self {
1419        ChunksExact {
1420            vec: self.vec,
1421            start: self.start,
1422            end: self.end,
1423            remainder_end: self.remainder_end,
1424            chunk_size: self.chunk_size,
1425        }
1426    }
1427}
segmented_vec/slice.rs

segmented_vec/
slice.rs
