cljrs_value/collections/
vector.rs

1use crate::Value;
2
3/// An immutable persistent vector backed by `rpds::Vector`.
4#[derive(Debug, Clone)]
5pub struct PersistentVector {
6    inner: rpds::VectorSync<Value>,
7}
8
9impl PersistentVector {
10    pub fn empty() -> Self {
11        Self {
12            inner: rpds::VectorSync::new_sync(),
13        }
14    }
15
16    pub fn from_vector(vector: rpds::VectorSync<Value>) -> Self {
17        Self { inner: vector }
18    }
19
20    pub fn count(&self) -> usize {
21        self.inner.len()
22    }
23
24    pub fn is_empty(&self) -> bool {
25        self.inner.is_empty()
26    }
27
28    /// Append a value. O(log n) amortized.
29    pub fn conj(&self, val: Value) -> Self {
30        Self {
31            inner: self.inner.push_back(val),
32        }
33    }
34
35    /// Return the element at `idx`, or `None` if out of bounds.
36    pub fn nth(&self, idx: usize) -> Option<&Value> {
37        self.inner.get(idx)
38    }
39
40    /// Last element.
41    pub fn peek(&self) -> Option<&Value> {
42        self.inner.last()
43    }
44
45    /// Return a new vector with element `idx` replaced, or appended if `idx == len`.
46    pub fn assoc_nth(&self, idx: usize, val: Value) -> Option<Self> {
47        if idx == self.inner.len() {
48            Some(self.conj(val))
49        } else {
50            Some(Self {
51                inner: self.inner.set(idx, val)?,
52            })
53        }
54    }
55
56    /// Remove the last element. Returns `None` if empty.
57    pub fn pop(&self) -> Option<Self> {
58        Some(Self {
59            inner: self.inner.drop_last()?,
60        })
61    }
62
63    /// Iterate over elements in index order.
64    pub fn iter(&self) -> impl Iterator<Item = &Value> {
65        self.inner.iter()
66    }
67
68    pub fn inner(&self) -> &rpds::VectorSync<Value> {
69        &self.inner
70    }
71}
72
73impl std::iter::FromIterator<Value> for PersistentVector {
74    fn from_iter<I: IntoIterator<Item = Value>>(iter: I) -> Self {
75        let mut v = rpds::VectorSync::new_sync();
76        for item in iter {
77            v = v.push_back(item);
78        }
79        Self { inner: v }
80    }
81}
82
83impl PartialEq for PersistentVector {
84    fn eq(&self, other: &Self) -> bool {
85        if self.inner.len() != other.inner.len() {
86            return false;
87        }
88        self.iter().zip(other.iter()).all(|(a, b)| a == b)
89    }
90}
91
92impl cljrs_gc::Trace for PersistentVector {
93    fn trace(&self, visitor: &mut cljrs_gc::MarkVisitor) {
94        for v in self.inner.iter() {
95            v.trace(visitor);
96        }
97    }
98
99    fn gc_size_extra(&self) -> usize {
100        // Per element: Arc<T> allocation (16 overhead) + thin ptr in leaf node (8).
101        let n = self.inner.len();
102        n * (24 + std::mem::size_of::<Value>())
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109    use crate::Value;
110
111    fn int(n: i64) -> Value {
112        Value::Long(n)
113    }
114
115    #[test]
116    fn test_empty() {
117        let v = PersistentVector::empty();
118        assert!(v.is_empty());
119        assert_eq!(v.count(), 0);
120        assert!(v.nth(0).is_none());
121    }
122
123    #[test]
124    fn test_conj_small() {
125        let v = PersistentVector::from_iter([int(1), int(2), int(3)]);
126        assert_eq!(v.count(), 3);
127        assert_eq!(v.nth(0), Some(&int(1)));
128        assert_eq!(v.nth(2), Some(&int(3)));
129    }
130
131    #[test]
132    fn test_conj_forces_tail_flush() {
133        let v = PersistentVector::from_iter((0..33).map(int));
134        assert_eq!(v.count(), 33);
135        for i in 0..33 {
136            assert_eq!(v.nth(i), Some(&int(i as i64)), "nth({i}) wrong");
137        }
138    }
139
140    #[test]
141    fn test_large() {
142        let n = 1025;
143        let v = PersistentVector::from_iter((0..n).map(|i| int(i as i64)));
144        assert_eq!(v.count(), n);
145        for i in 0..n {
146            assert_eq!(v.nth(i), Some(&int(i as i64)));
147        }
148    }
149
150    #[test]
151    fn test_peek() {
152        let v = PersistentVector::from_iter([int(1), int(2), int(3)]);
153        assert_eq!(v.peek(), Some(&int(3)));
154    }
155
156    #[test]
157    fn test_assoc_nth() {
158        let v = PersistentVector::from_iter([int(1), int(2), int(3)]);
159        let v2 = v.assoc_nth(1, int(99)).unwrap();
160        assert_eq!(v2.nth(0), Some(&int(1)));
161        assert_eq!(v2.nth(1), Some(&int(99)));
162        assert_eq!(v2.nth(2), Some(&int(3)));
163        // Original unchanged.
164        assert_eq!(v.nth(1), Some(&int(2)));
165    }
166
167    #[test]
168    fn test_pop() {
169        let v = PersistentVector::from_iter([int(1), int(2), int(3)]);
170        let v2 = v.pop().unwrap();
171        assert_eq!(v2.count(), 2);
172        assert_eq!(v2.nth(0), Some(&int(1)));
173        assert_eq!(v2.nth(1), Some(&int(2)));
174    }
175
176    #[test]
177    fn test_equality() {
178        let a = PersistentVector::from_iter([int(1), int(2)]);
179        let b = PersistentVector::from_iter([int(1), int(2)]);
180        let c = PersistentVector::from_iter([int(1), int(3)]);
181        assert_eq!(a, b);
182        assert_ne!(a, c);
183    }
184
185    #[test]
186    fn test_iter_order() {
187        let v = PersistentVector::from_iter((0..10).map(|i| int(i as i64)));
188        let items: Vec<_> = v.iter().cloned().collect();
189        assert_eq!(items, (0..10).map(|i| int(i as i64)).collect::<Vec<_>>());
190    }
191}
cljrs_value/collections/vector.rs

cljrs_value/collections/
vector.rs
