rpds/queue/
mod.rs

1use crate::List;
2use alloc::vec::Vec;
3use archery::*;
4use core::borrow::Borrow;
5use core::cmp::Ordering;
6use core::fmt::Display;
7use core::hash::{Hash, Hasher};
8use core::iter::FromIterator;
9
10// TODO Use impl trait instead of this when available.
11type IterPtr<'a, T, P> =
12    core::iter::Chain<crate::list::IterPtr<'a, T, P>, LazilyReversedListIter<'a, T, P>>;
13pub type Iter<'a, T, P> = core::iter::Map<IterPtr<'a, T, P>, fn(&SharedPointer<T, P>) -> &T>;
14
15/// Creates a [`Queue`](crate::Queue) containing the given arguments:
16///
17/// ```
18/// # use rpds::*;
19/// #
20/// let q = Queue::new()
21///     .enqueue(1)
22///     .enqueue(2)
23///     .enqueue(3);
24///
25/// assert_eq!(queue![1, 2, 3], q);
26/// ```
27#[macro_export]
28macro_rules! queue {
29    ($($e:expr),*) => {
30        {
31            #[allow(unused_mut)]
32            let mut q = $crate::Queue::new();
33            $(
34                q.enqueue_mut($e);
35            )*
36            q
37        }
38    };
39}
40
41/// Creates a [`Queue`](crate::Queue) that implements `Sync`, containing the given arguments:
42///
43/// ```
44/// # use rpds::*;
45/// #
46/// let q = Queue::new_sync()
47///     .enqueue(1)
48///     .enqueue(2)
49///     .enqueue(3);
50///
51/// assert_eq!(queue_sync![1, 2, 3], q);
52///
53/// fn is_sync() -> impl Sync {
54///     queue_sync![0, 1, 3]
55/// }
56/// ```
57#[macro_export]
58macro_rules! queue_sync {
59    ($($e:expr),*) => {
60        {
61            #[allow(unused_mut)]
62            let mut q = $crate::Queue::new_sync();
63            $(
64                q.enqueue_mut($e);
65            )*
66            q
67        }
68    };
69}
70
71/// A persistent queue with structural sharing.
72///
73/// # Complexity
74///
75/// Let *n* be the number of elements in the queue.
76///
77/// ## Temporal complexity
78///
79/// | Operation             | Average | Worst case  |
80/// |:--------------------- | -------:| -----------:|
81/// | `new()`               |    Θ(1) |        Θ(1) |
82/// | `enqueue()`           |    Θ(1) |        Θ(1) |
83/// | `dequeue()`           |    Θ(1) |        Θ(n) |
84/// | `dequeue()` amortized |    Θ(1) |        Θ(1) |
85/// | `peek()`              |    Θ(1) |        Θ(1) |
86/// | `len()`               |    Θ(1) |        Θ(1) |
87/// | `clone()`             |    Θ(1) |        Θ(1) |
88/// | iterator creation     |    Θ(1) |        Θ(1) |
89/// | iterator step         |    Θ(1) |        Θ(n) |
90/// | iterator full         |    Θ(n) |        Θ(n) |
91///
92/// # Implementation details
93///
94/// This queue is implemented as described in
95/// [Immutability in C# Part Four: An Immutable Queue](https://goo.gl/hWyMuS).
96#[derive(Debug)]
97pub struct Queue<T, P = RcK>
98where
99    P: SharedPointerKind,
100{
101    in_list: List<T, P>,
102    out_list: List<T, P>,
103}
104
105pub type QueueSync<T> = Queue<T, ArcTK>;
106
107impl<T> QueueSync<T> {
108    #[must_use]
109    pub fn new_sync() -> QueueSync<T> {
110        Queue::new_with_ptr_kind()
111    }
112}
113
114impl<T> Queue<T> {
115    #[must_use]
116    pub fn new() -> Queue<T> {
117        Queue::new_with_ptr_kind()
118    }
119}
120
121impl<T, P> Queue<T, P>
122where
123    P: SharedPointerKind,
124{
125    #[must_use]
126    pub fn new_with_ptr_kind() -> Queue<T, P> {
127        Queue { in_list: List::new_with_ptr_kind(), out_list: List::new_with_ptr_kind() }
128    }
129
130    #[must_use]
131    pub fn peek(&self) -> Option<&T> {
132        if !self.out_list.is_empty() { self.out_list.first() } else { self.in_list.last() }
133    }
134
135    #[must_use]
136    pub fn dequeue(&self) -> Option<Queue<T, P>> {
137        let mut new_queue = self.clone();
138
139        if new_queue.dequeue_mut() { Some(new_queue) } else { None }
140    }
141
142    pub fn dequeue_mut(&mut self) -> bool {
143        if !self.out_list.is_empty() {
144            self.out_list.drop_first_mut();
145            true
146        } else if !self.in_list.is_empty() {
147            core::mem::swap(&mut self.in_list, &mut self.out_list);
148
149            self.out_list.reverse_mut();
150            self.out_list.drop_first_mut();
151            true
152        } else {
153            false
154        }
155    }
156
157    #[must_use]
158    pub fn enqueue(&self, v: T) -> Queue<T, P> {
159        let mut new_queue = self.clone();
160
161        new_queue.enqueue_mut(v);
162
163        new_queue
164    }
165
166    pub fn enqueue_mut(&mut self, v: T) {
167        self.in_list.push_front_mut(v);
168    }
169
170    #[must_use]
171    #[inline]
172    pub fn len(&self) -> usize {
173        self.in_list.len() + self.out_list.len()
174    }
175
176    #[must_use]
177    #[inline]
178    pub fn is_empty(&self) -> bool {
179        self.len() == 0
180    }
181
182    pub fn iter(&self) -> Iter<'_, T, P> {
183        self.iter_ptr().map(|v| v.borrow())
184    }
185
186    fn iter_ptr(&self) -> IterPtr<'_, T, P> {
187        self.out_list.iter_ptr().chain(LazilyReversedListIter::new(&self.in_list))
188    }
189}
190
191impl<T, P> Default for Queue<T, P>
192where
193    P: SharedPointerKind,
194{
195    fn default() -> Queue<T, P> {
196        Queue::new_with_ptr_kind()
197    }
198}
199
200impl<T: PartialEq, P, PO> PartialEq<Queue<T, PO>> for Queue<T, P>
201where
202    P: SharedPointerKind,
203    PO: SharedPointerKind,
204{
205    fn eq(&self, other: &Queue<T, PO>) -> bool {
206        self.len() == other.len() && self.iter().eq(other.iter())
207    }
208}
209
210impl<T: Eq, P> Eq for Queue<T, P> where P: SharedPointerKind {}
211
212impl<T: PartialOrd<T>, P, PO> PartialOrd<Queue<T, PO>> for Queue<T, P>
213where
214    P: SharedPointerKind,
215    PO: SharedPointerKind,
216{
217    fn partial_cmp(&self, other: &Queue<T, PO>) -> Option<Ordering> {
218        self.iter().partial_cmp(other.iter())
219    }
220}
221
222impl<T: Ord, P> Ord for Queue<T, P>
223where
224    P: SharedPointerKind,
225{
226    fn cmp(&self, other: &Queue<T, P>) -> Ordering {
227        self.iter().cmp(other.iter())
228    }
229}
230
231impl<T: Hash, P> Hash for Queue<T, P>
232where
233    P: SharedPointerKind,
234{
235    fn hash<H: Hasher>(&self, state: &mut H) {
236        // Add the hash of length so that if two collections are added one after the other it
237        // doesn't hash to the same thing as a single collection with the same elements in the same
238        // order.
239        self.len().hash(state);
240
241        for e in self {
242            e.hash(state);
243        }
244    }
245}
246
247impl<T, P> Clone for Queue<T, P>
248where
249    P: SharedPointerKind,
250{
251    fn clone(&self) -> Queue<T, P> {
252        Queue { in_list: self.in_list.clone(), out_list: self.out_list.clone() }
253    }
254}
255
256impl<T: Display, P> Display for Queue<T, P>
257where
258    P: SharedPointerKind,
259{
260    fn fmt(&self, fmt: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
261        let mut first = true;
262
263        fmt.write_str("Queue(")?;
264
265        for v in self {
266            if !first {
267                fmt.write_str(", ")?;
268            }
269            v.fmt(fmt)?;
270            first = false;
271        }
272
273        fmt.write_str(")")
274    }
275}
276
277impl<'a, T, P> IntoIterator for &'a Queue<T, P>
278where
279    P: SharedPointerKind,
280{
281    type Item = &'a T;
282    type IntoIter = Iter<'a, T, P>;
283
284    fn into_iter(self) -> Iter<'a, T, P> {
285        self.iter()
286    }
287}
288
289impl<T, P> FromIterator<T> for Queue<T, P>
290where
291    P: SharedPointerKind,
292{
293    fn from_iter<I: IntoIterator<Item = T>>(into_iter: I) -> Queue<T, P> {
294        Queue { out_list: List::from_iter(into_iter), in_list: List::new_with_ptr_kind() }
295    }
296}
297
298pub enum LazilyReversedListIter<'a, T: 'a, P>
299where
300    P: SharedPointerKind,
301{
302    Uninitialized { list: &'a List<T, P> },
303    Initialized { vec: Vec<&'a SharedPointer<T, P>>, current: Option<usize> },
304}
305
306impl<T, P> LazilyReversedListIter<'_, T, P>
307where
308    P: SharedPointerKind,
309{
310    fn new(list: &List<T, P>) -> LazilyReversedListIter<'_, T, P> {
311        LazilyReversedListIter::Uninitialized { list }
312    }
313}
314
315impl<'a, T, P> Iterator for LazilyReversedListIter<'a, T, P>
316where
317    P: SharedPointerKind,
318{
319    type Item = &'a SharedPointer<T, P>;
320
321    fn next(&mut self) -> Option<&'a SharedPointer<T, P>> {
322        match self {
323            LazilyReversedListIter::Uninitialized { list } => {
324                let len = list.len();
325                let mut vec: Vec<&'a SharedPointer<T, P>> = Vec::with_capacity(len);
326
327                for v in list.iter_ptr() {
328                    vec.push(v);
329                }
330
331                *self = LazilyReversedListIter::Initialized {
332                    vec,
333                    current: if len > 0 { Some(len - 1) } else { None },
334                };
335
336                self.next()
337            }
338
339            &mut LazilyReversedListIter::Initialized { ref vec, ref mut current } => {
340                let v = current.map(|i| vec[i]);
341
342                *current = match *current {
343                    Some(0) => None,
344                    Some(i) => Some(i - 1),
345                    None => None,
346                };
347
348                v
349            }
350        }
351    }
352
353    fn size_hint(&self) -> (usize, Option<usize>) {
354        let len = match self {
355            LazilyReversedListIter::Uninitialized { list } => list.len(),
356            LazilyReversedListIter::Initialized { current: Some(i), .. } => i + 1,
357            LazilyReversedListIter::Initialized { current: None, .. } => 0,
358        };
359
360        (len, Some(len))
361    }
362}
363
364impl<T, P> ExactSizeIterator for LazilyReversedListIter<'_, T, P> where P: SharedPointerKind {}
365
366#[cfg(feature = "serde")]
367pub mod serde {
368    use super::*;
369    use ::serde::de::{Deserialize, Deserializer};
370    use ::serde::ser::{Serialize, Serializer};
371
372    impl<T, P> Serialize for Queue<T, P>
373    where
374        T: Serialize,
375        P: SharedPointerKind,
376    {
377        fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
378            serializer.collect_seq(self)
379        }
380    }
381
382    impl<'de, T, P> Deserialize<'de> for Queue<T, P>
383    where
384        T: Deserialize<'de>,
385        P: SharedPointerKind,
386    {
387        fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Queue<T, P>, D::Error> {
388            Deserialize::deserialize(deserializer)
389                .map(|list| Queue { out_list: list, in_list: List::new_with_ptr_kind() })
390        }
391    }
392}
393
394#[cfg(test)]
395mod test;
rpds/queue/mod.rs

rpds/queue/
mod.rs
