1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
//! Utilities.
use std::cmp::Ordering;
use std::ops::Range;
/// Additional methods for slices.
pub trait SliceExt<T> {
/// Split a slice into consecutive groups with the same key.
///
/// Returns an iterator of pairs of a key and the group with that key.
fn group_by_key<K, F>(&self, f: F) -> GroupByKey<'_, T, F>
where
F: FnMut(&T) -> K,
K: PartialEq;
}
impl<T> SliceExt<T> for [T] {
fn group_by_key<K, F>(&self, f: F) -> GroupByKey<'_, T, F>
where
F: FnMut(&T) -> K,
K: PartialEq,
{
GroupByKey { slice: self, f }
}
}
/// This struct is produced by [`SliceExt::group_by_key`].
pub struct GroupByKey<'a, T, F> {
slice: &'a [T],
f: F,
}
impl<'a, T, K, F> Iterator for GroupByKey<'a, T, F>
where
F: FnMut(&T) -> K,
K: PartialEq,
{
type Item = (K, &'a [T]);
fn next(&mut self) -> Option<Self::Item> {
let first = self.slice.first()?;
let key = (self.f)(first);
let mut i = 1;
while self.slice.get(i).map_or(false, |t| (self.f)(t) == key) {
i += 1;
}
let (head, tail) = self.slice.split_at(i);
self.slice = tail;
Some((key, head))
}
}
/// Additional methods for [`Range<usize>`].
pub trait RangeExt {
/// Locate a position relative to a range.
///
/// This can be used for binary searching the range that contains the
/// position as follows:
/// ```
/// # use typst::util::RangeExt;
/// assert_eq!(
/// [1..2, 2..7, 7..10].binary_search_by(|r| r.locate(5)),
/// Ok(1),
/// );
/// ```
fn locate(&self, pos: usize) -> Ordering;
}
impl RangeExt for Range<usize> {
fn locate(&self, pos: usize) -> Ordering {
if pos < self.start {
Ordering::Greater
} else if pos < self.end {
Ordering::Equal
} else {
Ordering::Less
}
}
}
|
