card_est_array/impls/
slice_estimator_array.rs

1/*
2 * SPDX-FileCopyrightText: 2024 Matteo Dell'Acqua
3 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4 *
5 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6 */
7
8use super::DefaultEstimator;
9use crate::traits::*;
10use sux::traits::Word;
11use sync_cell_slice::{SyncCell, SyncSlice};
12
13/// An array for estimators implementing a shared [`EstimationLogic`], and whose
14/// backend is a slice.
15///
16/// Note that we need a specific type for arrays of slice backends as one cannot
17/// create a slice of slices.
18pub struct SliceEstimatorArray<L, W, S> {
19    pub(super) logic: L,
20    pub(super) backend: S,
21    _marker: std::marker::PhantomData<W>,
22}
23
24/// A view of a [`SliceEstimatorArray`] as a [`SyncEstimatorArray`].
25pub struct SyncSliceEstimatorArray<L, W, S> {
26    pub(super) logic: L,
27    pub(super) backend: S,
28    _marker: std::marker::PhantomData<W>,
29}
30
31unsafe impl<L, W, S> Sync for SyncSliceEstimatorArray<L, W, S>
32where
33    L: Sync,
34    W: Sync,
35    S: Sync,
36{
37}
38
39impl<L: SliceEstimationLogic<W> + Sync, W: Word, S: AsRef<[SyncCell<W>]> + Sync>
40    SyncEstimatorArray<L> for SyncSliceEstimatorArray<L, W, S>
41{
42    unsafe fn set(&self, index: usize, content: &L::Backend) {
43        debug_assert!(content.as_ref().len() == self.logic.backend_len());
44        let offset = index * self.logic.backend_len();
45        for (c, &b) in self.backend.as_ref()[offset..].iter().zip(content.as_ref()) {
46            // SAFETY: we are the only ones writing to this cell
47            unsafe { c.set(b) }
48        }
49    }
50
51    fn logic(&self) -> &L {
52        &self.logic
53    }
54
55    unsafe fn get(&self, index: usize, backend: &mut L::Backend) {
56        debug_assert!(backend.as_ref().len() == self.logic.backend_len());
57        let offset = index * self.logic.backend_len();
58        for (b, c) in backend
59            .iter_mut()
60            .zip(self.backend.as_ref()[offset..].iter())
61        {
62            // SAFETY: we are the only ones reading from this cell
63            *b = unsafe { c.get() }
64        }
65    }
66
67    unsafe fn clear(&self) {
68        self.backend
69            .as_ref()
70            .iter()
71            .for_each(|c| unsafe { c.set(W::ZERO) })
72    }
73
74    fn len(&self) -> usize {
75        self.backend.as_ref().len() / self.logic.backend_len()
76    }
77}
78
79impl<L: SliceEstimationLogic<W>, W, S: AsRef<[W]>> SliceEstimatorArray<L, W, S> {
80    /// Returns the number of estimators in the array.
81    #[inline(always)]
82    pub fn len(&self) -> usize {
83        let backend = self.backend.as_ref();
84        debug_assert!(backend.len() % self.logic.backend_len() == 0);
85        backend.len() / self.logic.backend_len()
86    }
87
88    /// Returns `true` if the array contains no estimators.
89    #[inline(always)]
90    pub fn is_empty(&self) -> bool {
91        self.backend.as_ref().is_empty()
92    }
93}
94
95impl<L: SliceEstimationLogic<W> + Clone + Sync, W: Word, S: AsMut<[W]>> AsSyncArray<L>
96    for SliceEstimatorArray<L, W, S>
97{
98    type SyncEstimatorArray<'a>
99        = SyncSliceEstimatorArray<L, W, &'a [SyncCell<W>]>
100    where
101        Self: 'a;
102
103    fn as_sync_array(&mut self) -> SyncSliceEstimatorArray<L, W, &[SyncCell<W>]> {
104        SyncSliceEstimatorArray {
105            logic: self.logic.clone(),
106            backend: self.backend.as_mut().as_sync_slice(),
107            _marker: std::marker::PhantomData,
108        }
109    }
110}
111
112impl<L, W, S: AsRef<[W]>> AsRef<[W]> for SliceEstimatorArray<L, W, S> {
113    fn as_ref(&self) -> &[W] {
114        self.backend.as_ref()
115    }
116}
117
118impl<L, W, S: AsMut<[W]>> AsMut<[W]> for SliceEstimatorArray<L, W, S> {
119    fn as_mut(&mut self) -> &mut [W] {
120        self.backend.as_mut()
121    }
122}
123
124impl<L: SliceEstimationLogic<W>, W: Word> SliceEstimatorArray<L, W, Box<[W]>> {
125    /// Creates a new estimator slice with the provided logic.
126    ///
127    /// # Arguments
128    /// * `logic`: the estimator logic to use.
129    /// * `len`: the number of the estimators in the array.
130    pub fn new(logic: L, len: usize) -> Self {
131        let num_backend_len = logic.backend_len();
132        let backend = vec![W::ZERO; len * num_backend_len].into();
133        Self {
134            logic,
135            backend,
136            _marker: std::marker::PhantomData,
137        }
138    }
139}
140
141impl<L: SliceEstimationLogic<W> + Clone, W: Word, S: AsRef<[W]>> EstimatorArray<L>
142    for SliceEstimatorArray<L, W, S>
143{
144    type Estimator<'a>
145        = DefaultEstimator<L, &'a L, &'a [W]>
146    where
147        Self: 'a;
148
149    #[inline(always)]
150    fn get_backend(&self, index: usize) -> &L::Backend {
151        let offset = index * self.logic.backend_len();
152        &self.backend.as_ref()[offset..][..self.logic.backend_len()]
153    }
154
155    #[inline(always)]
156    fn logic(&self) -> &L {
157        &self.logic
158    }
159
160    #[inline(always)]
161    fn get_estimator(&self, index: usize) -> Self::Estimator<'_> {
162        DefaultEstimator::new(&self.logic, self.get_backend(index))
163    }
164
165    #[inline(always)]
166    fn len(&self) -> usize {
167        self.len()
168    }
169}
170
171impl<L: SliceEstimationLogic<W> + Clone, W: Word, S: AsRef<[W]> + AsMut<[W]>> EstimatorArrayMut<L>
172    for SliceEstimatorArray<L, W, S>
173{
174    type EstimatorMut<'a>
175        = DefaultEstimator<L, &'a L, &'a mut [W]>
176    where
177        Self: 'a;
178
179    #[inline(always)]
180    fn get_backend_mut(&mut self, index: usize) -> &mut L::Backend {
181        let offset = index * self.logic.backend_len();
182        &mut self.backend.as_mut()[offset..][..self.logic.backend_len()]
183    }
184
185    #[inline(always)]
186    fn get_estimator_mut(&mut self, index: usize) -> Self::EstimatorMut<'_> {
187        let logic = &self.logic;
188        // We have to extract manually the backend because get_backend_mut
189        // borrows self mutably, but we need to borrow just self.backend.
190        let offset = index * self.logic.backend_len();
191        let backend = &mut self.backend.as_mut()[offset..][..self.logic.backend_len()];
192
193        DefaultEstimator::new(logic, backend)
194    }
195
196    #[inline(always)]
197    fn clear(&mut self) {
198        self.backend.as_mut().iter_mut().for_each(|v| *v = W::ZERO)
199    }
200}
card_est_array/impls/slice_estimator_array.rs

card_est_array/impls/
slice_estimator_array.rs
