uqa_core/memory/
deque.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! A rolling deque whose retained capacity remains charged after prefix removal.
8
9use std::collections::VecDeque;
10
11use super::{replacement, MemoryBudget, MemoryError, MemoryReservation};
12
13#[derive(Debug)]
14pub struct BudgetedDeque<T> {
15    values: VecDeque<T>,
16    memory: MemoryReservation,
17}
18
19impl<T> BudgetedDeque<T> {
20    pub fn new(budget: &MemoryBudget) -> Self {
21        Self {
22            values: VecDeque::new(),
23            memory: budget.empty_reservation(),
24        }
25    }
26
27    pub fn len(&self) -> usize {
28        self.values.len()
29    }
30
31    pub fn is_empty(&self) -> bool {
32        self.values.is_empty()
33    }
34
35    pub fn capacity(&self) -> usize {
36        self.values.capacity()
37    }
38
39    pub fn reserve(&mut self, additional: usize) -> Result<(), MemoryError> {
40        let required = self
41            .len()
42            .checked_add(additional)
43            .ok_or(MemoryError::SizeOverflow)?;
44        if required <= self.values.capacity() {
45            return Ok(());
46        }
47        let (capacity, memory) = replacement::<T>(self.memory.budget(), self.capacity(), required)?;
48        let mut values = VecDeque::new();
49        values.try_reserve_exact(capacity)?;
50        while let Some(value) = self.values.pop_front() {
51            values.push_back(value);
52        }
53        self.values = values;
54        self.memory = memory;
55        Ok(())
56    }
57
58    pub fn push_back(&mut self, value: T) -> Result<(), MemoryError> {
59        self.reserve(1)?;
60        self.values.push_back(value);
61        Ok(())
62    }
63
64    pub fn push_front(&mut self, value: T) -> Result<(), MemoryError> {
65        self.reserve(1)?;
66        self.values.push_front(value);
67        Ok(())
68    }
69
70    pub fn pop_front(&mut self) -> Option<T> {
71        self.values.pop_front()
72    }
73
74    pub fn pop_back(&mut self) -> Option<T> {
75        self.values.pop_back()
76    }
77
78    pub fn iter(&self) -> std::collections::vec_deque::Iter<'_, T> {
79        self.values.iter()
80    }
81}
82
83impl<T> std::ops::Index<usize> for BudgetedDeque<T> {
84    type Output = T;
85
86    fn index(&self, index: usize) -> &T {
87        &self.values[index]
88    }
89}
90
91impl<'a, T> IntoIterator for &'a BudgetedDeque<T> {
92    type Item = &'a T;
93    type IntoIter = std::collections::vec_deque::Iter<'a, T>;
94
95    fn into_iter(self) -> Self::IntoIter {
96        self.iter()
97    }
98}
99
100impl<T> std::ops::IndexMut<usize> for BudgetedDeque<T> {
101    fn index_mut(&mut self, index: usize) -> &mut T {
102        &mut self.values[index]
103    }
104}
uqa_core/memory/deque.rs

uqa_core/memory/
deque.rs
