graphrefly_structures/
backend.rs

1//! Pluggable backend traits for reactive data structures (M5.A — D178).
2//!
3//! Each structure delegates storage to a backend trait. Default implementations
4//! use `Vec<T>` / `HashMap<K, V>`. `imbl`-backed persistent backends are
5//! deferred until bench evidence justifies (D178).
6
7use std::collections::HashMap;
8use std::hash::Hash;
9
10// ---------------------------------------------------------------------------
11// LogBackend
12// ---------------------------------------------------------------------------
13
14/// Storage backend for [`crate::ReactiveLog`].
15pub trait LogBackend<T: Clone>: Send + Sync {
16    fn size(&self) -> usize;
17    fn at(&self, index: i64) -> Option<T>;
18    fn append(&mut self, value: T);
19    fn append_many(&mut self, values: Vec<T>);
20    fn clear(&mut self) -> usize;
21    fn trim_head(&mut self, n: usize) -> usize;
22    fn to_vec(&self) -> Vec<T>;
23}
24
25/// Default `Vec`-backed log backend with optional ring-buffer cap.
26pub struct VecLogBackend<T> {
27    data: Vec<T>,
28    max_size: Option<usize>,
29}
30
31impl<T> VecLogBackend<T> {
32    #[must_use]
33    pub fn new(max_size: Option<usize>) -> Self {
34        Self {
35            data: Vec::new(),
36            max_size,
37        }
38    }
39}
40
41impl<T: Clone + Send + Sync> LogBackend<T> for VecLogBackend<T> {
42    fn size(&self) -> usize {
43        self.data.len()
44    }
45
46    fn at(&self, index: i64) -> Option<T> {
47        let len = self.data.len() as i64;
48        let idx = if index < 0 { len + index } else { index };
49        if idx < 0 || idx >= len {
50            None
51        } else {
52            Some(self.data[idx as usize].clone())
53        }
54    }
55
56    fn append(&mut self, value: T) {
57        self.data.push(value);
58        if let Some(max) = self.max_size {
59            if self.data.len() > max {
60                let excess = self.data.len() - max;
61                self.data.drain(..excess);
62            }
63        }
64    }
65
66    fn append_many(&mut self, values: Vec<T>) {
67        self.data.extend(values);
68        if let Some(max) = self.max_size {
69            if self.data.len() > max {
70                let excess = self.data.len() - max;
71                self.data.drain(..excess);
72            }
73        }
74    }
75
76    fn clear(&mut self) -> usize {
77        let count = self.data.len();
78        self.data.clear();
79        count
80    }
81
82    fn trim_head(&mut self, n: usize) -> usize {
83        let actual = n.min(self.data.len());
84        self.data.drain(..actual);
85        actual
86    }
87
88    fn to_vec(&self) -> Vec<T> {
89        self.data.clone()
90    }
91}
92
93// ---------------------------------------------------------------------------
94// ListBackend
95// ---------------------------------------------------------------------------
96
97/// Storage backend for [`crate::ReactiveList`].
98pub trait ListBackend<T: Clone>: Send + Sync {
99    fn size(&self) -> usize;
100    fn at(&self, index: i64) -> Option<T>;
101    fn append(&mut self, value: T);
102    fn append_many(&mut self, values: Vec<T>);
103    fn insert(&mut self, index: usize, value: T);
104    fn insert_many(&mut self, index: usize, values: Vec<T>);
105    /// Remove and return element at `index`. Negative indices count from end.
106    fn pop(&mut self, index: i64) -> Option<T>;
107    fn clear(&mut self) -> usize;
108    fn to_vec(&self) -> Vec<T>;
109}
110
111/// Default `Vec`-backed list backend.
112pub struct VecListBackend<T> {
113    data: Vec<T>,
114}
115
116impl<T> VecListBackend<T> {
117    #[must_use]
118    pub fn new() -> Self {
119        Self { data: Vec::new() }
120    }
121}
122
123impl<T> Default for VecListBackend<T> {
124    fn default() -> Self {
125        Self::new()
126    }
127}
128
129impl<T: Clone + Send + Sync> ListBackend<T> for VecListBackend<T> {
130    fn size(&self) -> usize {
131        self.data.len()
132    }
133
134    fn at(&self, index: i64) -> Option<T> {
135        let len = self.data.len() as i64;
136        let idx = if index < 0 { len + index } else { index };
137        if idx < 0 || idx >= len {
138            None
139        } else {
140            Some(self.data[idx as usize].clone())
141        }
142    }
143
144    fn append(&mut self, value: T) {
145        self.data.push(value);
146    }
147
148    fn append_many(&mut self, values: Vec<T>) {
149        self.data.extend(values);
150    }
151
152    fn insert(&mut self, index: usize, value: T) {
153        self.data.insert(index, value);
154    }
155
156    fn insert_many(&mut self, index: usize, values: Vec<T>) {
157        for (i, v) in values.into_iter().enumerate() {
158            self.data.insert(index + i, v);
159        }
160    }
161
162    fn pop(&mut self, index: i64) -> Option<T> {
163        let len = self.data.len() as i64;
164        let idx = if index < 0 { len + index } else { index };
165        if idx < 0 || idx >= len {
166            None
167        } else {
168            Some(self.data.remove(idx as usize))
169        }
170    }
171
172    fn clear(&mut self) -> usize {
173        let count = self.data.len();
174        self.data.clear();
175        count
176    }
177
178    fn to_vec(&self) -> Vec<T> {
179        self.data.clone()
180    }
181}
182
183// ---------------------------------------------------------------------------
184// MapBackend
185// ---------------------------------------------------------------------------
186
187/// Storage backend for [`crate::ReactiveMap`].
188pub trait MapBackend<K: Clone + Eq + Hash, V: Clone>: Send + Sync {
189    fn size(&self) -> usize;
190    fn has(&self, key: &K) -> bool;
191    fn get(&self, key: &K) -> Option<V>;
192    fn set(&mut self, key: K, value: V);
193    fn set_many(&mut self, entries: Vec<(K, V)>);
194    fn delete(&mut self, key: &K) -> bool;
195    fn delete_many(&mut self, keys: &[K]) -> usize;
196    fn clear(&mut self) -> usize;
197    fn to_vec(&self) -> Vec<(K, V)>;
198}
199
200/// Default `HashMap`-backed map backend.
201pub struct HashMapBackend<K, V> {
202    data: HashMap<K, V>,
203}
204
205impl<K, V> HashMapBackend<K, V> {
206    #[must_use]
207    pub fn new() -> Self {
208        Self {
209            data: HashMap::new(),
210        }
211    }
212}
213
214impl<K, V> Default for HashMapBackend<K, V> {
215    fn default() -> Self {
216        Self::new()
217    }
218}
219
220impl<K: Clone + Eq + Hash + Send + Sync, V: Clone + Send + Sync> MapBackend<K, V>
221    for HashMapBackend<K, V>
222{
223    fn size(&self) -> usize {
224        self.data.len()
225    }
226
227    fn has(&self, key: &K) -> bool {
228        self.data.contains_key(key)
229    }
230
231    fn get(&self, key: &K) -> Option<V> {
232        self.data.get(key).cloned()
233    }
234
235    fn set(&mut self, key: K, value: V) {
236        self.data.insert(key, value);
237    }
238
239    fn set_many(&mut self, entries: Vec<(K, V)>) {
240        for (k, v) in entries {
241            self.data.insert(k, v);
242        }
243    }
244
245    fn delete(&mut self, key: &K) -> bool {
246        self.data.remove(key).is_some()
247    }
248
249    fn delete_many(&mut self, keys: &[K]) -> usize {
250        keys.iter()
251            .filter(|k| self.data.remove(*k).is_some())
252            .count()
253    }
254
255    fn clear(&mut self) -> usize {
256        let count = self.data.len();
257        self.data.clear();
258        count
259    }
260
261    fn to_vec(&self) -> Vec<(K, V)> {
262        self.data
263            .iter()
264            .map(|(k, v)| (k.clone(), v.clone()))
265            .collect()
266    }
267}
268
269// ---------------------------------------------------------------------------
270// IndexBackend
271// ---------------------------------------------------------------------------
272
273/// A row in a reactive index: primary key, secondary sort key, value.
274#[derive(Debug, Clone, PartialEq, Eq)]
275#[cfg_attr(
276    feature = "serde-support",
277    derive(serde::Serialize, serde::Deserialize)
278)]
279pub struct IndexRow<K, V> {
280    pub primary: K,
281    pub secondary: String,
282    pub value: V,
283}
284
285/// Storage backend for [`crate::ReactiveIndex`].
286pub trait IndexBackend<K: Clone + Eq + Hash, V: Clone>: Send + Sync {
287    fn size(&self) -> usize;
288    fn has(&self, primary: &K) -> bool;
289    fn get(&self, primary: &K) -> Option<V>;
290    /// Get the full row (primary + secondary + value) by primary key.
291    fn get_row(&self, primary: &K) -> Option<IndexRow<K, V>>;
292    /// Returns `true` if inserted (new key), `false` if updated.
293    fn upsert(&mut self, primary: K, secondary: String, value: V) -> bool;
294    fn upsert_many(&mut self, rows: Vec<(K, String, V)>) -> usize;
295    fn delete(&mut self, primary: &K) -> bool;
296    fn delete_many(&mut self, primaries: &[K]) -> usize;
297    fn clear(&mut self) -> usize;
298    fn to_ordered(&self) -> Vec<IndexRow<K, V>>;
299    fn to_primary_map(&self) -> Vec<(K, V)>;
300}
301
302/// Default sorted-`Vec` + `HashMap`-backed index backend.
303///
304/// Maintains a sorted Vec of `IndexRow` ordered by `(secondary, primary_str)`
305/// plus a parallel HashMap for O(1) primary lookup.
306pub struct VecIndexBackend<K, V> {
307    rows: Vec<IndexRow<K, V>>,
308    primary_map: HashMap<K, V>,
309    /// Parallel map for O(1) secondary lookup by primary key.
310    secondary_map: HashMap<K, String>,
311}
312
313impl<K, V> VecIndexBackend<K, V> {
314    #[must_use]
315    pub fn new() -> Self {
316        Self {
317            rows: Vec::new(),
318            primary_map: HashMap::new(),
319            secondary_map: HashMap::new(),
320        }
321    }
322}
323
324impl<K, V> Default for VecIndexBackend<K, V> {
325    fn default() -> Self {
326        Self::new()
327    }
328}
329
330impl<K: Clone + Eq + Hash + Send + Sync + ToString, V: Clone + Send + Sync> IndexBackend<K, V>
331    for VecIndexBackend<K, V>
332{
333    fn size(&self) -> usize {
334        self.primary_map.len()
335    }
336
337    fn has(&self, primary: &K) -> bool {
338        self.primary_map.contains_key(primary)
339    }
340
341    fn get(&self, primary: &K) -> Option<V> {
342        self.primary_map.get(primary).cloned()
343    }
344
345    fn get_row(&self, primary: &K) -> Option<IndexRow<K, V>> {
346        let value = self.primary_map.get(primary)?;
347        let secondary = self.secondary_map.get(primary)?;
348        Some(IndexRow {
349            primary: primary.clone(),
350            secondary: secondary.clone(),
351            value: value.clone(),
352        })
353    }
354
355    fn upsert(&mut self, primary: K, secondary: String, value: V) -> bool {
356        let is_new = !self.primary_map.contains_key(&primary);
357        if !is_new {
358            // Remove old row from sorted vec.
359            self.rows.retain(|r| r.primary != primary);
360        }
361        self.primary_map.insert(primary.clone(), value.clone());
362        self.secondary_map
363            .insert(primary.clone(), secondary.clone());
364        let row = IndexRow {
365            primary,
366            secondary,
367            value,
368        };
369        let pos = self
370            .rows
371            .binary_search_by(|r| {
372                r.secondary
373                    .cmp(&row.secondary)
374                    .then_with(|| r.primary.to_string().cmp(&row.primary.to_string()))
375            })
376            .unwrap_or_else(|p| p);
377        self.rows.insert(pos, row);
378        is_new
379    }
380
381    fn upsert_many(&mut self, rows: Vec<(K, String, V)>) -> usize {
382        let mut inserted = 0;
383        for (k, s, v) in rows {
384            if self.upsert(k, s, v) {
385                inserted += 1;
386            }
387        }
388        inserted
389    }
390
391    fn delete(&mut self, primary: &K) -> bool {
392        if self.primary_map.remove(primary).is_some() {
393            self.secondary_map.remove(primary);
394            self.rows.retain(|r| r.primary != *primary);
395            true
396        } else {
397            false
398        }
399    }
400
401    fn delete_many(&mut self, primaries: &[K]) -> usize {
402        primaries.iter().filter(|k| self.delete(k)).count()
403    }
404
405    fn clear(&mut self) -> usize {
406        let count = self.primary_map.len();
407        self.rows.clear();
408        self.primary_map.clear();
409        self.secondary_map.clear();
410        count
411    }
412
413    fn to_ordered(&self) -> Vec<IndexRow<K, V>> {
414        self.rows.clone()
415    }
416
417    fn to_primary_map(&self) -> Vec<(K, V)> {
418        self.primary_map
419            .iter()
420            .map(|(k, v)| (k.clone(), v.clone()))
421            .collect()
422    }
423}
graphrefly_structures/backend.rs

graphrefly_structures/
backend.rs
