orx_funvec/funvec_ref.rs
1use crate::{index::IntoIndex, iter_over_ref::IterOverRefs};
2
3/// Trait to provide abstraction over `DIM`-dimensional vectors allowing reference access using indices.
4///
5/// Such an abstraction is particularly important in performance-critical algorithms both requiring flexibility through abstraction
6/// over inputs and performance through monomorphization.
7///
8/// This trait for a given or generic `DIM` can be extended by implementing `fn ref_at<Idx: IntoIndex<DIM>>(&self, index: Idx) -> Option<&T>`.
9///
10/// # Examples - Dimension 1
11///
12/// ```rust
13/// use orx_funvec::*;
14///
15/// fn moving_average<V: FunVecRef<1, i32>>(observations: &V, period: usize) -> Option<i32> {
16/// let last = if period == 0 { None } else { observations.ref_at(period - 1) };
17/// let current = observations.ref_at(period);
18///
19/// match (last, current) {
20/// (None, None) => None,
21/// (None, Some(y)) => Some(*y),
22/// (Some(x), None) => Some(*x),
23/// (Some(x), Some(y)) => Some((x + y) / 2)
24/// }
25/// }
26///
27/// let period = 2;
28///
29/// let stdvec = vec![10, 11, 12, 13];
30/// assert_eq!(Some(11), moving_average(&stdvec, period));
31///
32/// let map = std::collections::HashMap::from_iter([(1, 10), (2, 20), (3, 30)].into_iter());
33/// assert_eq!(Some(15), moving_average(&map, period));
34///
35/// let closure = orx_closure::Capture(())
36/// .fun_option_ref(|_, i: usize| Some(if i == 2 { &20 } else { &30 }));
37/// assert_eq!(Some(25), moving_average(&closure, period));
38///
39/// let uniform = ScalarAsVec(42);
40/// assert_eq!(Some(42), moving_average(&uniform, period));
41///
42/// let no_data = EmptyVec::new();
43/// assert_eq!(None, moving_average(&no_data, period));
44/// ```
45///
46/// # Examples - Dimension 2
47///
48/// ```rust
49/// use orx_funvec::*;
50/// use orx_closure::Capture;
51/// use std::collections::{BTreeMap, HashMap};
52///
53/// fn distance_between<V: FunVecRef<2, u32>>(distances: &V, a: usize, b: usize) -> Option<&u32> {
54/// distances.ref_at((a, b))
55/// }
56///
57/// // complete matrix
58/// let jagged_vecs = vec![
59/// vec![0, 1, 2, 3],
60/// vec![10, 11, 12, 13],
61/// vec![20, 21, 22, 23],
62/// vec![30, 31, 32, 33],
63/// ];
64/// assert_eq!(Some(&23), distance_between(&jagged_vecs, 2, 3));
65/// assert_eq!(None, distance_between(&jagged_vecs, 2, 4));
66/// assert_eq!(None, distance_between(&jagged_vecs, 4, 0));
67///
68/// // some sparsity in the first or second dimensions
69/// let vec_of_maps = vec![
70/// BTreeMap::from_iter([(1, 1), (14, 2)].into_iter()),
71/// BTreeMap::from_iter([(0, 10), (7, 20)].into_iter()),
72/// BTreeMap::from_iter([(9, 100), (16, 200)].into_iter()),
73/// ];
74/// assert_eq!(Some(&20), distance_between(&vec_of_maps, 1, 7));
75/// assert_eq!(None, distance_between(&vec_of_maps, 0, 0));
76/// assert_eq!(None, distance_between(&vec_of_maps, 3, 0));
77///
78/// let map_of_vecs = HashMap::from_iter([
79/// (1, vec![3, 4, 5]),
80/// (7, vec![30, 40, 50]),
81/// ].into_iter());
82/// assert_eq!(Some(&5), distance_between(&map_of_vecs, 1, 2));
83/// assert_eq!(Some(&40), distance_between(&map_of_vecs, 7, 1));
84/// assert_eq!(None, distance_between(&map_of_vecs, 0, 0));
85///
86/// // complete sparsity
87/// let map_of_indices = HashMap::from_iter([
88/// ((0, 1), 14),
89/// ((3, 6), 42),
90/// ].into_iter());
91/// assert_eq!(Some(&14), distance_between(&map_of_indices, 0, 1));
92/// assert_eq!(Some(&42), distance_between(&map_of_indices, 3, 6));
93/// assert_eq!(None, distance_between(&map_of_indices, 0, 0));
94///
95/// // uniform distance for all pairs
96/// let uniform = ScalarAsVec(42);
97/// assert_eq!(Some(&42), distance_between(&uniform, 7, 42));
98///
99/// // all disconnected pairs
100/// let disconnected = EmptyVec::new();
101/// assert_eq!(None, distance_between(&disconnected, 7, 42));
102/// ```
103pub trait FunVecRef<const DIM: usize, T>
104where
105 T: ?Sized,
106{
107 /// Returns a reference to the element at the given `index` or `None` if the position is empty.
108 ///
109 /// This allows to access elements of all funvec implementations in a unified way. Thanks to monomorphization, this abstraction does not have a performance penalty.
110 ///
111 /// Note that funvec's are different than, generalization of, traditional vectors since the elements are not necessarily contagious or dense.
112 /// Instead they can be sparse to desired degrees.
113 ///
114 /// Therefore, `ref_at` always returns an optional.
115 ///
116 /// # Examples - Dimension 1
117 ///
118 /// ```rust
119 /// use orx_funvec::*;
120 /// use orx_closure::Capture;
121 /// use std::collections::{HashSet, HashMap};
122 ///
123 /// struct Student {
124 /// name: String,
125 /// age: u32,
126 /// }
127 /// impl Student {
128 /// fn new(name: &str, age: u32) -> Self {
129 /// Self { name: name.to_string(), age }
130 /// }
131 /// }
132 ///
133 /// fn average_student_age<S: FunVecRef<1, Student>>(students: &S, ids: &HashSet<usize>) -> u32 {
134 /// let mut sum_age = 0;
135 /// let mut num_students = 0;
136 /// for id in ids {
137 /// if let Some(student) = students.ref_at(*id) {
138 /// sum_age += student.age;
139 /// num_students += 1;
140 /// }
141 /// }
142 /// if num_students == 0 {
143 /// 0
144 /// } else {
145 /// sum_age / num_students
146 /// }
147 /// }
148 ///
149 /// let ids = HashSet::from_iter([0, 2, 3].into_iter());
150 ///
151 /// let stdvec = vec![Student::new("foo", 18), Student::new("bar", 22), Student::new("baz", 16)];
152 /// assert_eq!(17, average_student_age(&stdvec, &ids));
153 ///
154 /// let map = HashMap::from_iter([
155 /// (0, Student::new("foo", 18)),
156 /// (3, Student::new("bar", 20)),
157 /// (10, Student::new("baz", 30)),
158 /// ].into_iter());
159 /// assert_eq!(19, average_student_age(&map, &ids));
160 ///
161 /// let regular = vec![Student::new("foo", 18), Student::new("bar", 22), Student::new("baz", 16)];
162 /// let exchange: HashMap<usize, Student> = HashMap::from_iter([
163 /// (3, Student::new("john", 20)),
164 /// (42, Student::new("doe", 17)),
165 /// ].into_iter());
166 /// let closure = Capture((regular, exchange)).fun_option_ref(|(r, x), i: usize| {
167 /// r.get(i).or(x.get(&i))
168 /// });
169 /// assert_eq!(18, average_student_age(&closure, &ids));
170 ///
171 /// let only_foo = ScalarAsVec(Student::new("foo", 42));
172 /// assert_eq!(42, average_student_age(&only_foo, &ids));
173 ///
174 /// let no_students = EmptyVec::new();
175 /// assert_eq!(0, average_student_age(&no_students, &ids));
176 /// ```
177 ///
178 /// # Examples - Dimension 2
179 ///
180 /// ```rust
181 /// use orx_funvec::*;
182 /// use orx_closure::Capture;
183 /// use std::collections::{BTreeMap, HashMap};
184 ///
185 /// fn distance<V: FunVecRef<2, u32>>(distances: &V, a: usize, b: usize) -> Option<&u32> {
186 /// distances.ref_at([a, b])
187 /// }
188 ///
189 /// // complete matrix
190 /// let jagged_vecs = vec![
191 /// vec![0, 1, 2, 3],
192 /// vec![10, 11, 12, 13],
193 /// vec![20, 21, 22, 23],
194 /// vec![30, 31, 32, 33],
195 /// ];
196 /// assert_eq!(Some(&23), distance(&jagged_vecs, 2, 3));
197 /// assert_eq!(None, distance(&jagged_vecs, 2, 4));
198 /// assert_eq!(None, distance(&jagged_vecs, 4, 0));
199 ///
200 /// // some sparsity in the first or second dimensions
201 /// let vec_of_maps = vec![
202 /// BTreeMap::from_iter([(1, 1), (14, 2)].into_iter()),
203 /// BTreeMap::from_iter([(0, 10), (7, 20)].into_iter()),
204 /// BTreeMap::from_iter([(9, 100), (16, 200)].into_iter()),
205 /// ];
206 /// assert_eq!(Some(&20), distance(&vec_of_maps, 1, 7));
207 /// assert_eq!(None, distance(&vec_of_maps, 0, 0));
208 /// assert_eq!(None, distance(&vec_of_maps, 3, 0));
209 ///
210 /// let map_of_vecs = HashMap::from_iter([
211 /// (1, vec![3, 4, 5]),
212 /// (7, vec![30, 40, 50]),
213 /// ].into_iter());
214 /// assert_eq!(Some(&5), distance(&map_of_vecs, 1, 2));
215 /// assert_eq!(Some(&40), distance(&map_of_vecs, 7, 1));
216 /// assert_eq!(None, distance(&map_of_vecs, 0, 0));
217 ///
218 /// // complete sparsity
219 /// let map_of_indices = HashMap::from_iter([
220 /// ((0, 1), 14),
221 /// ((3, 6), 42),
222 /// ].into_iter());
223 /// assert_eq!(Some(&14), distance(&map_of_indices, 0, 1));
224 /// assert_eq!(Some(&42), distance(&map_of_indices, 3, 6));
225 /// assert_eq!(None, distance(&map_of_indices, 0, 0));
226 ///
227 /// // uniform distance for all pairs
228 /// let uniform = ScalarAsVec(42);
229 /// assert_eq!(Some(&42), distance(&uniform, 7, 42));
230 ///
231 /// // all disconnected pairs
232 /// let disconnected = EmptyVec::new();
233 /// assert_eq!(None, distance(&disconnected, 7, 42));
234 /// ```
235 fn ref_at<Idx: IntoIndex<DIM>>(&self, index: Idx) -> Option<&T>;
236
237 /// Returns an iterator yielding references to elements of the vector for the given `indices`.
238 ///
239 /// `indices` can be any `Iterator` yielding `Idx` indices, where `Idx` can be any primitive that can be converted into `[usize; DIM]`.
240 /// For instance:
241 /// * `usize` or `(usize)` can be converted into `[usize; 1]`,
242 /// * `(usize, usize)` can be converted into `[usize; 2]`.
243 ///
244 /// This allows to iterate over all funvec implementations in a unified way. Thanks to monomorphization, this abstraction does not have a performance penalty.
245 ///
246 /// # Examples - Dimension 1
247 ///
248 /// ```rust
249 /// use orx_funvec::*;
250 /// use orx_closure::Capture;
251 /// use std::collections::{HashSet, HashMap};
252 ///
253 /// struct Student {
254 /// name: String,
255 /// age: u32,
256 /// }
257 /// impl Student {
258 /// fn new(name: &str, age: u32) -> Self {
259 /// Self { name: name.to_string(), age }
260 /// }
261 /// }
262 ///
263 /// fn average_student_age<S: FunVecRef<1, Student>>(students: &S, ids: &HashSet<usize>) -> u32 {
264 /// let (count, sum) = students.ref_iter_over(ids.iter().copied())
265 /// .flatten()
266 /// .map(|student| student.age)
267 /// .fold((0, 0), |(count, sum), value| (count + 1, sum + value));
268 ///
269 /// if count == 0 { 0 } else { sum / count }
270 /// }
271 ///
272 /// let ids = HashSet::from_iter([0, 2, 3].into_iter());
273 ///
274 /// let stdvec = vec![Student::new("foo", 18), Student::new("bar", 22), Student::new("baz", 16)];
275 /// assert_eq!(17, average_student_age(&stdvec, &ids));
276 ///
277 /// let map = HashMap::from_iter([
278 /// (0, Student::new("foo", 18)),
279 /// (3, Student::new("bar", 20)),
280 /// (10, Student::new("baz", 30)),
281 /// ].into_iter());
282 /// assert_eq!(19, average_student_age(&map, &ids));
283 ///
284 /// let regular = vec![Student::new("foo", 18), Student::new("bar", 22), Student::new("baz", 16)];
285 /// let exchange: HashMap<usize, Student> = HashMap::from_iter([
286 /// (3, Student::new("john", 20)),
287 /// (42, Student::new("doe", 17)),
288 /// ].into_iter());
289 /// let closure = Capture((regular, exchange))
290 /// .fun_option_ref(|(r, x), i: usize| r.get(i).or(x.get(&i)));
291 /// assert_eq!(18, average_student_age(&closure, &ids));
292 ///
293 /// let only_foo = ScalarAsVec(Student::new("foo", 42));
294 /// assert_eq!(42, average_student_age(&only_foo, &ids));
295 ///
296 /// let no_students = EmptyVec::new();
297 /// assert_eq!(0, average_student_age(&no_students, &ids));
298 /// ```
299 ///
300 /// # Examples - Dimension 2
301 ///
302 /// ```rust
303 /// use orx_funvec::*;
304 /// use orx_closure::Capture;
305 /// use std::collections::{BTreeMap, HashMap};
306 ///
307 /// fn total_distance<V, I>(distances: &V, pairs: I) -> u32
308 /// where
309 /// V: FunVecRef<2, u32>,
310 /// I: Iterator<Item = (usize, usize)>
311 /// {
312 /// distances.ref_iter_over(pairs).flatten().sum()
313 /// }
314 ///
315 /// // complete matrix
316 /// let jagged_vecs = vec![
317 /// vec![0, 1, 2, 3],
318 /// vec![10, 11, 12, 13],
319 /// vec![20, 21, 22, 23],
320 /// vec![30, 31, 32, 33],
321 /// ];
322 /// assert_eq!(0 + 1 + 10 + 11,
323 /// total_distance(&jagged_vecs, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
324 /// assert_eq!(12 + 33, total_distance(&jagged_vecs, [(1, 2), (3, 3), (10, 10)].iter().copied()));
325 ///
326 /// // some sparsity in the first or second dimensions
327 /// let vec_of_maps = vec![
328 /// BTreeMap::from_iter([(1, 1), (14, 2)].into_iter()),
329 /// BTreeMap::from_iter([(0, 10), (7, 20)].into_iter()),
330 /// BTreeMap::from_iter([(9, 100), (16, 200)].into_iter()),
331 /// ];
332 /// assert_eq!(1 + 10,
333 /// total_distance(&vec_of_maps, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
334 /// assert_eq!(20 + 100,
335 /// total_distance(&vec_of_maps, [(1, 7), (2, 9)].iter().copied()));
336 ///
337 /// let map_of_vecs = HashMap::from_iter([
338 /// (1, vec![3, 4, 5]),
339 /// (7, vec![30, 40, 50]),
340 /// ].into_iter());
341 /// assert_eq!(3 + 4,
342 /// total_distance(&map_of_vecs, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
343 /// assert_eq!(5 + 40,
344 /// total_distance(&map_of_vecs, [(1, 2), (7, 1)].iter().copied()));
345 ///
346 /// // complete sparsity
347 /// let map_of_indices = HashMap::from_iter([
348 /// ((0, 1), 14),
349 /// ((3, 6), 42),
350 /// ].into_iter());
351 /// assert_eq!(14,
352 /// total_distance(&map_of_indices, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
353 /// assert_eq!(14 + 42,
354 /// total_distance(&map_of_indices, [(0, 1), (3, 6), (100, 100)].iter().copied()));
355 ///
356 /// // uniform distance for all pairs
357 /// let uniform = ScalarAsVec(42);
358 /// assert_eq!(4 * 42,
359 /// total_distance(&uniform, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
360 /// assert_eq!(42 * 3,
361 /// total_distance(&uniform, [(0, 1), (3, 0), (100, 100)].iter().copied()));
362 ///
363 /// // all disconnected pairs
364 /// let disconnected = EmptyVec::new();
365 /// assert_eq!(0,
366 /// total_distance(&disconnected, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
367 /// assert_eq!(0,
368 /// total_distance(&disconnected, [(0, 1), (3, 0), (100, 100)].iter().copied()));
369 /// ```
370 fn ref_iter_over<'a, Idx, IdxIter>(
371 &self,
372 indices: IdxIter,
373 ) -> IterOverRefs<DIM, T, Idx, IdxIter, Self>
374 where
375 Idx: IntoIndex<DIM>,
376 IdxIter: Iterator<Item = Idx> + 'a,
377 {
378 IterOverRefs::new(self, indices)
379 }
380}