dashcache/
arr.rs

1/*!
2Cached immutable arrays, bags, and sets of values
3*/
4
5use super::{CanCollect, Caches};
6use elysees::Arc;
7use erasable::Thin;
8use itertools::Itertools;
9use slice_dst::SliceWithHeader;
10use std::fmt::{self, Debug, Formatter};
11use std::hash::{Hash, Hasher};
12use std::iter::FromIterator;
13use std::ops::Deref;
14
15type ThinArc<H, T> = Thin<Arc<SliceWithHeader<H, T>>>;
16
17/// A cached array satisfying a given predicate `P`
18#[repr(transparent)]
19pub struct CachedArr<A, P = (), H = ()> {
20    ptr: Option<ThinArc<H, A>>,
21    predicate: std::marker::PhantomData<P>,
22}
23
24impl<A, P: EmptyPredicate> Default for CachedArr<A, P> {
25    fn default() -> CachedArr<A, P> {
26        CachedArr::EMPTY
27    }
28}
29
30impl<A: Eq + Deref, P> CanCollect for CachedArr<A, P> {
31    #[inline]
32    fn can_collect(&self) -> bool {
33        if let Some(ptr) = &self.ptr {
34            Thin::with(ptr, |p| p.can_collect())
35        } else {
36            true
37        }
38    }
39    #[inline]
40    fn can_collect_clone(&self) -> bool {
41        if let Some(ptr) = &self.ptr {
42            Thin::with(ptr, |p| p.can_collect_clone())
43        } else {
44            true
45        }
46    }
47}
48
49impl<A: Eq + Deref, P> Caches<[A]> for CachedArr<A, P> {
50    #[inline]
51    fn cached(&self) -> &[A] {
52        self
53    }
54}
55
56impl<A, P, H> Clone for CachedArr<A, P, H> {
57    #[inline]
58    fn clone(&self) -> CachedArr<A, P, H> {
59        CachedArr {
60            ptr: self.ptr.clone(),
61            predicate: self.predicate,
62        }
63    }
64}
65
66impl<A: Deref, P, Q, H> PartialEq<CachedArr<A, P, H>> for CachedArr<A, Q, H> {
67    #[inline]
68    fn eq(&self, other: &CachedArr<A, P, H>) -> bool {
69        let lhs = self.as_slice();
70        let rhs = other.as_slice();
71        if lhs.len() != rhs.len() {
72            return false;
73        }
74        for (l, r) in lhs.iter().zip(rhs.iter()) {
75            if l.deref() as *const A::Target != r.deref() as *const A::Target {
76                return false;
77            }
78        }
79        true
80    }
81}
82
83impl<A: Deref, P, H> Eq for CachedArr<A, P, H> {}
84
85impl<A, P, H> CachedArr<A, P, H> {
86    /// Get the pointer to the first element of this `CachedArr`, or null if there is none (i.e. the slice is empty)
87    #[inline]
88    pub fn as_ptr(&self) -> *const A {
89        self.as_slice()
90            .first()
91            .map(|f| f as *const A)
92            .unwrap_or(std::ptr::null())
93    }
94    /// Get the slice underlying this `CachedArr`
95    #[inline]
96    pub fn as_slice(&self) -> &[A] {
97        self.ptr.as_ref().map(|p| &p.slice).unwrap_or(&[])
98    }
99    /// Iterate over the items of this `CachedArr`
100    #[inline]
101    pub fn iter(&self) -> std::slice::Iter<A> {
102        self.as_slice().iter()
103    }
104    /// Strip the predicate from this `CachedArr`
105    #[inline]
106    pub fn as_arr(&self) -> &CachedArr<A, (), H> {
107        self.coerce_ref()
108    }
109    /// Strip the predicate from this `CachedArr`, consuming it.
110    #[inline]
111    pub fn into_arr(self) -> CachedArr<A, (), H> {
112        self.coerce()
113    }
114    /// Coerce this array into one satisfying another predicate
115    #[inline]
116    pub fn coerce<Q>(self) -> CachedArr<A, Q, H> {
117        CachedArr {
118            ptr: self.ptr,
119            predicate: std::marker::PhantomData,
120        }
121    }
122    /// Coerce this array as a reference into one satisfying another predicate
123    #[inline]
124    pub fn coerce_ref<Q>(&self) -> &CachedArr<A, Q, H> {
125        unsafe { &*(self as *const CachedArr<A, P, H> as *const CachedArr<A, Q, H>) }
126    }
127}
128
129impl<A, P> Debug for CachedArr<A, P>
130where
131    A: Debug,
132{
133    #[inline]
134    fn fmt(&self, fmt: &mut Formatter) -> Result<(), fmt::Error> {
135        Debug::fmt(self.as_slice(), fmt)
136    }
137}
138
139impl<A, P> Hash for CachedArr<A, P>
140where
141    A: Deref,
142{
143    #[inline]
144    fn hash<H: Hasher>(&self, hasher: &mut H) {
145        for value in self.as_slice().iter() {
146            std::ptr::hash(value.deref() as *const _, hasher)
147        }
148    }
149}
150
151impl<A, P> Deref for CachedArr<A, P> {
152    type Target = [A];
153    #[inline]
154    fn deref(&self) -> &[A] {
155        self.as_slice()
156    }
157}
158
159impl<A> CachedArr<A> {
160    /// Create a new cached array from an exact length iterator
161    pub fn from_exact<I: ExactSizeIterator + Iterator<Item = A>>(iter: I) -> CachedArr<A> {
162        if iter.len() == 0 {
163            CachedArr::EMPTY
164        } else {
165            let ptr: Arc<_> = SliceWithHeader::new((), iter);
166            CachedArr {
167                ptr: Some(ptr.into()),
168                predicate: std::marker::PhantomData,
169            }
170        }
171    }
172}
173
174impl<A> From<Vec<A>> for CachedArr<A> {
175    fn from(v: Vec<A>) -> CachedArr<A> {
176        Self::from_exact(v.into_iter())
177    }
178}
179
180impl<A: Clone> From<&'_ [A]> for CachedArr<A> {
181    fn from(v: &[A]) -> CachedArr<A> {
182        Self::from_exact(v.iter().cloned())
183    }
184}
185
186impl<A: Deref> From<Vec<A>> for CachedBag<A> {
187    fn from(mut v: Vec<A>) -> CachedBag<A> {
188        v.sort_unstable_by_key(|a| a.deref() as *const _);
189        CachedArr::<A>::from(v).coerce()
190    }
191}
192
193impl<A: Deref> From<Vec<A>> for CachedSet<A> {
194    fn from(mut v: Vec<A>) -> CachedSet<A> {
195        v.sort_unstable_by_key(|a| (*a).deref() as *const _);
196        v.dedup_by_key(|a| (*a).deref() as *const _);
197        CachedArr::<A>::from(v).coerce()
198    }
199}
200
201impl<A> FromIterator<A> for CachedArr<A> {
202    fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> CachedArr<A> {
203        iter.into_iter().collect_vec().into()
204    }
205}
206
207impl<A: Deref> FromIterator<A> for CachedBag<A> {
208    fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> CachedBag<A> {
209        iter.into_iter().collect_vec().into()
210    }
211}
212
213impl<A: Deref> FromIterator<A> for CachedSet<A> {
214    fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> CachedSet<A> {
215        iter.into_iter().collect_vec().into()
216    }
217}
218
219/// A marker type for a predicate which is true for any empty array
220pub trait EmptyPredicate {}
221
222impl EmptyPredicate for () {}
223
224impl<A, P: EmptyPredicate> CachedArr<A, P> {
225    /// Get a constant empty `CachedArr`
226    pub const EMPTY: CachedArr<A, P> = CachedArr {
227        ptr: None,
228        predicate: std::marker::PhantomData,
229    };
230}
231
232/// A marker type indicating an array which is sorted by address, but may have duplicates
233#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
234pub struct Sorted;
235
236/// A marker trait indicating that `CachedArr`s satisfying this predicate may be used as a bag
237pub trait BagMarker {}
238
239impl BagMarker for Sorted {}
240impl EmptyPredicate for Sorted {}
241
242/// A marker type indicating an array which is strictly sorted by address (i.e. no duplicates)
243#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
244pub struct Uniq;
245
246/// A marker trait indicating that `CachedArr`s satisfying this predicate may be used as a set
247pub trait SetMarker: BagMarker {}
248
249impl BagMarker for Uniq {}
250impl SetMarker for Uniq {}
251impl EmptyPredicate for Uniq {}
252
253impl<A: Deref, P, H> CachedArr<A, P, H> {
254    /// Check if this array is sorted by address
255    pub fn is_sorted(&self) -> bool {
256        self.as_slice()
257            .windows(2)
258            .all(|w| w[0].deref() as *const _ <= w[1].deref() as *const _)
259    }
260    /// Check if this array is strictly sorted by address
261    pub fn is_set(&self) -> bool {
262        self.as_slice()
263            .windows(2)
264            .all(|w| w[0].deref() as *const _ < w[1].deref() as *const _)
265    }
266    /// Try to cast this array into a bag if sorted
267    pub fn try_as_bag(&self) -> Result<&CachedBag<A, H>, &Self> {
268        if self.is_sorted() {
269            Ok(self.coerce_ref())
270        } else {
271            Err(self)
272        }
273    }
274    /// Try to cast this array into a set if strictly sorted
275    pub fn try_as_set(&self) -> Result<&CachedSet<A, H>, &Self> {
276        if self.is_set() {
277            Ok(self.coerce_ref())
278        } else {
279            Err(self)
280        }
281    }
282    /// Sort this array and return it
283    pub fn sorted(&self) -> CachedBag<A>
284    where
285        A: Clone,
286    {
287        CachedBag::from(self.iter().cloned().collect_vec())
288    }
289    /// Sort and deduplicate this array and return it
290    pub fn set(&self) -> CachedSet<A>
291    where
292        A: Clone,
293    {
294        CachedSet::from(self.iter().cloned().collect_vec())
295    }
296    /// Try to cast this array into a bag if sorted
297    pub fn try_into_bag(self) -> Result<CachedBag<A, H>, Self> {
298        if self.is_sorted() {
299            Ok(self.coerce())
300        } else {
301            Err(self)
302        }
303    }
304    /// Try to cast this array into a set if strictly sorted
305    pub fn try_into_set(self) -> Result<CachedSet<A, H>, Self> {
306        if self.is_set() {
307            Ok(self.coerce())
308        } else {
309            Err(self)
310        }
311    }
312}
313
314impl<A: Deref, P: BagMarker, H> CachedArr<A, P, H> {
315    /// Cast this array into a bag
316    pub fn as_bag(&self) -> &CachedBag<A, H> {
317        self.coerce_ref()
318    }
319    /// Cast this array into a bag
320    pub fn into_bag(self) -> CachedBag<A, H> {
321        self.coerce()
322    }
323}
324
325impl<A: Deref, P: SetMarker, H> CachedArr<A, P, H> {
326    /// Cast this array into a set
327    pub fn as_set(&self) -> &CachedSet<A, H> {
328        self.coerce_ref()
329    }
330    /// Cast this array into a set
331    pub fn into_set(self) -> CachedSet<A, H> {
332        self.coerce()
333    }
334}
335
336/// A cached bag of elements
337pub type CachedBag<A, H = ()> = CachedArr<A, Sorted, H>;
338
339impl<A: Deref + Clone, H> CachedBag<A, H> {
340    /// Check whether an item is in this bag. If it is, return a reference.
341    pub fn contains_impl(&self, item: *const A::Target) -> Option<&A> {
342        self.as_slice()
343            .binary_search_by_key(&item, |a| (*a).deref() as *const A::Target)
344            .ok()
345            .map(|ix| &self.as_slice()[ix])
346    }
347    /// Deduplicate this bag into a set
348    pub fn uniq_impl(&self) -> CachedSet<A> {
349        let mut v = self.iter().cloned().collect_vec();
350        v.dedup_by_key(|a| (*a).deref() as *const A::Target);
351        CachedArr::<A>::from(v).coerce()
352    }
353}
354
355impl<A: Deref + Clone> CachedBag<A> {
356    /// Merge two bags
357    pub fn merge_impl(&self, rhs: &CachedBag<A>) -> CachedBag<A> {
358        // Edge cases
359        if rhs.is_empty() {
360            return self.clone();
361        } else if self.is_empty() {
362            return rhs.clone();
363        }
364        let union = self
365            .iter()
366            .merge_by(rhs.iter(), |l, r| {
367                (*l).deref() as *const A::Target <= (*r).deref() as *const A::Target
368            })
369            .cloned()
370            .collect_vec();
371        CachedArr::<A>::from(union).coerce()
372    }
373    /// Take the intersection of two bags
374    pub fn intersect_impl(&self, rhs: &CachedBag<A>) -> CachedBag<A> {
375        // Edge cases
376        if rhs.is_empty() {
377            return rhs.clone();
378        } else if self.is_empty() {
379            return self.clone();
380        }
381        let intersection = self
382            .iter()
383            .merge_join_by(rhs.iter(), |l, r| {
384                ((*l).deref() as *const A::Target).cmp(&((*r).deref() as *const A::Target))
385            })
386            .filter_map(|v| v.both().map(|(l, _)| l))
387            .cloned()
388            .collect_vec();
389        CachedArr::<A>::from(intersection).coerce()
390    }
391}
392
393impl<A: Deref + Clone, P: BagMarker, H> CachedArr<A, P, H> {
394    /// Check whether an item is in this bag. If it is, return a reference.
395    pub fn contains(&self, item: *const A::Target) -> Option<&A> {
396        self.coerce_ref().contains_impl(item)
397    }
398}
399
400impl<A: Deref + Clone, P: BagMarker> CachedArr<A, P> {
401    /// Merge two bags
402    #[inline]
403    pub fn merge<Q: BagMarker>(&self, rhs: &CachedArr<A, Q>) -> CachedBag<A> {
404        self.coerce_ref().merge_impl(rhs.coerce_ref())
405    }
406    /// Take the intersection of two bags
407    #[inline]
408    pub fn intersect<Q: BagMarker>(&self, rhs: &CachedArr<A, Q>) -> CachedArr<A, P> {
409        self.coerce_ref().intersect_impl(rhs.coerce_ref()).coerce()
410    }
411    /// Deduplicate this bag into a set
412    #[inline]
413    pub fn uniq(&self) -> CachedSet<A> {
414        self.coerce_ref().uniq_impl()
415    }
416}
417
418/// A cached set of elements
419pub type CachedSet<A, H = ()> = CachedArr<A, Uniq, H>;
420
421impl<A: Deref + Clone> CachedSet<A> {
422    /// Take the union of two sets
423    pub fn union_impl(&self, rhs: &CachedSet<A>) -> CachedSet<A> {
424        // Edge cases
425        if rhs.is_empty() {
426            return self.clone();
427        } else if self.is_empty() {
428            return rhs.clone();
429        }
430        let union = self
431            .iter()
432            .merge_join_by(rhs.iter(), |l, r| {
433                ((*l).deref() as *const A::Target).cmp(&((*r).deref() as *const A::Target))
434            })
435            .map(|v| v.reduce(|l, _| l))
436            .cloned()
437            .collect_vec();
438        CachedArr::<A>::from(union).coerce()
439    }
440}
441
442impl<A: Deref + Clone, P: SetMarker> CachedArr<A, P> {
443    /// Take the union of two sets
444    pub fn union<Q: SetMarker>(&self, rhs: &CachedArr<A, Q>) -> CachedSet<A> {
445        self.coerce_ref().union_impl(rhs.coerce_ref())
446    }
447}
dashcache/arr.rs

dashcache/
arr.rs
