orx_funvec/funvec_val.rs
1use crate::{index::IntoIndex, iter_over_val::IterOverValues};
2
3/// Trait to provide abstraction over `DIM`-dimensional vectors allowing 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 at<Idx: IntoIndex<DIM>>(&self, index: Idx) -> Option<T>`.
9///
10/// # Examples
11///
12/// ## Dimension 1 Example
13///
14/// ```rust
15/// use orx_funvec::*;
16/// use orx_closure::Capture;
17/// use std::collections::HashMap;
18///
19/// fn moving_average<V: FunVec<1, i32>>(observations: &V, period: usize) -> Option<i32> {
20/// let last = if period == 0 { None } else { observations.at(period - 1) };
21/// let current = observations.at(period);
22///
23/// match (last, current) {
24/// (None, None) => None,
25/// (None, Some(y)) => Some(y),
26/// (Some(x), None) => Some(x),
27/// (Some(x), Some(y)) => Some((x + y) / 2)
28/// }
29/// }
30///
31/// let period = 2;
32///
33/// let stdvec = vec![10, 11, 12, 13];
34/// assert_eq!(Some(11), moving_average(&stdvec, period));
35///
36/// let map = HashMap::from_iter([(1, 10), (2, 20), (3, 30)].into_iter());
37/// assert_eq!(Some(15), moving_average(&map, period));
38///
39/// let closure = Capture(()).fun(|_, i: usize| Some(if i == 2 { 20 } else { 30 }));
40/// assert_eq!(Some(25), moving_average(&closure, period));
41///
42/// let uniform = ScalarAsVec(42);
43/// assert_eq!(Some(42), moving_average(&uniform, period));
44///
45/// let no_data = EmptyVec::new();
46/// assert_eq!(None, moving_average(&no_data, period));
47/// ```
48///
49/// ## Dimension 2 Example
50///
51/// ```rust
52/// use orx_funvec::*;
53/// use orx_closure::Capture;
54/// use std::collections::{BTreeMap, HashMap};
55///
56/// fn distance<V: FunVec<2, u32>>(distances: &V, a: usize, b: usize) -> Option<u32> {
57/// distances.at([a, b])
58/// }
59///
60/// // complete matrix
61/// let jagged_vecs = vec![
62/// vec![0, 1, 2, 3],
63/// vec![10, 11, 12, 13],
64/// vec![20, 21, 22, 23],
65/// vec![30, 31, 32, 33],
66/// ];
67/// assert_eq!(Some(23), distance(&jagged_vecs, 2, 3));
68/// assert_eq!(None, distance(&jagged_vecs, 2, 4));
69/// assert_eq!(None, distance(&jagged_vecs, 4, 0));
70///
71/// // some sparsity in the first or second dimensions
72/// let vec_of_maps = vec![
73/// BTreeMap::from_iter([(1, 1), (14, 2)].into_iter()),
74/// BTreeMap::from_iter([(0, 10), (7, 20)].into_iter()),
75/// BTreeMap::from_iter([(9, 100), (16, 200)].into_iter()),
76/// ];
77/// assert_eq!(Some(20), distance(&vec_of_maps, 1, 7));
78/// assert_eq!(None, distance(&vec_of_maps, 0, 0));
79/// assert_eq!(None, distance(&vec_of_maps, 3, 0));
80///
81/// let map_of_vecs = HashMap::from_iter([
82/// (1, vec![3, 4, 5]),
83/// (7, vec![30, 40, 50]),
84/// ].into_iter());
85/// assert_eq!(Some(5), distance(&map_of_vecs, 1, 2));
86/// assert_eq!(Some(40), distance(&map_of_vecs, 7, 1));
87/// assert_eq!(None, distance(&map_of_vecs, 0, 0));
88///
89/// // complete sparsity
90/// let map_of_indices = HashMap::from_iter([
91/// ((0, 1), 14),
92/// ((3, 6), 42),
93/// ].into_iter());
94/// assert_eq!(Some(14), distance(&map_of_indices, 0, 1));
95/// assert_eq!(Some(42), distance(&map_of_indices, 3, 6));
96/// assert_eq!(None, distance(&map_of_indices, 0, 0));
97///
98/// // closure to compute distances on the fly rather than to store them
99/// fn get_euclidean_distance(location1: (f64, f64), location2: (f64, f64)) -> u32 {
100/// let (x1, y1) = location1;
101/// let (x2, y2) = location2;
102/// (f64::powf(x1 - x2, 2.0) + f64::powf(y1 - y2, 2.0)).sqrt() as u32
103/// }
104/// let locations = vec![(0.0, 1.0), (3.0, 5.0), (7.0, 2.0), (1.0, 1.0)];
105/// let closure = Capture(&locations).fun(|loc, (i, j): (usize, usize)| {
106/// loc.get(i)
107/// .and_then(|l1| loc.get(j).map(|l2| (l1, l2)))
108/// .map(|(l1, l2)| get_euclidean_distance(*l1, *l2))
109/// });
110/// assert_eq!(Some(0), distance(&closure, 1, 1));
111/// assert_eq!(Some(5), distance(&closure, 0, 1));
112/// assert_eq!(None, distance(&closure, 0, 4));
113///
114/// // uniform distance for all pairs
115/// let uniform = ScalarAsVec(42);
116/// assert_eq!(Some(42), distance(&uniform, 7, 42));
117///
118/// // all disconnected pairs
119/// let disconnected = EmptyVec::new();
120/// assert_eq!(None, distance(&disconnected, 7, 42));
121/// ```
122///
123/// ## Extension
124///
125/// Implementing the trait requires implementation of only the `fn at<Idx: IntoIndex<DIM>>(&self, index: Idx) -> Option<T>` method.
126///
127/// Assume we are working with distance matrices.
128/// In certain scenarios, we observe that we access only a limited number of pairs.
129/// Assuming the distance computation is expensive, we do not want to populate and store the entire matrix.
130/// Instead, we implement a distance provider with caching capabilities.
131/// The goal is to be able to use this provider as a generic distance matrix, and hence, we implement `FunVec<2, _>`.
132///
133/// ```rust
134/// use orx_funvec::*;
135/// use std::{cell::RefCell, collections::HashMap};
136///
137/// type Dist = u32;
138///
139/// struct DistanceProvider {
140/// locations: Vec<(i32, i32)>,
141/// cached: RefCell<HashMap<(usize, usize), Dist>>,
142/// }
143/// impl DistanceProvider {
144/// fn distance(&self, from: usize, to: usize) -> Option<Dist> {
145/// if let Some(cached) = self.cached.borrow().get(&(from, to)) {
146/// return Some(*cached);
147/// }
148/// let locations = self
149/// .locations
150/// .get(from)
151/// .and_then(|l1| self.locations.get(to).map(|l2| (l1, l2)));
152///
153/// if let Some((l1, l2)) = locations {
154/// let (x1, y1) = l1;
155/// let (x2, y2) = l2;
156/// let distance =
157/// ((i32::pow(x1 - x2, 2) + i32::pow(y1 - y2, 2)) as f32).sqrt() as Dist;
158///
159/// // cache computed distance
160/// self.cached.borrow_mut().insert((from, to), distance);
161///
162/// Some(distance)
163/// } else {
164/// None
165/// }
166/// }
167/// }
168///
169/// impl FunVec<2, Dist> for DistanceProvider {
170/// fn at<Idx: IntoIndex<2>>(&self, index: Idx) -> Option<Dist> {
171/// let [from, to] = index.into_index();
172/// self.distance(from, to)
173/// }
174/// }
175///
176/// let locations = vec![(0, 1), (3, 5), (7, 2), (1, 2)];
177/// let distances = DistanceProvider {
178/// locations,
179/// cached: RefCell::new(HashMap::new()),
180/// };
181///
182/// assert_eq!(Some(5), distances.at([0, 1]));
183/// assert_eq!(Some(5), distances.at([0, 1])); // from cache
184/// assert_eq!(None, distances.at([0, 4]));
185///
186/// let pairs = vec![(0, 1), (2, 3)];
187/// assert_eq!(
188/// 11u32,
189/// distances.iter_over(pairs.iter().copied()).flatten().sum()
190/// );
191/// ```
192pub trait FunVec<const DIM: usize, T>
193where
194 T: Clone + Copy,
195{
196 /// Returns the value at the given `index` or `None` if the position is empty.
197 ///
198 /// This allows to access elements of all funvec implementations in a unified way. Thanks to monomorphization, this abstraction does not have a performance penalty.
199 ///
200 /// Note that funvec's are different than, generalization of, traditional vectors since the elements are not necessarily contagious or dense.
201 /// Instead they can be sparse to desired degrees.
202 ///
203 /// Therefore, `at` always returns an optional.
204 ///
205 /// # Examples - Dimension 1
206 ///
207 /// ```rust
208 /// use orx_funvec::*;
209 /// use orx_closure::Capture;
210 /// use std::collections::HashMap;
211 ///
212 /// let stdvec = vec![10, 11, 12, 13];
213 /// assert_eq!(Some(13), stdvec.at(3));
214 /// assert_eq!(None, stdvec.at(4));
215 ///
216 /// let map = HashMap::from_iter([(1, 10), (2, 20)].into_iter());
217 /// assert_eq!(Some(10), map.at(1));
218 /// assert_eq!(None, map.at(0));
219 ///
220 /// let (s, t) = (0, 42);
221 /// let closure = Capture((s, t))
222 /// .fun(|(s, t), i: usize| if i == *s { Some(1) } else if i == *t { Some(-1) } else { None });
223 /// assert_eq!(Some(1), closure.at(0));
224 /// assert_eq!(Some(-1), closure.at(42));
225 /// assert_eq!(None, closure.at(3));
226 ///
227 /// let scalar = ScalarAsVec(42);
228 /// assert_eq!(Some(42), scalar.at(7));
229 /// assert_eq!(Some(42), scalar.at(12));
230 ///
231 /// let empty_vec: EmptyVec<i32> = EmptyVec::new();
232 /// assert_eq!(None, empty_vec.at([7]));
233 /// assert_eq!(None, empty_vec.at([12]));
234 /// ```
235 ///
236 /// # Examples - Dimension 2
237 ///
238 /// ```rust
239 /// use orx_funvec::*;
240 /// use orx_closure::Capture;
241 /// use std::collections::{BTreeMap, HashMap};
242 ///
243 /// fn distance<V: FunVec<2, u32>>(distances: &V, a: usize, b: usize) -> Option<u32> {
244 /// distances.at([a, b])
245 /// }
246 ///
247 /// // complete matrix
248 /// let jagged_vecs = vec![
249 /// vec![0, 1, 2, 3],
250 /// vec![10, 11, 12, 13],
251 /// vec![20, 21, 22, 23],
252 /// vec![30, 31, 32, 33],
253 /// ];
254 /// assert_eq!(Some(23), distance(&jagged_vecs, 2, 3));
255 /// assert_eq!(None, distance(&jagged_vecs, 2, 4));
256 /// assert_eq!(None, distance(&jagged_vecs, 4, 0));
257 ///
258 /// // some sparsity in the first or second dimensions
259 /// let vec_of_maps = vec![
260 /// BTreeMap::from_iter([(1, 1), (14, 2)].into_iter()),
261 /// BTreeMap::from_iter([(0, 10), (7, 20)].into_iter()),
262 /// BTreeMap::from_iter([(9, 100), (16, 200)].into_iter()),
263 /// ];
264 /// assert_eq!(Some(20), distance(&vec_of_maps, 1, 7));
265 /// assert_eq!(None, distance(&vec_of_maps, 0, 0));
266 /// assert_eq!(None, distance(&vec_of_maps, 3, 0));
267 ///
268 /// let map_of_vecs = HashMap::from_iter([
269 /// (1, vec![3, 4, 5]),
270 /// (7, vec![30, 40, 50]),
271 /// ].into_iter());
272 /// assert_eq!(Some(5), distance(&map_of_vecs, 1, 2));
273 /// assert_eq!(Some(40), distance(&map_of_vecs, 7, 1));
274 /// assert_eq!(None, distance(&map_of_vecs, 0, 0));
275 ///
276 /// // complete sparsity
277 /// let map_of_indices = HashMap::from_iter([
278 /// ((0, 1), 14),
279 /// ((3, 6), 42),
280 /// ].into_iter());
281 /// assert_eq!(Some(14), distance(&map_of_indices, 0, 1));
282 /// assert_eq!(Some(42), distance(&map_of_indices, 3, 6));
283 /// assert_eq!(None, distance(&map_of_indices, 0, 0));
284 ///
285 /// // closure to compute distances on the fly rather than to store them
286 /// fn get_euclidean_distance(location1: (f64, f64), location2: (f64, f64)) -> u32 {
287 /// let (x1, y1) = location1;
288 /// let (x2, y2) = location2;
289 /// (f64::powf(x1 - x2, 2.0) + f64::powf(y1 - y2, 2.0)).sqrt() as u32
290 /// }
291 /// let locations = vec![(0.0, 1.0), (3.0, 5.0), (7.0, 2.0), (1.0, 1.0)];
292 /// let closure = Capture(&locations).fun(|loc, (i, j): (usize, usize)| {
293 /// loc.get(i)
294 /// .and_then(|l1| loc.get(j).map(|l2| (l1, l2)))
295 /// .map(|(l1, l2)| get_euclidean_distance(*l1, *l2))
296 /// });
297 /// assert_eq!(Some(0), distance(&closure, 1, 1));
298 /// assert_eq!(Some(5), distance(&closure, 0, 1));
299 /// assert_eq!(None, distance(&closure, 0, 4));
300 ///
301 /// // uniform distance for all pairs
302 /// let uniform = ScalarAsVec(42);
303 /// assert_eq!(Some(42), distance(&uniform, 7, 42));
304 ///
305 /// // all disconnected pairs
306 /// let disconnected = EmptyVec::new();
307 /// assert_eq!(None, distance(&disconnected, 7, 42));
308 /// ```
309 fn at<Idx: IntoIndex<DIM>>(&self, index: Idx) -> Option<T>;
310
311 /// Returns an iterator of elements of the vector for the given `indices`.
312 ///
313 /// `indices` can be any `Iterator` yielding `Idx` indices, where `Idx` can be any usize-primitive that can be converted into `[usize; DIM]`.
314 /// For instance:
315 /// * `usize` or `(usize)` can be converted into `[usize; 1]`,
316 /// * `(usize, usize)` can be converted into `[usize; 2]`.
317 ///
318 /// This allows to iterate over all funvec implementations in a unified way. Thanks to monomorphization, this abstraction does not have a performance penalty.
319 ///
320 /// # Examples - Dimension 1
321 ///
322 /// ```rust
323 /// use orx_funvec::*;
324 /// use orx_closure::Capture;
325 /// use std::collections::HashMap;
326 ///
327 /// fn sum_values<V: FunVec<1, i32>, I: Iterator<Item = usize>>(vec: &V, indices: I) -> i32 {
328 /// vec.iter_over(indices).flatten().sum()
329 /// }
330 ///
331 /// let stdvec = vec![10, 11, 12, 13];
332 /// assert_eq!(23, sum_values(&stdvec, 1..3));
333 ///
334 /// let map = HashMap::from_iter([(1, 10), (8, 20), (12, 200)].into_iter());
335 /// assert_eq!(20, sum_values(&map, (1..10).filter(|x| x % 2 == 0)));
336 ///
337 /// let (s, t) = (0, 42);
338 /// let closure = Capture((s, t))
339 /// .fun(|(s, t), i: usize| if i == *s { Some(10) } else if i == *t { Some(-1) } else { None });
340 /// assert_eq!(9, sum_values(&closure, [0, 21, 42].iter().copied()));
341 ///
342 /// let scalar = ScalarAsVec(21);
343 /// assert_eq!(42, sum_values(&scalar, 1..3));
344 ///
345 /// let empty_vec: EmptyVec<i32> = EmptyVec::new();
346 /// assert_eq!(0, sum_values(&empty_vec, 1..3));
347 /// ```
348 ///
349 /// # Examples - Dimension 2
350 ///
351 /// ```rust
352 /// use orx_funvec::*;
353 /// use orx_closure::Capture;
354 /// use std::collections::{BTreeMap, HashMap};
355 ///
356 /// fn total_distance<V, I>(distances: &V, pairs: I) -> u32
357 /// where
358 /// V: FunVec<2, u32>,
359 /// I: Iterator<Item = (usize, usize)>
360 /// {
361 /// distances.iter_over(pairs).flatten().sum()
362 /// }
363 ///
364 /// // complete matrix
365 /// let jagged_vecs = vec![
366 /// vec![0, 1, 2, 3],
367 /// vec![10, 11, 12, 13],
368 /// vec![20, 21, 22, 23],
369 /// vec![30, 31, 32, 33],
370 /// ];
371 /// assert_eq!(0 + 1 + 10 + 11,
372 /// total_distance(&jagged_vecs, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
373 /// assert_eq!(12 + 33, total_distance(&jagged_vecs, [(1, 2), (3, 3), (10, 10)].iter().copied()));
374 ///
375 /// // some sparsity in the first or second dimensions
376 /// let vec_of_maps = vec![
377 /// BTreeMap::from_iter([(1, 1), (14, 2)].into_iter()),
378 /// BTreeMap::from_iter([(0, 10), (7, 20)].into_iter()),
379 /// BTreeMap::from_iter([(9, 100), (16, 200)].into_iter()),
380 /// ];
381 /// assert_eq!(1 + 10,
382 /// total_distance(&vec_of_maps, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
383 /// assert_eq!(20 + 100,
384 /// total_distance(&vec_of_maps, [(1, 7), (2, 9)].iter().copied()));
385 ///
386 /// let map_of_vecs = HashMap::from_iter([
387 /// (1, vec![3, 4, 5]),
388 /// (7, vec![30, 40, 50]),
389 /// ].into_iter());
390 /// assert_eq!(3 + 4,
391 /// total_distance(&map_of_vecs, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
392 /// assert_eq!(5 + 40,
393 /// total_distance(&map_of_vecs, [(1, 2), (7, 1)].iter().copied()));
394 ///
395 /// // complete sparsity
396 /// let map_of_indices = HashMap::from_iter([
397 /// ((0, 1), 14),
398 /// ((3, 6), 42),
399 /// ].into_iter());
400 /// assert_eq!(14,
401 /// total_distance(&map_of_indices, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
402 /// assert_eq!(14 + 42,
403 /// total_distance(&map_of_indices, [(0, 1), (3, 6), (100, 100)].iter().copied()));
404 ///
405 /// // closure to compute distances on the fly rather than to store them
406 /// fn get_euclidean_distance(location1: (f64, f64), location2: (f64, f64)) -> u32 {
407 /// let (x1, y1) = location1;
408 /// let (x2, y2) = location2;
409 /// (f64::powf(x1 - x2, 2.0) + f64::powf(y1 - y2, 2.0)).sqrt() as u32
410 /// }
411 /// let locations = vec![(0.0, 1.0), (3.0, 5.0), (7.0, 2.0), (1.0, 1.0)];
412 /// let closure = Capture(&locations).fun(|loc, (i, j): (usize, usize)| {
413 /// loc.get(i)
414 /// .and_then(|l1| loc.get(j).map(|l2| (l1, l2)))
415 /// .map(|(l1, l2)| get_euclidean_distance(*l1, *l2))
416 /// });
417 /// assert_eq!(2 * 5,
418 /// total_distance(&closure, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
419 /// assert_eq!(5 + 1,
420 /// total_distance(&closure, [(0, 1), (3, 0), (100, 100)].iter().copied()));
421 ///
422 /// // uniform distance for all pairs
423 /// let uniform = ScalarAsVec(42);
424 /// assert_eq!(4 * 42,
425 /// total_distance(&uniform, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
426 /// assert_eq!(42 * 3,
427 /// total_distance(&uniform, [(0, 1), (3, 0), (100, 100)].iter().copied()));
428 ///
429 /// // all disconnected pairs
430 /// let disconnected = EmptyVec::new();
431 /// assert_eq!(0,
432 /// total_distance(&disconnected, (0..2).flat_map(|i| (0..2).map(move |j| (i, j)))));
433 /// assert_eq!(0,
434 /// total_distance(&disconnected, [(0, 1), (3, 0), (100, 100)].iter().copied()));
435 /// ```
436 fn iter_over<'a, Idx, IdxIter>(
437 &self,
438 indices: IdxIter,
439 ) -> IterOverValues<DIM, T, Idx, IdxIter, Self>
440 where
441 Idx: IntoIndex<DIM>,
442 IdxIter: Iterator<Item = Idx> + 'a,
443 {
444 IterOverValues::new(self, indices)
445 }
446}