cairo_lang_utils/
deque.rs

1extern crate alloc;
2
3use alloc::collections::VecDeque;
4use alloc::vec::Vec;
5use core::ops::{Deref, DerefMut};
6
7/// A deque that implements `salsa::Update` if `T` implements `salsa::Update`.
8/// This is needed to implement `salsa::Update` for `Deque<T>` results of queries.
9#[derive(Clone, Debug, PartialEq, Eq)]
10pub struct Deque<T>(VecDeque<T>);
11
12impl<T> Deref for Deque<T> {
13    type Target = VecDeque<T>;
14
15    fn deref(&self) -> &Self::Target {
16        &self.0
17    }
18}
19
20impl<T> DerefMut for Deque<T> {
21    fn deref_mut(&mut self) -> &mut Self::Target {
22        &mut self.0
23    }
24}
25
26#[cfg(feature = "salsa")]
27unsafe impl<T: salsa::Update> salsa::Update for Deque<T> {
28    unsafe fn maybe_update(old_pointer: *mut Self, new_deque: Self) -> bool {
29        let old_deque: &mut Self = unsafe { &mut *old_pointer };
30
31        // If the lengths are different, just replace the old deque with the new one
32        if old_deque.len() != new_deque.len() {
33            old_deque.clear();
34            old_deque.extend(new_deque);
35            return true;
36        }
37
38        // Otherwise, recursively update each element
39        let mut changed = false;
40        for (old_item, new_item) in old_deque.iter_mut().zip(new_deque) {
41            changed |= unsafe { T::maybe_update(old_item, new_item) };
42        }
43        changed
44    }
45}
46
47impl<T> Default for Deque<T> {
48    fn default() -> Self {
49        Self(VecDeque::new())
50    }
51}
52
53impl<T> Deque<T> {
54    /// Creates a new empty deque.
55    pub fn new() -> Self {
56        Self(VecDeque::new())
57    }
58
59    /// Creates a new empty deque with space for at least `capacity` elements.
60    pub fn with_capacity(capacity: usize) -> Self {
61        Self(VecDeque::with_capacity(capacity))
62    }
63}
64
65impl<T> IntoIterator for Deque<T> {
66    type Item = T;
67    type IntoIter = alloc::collections::vec_deque::IntoIter<T>;
68
69    fn into_iter(self) -> Self::IntoIter {
70        self.0.into_iter()
71    }
72}
73
74impl<T> FromIterator<T> for Deque<T> {
75    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
76        Self(VecDeque::from_iter(iter))
77    }
78}
79
80impl<T, const N: usize> From<[T; N]> for Deque<T> {
81    fn from(arr: [T; N]) -> Self {
82        Self(VecDeque::from(arr))
83    }
84}
85
86impl<T> From<Vec<T>> for Deque<T> {
87    fn from(vec: Vec<T>) -> Self {
88        Self(VecDeque::from(vec))
89    }
90}
91
92impl<T> From<Deque<T>> for Vec<T> {
93    fn from(deque: Deque<T>) -> Self {
94        deque.0.into()
95    }
96}
cairo_lang_utils/deque.rs

cairo_lang_utils/
deque.rs
