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

segmented_vec/
slice.rs
