uiua/algorithm/monadic/
mod.rs

1//! Algorithms for monadic array operations
2
3mod sort;
4
5use core::str;
6use std::{
7    borrow::Cow,
8    cmp::Ordering,
9    collections::{HashMap, HashSet},
10    convert::identity,
11    f64::consts::{PI, TAU},
12    fmt,
13    io::Write,
14    iter::{self, once},
15    mem::{size_of, take},
16    ptr, slice,
17    time::Duration,
18};
19
20use ecow::{eco_vec, EcoVec};
21use rayon::prelude::*;
22use time::{Date, Month, OffsetDateTime, Time};
23use unicode_segmentation::UnicodeSegmentation;
24
25use crate::{
26    array::*,
27    cowslice::{cowslice, CowSlice},
28    grid_fmt::GridFmt,
29    val_as_arr,
30    value::Value,
31    Boxed, Complex, Primitive, Shape, Uiua, UiuaResult,
32};
33
34use super::{validate_size, ArrayCmpSlice, FillContext};
35
36impl Value {
37    /// Make the value 1-dimensional
38    pub fn deshape(&mut self) {
39        self.deshape_depth(0);
40    }
41    pub(crate) fn deshape_depth(&mut self, mut depth: usize) {
42        if let Value::Box(arr) = self {
43            if let Some(Boxed(val)) = arr.as_scalar_mut() {
44                val.deshape_depth(depth);
45                return;
46            }
47        }
48        if self.is_map() {
49            self.meta.take_map_keys();
50        }
51        depth = depth.min(self.rank());
52        let deshaped = self.shape.split_off(depth).into_iter().product();
53        self.shape.push(deshaped);
54        self.meta.take_sorted_flags();
55        self.validate();
56    }
57    pub(crate) fn deshape_sub(
58        &mut self,
59        irank: i32,
60        mut depth: usize,
61        extend: bool,
62        env: &Uiua,
63    ) -> UiuaResult {
64        depth = depth.min(self.rank());
65        let deep_rank = self.rank() - depth;
66        if irank > 0 && irank as usize == deep_rank {
67            return Ok(());
68        }
69        self.meta.take_map_keys();
70        let shape = &mut self.shape;
71        let rank = irank.unsigned_abs() as usize;
72        match irank.cmp(&0) {
73            Ordering::Equal => {
74                // First scalar
75                if depth == 0 {
76                    if shape.contains(&0) {
77                        if let Some(fv) = env.value_fill() {
78                            *self = fv.value.clone();
79                        } else {
80                            return Err(env.error(format!(
81                                "Cannot get first scalar of an empty array (shape {shape})"
82                            )));
83                        }
84                    } else {
85                        *shape = [].into();
86                        val_as_arr!(self, |arr| arr.data.truncate(1));
87                    }
88                } else {
89                    let row_len: usize = shape.iter().skip(depth).product();
90                    shape.truncate(depth);
91                    let elem_count = shape.elements();
92                    val_as_arr!(self, |arr| {
93                        let slice = arr.data.as_mut_slice();
94                        for i in 1..elem_count {
95                            slice[i] = take(&mut slice[i * row_len]);
96                        }
97                        arr.data.truncate(elem_count);
98                    });
99                }
100            }
101            Ordering::Greater => {
102                // Positive rank
103                match rank.cmp(&deep_rank) {
104                    Ordering::Equal => {}
105                    Ordering::Less => {
106                        let mut new_shape: Shape = shape.iter().take(depth).copied().collect();
107                        let mid = shape.len() + 1 - rank;
108                        let new_first_dim: usize = shape[depth..mid].iter().product();
109                        new_shape.extend(once(new_first_dim).chain(shape[mid..].iter().copied()));
110                        *shape = new_shape;
111                    }
112                    Ordering::Greater => {
113                        if extend {
114                            for _ in 0..rank - shape.len() {
115                                shape.insert(depth, 1);
116                            }
117                        } else {
118                            shape.insert(depth, 1);
119                        }
120                    }
121                }
122            }
123            Ordering::Less => {
124                // Negative rank
125                if rank + 1 > deep_rank {
126                    return if extend {
127                        Err(env.error(format!(
128                            "Negative {} has magnitude {}, but the \
129                            rank-{} array cannot be reduced that much",
130                            Primitive::Deshape.format(),
131                            rank,
132                            deep_rank
133                        )))
134                    } else {
135                        Ok(())
136                    };
137                }
138                let mut new_shape: Shape = shape.iter().take(depth).copied().collect();
139                let new_first_dim: usize = shape[depth..=depth + rank].iter().product();
140                new_shape
141                    .extend(once(new_first_dim).chain(shape[depth + rank + 1..].iter().copied()));
142                *shape = new_shape;
143            }
144        }
145        self.meta.take_sorted_flags();
146        self.validate();
147        Ok(())
148    }
149    pub(crate) fn undo_deshape(
150        &mut self,
151        sub: Option<i32>,
152        orig_shape: &Shape,
153        env: &Uiua,
154    ) -> UiuaResult {
155        if let Some(irank) = sub {
156            if self.rank() == 0 {
157                if let Value::Box(arr) = self {
158                    arr.data.as_mut_slice()[0]
159                        .0
160                        .undo_deshape(sub, orig_shape, env)?;
161                }
162                return Ok(());
163            }
164            if irank == 0 {
165                return Ok(());
166            }
167            let rank = irank.unsigned_abs() as usize;
168            let new_shape: Shape = if irank >= 0 {
169                // Positive rank
170                (orig_shape.iter())
171                    .take((orig_shape.len() + 1).saturating_sub(rank))
172                    .chain((self.shape.iter()).skip(rank.saturating_sub(orig_shape.len()).max(1)))
173                    .copied()
174                    .collect()
175            } else {
176                // Negative rank
177                (orig_shape.iter().take(rank + 1))
178                    .chain(self.shape.iter().skip(1))
179                    .copied()
180                    .collect()
181            };
182            if validate_size::<u8>(new_shape.iter().copied(), env)? != self.shape.elements() {
183                return Ok(());
184            }
185            self.shape = new_shape;
186            self.validate();
187            Ok(())
188        } else {
189            let mut new_shape = self.shape.clone();
190            if !new_shape.is_empty() {
191                new_shape.remove(0);
192            }
193            for &d in orig_shape.iter().rev() {
194                new_shape.prepend(d);
195            }
196            if new_shape.elements() == self.shape.elements() {
197                self.shape = new_shape;
198                Ok(())
199            } else {
200                let spec: Vec<Result<isize, bool>> =
201                    orig_shape.iter().map(|&d| Ok(d as isize)).collect();
202                self.reshape_impl(&spec, env)
203            }
204        }
205    }
206    pub(crate) fn box_depth(mut self, depth: usize) -> Array<Boxed> {
207        let depth = depth.min(self.rank());
208        if depth == 0 {
209            return Boxed(self).into();
210        }
211        let per_meta = self.meta.take_per_meta();
212        let new_shape: Shape = self.shape[..depth].into();
213        let row_shape: Shape = self.shape[depth..].into();
214        let data: EcoVec<Boxed> = self.into_row_shaped_slices(row_shape).map(Boxed).collect();
215        let mut arr = Array::new(new_shape, data);
216        arr.meta.set_per_meta(per_meta);
217        arr
218    }
219    /// Attempt to parse the value into a number
220    pub fn parse_num(mut self, env: &Uiua) -> UiuaResult<Self> {
221        let per_meta = self.meta.take_per_meta();
222        let mut parsed = match (self.rank(), self) {
223            (0 | 1, Value::Char(arr)) => {
224                let s: String = arr.data.iter().copied().collect();
225                match (
226                    s.strip_suffix("i").and_then(|s| s.split_once("r")),
227                    s.strip_suffix("i").and_then(|s| s.split_once("+")),
228                    s.strip_suffix("i").and_then(|s| s.split_once("-")),
229                ) {
230                    (Some((re, im)), None, _) | (None, Some((re, im)), _) => {
231                        let re = parse_uiua_num(re.into(), env);
232                        let im = parse_uiua_num(im.into(), env);
233                        re.and_then(|re| im.map(|im| Complex { re, im }.into()))
234                            .or_else(|e| env.value_fill().map(|fv| fv.value.clone()).ok_or(e))?
235                    }
236                    (_, _, Some((re, im))) => {
237                        let re = parse_uiua_num(re.into(), env);
238                        let im = parse_uiua_num(im.into(), env);
239                        re.and_then(|re| im.map(|im| Complex { re, im: -im }.into()))
240                            .or_else(|e| env.value_fill().map(|fv| fv.value.clone()).ok_or(e))?
241                    }
242                    _ => parse_uiua_num(s.into(), env)
243                        .map(Into::into)
244                        .or_else(|e| env.value_fill().map(|fv| fv.value.clone()).ok_or(e))?,
245                }
246            }
247            (0, Value::Box(arr)) => {
248                let Boxed(value) = arr.into_scalar().unwrap();
249                value.parse_num(env)?
250            }
251            (_, val @ (Value::Char(_) | Value::Box(_))) => {
252                let mut rows = Vec::with_capacity(val.row_count());
253                for row in val.into_rows() {
254                    rows.push(row.parse_num(env)?);
255                }
256                Value::from_row_values(rows, env)?
257            }
258            (_, val) => return Err(env.error(format!("Cannot parse {} array", val.type_name()))),
259        };
260        parsed.meta.set_per_meta(per_meta);
261        Ok(parsed)
262    }
263    pub(crate) fn unparse(mut self, env: &Uiua) -> UiuaResult<Self> {
264        let per_meta = self.meta.take_per_meta();
265        let mut unparsed = if self.rank() == 0 {
266            match self {
267                Value::Box(b) => b.into_scalar().unwrap().0.unparse(env)?,
268                value => value.format().into(),
269            }
270        } else {
271            fn padded<T: fmt::Display>(
272                c: char,
273                right: bool,
274                arr: Array<T>,
275                env: &Uiua,
276            ) -> UiuaResult<Array<char>> {
277                let mut buf = Vec::new();
278                let mut max_whole = 0;
279                let mut max_dec = 0;
280                for v in &arr.data {
281                    buf.clear();
282                    write!(&mut buf, "{v}").unwrap();
283                    if let Some(i) = buf.iter().position(|&c| c == b'.') {
284                        max_whole = max_whole.max(i);
285                        max_dec = max_dec.max(buf.len() - i - 1);
286                    } else {
287                        max_whole = max_whole.max(buf.len());
288                    }
289                }
290                let max_len = if max_dec == 0 {
291                    max_whole
292                } else {
293                    max_whole + max_dec + 1
294                };
295                let mut new_shape = arr.shape.clone();
296                new_shape.push(max_len);
297                let elem_count = validate_size::<char>(new_shape.iter().copied(), env)?;
298                let mut new_data = eco_vec![c; elem_count];
299                if max_len > 0 {
300                    for (i, s) in new_data.make_mut().chunks_exact_mut(max_len).enumerate() {
301                        let n = arr.data[i].to_string();
302                        let dot_pos = n.find('.');
303                        if right {
304                            for (s, c) in s.iter_mut().zip(n.chars()) {
305                                *s = c;
306                            }
307                        } else {
308                            let skip = if max_dec == 0 {
309                                0
310                            } else {
311                                dot_pos
312                                    .map(|i| max_dec - (n.len() - i - 1))
313                                    .unwrap_or(max_dec + 1)
314                            };
315                            for (s, c) in s.iter_mut().rev().skip(skip).zip(n.chars().rev()) {
316                                *s = c;
317                            }
318                        }
319                        if dot_pos.is_none() && max_dec > 0 && c.is_ascii_digit() {
320                            s[max_whole] = '.';
321                        }
322                    }
323                }
324                Ok(Array::new(new_shape, new_data))
325            }
326
327            match self {
328                Value::Num(arr) => {
329                    if let Ok(c) = env.scalar_fill::<char>() {
330                        padded(c.value, c.is_right(), arr, env)?.into()
331                    } else {
332                        let new_data: CowSlice<Boxed> = (arr.data.iter().map(|v| v.to_string()))
333                            .map(Value::from)
334                            .map(Boxed)
335                            .collect();
336                        Array::new(arr.shape.clone(), new_data).into()
337                    }
338                }
339                Value::Byte(arr) => {
340                    if let Ok(c) = env.scalar_fill::<char>() {
341                        padded(c.value, c.is_right(), arr, env)?.into()
342                    } else {
343                        let new_data: CowSlice<Boxed> = (arr.data.iter().map(|v| v.to_string()))
344                            .map(Value::from)
345                            .map(Boxed)
346                            .collect();
347                        Array::new(arr.shape.clone(), new_data).into()
348                    }
349                }
350                Value::Complex(arr) => {
351                    let new_data: CowSlice<Boxed> = (arr.data.iter().map(|v| v.to_string()))
352                        .map(Value::from)
353                        .map(Boxed)
354                        .collect();
355                    Array::new(arr.shape.clone(), new_data).into()
356                }
357                val => return Err(env.error(format!("Cannot unparse {} array", val.type_name()))),
358            }
359        };
360        unparsed.meta.set_per_meta(per_meta);
361        Ok(unparsed)
362    }
363}
364
365fn parse_uiua_num(mut s: Cow<str>, env: &Uiua) -> UiuaResult<f64> {
366    let mut mul = 1.0;
367    if s.contains('¯') {
368        s = s.replace('¯', "-").into();
369    }
370    if s.contains('`') {
371        s = s.replace('`', "-").into();
372    }
373    'glyphs: for (names, constant) in [
374        (["η", "eta"], PI * 0.5),
375        (["π", "pi"], PI),
376        (["τ", "tau"], TAU),
377        (["∞", "inf"], f64::INFINITY),
378    ] {
379        if let Some((before, after)) = s.split_once('/') {
380            for name in names {
381                if before.trim_start_matches('-') == name {
382                    s = format!("{}/{}", before.replace(name, &constant.to_string()), after).into();
383                    break 'glyphs;
384                } else if let Some(start) = before.strip_suffix(name) {
385                    mul = constant;
386                    s = format!("{}/{}", start, after).into();
387                    break 'glyphs;
388                }
389            }
390        } else {
391            for name in names {
392                if s.trim_start_matches('-') == name {
393                    s = s.replace(name, &constant.to_string()).into();
394                    break 'glyphs;
395                } else if let Some(start) = s.strip_suffix(name) {
396                    mul = constant;
397                    s = start.to_string().into();
398                    break 'glyphs;
399                }
400            }
401        }
402    }
403    match s.split_once('/') {
404        Some((numer, denom)) => numer
405            .parse::<f64>()
406            .and_then(|n| denom.parse::<f64>().map(|d| n / d)),
407        None => s.parse::<f64>(),
408    }
409    .map(|n| n * mul)
410    .map_err(|e| env.error(format!("Cannot parse into number: {}", e)))
411}
412
413impl<T: ArrayValue> Array<T> {
414    /// Make the array 1-dimensional
415    pub fn deshape(&mut self) {
416        if self.rank() == 1 {
417            return;
418        }
419        if self.is_map() {
420            self.meta.take_map_keys();
421        }
422        self.shape.deshape();
423    }
424    /// Add a 1-length dimension to the front of the array's shape
425    pub fn fix(&mut self) {
426        self.fix_depth(0);
427    }
428    pub(crate) fn fix_depth(&mut self, depth: usize) {
429        let depth = self.shape.fix_depth(depth);
430        if depth == 0 {
431            if let Some(keys) = self.meta.map_keys_mut() {
432                keys.fix();
433            }
434        }
435    }
436    /// Remove a 1-length dimension from the front of the array's shape
437    pub fn unfix(&mut self, env: &Uiua) -> UiuaResult {
438        if let Some(keys) = self.meta.map_keys_mut() {
439            keys.unfix();
440        }
441        self.shape.unfix().map_err(|e| env.error(e))?;
442        self.validate();
443        Ok(())
444    }
445    /// Collapse the top two dimensions of the array's shape
446    pub fn undo_fix(&mut self) {
447        if let Some(keys) = self.meta.map_keys_mut() {
448            keys.unfix();
449        }
450        _ = self.shape.unfix();
451        self.validate();
452    }
453}
454
455impl<T: ArrayValue> Array<T>
456where
457    Value: From<Array<T>>,
458{
459    pub(crate) fn box_depth(mut self, depth: usize) -> Array<Boxed> {
460        let depth = depth.min(self.rank());
461        if depth == 0 {
462            return Boxed(self.into()).into();
463        }
464        let per_meta = self.meta.take_per_meta();
465        let new_shape: Shape = self.shape[..depth].into();
466        let row_shape: Shape = self.shape[depth..].into();
467        let data: EcoVec<Boxed> = self
468            .into_row_shaped_slices(row_shape)
469            .map(Value::from)
470            .map(Boxed)
471            .collect();
472        let mut arr = Array::new(new_shape, data);
473        arr.meta.set_per_meta(per_meta);
474        arr
475    }
476}
477
478impl Value {
479    /// Create a `range` array
480    pub fn range(&self, env: &Uiua) -> UiuaResult<Self> {
481        self.range_start_impl(0, env)
482    }
483    pub(crate) fn range_start(&self, shape: &Self, env: &Uiua) -> UiuaResult<Self> {
484        let start = self.as_num(env, "Range start should be a scalar number")?;
485        if start.fract() == 0.0 && (isize::MIN as f64..=isize::MAX as f64).contains(&start) {
486            shape.range_start_impl(start as isize, env)
487        } else {
488            let range = shape.range(env)?;
489            self.clone().add(range, env)
490        }
491    }
492    fn range_start_impl(&self, start: isize, env: &Uiua) -> UiuaResult<Self> {
493        let ishape = self.as_ints(
494            env,
495            "Range max should be a single integer \
496            or a list of integers",
497        )?;
498        if self.rank() == 0 {
499            let max = ishape[0];
500            let mut value: Value = if max >= 0 {
501                if start >= 0 && max + start <= 256 {
502                    (start..max + start).map(|i| i as u8).collect()
503                } else {
504                    validate_size::<f64>([max.unsigned_abs()], env)?;
505                    (start..max + start).map(|i| i as f64).collect()
506                }
507            } else {
508                validate_size::<f64>([max.unsigned_abs()], env)?;
509                (max + start..start).map(|i| i as f64).rev().collect()
510            };
511            value.meta.mark_sorted_up(max >= 0);
512            value.meta.mark_sorted_down(max <= 0);
513            value.validate();
514            return Ok(value);
515        }
516        if ishape.is_empty() {
517            return Ok(Array::<f64>::new(0, CowSlice::new()).into());
518        }
519        let mut shape = Shape::from_iter(ishape.iter().map(|d| d.unsigned_abs()));
520        shape.push(shape.len());
521        let data = range(&ishape, start, env)?;
522        let mut value: Value = match data {
523            Ok(data) => Array::new(shape, data).into(),
524            Err(data) => Array::new(shape, data).into(),
525        };
526        let first_max = ishape.first().copied().unwrap_or(0);
527        value.meta.mark_sorted_up(first_max >= 0);
528        value.meta.mark_sorted_down(first_max <= 0);
529        value.validate();
530        Ok(value)
531    }
532    pub(crate) fn unshape(&self, env: &Uiua) -> UiuaResult<Self> {
533        let ishape = self.as_ints(
534            env,
535            "Shape should be a single integer or a list of integers",
536        )?;
537        let shape = Shape::from_iter(ishape.iter().map(|n| n.unsigned_abs()));
538        let elems: usize = validate_size::<f64>(shape.iter().copied(), env)?;
539        let data = EcoVec::from_iter((0..elems).map(|i| i as f64));
540        let mut arr = Array::new(shape, data);
541        let first_max = ishape.first().copied().unwrap_or(0);
542        for (i, s) in ishape.into_iter().enumerate() {
543            if s < 0 {
544                arr.reverse_depth(i);
545            }
546        }
547        arr.meta.mark_sorted_up(first_max >= 0);
548        arr.meta.mark_sorted_down(first_max <= 0);
549        Ok(arr.into())
550    }
551}
552
553pub(crate) fn range(
554    shape: &[isize],
555    start: isize,
556    env: &Uiua,
557) -> UiuaResult<Result<CowSlice<f64>, CowSlice<u8>>> {
558    if shape.is_empty() {
559        return Ok(Err(cowslice![0]));
560    }
561    let mut prod = 1usize;
562    for &d in shape {
563        if d != 0 {
564            let (new, overflow) = prod.overflowing_mul(d.unsigned_abs());
565            if overflow {
566                let mut starting_with = "[".to_string();
567                for (i, d) in shape.iter().take(3).enumerate() {
568                    if i > 0 {
569                        starting_with.push_str(" × ");
570                    }
571                    starting_with.push_str(&d.to_string());
572                }
573                if shape.len() > 3 {
574                    starting_with.push_str(" × …");
575                }
576                starting_with.push(']');
577                return Err(env.error(format!(
578                    "{} of length-{} shape {} would be too large",
579                    Primitive::Range.format(),
580                    shape.len(),
581                    starting_with
582                )));
583            }
584            prod = new;
585        }
586    }
587    if shape.contains(&0) {
588        return Ok(Err(CowSlice::new()));
589    }
590    let mut len = shape.len();
591    for &item in shape {
592        let (new, overflow) = len.overflowing_mul(item.unsigned_abs());
593        if overflow || new > 2usize.pow(30) / size_of::<f64>() {
594            let len = shape.len() as f64 * shape.iter().map(|d| *d as f64).product::<f64>();
595            return Err(env.error(format!(
596                "Attempting to make a range from shape {} would \
597                create an array with {} elements, which is too large",
598                FormatShape(&shape.iter().map(|d| d.unsigned_abs()).collect::<Vec<_>>()),
599                len
600            )));
601        }
602        len = new;
603    }
604    let mut scan = shape
605        .iter()
606        .rev()
607        .scan(1, |acc, &d| {
608            let old = *acc;
609            *acc *= d.unsigned_abs();
610            Some(old)
611        })
612        .collect::<Vec<usize>>();
613    scan.reverse();
614    let elem_count = shape.len() * shape.iter().map(|d| d.unsigned_abs()).product::<usize>();
615    let any_neg = shape.iter().any(|&d| d < 0);
616    let max = shape.iter().map(|d| d.unsigned_abs()).max().unwrap();
617    if start >= 0 && max as isize + start <= 256 && !any_neg {
618        validate_size::<u8>([len], env)?;
619        let mut data: EcoVec<u8> = eco_vec![0; len];
620        let data_slice = data.make_mut();
621        let start = start.unsigned_abs();
622        for i in 0..elem_count {
623            let dim = i % shape.len();
624            let index = i / shape.len();
625            data_slice[i] = (index / scan[dim] % shape[dim].unsigned_abs() + start) as u8;
626        }
627        Ok(Err(data.into()))
628    } else {
629        validate_size::<f64>([len], env)?;
630        let mut data: EcoVec<f64> = eco_vec![0.0; len];
631        let data_slice = data.make_mut();
632        let start = start as f64;
633        for i in 0..elem_count {
634            let dim = i % shape.len();
635            let index = i / shape.len();
636            data_slice[i] = (index / scan[dim] % shape[dim].unsigned_abs()) as f64;
637            if shape[dim] < 0 {
638                data_slice[i] = -1.0 - data_slice[i];
639            }
640            data_slice[i] += start;
641        }
642        Ok(Ok(data.into()))
643    }
644}
645
646impl Value {
647    /// Get the first row of the value
648    pub fn first(self, env: &Uiua) -> UiuaResult<Self> {
649        self.first_depth(0, env)
650    }
651    pub(crate) fn first_depth(mut self, depth: usize, env: &Uiua) -> UiuaResult<Self> {
652        self.match_fill(env);
653        val_as_arr!(self, |a| a.first_depth(depth, env).map(Into::into))
654    }
655    /// Get the last row of the value
656    pub fn last(self, env: &Uiua) -> UiuaResult<Self> {
657        self.last_depth(0, env)
658    }
659    pub(crate) fn last_depth(mut self, depth: usize, env: &Uiua) -> UiuaResult<Self> {
660        self.match_fill(env);
661        val_as_arr!(self, |a| a.last_depth(depth, env).map(Into::into))
662    }
663    pub(crate) fn undo_first(self, into: Self, env: &Uiua) -> UiuaResult<Self> {
664        into.try_map_boxed(|into| {
665            self.generic_bin_into(
666                into.unboxed(),
667                |a, b| a.undo_first(b, env).map(Into::into),
668                |a, b| a.undo_first(b, env).map(Into::into),
669                |a, b| a.undo_first(b, env).map(Into::into),
670                |a, b| a.undo_first(b, env).map(Into::into),
671                |a, b| a.undo_first(b, env).map(Into::into),
672                |a, b| {
673                    env.error(format!(
674                        "Cannot unfirst {} into {}",
675                        a.type_name(),
676                        b.type_name()
677                    ))
678                },
679            )
680        })
681    }
682    pub(crate) fn undo_last(self, into: Self, env: &Uiua) -> UiuaResult<Self> {
683        into.try_map_boxed(|into| {
684            self.generic_bin_into(
685                into.unboxed(),
686                |a, b| a.undo_last(b, env).map(Into::into),
687                |a, b| a.undo_last(b, env).map(Into::into),
688                |a, b| a.undo_last(b, env).map(Into::into),
689                |a, b| a.undo_last(b, env).map(Into::into),
690                |a, b| a.undo_last(b, env).map(Into::into),
691                |a, b| {
692                    env.error(format!(
693                        "Cannot unlast {} into {}",
694                        a.type_name(),
695                        b.type_name()
696                    ))
697                },
698            )
699        })
700    }
701}
702
703impl<T: ArrayValue> Array<T> {
704    /// Get the first row of the array
705    pub fn first(mut self, env: &Uiua) -> UiuaResult<Self> {
706        match &*self.shape {
707            [] => Ok(self),
708            [0, rest @ ..] => match env.scalar_fill() {
709                Ok(fill) => {
710                    self.data.extend_repeat(&fill.value, self.row_len());
711                    self.shape = rest.into();
712                    Ok(self)
713                }
714                Err(e) => Err(env
715                    .error(format!(
716                        "Cannot take {} of an empty array{e}",
717                        Primitive::First.format()
718                    ))
719                    .fill()),
720            },
721            _ => {
722                let row_len = self.row_len();
723                self.shape.remove(0);
724                self.data.truncate(row_len);
725                self.meta.take_map_keys();
726                self.meta.take_label();
727                Ok(self)
728            }
729        }
730    }
731    pub(crate) fn first_depth(mut self, mut depth: usize, env: &Uiua) -> UiuaResult<Self> {
732        depth = depth.min(self.rank());
733        if depth == 0 {
734            return self.first(env);
735        }
736        match &self.shape[depth..] {
737            [] => Ok(self),
738            [0, rest @ ..] => match env.scalar_fill() {
739                Ok(fill) => {
740                    self.shape = self.shape[..depth].iter().chain(rest).copied().collect();
741                    self.data.extend_repeat(&fill.value, self.shape.elements());
742                    self.validate();
743                    Ok(self)
744                }
745                Err(e) => Err(env
746                    .error(format!(
747                        "Cannot take {} of an empty array{e}",
748                        Primitive::First.format()
749                    ))
750                    .fill()),
751            },
752            [1, ..] => {
753                self.shape.remove(depth);
754                self.validate();
755                Ok(self)
756            }
757            [n, rest @ ..] => {
758                let row_len: usize = rest.iter().product();
759                let row_count: usize = self.shape[..depth].iter().product();
760                let slice = self.data.as_mut_slice();
761                for i in 1..row_count {
762                    let dest = i * row_len;
763                    let src = i * *n * row_len;
764                    unsafe {
765                        ptr::swap_nonoverlapping(
766                            slice.as_mut_ptr().add(dest),
767                            slice.as_mut_ptr().add(src),
768                            row_len,
769                        )
770                    };
771                }
772                self.shape.remove(depth);
773                self.data.truncate(self.shape.elements());
774                self.validate();
775                Ok(self)
776            }
777        }
778    }
779    /// Get the last row of the array
780    pub fn last(mut self, env: &Uiua) -> UiuaResult<Self> {
781        match &*self.shape {
782            [] => Ok(self),
783            [0, rest @ ..] => match env.scalar_fill() {
784                Ok(fill) => {
785                    self.data.extend_repeat(&fill.value, self.row_len());
786                    self.shape = rest.into();
787                    Ok(self)
788                }
789                Err(e) => Err(env
790                    .error(format!("Cannot take last of an empty array{e}"))
791                    .fill()),
792            },
793            _ => {
794                let row_len = self.row_len();
795                self.shape.remove(0);
796                let prefix_len = self.data.len() - row_len;
797                self.data = self.data[prefix_len..].into();
798                self.meta.take_map_keys();
799                self.meta.take_label();
800                Ok(self)
801            }
802        }
803    }
804    pub(crate) fn last_depth(mut self, mut depth: usize, env: &Uiua) -> UiuaResult<Self> {
805        depth = depth.min(self.rank());
806        if depth == 0 {
807            return self.last(env);
808        }
809        match &self.shape[depth..] {
810            [] => Ok(self),
811            [0, rest @ ..] => match env.scalar_fill() {
812                Ok(fill) => {
813                    self.shape = self.shape[..depth].iter().chain(rest).copied().collect();
814                    self.data.extend_repeat(&fill.value, self.shape.elements());
815                    Ok(self)
816                }
817                Err(e) => Err(env
818                    .error(format!("Cannot take last of an empty array{e}"))
819                    .fill()),
820            },
821            [1, ..] => {
822                self.shape.remove(depth);
823                self.validate();
824                Ok(self)
825            }
826            [n, rest @ ..] => {
827                let row_len: usize = rest.iter().product();
828                let row_count: usize = self.shape[..depth].iter().product();
829                let slice = self.data.as_mut_slice();
830                for i in 0..row_count {
831                    let dest = i * row_len;
832                    let src = (i + 1) * *n * row_len - row_len;
833                    unsafe {
834                        ptr::swap_nonoverlapping(
835                            slice.as_mut_ptr().add(dest),
836                            slice.as_mut_ptr().add(src),
837                            row_len,
838                        )
839                    };
840                }
841                self.shape.remove(depth);
842                self.data.truncate(self.shape.elements());
843                self.validate();
844                Ok(self)
845            }
846        }
847    }
848    pub(crate) fn undo_first(self, into: Self, env: &Uiua) -> UiuaResult<Self> {
849        self.join(into.drop(&[Ok(1)], env)?, true, env)
850    }
851    pub(crate) fn undo_last(self, into: Self, env: &Uiua) -> UiuaResult<Self> {
852        into.drop(&[Ok(-1)], env)?.join(self, true, env)
853    }
854}
855
856impl Value {
857    /// Reverse the rows of the value
858    pub fn reverse(&mut self) {
859        self.reverse_depth(0);
860    }
861    pub(crate) fn reverse_depth(&mut self, depth: usize) {
862        self.generic_mut_deep(
863            |a| a.reverse_depth(depth),
864            |a| a.reverse_depth(depth),
865            |a| a.reverse_depth(depth),
866            |a| a.reverse_depth(depth),
867            |a| a.reverse_depth(depth),
868        )
869    }
870}
871
872impl<T: ArrayValue> Array<T> {
873    /// Reverse the rows of the array
874    pub fn reverse(&mut self) {
875        self.reverse_depth(0);
876    }
877    pub(crate) fn reverse_depth(&mut self, mut depth: usize) {
878        depth = depth.min(self.rank());
879        let row_shape = &self.shape[depth..];
880        if row_shape.is_empty() {
881            return;
882        }
883        let chunk_size = row_shape.iter().product();
884        if chunk_size == 0 {
885            return;
886        }
887        let sorted_up = self.meta.is_sorted_up();
888        let sorted_down = self.meta.is_sorted_down();
889        let data = self.data.as_mut_slice();
890        let chunk_row_count = self.shape[depth];
891        let chunk_row_len = chunk_size / chunk_row_count;
892        for data in data.chunks_exact_mut(chunk_size) {
893            for i in 0..chunk_row_count / 2 {
894                let left = i * chunk_row_len;
895                let right = (chunk_row_count - i - 1) * chunk_row_len;
896                let left = &mut data[left] as *mut T;
897                let right = &mut data[right] as *mut T;
898                unsafe {
899                    ptr::swap_nonoverlapping(left, right, chunk_row_len);
900                }
901            }
902        }
903
904        // Reverse map keys
905        if depth == 0 {
906            if let Some(meta) = self.meta.get_mut() {
907                if let Some(keys) = &mut meta.map_keys {
908                    keys.reverse();
909                }
910            }
911            self.meta.mark_sorted_up(sorted_down);
912            self.meta.mark_sorted_down(sorted_up);
913        } else {
914            self.meta.take_sorted_flags();
915        }
916        self.validate();
917    }
918}
919
920impl Value {
921    /// Transpose the value
922    pub fn transpose(&mut self) {
923        self.generic_mut_deep(
924            Array::transpose,
925            Array::transpose,
926            Array::transpose,
927            Array::transpose,
928            Array::transpose,
929        )
930    }
931    pub(crate) fn transpose_depth(&mut self, depth: usize, amnt: i32) {
932        match self {
933            Value::Num(n) => n.transpose_depth(depth, amnt),
934            Value::Byte(b) => b.transpose_depth(depth, amnt),
935            Value::Complex(c) => c.transpose_depth(depth, amnt),
936            Value::Char(c) => c.transpose_depth(depth, amnt),
937            Value::Box(b) => {
938                if depth == b.rank() {
939                    for b in b.data.as_mut_slice() {
940                        b.0.transpose();
941                    }
942                } else {
943                    b.transpose_depth(depth, amnt);
944                }
945            }
946        }
947    }
948    /// Like transpose, but the axes are reversed instead of rotated
949    pub(crate) fn retropose_depth(&mut self, depth: usize) {
950        match self {
951            Value::Num(n) => n.retropose_depth(depth),
952            Value::Byte(b) => b.retropose_depth(depth),
953            Value::Complex(c) => c.retropose_depth(depth),
954            Value::Char(c) => c.retropose_depth(depth),
955            Value::Box(b) => {
956                if depth == b.rank() {
957                    for b in b.data.as_mut_slice() {
958                        b.0.retropose_depth(0);
959                    }
960                } else {
961                    b.retropose_depth(depth);
962                }
963            }
964        }
965    }
966}
967
968impl<T: ArrayValue> Array<T> {
969    /// Transpose the array
970    pub fn transpose(&mut self) {
971        self.transpose_depth(0, 1);
972    }
973    /// Untranspose the array
974    pub fn untranspose(&mut self) {
975        self.transpose_depth(0, -1);
976    }
977    pub(crate) fn transpose_depth(&mut self, mut depth: usize, amnt: i32) {
978        crate::profile_function!();
979        if depth == 0 && self.is_map() {
980            self.meta.take_map_keys();
981        }
982        if self.rank() == 0 {
983            return;
984        }
985        depth = depth.min(self.rank());
986        let trans_count = amnt.unsigned_abs() as usize % self.rank();
987        let trans_rank = self.rank() - depth;
988        // Early return if nothing would actually happen
989        if trans_rank < 2 || depth + trans_count == self.rank() || trans_count == 0 {
990            return;
991        }
992        self.meta.take_sorted_flags();
993        let forward = amnt.is_positive();
994        // Early return if any dimension is 0, because there are no elements
995        if self.shape[depth..].iter().any(|&d| d == 0) || depth > 0 && self.shape[depth - 1] == 0 {
996            if forward {
997                self.shape[depth..].rotate_left(trans_count);
998            } else {
999                self.shape[depth..].rotate_right(trans_count);
1000            }
1001            return;
1002        }
1003        let square_matrix = trans_rank == 2 && self.shape[depth] == self.shape[depth + 1];
1004        let s = self.shape[depth];
1005        // Count the number of subarrays
1006        let subs: usize = if forward {
1007            self.shape[depth..].iter().take(trans_count).product()
1008        } else {
1009            self.shape[depth..].iter().rev().skip(trans_count).product()
1010        };
1011        let data_slice = self.data.as_mut_slice();
1012        // Divide the array into chunks at the given depth
1013        for data in data_slice.chunks_exact_mut(self.shape[depth..].iter().product()) {
1014            // Special in-place case for square matrices
1015            if square_matrix {
1016                if subs > 500 {
1017                    // This is pretty unsafe, but no indices should collide, so it's fine? 🤷
1018                    let ptr: usize = data.as_mut_ptr() as usize;
1019                    (0..s - 1).into_par_iter().for_each(|i| {
1020                        let ptr: *mut T = ptr as *mut _;
1021                        for j in i + 1..s {
1022                            unsafe {
1023                                ptr::swap_nonoverlapping(ptr.add(i * s + j), ptr.add(j * s + i), 1);
1024                            }
1025                        }
1026                    });
1027                } else {
1028                    for i in 0..s - 1 {
1029                        for j in i + 1..s {
1030                            data.swap(i * s + j, j * s + i);
1031                        }
1032                    }
1033                }
1034                continue;
1035            }
1036            let stride = data.len() / subs;
1037            // The operation to perform on each subarray
1038            let op = |(temp_chunk_i, chunk): (usize, &mut [T])| {
1039                for (chunk_i, item) in chunk.iter_mut().enumerate() {
1040                    *item = data[chunk_i * stride + temp_chunk_i].clone();
1041                }
1042            };
1043            // Perform the operation on each subarray
1044            let mut temp = data.to_vec();
1045            if subs > 500 {
1046                temp.par_chunks_mut(subs).enumerate().for_each(op);
1047            } else {
1048                temp.chunks_mut(subs).enumerate().for_each(op);
1049            }
1050            data.clone_from_slice(&temp);
1051        }
1052        if forward {
1053            self.shape[depth..].rotate_left(trans_count);
1054        } else {
1055            self.shape[depth..].rotate_right(trans_count);
1056        }
1057    }
1058    /// Like transpose, but the axes are reversed instead of rotated
1059    pub(crate) fn retropose_depth(&mut self, mut depth: usize) {
1060        crate::profile_function!();
1061        if depth == 0 && self.is_map() {
1062            self.meta.take_map_keys();
1063        }
1064        if self.rank() == 0 {
1065            return;
1066        }
1067        depth = depth.min(self.rank());
1068        let trans_rank = self.rank() - depth;
1069        // Early return if nothing would actually happen
1070        if trans_rank < 2 {
1071            return;
1072        }
1073        self.meta.take_sorted_flags();
1074        // Early return if any dimension is 0, because there are no elements
1075        if self.shape[depth..].iter().any(|&d| d == 0) || depth > 0 && self.shape[depth - 1] == 0 {
1076            self.shape[depth..].reverse();
1077            return;
1078        }
1079        let subshape = Shape::from(&self.shape[depth..]);
1080        let newshape = Shape::from_iter(subshape.iter().rev().copied());
1081        let chunk_size = subshape.elements();
1082        let data_slice = self.data.as_mut_slice();
1083        let mut temp = data_slice[..chunk_size].to_vec();
1084        let mut dims = vec![0; subshape.len()];
1085        // Divide the array into chunks at the given depth
1086        for data in data_slice.chunks_exact_mut(chunk_size) {
1087            for i in 0..chunk_size {
1088                subshape.flat_to_dims(i, &mut dims);
1089                dims.reverse();
1090                let j = newshape.dims_to_flat(&dims).unwrap();
1091                temp[j] = data[i].clone();
1092            }
1093            data.swap_with_slice(&mut temp);
1094        }
1095        self.shape[depth..].reverse();
1096    }
1097}
1098
1099impl Value {
1100    /// `classify` the rows of the value
1101    pub fn classify(&self) -> Self {
1102        if self.rank() == 0 {
1103            return 0.into();
1104        }
1105        let map_keys = self.meta.map_keys.clone();
1106        let mut val: Value = val_as_arr!(self, Array::classify).into_iter().collect();
1107        if let Some(map_keys) = map_keys {
1108            val.meta.map_keys = Some(map_keys);
1109        }
1110        val.meta.mark_sorted_up(self.meta.is_sorted_up());
1111        val.validate();
1112        val
1113    }
1114    pub(crate) fn classify_depth(&self, depth: usize) -> Self {
1115        let map_keys = self.meta.map_keys.clone();
1116        let mut val = val_as_arr!(self, |a| a.classify_depth(depth));
1117        if let Some(map_keys) = map_keys {
1118            val.meta.map_keys = Some(map_keys);
1119        }
1120        val.validate();
1121        val
1122    }
1123    /// `deduplicate` the rows of the value
1124    pub fn deduplicate(&mut self, env: &Uiua) -> UiuaResult {
1125        val_as_arr!(self, |a| a.deduplicate(env))
1126    }
1127    /// Mask the `unique` rows of the value
1128    pub fn unique(&self) -> Self {
1129        val_as_arr!(self, Array::unique).into()
1130    }
1131    /// Count the unique rows of the value
1132    pub fn count_unique(&self) -> usize {
1133        val_as_arr!(self, Array::count_unique)
1134    }
1135    /// Check that all values are true
1136    pub fn all_true(&self) -> bool {
1137        match self {
1138            Value::Num(arr) => arr.data.iter().all(|&n| n == 1.0),
1139            Value::Byte(arr) => arr.data.iter().all(|&b| b == 1),
1140            Value::Char(_) => false,
1141            Value::Box(arr) => arr.data.iter().all(|Boxed(val)| val.all_true()),
1142            Value::Complex(arr) => arr.data.iter().all(|&c| c.re == 1.0 && c.im == 1.0),
1143        }
1144    }
1145    /// Count which occurrence of each row that row is
1146    pub fn occurrences(&self) -> Array<f64> {
1147        val_as_arr!(self, Array::occurrences)
1148    }
1149}
1150
1151impl<T: ArrayValue> Array<T> {
1152    /// `classify` the rows of the array
1153    pub fn classify(&self) -> Vec<usize> {
1154        let mut classified = Vec::with_capacity(self.row_count());
1155        if self.meta.is_sorted_up() {
1156            let mut rows = self.row_slices().map(ArrayCmpSlice);
1157            if let Some(mut prev) = rows.next() {
1158                let mut curr_class = 0;
1159                classified.push(curr_class);
1160                for row in rows {
1161                    if row != prev {
1162                        curr_class += 1;
1163                        prev = row;
1164                    }
1165                    classified.push(curr_class);
1166                }
1167            }
1168            classified
1169        } else {
1170            let mut classes = HashMap::new();
1171            for row in self.row_slices().map(ArrayCmpSlice) {
1172                let new_class = classes.len();
1173                let class = *classes.entry(row).or_insert(new_class);
1174                classified.push(class);
1175            }
1176            classified
1177        }
1178    }
1179    fn classify_depth(&self, mut depth: usize) -> Value {
1180        if self.rank() == 0 {
1181            return 0.into();
1182        }
1183        depth = depth.min(self.rank());
1184        let row_shape = Shape::from(&self.shape[depth..]);
1185        let mut classes = HashMap::new();
1186        let row_row_count = row_shape.row_count();
1187        let classified_shape = Shape::from(&self.shape[..=depth.min(self.rank() - 1)]);
1188        let mut i = 0;
1189        let val: Value = if row_row_count < 256 {
1190            // Fits in a u8
1191            let mut classified = eco_vec![0u8; classified_shape.elements()];
1192            if row_shape.elements() == 0 || row_shape.row_len() == 0 {
1193                return Array::new(classified_shape, classified).into();
1194            }
1195            let classified_slice = classified.make_mut();
1196            for row in self.data.chunks_exact(row_shape.elements()) {
1197                classes.clear();
1198                for row in row.chunks_exact(row_shape.row_len()) {
1199                    let new_class = classes.len();
1200                    let class = *classes.entry(ArrayCmpSlice(row)).or_insert(new_class);
1201                    classified_slice[i] = class as u8;
1202                    i += 1;
1203                }
1204            }
1205            Array::new(classified_shape, classified).into()
1206        } else {
1207            // Doesn't fit in a u8
1208            let mut classified = eco_vec![0.0; classified_shape.elements()];
1209            if row_shape.elements() == 0 || row_shape.row_len() == 0 {
1210                return Array::new(classified_shape, classified).into();
1211            }
1212            let classified_slice = classified.make_mut();
1213            for row in self.data.chunks_exact(row_shape.elements()) {
1214                classes.clear();
1215                for row in row.chunks_exact(row_shape.row_len()) {
1216                    let new_class = classes.len();
1217                    let class = *classes.entry(ArrayCmpSlice(row)).or_insert(new_class);
1218                    classified_slice[i] = class as f64;
1219                    i += 1;
1220                }
1221            }
1222            Array::new(classified_shape, classified).into()
1223        };
1224        val.validate();
1225        val
1226    }
1227    /// `deduplicate` the rows of the array
1228    pub fn deduplicate(&mut self, env: &Uiua) -> UiuaResult {
1229        if self.rank() == 0 {
1230            return Ok(());
1231        }
1232        let map_keys_unique = self
1233            .meta
1234            .take_map_keys()
1235            .map(|keys| (keys.normalized(), self.unique()));
1236        let row_count = self.row_count();
1237        let row_len = self.row_len();
1238        let mut new_len = 0;
1239        if self.meta.is_sorted_up() || self.meta.is_sorted_down() {
1240            if row_count > 0 {
1241                let slice = self.data.as_mut_slice();
1242                if row_count > 0 {
1243                    new_len += 1;
1244                }
1245                for i in 1..row_count {
1246                    let prev_start = (new_len - 1) * row_len;
1247                    let prev_end = prev_start + row_len;
1248                    let curr_start = i * row_len;
1249                    let curr_end = curr_start + row_len;
1250                    if ArrayCmpSlice(&slice[prev_start..prev_end])
1251                        != ArrayCmpSlice(&slice[curr_start..curr_end])
1252                    {
1253                        for j in 0..row_len {
1254                            slice[new_len * row_len + j] = slice[curr_start + j].clone();
1255                        }
1256                        new_len += 1;
1257                    }
1258                }
1259                self.data.truncate(new_len * row_len);
1260            }
1261        } else {
1262            let mut seen = HashSet::new();
1263            let mut deduped = CowSlice::new();
1264            for row in self.row_slices() {
1265                if seen.insert(ArrayCmpSlice(row)) {
1266                    deduped.extend_from_slice(row);
1267                    new_len += 1;
1268                }
1269            }
1270            self.data = deduped;
1271        }
1272        self.shape[0] = new_len;
1273        if let Some((keys, unique)) = map_keys_unique {
1274            let keys = Value::from(unique).keep(keys, env)?;
1275            self.map(keys, env)?;
1276        }
1277        self.validate();
1278        Ok(())
1279    }
1280    /// Mask the `unique` rows of the array
1281    pub fn unique(&self) -> Array<u8> {
1282        if self.rank() == 0 {
1283            return 1u8.into();
1284        }
1285        let map_keys = self.meta.map_keys.clone();
1286        let mut seen = HashSet::new();
1287        let mut mask = eco_vec![0u8; self.row_count()];
1288        let mask_slice = mask.make_mut();
1289        for (i, row) in self.row_slices().enumerate() {
1290            if seen.insert(ArrayCmpSlice(row)) {
1291                mask_slice[i] = 1;
1292            }
1293        }
1294        let mut arr = Array::new([self.row_count()], mask);
1295        arr.meta.flags.set(ArrayFlags::BOOLEAN, true);
1296        arr.meta.map_keys = map_keys;
1297        arr
1298    }
1299    /// Count the number of unique rows in the array
1300    pub fn count_unique(&self) -> usize {
1301        let mut seen = HashSet::new();
1302        self.row_slices()
1303            .filter(|row| seen.insert(ArrayCmpSlice(row)))
1304            .count()
1305    }
1306    /// Count which occurrence of each row that row is
1307    pub fn occurrences(&self) -> Array<f64> {
1308        let mut data = eco_vec![0.0; self.row_count()];
1309        let shape: Shape = self.shape.iter().take(1).copied().collect();
1310        if self.row_count() == 0 {
1311            return Array::new(shape, data);
1312        }
1313        let slice = data.make_mut();
1314        if self.meta.is_sorted_up() || self.meta.is_sorted_down() {
1315            let mut rows = self.row_slices().map(ArrayCmpSlice);
1316            let mut prev = rows.next().unwrap();
1317            slice[0] = 0.0;
1318            let mut next_count = 1.0;
1319            for (row, count) in rows.zip(slice.iter_mut().skip(1)) {
1320                if row == prev {
1321                    *count = next_count;
1322                    next_count += 1.0;
1323                } else {
1324                    *count = 0.0;
1325                    next_count = 1.0;
1326                }
1327                prev = row;
1328            }
1329        } else {
1330            let mut counts = HashMap::new();
1331            for (row, count) in self.row_slices().zip(slice.iter_mut()) {
1332                let curr = counts.entry(ArrayCmpSlice(row)).or_insert(0.0);
1333                *count = *curr;
1334                *curr += 1.0;
1335            }
1336        }
1337        Array::new(shape, data)
1338    }
1339}
1340
1341impl Value {
1342    /// Encode the `bits` of the value
1343    pub fn bits(&self, count: Option<usize>, env: &Uiua) -> UiuaResult<Value> {
1344        match self {
1345            Value::Byte(n) => n.bits(count, env),
1346            Value::Num(n) => n.bits(count, env),
1347            _ => Err(env.error("Argument to bits must be an array of natural numbers")),
1348        }
1349    }
1350    /// Decode the `bits` of the value
1351    pub fn unbits(&self, env: &Uiua) -> UiuaResult<Value> {
1352        match self {
1353            Value::Byte(n) => n.un_bits(env),
1354            Value::Num(n) => n.un_bits(env),
1355            _ => Err(env.error("Argument to un bits must be an array of integers")),
1356        }
1357    }
1358    pub(crate) fn undo_un_bits(&self, orig_shape: &Self, env: &Uiua) -> UiuaResult<Value> {
1359        let min_bits_len = orig_shape
1360            .as_nats(env, "Shape must be an array of natural numbers")?
1361            .pop()
1362            .unwrap_or(0);
1363        match self {
1364            Value::Byte(n) => n.bits_impl(min_bits_len, None, env),
1365            Value::Num(n) => n.bits_impl(min_bits_len, None, env),
1366            _ => Err(env.error("Argument to undo un bits must be an array of integers")),
1367        }
1368    }
1369}
1370
1371impl<T: RealArrayValue> Array<T> {
1372    /// Encode the `bits` of the array
1373    pub fn bits(&self, count: Option<usize>, env: &Uiua) -> UiuaResult<Value> {
1374        self.bits_impl(0, count, env)
1375    }
1376    fn bits_impl(
1377        &self,
1378        min_bits_len: usize,
1379        count: Option<usize>,
1380        env: &Uiua,
1381    ) -> UiuaResult<Value> {
1382        let mut nats = Vec::with_capacity(self.data.len());
1383        let mut negatives = Vec::with_capacity(self.data.len());
1384        let mut any_neg = false;
1385        for &n in &self.data {
1386            if !n.is_int() {
1387                return Err(env.error(format!(
1388                    "Array must be a list of integers, but {} is not an integer",
1389                    n.grid_string(false)
1390                )));
1391            }
1392            let n = n.to_f64();
1393            if n.abs() > u128::MAX as f64 {
1394                return Err(env.error(format!(
1395                    "{} is too large for the {} algorithm",
1396                    n.grid_string(false),
1397                    Primitive::Bits.format()
1398                )));
1399            }
1400            let mut nat = n.abs().round() as u128;
1401            if let Some(count) = count {
1402                nat &= (1 << count) - 1;
1403            }
1404            nats.push(nat);
1405            negatives.push(n < 0.0);
1406            any_neg |= n < 0.0;
1407        }
1408        let bit_count = if let Some(count) = count {
1409            count
1410        } else {
1411            let mut max = if let Some(max) = nats.iter().max() {
1412                *max
1413            } else {
1414                let mut shape = self.shape.clone();
1415                shape.push(0);
1416                return Ok(Array::<u8>::new(shape, CowSlice::new()).into());
1417            };
1418            let mut max_bits = 0;
1419            while max != 0 {
1420                max_bits += 1;
1421                max >>= 1;
1422            }
1423            max_bits.max(min_bits_len)
1424        };
1425        let mut shape = self.shape.clone();
1426        shape.push(bit_count);
1427        let val: Value = if any_neg {
1428            // If any number is negative, make a f64 array
1429            let mut new_data = eco_vec![0.0; self.data.len() * bit_count];
1430            let new_data_slice = new_data.make_mut();
1431            // LSB first
1432            for (i, (n, is_neg)) in nats.into_iter().zip(negatives).enumerate() {
1433                for j in 0..bit_count {
1434                    let index = i * bit_count + j;
1435                    new_data_slice[index] = u8::from(n & (1 << j) != 0) as f64;
1436                    if is_neg {
1437                        new_data_slice[index] = -new_data_slice[index];
1438                    }
1439                }
1440            }
1441            Array::new(shape, new_data).into()
1442        } else {
1443            // If all numbers are natural, make a u8 array
1444            let mut new_data = eco_vec![0; self.data.len() * bit_count];
1445            let new_data_slice = new_data.make_mut();
1446            // LSB first
1447            for (i, n) in nats.into_iter().enumerate() {
1448                for j in 0..bit_count {
1449                    let index = i * bit_count + j;
1450                    new_data_slice[index] = u8::from(n & (1 << j) != 0);
1451                }
1452            }
1453            let mut arr = Array::new(shape, new_data);
1454            arr.meta.flags.set(ArrayFlags::BOOLEAN, true);
1455            arr.into()
1456        };
1457        val.validate();
1458        Ok(val)
1459    }
1460}
1461
1462impl<T> Array<T>
1463where
1464    T: RealArrayValue,
1465    Array<T>: Into<Value>,
1466{
1467    /// Decode the `bits` of the array
1468    pub fn un_bits(&self, env: &Uiua) -> UiuaResult<Value> {
1469        for &n in &self.data {
1470            if !n.is_int() {
1471                return Err(env.error(format!(
1472                    "Array must be a list of integers, but {} is not an integer",
1473                    n.grid_string(false)
1474                )));
1475            }
1476        }
1477        if self.rank() == 0 {
1478            return Ok(self.clone().into());
1479        }
1480        let mut shape = self.shape.clone();
1481        let bits_slice_len = shape.pop().unwrap();
1482        let elems = shape.elements();
1483        if bits_slice_len == 0 {
1484            return Ok(Array::<u8>::new(shape, eco_vec![0; elems]).into());
1485        }
1486        let mut new_data = eco_vec![0.0; elems];
1487        let new_data_slice = new_data.make_mut();
1488        // LSB first
1489        for (i, bits) in self.data.chunks_exact(bits_slice_len).enumerate() {
1490            let mut n = 0.0;
1491            for (j, bit) in bits.iter().enumerate() {
1492                n += bit.to_f64() * 2.0f64.powi(j as i32);
1493            }
1494            new_data_slice[i] = n;
1495        }
1496        Ok(Array::new(shape, new_data).into())
1497    }
1498}
1499
1500impl Value {
1501    /// Get the indices `where` the value is nonzero
1502    pub fn wher(&self, env: &Uiua) -> UiuaResult<Value> {
1503        let counts =
1504            self.as_natural_array(env, "Argument to where must be an array of naturals")?;
1505        let total: usize = counts.data.iter().fold(0, |acc, &b| acc.saturating_add(b));
1506        let mut val: Value = match self.rank() {
1507            0 => {
1508                validate_size::<u8>([total], env)?;
1509                let data = eco_vec![0u8; total];
1510                let mut arr = Array::new([total], data);
1511                arr.meta.mark_sorted_down(true);
1512                arr.into()
1513            }
1514            1 => {
1515                validate_size::<f64>([total], env)?;
1516                let mut data = EcoVec::with_capacity(total);
1517                for (i, &b) in counts.data.iter().enumerate() {
1518                    let i = i as f64;
1519                    for _ in 0..b {
1520                        data.push(i);
1521                    }
1522                }
1523                Array::from(data).into()
1524            }
1525            _ => {
1526                validate_size::<f64>([total, counts.rank()], env)?;
1527                let mut data = EcoVec::with_capacity(total * counts.rank());
1528                for (i, &b) in counts.data.iter().enumerate() {
1529                    for _ in 0..b {
1530                        let mut i = i;
1531                        let start = data.len();
1532                        for &d in counts.shape.iter().rev() {
1533                            data.insert(start, (i % d) as f64);
1534                            i /= d;
1535                        }
1536                    }
1537                }
1538                let shape = Shape::from([total, counts.rank()].as_ref());
1539                Array::new(shape, data).into()
1540            }
1541        };
1542        val.meta.mark_sorted_up(true);
1543        val.validate();
1544        Ok(val)
1545    }
1546    /// Get the `first` index `where` the value is nonzero
1547    pub fn first_where(&self, env: &Uiua) -> UiuaResult<Array<f64>> {
1548        self.first_where_impl(env, identity, identity)
1549    }
1550    /// Get the last index `where` the value is nonzero
1551    pub fn last_where(&self, env: &Uiua) -> UiuaResult<Array<f64>> {
1552        self.first_where_impl(env, Iterator::rev, Iterator::rev)
1553    }
1554    fn first_where_impl<'a, B, N>(
1555        &'a self,
1556        env: &Uiua,
1557        byte_iter: impl Fn(iter::Enumerate<slice::Iter<'a, u8>>) -> B,
1558        num_iter: impl Fn(iter::Enumerate<slice::Iter<'a, f64>>) -> N,
1559    ) -> UiuaResult<Array<f64>>
1560    where
1561        B: Iterator<Item = (usize, &'a u8)>,
1562        N: Iterator<Item = (usize, &'a f64)>,
1563    {
1564        if self.rank() <= 1 {
1565            match self {
1566                Value::Num(nums) => {
1567                    for (i, n) in num_iter(nums.data.iter().enumerate()) {
1568                        if n.fract() != 0.0 || *n < 0.0 {
1569                            return Err(env.error("Argument to where must be an array of naturals"));
1570                        }
1571                        if *n != 0.0 {
1572                            return Ok(Array::scalar(i as f64));
1573                        }
1574                    }
1575                    env.scalar_fill::<f64>()
1576                        .map(|fv| fv.value.into())
1577                        .map_err(|e| env.error(format!("Cannot take first of an empty array{e}")))
1578                }
1579                Value::Byte(bytes) => {
1580                    for (i, n) in byte_iter(bytes.data.iter().enumerate()) {
1581                        if *n != 0 {
1582                            return Ok(Array::scalar(i as f64));
1583                        }
1584                    }
1585                    env.scalar_fill::<f64>()
1586                        .map(|fv| fv.value.into())
1587                        .map_err(|e| env.error(format!("Cannot take first of an empty array{e}")))
1588                }
1589                value => Err(env.error(format!(
1590                    "Argument to where must be an array of naturals, but it is {}",
1591                    value.type_name_plural()
1592                ))),
1593            }
1594        } else {
1595            match self {
1596                Value::Num(nums) => {
1597                    for (i, n) in num_iter(nums.data.iter().enumerate()) {
1598                        if n.fract() != 0.0 || *n < 0.0 {
1599                            return Err(env.error("Argument to where must be an array of naturals"));
1600                        }
1601                        if *n != 0.0 {
1602                            let mut i = i;
1603                            let mut res = Vec::with_capacity(nums.rank());
1604                            for &d in nums.shape.iter().rev() {
1605                                res.insert(0, (i % d) as f64);
1606                                i /= d;
1607                            }
1608                            return Ok(Array::from_iter(res));
1609                        }
1610                    }
1611                    env.scalar_fill::<f64>()
1612                        .map(|fv| fv.value.into())
1613                        .map_err(|e| env.error(format!("Cannot take first of an empty array{e}")))
1614                }
1615                Value::Byte(bytes) => {
1616                    for (i, n) in byte_iter(bytes.data.iter().enumerate()) {
1617                        if *n != 0 {
1618                            let mut i = i;
1619                            let mut res = Vec::with_capacity(bytes.rank());
1620                            for &d in bytes.shape.iter().rev() {
1621                                res.insert(0, (i % d) as f64);
1622                                i /= d;
1623                            }
1624                            return Ok(Array::from_iter(res));
1625                        }
1626                    }
1627                    env.scalar_fill::<f64>()
1628                        .map(|fv| fv.value.into())
1629                        .map_err(|e| env.error(format!("Cannot take first of an empty array{e}")))
1630                }
1631                value => Err(env.error(format!(
1632                    "Argument to where must be an array of naturals, but it is {}",
1633                    value.type_name_plural()
1634                ))),
1635            }
1636        }
1637    }
1638    pub(crate) fn len_where(&self, env: &Uiua) -> UiuaResult<f64> {
1639        match self {
1640            Value::Num(nums) => {
1641                let mut len = 0.0;
1642                let mut ok = true;
1643                for &n in &nums.data {
1644                    if n.fract() != 0.0 || n < 0.0 {
1645                        ok = false;
1646                        break;
1647                    }
1648                    len += n;
1649                }
1650                ok.then_some(len)
1651                    .ok_or_else(|| env.error("Argument to where must be an array of naturals"))
1652            }
1653            Value::Byte(bytes) => {
1654                // `abs` in needed to fix some weird behavior on WASM
1655                Ok(bytes.data.iter().map(|&n| n as f64).sum::<f64>().abs())
1656            }
1657            value => Err(env.error(format!(
1658                "Argument to where must be an array of naturals, but it is {}",
1659                value.type_name_plural()
1660            ))),
1661        }
1662    }
1663    /// `un` `where`
1664    pub fn unwhere(&self, env: &Uiua) -> UiuaResult<Self> {
1665        self.unwhere_impl(&[], env)
1666    }
1667    fn unwhere_impl(&self, min_size: &[usize], env: &Uiua) -> UiuaResult<Self> {
1668        const INDICES_ERROR: &str = "Argument to ° un ⊚ where must be an array of naturals";
1669        Ok(match self.shape.dims() {
1670            [] | [_] => {
1671                let indices = self.as_nats(env, INDICES_ERROR)?;
1672                let is_sorted = indices
1673                    .iter()
1674                    .zip(indices.iter().skip(1))
1675                    .all(|(&a, &b)| a <= b);
1676                let mut size = indices.iter().max().map(|&i| i + 1).unwrap_or(0);
1677                if let Some(&min) = min_size.first() {
1678                    size = size.max(min);
1679                }
1680                validate_size::<f64>([size], env)?;
1681                let mut data = eco_vec![0.0; size];
1682                let data_slice = data.make_mut();
1683                if is_sorted {
1684                    let mut j = 0;
1685                    for i in 0..size {
1686                        while indices.get(j).is_some_and(|&n| n < i) {
1687                            j += 1;
1688                        }
1689                        let mut count: usize = 0;
1690                        while indices.get(j).copied() == Some(i) {
1691                            j += 1;
1692                            count += 1;
1693                        }
1694                        data_slice[i] = count as f64;
1695                    }
1696                } else {
1697                    let mut counts = HashMap::new();
1698                    for &i in &indices {
1699                        *counts.entry(i).or_insert(0) += 1;
1700                    }
1701                    for i in 0..size {
1702                        data_slice[i] = counts.get(&i).copied().unwrap_or(0) as f64;
1703                    }
1704                }
1705                Array::from(data).into()
1706            }
1707            [_, trailing] => {
1708                let indices = self.as_natural_array(env, INDICES_ERROR)?;
1709                let mut counts: HashMap<&[usize], usize> = HashMap::new();
1710                for row in indices.row_slices() {
1711                    *counts.entry(row).or_default() += 1;
1712                }
1713                let mut shape = Shape::with_capacity(*trailing);
1714                for _ in 0..*trailing {
1715                    shape.push(0);
1716                }
1717                for row in counts.keys() {
1718                    for (a, r) in shape.iter_mut().zip(*row) {
1719                        *a = (*a).max(*r + 1);
1720                    }
1721                }
1722                for (s, &m) in shape.iter_mut().zip(min_size) {
1723                    *s = (*s).max(m);
1724                }
1725                if counts.values().all(|&n| n < 256) {
1726                    let data_len = validate_size::<u8>(shape.iter().copied(), env)?;
1727                    let mut data = eco_vec![0u8; data_len];
1728                    let data_slice = data.make_mut();
1729                    for (key, count) in counts {
1730                        let mut i = 0;
1731                        let mut row_len = 1;
1732                        for (d, &n) in shape.iter().zip(key).rev() {
1733                            i += n * row_len;
1734                            row_len *= d;
1735                        }
1736                        data_slice[i] = count as u8;
1737                    }
1738                    Array::new(shape, data).into()
1739                } else {
1740                    let data_len = validate_size::<f64>(shape.iter().copied(), env)?;
1741                    let mut data = eco_vec![0.0; data_len];
1742                    let data_slice = data.make_mut();
1743                    for (key, count) in counts {
1744                        let mut i = 0;
1745                        let mut row_len = 1;
1746                        for (d, &n) in shape.iter().zip(key).rev() {
1747                            i += n * row_len;
1748                            row_len *= d;
1749                        }
1750                        data_slice[i] = count as f64;
1751                    }
1752                    Array::new(shape, data).into()
1753                }
1754            }
1755            shape => return Err(env.error(format!("Cannot unwhere rank-{} array", shape.len()))),
1756        })
1757    }
1758    pub(crate) fn undo_where(&self, shape: &[usize], env: &Uiua) -> UiuaResult<Self> {
1759        self.unwhere_impl(shape, env)
1760    }
1761    pub(crate) fn all_same(&self) -> bool {
1762        if self.row_count() <= 1
1763            || self.rank() == 1 && self.meta.is_sorted_up() && self.meta.is_sorted_down()
1764        {
1765            return true;
1766        }
1767        val_as_arr!(self, |arr| {
1768            if arr.rank() == 1 {
1769                return arr.data.windows(2).all(|win| win[1].array_eq(&win[0]));
1770            }
1771            let row_len = arr.row_len();
1772            arr.data.windows(2 * row_len).all(|win| {
1773                win.iter()
1774                    .zip(win[row_len..].iter())
1775                    .all(|(a, b)| a.array_eq(b))
1776            })
1777        })
1778    }
1779}
1780
1781impl Value {
1782    /// Convert a string value to a list of UTF-8 bytes
1783    pub fn utf8(&self, env: &Uiua) -> UiuaResult<Self> {
1784        let s = self.as_string(env, "Argument to utf₈ must be a string")?;
1785        Ok(Array::<u8>::from_iter(s.into_bytes()).into())
1786    }
1787    /// Convert a string value to a list of UTF-16 code units
1788    pub fn utf16(&self, env: &Uiua) -> UiuaResult<Self> {
1789        let s = self.as_string(env, "Argument to utf₁₆ must be a string")?;
1790        Ok(Array::<f64>::from_iter(s.encode_utf16().map(|u| u as f64)).into())
1791    }
1792    /// Convert a list of UTF-8 bytes to a string value
1793    pub fn unutf8(&self, env: &Uiua) -> UiuaResult<Self> {
1794        let bytes = self.as_bytes(env, "Argument to °utf₈ must be a list of bytes")?;
1795        let s = String::from_utf8(bytes).map_err(|e| env.error(e))?;
1796        Ok(s.into())
1797    }
1798    /// Convert a list of UTF-16 code units to a string value
1799    pub fn unutf16(&self, env: &Uiua) -> UiuaResult<Self> {
1800        let code_units = self.as_u16s(env, "Argument to °utf₁₆ must be a list of code units")?;
1801        let s = String::from_utf16(&code_units).map_err(|e| env.error(e))?;
1802        Ok(s.into())
1803    }
1804    /// Convert a string value to a list of boxed UTF-8 grapheme clusters
1805    pub fn graphemes(&self, env: &Uiua) -> UiuaResult<Self> {
1806        let s = self.as_string(env, "Argument to graphemes must be a string")?;
1807        let mut data = EcoVec::new();
1808        for grapheme in s.graphemes(true) {
1809            data.push(Boxed(grapheme.into()));
1810        }
1811        Ok(Array::from(data).into())
1812    }
1813    /// Convert a list of boxed UTF-8 grapheme clusters to a string value
1814    pub fn ungraphemes(self, env: &Uiua) -> UiuaResult<Self> {
1815        let mut data = EcoVec::new();
1816        for val in self.into_rows().map(Value::unboxed) {
1817            let s = val.as_string(env, "Argument to ungraphemes must be a list of strings")?;
1818            data.extend(s.chars());
1819        }
1820        Ok(Array::from(data).into())
1821    }
1822}
1823
1824impl Value {
1825    pub(crate) fn first_min_index(&self, env: &Uiua) -> UiuaResult<Self> {
1826        val_as_arr!(self, env, Array::first_min_index).map(Into::into)
1827    }
1828    pub(crate) fn first_max_index(&self, env: &Uiua) -> UiuaResult<Self> {
1829        val_as_arr!(self, env, Array::first_max_index).map(Into::into)
1830    }
1831    pub(crate) fn last_min_index(&self, env: &Uiua) -> UiuaResult<Self> {
1832        val_as_arr!(self, env, Array::last_min_index).map(Into::into)
1833    }
1834    pub(crate) fn last_max_index(&self, env: &Uiua) -> UiuaResult<Self> {
1835        val_as_arr!(self, env, Array::last_max_index).map(Into::into)
1836    }
1837}
1838
1839impl<T: ArrayValue> Array<T> {
1840    pub(crate) fn first_min_index(&self, env: &Uiua) -> UiuaResult<f64> {
1841        if self.rank() == 0 || self.meta.is_sorted_up() {
1842            return Ok(0.0);
1843        }
1844        if self.row_count() == 0 {
1845            return env
1846                .scalar_fill::<f64>()
1847                .map(|fv| fv.value)
1848                .map_err(|e| env.error(format!("Cannot get min index of an empty array{e}")));
1849        }
1850        let index = self
1851            .row_slices()
1852            .map(ArrayCmpSlice)
1853            .enumerate()
1854            .min_by(|(_, a), (_, b)| a.cmp(b))
1855            .unwrap()
1856            .0;
1857        Ok(index as f64)
1858    }
1859    pub(crate) fn first_max_index(&self, env: &Uiua) -> UiuaResult<f64> {
1860        if self.rank() == 0 {
1861            return Ok(0.0);
1862        }
1863        if self.row_count() == 0 {
1864            return env
1865                .scalar_fill::<f64>()
1866                .map(|fv| fv.value)
1867                .map_err(|e| env.error(format!("Cannot get max index of an empty array{e}")));
1868        }
1869        let index = self
1870            .row_slices()
1871            .map(ArrayCmpSlice)
1872            .enumerate()
1873            .min_by(|(_, a), (_, b)| a.cmp(b).reverse())
1874            .unwrap()
1875            .0;
1876        Ok(index as f64)
1877    }
1878    pub(crate) fn last_min_index(&self, env: &Uiua) -> UiuaResult<f64> {
1879        if self.rank() == 0 {
1880            return Ok(0.0);
1881        }
1882        if self.row_count() == 0 {
1883            return env
1884                .scalar_fill::<f64>()
1885                .map(|fv| fv.value)
1886                .map_err(|e| env.error(format!("Cannot get min index of an empty array{e}")));
1887        }
1888        let index = self
1889            .row_slices()
1890            .map(ArrayCmpSlice)
1891            .enumerate()
1892            .max_by(|(_, a), (_, b)| a.cmp(b).reverse())
1893            .unwrap()
1894            .0;
1895        Ok(index as f64)
1896    }
1897    pub(crate) fn last_max_index(&self, env: &Uiua) -> UiuaResult<f64> {
1898        if self.rank() == 0 || self.meta.is_sorted_up() {
1899            return Ok(0.0);
1900        }
1901        if self.row_count() == 0 {
1902            return env
1903                .scalar_fill::<f64>()
1904                .map(|fv| fv.value)
1905                .map_err(|e| env.error(format!("Cannot get max index of an empty array{e}")));
1906        }
1907        let index = self
1908            .row_slices()
1909            .map(ArrayCmpSlice)
1910            .enumerate()
1911            .max_by(|(_, a), (_, b)| a.cmp(b))
1912            .unwrap()
1913            .0;
1914        Ok(index as f64)
1915    }
1916}
1917
1918impl Value {
1919    pub(crate) fn primes(&self, env: &Uiua) -> UiuaResult<Array<f64>> {
1920        match self {
1921            Value::Num(n) => n.primes(env),
1922            Value::Byte(b) => b.convert_ref::<f64>().primes(env),
1923            value => Err(env.error(format!("Cannot get primes of {} array", value.type_name()))),
1924        }
1925    }
1926}
1927
1928impl Array<f64> {
1929    pub(crate) fn primes(&self, env: &Uiua) -> UiuaResult<Array<f64>> {
1930        let mut max = 0;
1931        // Validate nums and calc max
1932        for &n in &self.data {
1933            if n <= 0.0 {
1934                return Err(env.error(format!(
1935                    "Cannot get primes of non-positive number {}",
1936                    n.grid_string(true)
1937                )));
1938            }
1939            if n.fract() != 0.0 {
1940                return Err(env.error(format!(
1941                    "Cannot get primes of non-integer number {}",
1942                    n.grid_string(true)
1943                )));
1944            }
1945            if n > usize::MAX as f64 {
1946                return Err(env.error(format!(
1947                    "Cannot get primes of {} because it is too large",
1948                    n.grid_string(true)
1949                )));
1950            }
1951            max = max.max(n as usize);
1952        }
1953
1954        if self.shape.elements() == 1 {
1955            let mut n = self.data[0] as usize;
1956            let mut primes = EcoVec::new();
1957            for d in 2..=self.data[0].sqrt().ceil() as usize {
1958                while n % d == 0 {
1959                    primes.push(d as f64);
1960                    n /= d;
1961                }
1962            }
1963            if n > 1 {
1964                primes.push(n as f64);
1965            }
1966            let mut shape = self.shape.clone();
1967            shape.prepend(primes.len());
1968            return Ok(Array::new(shape, primes));
1969        }
1970
1971        validate_size::<usize>([max, 2], env)?;
1972
1973        // Sieve of Eratosthenes
1974        let mut spf = vec![1; max + 1];
1975        for i in 2..=max {
1976            spf[i] = i;
1977        }
1978        for i in 2..=max {
1979            if spf[i] == i {
1980                let (ii, overflow) = i.overflowing_mul(i);
1981                if !overflow && ii <= max {
1982                    for j in (ii..=max).step_by(i) {
1983                        if spf[j] == j {
1984                            spf[j] = i;
1985                        }
1986                    }
1987                }
1988            }
1989        }
1990
1991        // Factorize
1992        let mut lengths: Vec<usize> = Vec::with_capacity(self.data.len());
1993        let mut factors: Vec<usize> = Vec::with_capacity(self.data.len());
1994        for &n in &self.data {
1995            let mut m = n as usize;
1996            if m == 1 {
1997                lengths.push(0);
1998                continue;
1999            }
2000            let mut len = 0;
2001            while m != 1 {
2002                factors.push(spf[m]);
2003                m /= spf[m];
2004                len += 1;
2005            }
2006            lengths.push(len);
2007        }
2008
2009        // Pad and create array
2010        let longest = lengths.iter().max().copied().unwrap_or(0);
2011        let mut data = eco_vec![1.0; self.data.len() * longest];
2012        let data_slice = data.make_mut();
2013        let mut k = 0;
2014        for (i, len) in lengths.into_iter().enumerate() {
2015            for j in (longest - len)..longest {
2016                data_slice[j * self.data.len() + i] = factors[k] as f64;
2017                k += 1;
2018            }
2019        }
2020        let mut shape = self.shape.clone();
2021        shape.prepend(longest);
2022        Ok(Array::new(shape, data))
2023    }
2024}
2025
2026impl Value {
2027    /// Convert a value from RGB to HSV
2028    pub fn rgb_to_hsv(self, env: &Uiua) -> UiuaResult<Self> {
2029        match self {
2030            Value::Num(arr) => arr.rgb_to_hsv(env).map(Into::into),
2031            Value::Byte(arr) => arr.convert_ref::<f64>().rgb_to_hsv(env).map(Into::into),
2032            val => Err(env.error(format!("Cannot convert {} to HSV", val.type_name_plural()))),
2033        }
2034    }
2035    /// Convert a value from HSV to RGB
2036    pub fn hsv_to_rgb(self, env: &Uiua) -> UiuaResult<Self> {
2037        match self {
2038            Value::Num(arr) => arr.hsv_to_rgb(env).map(Into::into),
2039            Value::Byte(arr) => arr.convert_ref::<f64>().hsv_to_rgb(env).map(Into::into),
2040            val => Err(env.error(format!("Cannot convert {} to RGB", val.type_name_plural()))),
2041        }
2042    }
2043}
2044
2045impl Array<f64> {
2046    /// Convert an array from RGB to HSV
2047    pub fn rgb_to_hsv(mut self, env: &Uiua) -> UiuaResult<Self> {
2048        if !(self.shape.ends_with(&[3]) || self.shape.ends_with(&[4])) {
2049            return Err(env.error(format!(
2050                "Array to convert to HSV must have a shape \
2051                ending with 3 or 4, but its shape is {}",
2052                self.shape
2053            )));
2054        }
2055        let channels = *self.shape.last().unwrap();
2056        for rgb in self.data.as_mut_slice().chunks_exact_mut(channels) {
2057            let [r, g, b, ..] = *rgb else {
2058                unreachable!();
2059            };
2060            let max = r.max(g).max(b);
2061            let min = r.min(g).min(b);
2062            let delta = max - min;
2063            let recip_delta = if delta != 0.0 { 1.0 / delta } else { 0.0 };
2064            let h = if delta != 0.0 {
2065                (TAU * if max == r {
2066                    ((g - b) * recip_delta).rem_euclid(6.0)
2067                } else if max == g {
2068                    (b - r).mul_add(recip_delta, 2.0)
2069                } else {
2070                    (r - g).mul_add(recip_delta, 4.0)
2071                }) / 6.0
2072            } else {
2073                0.0
2074            };
2075            let s = if max == 0.0 { 0.0 } else { 1.0 - min / max };
2076            let v = max;
2077            rgb[0] = h;
2078            rgb[1] = s;
2079            rgb[2] = v;
2080        }
2081        self.meta.take_sorted_flags();
2082        self.validate();
2083        Ok(self)
2084    }
2085    /// Convert an array from HSV to RGB
2086    pub fn hsv_to_rgb(mut self, env: &Uiua) -> UiuaResult<Self> {
2087        if !(self.shape.ends_with(&[3]) || self.shape.ends_with(&[4])) {
2088            return Err(env.error(format!(
2089                "Array to convert to RBG must have a shape \
2090                ending with 3 or 4, but its shape is {}",
2091                self.shape
2092            )));
2093        }
2094        let channels = *self.shape.last().unwrap();
2095        for hsv in self.data.as_mut_slice().chunks_exact_mut(channels) {
2096            let [h, s, v, ..] = *hsv else {
2097                unreachable!();
2098            };
2099            let [r, g, b] = hsv_to_rgb(h, s, v);
2100            hsv[0] = r;
2101            hsv[1] = g;
2102            hsv[2] = b;
2103        }
2104        self.meta.take_sorted_flags();
2105        self.validate();
2106        Ok(self)
2107    }
2108}
2109
2110pub(crate) fn hsv_to_rgb(h: f64, s: f64, v: f64) -> [f64; 3] {
2111    let h = h / TAU * 6.0;
2112    let i = h.floor() as isize;
2113    let f = h - i as f64;
2114    let p = v * (1.0 - s);
2115    let q = v * (1.0 - f * s);
2116    let t = v * (1.0 - (1.0 - f) * s);
2117    match i.rem_euclid(6) {
2118        0 => [v, t, p],
2119        1 => [q, v, p],
2120        2 => [p, v, t],
2121        3 => [p, q, v],
2122        4 => [t, p, v],
2123        _ => [v, p, q],
2124    }
2125}
2126
2127fn f64_repr(n: f64) -> String {
2128    let abs = n.abs();
2129    let pos = if abs == PI / 2.0 {
2130        "η".into()
2131    } else if abs == PI {
2132        "π".into()
2133    } else if abs == TAU {
2134        "τ".into()
2135    } else if abs.is_infinite() {
2136        "∞".into()
2137    } else {
2138        abs.to_string()
2139    };
2140    if n < 0.0 {
2141        format!("¯{}", pos)
2142    } else {
2143        pos
2144    }
2145}
2146
2147impl Value {
2148    /// Get the `repr` of a value
2149    pub fn representation(&self) -> String {
2150        const MAX_SINGLE_LINE_LEN: usize = 40;
2151        let mut s = match self.rank() {
2152            0 => match self {
2153                Value::Num(arr) => {
2154                    let n = arr.data[0];
2155                    let bool_lit = arr.meta.flags.contains(ArrayFlags::BOOLEAN_LITERAL);
2156                    if n == 0.0 && bool_lit {
2157                        "False".into()
2158                    } else if n == 1.0 && bool_lit {
2159                        "True".into()
2160                    } else {
2161                        f64_repr(n)
2162                    }
2163                }
2164                Value::Byte(arr) => {
2165                    let b = arr.data[0];
2166                    let bool_lit = arr.meta.flags.contains(ArrayFlags::BOOLEAN_LITERAL);
2167                    if b == 0 && bool_lit {
2168                        "False".into()
2169                    } else if b == 1 && bool_lit {
2170                        "True".into()
2171                    } else {
2172                        b.to_string()
2173                    }
2174                }
2175                Value::Complex(arr) => {
2176                    let c = arr.data[0];
2177                    if c == Complex::I {
2178                        "i".into()
2179                    } else if c == -Complex::I {
2180                        "¯i".into()
2181                    } else {
2182                        format!("ℂ{} {}", f64_repr(c.im), f64_repr(c.re))
2183                    }
2184                }
2185                Value::Char(arr) => {
2186                    let c = arr.data[0];
2187                    match c {
2188                        ' ' => "@\\s".into(),
2189                        c => c.grid_string(false),
2190                    }
2191                }
2192                Value::Box(arr) => format!("□{}", arr.data[0].0.representation()),
2193            },
2194            1 => match self {
2195                Value::Char(arr) => format!("{:?}", arr.data.iter().collect::<String>()),
2196                Value::Box(arr) => {
2197                    let mut s = '{'.to_string();
2198                    for (i, v) in arr.data.iter().enumerate() {
2199                        if i > 0 {
2200                            s.push(' ');
2201                        }
2202                        s.push_str(&v.0.representation());
2203                    }
2204                    s.push('}');
2205                    s
2206                }
2207                value => {
2208                    let mut s = '['.to_string();
2209                    for (i, v) in value.rows().enumerate() {
2210                        if i > 0 {
2211                            s.push(' ');
2212                        }
2213                        s.push_str(&v.representation());
2214                    }
2215                    s.push(']');
2216                    s
2217                }
2218            },
2219            _ => {
2220                let mut s = '['.to_string();
2221                let rows: Vec<String> = self.rows().map(|v| v.representation()).collect();
2222                let max_row_len = rows.iter().map(String::len).max().unwrap_or(0);
2223                for (i, row) in rows.iter().enumerate() {
2224                    if i > 0 {
2225                        if max_row_len > MAX_SINGLE_LINE_LEN {
2226                            s.push_str("\n  ");
2227                        } else {
2228                            s.push(' ');
2229                        }
2230                    }
2231                    s.push_str(row);
2232                }
2233                s.push(']');
2234                s
2235            }
2236        };
2237        if let Some(map_keys) = &self.meta.map_keys {
2238            s = format!(
2239                "map {} {}",
2240                map_keys.clone().normalized().representation(),
2241                s
2242            );
2243        }
2244        if let Some(label) = &self.meta.label {
2245            s = format!("${label} {s}");
2246        }
2247        s
2248    }
2249    /// Get the `datetime` of a value
2250    pub fn datetime(&self, env: &Uiua) -> UiuaResult<Array<f64>> {
2251        let mut arr = match self {
2252            Value::Num(arr) => arr.clone(),
2253            Value::Byte(arr) => arr.convert_ref(),
2254            value => return Err(env.error(format!("Cannot get datetime of {}", value.type_name()))),
2255        };
2256        let size = validate_size::<f64>(arr.shape.iter().copied().chain([6]), env)?;
2257        let mut new_data = eco_vec![0.0; size];
2258        let slice = new_data.make_mut();
2259        for (i, &n) in arr.data.iter().enumerate() {
2260            let dur = time::Duration::checked_seconds_f64(n).ok_or_else(|| {
2261                env.error(format!("{} is not a valid time", n.grid_string(false)))
2262            })?;
2263            let dt = if n >= 0.0 {
2264                OffsetDateTime::UNIX_EPOCH.checked_add(dur)
2265            } else {
2266                OffsetDateTime::UNIX_EPOCH.checked_sub(dur)
2267            }
2268            .ok_or_else(|| env.error(format!("{} is not a valid time", n.grid_string(false))))?;
2269            slice[i * 6] = dt.year() as f64;
2270            slice[i * 6 + 1] = dt.month() as u8 as f64;
2271            slice[i * 6 + 2] = dt.day() as f64;
2272            slice[i * 6 + 3] = dt.hour() as f64;
2273            slice[i * 6 + 4] = dt.minute() as f64;
2274            slice[i * 6 + 5] = dt.second() as f64;
2275        }
2276        arr.data = new_data.into();
2277        arr.shape.push(6);
2278        arr.meta.reset_flags();
2279        arr.validate();
2280        Ok(arr)
2281    }
2282    pub(crate) fn undatetime(&self, env: &Uiua) -> UiuaResult<Array<f64>> {
2283        let mut arr = match self {
2284            Value::Num(arr) => arr.clone(),
2285            Value::Byte(arr) => arr.convert_ref(),
2286            value => {
2287                return Err(env.error(format!("Cannot decode datetime from {}", value.type_name())))
2288            }
2289        };
2290        let convert = |chunk: &[f64]| -> UiuaResult<f64> {
2291            let mut year = chunk.first().copied().unwrap_or(0.0);
2292            let mut month = chunk.get(1).copied().unwrap_or(1.0) - 1.0;
2293            let mut day = chunk.get(2).copied().unwrap_or(1.0) - 1.0;
2294            let mut hour = chunk.get(3).copied().unwrap_or(0.0);
2295            let mut minute = chunk.get(4).copied().unwrap_or(0.0);
2296            let mut second = chunk.get(5).copied().unwrap_or(0.0);
2297            let mut frac = chunk.get(6).copied().unwrap_or(0.0);
2298            frac += second.fract();
2299            second = second.floor();
2300            second += minute.fract() * 60.0;
2301            minute = minute.floor();
2302            minute += hour.fract() * 60.0;
2303            hour = hour.floor();
2304            hour += day.fract() * 24.0;
2305            day = day.floor();
2306            day += month.fract() * 30.0;
2307            month = month.floor();
2308            month += year.fract() * 12.0;
2309            year = year.floor();
2310            if frac >= 1.0 {
2311                second += frac.floor();
2312                frac = 1.0 - frac.fract();
2313            } else if frac < 0.0 {
2314                second += frac;
2315                frac = -frac.fract();
2316            }
2317            if second >= 60.0 {
2318                minute += (second / 60.0).floor();
2319                second %= 60.0;
2320            } else if second < 0.0 {
2321                minute += second / 60.0;
2322                second = 60.0 + (second % 60.0);
2323            }
2324            if minute >= 60.0 {
2325                hour += (minute / 60.0).floor();
2326                minute %= 60.0;
2327            } else if minute < 0.0 {
2328                hour += minute / 60.0;
2329                minute = 60.0 + (minute % 60.0);
2330            }
2331            if hour >= 24.0 {
2332                day += (hour / 24.0).floor();
2333                hour %= 24.0;
2334            } else if hour < 0.0 {
2335                day += hour / 24.0;
2336                hour = 24.0 + (hour % 24.0);
2337            }
2338            let day_delta = if day >= 28.0 {
2339                let delta = day - 27.0;
2340                day -= delta;
2341                delta
2342            } else if day < 0.0 {
2343                let delta = day;
2344                day = 0.0;
2345                delta
2346            } else {
2347                day.fract()
2348            };
2349            if month >= 12.0 {
2350                year += (month / 12.0).floor();
2351                month %= 12.0;
2352            } else if month < 0.0 {
2353                year += month / 12.0;
2354                month = 12.0 + (month % 12.0);
2355            }
2356            let year = year as i32;
2357            let month = month as u8 + 1;
2358            let day = day as u8 + 1;
2359            let hour = hour as u8;
2360            let minute = minute as u8;
2361            let second = second as u8;
2362            let mut dt = OffsetDateTime::new_utc(
2363                Date::from_calendar_date(year, Month::January.nth_next(month - 1), day).map_err(
2364                    |e| env.error(format!("Invalid date {year:04}-{month:02}-{day:02}: {e}")),
2365                )?,
2366                Time::from_hms(hour, minute, second).map_err(|e| {
2367                    env.error(format!(
2368                        "Invalid time {hour:02}:{minute:02}:{second:02}: {e}"
2369                    ))
2370                })?,
2371            );
2372            if day_delta > 0.0 {
2373                dt += Duration::from_secs_f64(day_delta * 86400.0);
2374            } else if day_delta < 0.0 {
2375                dt -= Duration::from_secs_f64(day_delta.abs() * 86400.0);
2376            }
2377            Ok(dt.unix_timestamp() as f64 + frac)
2378        };
2379        let [shape_pre @ .., n] = &*arr.shape else {
2380            return Err(env.error("Cannot decode datetime from scalar"));
2381        };
2382        arr.data = if *n == 0 {
2383            let size = validate_size::<f64>(shape_pre.iter().copied(), env)?;
2384            eco_vec![0.0; size].into()
2385        } else {
2386            let mut new_data = eco_vec![0.0; arr.data.len() / *n];
2387            let slice = new_data.make_mut();
2388            if *n > 0 {
2389                for (i, chunk) in arr.data.chunks_exact(*n).enumerate() {
2390                    slice[i] = convert(chunk)?;
2391                }
2392            }
2393            new_data.into()
2394        };
2395        arr.shape.pop();
2396        arr.validate();
2397        Ok(arr)
2398    }
2399}