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    #[cfg(feature = "no-gc")]
111    fn immutable_children(&self) -> bool {
112        true
113    }
114    fn trace(&self, visitor: &mut cljrs_gc::MarkVisitor) {
115        // front: Arc<PersistentList> — trace through to find embedded GcPtrs
116        self.front.trace(visitor);
117        // rear: PersistentVector — trace normally
118        self.rear.trace(visitor);
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125    use crate::Value;
126
127    fn int(n: i64) -> Value {
128        Value::Long(n)
129    }
130
131    #[test]
132    fn test_basic_enqueue_dequeue() {
133        let q = PersistentQueue::empty()
134            .conj(int(1))
135            .conj(int(2))
136            .conj(int(3));
137        assert_eq!(q.count(), 3);
138        assert_eq!(q.peek(), Some(&int(1)));
139
140        let q = q.pop().unwrap();
141        assert_eq!(q.peek(), Some(&int(2)));
142        assert_eq!(q.count(), 2);
143
144        let q = q.pop().unwrap();
145        assert_eq!(q.peek(), Some(&int(3)));
146
147        let q = q.pop().unwrap();
148        assert!(q.is_empty());
149        assert!(q.pop().is_none());
150    }
151
152    #[test]
153    fn test_fifo_order() {
154        let q = PersistentQueue::empty()
155            .conj(int(10))
156            .conj(int(20))
157            .conj(int(30));
158        let items: Vec<_> = q.iter().cloned().collect();
159        assert_eq!(items, vec![int(10), int(20), int(30)]);
160    }
161}
cljrs_value/collections/queue.rs

cljrs_value/collections/
queue.rs
