diff options
| -rw-r--r-- | crates/typst/src/eval/array.rs | 32 | ||||
| -rw-r--r-- | crates/typst/src/eval/methods.rs | 1 | ||||
| -rw-r--r-- | docs/reference/types.md | 15 | ||||
| -rw-r--r-- | tests/typ/compiler/array.typ | 15 |
4 files changed, 63 insertions, 0 deletions
diff --git a/crates/typst/src/eval/array.rs b/crates/typst/src/eval/array.rs index a7a1387b..5d5fdcdb 100644 --- a/crates/typst/src/eval/array.rs +++ b/crates/typst/src/eval/array.rs @@ -398,6 +398,38 @@ impl Array { .map(|(i, value)| array![i, value.clone()].into_value()) .collect() } + + /// Deduplicates all items in the array. + pub fn dedup(&self, vm: &mut Vm, key: Option<Func>) -> SourceResult<Self> { + let mut out = EcoVec::with_capacity(self.0.len()); + let mut key_of = |x: Value| match &key { + // NOTE: We are relying on `comemo`'s memoization of function + // evaluation to not excessively reevaluate the `key`. + Some(f) => f.call_vm(vm, Args::new(f.span(), [x])), + None => Ok(x), + }; + + // This algorithm is O(N^2) because we cannot rely on `HashSet` since: + // 1. We would like to preserve the order of the elements. + // 2. We cannot hash arbitrary `Value`. + 'outer: for value in self.iter() { + let key = key_of(value.clone())?; + if out.is_empty() { + out.push(value.clone()); + continue; + } + + for second in out.iter() { + if typst::eval::ops::equal(&key, &key_of(second.clone())?) { + continue 'outer; + } + } + + out.push(value.clone()); + } + + Ok(Self(out)) + } } impl Debug for Array { diff --git a/crates/typst/src/eval/methods.rs b/crates/typst/src/eval/methods.rs index a7368426..bf47b7aa 100644 --- a/crates/typst/src/eval/methods.rs +++ b/crates/typst/src/eval/methods.rs @@ -147,6 +147,7 @@ pub fn call( "sorted" => array.sorted(vm, span, args.named("key")?)?.into_value(), "zip" => array.zip(args.expect("other")?).into_value(), "enumerate" => array.enumerate().into_value(), + "dedup" => array.dedup(vm, args.named("key")?)?.into_value(), _ => return missing(), }, diff --git a/docs/reference/types.md b/docs/reference/types.md index 28646cd2..d602bc3e 100644 --- a/docs/reference/types.md +++ b/docs/reference/types.md @@ -966,6 +966,21 @@ Return a new array with the same items, but sorted. If given, applies this function to the elements in the array to determine the keys to sort by. - returns: array +### dedup() +Returns a new array with all duplicate items removed. + +Only the first element of each duplicate is kept. + +```example +#{ + (1, 1, 2, 3, 1).dedup() == (1, 2, 3) +} +``` + +- key: function (named) + If given, applies this function to the elements in the array to determine the keys to deduplicate by. +- returns: array + # Dictionary A map from string keys to values. diff --git a/tests/typ/compiler/array.typ b/tests/typ/compiler/array.typ index a96a800f..4bc027ef 100644 --- a/tests/typ/compiler/array.typ +++ b/tests/typ/compiler/array.typ @@ -238,6 +238,21 @@ #test(((1, 2), 3).zip((4, 5)), (((1, 2), 4), (3, 5))) #test((1, "hi").zip((true, false)), ((1, true), ("hi", false))) +--- +// Test the `dedup` method. +#test(().dedup(), ()) +#test((1,).dedup(), (1,)) +#test((1, 1).dedup(), (1,)) +#test((1, 2, 1).dedup(), (1, 2)) +#test(("Jane", "John", "Eric").dedup(), ("Jane", "John", "Eric")) +#test(("Jane", "John", "Eric", "John").dedup(), ("Jane", "John", "Eric")) + +--- +// Test the `dedup` with the `key` argument. +#test((1, 2, 3, 4, 5, 6).dedup(key: x => calc.rem(x, 2)), (1, 2)) +#test((1, 2, 3, 4, 5, 6).dedup(key: x => calc.rem(x, 3)), (1, 2, 3)) +#test(("Hello", "World", "Hi", "There").dedup(key: x => x.len()), ("Hello", "Hi")) +#test(("Hello", "World", "Hi", "There").dedup(key: x => x.at(0)), ("Hello", "World", "There")) --- // Error: 32-37 cannot divide by zero |