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 new_deque = new_deque;
30        let old_deque: &mut Self = unsafe { &mut *old_pointer };
31
32        // If the lengths are different, just replace the old deque with the new one
33        if old_deque.len() != new_deque.len() {
34            old_deque.clear();
35            old_deque.extend(new_deque);
36            return true;
37        }
38
39        // Otherwise, recursively update each element
40        let mut changed = false;
41        for (old_item, new_item) in old_deque.iter_mut().zip(new_deque) {
42            changed |= unsafe { T::maybe_update(old_item, new_item) };
43        }
44        changed
45    }
46}
47
48impl<T> Default for Deque<T> {
49    fn default() -> Self {
50        Self(VecDeque::new())
51    }
52}
53
54impl<T> Deque<T> {
55    /// Creates a new empty deque.
56    pub fn new() -> Self {
57        Self(VecDeque::new())
58    }
59
60    /// Creates a new empty deque with space for at least `capacity` elements.
61    pub fn with_capacity(capacity: usize) -> Self {
62        Self(VecDeque::with_capacity(capacity))
63    }
64}
65
66impl<T> IntoIterator for Deque<T> {
67    type Item = T;
68    type IntoIter = alloc::collections::vec_deque::IntoIter<T>;
69
70    fn into_iter(self) -> Self::IntoIter {
71        self.0.into_iter()
72    }
73}
74
75impl<T> FromIterator<T> for Deque<T> {
76    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
77        Self(VecDeque::from_iter(iter))
78    }
79}
80
81impl<T, const N: usize> From<[T; N]> for Deque<T> {
82    fn from(arr: [T; N]) -> Self {
83        Self(VecDeque::from(arr))
84    }
85}
86
87impl<T> From<Vec<T>> for Deque<T> {
88    fn from(vec: Vec<T>) -> Self {
89        Self(VecDeque::from(vec))
90    }
91}
92
93impl<T> From<Deque<T>> for Vec<T> {
94    fn from(deque: Deque<T>) -> Self {
95        deque.0.into()
96    }
97}
cairo_lang_utils/deque.rs

cairo_lang_utils/
deque.rs
