orx_v/cached/
cached_vec.rs

1use super::cache::{Cache, DefaultCache};
2use crate::common_trait_helpers::debug::*;
3use crate::{NVec, dim::*};
4use core::fmt::Debug;
5use core::{cell::UnsafeCell, marker::PhantomData};
6
7/// Wraps an `NVec<D, T>` into a cached vector which maintains an internal cache.
8///
9/// Each time an element is requested, the vector first checks the cache:
10/// * if the value is readily available in the cache, the vector returns it,    
11/// * otherwise, it computes its value, caches it for future use and returns it.
12///
13/// The cache is often a simple lookup or map, such as the HashMap. However, it might
14/// be more advanced such as the least frequently used cache. Any internal structure
15/// implementing the [`Cache`] can be used.
16///
17/// The aim of the cached vector is to improve the execution time where computing an
18/// element is expensive. Consider for instance element (i, j) corresponds to the
19/// duration between two addresses i and j on a street network which requires running
20/// an algorithm to compute. Further assume that:
21/// * pre-computing all elements is not justified as we will access only a small portion
22///   of the entire matrix, and
23/// * we do not know ahead of time which indices that we will access.
24///
25/// In such scenarios, [`IntoCached`] trait makes it very convenient to convert a functional
26/// vector into a cached functional vector.
27///
28/// # Examples
29///
30/// ```
31/// use orx_v::*;
32///
33/// // assume an expensive api call to compute distance
34/// fn api_call_to_get_distance(from: usize, to: usize) -> u64 {
35///     match from > to {
36///         true => (from - to) as u64,
37///         false => (to - from) as u64,
38///     }
39/// }
40///
41/// let v2 = V.d2().fun(|[i, j]| api_call_to_get_distance(i, j)).into_cached();
42/// assert_eq!(v2.cache_len(), 0);
43///
44/// // makes the api call; caches and returns the value
45/// assert_eq!(v2.at([0, 3]), 3);
46/// assert_eq!(v2.cache_len(), 1);
47///
48/// // does not repeat the api call; returns the value from the cache
49/// assert_eq!(v2.at([0, 3]), 3);
50/// ```
51///
52/// [`IntoCached`]: crate::IntoCached
53pub struct CachedVec<D, T, V, C = DefaultCache<D, T>>
54where
55    D: Dim,
56    V: NVec<D, T>,
57    C: Cache<D::Idx, T>,
58    T: Copy,
59{
60    pub(super) vec: V,
61    pub(super) cache: UnsafeCell<C>,
62    phantom: PhantomData<(D, T)>,
63}
64
65impl<D, T, V, C> CachedVec<D, T, V, C>
66where
67    D: Dim,
68    V: NVec<D, T>,
69    C: Cache<D::Idx, T>,
70    T: Copy,
71{
72    #[allow(clippy::mut_from_ref)]
73    #[inline(always)]
74    pub(super) unsafe fn entry_or_insert_with(&self, idx: impl IntoIdx<D>) -> &mut T {
75        let cache = unsafe { &mut *self.cache.get() };
76        cache.entry_or_insert_with(idx.into_idx(), |idx| self.vec.at(idx))
77    }
78
79    pub(crate) fn new(vec: V, cache: C) -> Self {
80        Self {
81            vec,
82            cache: cache.into(),
83            phantom: PhantomData,
84        }
85    }
86
87    /// Destructs the cached vec and returns the tuple of the underlying `NVec<D, T>`
88    /// and cache.
89    ///
90    /// Note that a new cached vector can be constructed by re-using the cache by
91    /// calling the [`into_cached_with`] method on the vec.
92    ///
93    /// [`into_cached_with`]: `crate::IntoCached::into_cached_with`
94    pub fn into_inner(self) -> (V, C) {
95        (self.vec, self.cache.into_inner())
96    }
97
98    /// Clears the internal cache of the cached vector; i.e., forgets all cached
99    /// elements.
100    pub fn clean_cache(&mut self) {
101        let cache = unsafe { &mut *self.cache.get() };
102        cache.clear();
103    }
104
105    /// Returns the number of elements which are currently available in the cache.
106    pub fn cache_len(&self) -> usize {
107        let cache = unsafe { &*self.cache.get() };
108        cache.len()
109    }
110}
111
112macro_rules! impl_debug {
113    ($dim:ty, $dbg_fn:ident) => {
114        impl<T, V, C> Debug for CachedVec<$dim, T, V, C>
115        where
116            V: NVec<$dim, T>,
117            C: Cache<<$dim as Dim>::Idx, T>,
118            T: Copy + Debug,
119            Self: NVec<$dim, T>,
120        {
121            fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
122                write!(
123                    f,
124                    "{{ kind: CachedVec, dim: D{}, is_bounded: {}, cache_len: {}, values: ",
125                    <$dim as Dim>::dimension(),
126                    self.is_bounded(),
127                    self.cache_len(),
128                )?;
129                $dbg_fn(f, self)?;
130                write!(f, " }}")
131            }
132        }
133    };
134}
135
136impl_debug!(D1, dbg_values_d1);
137impl_debug!(D2, dbg_values_d2);
138impl_debug!(D3, dbg_values_d3);
139impl_debug!(D4, dbg_values_d4);
orx_v/cached/cached_vec.rs

orx_v/cached/
cached_vec.rs
