Skip to main content

polars_core/frame/group_by/
position.rs

1use std::mem::ManuallyDrop;
2use std::ops::{Deref, DerefMut};
3
4use polars_arrow::offset::OffsetsBuffer;
5use polars_utils::idx_vec::IdxVec;
6use polars_utils::slice_enum::Slice;
7use rayon::iter::plumbing::UnindexedConsumer;
8use rayon::prelude::*;
9
10use crate::prelude::*;
11use crate::runtime::RAYON;
12use crate::utils::{NoNull, flatten};
13
14/// Indexes of the groups, the first index is stored separately.
15/// this make sorting fast.
16#[derive(Debug, Clone, PartialEq, Eq, Default)]
17pub struct GroupsIdx {
18    /// If true, the groups are ordered by their first index.
19    pub(crate) groups_sorted_by_first_idx: bool,
20    /// If true, the indices within every group are non-decreasing.
21    /// Sorted columns then take their per-group min and max from the group ends.
22    /// `false` only costs speed, never correctness.
23    pub(crate) sorted_idxs_in_groups: bool,
24    /// Positions of the start of each group.
25    first: Vec<IdxSize>,
26    /// Global positions of all elements of all groups.
27    ///
28    /// A group can hold the same position more than once. For example, `max().over("g")`
29    /// inside `agg` computes one value per partition, and each row of a partition gets the
30    /// position of that value.
31    all: Vec<IdxVec>,
32}
33
34pub type IdxItem = (IdxSize, IdxVec);
35pub type BorrowIdxItem<'a> = (IdxSize, &'a IdxVec);
36
37impl Drop for GroupsIdx {
38    fn drop(&mut self) {
39        let v = std::mem::take(&mut self.all);
40        // ~65k took approximately 1ms on local machine, so from that point we drop on other thread
41        // to stop query from being blocked
42        #[cfg(not(target_family = "wasm"))]
43        if v.len() > 1 << 16 {
44            std::thread::spawn(move || drop(v));
45        } else {
46            drop(v);
47        }
48
49        #[cfg(target_family = "wasm")]
50        drop(v);
51    }
52}
53
54impl From<Vec<IdxItem>> for GroupsIdx {
55    fn from(v: Vec<IdxItem>) -> Self {
56        v.into_iter().collect()
57    }
58}
59
60impl From<Vec<Vec<IdxItem>>> for GroupsIdx {
61    fn from(v: Vec<Vec<IdxItem>>) -> Self {
62        // single threaded flatten: 10% faster than `iter().flatten().collect()
63        // this is the multi-threaded impl of that
64        let (cap, offsets) = flatten::cap_and_offsets(&v);
65        let mut first = Vec::with_capacity(cap);
66        let first_ptr = first.as_ptr() as usize;
67        let mut all = Vec::with_capacity(cap);
68        let all_ptr = all.as_ptr() as usize;
69
70        RAYON.install(|| {
71            v.into_par_iter()
72                .zip(offsets)
73                .for_each(|(mut inner, offset)| {
74                    unsafe {
75                        let first = (first_ptr as *const IdxSize as *mut IdxSize).add(offset);
76                        let all = (all_ptr as *const IdxVec as *mut IdxVec).add(offset);
77
78                        let inner_ptr = inner.as_mut_ptr();
79                        for i in 0..inner.len() {
80                            let (first_val, vals) = std::ptr::read(inner_ptr.add(i));
81                            std::ptr::write(first.add(i), first_val);
82                            std::ptr::write(all.add(i), vals);
83                        }
84                        // set len to 0 so that the contents will not get dropped
85                        // they are moved to `first` and `all`
86                        inner.set_len(0);
87                    }
88                });
89        });
90        unsafe {
91            all.set_len(cap);
92            first.set_len(cap);
93        }
94        GroupsIdx {
95            groups_sorted_by_first_idx: false,
96            sorted_idxs_in_groups: false,
97            first,
98            all,
99        }
100    }
101}
102
103impl GroupsIdx {
104    pub fn new(first: Vec<IdxSize>, all: Vec<IdxVec>, groups_sorted_by_first_idx: bool) -> Self {
105        Self {
106            groups_sorted_by_first_idx,
107            sorted_idxs_in_groups: false,
108            first,
109            all,
110        }
111    }
112
113    pub fn sort_by_first_idx(&mut self) {
114        if self.groups_sorted_by_first_idx {
115            return;
116        }
117        let mut idx = 0;
118        let first = std::mem::take(&mut self.first);
119        // store index and values so that we can sort those
120        let mut idx_vals = first
121            .into_iter()
122            .map(|v| {
123                let out = [idx, v];
124                idx += 1;
125                out
126            })
127            .collect_trusted::<Vec<_>>();
128        idx_vals.sort_unstable_by_key(|v| v[1]);
129
130        let take_first = || idx_vals.iter().map(|v| v[1]).collect_trusted::<Vec<_>>();
131        let take_all = || {
132            idx_vals
133                .iter()
134                .map(|v| unsafe {
135                    let idx = v[0] as usize;
136                    std::mem::take(self.all.get_unchecked_mut(idx))
137                })
138                .collect_trusted::<Vec<_>>()
139        };
140        let (first, all) = RAYON.install(|| rayon::join(take_first, take_all));
141        self.first = first;
142        self.all = all;
143        self.groups_sorted_by_first_idx = true
144    }
145    pub fn is_sorted_by_first_idx(&self) -> bool {
146        self.groups_sorted_by_first_idx
147    }
148
149    pub fn has_sorted_idxs_in_groups(&self) -> bool {
150        self.sorted_idxs_in_groups
151    }
152
153    /// Marks whether the indices within every group are ascending,
154    /// which speeds up the per-group minimum and maximum of sorted columns.
155    /// Only pass `sorted=true` if they are. `sorted=false` is always correct.
156    pub fn set_sorted_idxs_in_groups(&mut self, sorted: bool) {
157        debug_assert!(!sorted || self.all.iter().all(|idx| idx.is_sorted()));
158        self.sorted_idxs_in_groups = sorted;
159    }
160
161    pub fn iter(
162        &self,
163    ) -> std::iter::Zip<
164        std::iter::Copied<std::slice::Iter<'_, IdxSize>>,
165        std::slice::Iter<'_, IdxVec>,
166    > {
167        self.into_iter()
168    }
169
170    #[inline(always)]
171    pub fn all(&self) -> &[IdxVec] {
172        &self.all
173    }
174
175    #[inline(always)]
176    pub fn first(&self) -> &[IdxSize] {
177        &self.first
178    }
179
180    #[inline(always)]
181    pub(crate) fn len(&self) -> usize {
182        self.first.len()
183    }
184
185    #[inline(always)]
186    pub(crate) unsafe fn get_unchecked(&self, index: usize) -> BorrowIdxItem<'_> {
187        let first = *self.first.get_unchecked(index);
188        let all = self.all.get_unchecked(index);
189        (first, all)
190    }
191
192    // Create an 'empty group', containing 1 group of length 0
193    pub fn new_empty() -> Self {
194        Self {
195            groups_sorted_by_first_idx: false,
196            sorted_idxs_in_groups: true,
197            first: vec![0],
198            all: vec![vec![].into()],
199        }
200    }
201}
202
203impl FromIterator<IdxItem> for GroupsIdx {
204    fn from_iter<T: IntoIterator<Item = IdxItem>>(iter: T) -> Self {
205        let (first, all) = iter.into_iter().unzip();
206        GroupsIdx {
207            groups_sorted_by_first_idx: false,
208            sorted_idxs_in_groups: false,
209            first,
210            all,
211        }
212    }
213}
214
215impl<'a> IntoIterator for &'a GroupsIdx {
216    type Item = BorrowIdxItem<'a>;
217    type IntoIter = std::iter::Zip<
218        std::iter::Copied<std::slice::Iter<'a, IdxSize>>,
219        std::slice::Iter<'a, IdxVec>,
220    >;
221
222    fn into_iter(self) -> Self::IntoIter {
223        self.first.iter().copied().zip(self.all.iter())
224    }
225}
226
227impl IntoIterator for GroupsIdx {
228    type Item = IdxItem;
229    type IntoIter = std::iter::Zip<std::vec::IntoIter<IdxSize>, std::vec::IntoIter<IdxVec>>;
230
231    fn into_iter(mut self) -> Self::IntoIter {
232        let first = std::mem::take(&mut self.first);
233        let all = std::mem::take(&mut self.all);
234        first.into_iter().zip(all)
235    }
236}
237
238impl FromParallelIterator<IdxItem> for GroupsIdx {
239    fn from_par_iter<I>(par_iter: I) -> Self
240    where
241        I: IntoParallelIterator<Item = IdxItem>,
242    {
243        let (first, all) = par_iter.into_par_iter().unzip();
244        GroupsIdx {
245            groups_sorted_by_first_idx: false,
246            sorted_idxs_in_groups: false,
247            first,
248            all,
249        }
250    }
251}
252
253impl<'a> IntoParallelIterator for &'a GroupsIdx {
254    type Iter = rayon::iter::Zip<
255        rayon::iter::Copied<rayon::slice::Iter<'a, IdxSize>>,
256        rayon::slice::Iter<'a, IdxVec>,
257    >;
258    type Item = BorrowIdxItem<'a>;
259
260    fn into_par_iter(self) -> Self::Iter {
261        self.first.par_iter().copied().zip(self.all.par_iter())
262    }
263}
264
265impl IntoParallelIterator for GroupsIdx {
266    type Iter = rayon::iter::Zip<rayon::vec::IntoIter<IdxSize>, rayon::vec::IntoIter<IdxVec>>;
267    type Item = IdxItem;
268
269    fn into_par_iter(mut self) -> Self::Iter {
270        let first = std::mem::take(&mut self.first);
271        let all = std::mem::take(&mut self.all);
272        first.into_par_iter().zip(all.into_par_iter())
273    }
274}
275
276/// Every group is indicated by an array where the
277///  - first value is an index to the start of the group
278///  - second value is the length of the group
279///
280/// Only used when group values are stored together
281///
282/// This type should have the invariant that it is always sorted in ascending
283/// order by the start indices.
284pub type GroupsSlice = Vec<[IdxSize; 2]>;
285
286#[derive(Debug, Clone, PartialEq, Eq)]
287pub enum GroupsType {
288    Idx(GroupsIdx),
289    Slice {
290        // the groups slices
291        groups: GroupsSlice,
292        /// Indicates if the groups may overlap, i.e., at least one index MAY be
293        /// included in more than one group slice.
294        overlapping: bool,
295        /// Indicates if the groups are rolling, i.e. for every consecutive group
296        /// slice (offset, len), and given start = offset and end = offset + len,
297        /// then both new_start >= start AND new_end >= end MUST be true.
298        monotonic: bool,
299    },
300}
301
302impl Default for GroupsType {
303    fn default() -> Self {
304        GroupsType::Idx(GroupsIdx::default())
305    }
306}
307
308/// Returns whether `groups` is monotonic:
309/// True if for every consecutive pair of group slices both the
310/// start and the end offset are non-decreasing.
311pub fn slice_groups_are_monotonic(groups: &GroupsSlice) -> bool {
312    if groups.len() < 2 {
313        return true;
314    }
315
316    let (offset, len) = (groups[0][0], groups[0][1]);
317    let mut prev_start = offset;
318    let mut prev_end = offset + len;
319
320    for g in &groups[1..] {
321        let start = g[0];
322        let end = g[0] + g[1];
323
324        if start < prev_start || end < prev_end {
325            return false;
326        }
327
328        prev_start = start;
329        prev_end = end;
330    }
331    true
332}
333
334impl GroupsType {
335    pub fn new_slice(groups: GroupsSlice, overlapping: bool, monotonic: bool) -> Self {
336        #[cfg(debug_assertions)]
337        {
338            fn groups_overlap(groups: &GroupsSlice) -> bool {
339                if groups.len() < 2 {
340                    return false;
341                }
342                let mut groups = groups.clone();
343                groups.sort();
344                let mut prev_end = groups[0][1];
345
346                for g in &groups[1..] {
347                    let start = g[0];
348                    let end = g[1];
349                    if start < prev_end {
350                        return true;
351                    }
352                    if end > prev_end {
353                        prev_end = end;
354                    }
355                }
356                false
357            }
358
359            assert!(overlapping || !groups_overlap(&groups));
360            assert!(!monotonic || slice_groups_are_monotonic(&groups));
361        }
362
363        Self::Slice {
364            groups,
365            overlapping,
366            monotonic,
367        }
368    }
369
370    pub fn into_idx(self) -> GroupsIdx {
371        match self {
372            GroupsType::Idx(groups) => groups,
373            GroupsType::Slice { groups, .. } => {
374                polars_warn!(
375                    "Had to reallocate groups, missed an optimization opportunity. Please open an issue."
376                );
377                let mut groups: GroupsIdx = groups
378                    .iter()
379                    .map(|&[first, len]| (first, (first..first + len).collect::<IdxVec>()))
380                    .collect();
381                groups.sorted_idxs_in_groups = true;
382                groups
383            },
384        }
385    }
386
387    pub(crate) fn prepare_list_agg(
388        &self,
389        total_len: usize,
390    ) -> (Option<IdxCa>, OffsetsBuffer<i64>, bool) {
391        let mut can_fast_explode = true;
392        match self {
393            GroupsType::Idx(groups) => {
394                let mut list_offset = Vec::with_capacity(self.len() + 1);
395                let mut gather_offsets = Vec::with_capacity(total_len);
396
397                let mut len_so_far = 0i64;
398                list_offset.push(len_so_far);
399
400                for idx in groups {
401                    let idx = idx.1;
402                    gather_offsets.extend_from_slice(idx);
403                    len_so_far += idx.len() as i64;
404                    list_offset.push(len_so_far);
405                    can_fast_explode &= !idx.is_empty();
406                }
407                unsafe {
408                    (
409                        Some(IdxCa::from_vec(PlSmallStr::EMPTY, gather_offsets)),
410                        OffsetsBuffer::new_unchecked(list_offset.into()),
411                        can_fast_explode,
412                    )
413                }
414            },
415            GroupsType::Slice { groups, .. } => {
416                let mut list_offset = Vec::with_capacity(self.len() + 1);
417                let mut gather_offsets = Vec::with_capacity(total_len);
418                let mut len_so_far = 0i64;
419                list_offset.push(len_so_far);
420
421                for g in groups {
422                    let len = g[1];
423                    let offset = g[0];
424                    gather_offsets.extend(offset..offset + len);
425
426                    len_so_far += len as i64;
427                    list_offset.push(len_so_far);
428                    can_fast_explode &= len > 0;
429                }
430
431                unsafe {
432                    (
433                        Some(IdxCa::from_vec(PlSmallStr::EMPTY, gather_offsets)),
434                        OffsetsBuffer::new_unchecked(list_offset.into()),
435                        can_fast_explode,
436                    )
437                }
438            },
439        }
440    }
441
442    pub fn iter(&self) -> GroupsTypeIter<'_> {
443        GroupsTypeIter::new(self)
444    }
445
446    pub fn sort_by_first_idx(&mut self) {
447        match self {
448            GroupsType::Idx(groups) => {
449                if !groups.is_sorted_by_first_idx() {
450                    groups.sort_by_first_idx()
451                }
452            },
453            GroupsType::Slice { .. } => {
454                // Only reached for non-overlapping slices, which are ordered by start.
455            },
456        }
457    }
458
459    pub(crate) fn is_sorted_by_first_idx(&self) -> bool {
460        match self {
461            GroupsType::Idx(groups) => groups.is_sorted_by_first_idx(),
462            // Overlapping slices can step back, e.g. after a per-window `slice` offset.
463            GroupsType::Slice {
464                overlapping,
465                monotonic,
466                ..
467            } => !*overlapping || *monotonic,
468        }
469    }
470
471    pub fn has_sorted_idxs_in_groups(&self) -> bool {
472        match self {
473            GroupsType::Idx(groups) => groups.has_sorted_idxs_in_groups(),
474            GroupsType::Slice { .. } => true,
475        }
476    }
477
478    pub fn is_overlapping(&self) -> bool {
479        matches!(
480            self,
481            GroupsType::Slice {
482                overlapping: true,
483                ..
484            }
485        )
486    }
487
488    pub fn is_monotonic(&self) -> bool {
489        matches!(
490            self,
491            GroupsType::Slice {
492                monotonic: true,
493                ..
494            }
495        )
496    }
497
498    pub fn take_group_firsts(self) -> Vec<IdxSize> {
499        match self {
500            GroupsType::Idx(mut groups) => std::mem::take(&mut groups.first),
501            GroupsType::Slice { groups, .. } => {
502                groups.into_iter().map(|[first, _len]| first).collect()
503            },
504        }
505    }
506
507    /// Checks if groups are of equal length. The caller is responsible for
508    /// updating the groups by calling `groups()` prior to calling this method.
509    pub fn check_lengths(self: &GroupsType, other: &GroupsType) -> PolarsResult<()> {
510        if std::ptr::eq(self, other) {
511            return Ok(());
512        }
513        polars_ensure!(self.iter().zip(other.iter()).all(|(a, b)| {
514            a.len() == b.len()
515        }), ShapeMismatch: "expressions must have matching group lengths");
516        Ok(())
517    }
518
519    /// # Safety
520    /// This will not do any bounds checks. The caller must ensure
521    /// all groups have members.
522    pub unsafe fn take_group_lasts(self) -> Vec<IdxSize> {
523        match self {
524            GroupsType::Idx(groups) => groups
525                .all
526                .iter()
527                .map(|idx| *idx.get_unchecked(idx.len() - 1))
528                .collect(),
529            GroupsType::Slice { groups, .. } => groups
530                .into_iter()
531                .map(|[first, len]| first + len - 1)
532                .collect(),
533        }
534    }
535
536    pub fn par_iter(&self) -> GroupsTypeParIter<'_> {
537        GroupsTypeParIter::new(self)
538    }
539
540    /// Get a reference to the `GroupsIdx`.
541    ///
542    /// # Panic
543    ///
544    /// panics if the groups are a slice.
545    pub fn unwrap_idx(&self) -> &GroupsIdx {
546        match self {
547            GroupsType::Idx(groups) => groups,
548            GroupsType::Slice { .. } => panic!("groups are slices not index"),
549        }
550    }
551
552    /// Get a reference to the `GroupsSlice`.
553    ///
554    /// # Panic
555    ///
556    /// panics if the groups are an idx.
557    pub fn unwrap_slice(&self) -> &GroupsSlice {
558        match self {
559            GroupsType::Slice { groups, .. } => groups,
560            GroupsType::Idx(_) => panic!("groups are index not slices"),
561        }
562    }
563
564    pub fn get(&self, index: usize) -> GroupsIndicator<'_> {
565        match self {
566            GroupsType::Idx(groups) => {
567                let first = groups.first[index];
568                let all = &groups.all[index];
569                GroupsIndicator::Idx((first, all))
570            },
571            GroupsType::Slice { groups, .. } => GroupsIndicator::Slice(groups[index]),
572        }
573    }
574
575    /// Get a mutable reference to the `GroupsIdx`.
576    ///
577    /// # Panic
578    ///
579    /// panics if the groups are a slice.
580    pub fn idx_mut(&mut self) -> &mut GroupsIdx {
581        match self {
582            GroupsType::Idx(groups) => groups,
583            GroupsType::Slice { .. } => panic!("groups are slices not index"),
584        }
585    }
586
587    pub fn len(&self) -> usize {
588        match self {
589            GroupsType::Idx(groups) => groups.len(),
590            GroupsType::Slice { groups, .. } => groups.len(),
591        }
592    }
593
594    pub fn is_empty(&self) -> bool {
595        self.len() == 0
596    }
597
598    pub fn group_count(&self) -> IdxCa {
599        match self {
600            GroupsType::Idx(groups) => {
601                let ca: NoNull<IdxCa> = groups
602                    .iter()
603                    .map(|(_first, idx)| idx.len() as IdxSize)
604                    .collect_trusted();
605                ca.into_inner()
606            },
607            GroupsType::Slice { groups, .. } => {
608                let ca: NoNull<IdxCa> = groups.iter().map(|[_first, len]| *len).collect_trusted();
609                ca.into_inner()
610            },
611        }
612    }
613
614    pub fn as_list_chunked(&self) -> ListChunked {
615        match self {
616            GroupsType::Idx(groups) => groups
617                .iter()
618                .map(|(_first, idx)| {
619                    let ca: NoNull<IdxCa> = idx.iter().map(|&v| v as IdxSize).collect();
620                    ca.into_inner().into_series()
621                })
622                .collect_trusted(),
623            GroupsType::Slice { groups, .. } => groups
624                .iter()
625                .map(|&[first, len]| {
626                    let ca: NoNull<IdxCa> = (first..first + len).collect_trusted();
627                    ca.into_inner().into_series()
628                })
629                .collect_trusted(),
630        }
631    }
632
633    pub fn into_sliceable(self) -> GroupPositions {
634        let len = self.len();
635        slice_groups(Arc::new(self), 0, len)
636    }
637
638    pub fn num_elements(&self) -> usize {
639        match self {
640            GroupsType::Idx(i) => i.all().iter().map(|v| v.len()).sum(),
641            GroupsType::Slice {
642                groups,
643                overlapping: _,
644                monotonic: _,
645            } => groups.iter().map(|[_, l]| *l as usize).sum(),
646        }
647    }
648}
649
650impl From<GroupsIdx> for GroupsType {
651    fn from(groups: GroupsIdx) -> Self {
652        GroupsType::Idx(groups)
653    }
654}
655
656pub enum GroupsIndicator<'a> {
657    Idx(BorrowIdxItem<'a>),
658    Slice([IdxSize; 2]),
659}
660
661impl GroupsIndicator<'_> {
662    pub fn len(&self) -> usize {
663        match self {
664            GroupsIndicator::Idx(g) => g.1.len(),
665            GroupsIndicator::Slice([_, len]) => *len as usize,
666        }
667    }
668    pub fn first(&self) -> IdxSize {
669        match self {
670            GroupsIndicator::Idx(g) => g.0,
671            GroupsIndicator::Slice([first, _]) => *first,
672        }
673    }
674    pub fn is_empty(&self) -> bool {
675        self.len() == 0
676    }
677}
678
679pub struct GroupsTypeIter<'a> {
680    vals: &'a GroupsType,
681    len: usize,
682    idx: usize,
683}
684
685impl<'a> GroupsTypeIter<'a> {
686    fn new(vals: &'a GroupsType) -> Self {
687        let len = vals.len();
688        let idx = 0;
689        GroupsTypeIter { vals, len, idx }
690    }
691}
692
693impl<'a> Iterator for GroupsTypeIter<'a> {
694    type Item = GroupsIndicator<'a>;
695
696    fn nth(&mut self, n: usize) -> Option<Self::Item> {
697        self.idx = self.idx.saturating_add(n);
698        self.next()
699    }
700
701    fn next(&mut self) -> Option<Self::Item> {
702        if self.idx >= self.len {
703            return None;
704        }
705
706        let out = unsafe {
707            match self.vals {
708                GroupsType::Idx(groups) => {
709                    let item = groups.get_unchecked(self.idx);
710                    Some(GroupsIndicator::Idx(item))
711                },
712                GroupsType::Slice { groups, .. } => {
713                    Some(GroupsIndicator::Slice(*groups.get_unchecked(self.idx)))
714                },
715            }
716        };
717        self.idx += 1;
718        out
719    }
720
721    fn size_hint(&self) -> (usize, Option<usize>) {
722        let remaining = self.len.saturating_sub(self.idx);
723        (remaining, Some(remaining))
724    }
725}
726
727impl ExactSizeIterator for GroupsTypeIter<'_> {}
728
729pub struct GroupsTypeParIter<'a> {
730    vals: &'a GroupsType,
731    len: usize,
732}
733
734impl<'a> GroupsTypeParIter<'a> {
735    fn new(vals: &'a GroupsType) -> Self {
736        let len = vals.len();
737        GroupsTypeParIter { vals, len }
738    }
739}
740
741impl<'a> ParallelIterator for GroupsTypeParIter<'a> {
742    type Item = GroupsIndicator<'a>;
743
744    fn drive_unindexed<C>(self, consumer: C) -> C::Result
745    where
746        C: UnindexedConsumer<Self::Item>,
747    {
748        (0..self.len)
749            .into_par_iter()
750            .map(|i| unsafe {
751                match self.vals {
752                    GroupsType::Idx(groups) => GroupsIndicator::Idx(groups.get_unchecked(i)),
753                    GroupsType::Slice { groups, .. } => {
754                        GroupsIndicator::Slice(*groups.get_unchecked(i))
755                    },
756                }
757            })
758            .drive_unindexed(consumer)
759    }
760}
761
762#[derive(Debug)]
763pub struct GroupPositions {
764    // SAFETY: sliced is a shallow clone of original
765    // It emulates a shared reference, not an exclusive reference
766    // Its data must not be mutated through direct access
767    sliced: ManuallyDrop<GroupsType>,
768    // Unsliced buffer
769    original: Arc<GroupsType>,
770    offset: usize,
771    len: usize,
772}
773
774impl Clone for GroupPositions {
775    fn clone(&self) -> Self {
776        let sliced = slice_groups_inner(&self.original, self.offset, self.len);
777
778        Self {
779            sliced,
780            original: self.original.clone(),
781            offset: self.offset,
782            len: self.len,
783        }
784    }
785}
786
787impl AsRef<GroupsType> for GroupPositions {
788    fn as_ref(&self) -> &GroupsType {
789        self.sliced.deref()
790    }
791}
792
793impl Deref for GroupPositions {
794    type Target = GroupsType;
795
796    fn deref(&self) -> &Self::Target {
797        self.sliced.deref()
798    }
799}
800
801impl Default for GroupPositions {
802    fn default() -> Self {
803        GroupsType::default().into_sliceable()
804    }
805}
806
807impl GroupPositions {
808    pub fn slice(&self, slice: impl Into<Slice>) -> Self {
809        let range = slice.into().resolve(self.len());
810        slice_groups(
811            self.original.clone(),
812            self.offset + range.start,
813            range.len(),
814        )
815    }
816
817    pub fn sort_by_first_idx(&mut self) {
818        if !self.as_ref().is_sorted_by_first_idx() {
819            let original = Arc::make_mut(&mut self.original);
820            original.sort_by_first_idx();
821
822            self.sliced = slice_groups_inner(original, self.offset, self.len);
823        }
824    }
825
826    pub fn unroll(mut self) -> GroupPositions {
827        match self.sliced.deref_mut() {
828            GroupsType::Idx(_) => self,
829            GroupsType::Slice {
830                overlapping: false, ..
831            } => self,
832            GroupsType::Slice { groups, .. } => {
833                // SAFETY: sliced is a shallow partial clone of original.
834                // A new owning Vec is required per GH issue #21859
835                let mut cum_offset = 0 as IdxSize;
836                let groups: Vec<_> = groups
837                    .iter()
838                    .map(|[_, len]| {
839                        let new = [cum_offset, *len];
840                        cum_offset += *len;
841                        new
842                    })
843                    .collect();
844
845                GroupsType::new_slice(groups, false, true).into_sliceable()
846            },
847        }
848    }
849
850    pub fn as_unrolled_slice(&self) -> Option<&GroupsSlice> {
851        match &*self.sliced {
852            GroupsType::Idx(_) => None,
853            GroupsType::Slice {
854                groups: _,
855                overlapping: true,
856                monotonic: _,
857            } => None,
858            GroupsType::Slice {
859                groups,
860                overlapping: false,
861                monotonic: _,
862            } => Some(groups),
863        }
864    }
865
866    /// Compare groups based on inner pointer.
867    pub fn is_same(&self, other: &Self) -> bool {
868        Arc::ptr_eq(&self.original, &other.original)
869            && self.offset == other.offset
870            && self.len == other.len
871    }
872}
873
874fn slice_groups_inner(g: &GroupsType, offset: usize, len: usize) -> ManuallyDrop<GroupsType> {
875    // SAFETY:
876    // we create new `Vec`s from the sliced groups. But we wrap them in ManuallyDrop
877    // so that we never call drop on them.
878    // These groups lifetimes are bounded to the `g`. This must remain valid
879    // for the scope of the aggregation.
880    match g {
881        GroupsType::Idx(groups) => {
882            let first = unsafe {
883                let first = &groups.first()[offset..][..len];
884                let ptr = first.as_ptr() as *mut _;
885                Vec::from_raw_parts(ptr, first.len(), first.len())
886            };
887
888            let all = unsafe {
889                let all = &groups.all()[offset..][..len];
890                let ptr = all.as_ptr() as *mut _;
891                Vec::from_raw_parts(ptr, all.len(), all.len())
892            };
893            let mut sliced = GroupsIdx::new(first, all, groups.is_sorted_by_first_idx());
894            sliced.sorted_idxs_in_groups = groups.has_sorted_idxs_in_groups();
895            ManuallyDrop::new(GroupsType::Idx(sliced))
896        },
897        GroupsType::Slice {
898            groups,
899            overlapping,
900            monotonic,
901        } => {
902            let groups = unsafe {
903                let groups = &groups[offset..][..len];
904                let ptr = groups.as_ptr() as *mut _;
905                Vec::from_raw_parts(ptr, groups.len(), groups.len())
906            };
907
908            ManuallyDrop::new(GroupsType::new_slice(groups, *overlapping, *monotonic))
909        },
910    }
911}
912
913fn slice_groups(g: Arc<GroupsType>, offset: usize, len: usize) -> GroupPositions {
914    let sliced = slice_groups_inner(g.as_ref(), offset, len);
915
916    GroupPositions {
917        sliced,
918        original: g,
919        offset,
920        len,
921    }
922}