Skip to main content

polars_ops/series/ops/
various.rs

1use polars_core::chunked_array::ops::row_encode::_get_rows_encoded_ca;
2use polars_core::prelude::arity::unary_elementwise_values;
3use polars_core::prelude::*;
4use polars_core::series::IsSorted;
5use polars_core::with_match_physical_numeric_polars_type;
6#[cfg(feature = "hash")]
7use polars_utils::aliases::PlSeedableRandomStateQuality;
8use polars_utils::total_ord::TotalOrd;
9
10use crate::series::ops::SeriesSealed;
11
12pub trait SeriesMethods: SeriesSealed {
13    /// Create a [`DataFrame`] with the unique `values` of this [`Series`] and a column `"counts"`
14    /// with dtype [`IdxType`]
15    fn value_counts(
16        &self,
17        sort: bool,
18        parallel: bool,
19        name: PlSmallStr,
20        normalize: bool,
21    ) -> PolarsResult<DataFrame> {
22        let s = self.as_series();
23        polars_ensure!(
24            s.name() != &name,
25            Duplicate: "using `value_counts` on a column/series named '{}' would lead to duplicate \
26            column names; change `name` to fix", name,
27        );
28        let groups = s.group_tuples(parallel, sort)?;
29        let values = unsafe { s.agg_first(&groups) }
30            .with_name(s.name().clone())
31            .into();
32        let counts = groups.group_count().with_name(name.clone());
33
34        let counts = if normalize {
35            let len = s.len() as f64;
36            let counts: Float64Chunked =
37                unary_elementwise_values(&counts, |count| count as f64 / len);
38            counts.into_column()
39        } else {
40            counts.into_column()
41        };
42
43        let height = counts.len();
44        let cols = vec![values, counts];
45        let df = unsafe { DataFrame::new_unchecked(height, cols) };
46        if sort {
47            df.sort(
48                [name],
49                SortMultipleOptions::default()
50                    .with_order_descending(true)
51                    .with_multithreaded(parallel),
52            )
53        } else {
54            Ok(df)
55        }
56    }
57
58    #[cfg(feature = "hash")]
59    fn hash(&self, build_hasher: PlSeedableRandomStateQuality) -> UInt64Chunked {
60        let s = self.as_series();
61        let mut h = vec![];
62        s.0.vec_hash(build_hasher, &mut h).unwrap();
63        UInt64Chunked::from_vec(s.name().clone(), h)
64    }
65
66    fn ensure_sorted_arg(&self, operation: &str) -> PolarsResult<()> {
67        polars_ensure!(
68            self.is_sorted(SortOptions::default())?,
69            InvalidOperation: "argument in operation '{}' is not sorted, please sort the 'expr/series/column' first",
70            operation
71        );
72        Ok(())
73    }
74
75    /// Checks if a [`Series`] is sorted with concrete options. Tries to fail fast.
76    ///
77    /// For inference of `descending` / `nulls_last`, see [`Self::is_sorted_any`].
78    fn is_sorted(&self, options: SortOptions) -> PolarsResult<bool> {
79        is_sorted_impl(self.as_series(), options)
80    }
81
82    fn is_sorted_any(
83        &self,
84        descending: Option<bool>,
85        nulls_last: Option<bool>,
86    ) -> PolarsResult<bool> {
87        let s = self.as_series();
88        let (descending, nulls_last) = resolve_sort_options(s, descending, nulls_last)?;
89        // When an option could not be inferred the series is trivially sorted along that axis
90        // (e.g. all non-null values equal, or no nulls), so any value works; default to `false`.
91        let options = SortOptions {
92            descending: descending.unwrap_or(false),
93            nulls_last: nulls_last.unwrap_or(false),
94            ..Default::default()
95        };
96        is_sorted_impl(s, options)
97    }
98}
99
100/// Lists, arrays, structs and maps have no ordering comparisons, so order them as `sort` does: by
101/// their row encoding. The encoded values are not null, and compare in ascending byte order as the
102/// original values compare under `descending` and `nulls_last`.
103fn row_encode_nested(
104    s: &Series,
105    descending: bool,
106    nulls_last: bool,
107) -> PolarsResult<Option<Series>> {
108    match s.dtype() {
109        DataType::List(_) => {},
110        #[cfg(feature = "dtype-array")]
111        DataType::Array(..) => {},
112        #[cfg(feature = "dtype-struct")]
113        DataType::Struct(_) => {},
114        #[cfg(feature = "dtype-map")]
115        DataType::Map(..) => {},
116        _ => return Ok(None),
117    }
118    let encoded = _get_rows_encoded_ca(
119        PlSmallStr::EMPTY,
120        &[s.clone().into()],
121        &[descending],
122        &[nulls_last],
123        false,
124    )?;
125    Ok(Some(encoded.into_series()))
126}
127
128fn is_sorted_impl(s: &Series, options: SortOptions) -> PolarsResult<bool> {
129    let null_count = s.null_count();
130
131    if (options.descending
132        && (options.nulls_last || null_count == 0)
133        && matches!(s.is_sorted_flag(), IsSorted::Descending))
134        || (!options.descending
135            && (!options.nulls_last || null_count == 0)
136            && matches!(s.is_sorted_flag(), IsSorted::Ascending))
137    {
138        return Ok(true);
139    }
140
141    if let Some(encoded) = row_encode_nested(s, options.descending, options.nulls_last)? {
142        let options = SortOptions {
143            descending: false,
144            nulls_last: false,
145            ..options
146        };
147        return is_sorted_impl(&encoded, options);
148    }
149
150    let s_len = s.len();
151    if null_count == s_len {
152        // All nulls are equal.
153        return Ok(true);
154    }
155    // Check if nulls are in the right location.
156    if null_count > 0 {
157        if options.nulls_last {
158            if s.slice(Slice::tail(null_count)).null_count() != null_count {
159                return Ok(false);
160            }
161        } else if s.slice(Slice::head(null_count)).null_count() != null_count {
162            return Ok(false);
163        }
164    }
165
166    if s.dtype().is_primitive_numeric() {
167        with_match_physical_numeric_polars_type!(s.dtype(), |$T| {
168            let ca: &ChunkedArray<$T> = s.as_ref().as_ref().as_ref();
169            return Ok(is_sorted_ca_num::<$T>(ca, options))
170        })
171    }
172
173    // Logical non-primitive types (e.g. String, Categorical, List, …): take only the contiguous
174    // non-null values (`non_null`). For ordinary `Categorical` use `iter_str` (below); otherwise
175    // `to_physical_repr`, then
176    // (1) for ordinary [`DataType::Categorical`], compare adjacent **decoded strings** (`iter_str`),
177    // (2) reuse `is_sorted_ca_num` when the physical type is primitive numeric (temporal /
178    //     Decimal, Enum-as-integer, …) after `to_physical_repr`;
179    // (3) uses a dedicated kernel for boolean values,
180    // (4) else scans string / binary values with `TotalOrd`,
181    // (5) else fall back to pairwise `Series::lt_eq` / `gt_eq` (nested types, etc.).
182    let non_null_len = s_len - null_count;
183    if non_null_len <= 1 {
184        return Ok(true);
185    }
186
187    let offset = (!options.nulls_last as i64) * (null_count as i64);
188    let non_null = s.slice((offset, non_null_len));
189    debug_assert_eq!(
190        non_null.null_count(),
191        0,
192        "internal error: `is_sorted` non-null slice contains nulls"
193    );
194
195    #[cfg(feature = "dtype-categorical")]
196    if matches!(non_null.dtype(), DataType::Categorical(_, _)) {
197        return is_sorted_categorical_lexical_adjacent(&non_null, options);
198    }
199
200    let phys = non_null.to_physical_repr();
201    let s_phys = phys.as_ref();
202    if s_phys.dtype().is_primitive_numeric() {
203        with_match_physical_numeric_polars_type!(s_phys.dtype(), |$T| {
204            let ca: &ChunkedArray<$T> = s_phys.as_ref().as_ref().as_ref();
205            return Ok(is_sorted_ca_num::<$T>(ca, options))
206        })
207    }
208
209    match s_phys.dtype() {
210        DataType::Boolean => {
211            let ca = s_phys.bool()?;
212            Ok(is_sorted_ca_bool(ca, options.descending))
213        },
214        DataType::String => {
215            let ca = s_phys.str()?;
216            Ok(is_sorted_adjacent_total_ord(
217                ca.no_null_iter(),
218                options.descending,
219            ))
220        },
221        DataType::Binary => {
222            let ca = s_phys.binary()?;
223            Ok(is_sorted_adjacent_total_ord(
224                ca.no_null_iter(),
225                options.descending,
226            ))
227        },
228        DataType::BinaryOffset => {
229            let ca = s_phys.binary_offset()?;
230            Ok(is_sorted_adjacent_total_ord(
231                ca.no_null_iter(),
232                options.descending,
233            ))
234        },
235        _ => {
236            // `non_null` excludes nulls already; compare `non_null[..-1]` with `non_null[1..]`.
237            let cmp_len = non_null_len - 1;
238            let s1 = non_null.slice(Slice::head(cmp_len));
239            let s2 = non_null.slice((1usize, cmp_len));
240            let cmp_op = if options.descending {
241                Series::gt_eq
242            } else {
243                Series::lt_eq
244            };
245            Ok(cmp_op(&s1, &s2)?.all())
246        },
247    }
248}
249
250/// Returns whether iterator elements are non-decreasing (`descending == false`) or non-increasing
251/// (`descending == true`) under [`TotalOrd`].
252///
253/// Assumes the iterator `it` yields **only** the non-null values in row order (one item per row). An empty
254/// iterator is considered sorted. Stops at the first pair that violates the ordering.
255fn is_sorted_adjacent_total_ord<T: TotalOrd>(
256    it: impl Iterator<Item = T>,
257    descending: bool,
258) -> bool {
259    let mut it = it;
260    // Sliding window: `prev` is always the previous element; seed with the first value.
261    let Some(mut prev) = it.next() else {
262        return true;
263    };
264    if descending {
265        for v in it {
266            if !prev.tot_ge(&v) {
267                return false;
268            }
269            prev = v;
270        }
271    } else {
272        for v in it {
273            if !prev.tot_le(&v) {
274                return false;
275            }
276            prev = v;
277        }
278    }
279    true
280}
281
282/// Ordinary [`DataType::Categorical`]: lexical order via adjacent decoded strings (`iter_str`), same as
283/// `Series::lt_eq` / `gt_eq`, but without a Boolean series. Caller must pass a contiguous **non-null**
284/// slice.
285#[cfg(feature = "dtype-categorical")]
286fn is_sorted_categorical_lexical_adjacent(s: &Series, options: SortOptions) -> PolarsResult<bool> {
287    polars_ensure!(
288        matches!(s.dtype(), DataType::Categorical(_, _)),
289        ComputeError: "internal error: expected Categorical in lexical `is_sorted` path",
290    );
291
292    with_match_categorical_physical_type!(s.dtype().cat_physical().unwrap(), |$C| {
293        let ca = s.cat::<$C>()?;
294
295        // `ca.null_count() == 0` implies each `phys` row decodes via `iter_str` to `Some(..)`
296        Ok(is_sorted_adjacent_total_ord(
297            ca.iter_str().map(|opt| {
298                opt.expect(
299                    "`iter_str` produced None while categorical null_count reported 0 (`is_sorted`)"
300                )
301            }),
302            options.descending,
303        ))
304    })
305}
306
307/// Booleans ordered as [`false`] < [`true`] (same as inequality comparisons on [`BooleanChunked`]).
308///
309/// Monotone order is equivalent to at most one plateau change: ascending is `F…FT…T`, descending is
310/// `T…TF…F`. Implemented with `first_true_idx` / `first_false_idx` plus a global false/true count
311/// check.
312///
313/// Caller must ensure **`ca` has no nulls** on the flattened series (see `non_null` slice above).
314fn is_sorted_ca_bool(ca: &BooleanChunked, descending: bool) -> bool {
315    let len = ca.len();
316    if len <= 1 {
317        return true;
318    }
319    debug_assert_eq!(
320        ca.null_count(),
321        0,
322        "internal error: `is_sorted_ca_bool` expects a non-null boolean slice"
323    );
324    if descending {
325        let Some(idx) = ca.first_false_idx() else {
326            return true;
327        };
328        !ca.slice((idx, ca.len() - idx)).any()
329    } else {
330        let Some(idx) = ca.first_true_idx() else {
331            return true;
332        };
333        ca.slice((idx, ca.len() - idx)).all()
334    }
335}
336
337/// Infers the `(descending, nulls_last)` sort options for `s`, honoring any provided hints.
338///
339/// Each returned value is `Some` when known — taken from the corresponding hint when given,
340/// otherwise inferred from the data — and `None` when it cannot be inferred from `s` alone:
341/// - `descending` is `None` when there are fewer than two distinct non-null values, so no direction
342///   is implied.
343/// - `nulls_last` is `None` when `s` has no nulls, is entirely null, or the nulls are interleaved
344///   (the last of which is not sorted under any placement and is rejected by the `is_sorted` check).
345///
346/// The two axes are independent, so callers can use whichever was determined even when the other
347/// could not be.
348pub fn resolve_sort_options(
349    s: &Series,
350    descending: Option<bool>,
351    nulls_last: Option<bool>,
352) -> PolarsResult<(Option<bool>, Option<bool>)> {
353    let nulls_last = match nulls_last {
354        Some(n) => Some(n),
355        None => infer_nulls_last(s),
356    };
357
358    let descending = match descending {
359        Some(d) => Some(d),
360        None => infer_descending(s, nulls_last.unwrap_or(false))?,
361    };
362
363    Ok((descending, nulls_last))
364}
365
366/// Infers null placement from `s`: `Some(true)` if all nulls sit at the tail, `Some(false)` if all
367/// sit at the head, and `None` if there are no nulls, `s` is entirely null, or the nulls are
368/// interleaved (the latter is not sorted under any placement; the `is_sorted` check rejects it).
369fn infer_nulls_last(s: &Series) -> Option<bool> {
370    let null_count = s.null_count();
371    let s_len = s.len();
372
373    if null_count == 0 || null_count == s_len {
374        return None;
375    }
376
377    if s.slice(Slice::tail(null_count)).null_count() == null_count {
378        Some(true)
379    } else if s.slice(Slice::head(null_count)).null_count() == null_count {
380        Some(false)
381    } else {
382        None
383    }
384}
385
386fn infer_descending(s: &Series, nulls_last: bool) -> PolarsResult<Option<bool>> {
387    let null_count = s.null_count();
388    let non_null_len = s.len() - null_count;
389    if non_null_len < 2 {
390        return Ok(None);
391    }
392
393    let non_null_start = if nulls_last { 0 } else { null_count };
394    let non_null = s.slice((non_null_start, non_null_len));
395    let non_null = row_encode_nested(&non_null, false, nulls_last)?.unwrap_or(non_null);
396
397    let a = non_null.slice(Slice::head(non_null_len - 1));
398    let b = non_null.slice((1usize, non_null_len - 1));
399
400    let lt = a.lt(&b)?;
401    let gt = a.gt(&b)?;
402
403    let lt_first = lt.iter().position(|v| v == Some(true));
404    let gt_first = gt.iter().position(|v| v == Some(true));
405
406    Ok(match (lt_first, gt_first) {
407        (None, None) => None,
408        (Some(_), None) => Some(false),
409        (None, Some(_)) => Some(true),
410        (Some(l), Some(g)) => Some(g < l),
411    })
412}
413
414fn check_cmp<T: NumericNative, Cmp: Fn(&T, &T) -> bool>(
415    vals: &[T],
416    f: Cmp,
417    previous: &mut T,
418) -> bool {
419    let mut sorted = true;
420    for c in vals.chunks(1024) {
421        for v in c {
422            sorted &= f(previous, v);
423            *previous = *v;
424        }
425        if !sorted {
426            return false;
427        }
428    }
429    sorted
430}
431
432fn is_sorted_ca_num<T: PolarsNumericType>(ca: &ChunkedArray<T>, options: SortOptions) -> bool {
433    if let Ok(vals) = ca.cont_slice() {
434        let Some(mut previous) = vals.first().copied() else {
435            return true;
436        };
437        return if options.descending {
438            check_cmp(vals, |prev, c| prev.tot_ge(c), &mut previous)
439        } else {
440            check_cmp(vals, |prev, c| prev.tot_le(c), &mut previous)
441        };
442    };
443
444    if ca.null_count() == 0 {
445        let Some(mut previous) = ca
446            .downcast_iter()
447            .find_map(|arr| arr.values().first().copied())
448        else {
449            return true;
450        };
451        for arr in ca.downcast_iter() {
452            let vals = arr.values();
453            let sorted = if options.descending {
454                check_cmp(vals, |prev, c| prev.tot_ge(c), &mut previous)
455            } else {
456                check_cmp(vals, |prev, c| prev.tot_le(c), &mut previous)
457            };
458            if !sorted {
459                return false;
460            }
461        }
462        return true;
463    };
464
465    let null_count = ca.null_count();
466    if options.nulls_last {
467        let ca = ca.slice(Slice::head(ca.len() - null_count));
468        is_sorted_ca_num(&ca, options)
469    } else {
470        let ca = ca.slice((null_count, ca.len() - null_count));
471        is_sorted_ca_num(&ca, options)
472    }
473}
474
475impl SeriesMethods for Series {}