1use std::cmp::Ordering;
4
5use runmat_builtins::{CharArray, ComplexTensor, StringArray, Tensor, Value};
6use runmat_macros::runtime_builtin;
7
8use super::type_resolvers::bool_output_type;
9use crate::build_runtime_error;
10use crate::builtins::common::gpu_helpers;
11use crate::builtins::common::spec::{
12 BroadcastSemantics, BuiltinFusionSpec, BuiltinGpuSpec, ConstantStrategy, GpuOpKind,
13 ReductionNaN, ResidencyPolicy, ScalarType, ShapeRequirements,
14};
15use crate::builtins::common::tensor;
16
17#[runmat_macros::register_gpu_spec(builtin_path = "crate::builtins::array::sorting_sets::issorted")]
18pub const GPU_SPEC: BuiltinGpuSpec = BuiltinGpuSpec {
19 name: "issorted",
20 op_kind: GpuOpKind::Custom("predicate"),
21 supported_precisions: &[ScalarType::F32, ScalarType::F64],
22 broadcast: BroadcastSemantics::None,
23 provider_hooks: &[],
24 constant_strategy: ConstantStrategy::InlineLiteral,
25 residency: ResidencyPolicy::GatherImmediately,
26 nan_mode: ReductionNaN::Include,
27 two_pass_threshold: None,
28 workgroup_size: None,
29 accepts_nan_mode: true,
30 notes: "GPU inputs gather to the host until providers implement dedicated predicate kernels.",
31};
32
33#[runmat_macros::register_fusion_spec(
34 builtin_path = "crate::builtins::array::sorting_sets::issorted"
35)]
36pub const FUSION_SPEC: BuiltinFusionSpec = BuiltinFusionSpec {
37 name: "issorted",
38 shape: ShapeRequirements::Any,
39 constant_strategy: ConstantStrategy::InlineLiteral,
40 elementwise: None,
41 reduction: None,
42 emits_nan: false,
43 notes: "Predicate builtin evaluated outside fusion; planner prevents kernel generation.",
44};
45
46fn issorted_error(message: impl Into<String>) -> crate::RuntimeError {
47 build_runtime_error(message)
48 .with_builtin("issorted")
49 .build()
50}
51
52#[runtime_builtin(
53 name = "issorted",
54 category = "array/sorting_sets",
55 summary = "Determine whether an array is already sorted.",
56 keywords = "issorted,sorted,monotonic,rows",
57 accel = "sink",
58 sink = true,
59 type_resolver(bool_output_type),
60 builtin_path = "crate::builtins::array::sorting_sets::issorted"
61)]
62async fn issorted_builtin(value: Value, rest: Vec<Value>) -> crate::BuiltinResult<Value> {
63 let input = normalize_input(value).await?;
64 let shape = input.shape();
65 let args = IssortedArgs::parse(&rest, &shape)?;
66
67 let result = match input {
68 InputArray::Real(tensor) => issorted_real(&tensor, &args)?,
69 InputArray::Complex(tensor) => issorted_complex(&tensor, &args)?,
70 InputArray::String(array) => issorted_string(&array, &args)?,
71 };
72
73 Ok(Value::Bool(result))
74}
75
76struct IssortedArgs {
77 mode: CheckMode,
78 direction: Direction,
79 comparison: ComparisonMethod,
80 missing: MissingPlacement,
81}
82
83#[derive(Clone, Copy, Debug, PartialEq, Eq)]
84enum CheckMode {
85 Dimension(usize),
86 Rows,
87}
88
89#[derive(Clone, Copy, Debug, PartialEq, Eq)]
90enum Direction {
91 Ascend,
92 Descend,
93 Monotonic,
94 StrictAscend,
95 StrictDescend,
96 StrictMonotonic,
97}
98
99#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
100enum ComparisonMethod {
101 #[default]
102 Auto,
103 Real,
104 Abs,
105}
106
107#[derive(Clone, Copy, Debug, PartialEq, Eq)]
108enum MissingPlacement {
109 Auto,
110 First,
111 Last,
112}
113
114#[derive(Clone, Copy, Debug, PartialEq, Eq)]
115enum MissingPlacementResolved {
116 First,
117 Last,
118}
119
120impl MissingPlacement {
121 fn resolve(self, direction: SortDirection) -> MissingPlacementResolved {
122 match self {
123 MissingPlacement::First => MissingPlacementResolved::First,
124 MissingPlacement::Last => MissingPlacementResolved::Last,
125 MissingPlacement::Auto => match direction {
126 SortDirection::Ascend => MissingPlacementResolved::Last,
127 SortDirection::Descend => MissingPlacementResolved::First,
128 },
129 }
130 }
131}
132
133#[derive(Clone, Copy, Debug, PartialEq, Eq)]
134enum SortDirection {
135 Ascend,
136 Descend,
137}
138
139#[derive(Clone, Copy)]
140struct OrderSpec {
141 direction: SortDirection,
142 strict: bool,
143}
144
145enum InputArray {
146 Real(Tensor),
147 Complex(ComplexTensor),
148 String(StringArray),
149}
150
151impl InputArray {
152 fn shape(&self) -> Vec<usize> {
153 match self {
154 InputArray::Real(t) => t.shape.clone(),
155 InputArray::Complex(t) => t.shape.clone(),
156 InputArray::String(sa) => sa.shape.clone(),
157 }
158 }
159}
160
161impl IssortedArgs {
162 fn parse(args: &[Value], shape: &[usize]) -> crate::BuiltinResult<Self> {
163 let mut dim_arg: Option<usize> = None;
164 let mut direction: Option<Direction> = None;
165 let mut comparison: ComparisonMethod = ComparisonMethod::Auto;
166 let mut missing: MissingPlacement = MissingPlacement::Auto;
167 let mut mode = CheckMode::Dimension(default_dimension(shape));
168 let mut saw_rows = false;
169
170 let mut idx = 0;
171 while idx < args.len() {
172 let arg = &args[idx];
173 if let Some(token) = value_to_string_lower(arg) {
174 match token.as_str() {
175 "rows" => {
176 if saw_rows {
177 return Err(issorted_error(
178 "issorted: 'rows' specified more than once",
179 ));
180 }
181 if dim_arg.is_some() {
182 return Err(issorted_error(
183 "issorted: cannot combine 'rows' with a dimension argument",
184 ));
185 }
186 saw_rows = true;
187 mode = CheckMode::Rows;
188 idx += 1;
189 continue;
190 }
191 "ascend" => {
192 ensure_unique_direction(&direction)?;
193 direction = Some(Direction::Ascend);
194 idx += 1;
195 continue;
196 }
197 "descend" => {
198 ensure_unique_direction(&direction)?;
199 direction = Some(Direction::Descend);
200 idx += 1;
201 continue;
202 }
203 "monotonic" => {
204 ensure_unique_direction(&direction)?;
205 direction = Some(Direction::Monotonic);
206 idx += 1;
207 continue;
208 }
209 "strictascend" => {
210 ensure_unique_direction(&direction)?;
211 direction = Some(Direction::StrictAscend);
212 idx += 1;
213 continue;
214 }
215 "strictdescend" => {
216 ensure_unique_direction(&direction)?;
217 direction = Some(Direction::StrictDescend);
218 idx += 1;
219 continue;
220 }
221 "strictmonotonic" => {
222 ensure_unique_direction(&direction)?;
223 direction = Some(Direction::StrictMonotonic);
224 idx += 1;
225 continue;
226 }
227 "comparisonmethod" => {
228 idx += 1;
229 if idx >= args.len() {
230 return Err(issorted_error(
231 "issorted: expected a value for 'ComparisonMethod'",
232 ));
233 }
234 let value = value_to_string_lower(&args[idx]).ok_or_else(|| {
235 issorted_error("issorted: 'ComparisonMethod' expects a string value")
236 })?;
237 comparison = match value.as_str() {
238 "auto" => ComparisonMethod::Auto,
239 "real" => ComparisonMethod::Real,
240 "abs" | "magnitude" => ComparisonMethod::Abs,
241 other => {
242 return Err(issorted_error(format!(
243 "issorted: unsupported ComparisonMethod '{other}'"
244 )));
245 }
246 };
247 idx += 1;
248 continue;
249 }
250 "missingplacement" => {
251 idx += 1;
252 if idx >= args.len() {
253 return Err(issorted_error(
254 "issorted: expected a value for 'MissingPlacement'",
255 ));
256 }
257 let value = value_to_string_lower(&args[idx]).ok_or_else(|| {
258 issorted_error("issorted: 'MissingPlacement' expects a string value")
259 })?;
260 missing = match value.as_str() {
261 "auto" => MissingPlacement::Auto,
262 "first" => MissingPlacement::First,
263 "last" => MissingPlacement::Last,
264 other => {
265 return Err(issorted_error(format!(
266 "issorted: unsupported MissingPlacement '{other}'"
267 )));
268 }
269 };
270 idx += 1;
271 continue;
272 }
273 _ => {}
274 }
275 }
276
277 if !saw_rows && dim_arg.is_none() {
278 if let Ok(dim) = tensor::parse_dimension(arg, "issorted") {
279 dim_arg = Some(dim);
280 idx += 1;
281 continue;
282 }
283 }
284
285 return Err(issorted_error(format!(
286 "issorted: unrecognised argument {:?}",
287 arg
288 )));
289 }
290
291 if let Some(dim) = dim_arg {
292 mode = CheckMode::Dimension(dim);
293 }
294
295 Ok(IssortedArgs {
296 mode,
297 direction: direction.unwrap_or(Direction::Ascend),
298 comparison,
299 missing,
300 })
301 }
302}
303
304fn ensure_unique_direction(direction: &Option<Direction>) -> crate::BuiltinResult<()> {
305 if direction.is_some() {
306 Err(issorted_error(
307 "issorted: sorting direction specified more than once",
308 ))
309 } else {
310 Ok(())
311 }
312}
313
314async fn normalize_input(value: Value) -> crate::BuiltinResult<InputArray> {
315 match value {
316 Value::Tensor(tensor) => Ok(InputArray::Real(tensor)),
317 Value::LogicalArray(logical) => {
318 let tensor = tensor::logical_to_tensor(&logical)
319 .map_err(|e| issorted_error(e))?;
320 Ok(InputArray::Real(tensor))
321 }
322 Value::Num(_) | Value::Int(_) | Value::Bool(_) => {
323 let tensor = tensor::value_into_tensor_for("issorted", value)
324 .map_err(|e| issorted_error(e))?;
325 Ok(InputArray::Real(tensor))
326 }
327 Value::ComplexTensor(ct) => Ok(InputArray::Complex(ct)),
328 Value::Complex(re, im) => {
329 let tensor = ComplexTensor::new(vec![(re, im)], vec![1, 1])
330 .map_err(|e| issorted_error(format!("issorted: {e}")))?;
331 Ok(InputArray::Complex(tensor))
332 }
333 Value::CharArray(ca) => {
334 let tensor = char_array_to_tensor(&ca)?;
335 Ok(InputArray::Real(tensor))
336 }
337 Value::StringArray(sa) => Ok(InputArray::String(sa)),
338 Value::String(s) => {
339 let array =
340 StringArray::new(vec![s], vec![1, 1]).map_err(|e| issorted_error(format!("issorted: {e}")))?;
341 Ok(InputArray::String(array))
342 }
343 Value::GpuTensor(handle) => {
344 let tensor = gpu_helpers::gather_tensor_async(&handle).await?;
345 Ok(InputArray::Real(tensor))
346 }
347 other => Err(issorted_error(format!(
348 "issorted: unsupported input type {:?}; expected numeric, logical, complex, char, or string arrays",
349 other
350 ))),
351 }
352}
353
354fn issorted_real(tensor: &Tensor, args: &IssortedArgs) -> crate::BuiltinResult<bool> {
355 if tensor.data.is_empty() {
356 return Ok(true);
357 }
358 match args.mode {
359 CheckMode::Dimension(dim) => Ok(check_real_dimension(tensor, dim, args)),
360 CheckMode::Rows => check_real_rows(tensor, args),
361 }
362}
363
364fn issorted_complex(tensor: &ComplexTensor, args: &IssortedArgs) -> crate::BuiltinResult<bool> {
365 if tensor.data.is_empty() {
366 return Ok(true);
367 }
368 match args.mode {
369 CheckMode::Dimension(dim) => Ok(check_complex_dimension(tensor, dim, args)),
370 CheckMode::Rows => check_complex_rows(tensor, args),
371 }
372}
373
374fn issorted_string(array: &StringArray, args: &IssortedArgs) -> crate::BuiltinResult<bool> {
375 if array.data.is_empty() {
376 return Ok(true);
377 }
378 if !matches!(args.comparison, ComparisonMethod::Auto) {
379 return Err(issorted_error(
380 "issorted: 'ComparisonMethod' is not supported for string arrays",
381 ));
382 }
383 match args.mode {
384 CheckMode::Dimension(dim) => Ok(check_string_dimension(array, dim, args)),
385 CheckMode::Rows => check_string_rows(array, args),
386 }
387}
388
389fn check_real_dimension(tensor: &Tensor, dim: usize, args: &IssortedArgs) -> bool {
390 let dim_index = dim.saturating_sub(1);
391 if dim_index >= tensor.shape.len() {
392 return true;
393 }
394 let len_dim = tensor.shape[dim_index];
395 if len_dim <= 1 {
396 return true;
397 }
398
399 let before = product(&tensor.shape[..dim_index]);
400 let after = product(&tensor.shape[dim_index + 1..]);
401 let effective_comp = match args.comparison {
402 ComparisonMethod::Auto => ComparisonMethod::Real,
403 other => other,
404 };
405 let mut slice = Vec::with_capacity(len_dim);
406 for after_idx in 0..after {
407 for before_idx in 0..before {
408 slice.clear();
409 for k in 0..len_dim {
410 let idx = before_idx + k * before + after_idx * before * len_dim;
411 slice.push(tensor.data[idx]);
412 }
413 if !check_real_slice(&slice, args.direction, effective_comp, args.missing) {
414 return false;
415 }
416 }
417 }
418 true
419}
420
421fn check_complex_dimension(tensor: &ComplexTensor, dim: usize, args: &IssortedArgs) -> bool {
422 let dim_index = dim.saturating_sub(1);
423 if dim_index >= tensor.shape.len() {
424 return true;
425 }
426 let len_dim = tensor.shape[dim_index];
427 if len_dim <= 1 {
428 return true;
429 }
430 let before = product(&tensor.shape[..dim_index]);
431 let after = product(&tensor.shape[dim_index + 1..]);
432 let effective_comp = match args.comparison {
433 ComparisonMethod::Auto => ComparisonMethod::Abs,
434 other => other,
435 };
436 let mut slice = Vec::with_capacity(len_dim);
437 for after_idx in 0..after {
438 for before_idx in 0..before {
439 slice.clear();
440 for k in 0..len_dim {
441 let idx = before_idx + k * before + after_idx * before * len_dim;
442 slice.push(tensor.data[idx]);
443 }
444 if !check_complex_slice(&slice, args.direction, effective_comp, args.missing) {
445 return false;
446 }
447 }
448 }
449 true
450}
451
452fn check_string_dimension(array: &StringArray, dim: usize, args: &IssortedArgs) -> bool {
453 let dim_index = dim.saturating_sub(1);
454 if dim_index >= array.shape.len() {
455 return true;
456 }
457 let len_dim = array.shape[dim_index];
458 if len_dim <= 1 {
459 return true;
460 }
461 let before = product(&array.shape[..dim_index]);
462 let after = product(&array.shape[dim_index + 1..]);
463 let mut slice = Vec::with_capacity(len_dim);
464 for after_idx in 0..after {
465 for before_idx in 0..before {
466 slice.clear();
467 for k in 0..len_dim {
468 let idx = before_idx + k * before + after_idx * before * len_dim;
469 slice.push(array.data[idx].as_str());
470 }
471 if !check_string_slice(&slice, args.direction, args.missing) {
472 return false;
473 }
474 }
475 }
476 true
477}
478
479fn check_real_rows(tensor: &Tensor, args: &IssortedArgs) -> crate::BuiltinResult<bool> {
480 if tensor.shape.len() > 2 {
481 return Err(issorted_error("issorted: 'rows' expects a 2-D matrix"));
482 }
483 let rows = tensor.rows();
484 let cols = tensor.cols();
485 if rows <= 1 || cols == 0 {
486 return Ok(true);
487 }
488 let effective_comp = match args.comparison {
489 ComparisonMethod::Auto => ComparisonMethod::Real,
490 other => other,
491 };
492 let orders = direction_orders(args.direction);
493 for &order in orders {
494 if real_rows_in_order(tensor, rows, cols, order, effective_comp, args.missing) {
495 return Ok(true);
496 }
497 }
498 Ok(false)
499}
500
501fn check_complex_rows(tensor: &ComplexTensor, args: &IssortedArgs) -> crate::BuiltinResult<bool> {
502 if tensor.shape.len() > 2 {
503 return Err(issorted_error("issorted: 'rows' expects a 2-D matrix"));
504 }
505 let rows = tensor.rows;
506 let cols = tensor.cols;
507 if rows <= 1 || cols == 0 {
508 return Ok(true);
509 }
510 let effective_comp = match args.comparison {
511 ComparisonMethod::Auto => ComparisonMethod::Abs,
512 other => other,
513 };
514 let orders = direction_orders(args.direction);
515 for &order in orders {
516 if complex_rows_in_order(tensor, rows, cols, order, effective_comp, args.missing) {
517 return Ok(true);
518 }
519 }
520 Ok(false)
521}
522
523fn check_string_rows(array: &StringArray, args: &IssortedArgs) -> crate::BuiltinResult<bool> {
524 if array.shape.len() > 2 {
525 return Err(issorted_error("issorted: 'rows' expects a 2-D matrix"));
526 }
527 let rows = array.rows;
528 let cols = array.cols;
529 if rows <= 1 || cols == 0 {
530 return Ok(true);
531 }
532 let orders = direction_orders(args.direction);
533 for &order in orders {
534 if string_rows_in_order(array, rows, cols, order, args.missing) {
535 return Ok(true);
536 }
537 }
538 Ok(false)
539}
540
541fn real_rows_in_order(
542 tensor: &Tensor,
543 rows: usize,
544 cols: usize,
545 order: OrderSpec,
546 comparison: ComparisonMethod,
547 missing: MissingPlacement,
548) -> bool {
549 if order.strict && tensor.data.iter().any(|v| v.is_nan()) {
550 return false;
551 }
552 let missing_resolved = missing.resolve(order.direction);
553 for row in 0..rows - 1 {
554 let ord = compare_real_row_pair(
555 tensor,
556 rows,
557 cols,
558 row,
559 row + 1,
560 order.direction,
561 comparison,
562 missing_resolved,
563 );
564 if !order_satisfied(ord, order) {
565 return false;
566 }
567 }
568 true
569}
570
571fn complex_rows_in_order(
572 tensor: &ComplexTensor,
573 rows: usize,
574 cols: usize,
575 order: OrderSpec,
576 comparison: ComparisonMethod,
577 missing: MissingPlacement,
578) -> bool {
579 if order.strict && tensor.data.iter().any(|v| complex_is_nan(*v)) {
580 return false;
581 }
582 let missing_resolved = missing.resolve(order.direction);
583 for row in 0..rows - 1 {
584 let ord = compare_complex_row_pair(
585 tensor,
586 rows,
587 cols,
588 row,
589 row + 1,
590 order.direction,
591 comparison,
592 missing_resolved,
593 );
594 if !order_satisfied(ord, order) {
595 return false;
596 }
597 }
598 true
599}
600
601fn string_rows_in_order(
602 array: &StringArray,
603 rows: usize,
604 cols: usize,
605 order: OrderSpec,
606 missing: MissingPlacement,
607) -> bool {
608 if order.strict && array.data.iter().any(|s| is_string_missing(s)) {
609 return false;
610 }
611 let missing_resolved = missing.resolve(order.direction);
612 for row in 0..rows - 1 {
613 let ord = compare_string_row_pair(
614 array,
615 rows,
616 cols,
617 row,
618 row + 1,
619 order.direction,
620 missing_resolved,
621 );
622 if !order_satisfied(ord, order) {
623 return false;
624 }
625 }
626 true
627}
628
629#[allow(clippy::too_many_arguments)]
630fn compare_real_row_pair(
631 tensor: &Tensor,
632 rows: usize,
633 cols: usize,
634 a: usize,
635 b: usize,
636 direction: SortDirection,
637 comparison: ComparisonMethod,
638 missing: MissingPlacementResolved,
639) -> Ordering {
640 for col in 0..cols {
641 let idx_a = a + col * rows;
642 let idx_b = b + col * rows;
643 let ord = compare_real_scalars(
644 tensor.data[idx_a],
645 tensor.data[idx_b],
646 direction,
647 comparison,
648 missing,
649 );
650 if ord != Ordering::Equal {
651 return ord;
652 }
653 }
654 Ordering::Equal
655}
656
657#[allow(clippy::too_many_arguments)]
658fn compare_complex_row_pair(
659 tensor: &ComplexTensor,
660 rows: usize,
661 cols: usize,
662 a: usize,
663 b: usize,
664 direction: SortDirection,
665 comparison: ComparisonMethod,
666 missing: MissingPlacementResolved,
667) -> Ordering {
668 for col in 0..cols {
669 let idx_a = a + col * rows;
670 let idx_b = b + col * rows;
671 let ord = compare_complex_scalars(
672 tensor.data[idx_a],
673 tensor.data[idx_b],
674 direction,
675 comparison,
676 missing,
677 );
678 if ord != Ordering::Equal {
679 return ord;
680 }
681 }
682 Ordering::Equal
683}
684
685fn compare_string_row_pair(
686 array: &StringArray,
687 rows: usize,
688 cols: usize,
689 a: usize,
690 b: usize,
691 direction: SortDirection,
692 missing: MissingPlacementResolved,
693) -> Ordering {
694 for col in 0..cols {
695 let idx_a = a + col * rows;
696 let idx_b = b + col * rows;
697 let ord = compare_string_scalars(
698 array.data[idx_a].as_str(),
699 array.data[idx_b].as_str(),
700 direction,
701 missing,
702 );
703 if ord != Ordering::Equal {
704 return ord;
705 }
706 }
707 Ordering::Equal
708}
709
710fn order_satisfied(ord: Ordering, order: OrderSpec) -> bool {
711 match order.direction {
712 SortDirection::Ascend => match ord {
713 Ordering::Greater => false,
714 Ordering::Equal => !order.strict,
715 Ordering::Less => true,
716 },
717 SortDirection::Descend => match ord {
718 Ordering::Less => true,
719 Ordering::Equal => !order.strict,
720 Ordering::Greater => false,
721 },
722 }
723}
724
725fn check_real_slice(
726 slice: &[f64],
727 direction: Direction,
728 comparison: ComparisonMethod,
729 missing: MissingPlacement,
730) -> bool {
731 if slice.len() <= 1 {
732 return true;
733 }
734 let orders = direction_orders(direction);
735 for &order in orders {
736 if order.strict && slice.iter().any(|v| v.is_nan()) {
737 continue;
738 }
739 let missing_resolved = missing.resolve(order.direction);
740 if real_slice_in_order(slice, order, comparison, missing_resolved) {
741 return true;
742 }
743 }
744 false
745}
746
747fn check_complex_slice(
748 slice: &[(f64, f64)],
749 direction: Direction,
750 comparison: ComparisonMethod,
751 missing: MissingPlacement,
752) -> bool {
753 if slice.len() <= 1 {
754 return true;
755 }
756 let orders = direction_orders(direction);
757 for &order in orders {
758 if order.strict && slice.iter().any(|v| complex_is_nan(*v)) {
759 continue;
760 }
761 let missing_resolved = missing.resolve(order.direction);
762 if complex_slice_in_order(slice, order, comparison, missing_resolved) {
763 return true;
764 }
765 }
766 false
767}
768
769fn check_string_slice(slice: &[&str], direction: Direction, missing: MissingPlacement) -> bool {
770 if slice.len() <= 1 {
771 return true;
772 }
773 let orders = direction_orders(direction);
774 for &order in orders {
775 if order.strict && slice.iter().any(|s| is_string_missing(s)) {
776 continue;
777 }
778 let missing_resolved = missing.resolve(order.direction);
779 if string_slice_in_order(slice, order, missing_resolved) {
780 return true;
781 }
782 }
783 false
784}
785
786fn real_slice_in_order(
787 slice: &[f64],
788 order: OrderSpec,
789 comparison: ComparisonMethod,
790 missing: MissingPlacementResolved,
791) -> bool {
792 for pair in slice.windows(2) {
793 let ord = compare_real_scalars(pair[0], pair[1], order.direction, comparison, missing);
794 if !order_satisfied(ord, order) {
795 return false;
796 }
797 }
798 true
799}
800
801fn complex_slice_in_order(
802 slice: &[(f64, f64)],
803 order: OrderSpec,
804 comparison: ComparisonMethod,
805 missing: MissingPlacementResolved,
806) -> bool {
807 for pair in slice.windows(2) {
808 let ord = compare_complex_scalars(pair[0], pair[1], order.direction, comparison, missing);
809 if !order_satisfied(ord, order) {
810 return false;
811 }
812 }
813 true
814}
815
816fn string_slice_in_order(
817 slice: &[&str],
818 order: OrderSpec,
819 missing: MissingPlacementResolved,
820) -> bool {
821 for pair in slice.windows(2) {
822 let ord = compare_string_scalars(pair[0], pair[1], order.direction, missing);
823 if !order_satisfied(ord, order) {
824 return false;
825 }
826 }
827 true
828}
829
830fn compare_real_scalars(
831 a: f64,
832 b: f64,
833 direction: SortDirection,
834 comparison: ComparisonMethod,
835 missing: MissingPlacementResolved,
836) -> Ordering {
837 match (a.is_nan(), b.is_nan()) {
838 (true, true) => Ordering::Equal,
839 (true, false) => match missing {
840 MissingPlacementResolved::First => Ordering::Less,
841 MissingPlacementResolved::Last => Ordering::Greater,
842 },
843 (false, true) => match missing {
844 MissingPlacementResolved::First => Ordering::Greater,
845 MissingPlacementResolved::Last => Ordering::Less,
846 },
847 (false, false) => compare_real_finite_scalars(a, b, direction, comparison),
848 }
849}
850
851fn compare_real_finite_scalars(
852 a: f64,
853 b: f64,
854 direction: SortDirection,
855 comparison: ComparisonMethod,
856) -> Ordering {
857 if matches!(comparison, ComparisonMethod::Abs) {
858 let abs_cmp = a.abs().partial_cmp(&b.abs()).unwrap_or(Ordering::Equal);
859 if abs_cmp != Ordering::Equal {
860 return match direction {
861 SortDirection::Ascend => abs_cmp,
862 SortDirection::Descend => abs_cmp.reverse(),
863 };
864 }
865 }
866 match direction {
867 SortDirection::Ascend => a.partial_cmp(&b).unwrap_or(Ordering::Equal),
868 SortDirection::Descend => b.partial_cmp(&a).unwrap_or(Ordering::Equal),
869 }
870}
871
872fn compare_complex_scalars(
873 a: (f64, f64),
874 b: (f64, f64),
875 direction: SortDirection,
876 comparison: ComparisonMethod,
877 missing: MissingPlacementResolved,
878) -> Ordering {
879 match (complex_is_nan(a), complex_is_nan(b)) {
880 (true, true) => Ordering::Equal,
881 (true, false) => match missing {
882 MissingPlacementResolved::First => Ordering::Less,
883 MissingPlacementResolved::Last => Ordering::Greater,
884 },
885 (false, true) => match missing {
886 MissingPlacementResolved::First => Ordering::Greater,
887 MissingPlacementResolved::Last => Ordering::Less,
888 },
889 (false, false) => compare_complex_finite_scalars(a, b, direction, comparison),
890 }
891}
892
893fn compare_complex_finite_scalars(
894 a: (f64, f64),
895 b: (f64, f64),
896 direction: SortDirection,
897 comparison: ComparisonMethod,
898) -> Ordering {
899 match comparison {
900 ComparisonMethod::Real => compare_complex_real_first(a, b, direction),
901 ComparisonMethod::Abs | ComparisonMethod::Auto => {
902 let abs_cmp = complex_abs(a)
903 .partial_cmp(&complex_abs(b))
904 .unwrap_or(Ordering::Equal);
905 if abs_cmp != Ordering::Equal {
906 return match direction {
907 SortDirection::Ascend => abs_cmp,
908 SortDirection::Descend => abs_cmp.reverse(),
909 };
910 }
911 compare_complex_real_first(a, b, direction)
912 }
913 }
914}
915
916fn compare_complex_real_first(a: (f64, f64), b: (f64, f64), direction: SortDirection) -> Ordering {
917 let real_cmp = match direction {
918 SortDirection::Ascend => a.0.partial_cmp(&b.0),
919 SortDirection::Descend => b.0.partial_cmp(&a.0),
920 }
921 .unwrap_or(Ordering::Equal);
922 if real_cmp != Ordering::Equal {
923 return real_cmp;
924 }
925 match direction {
926 SortDirection::Ascend => a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal),
927 SortDirection::Descend => b.1.partial_cmp(&a.1).unwrap_or(Ordering::Equal),
928 }
929}
930
931fn compare_string_scalars(
932 a: &str,
933 b: &str,
934 direction: SortDirection,
935 missing: MissingPlacementResolved,
936) -> Ordering {
937 let missing_a = is_string_missing(a);
938 let missing_b = is_string_missing(b);
939 match (missing_a, missing_b) {
940 (true, true) => Ordering::Equal,
941 (true, false) => match missing {
942 MissingPlacementResolved::First => Ordering::Less,
943 MissingPlacementResolved::Last => Ordering::Greater,
944 },
945 (false, true) => match missing {
946 MissingPlacementResolved::First => Ordering::Greater,
947 MissingPlacementResolved::Last => Ordering::Less,
948 },
949 (false, false) => match direction {
950 SortDirection::Ascend => a.cmp(b),
951 SortDirection::Descend => b.cmp(a),
952 },
953 }
954}
955
956fn complex_is_nan(value: (f64, f64)) -> bool {
957 value.0.is_nan() || value.1.is_nan()
958}
959
960fn complex_abs(value: (f64, f64)) -> f64 {
961 value.0.hypot(value.1)
962}
963
964fn is_string_missing(value: &str) -> bool {
965 value.eq_ignore_ascii_case("<missing>")
966}
967
968fn direction_orders(direction: Direction) -> &'static [OrderSpec] {
969 match direction {
970 Direction::Ascend => &[OrderSpec {
971 direction: SortDirection::Ascend,
972 strict: false,
973 }],
974 Direction::Descend => &[OrderSpec {
975 direction: SortDirection::Descend,
976 strict: false,
977 }],
978 Direction::Monotonic => &[
979 OrderSpec {
980 direction: SortDirection::Ascend,
981 strict: false,
982 },
983 OrderSpec {
984 direction: SortDirection::Descend,
985 strict: false,
986 },
987 ],
988 Direction::StrictAscend => &[OrderSpec {
989 direction: SortDirection::Ascend,
990 strict: true,
991 }],
992 Direction::StrictDescend => &[OrderSpec {
993 direction: SortDirection::Descend,
994 strict: true,
995 }],
996 Direction::StrictMonotonic => &[
997 OrderSpec {
998 direction: SortDirection::Ascend,
999 strict: true,
1000 },
1001 OrderSpec {
1002 direction: SortDirection::Descend,
1003 strict: true,
1004 },
1005 ],
1006 }
1007}
1008
1009fn default_dimension(shape: &[usize]) -> usize {
1010 if shape.is_empty() {
1011 return 1;
1012 }
1013 shape
1014 .iter()
1015 .position(|&extent| extent > 1)
1016 .map(|idx| idx + 1)
1017 .unwrap_or(1)
1018}
1019
1020fn product(slice: &[usize]) -> usize {
1021 slice
1022 .iter()
1023 .copied()
1024 .fold(1usize, |acc, value| acc.saturating_mul(value.max(1)))
1025}
1026
1027fn value_to_string_lower(value: &Value) -> Option<String> {
1028 match String::try_from(value) {
1029 Ok(text) => Some(text.trim().to_ascii_lowercase()),
1030 Err(_) => None,
1031 }
1032}
1033
1034fn char_array_to_tensor(array: &CharArray) -> crate::BuiltinResult<Tensor> {
1035 let rows = array.rows;
1036 let cols = array.cols;
1037 let mut data = vec![0.0f64; rows * cols];
1038 for r in 0..rows {
1039 for c in 0..cols {
1040 let ch = array.data[r * cols + c];
1041 let idx = r + c * rows;
1042 data[idx] = ch as u32 as f64;
1043 }
1044 }
1045 Tensor::new(data, vec![rows, cols]).map_err(|e| issorted_error(format!("issorted: {e}")))
1046}
1047
1048#[cfg(test)]
1049pub(crate) mod tests {
1050 use super::*;
1051 use crate::builtins::common::test_support;
1052 use futures::executor::block_on;
1053 use runmat_builtins::{IntValue, LogicalArray, ResolveContext, Type, Value};
1054
1055 fn issorted_builtin(value: Value, rest: Vec<Value>) -> crate::BuiltinResult<Value> {
1056 block_on(super::issorted_builtin(value, rest))
1057 }
1058
1059 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1060 #[test]
1061 fn issorted_numeric_vector_true() {
1062 let tensor = Tensor::new(vec![1.0, 2.0, 3.0], vec![3, 1]).unwrap();
1063 let result = issorted_builtin(Value::Tensor(tensor), vec![]).expect("issorted");
1064 assert_eq!(result, Value::Bool(true));
1065 }
1066
1067 #[test]
1068 fn issorted_type_resolver_bool() {
1069 assert_eq!(
1070 bool_output_type(&[Type::tensor()], &ResolveContext::new(Vec::new())),
1071 Type::Bool
1072 );
1073 }
1074
1075 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1076 #[test]
1077 fn issorted_numeric_vector_false() {
1078 let tensor = Tensor::new(vec![3.0, 2.0, 1.0], vec![3, 1]).unwrap();
1079 let result = issorted_builtin(Value::Tensor(tensor), vec![]).expect("issorted");
1080 assert_eq!(result, Value::Bool(false));
1081 }
1082
1083 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1084 #[test]
1085 fn issorted_logical_vector() {
1086 let logical = LogicalArray::new(vec![0, 1, 1], vec![3, 1]).unwrap();
1087 let result =
1088 issorted_builtin(Value::LogicalArray(logical), vec![]).expect("issorted logical");
1089 assert_eq!(result, Value::Bool(true));
1090 }
1091
1092 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1093 #[test]
1094 fn issorted_dimension_argument() {
1095 let tensor = Tensor::new(vec![1.0, 2.0, 3.0, 3.0], vec![2, 2]).unwrap();
1096 let args = vec![Value::Int(IntValue::I32(2))];
1097 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1098 assert_eq!(result, Value::Bool(true));
1099 }
1100
1101 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1102 #[test]
1103 fn issorted_strictascend_rejects_duplicates() {
1104 let tensor = Tensor::new(vec![1.0, 1.0, 2.0], vec![3, 1]).unwrap();
1105 let args = vec![Value::from("strictascend")];
1106 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1107 assert_eq!(result, Value::Bool(false));
1108 }
1109
1110 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1111 #[test]
1112 fn issorted_strictmonotonic_true_with_descend() {
1113 let tensor = Tensor::new(vec![9.0, 4.0, 1.0], vec![3, 1]).unwrap();
1114 let args = vec![Value::from("strictmonotonic")];
1115 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1116 assert_eq!(result, Value::Bool(true));
1117 }
1118
1119 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1120 #[test]
1121 fn issorted_strictmonotonic_rejects_plateaus() {
1122 let tensor = Tensor::new(vec![4.0, 4.0, 2.0, 1.0], vec![4, 1]).unwrap();
1123 let args = vec![Value::from("strictmonotonic")];
1124 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1125 assert_eq!(result, Value::Bool(false));
1126 }
1127
1128 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1129 #[test]
1130 fn issorted_monotonic_accepts_descending() {
1131 let tensor = Tensor::new(vec![5.0, 4.0, 4.0, 1.0], vec![4, 1]).unwrap();
1132 let args = vec![Value::from("monotonic")];
1133 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1134 assert_eq!(result, Value::Bool(true));
1135 }
1136
1137 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1138 #[test]
1139 fn issorted_monotonic_rejects_unsorted_data() {
1140 let tensor = Tensor::new(vec![1.0, 3.0, 2.0], vec![3, 1]).unwrap();
1141 let args = vec![Value::from("monotonic")];
1142 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1143 assert_eq!(result, Value::Bool(false));
1144 }
1145
1146 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1147 #[test]
1148 fn issorted_missingplacement_first() {
1149 let tensor = Tensor::new(vec![f64::NAN, 2.0, 3.0], vec![3, 1]).unwrap();
1150 let args = vec![Value::from("MissingPlacement"), Value::from("first")];
1151 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1152 assert_eq!(result, Value::Bool(true));
1153 }
1154
1155 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1156 #[test]
1157 fn issorted_missingplacement_first_violation() {
1158 let tensor = Tensor::new(vec![2.0, f64::NAN, 3.0], vec![3, 1]).unwrap();
1159 let args = vec![Value::from("MissingPlacement"), Value::from("first")];
1160 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1161 assert_eq!(result, Value::Bool(false));
1162 }
1163
1164 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1165 #[test]
1166 fn issorted_missingplacement_auto_descend_prefers_front() {
1167 let tensor = Tensor::new(vec![f64::NAN, 5.0, 3.0], vec![3, 1]).unwrap();
1168 let args = vec![Value::from("descend")];
1169 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1170 assert_eq!(result, Value::Bool(true));
1171 }
1172
1173 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1174 #[test]
1175 fn issorted_comparison_abs() {
1176 let tensor = Tensor::new(vec![-1.0, 1.5, -2.0], vec![3, 1]).unwrap();
1177 let args = vec![Value::from("ComparisonMethod"), Value::from("abs")];
1178 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1179 assert_eq!(result, Value::Bool(true));
1180 }
1181
1182 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1183 #[test]
1184 fn issorted_complex_abs_method() {
1185 let tensor =
1186 ComplexTensor::new(vec![(1.0, 1.0), (2.0, 0.0), (2.0, 3.0)], vec![3, 1]).unwrap();
1187 let args = vec![Value::from("ComparisonMethod"), Value::from("abs")];
1188 let result = issorted_builtin(Value::ComplexTensor(tensor), args).expect("issorted");
1189 assert_eq!(result, Value::Bool(true));
1190 }
1191
1192 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1193 #[test]
1194 fn issorted_complex_real_method() {
1195 let tensor =
1196 ComplexTensor::new(vec![(1.0, 1.0), (1.0, 1.0), (2.0, 0.0)], vec![3, 1]).unwrap();
1197 let args = vec![
1198 Value::from("ComparisonMethod"),
1199 Value::from("real"),
1200 Value::from("strictascend"),
1201 ];
1202 let result = issorted_builtin(Value::ComplexTensor(tensor), args).expect("issorted");
1203 assert_eq!(result, Value::Bool(false));
1204 }
1205
1206 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1207 #[test]
1208 fn issorted_rows_true() {
1209 let tensor = Tensor::new(vec![1.0, 2.0, 1.0, 3.0], vec![2, 2]).unwrap();
1210 let args = vec![Value::from("rows")];
1211 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1212 assert_eq!(result, Value::Bool(true));
1213 }
1214
1215 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1216 #[test]
1217 fn issorted_rows_dimension_error() {
1218 let tensor = Tensor::new(vec![1.0, 2.0, 3.0, 4.0], vec![2, 2, 1]).unwrap();
1219 let result = issorted_builtin(Value::Tensor(tensor), vec![Value::from("rows")]);
1220 assert!(result.is_err());
1221 }
1222
1223 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1224 #[test]
1225 fn issorted_rows_descend_false() {
1226 let tensor = Tensor::new(vec![1.0, 2.0, 4.0, 0.0], vec![2, 2]).unwrap();
1227 let args = vec![Value::from("rows"), Value::from("descend")];
1228 let result = issorted_builtin(Value::Tensor(tensor), args).expect("issorted");
1229 assert_eq!(result, Value::Bool(false));
1230 }
1231
1232 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1233 #[test]
1234 fn issorted_string_dimension() {
1235 let array = StringArray::new(
1236 vec![
1237 "pear".into(),
1238 "plum".into(),
1239 "apple".into(),
1240 "banana".into(),
1241 ],
1242 vec![2, 2],
1243 )
1244 .unwrap();
1245 let args = vec![Value::Int(IntValue::I32(2))];
1246 let result =
1247 issorted_builtin(Value::StringArray(array), args).expect("issorted string dim");
1248 assert_eq!(result, Value::Bool(false));
1249 }
1250
1251 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1252 #[test]
1253 fn issorted_string_missingplacement_last() {
1254 let array = StringArray::new(
1255 vec!["apple".into(), "banana".into(), "<missing>".into()],
1256 vec![3, 1],
1257 )
1258 .unwrap();
1259 let args = vec![Value::from("MissingPlacement"), Value::from("last")];
1260 let result =
1261 issorted_builtin(Value::StringArray(array), args).expect("issorted string placement");
1262 assert_eq!(result, Value::Bool(true));
1263 }
1264
1265 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1266 #[test]
1267 fn issorted_string_missingplacement_last_violation() {
1268 let array = StringArray::new(vec!["<missing>".into(), "apple".into()], vec![2, 1]).unwrap();
1269 let args = vec![Value::from("MissingPlacement"), Value::from("last")];
1270 let result =
1271 issorted_builtin(Value::StringArray(array), args).expect("issorted string placement");
1272 assert_eq!(result, Value::Bool(false));
1273 }
1274
1275 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1276 #[test]
1277 fn issorted_string_comparison_method_error() {
1278 let array = StringArray::new(vec!["apple".into(), "berry".into()], vec![2, 1]).unwrap();
1279 let args = vec![Value::from("ComparisonMethod"), Value::from("real")];
1280 let result = issorted_builtin(Value::StringArray(array), args);
1281 assert!(result.is_err());
1282 }
1283
1284 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1285 #[test]
1286 fn issorted_char_array_input() {
1287 let chars = CharArray::new(vec!['a', 'c', 'e'], 1, 3).unwrap();
1288 let result = issorted_builtin(Value::CharArray(chars), vec![]).expect("issorted char");
1289 assert_eq!(result, Value::Bool(true));
1290 }
1291
1292 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1293 #[test]
1294 fn issorted_duplicate_direction_error() {
1295 let tensor = Tensor::new(vec![1.0, 2.0], vec![2, 1]).unwrap();
1296 let args = vec![Value::from("ascend"), Value::from("descend")];
1297 let result = issorted_builtin(Value::Tensor(tensor), args);
1298 assert!(result.is_err());
1299 }
1300
1301 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1302 #[test]
1303 fn issorted_gpu_roundtrip() {
1304 test_support::with_test_provider(|provider| {
1305 let tensor = Tensor::new(vec![1.0, 2.0, 3.0], vec![3, 1]).unwrap();
1306 let view = runmat_accelerate_api::HostTensorView {
1307 data: &tensor.data,
1308 shape: &tensor.shape,
1309 };
1310 let handle = provider.upload(&view).expect("upload");
1311 let result = issorted_builtin(Value::GpuTensor(handle), vec![]).expect("issorted gpu");
1312 assert_eq!(result, Value::Bool(true));
1313 });
1314 }
1315
1316 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test::wasm_bindgen_test)]
1317 #[test]
1318 #[cfg(feature = "wgpu")]
1319 fn issorted_wgpu_matches_cpu() {
1320 let _ = runmat_accelerate::backend::wgpu::provider::register_wgpu_provider(
1321 runmat_accelerate::backend::wgpu::provider::WgpuProviderOptions::default(),
1322 );
1323 let tensor = Tensor::new(vec![1.0, 2.0, 3.0], vec![3, 1]).unwrap();
1324 let cpu = issorted_builtin(Value::Tensor(tensor.clone()), vec![]).expect("cpu issorted");
1325 let view = runmat_accelerate_api::HostTensorView {
1326 data: &tensor.data,
1327 shape: &tensor.shape,
1328 };
1329 let handle = runmat_accelerate_api::provider()
1330 .expect("wgpu provider")
1331 .upload(&view)
1332 .expect("upload");
1333 let gpu = issorted_builtin(Value::GpuTensor(handle), vec![]).expect("gpu issorted");
1334 assert_eq!(gpu, cpu);
1335 }
1336}