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

segmented_vec/
slice.rs
