cljrs_value/collections/
queue.rs

1use std::sync::Arc;
2
3use crate::Value;
4use crate::collections::list::PersistentList;
5use crate::collections::vector::PersistentVector;
6
7/// An immutable FIFO queue.
8///
9/// Uses a front list (for dequeue) and a rear vector (for enqueue).
10/// Amortized O(1) for both operations.
11#[derive(Debug, Clone)]
12pub struct PersistentQueue {
13    front: Arc<PersistentList>,
14    rear: PersistentVector,
15    count: usize,
16}
17
18impl PersistentQueue {
19    pub fn empty() -> Self {
20        Self {
21            front: Arc::new(PersistentList::empty()),
22            rear: PersistentVector::empty(),
23            count: 0,
24        }
25    }
26
27    pub fn new(front: PersistentList, rear: PersistentVector) -> Self {
28        let count = front.count() + rear.count();
29        Self {
30            front: Arc::new(front.clone()),
31            rear: rear.clone(),
32            count,
33        }
34    }
35
36    pub fn count(&self) -> usize {
37        self.count
38    }
39
40    pub fn is_empty(&self) -> bool {
41        self.count == 0
42    }
43
44    /// Add an element to the back of the queue.
45    pub fn conj(&self, val: Value) -> Self {
46        Self {
47            front: Arc::clone(&self.front),
48            rear: self.rear.conj(val),
49            count: self.count + 1,
50        }
51    }
52
53    /// View the front element without removing it.
54    pub fn peek(&self) -> Option<&Value> {
55        if self.front.is_empty() {
56            self.rear.nth(0)
57        } else {
58            self.front.first()
59        }
60    }
61
62    /// Remove the front element, returning the new queue.
63    pub fn pop(&self) -> Option<Self> {
64        if self.count == 0 {
65            return None;
66        }
67        if !self.front.is_empty() {
68            let new_front = Arc::new((*self.front.rest()).clone());
69            // If front is now empty, move rear to front.
70            if new_front.is_empty() && !self.rear.is_empty() {
71                let new_front = Arc::new(PersistentList::from_iter(self.rear.iter().cloned()));
72                return Some(Self {
73                    front: new_front,
74                    rear: PersistentVector::empty(),
75                    count: self.count - 1,
76                });
77            }
78            return Some(Self {
79                front: new_front,
80                rear: self.rear.clone(),
81                count: self.count - 1,
82            });
83        }
84        // Front is empty — rear has the items.
85        let new_front = Arc::new(PersistentList::from_iter(self.rear.iter().cloned()));
86        let new_front_rest = new_front.rest();
87        Some(Self {
88            front: new_front_rest,
89            rear: PersistentVector::empty(),
90            count: self.count - 1,
91        })
92    }
93
94    /// Iterate over elements from front to back.
95    pub fn iter(&self) -> impl Iterator<Item = &Value> {
96        self.front.iter().chain(self.rear.iter())
97    }
98}
99
100impl PartialEq for PersistentQueue {
101    fn eq(&self, other: &Self) -> bool {
102        if self.count != other.count {
103            return false;
104        }
105        self.iter().zip(other.iter()).all(|(a, b)| a == b)
106    }
107}
108
109impl cljrs_gc::Trace for PersistentQueue {
110    fn trace(&self, visitor: &mut cljrs_gc::MarkVisitor) {
111        // front: Arc<PersistentList> — trace through to find embedded GcPtrs
112        self.front.trace(visitor);
113        // rear: PersistentVector — trace normally
114        self.rear.trace(visitor);
115    }
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121    use crate::Value;
122
123    fn int(n: i64) -> Value {
124        Value::Long(n)
125    }
126
127    #[test]
128    fn test_basic_enqueue_dequeue() {
129        let q = PersistentQueue::empty()
130            .conj(int(1))
131            .conj(int(2))
132            .conj(int(3));
133        assert_eq!(q.count(), 3);
134        assert_eq!(q.peek(), Some(&int(1)));
135
136        let q = q.pop().unwrap();
137        assert_eq!(q.peek(), Some(&int(2)));
138        assert_eq!(q.count(), 2);
139
140        let q = q.pop().unwrap();
141        assert_eq!(q.peek(), Some(&int(3)));
142
143        let q = q.pop().unwrap();
144        assert!(q.is_empty());
145        assert!(q.pop().is_none());
146    }
147
148    #[test]
149    fn test_fifo_order() {
150        let q = PersistentQueue::empty()
151            .conj(int(10))
152            .conj(int(20))
153            .conj(int(30));
154        let items: Vec<_> = q.iter().cloned().collect();
155        assert_eq!(items, vec![int(10), int(20), int(30)]);
156    }
157}
cljrs_value/collections/queue.rs

cljrs_value/collections/
queue.rs
