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 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 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 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
100fn 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 return Ok(true);
154 }
155 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 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 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
250fn is_sorted_adjacent_total_ord<T: TotalOrd>(
256 it: impl Iterator<Item = T>,
257 descending: bool,
258) -> bool {
259 let mut it = it;
260 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#[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 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
307fn 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
337pub 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
366fn 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 {}